[Computer Vision] Harris Corner Detection 해리스 코너 검출

 

 

Feature Detection

 이미지에서 의미 있는 점들을 feature point 라고 한다. Edge와 corner와 같은 특징을 가진 점들을 이미지에서 뽑아내어 object recognition, 3d reconstruction 같은 유용한 작업들을 수행할 수 있다. Feature detection 기법중 가장 간단한 corner detection에 대하여 먼저 살펴보고자 한다.

 

이미지에서 corner를 인식하려면 먼저 코너가 어떤 특징을 가지고 있는지 알아야 한다. 

 

 어떤 sliding window를 움직였을때 flat region에서는 아무런 intensity 변화가 생기지 않는다. edge에서는 edge의 방향으로 움직였을때 아무런 변화가 생기지 않고, 그 이외의 방향으로 움직였을 때 intensity의 변화가 생긴다. 반면 corner 에서는 어느 방향으로 움직이던 sliding window 내부에 intensity change가 생긴다. 이 특징을 이용하여 코너 검출을 할 수가 있다. 

 

 Sliding window를 움직였을 때 변화량을 식으로 표현하면

 

$ E(u,v) = \sum_{x}^{y} w(x,y) [I(x+u, y+v) - I(x, y)] $

 

가 되고, 따라서 이미지 위의 어떤 한 sliding window 를 대표하는 점 x,y 에서 u,v 만큼 움직임에 따른 intensity의 변화량을 E로 나타낼 수 있다. 따라서 uv space에서 코너가 있다면 아래 그림과 같이 u=0, v=0 지점만 0이고 (shift 가 없기 때문) 조금의 shift에도 모든 방향으로 intensity change 를 나타내는 E가 커진다고 생각할 수 있다. uv domain에서 3차원으로 생각하면 코너에서는 E 함수가 그림과 같이 peak를 가지는 것을 알 수 있다.

 

하지만 현실적으로 모든 window 에서 E를 계산하기에는 상당히 많은 시간이 필요하기 때문에 ( $ O(window\text{ }width^2 \times shift \text{ }range^2 \times image\text{ }width^2) $) E 함수를 quadratic surface 로 approximate을 하여 계산하면 모든 window들을 더욱 빠르게 처리할 수 있다.  E 함수를 Taylor Series로 전개하면 아래와 같은 식이 된다.

 

 $ E(u, v) = E(0, 0) + \begin{bmatrix} u & v \end{bmatrix} \begin{bmatrix} E_u(0, 0) \\ E_v(0, 0) \end{bmatrix} + \frac{1}{2} \begin{bmatrix} u & v \end{bmatrix} \begin{bmatrix} E_{uu}(0, 0) & E_{uv}(0, 0) \\ E_{vu}(0, 0) & E_{vv}(0, 0) \end{bmatrix} \begin{bmatrix} u \\ v \end{bmatrix} = \begin{bmatrix} u & v \end{bmatrix} \begin{bmatrix} E_{uu}(0, 0) & E_{uv}(0, 0) \\ E_{vu}(0, 0) & E_{vv}(0, 0) \end{bmatrix} \begin{bmatrix} u \\ v \end{bmatrix} $

 

위 식에서 quadratic surface로 approximate을 하였기 때문에 1차 편미분 항인 $E_u(0,0)$와 $E_v(0,0)$는 0이 되고 (quadratic surface에서는 원점에서 기울기가 0이기 때문) $E(0,0)$ 또한 상수항이므로 0이 된다. 따라서 남는 항은 2차 편미분으로 구성된 부분이다. 이때 식은 다음과 같이 단순화된다:

 

$ E(u, v) \approx \frac{1}{2} \begin{bmatrix} u & v \end{bmatrix} \begin{bmatrix} E_{uu}(0, 0) & E_{uv}(0, 0) \\ E_{vu}(0, 0) & E_{vv}(0, 0) \end{bmatrix} \begin{bmatrix} u \\ v \end{bmatrix} $

 

