11.3.1 허프 변환을 이용한 직선 검출 방법

직선은 영상에서 찾을 수 있는 많은 특징 중의 하나이며, 영상을 분석함에 있어 중요한 정보를 제공한다. 반도체 검사 시스템에서 직선으로 이루어진 사각형 영역을 찾아내어 검사 결과의 정확도를 향상시킬 수도 있고, 수평이 맞지 않는 영상에서 수평선 또는 수직선 성분을 찾아내어 수평을 맞추기 위한 적절한 각도를 자동으로 찾아낼 수도 있다. 영상에서 직선 성분을 찾기 위해서는 우선 엣지 픽셀의 위치를 찾아내고, 이러한 엣지 픽셀들이 직선의 방정식에 맞게 일렬로 배열되어 있는지를 확인해야 할 것이다.

영상 처리에서 직선을 찾기 위해 가장 널리 사용되는 방법은 허프 변환이다. 허프 변환은 2차원 영상 좌표에서의 직선의 방정식을 파라미터^parameter 공간으로 변환하여 직선을 찾는 알고리즘이다. 일반적으로 2차원 공간에서의 직선의 방정식은 다음과 같이 나타낼 수 있다.

y = ax+b

위 식에서 a는 기울기^slope이고, b는 y 절편^{y intersection}이다. 이 직선의 방정식은 가로축이 x, 세로축이 y인 2차원 xy 좌표 공간에서 정의되어 있으며, a와 b는 직선의 모양을 결정하는 파라미터이다. 만약 이 방정식을 가로축이 a이고, 세로축이 b인 공간에서 정의한다면 어떻게 될까? 즉, 위 방정식을 조금 변형하여 다음과 같이 써 보자.

b = -xa+y

위와 같이 2차원 xy 공간에서의 직선의 방정식을 ab 공간으로 변형하면 재미난 현상을 발견할 수 있다. 2차원 xy 공간에서의 직선은 ab 공간에서 한 점으로 나타나고, 반대로 xy 공간에서 한 점은 ab 공간에서 직선의 형태로 나타난다는 점이다. 허프 변환은 이러한 현상을 이용하여 xy 공간에서의 직선을 찾는다.