3장 에지 검출 - 허프변환(Hough Transform)

허프 변환

- 에지 연결 과정 없이 선분 검출 (전역 연산을 이용한 지각 군집화)

//연결 관계가 명확하지 않거나 잡음으로 인해 작은 조각으로 끊어져 있는 경우 좋다.

//전체 공간을 조사하는 전역연산(global operation)

//일직선 상에 있다고 지각하는 점들을 한 곳으로 모으는 원리 지각 군집화(perceptual grouping), clustring

- 영상 공간 y-x를 기울기 절편 공간 b-a로 매핑

점(y_3, x_3)을 지나는 모든 좌표의 방정식 : y_3 = ax_3+b 

(1, 5)  : 5 = 1a+b  --> b = -1a+5

(2, 3)  : 3 = 2a+b  --> b = -2a+3

(4, 1)  : 1 = 4a+b  --> b = -4a+1

이 세 직선의 교점 (b_1,a_1)로 세 점을 연결한 직선의 방정식을 구할 수 있다. : y = a_1x+b_1

문제1. 수직선의 기울기가 ∞인 문제

- 해결: 극좌표계 사용한다. 

ρ : 편차 , θ : 원점으로 수직인 선의 각

세 점이 만나는 점이 직선의 방정식이다.

ycosθ + xsinθ = ρ

ρ = √(x^2+y^2)sin(θ+α)

θ = α tan^-1(x)

문제2. 세 점이 완벽하게 동일한 직선 위에 놓여 있지 못할 때

이산 공간에 에지 점이 정의되므로 어느 정도의 오류는 필연적으로 발생한다.

- 해결 : ρ-θ공간을 적절한 구간으로 양자화 한다.-->누적 배열(accumulation array)

//오류를 흡수하고 그래프의 자취가 밀집하는 곳을 용이하게 찾는다.

θ와 ρ의 범위는-90도 < θ < 90도,  -D <=ρ < D (D : y-x공간의 원점에서 맞은편 꼭지점 까지 거리)이다.

 

step1. 누적 배열 A를 0으로 초기화 한다.

step2. ycosθ + xsinθ = ρ 그래프가 지나가는 A의 칸을 1증가시킨다.

step3. 모든 에지 점을 처리한다.

step4. A를 조사하여 임계값을 넘는 지역 최대점을 검출한다.

step5. 답

누적 배열을 얼마나 촘촘하게 이산화할지가 문제이다.

- 너무 촘촘하면 방정식이 지나는 자취가 어떤 칸으로 집중되지 못하고 주위로 퍼진다.

- 너무 안 촘촘하면 한 단계의 크기가 너무 커서 직선의 정확도가 떨어진다.

 

허프 변환은 직선의 방정식으로 출력하기 때문에 선분이 필요한 경우에는 양 끝점을 찾는 후처리 과정이 필요하다.

직선에 해당하는 칸으로 매핑된 에지들을 조사하여 끝점을 찾아내는 추가적인 수고를 감소해야한다.

원 검출

3차원 누적 배열 사용

허프 변환 방정식으로 어떠한 도형도 검출할 수 있다.

누적 배열 A를 3차원으로 만들고 a,b,r 세 개로 양자화한다.

 

일종의 군집화 알고리즘이다. clustering

인라이어와 아웃라이어가 심하게 섞여있는 상황에서 인라이어의 군집을 찾아내는 데에도 활용할 수 있는 일반성을 가진 방법론이다.