[CV] Harris Corner Detection

📹 What is corner?

Corner를 어떻게 정의해야 할까? 사실 Harris corner detector는 너무 느리기 때문에 현재에는 사용하지 않는 알고리즘이라고 한다. 하지만 Harris가 제안한 corner의 수학적 정의, 이를 수학적으로 탐지할 수 있는 알고리즘은 아주 인상적이다. Harris는 다음과 같은 방식으로 flat/edge/corner를 구분하였다.

• flat : 한 점에 대해서, 모든 방향에 대해 변화량이 작다.
• edge : 한 방향으로만 변화량이 작다.
• corner : 모든 방향으로의 변화량이 크다.

📹 Mathematics of Harris Detector

정리하자면 corner를 찾기 위해서는 한 점에 대해 주변으로의 변화량을 계산해야 한다. 이는 window를 사용하면 간단히 계산할 수 있다. 핵심은 어느 방향으로 얼마나 변하냐는 것이다. 이를 위해 변화량 함수를 1차 Taylor series로 근사하고, 대각화를 진행한다. (대각화에 대해서는 선형대수 포스팅에 잘 정리되어 있다.)

\[E(u,v) = \sum_{(x,y)\in W}^{}\begin{bmatrix} I(x+u, y+v) - I(x,y)\end{bmatrix}^{2}\]

\[\begin{align*} I(x+u, y+v) &= I(x,y) + \frac{\partial I}{\partial x} u + \frac{\partial I}{\partial y} v + \textit{higher order term...} \\ &\approx I(x,y) + \frac{\partial I}{\partial x} u + \frac{\partial I}{\partial y} v \\ &= I(x,y) + \begin{bmatrix}I_{x} \, I_{y}\end{bmatrix}\begin{bmatrix} u \\v \end{bmatrix} \end{align*}\]

\[\begin{align*} E(u,v) &\approx \sum_{(x,y)\in W}^{}\begin{bmatrix} I(x,y) + \begin{bmatrix} I_{x} & I_{y} \end{bmatrix}\begin{bmatrix} u \\ v \end{bmatrix} - I(x, y) \end{bmatrix}^{2} \\ &= \sum_{(x,y) \in W}^{} \begin{bmatrix} \begin{bmatrix} I_{x} & I_{y} \end{bmatrix} \begin{bmatrix} u \\ v \end{bmatrix} \end{bmatrix}^{2} \\ &= \sum_{(x,y) \in W}^{} \begin{bmatrix} u & v \end{bmatrix} \begin{bmatrix} I_{x}^{2} & I_{x} I_{y} \\ I_{y} I_{x} & I_{y}^{2} \end{bmatrix} \begin{bmatrix} u \\ v \end{bmatrix} \\ &= \begin{bmatrix} u & v \end{bmatrix} \left ( \sum_{(x,y) \in W}^{} \begin{bmatrix} I_{x}^{2} & I_{x} I_{y} \\ I_{y} I_{x} & I_{y}^{2} \\ \end{bmatrix} \right ) \begin{bmatrix} u \\ v \end{bmatrix} \\ &= \begin{bmatrix} u & v \end{bmatrix} \mathbf{M} \begin{bmatrix} u \\ v \end{bmatrix} \end{align*}\]

즉, (u,v)에서의 변화량은 matrix M에 의해 결정된다. 이때 주목할 점은 M이 symmetric 하기 때문에 대각화가 가능하다는 점이고, M의 eigen value에 따라 임의의 방향에 대한 변화율이 결정된다.

\[\begin{align*} \mathbf{M} &= \sum_{(x,y) \in W}^{} \begin{bmatrix} I_{x}^{2} & I_{x} I_{y} \\ I_{y} I_{x} & I_{y}^{2} \end{bmatrix} \\ \\ &= X \begin{bmatrix} \lambda_{1} & 0 \\ 0 & \lambda_{2} \end{bmatrix} X^{T} \end{align*}\]

• λ1 & λ2가 모두 작음 : 모든 방향으로의 변화율이 작음 → Flat
• λ1과 λ2 중 하나는 크고 하나는 작음 : 특정 방향의 변화율이 작음 → Edge
• λ1 & λ2가 모두 큼 : 모든 방향으로의 변화율이 큼 → Corner

R score

우리가 필요한 건 λ1과 λ2의 구체적인 값이 아니라, 대략적인 크기와 비율이다. 따라서 Determinant와 Trace의 성질을 이용하면 직접 대각화를 하지 않고도 간편히 구할 수 있다.

\[\mathbf{R} = det (M) - k(trace M)^{2} \quad \begin{align*} \textit{where} \quad det(M) &= \lambda_{1} \lambda_{2} \\ trace(M) &= \lambda_{1} + \lambda_{2} \end{align*}\]

• k = 0.04 ~ 0.06
• If only one of λ1 or λ2 is large: det(M) ↓, R↓ → Not a corner
• If both λ1 and λ2 are large: det(M) ↑, R↑ → Corner

Non-max suppression

R scroe가 특정 값 이상인 점을 뽑는 방식으로 Corner를 탐지한다고 하면, 하나의 corner를 여러 픽셀에서 동시에 탐지하게 될 것이다. 따라서 중복된 탐지를 제거하기 위해 NMS 알고리즘을 수행한다. 알고리즘의 작동 방식은 현재 픽셀에서의 R score값이 주변의 R score보다 클 때에만 값을 유지하고, 만약 작다면 0으로 만들어 R score를 압축한다.

📹 Harris Corner Detector Algorithm

1. Compute gradients for all pixels
2. For each pixel, compute M matrix and R socre
3. Find points with R > threshold
4. Non-max suppression

📹 About Affine Transforms

Affine Transfrom이란 간단히 말해 (translation + rotation) 변환이다. Harris corner detector는 Affine transform에 invariant 할까? 정답은 그렇다. Translation은 당연히 invariant하고, rotation 또한 eigen vector의 방향만 바뀔 뿐 eigen values의 비율은 변하지 않기 때문이다.

📹 About Scaling

Problem	Solution

Harris Detector는 scaling에도 invariant할까? 다시 말해 corner의 사이즈가 달라져도 같은 detector(same window, smae threshold)로 탐지가 가능할까? 정답은 응 아니야. 큰 사이즈의 코너를 탐지할 때 사이즈가 작은 detector를 사용할 경우 직선으로 탐지할 가능성이 크기 때문이다. 이를 해결하기 위해서는 detector의 사이즈를 바꿔가며 R score를 구하고 그 중 최대값을 구해야 한다. 가능은 하지만 너무 번거로운 작업이다. 이 지점이 바로 harris detector의 한계이고, Scale Invariant Feature Transform(SIFT)의 등장 배경이다.

📹 Results

맨 위로 이동하기

Vision 카테고리 내 다른 글 보러가기