[ 영상 처리 ] Ch9. Local Feature Detection and Matching(1)

본 영상 처리 개념과 기법들에 대한 공부를 진행하면서 배운 내용들을 중심으로 정리한 포스팅입니다. 

책은 Computer Vision: Algorithms and Applications를 기반으로 공부하였습니다.

또한, 인하대학교 박인규 교수님의 디지털 영상 처리 과목을 기반으로 제작된 포스팅입니다.

---

이번 포스팅에서는 Local Feature Detection에 대하여 집중적으로 다뤄볼 것이다. 

 

Local Feature vs Global Feature

 

Local Feature는 영상의 전체가 아닌 일부를 표현(특정)하는 특성이다. 반면, Global Feature는 영상 전체의 특징을 의미한다. 영상의 픽셀 Intensity 분포, Gradient 등이 Global Feature를 의미한다. 

 

Local Feature는 결국, 영상의 일부를 표현할 수 있는 Unique한 특성이라고 이해하고 넘어가자.

 

Local Feature

Feature라는 개념을 조금 더 자세히 정의 해 보자. 사람의 얼굴의 Feature를 찾으라 하면, 우뚝 솟은 "코"라 할 수 있다. 사각 식탁에서의 Feature는 각 모서리(코너)가 될 수 있다. 이처럼 Feature는 다른 영역과 구분되는 자신만의 성질(특징)이다. 그렇다면, Local Feature는 위에서 언급한 것 처럼, 다른 영상의 일부와 구분되는 Unique한 속성을 가져야 한다. 

 

 

Local Feature를 찾기 위해서는, 어떤 Patch(Window)가 Unique한지 살펴봐야 한다. A Patch의 경우 빨간색 Patch로 그린 것 처럼, 인접 영역과 구분되지 않는다. 즉, 같은 색상 분포를 가지는 Patch를 생성할 수 있다. B Patch의 경우 경계에 대한 정보(Bounding Info, Edge)가 주어졌다. 하지만, 유사한 Boundary를 가지는 Patch를 생성할 수 있기 때문에 Unique하지 않다. 반면, C Patch의 경우 밝기가 2방향 이상 변하는 Corner를 포함하고 있다. C Patch와 동일한 Patch를 영상 내부에서 찾을 수 없다. 즉, Unique한 Local Feature가 된다. 

 

A는 아무 변화가 없는 Flat한 Patch이고, B는 Edge를 포함하고 있지만 두 Patch 모두 Local Feature가 될 수 없다. 반면, C Patch는 Corner로, Feature로써 강력한 기능을 한다. 모든 Corner가 Unique하다고 할 순 없지만, 일반적으로 좋은 Feature의 역할을 한다.

 

이러한 Local Feature는 어디에 사용할까?

 

 

위 두 사진은 서로 다른 사진이지만, 겹치는 영역이 있다. 겹치는 영역에 대하여 각각의 사진에서 찾은 Local Feature는 각 사진에서 Unique하다. 따라서 같은 Local Feature를 Matching시킨다면, 오른쪽과 같이 더 넓은 화각을 가지는 파노라마 사진의 결과를 얻을 수 있다.

 

Pipeline : Detection, Description, Matching

Feature Detection, Description, Matching 기술은 컴퓨터 비젼 대부분의 영역에서 활용된다. 

 

 

 

각 기술들이 어떠한 과정으로 진행되는지 살펴보자.

 

먼저 영상에서 Feature를 추출하는데, 이때 Feature를 포함하는 Patch를 추출한다(Feature Detection).  Feature를 포함하는 Patch는 Normalization을 통해 Feature와 Feature 인접 영역의 픽셀 분포($f_A$)로 표현된다. 이때, $f_A$는 Patch 내부 정보를 벡터화한 일종의 Descriptor Vector이다. 

 