여기서 남은 2차 미분 항을 계산하면 Second Moment Matrix가 나온다.

 

$ M=\begin{bmatrix} \sum w(x, y) I_x(x, y)^2 & \sum w(x, y) I_x(x, y) I_y(x, y) \\ \sum w(x, y) I_x(x, y) I_y(x, y) & \sum w(x, y) I_y(x, y)^2 \end{bmatrix} $

 

Second Moment Matrix를 diagonalize 하면

 

$ E(u, v) = \begin{bmatrix} u & v \end{bmatrix} M \begin{bmatrix} u \\ v \end{bmatrix} = \begin{bmatrix} u & v \end{bmatrix} R^{-1} \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix} R \begin{bmatrix} u \\ v \end{bmatrix} $

 

가 된다. 이때 quadratic surface로 approximate 한 E 함수의 단면을 보면 $E(u,v)$ 가 constant 이기 때문에 uv space를 회전시킨 basis에서의 타원이 된다.

 

https://dsp.stackexchange.com/questions/15060/how-to-understand-relationships-between-ellipse-and-second-moment-matrix-of-harr

 

Matrix를 전개하면 $ \lambda_1 s^2 + \lambda_2 t^2 = C $ 형태로 나오기 때문에 장축의 길이는 $ \lambda_{min}^{-0.5} $ 이고 단축의 길이는 $ \lambda_{max} ^ {-0.5} $ 가 된다. 이 타원의 모양에서 단축 방향으로의 intensity change가 가장 빠르고 장축 방향으로의 intensity change 가 가장 느리다라는 사실을 알 수 있다. Corner 에서는 모든 방향으로의 intensity change가 고르게 빠르기 때문에 second moment matrix의 eigenvalue가 비슷해야 하고, 변화량이 커야 하기 때문에 두 eigenvalue의 값이 커야한다.

 

정리하자면, corner에서는 second moment matrix의 maximum eigenvalue와 minimum eigenvalue가 비슷하고 값이 크다. 따라서 타원의 장축과 단축의 길이가 비슷하고, E 함수의 단면은 커다란 원이 된다.

 

 

Harris Corner Detector

Harris corner detector 는 얼마나 corner 한지를 측정해주는 양인 cornerness를 아래와 같이 정의한다.

 

$ C = \lambda_1 \lambda_2 - \alpha (\lambda_1 + \lambda_2) = det (M) - \alpha tr(M) $

 

$\alpha$ 는 임의의 상수이며 보통 0.2-0.4 사이의 값으로 고른다. C의 값의 클수록 더욱 정확한 corner이고, flat 과 corner를 구분하기 위해 C의 값에 threshold 를 잡아 일정 값 이상이 되면 corner, 아니면 flat으로 정의할 수 있다. 

https://docs.opencv.org/3.4/dc/d0d/tutorial_py_features_harris.html

 

C의 값이 threshold보다 높은 값을 가지는 점들만 고르게 되면 생각보다 매우 많은 점들을 잡게 된다. 따라서 정확한 corner만 검출하려면 이미지 내 local space를 잡아서 maximum 인 값을 제외한 corner point를 버려야 한다. 아래 사진을 보면 주황색 박스에 불필요하게 많은 corner point들이 검출된 것을 볼 수 있다. 저 박스 안에 있는 점들중 가장 cornerness가 높은 점들 몇개만 골라 추출하는 것을 non-maxima suppression 이라고 한다. 위에 있는 그림은 non-maxima supression을 하기 전, 아래에 있는 그림은 non-maxima suppression을 한 이후의 사진이다. 같은 박스 위치에 검출된 불필요한 코너의 갯수가 줄어든 것을 볼 수 있다. 

 

Before non-maxima suppression

 

After non-maxima suppression

 

References

KAIST MinHKim CS484 Introduction to Computer Vision