CV 1. Local Features

Computer Vision[1]

1. Image Features

이미지는 각 pixel (0~255)로 나타나는 matrix이다. Raw pixel을 사용해 image를 분석할 수 있지만, Raw pixel은 1. scale variation, 2. intra-class variation, 3. deformation, 4. occlusion, 5. illumination change 등에 매우 취약하므로, 이미지의 pixel matrix에서 특정 "feature"를 찾는 과정이 필요하다. Feature는 하나의 이미지에 "vector" 형태로 추출되며, 추출된 "vector (e.g., feature)"는 Decision Marker (ex, machine learning models)에 의해서 분류(classification)을 할 수 있게 된다.

Image로 부터 추출된 feature 들의 모음을 "Bag of Visual Word"라고 불리며, Word의 representative한 features는 clustering 방법을 사용하여 unsupervised 방법으로 결정된다. 좋은 Image의 Features는

1) Repeatability

- geometric과 photometric 변환에도 불구하고 똑같은 이미지에서 동일한 "특징"이어야 하며,

2) Saliency

- 특징은 image의 interesting point를 포함하여야 하며,

3) Locality

- 특징은 image 내의 작은 영역을 차지해야한다.

Interest points = Local features는 주로 이미지에서 "Corner"와 "Blob"이며, 이 Features를 이미지에서 얻기 위해서는 low-level의 image processing 단계가 필요하다.

2. Image Processing

1) Convolution (Kernel)

Convolution 연산은, 어떤 Kernel (값을 갖고 있는 rectangle matrix)가 이미지에 sliding window방식으로 훑으면서, 이미지의 pixel에 Kernel의 parameters에 elementwise multiplication 연산을 진행한 후, 하나의 pixel로 바꿔주는 과정을 의미한다. (너무 복잡하면 구글에 "Image Convolution"이라고 검색해보자!)

Convolution 연산을 통해서, Image로 부터 "Sharp", "Smooth", "Gradient"의 이미지 정보를 얻을 수 있다. 밑의 그림에서 "Sharpen" 연산에서는 original image의 edge가 두드러지는 것을 확인할 수 있으며, "Gaussian blur" 연산에서는 original image가 더 흐릿해지는 것을 확인할 수 있다. 이와 반대로 "Edge detection" 연산에서는 이미지의 X방향 Y 방향의 Gradient를 계산하여 Edge를 찾아내는데 사용된다.

Operation	Kernel ω	Image result g(x,y)
Identity	${\displaystyle {\begin{bmatrix}0&0&0\\0&1&0\\0&0&0\end{bmatrix}}}$
Edge detection	${\displaystyle {\begin{bmatrix}\ \ 1&0&-1\\\ \ 0&0&\ \ 0\\-1&0&\ \ 1\end{bmatrix}}}$
	${\displaystyle {\begin{bmatrix}0&\ \ 1&0\\1&-4&1\\0&\ \ 1&0\end{bmatrix}}}$
	${\displaystyle {\begin{bmatrix}-1&-1&-1\\-1&\ \ 8&-1\\-1&-1&-1\end{bmatrix}}}$
Sharpen	${\displaystyle {\begin{bmatrix}\ \ 0&-1&\ \ 0\\-1&\ \ 5&-1\\\ \ 0&-1&\ \ 0\end{bmatrix}}}$
Box blur  (normalized)	${\displaystyle {\frac {1}{9}}{\begin{bmatrix}1&1&1\\1&1&1\\1&1&1\end{bmatrix}}}$
Gaussian blur 3 × 3  (approximation)	${\displaystyle {\frac {1}{16}}{\begin{bmatrix}1&2&1\\2&4&2\\1&2&1\end{bmatrix}}}$
Gaussian blur 5 × 5  (approximation)	${\displaystyle {\frac {1}{256}}{\begin{bmatrix}1&4&6&4&1\\4&16&24&16&4\\6&24&36&24&6\\4&16&24&16&4\\1&4&6&4&1\end{bmatrix}}}$
Unsharp masking 5 × 5  Based on Gaussian blur  with amount as 1 and  threshold as 0 (with no image mask)	${\displaystyle {\frac {-1}{256}}{\begin{bmatrix}1&4&\ \ 6&4&1\\4&16&\ \ 24&16&4\\6&24&-476&24&6\\4&16&\ \ 24&16&4\\1&4&\ \ 6&4&1\end{bmatrix}}}$

출처: Wikipedia, Kernel (Image Processing), https://en.wikipedia.org/wiki/Kernel_(image_processing)

