직선 검출 허프 변환

2차원 공간상의 직선을 표현하는 방법중 가장 쉬운 방법은 y = ax+b이다.

a값이 직선의 기울기, b 값이 y축과 만나는 y절편이다.

직선의 방정식을 이용하면 모든 직선을 실수 a와 b의 조합으로 나타낼 수 있으며, 입력 영상에 나타날 수 있는

직선이 가지는 a, b값의 범위는 매우 많다.

기울기와, y절편값을 조절하면 수많은 직선을 만들 수 있다. 

따라서 직선을 찾기 위해 이 모든 값을 조사하는건 현실적으로 불가능하다.

이 문제를 해결하기 위해 사용하는 방법이 바로 허프 변환(Hough Transform)이다.

좀더 효율적으로 변수를 조합하여 직선을 표현하여 문제를 해결하는 것이다.

허프 변환은 직선 뿐만 아니라 2차원 평면, 원, 3차원 공간평면 등 다양한 도형에 대해 적용이 가능하다.

허프 변환은 아주 신기한 방법이다. 직선의 방정식을 x, y 극좌표계에서 a값(기울기)와 b(y절편)을 아래와 같은

극좌표계로 변형했을때 같은 기울기를 갖는 직선은 한점에서 만난다는 점이다.

따라서 이를 이용하면 직선을 구할 수 있다.

직선을 위 그림과 같이 표현하면 ρ는 원점에서부터 직선 까지의 거리를 나타내며, Θ는 y축과 직선에서 수직으로 그린

선의 각도를 나타낸다. 위 직선의 방정식을 이용하면 유한한 범위의 ρ와 Θ값을 이용하여 평면 위의 직선을 표현할 수 있다.

따라서 기존 직선의 방정식을 위와 같은 직선의 방정식으로 변형하면 한정 범위안의 직선을 찾을 수 있을 것이다.

극좌표계를 사용하면 평면 위의 한점(x,y)을 지나는 모든 직선을 ρ와 Θ의 조합으로 표현할 수 있다.

영상에서 모든 경계선 좌표 (x,y)에 대해 위 작업을 수행하면 많은 수의 ρ와 Θ 조합을 얻을 수 있다.

만약 한 점에서 많은 직선이 교차할 경우 하나의 픽셀 에 많은 점이 교차할 것이다. 

이것을 이용하여 같은 직선상의 좌표를 구할 수 있다.

허프 변환을 구현할 때 각도 Θ값의 범위를 0'~360' 사이가 아닌 0'~180'로 하고, ρ 값이 음수 값을 가질 수 있도록 한다.