Image 2를 보면, Image 1 영상에서 Rotation/Translation/Scaling(Similarity Transform)이 적용되었다. 해당 영상에서도 역시 Feature Detection을 통해 Feature를 추출하고, Feature를 포함하는 Patch를 추출한다. 하지만, Similarity Transform이 적용 되었기 때문에, Patch 내부의 영역도 해당 영향을 받는다. 그렇기에 Normalization을 통해 Patch의 방향과 크기를 특정한 기준을 가지고 표현함으로써 Feature Orientation, Size 등의 정보를 정확히 비교 가능하다. 

 

각 영상에서 추출한 Descriptor Vector $f_A, f_B$의 차이를 계산하고, 일정한 Threshold $T$보다 작으면, 동일한 Feature라고 판단하는 Feature Matching 과정이 진행된다.

 

Challenge : Diverse Scene Variation

 

 

Feature Detection, Description, Matching 과정에 쉬워 보이지만 다양한 방해 요소들이 존재한다. 특히, 원본 영상에서의 조명, 회전, 크기, 시점 변화, 왜곡 등 다양한 변환 과정은 동일한 Feature에 대하여 서로 다른 Feature Descriptor를 생성하기 때문에 Matching에 큰 영향을 준다. 

 

Example of Local Features

다양한 변환에도 강건한 특징 검출기가 필요한데, Local Feature에 따른 대표적인 특징 검출기를 알아보자.

 

 

 

먼저 Edge이다. 우리는 Edge가 Feature로써 강건하지 않음을 위에서 확인했다. 다음은 Corner이다. Corner는 Edge에 비해 Feature로 사용하기에 더 좋지만, Scale에 영향을 받는 단점이 존재한다. 대표적인 Corner 검출기로는 Harris Corner Detector가 있으며 전부 뒤에서 배운다. 다음으로 Blob이다. Blob은 Corner에 Scale 정보가 추가되었다고만 이해하고 넘어가자. Corner의 단점을 보완하였기에 크기에 불변하는 Feature이며, 대표적으로 SIFT가 있다. 그림 c)가 Blob Feature Detection 결과이며, Scale요소가 반지름의 크기로 나타난다. 

 

Affine Covariant region은 넘어가자.

 

Harris Corner Detector

Harris Corner Detector는 Corner Info를 바탕으로 Feature를 검출한다. 그렇다면 Corner Feature가 정확히 뭘까?

 

 

Corner는 2개의 Edge가 만나 높은 곡률을 가지는 지점으로, 영상에서 서로 다른 두 영역이 만나는 점, Texture가 심한 표면, 가려지는 현상(Occlusion)에서 발생하는 밝기 변화가 심한 교점 등에서 발생한다. 

 

그렇다면 왜 Corner가 Feature로써 적합할까? Corner는 Unique하기 때문에 Stable Feature라 할 수 있다. 즉, Corner가 포함된 Patch는 영상 내 다른 Patch와 유사할 확률이 적다. 또한, Corner는 시점과 조도에 무관하다. 

 

Flat, Edge, Corner의 Patch 변화에 따른 특징을 살펴보자. Flat한 영역의 경우 어느 방향으로 Patch를 움직여도 변화가 없다. Edge의 경우 Edge와 수직인 방향으로 Patch를 움직이면 Patch 내 픽셀 분포의 차이는 존재한다. 하지만, Edge 방향으로 움직이면 Unique한 표현이 불가하다. 하지만, Corner의 경우 어떠한 방향으로 Patch를 움직여도 차이가 존재하게 된다. 따라서 Unique하게 표현할 수 있다!

 

Harris Detector Formulation

앞서 우리는 Patch를 움직여 가며 Patch 내의 픽셀 인텐시티의 차이를 보고, Corner가 적합한 Feature임을 판단하였다. 이를 수식화 하면 다음과 같다.

 

 

여기서 $\Delta u$는 Patch의 이동 Vector, $I$는 Intensity, $w(x_i)$는 Window Function으로 Patch 영역 내부를 의미한다. $x_i$는 특징점이라고 추정되는 좌표임을 고려하여 위 수식을 해석 해 보면, 특징점으로 추정되는 위치($x_i$)와, 해당 위치의 인접 픽셀로 이동한 위치($x_i + \Delta u$)에서의 Intensity Difference의 제곱을 계산한 것이 $E_{AC}(\Delta u)$이다.

 

 

 

