허프 변환 - 직선

허프 변환은 이미지 속에서 주요 특징 요소 들을 - 직선, 원, 타원, 등등 - 찾는 방법이다.

1959년 Paul Hough가 'bubble chamber' 사진의 기계적 분석을 위해 고안했으며,

1962년 "Method and Means for Recognizing Complex Patterns" 이란 타이틀로 미국 특허를 

획득했다. 더 자세한 이력이나 설명은 위키에 자세히 나와 있다.

우선 기본 원리부터 이해하자.

직선을 수학적으로 표현하는 방법에는 여러 가지가 있다.

( x, y ) 평면에서 기울기 m, 절편 n인 직선은

y = m*x + n.

( x1, y1 ), ( x2, y2 ) 두 점을 지나는 직선은

y - y1 = ( ( y2-y1 ) / ( x2-x1 ) ) *( x - x1 ).

x 절편이 a, y 절편이 b인 직선은 아래와 같다.

아래 그림을 보자.

 

빨간 직선을 절편이 아닌 각도와 거리로 표현하려면 어떻게 해야할까?

빨간 직선의 x 축과 만나는 점을 x1, y 축과 만나는 점을 y1이라 하면  

( x, y ) 평면 상의 한 점 ( x2, y2 )를 위 직선의 방정식에 대입하면

r = x2cosθ +y2sinθ 이 되어 θ 값에 따라 r의 값이 변하는 곡선이 된다.

x 축은 θ가 0이고 -x 축은 180도가 되어 θ가 0 <= θ < pi/2 이 구간이면 ( x2, y2 ) 점을 지나는 

( x, y ) 평면상의 모든 직선을 표현할 수 있다. 

아래 그림을 보면

첫 화면은 (2,2)점을 지나는 기울기가 다른 직선들을 표시한 것이다. 초록색 직선의 경우 θ는 30도 정도 될 것이다.( 원점을 지나며 초록색 직선과 수직인 직선의 x축과의 각도 ), 빨간색 직선은 60도.

두번째 화면은 각 직선들의 ( θ, r ) 평면상의 위치를 표현한 것으로 r = 2cosθ +2sinθ 인 직선에서 각도가 30도로 고정되면 r의 길이도 결정되어 한 점이 된다.

세번째는 각도를 0도 부터 180도까지 1도씩 증가시킨 것으로 sine 곡선이 된다.

( x, y ) 평면 상의 5개 점을(왼쪽 그림) ( θ, r ) 평면에 표현하면(오른쪽 그림) 0도에서 180도로 변함에 따라 r의 값이 변하여 삼각함수 곡선이 5개가 그려진다. 5개의 점이 일직선 상에 있다면 ( θ, r ) 평면의 5개 곡선은 한 점에서 만나게 된다. 위 예의 경우 만나는 지점의 위치는 ( 45, 2.828 ) 이다.  r = xcosθ +ysinθ  직선에 θ=45, r=2.828을 대입하면 2.828 = xcos(45)+ysin(45) 는  y = -x + 4 의 직선을 얻을 수 있다.