Harris Corner Detector

Harris corner detector 를 이야기 하기전에 먼저 Moravec corner detector 에 대해 언급을 해야한다. Harris corner detector 는 H. Moravec (1980) 이 제안한 corner detector 를 개선한 것이기 때문에 배경을 알고 가면 더 쉽게 이해가 된다. 사실 나도 이 논문을 읽어보진 않았다.

Moravec corner detector 의 핵심은 조그만 사각형 윈도우를 모든 방향으로 45도 간격으로 이동하면서 얻은 값을 가지고 코너가 있는지 여부를 판단하는 것이다. 물론 여기에는 엣지edge도 포함이 된다. 왜 45도가 되는지는 금방 알 수 있다. 모든 방향으로 1픽셀씩 움직으면 결국 8방향 45도 간격으로 밖에 되지 않기 때문이다. 실제로는 4가지 변위만 측정

Flat
Flat
Edge
Edge
Corner
Corner
E(u,v) = \sum\limits_{x,y}^{} w(x,y)[I(x+u,y+v)-I(x,y)]^2 (1)
window function w(x,y)=binary window

위의 그림과 식 (1)이 Moravec corner detector 이다. I는 이미지이고, w는 윈도우 함수이다. E는 (u,v)를 이동해가면서 intensity 변화량을 검출한 결과이다. (u,v)를 (1,0), (1,1), (0,1), (-1,1) 로 바꿔가며 네가지 변위를 측정해서 \mathbf{min}(E)의 local maxima 를 탐색한다. 그러나 위의 그림에서 보듯이 Moravec 은 아래와 같은 몇가지 문제를 안고 있다.

  1. 노이즈에 취약하다 – binary window function
  2. 45도 각도의 엣지만을 고려할 수 있다 – (u,v)이동 변위의 고정된 4개 픽셀 값
  3. \mathbf{min}(E) 값만을 가지고 검출한다

이 문제를 해결한 것이 바로 Harris corner detector 다. Harris 는 위에서 언급한 Moravec 의 3가지 문제점에 대한 개선방안을 제시했다.

  1. 노이즈에 취약하다 – gaussian window function 사용

    2. w(x,y)=e^{-\frac{(x^2+y^2)}{2\sigma^2}} (2)
    window function w(x,y)=gaussian window

    즉, 가우시안을 윈도우 함수로 사용해서 노이즈에 대한 민감도를 낮췄다.

  2. 45도 각도의 엣지만을 고려할 수 있다 – 테일러 확장Taylor’s expansion으로 (u,v)의 미소변위에 대해 측정 가능


    3. 기존의 픽셀단위 이동으로는 엣지의 방향을 45도 간격으로 밖에 구할 수 없었다. 이를 해결하기 위해 Moravec 이 제안한 식 (1) 을 테일러 시리즈로 확장해서 엣지의 방향을 보다 정확하게 찾아낼 수 있도록 개선했다. 테일러 확장Taylor expansion한 결과는 식 (3) 과 같다. 2D 테일러 시리즈의 자세한 사항은 이전글을 참고하자.

    \begin{array}{rcl} E(u,v) & \approx & \sum\limits_{x,y}^{} w(x,y)[I(x,y) + uI_x + vI_y - I(x,y)]^2 \\ & \approx & \sum\limits_{x,y}^{} w(x,y)[u^2I_x^2 + 2uvI_xI_y + v^2I_y^2] \end{array} (3)

    (3) 을 다시한번 매트릭스 형태로 정렬하면,

    \begin{array}{rcl} E(u,v) & \approx & [u,v] \left( \sum\limits_{x,y}^{} w(x,y) \begin{bmatrix} I_x^2 & I_xI_y \\ I_xI_y & I_y^2 \end{bmatrix} \right) \begin{bmatrix} u \\ v \end{bmatrix} \\ \\ & \approx & [u,v]M \begin{bmatrix} u \\ v \end{bmatrix} \end{array} (4)
    where, M = \sum\limits_{x,y}^{} w(x,y) \begin{bmatrix} I_x^2 & I_xI_y \\ I_xI_y & I_y^2 \end{bmatrix}

    (4) 에서 보는것 처럼 모든 (u,v)에 대한 이미지의 모든 점 (x,y)를 고려한다.

  3. \mathbf{min}(E) 값만을 가지고 검출한다


    4. 이 부분은 아직 잘 이해가 안된다. 개념적으로는 Local maxima of \mathbf{min}(E) 값만을 검출하더라도 코너라면 (1,0), (1,1), (0,1), (-1,1) 네 방향에서 모두 크게 나올 것이므로 가능하다. 그러나 나머지 유용한 정보들은 모두 버려지게 된다. 이를 개선한 것이 위의 (4) 이다. 테일러 시리즈로 확장하면서 max of min(E) 가 아니라 모든 점들의 정보를 다 사용하기 때문에 보다 정확한 코너의 방향을 추정할 수 있다.

이제 Harris corner detector 를 어떻게 해석하는지에 대해 살펴보자. (4) 에서 M은 symmetric 이므로 이를 decomposition 하면 아래와 같이 정리된다.

M = Q^{\mathsf{T}} \Lambda Q (5)
where, Q is rotation, \Lambda is Diagonal
\begin{array}{rcl} E(u,v) & \approx & [u,v] Q^{\mathsf{T}} \Lambda Q \begin{bmatrix} u \\ v \end{bmatrix} \\ \\ & \approx & [u',v'] \Lambda \begin{bmatrix} u' \\ v' \end{bmatrix} \\ \\ & \approx & \Lambda_{1,1} (u')^2 + \Lambda_{2,2} (v')^2 \end{array} (6)

(6) 에서 보는바와 같이 E(u,v)는 \Lambda 다시말해 eigen-value 값에 의해 결정이 된다. 이를 수학적으로 판단하기 위한 수식이 바로 (7) 이다.

R = \mathbf{det} M + k (\mathbf{trace} M)^2 (7)
\mathbf{det} M = \lambda_1 \lambda_2
\mathbf{trace} M = \lambda_1 + \lambda_2
k = 0.04 ~ 0.06: empirical constant

\lambda_1과 \lambda_2는 diagonal matrix \Lambda의 eigen-value 이다. 이번에는 여기까지 🙂

참고

Leave a comment