Hough Transform 허프 변환

허프 변환(Hough Transform)의 기본 개념은 정말 어쩌면 무식한 방법이 아닐까 생각한다.

어떤 점이 주어졌다면, 그 점을 기준으로 그점을 지나는 모든 직선의 방정식의 파라미터를 저장해놓고, 여러개의

점들에 대해 반복하여 파라미터의 빈도수를 누적함으로써, 같은 직선에 속하는 점들이 몇개나 있는지 검사하는

방법이다. 그리하여 많은 점들이 같은 직선상에 존재한다면, 파라미터를 이용하여 직선으로 표현하여 직선을 검출

하는 방법이다.

 

위 그림은 허프변환의 수식에 대한 풀이를 나타낸다. 직선 A는 r이라 표현된 직선 A의 법선 벡터와 만나는 점 x,y라 놓으면, 직선 A의 방정식은 수식 1과 같이 표현할 수 있다.

여기서 수식 1을 극좌표를 이용하여 표현하면 기울기와 y 절편을 극좌표를 이용하여 표현해야하는데, 이 방법이 수식 2~8 까지이다.

그래서 허프 변환의 최종 수식 8 이 나온 것이다.

여기서 x, y는 상수이며, 세타와 로우, 즉 여기서는 r이 되겠죠.

이 수식을 이용하는 방법은, 어떤 점 x, y를 대입하고 세타를 변화시킴으로써 대응되는 r값을 계산 할 수 있을 것이다.

그럼 (세타, r) 을 기준으로하는 좌표 평면을 만들 수 있고, 이런 좌표 평면에 결과로 나온 세타와 r의 좌표에 +1 씩 누적하여 허프 변환의 누적 맵을 만든다.

이렇게 관심있는 모든 점들에 대해서 허프 변환의 누적맵에 누적을 하게 되면, 같은 직선 상에 있는 점들은 어떤 특정한 세타와, r 좌표에 다른 곳보다 많이 +1을 수행하게 되어 누적맵에서 큰 값을 갖게 된다.

그럼 몇개 이상 누적된 세타와 r을 이용해서 직선으로 표현하면, 직선을 검출할 수 있습니다.

이러한 원리가 허프의 기본 원리 입니다.

 

 

Tip

Opencv에서 허프 변환으로 두 직선의 교점을 구하는 방법

두 선의 직선의 방정식을 다음과 같이 표현 할 수 있다.

        * 이를 연립하여 풀기 위해 y= 형태로 정리한다.

        *  xcos(theta1) + ysin(theta1) = rho1

        *  xcos(theta2) + ysin(theta2) = rho2

        *  y= -xcos(theta1)/sin(theta1) + rho1/sin(theta1)

        *  y= -xcos(theta2)/sin(theta2) + rho2/sin(theta2)

        *  

        *  -xcos(theta1)/sin(theta1) + rho1/sin(theta1) = -xcos(theta2)/sin(theta2) + rho2/sin(theta2)

        *  

        *   ( -cos(theta1)/sin(theta1) + cos(theta2)/sin(theta2) )x = rho2/sin(theta2) - rho1/sin(theta1)

        * 따라서 X는

        * x =  [ rho2/sin(theta2) - rho1/sin(theta1) ]  /  ( -cos(theta1)/sin(theta1) + cos(theta2)/sin(theta2) )

theta와 rho는 허프변환을 이용하면 쉽게 구할 수 있다.

다음은 임의의 직선에서 y가 정해졌을때 x를 구하는 수식이다.

   * xcos(theta) + ysin(theta)= rho

        * xcos(theta) = rho-ysin(theta)

        * x = (rho - ysin(theta) ) / cos(theta)