Window Function이 조금 생소할 수 있는데, 이는 위 연산을 영상 전체가 아닌 Patch(Window) 내부에서만 진행함을 의미한다. 따라서 Patch 내의 화소를 연산할 때만 1로, 아니면 0으로 만들어 준다. 이때, 1과 0 이진화 된 Value가 아닌 Gaussian을 적용할 수도 있다.

 

$w(x_i)$가 분홍색 Patch라고 생각하면 된다. Patch 자체는 고정되었다고 생각하고, 영상이 파란색 방향으로 Shift되는 상황이다. 이때, 영상 전체가 아닌 해당 Patch 내부의 차이만 고려한다는 의미이고, 그때의 Patch내 영상이 위에 표현되어 있다. 만약 Flat한 영역이라고 하면, Shift되더라도 $E_{AC}(\Delta u)$는 매우 작을 것이다. Edge인 경우는 Edge와 평행한 특정 방향으로의 차이는 매우 작기 때문에 Corner보다 $E_{AC}(\Delta u)$가 작다. 따라서 큰 $E_{AC}(\Delta u)$를 가지는 곳이 Corner일 가능성이 높고, $E_{AC}(\Delta u)$가 클수록 Unique함을 의미한다.

 

 

Flat, Edge, Corner에 해당하는 특징점에서의 Patch를 기반으로 구한 $E_{AC}(\Delta u)$를 $ \Delta u$를 변화시키면서 구한 그래프로,  $E_{AC}(\Delta u)$의 함수 분포라고 할 수 있다. Flat한 부분의 경우 전반적으로 밝은 화소를 보이는데, 차이가 거의 없음을 의미한다. Edge의 경우 특정한 방향으로 밝은 분포를 보이는데, 해당 방향이 Edge와 평행한 방향이다. Corner의 경우 전 방향으로 어두운 분포를 보임을 확인할 수 있다. 즉, 인접한 영역과 차이가 있는 Unique한 특징을 보인다.

 

우리는 어떻게 코너를 찾아야 하는지 수식적으로 나타낼 수 있다. 그렇다면 어떻게 자동적으로 Corner를 검출하게 할 수 있을까?

 

여기서 테일러 급수를 잠깐 살펴보고 가자. 

 

 

$I$는 앞서 말한 것 처럼 Intensity를 의미한다. 따라서 $(x+u, y+v)$ 위치에서의 Intensity는 $(x,y)$에서의 Intensity, x 방향으로의 기울기($\frac{\partial I}{\partial x}$)와 u의 곱, y방향으로의 기울기 ($\frac{\partial I}{\partial y}$)와 v의 곱의 합으로 근사할 수 있다. 이때, $u,v$는 $\Delta u$ 즉, Patch를 이동시킬 변화량을 의미한다. 그리고 해당 근사치를 Matrix의 곱으로 표현하면 위와 같이 표현 가능하다. 그렇구나~ 하고 넘어가자.

 

 

앞서 구한 $E_{AC}(\Delta u)$식을 다시 가져왔다. 그리고 앞서 언급한 테일러 급수를 이용하여 근사시켰다.

 

 

두 식은 동일한 표현이지만, 표현을 다르게 했다고 이해하면 된다. $x_i$는 특징점일 가능성이 있는 위치이기에 $(x,y)$로 표현되고, 각 방향으로의 미분을 $I_x, I_y$로 표현 한 것이다. 그리고 이전에 배운 것 처럼, 각 방향으로의 미분은 결국 Gradient이였음을 기억하자.

 

 

위 식에서 동일한 $I_o(x_i)$를 지우면 아래와 같다.

 

 

