코너 검출 (Corner Detection)

지난 글에서 모서리(edge)와 직선(line)을 검출하는 것을 알아보았다.
이번에는 어떤 물체의 코너(corner)를 검출하는 법을 배워보자.

Sliding Window Method

이미지에서 코너를 찾기 위해, $n\times n $크기의 window로 이미지를 훑어가며 코너를 찾을 것이다.
window가 상하좌우로 움직일 때 특정한 방향으로 움직일 때만 밝기의 변화가 있다면 edge, 모든 방향으로 움직일 때 모두 밝기 변화가 있다면 corner라 생각할 수 있다. (이미지를 참고하면 편하다.)

https://www.researchgate.net/figure/The-basic-idea-of-Harris-corner-detector_fig2_322517116

이를 수식으로 표현하면 다음과 같다.

$$ E(u, v) = \sum_{(x,y)\in W} (I(x+u, y+v) - I(x,y))^2 $$

$E(u,v)$는 어떤 이미지의 $(x,y)$좌표에서 $(u,v)$만큼 이동하였을 때의 밝기 변화의 제곱이다.
이 식을 조금 단순화 해보자. (모르겠으면 그냥 단순화된 식만 봐도 된다.)

테일러급수란 친구가 등장한다.
$$f(x+d) \approx f(x) + \frac{\partial f}{\partial x}d $$

$$I(x+u, y+v) \approx I(x, y) + I_xu + I_yv $$

이를 $E$에 적용하면 다음과 같다.
$$\begin{align} E(u, v) &\approx \sum_{(x,y)\in W} (I(x, y) + I_xu + I_yv - I[x,y])^2 \\
&= \sum_{(x,y)\in W} (I_xu + I_yv)^2 \\
&= \sum_{(x,y)\in W} I_x^2u^2 + 2l_xI_yuv + l_y^2v^2 \end{align}$$

이걸 $M$이라는 Second Moment Matrix를 투입해 다음과 같이 정리한다.

$$ M = \begin{bmatrix} \sum_{x,y \in W} I_x^2 & \sum_{x,y \in W} I_xI_y \\
\sum_{x,y \in W} I_xI_y & \sum_{x,y \in W}I_y^2\end{bmatrix} $$

$$ E(u, v) \approx [u, v]M[u, v]^T$$

이때, $M$ 행렬은 아래와 같이 두 값이 0인 대각행렬로 분해할 수 있다.

$$ M = R^{-1}\begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_2\end{bmatrix}R $$

$\lambda$를 통해 영상의 밝기값이 얼마나 빠르게 변화하는지 알 수 있고, $R$을 통해 밝기값이 변화하는 방향을 알 수 있다.

이제, 비로소 코너를 검출해 보자.

1. 이미지의 모든 픽셀에 대해, 위 행렬 $M$을 구해준다.
2. 만약 $\lambda$ 값이 모두 작다면(즉, 밝기가 모든 방향으로 적게 변화한다면), flat 한 영역이다.
3. $\lambda$ 값 중 하나만 크다면(한 방향으로 밝기가 크게 변화), edge이다.
4. $\lambda$ 값이 모두 크다면(모든 방향으로 밝기가 변화), corner이다.

$\lambda$값들은 $M$ 행렬의 eigenvalue들이다.

R의 근삿값 구하기

eigenvalue 계산을 통해 $R$을 모든 픽셀에 대해 구하면 너무 연산량이 많아진다.
그렇기 때문에 아래 식을 이용하여 근삿값을 구하여 $R$을 대체한다.

$$ \begin{align} R &= \det(M) - \alpha trace(M)^2\\
&= \lambda_1 \lambda_2 - \alpha(\lambda_1 + \lambda_2)^2 \end{align}$$

이때, $\alpha$는 0.04~0.06 사이의 상수이다.

이렇게 계산한 R값의 절댓값이 작으면 Flat, R이 0 미만이면 Edge, 0 이상이면 Corner로 분류할 수 있다.

Harris Corner Detection

지금까지 배운 것이 Harris Corner Detection 방법이다.

1. 모든 픽셀에 대하여 미분값 $I_x, I_y$를 구한다.
2. 모든 픽셀에 대하여 가우시안 가중치 $w$를 사용하여 $M$을 구한다.
   1. 가우시안 가중치는, 이미지의 중심일수록 큰 가중치를 곱하는 것을 말한다.
   2. 위에서 설명한 $M$ 식에 $w(x, y)$를 element wise multiplication 해주면 된다.
3. 각 픽셀에 $R$ 값을 구한다.
4. $R$에 임계값을 적용하여 flat 한 영역들과 edge들을 날린다.
5. Non Max Suppression(NMS)을 적용해 local maxima만 남긴다.
   1. 코너 영역 중에서도 가장 변화량이 큰 점만 남긴다.

Affine Intensity Change

Harris Corner Detection에는 임계값이 존재하기 때문에, 만약 이미지 전체의 밝기가 선형으로 변화하면 결과가 달라진다.

$$ I_{new} = \alpha I_{old} + b$$

Translation Invariant

Harris Method는 Sliding Window 방식, 합성곱 방식으로 이루어지기 때문에 코너의 위치가 바뀌어도 같은 결과(검출 성공)를 낸다.

Rotation Invariant

만약 코너가 회전하게 되면, 밝기 값의 변화량($\lambda$)은 유지되고 변화 방향만 바뀌게 되는데, Harris Method는 $\lambda$만 사용하기 때문에 같은 결과를 낸다.

Image Scaling

이미지의 크기가 변화하게 되면 이때는 밝기의 변화율도 달라진다. 그렇기 때문에 결과가 바뀌게 된다.

이러한 Scale 변화에 Invariant 하게 만들기 위해, 원본 이미지를 다양한 크기로 변환하여 각각 corner를 검출하고 결과를 합치기도 한다.

FAST corners

최근에는 Harris Corner Detector보다 FAST Corner Detector를 사용한다.
FAST Corner Detector는 주변 일정 반경의 픽셀 정보를 사용하여 코너를 검출하는데, 이 글에서 자세히 다루지는 않겠다.