[ openCV | C++ ] Hough Line Transform 이론편.개념정리.

1. 기본개념

2. 조금 더 깊이(논문)

• FINITE LINE

---

1. 기본개념

허프 변환 - 위키백과, 우리 모두의 백과사전

허프 변환 - 위키백과, 우리 모두의 백과사전

일반적인 1차 직선 방정식은 x, y 평면에서 다음과 같이 표현할 수 있습니다.

 

y=ax+b

 

여기서 결론적으로 먼저 얘기하면, Hough Line Transform 은 x, y 평면 도메인을 r, theta(θ, 각도) 평면으로 변환하는 작업을 의미합니다. 물론, r, theta 평면 데이터를 가지고 우리가 익숙한 x, y 평면으로 다시 변환할 수도 있습니다. 이런 작업을 이용해서, 직선을 표현하게 됩니다.

 

r=xcosθ+ysinθ

 

직선을 표현하기 위해 r, theta 요소를 사용.

 

위 그림처럼 한 점을 지나는 모든 직선(x, y가 상수(=고정) 일 경우)을 표현하기 위해 r과 각도 θ를 이용할 수 있습니다. r( ρ(rho)라는 명칭으로도 사용됨.)은 원점에서 타겟 직선까지의 수직거리를 의미하며, 각도 θ 는 타겟직선과 수직을 이루는 직선(원점에서 시작하는 직선)의 반시계 방향 각도를 의미합니다. 

x, y 평면에서 한 점을 지나는 모든 직선을 r, θ 요소를 사용하여 r, θ평면에 그 형태를 표시할 수 있습니다. 이때 한 점을 기준으로 회전하여 서로 다른 직선으로써 구별할 수 있는 범위는 180도입니다.

(180도를 초과하면 다시 +0도부터 시작되는 거 다들 아시죠? 삼각함수 시간에 배웠을 거 같네요. +π/2)

 

아래 그림과 같이 한 점에 대해 직선이 회전할 경우 r, θ평면에서 수직거리 r, 각도 θ 값이 어떻게 표시되는지 확인할 수 있습니다. r, θ 도메인으로 변환했을 때 함수의 형상은 사인 함수 형상을 갖게 됩니다. 각 직선에 대해서 어떻게 표시되는지 가만히 한번 비교해보면 좋을 것 같습니다.

 

좌 : 한 점 A에 대해서 직선을 회전 시킴. 우 : 한 점에 대한 r,θ 곡선 ? 정도로 말할 수 있을것 같습니다.

 

또한 아래와 같이 x, y평면에서 서로 다른 점을 r, θ평면에 표현할 수 있으며, 오른쪽 그림처럼 여러 개의 서로 다른 사인 함수 형상의 그래프로 표현될 수 있습니다. 

 

좌 : x,y 평면에서 한 직선을 통과하는 다수의 포인트, 우 : 좌의 각 포인트를 r, θ평면으로 변환한 결과.

 

r, θ 평면에서 서로 다른 곡선으로 교점이 발생할 수 있는데요. 이 교점은 (x,y 평면의)각 포인트에서 발생한 직선, 즉, 특정 각도와 수직거리가 같을 경우, Hough 평면(r,θ)으로 변환된 곡선으로부터 교점을 형성합니다.(한국말이 제일 어려운것 같습니다.) 이 부분을 역으로 해석하면, r, θ평면에서 생성된 교점은 (x, y평면에서) 서로 다른 포인트이지만 r, θ 평면에서 동일한 한 직선을 표현하는 속성(쉽게 말해 기울기와 y절편과 같은 개념을 가지게 됨.)을 가지게 됩니다. 이 특정 속성을 이용해서, x, y 평면의 직선 방정식으로 재 정의할 수 있을 것 같습니다.

코드 구현의 opencv 라이브러리에서는 어떤 것을 목표로 하는지, 또 어떤 데이터가 입력이 되고 출력은 어떤 형태를 목적으로 하는지에 따라서 활용방법이 달라지지 않을까? 하는 생각이 듭니다. 

 

2. 조금 더 깊이(논문)

Line Detection by Hough transformation

논문에서 설명하고 있는 hough line transform의 단계는 다음과 같습니다.

 

논문 중 발췌 내용. 이미지에서 검출된 직선은 r,θ평면에서 가장 밝기가 높은 교점(x,y평면에서 직선의 속성을 표현)으로 표현 된다.

자세한 설명은 논문을 참고하세요. 내용이 많이 길지는 않습니다. 개념정리하기 위해 읽어보면 좋을 것 같네요.

 

FINITE LINE(논문 내용 중)

 

종래의 일반 기법에서는 라인을 검출할 때 r, θ 값 만 이용해서 알고리즘에 적용했기 때문에, 검출된 라인의 길이 값에 대한 조절은 하지 못했다고 합니다. 그래서 검출되는 라인은 모두 infinite(무한 직선) 한 형태로 찾아주게 되고, 이미지에 표시도 무한하게만 표현되는 것을 확인할 수 있습니다. 만약 finite 한 직선을 사용하고자 한다면 검출된 라인에 컨디션 부여해서 설정할 수 있다고 합니다.

첫 번째 방법. 라인 검출에 사용된 모든 픽셀 포인트 데이터를 저장하고, 경계 값을 사용자가 지정해서 유한한 직선을 생성한다. 단점은 포인트 데이터를 모두 사용하기 때문에 메모리 사용이 과다하게 발생한다고 합니다.

두 번째 방법. 검출된 infinite 직선들 중에서, finite 한 직선을 찾는 방법 확률적으로 탐색하는 방법입니다. 이 부분이 주류를 이루는 방법이라고 생각되며,  Progressive Probabilistic Hough Transform(PPHT)라는 방법을 이용합니다. 이 방법은 랜덤으로 픽셀 데이터에 대해서 직선 여부를 탐색하는 방법으로, 빠르게 직선을 찾아 줄 수 있다고 합니다.(이 부분에 대해서는 직선 검출의 한 기법으로서 설명된 부분이기 때문에 코드 구현을 진행하면서 알아보는 게 좋을 것 같네요. )

그리고, 논문에서는 아래 그림과 같이 펌프 부품을 이용해서 finite Lines를 검출하고 있으며, Hough Space 상에서 True Line(finite 직선)으로 6개 직선이 검출된 것을 확인할 수 있습니다. Hough Transform 그래프에서 6개의 피크 값을 구해서 직선으로 재 변환한 것 같습니다.

 

 

 

논문에서 이 작업은 매틀랩을 이용해서 진행했고, 아래와 같은 함수를 사용했습니다.

 

- hough: Performs the Hough transform on a binary edge image, and returns the accumulator. The resolution of the accumulator used in this worksheet is 1 for both r and θ. 

- houghpeaks: Detects lines by interpreting the accumulator. In this worksheet the threshold was set to 20% of the maximum value in the accumulator, and the suppression neighbourhood was set to approximately 5% of the resolution of r and θ respectively.

- houghlines(무한 직선을 유한 직선으로 변경해주는 함수이다.): Converts infinite lines to finite lines. In this worksheet, the minimum length of a line was set to 30 pixels, and the algorithm was allowed to connect lines through holes of up to 30 pixels.