이렇게 표현되는게 이해가 안된다고 걱정하지 말고, 그냥 자연스러운 Matrix 내적 및 제곱의 연산 결과라고 이해하자. 결국, $E_{AC}(\Delta u)$를 위와 같은 형태로 표현 가능하며, Vector의 Transpose와 정방향렬, Vector의 곱으로 표현되는 해당 형태를 Quadratic Form이라 한다.

 

최종적으로 $E_{AC}(\Delta u)$는 다음과 같이 표현된다.

 

$$E_{AC}(\Delta u) = \Delta u^T A \Delta u$$

 

이때, $A$ Matrix는 아래와 같이 표현되는데, Patch 내부만 계산한다는 Window Function과 $I_x, I_y$를 원소로 하는 Matrix로 표현된다.

 

 

 

결국 $E_{AC}(\Delta u) = \Delta u^T A \Delta u$ 이와 같이 표현할 수 있으며, $\Delta u, \Delta v$는 Constant이기 때문에, Corner는 $E_{AC}(\Delta u)$이 커야 하고, $E_{AC}(\Delta u)$는 A Matrix에 의해 결정된다고 할 수 있다.

 

이젠, A Matrix의 표현을 조금 정리 해 보자.

 

 

결국, Window Function은 Patch 내부의 제한된 영역 에서만 계산한다는 의미이기에, Matrix 안쪽으로 집어넣을 수 있으며, 다시 Matrix를 분해하면 최종적으로 위와 같이 표현할 수 있다.

 

The mean of A Matrix

이제 Corner를 찾기 위해서는  $E_{AC}(\Delta u)$를 계산해야 되고, 최종적으로는 $A$ Matrix를 통해 Corner Detection이 가능함을 배웠다. 그렇다면, $A$ Matrix를 분석하여 $x_i$가 Corner일 때의 특징을 살펴보자. $A$ Matrix는 패치 내의 $I_x, I_y$로 구성된 행렬임을 기억하자.

 

 

Flat한 영역의 경우 Gradient 즉, 픽셀 차이가 적기 때문에 미분 갑싱 0에 가까운 갑승로 구성되어 있다. 완벽한 0이 아닌 이유는 Noise가 포함되었기 때문이다. Edge의 경우 현재 Vertical Edge이기 때문에, 수직 방향의 변화량 $I_y$는 0에 가까운 값을 가지지만, 수평 방향의 변화량 $I_x$는 큰 값이 발생함을 확인할 수 있다. 즉, Edge의 경우 Edge와 수직한 한쪽 방향의 미분값이 크다.

 

Corner를 살펴보자. Corner는 두 Edge가 만나는 부분이기에, 각 Edge의 수직한 방향으로의 값이 큰 경우가 존재한다. 뿐만 아니라 Corner 부분은 모든 방향에서의 변화량이 크기 때문에, $I_x, I_y$모두 큰 부분이 존재한다. 

 

수식적으로 이를 전부 표현하는데는 어려움이 있다. 따라서 Eigen Value 즉, 행렬의 고유값을 도입하여 표현 해 보자. 행렬의 고유값은 행렬의 특성을 나타내는 대표값이라고 생각하면 된다.

 

 

$A$ Matrix는 $I_x, I_y$로 표현되며, Eigen Value로는 오른쪽과 같이 표현된다. 위 관계를 고려하여 위 분포도를 다시한번 살펴 보자.

 

 

 

Flat은 $I_x, I_y$ 모두 0에 가까운 작은 값을 가진다. 따라서 Eigen Value 모두 0이거나 0에 가까운 값을 가진다. Edge는 Edge의 수직인 방향으로의 미분값만 크다. 따라서 두 Eigen Value 중 하나는 Eigen Value가 크고, 나머지는 0에 가까운 작은 값을 가진다. 고유값은 순서가 없기 때문에 어느 하나가 상대적으로 크다고 이해하자. Corner의 경우 $I_x, I_y$ 모두 큰 값을 가지기 때문에, 두 고유값 모두 크다. 따라서 행렬 $A$의 고유값을 구하면 Corner를 판단한 수 있다.