7. Hough Transform

1.목적
Hough Transform을 사용하여 이미지에서 직선 혹은 다른 패턴을 추출 할 수 있다.
 
2.이론
Hough Transform은 이미지에서 직선을 추출하는 방법이다.

위의 그림처럼 x-y평면위 직선 상의 한 점은, 직선의 절편 a,b를 변수로 놓았을 때 a-b평면에서의 직선으로 나타낼 수 있다.

여기서 직선 여러 점을 a-b평면으로 옮기면 여러 직선이 나오고, 모든 직선이 지나는 교점은 x-y평면으로 옮기면 인 직선으로 다시 변환된다.

따라서, 두 평면상에 점 <-> 직선의 변환관계가 성립하고.
이것을 이용하여 직선을 추출하는 방법이 Hough Transform이다.

예를 들어, x-y 평면의 엣지는 a-b평면의 한 점으로 지나므로
x-y평면으로 나타낸 이미지의 모든 pixel을 a-b평면으로 옮겨서
그 교점만 추출한다면, 원본이미지의 직선 엣지를 쉽게 파악할 수 있다.

교점으로 표현 된다.

위의 방식에서 기울기 a의 범위가 ∞ 까지 이므로, a = ∞ 에 가까울 경우에는 구현상에 문제가 생긴다.

이 문제를 해결하기 위해 polar coordinate를 도입하면 각도 0< θ < π
이므로, 유한한 범위에서 표현 할 수 있게 된다.

이때, 원점으로부터의 거리, ρ의 범위는 0< ρ <diagonal of image가 된다.
 

실제 구현에서는 위와 같이
①배열을 만들어서
②x-y점의 각 픽셀을 (ρ,θ)의 포물선으로 옮기고
③각 점에 1점씩 부여하여,(voting)
④그 점수가 가장 높은 점을 다시 x-y평면의 직선으로 만드는 방식을 사용한다.

3.알고리즘
 
1. 투표 배열(Hough space)의 모든 값을 0으로 초기화한다.
2. 원본이미지의 모든 pixel을 Hough space(투표배열)로 옮긴다.
3. 옮김과 동시에 1표씩 값을 추가하여 부여한다.
4. threshold를 설정하여 누적 투표 값이 threshold 이상인 점들을(빈도 높은 교차점) x-y 평면으로 옮긴다(옮기면 직선)

참고
- 개리 로스트브라드스키, 에이드리안 캘러. Learning OPEN CV 제대로 배우기. 한빛미디어(2009)
- Google. "hough transform", http://t9t9.com/113
- 나의 옛날 보고서.