3. Harris Corner Detection

앞에서 주요한 Local feature로는 corner와 blob이 있다고 언급하였다. Image 내에서 Corner를 검출하기 위해 Harris Corner Detection이 제안되었다. 

기본 아이디어는 다음과 같다.

"어느 특정 고정된 크기의 patch를 움직였을 때, 모든 방향으로 심하게 차이가 나면 Corner이고, 차이가 없으면 Flat region, 그리고 한쪽 방향으로 차이가 없다면 Edge 이다."

Harris Corner Detection의 식을 보면,

w는 point (x,y) 주변의 고려하고 싶은 patch의 크기를 정의하며 uniform 형태 혹은 Gaussian의 형태를 사용할 수 있으며, Gaussian window는 noise에 robust한 특징을 갖고 있다.

식을 보면, u,v 방향만큼 이동하였을 때의 pixel 값의 차이를 계산하는 것을 확인할 수 있다.

First-order Taylor Expansion에 의해서 approximation을 할 수 있으며, Intensity의 변화 (E)는 M 행렬과 unit vector로 나타낼 수 있다. M 행렬은 Image의 gradient x방향과 y방향의 Covariance matrix 형태를 갖고 있는 것이 특징이다. M 행렬은 2 x 2의 크기로 2개의 eigenvalue와 이에 해당하는 2개의 eigenvector로 나타낼 수 있는데, 이 eigenvalue에 의미가 있다. 두 eigenvalue의 값이 크다면 어떤 방향이든지 (u,v)를 곱해도 E 값은 크다. 반대로, 두 eigenvalue의 갑이 작다면 어떤 방향이든지 (u,v)를 곱해도 E 값은 작을 수 밖에 없다. 만약 하나의 eigenvalue만 값이 크다면 그 방향으로의 (u,v)를 곱할 경우만 E 값이 커지며, 그외는 E 값이 작을 것이다. 따라서, 3개의 case (flat, edge, and corner)를 M 행렬로 구분할 수 있다.

하지만, eigenvalue를 구하는 것은 어렵기 때문에, M 행렬에서, Corner성을 계산하는 방법은 다음과 같다.

R이 매우 크다면 det(M) 값이 크다는 것이고 이는 두개의 eigenvalue가 크다는 것을 의미한다.

4. Blob Detection

Harris Corner Detection으로 Image에서 Corner를 검출할 수 있다. 그외의 주요한 Local Feature는 Blob인데, blob은 어떤 group을 의미한다. Blob을 검출하기 위해서는 Image의 significant한 변화를 특정 구간에서 찾을 수 있는 방법이 필요하고, 이는 Laplace of Gaussian으로 검출된다. Laplace of Gaussian은 다음과 같다.

이 함수의 주요한 특징은 Mexican모자처럼 주변에는 평평하고 머리 부분은 길쭉하게 튀어나와있다는 것이다. (google에 검색해보자!) 이 길쭉한 부분이 바로 Blob의 영역이되며 가장 길쭉하게 튀어나온 부분이 Blob의 중앙부분이 되는 것이 가장 이상적이다.

하지만, 문제점은 Laplace of Gaussian의 분모(sigma의 4승)에 의해서 sigma가 커질 수록 Laplace of Gaussian 값이 매우 작아진다. (sigma가 커지면 더 넓은 blob을 detection할 수 있다.) 이 문제를 제거하기 위해서 Scale Normalization을 하며, 다음과 같다.

기존의 Laplace of Gaussian 앞에 sigma의 제곱을 곱해줌으로써, 다양한 blob의 크기를 blob의 중앙에서 가장 큰 크기를 갖고 detection을 할 수 있게 된다.

5. What is the next?

Harris Corner Detection과 Laplace of Gaussian으로 Image의 유의미한 Features들을 추출할 수 있다. 하지만, Harris Corner Detection은 Scale의 변화에 매우 취약하며 (생각해보자! 매우 멀리서 보면 모든것이 Corner이다.), Laplace of Gaussian은 많은 연산량을 요구한다. (매 Sigma마다 LoG를 계산해야하며, LoG는 여러개의 n x 1 filter로 나눌 수 없다. + normalization을 위해서 sigma의 제곱을 곱해줘야한다.)

이를 해결하기 위해 Scale-Invariant Feature Transform (SIFT)가 등장한다.

Image Processing, Convolution, Harris Corner Detection, Laplace of Gaussian, Image Features, Local Features, Corner, Blob