해리스(Harris) 알고리즘

해리스(Harris) 코너 알고리즘.

그는 잡음에 대처하기 위해 식(4.1)의 박스형 마스크를 중심에서 멀어질수록 서서히 값이 작아지는 가우시안 마스크 G(y,x)로 대치하였다. 이렇게 하여 식 (4.1)의 제곱차의 합은 식 (4.3)의 가중치 제곱차의 합WSSD(Weighted Sum Of Squared Difference)으로 확장 된다.

\[\textcolor{Black}{ S(v,u)=\sum_y\sum_xG(y,x) \big(f(y+v,x+u)−f(y,x)\big)^2 \quad (4.3) }\]

가장 중요한 문제는 (v,u)를 어떻게 변화시켜 주위를 조사할 것인지에 관한 것이다. 모라벡은 한 화소만 이동시켜 동서남북을 조사하였다. 하지만 이렇게 하면 360˚ 모든 방향을 동등하게 취급한다는 등방성을 만족하지 못한다. 결국 물체가 0˚, 90˚, 180˚, 270˚ 만큼 회전하면 적절히 대처할 수 있지만 32˚나 48˚와 같이 임의의 값만큼 회전하는 경우는 대처하지 못한다. 다시말해 등방성을 만족하지 못해 매우 제한적인 회전 불변성을 지닌다는 뜻이다. 미분을 도입하면 이 문제를 해결할 수 있다. 테일러 확장(Taylor expansion)에 따르면 식 (4.4)가 성립한다. (y,x)로 부터 작은양 (v.u)만큼 이동한점 (y+v, x+u)의 함수값 f(y+v, x+u)는 (y,x)에서 함수값 f(y,x)에 두 방향으로의 증가량인 vdy(y,x)와 udx(y,x)를 더해 준 값으로 근사화 할 수 있다는 뜻. 여기에서 dy(y,x)와 dx(y,x)는 (y,x)에서 도함수 ∂f/∂y 와 ∂f/∂x 의 값을 말한다. 해리스의 논문에서는 이들을 구하기 위해 y방향 마스크 [-1 0 +1]T와 x방향 마스크 [-1 0 +1]을 사용한다. \(\textcolor{Black}{ f(y+v,x+u)≅f(y,x)+vd_y (y,x)+ud_x (y,x) \quad(4.4) }\)

식 (4.4)를 식 (4.3)에 대입한 후 정리하면 식 (4.5)를 얻는다.

\[\textcolor{Black}{ S(v,u)≅\sum_y\sum_x G(y,x)\big(vd_y (y,x)+ud_x (y,x) \big)^2 \quad (4.5) }\]

\(\textcolor{Black}{ d_y (y,x)=d_y, \quad d_x (y,x)= d_x }\) \(\textcolor{Black}{ =\sum_y\sum_x G(y,x)(v^2 d_y^2+2vud_y d_x+u^2 d_x^2) }\) \(\textcolor{Black}{ =\sum_y\sum_x G(y,x)(vd_y+ud_x)^2 }\) \(\textcolor{Black}{ =\sum_y\sum_x G(y,x)(v,u) \begin{pmatrix} d_y^2 && d_y d_x \\ d_y d_x && d_x^2 \end{pmatrix} \begin{pmatrix} v \\ u \end{pmatrix} }\)

\(\textcolor{Black}{ =(v,u)\sum_y\sum_x G(y,x)\begin{pmatrix} d_y^2 &&d_y d_x \\ d_y d_x && d_x^2\end{pmatrix} \begin{pmatrix} v\\u \end{pmatrix} }\) \(\textcolor{Black}{ S(v,u)≅(v u)\begin{pmatrix}G ∗ d_y^2 && G ∗ d_y d_x \\ G ∗ d_y d_x && G ∗ d_x^2 \end{pmatrix} \begin{pmatrix}v\\u\end{pmatrix} = uAu^T }\)

2차 모멘트 행렬

식 (4.6)에 들어있는 행렬 A는 해리스가 제안한 코너 검출 알고리즘에서 핵심적인 역할을 하므로 식(4.7)로 따로 써 보자. \(\textcolor{Black}{ A=\begin{pmatrix}G ∗ d_y^2&&G ∗ d_y d_x\\G ∗ d_y d_x&&G ∗ d_x^2 \end{pmatrix} \quad (4.7) }\) 행렬 A는 자가 공관계(auto-correlation) 행렬 또는 2차 모멘트 행렬(second moment matrix)이라 불린다.

특징 가능성 측정

[표 4-1]은 [예제 4-2]에서 사용한 삼각형 영상의 세 점 a, b, c에 대한 행렬 A와 그들의 고유값(eigenvalue)을 보여준다. 이 사례에서 알 수 있듯이 고유값을 보고 세 가지 경우로 나눌 수 있다.

• c와 같이 두 개의 고유값 모두 0이거나 0에 가까우면 그곳은 변화가 거의 없는 곳이다.
• b와 같이 고유값 하나는 크고 다른 하나는 작으면 그곳은 한 방향으로 변화가 있는 에지이다.
• a와 같이 고유값 두 개가 모두 크면 그곳은 여러 방향으로 변화가 있는 지점이다. 그곳이 바로 특징점으로 적합하다.

식 (4.8)은 두 고유값이 모두 클 때만 크므로, 특징점일 가능성을 측정하는 데 훌륭한 역할을 수행한다. 여기에서 k는 상황에 맞게 설정할 수 있는데, 보통 0.04 정도가 적절한 것으로 알려져 있다. \(\textcolor{Black}{ C=λ_1 λ_2−k(λ_1+λ_2 )^2 (4.8) }\) 식(4.7)의 행렬을 \({A=((prrq))}\)이라 하면, 두 고유값의 합 \({λ_1+λ_2=p+q=trace(A)}\)이고, \({λ_1 λ_2=pq−r^2=det⁡(A)}\)이다.

\[\textcolor{Black}{ C=det⁡(A)−k×trace(A)^2=(pq−r^2 )−k(p+q)^2 \quad(4.9) }\]

출처 - Computer Vision