[Computer Vision] Feature detection(Cont.)

해당 글은 건국대학교 지서원 교수님의 컴퓨터 비전 수업 내용을 정리한 글입니다.

 

이전 글:

2026.04.20 - [[Konkuk Univ. 4th]/[Computer Vision]] - [Computer Vision] Feature detection

[Computer Vision] Feature detection

 

Harris Corner Detector(cont.)

 

두 이미지 patch가 얼마나 비슷하게 생겼는지 판별하기 위해, 가장 기초적인 수학적 지표인 SSD(sum of difference)를 도입할 수 있습니다:

SSD

 

이는 두 픽셀 배열의 차이를 제곱하여 모두 더하는 방식입니다.

 

한편, unique한 특징점으르 찾기 위한 가장 무식하고 확실한 방법은 1) 이미지 내의 가능한 모든 patch N개를 추출한 다음, 2) 모든 patches들끼리 SSD를 계산하여 NxN 크기의 오차 행렬을 만들고, 3) 그중에서 최솟값이 가장 큰(즉, 다른 어떤 patch와도 닮지 않은) patch를 고르면 됩니다.

 

하지만 이 O(N^2) 알고리즘은 극단적으로 비효율적이며, 실시간 연산 속도가 생명인 vision system에서 N값이 조금만 커져도 연산량이 폭바라하므로, impractical한 방법입니다. 대신에 이미지 전체가 아닌 아주 좁은 local neighbor 영역만 검사할 수 있습니다.

 

patch를 임의의 방향으로 살짝 이동시켰을 때 발생하는 pixel intensity 변화를 측정하는 autocorrelation 함수를 사용합니다:

autocorrelation

 

자기 자신을 복사하여 옆으로 약간 밀어낸 뒤 원래 이미지와 빼서 비교하는 방식입니다. 예를 들면 다음과 같습니다:

(left) corner autocorrelation, (middle) edge autocorrelation, (right) falt autocorrelation.

 

error를 z축으로 해서 3d 그래프로 나타내면 다음과 같습니다:

3D

• flat: 모든 이동 방향에 대해 error 값이 매우 작아 바닥에 깔려있는 평면 형태입니다.
• edge: 능선 방향으로 patch를 밀면 겹치기 때문에, error가 낮지만(골짜기 형태), 수직으로 밀면 error가 높아지는 형태입니다.
• corner: 모든 방향으로의 미세한 이동이 즉각적인 error 폭등을 유발하므로, 가운데가 음푹 파인 뾰족한 그릇(bowl) 형태가 됩니다.

 

Error function.

 

이를 컴퓨터가 계산할 수 있도록 방정식의 형태로 정리하면 다음과 같습니다:

error function

 

local region의 변화량을 측정하는 비선형 error function을 연산 가능한 형탤로 선형화하기 위해 1차 테일러 급수 근사를 도입합니다:

use the first order taylor series approximation

 

이동된 이미지 I(x+u, y+v)를 원본 I(x,y)에 미분값 uIx + vIy를 더한 형태로 근사할 수 있습니다. 이를 원래 식에 대입하여 전개하면 마지막 term의 2차 다항식이 도출됩니다. 그리고 이를 matrix의 형태로 묶으면 다음과 같습니다:

we can rewrite it using a matrix form:

 

이는 이전에 다루었던 Harris matrix이며, 이는 픽셀의 변화량을 측정하는 물리적 문제가 2x2 행렬의 고유값을 분석하여 error가 극대화되는 방향을 찾는 기하학적 문제로 귀결됨을 보여줍니다.

 

* 위 수식에서 이동 벡터 [u,v]의 크기를 1로 고정했을 때(즉, 일정한 반경 내에서 이동할 때), error E(u,v)를 최대로 만드는 방향은 harris matrix M의 가장 큰 고유값에 대응하는 고유 벡터 방향입니다. 반대로, error가 가장 적게 증가하는 방향은 가장 작은 고유값에 대응하는 고유 벡터 방향입니다.

 

* corner는 모든 방향으로 이동했을 때 error가 급격히 증가하는 지점으로 정의됩니다. 즉, error가 가장 적게 증가하는 방향(최소 방향)으로 이동하더라도 그 error값 자체가 매우 커야만 진정한 corner라고 할 수 있습니다. 따라서 알고리즘은 가장 작은 고유값조차도 충분히 큰 지점을 찾음으로써, 해당 patch가 어느 방향으로든 강한 변화율을 가지고 있음을 수학적으로 보장하게 됩니다.

 

Step 1. SSD 기반의 자기 상관성 (Autocorrelation) 정의

어떤 픽셀 패치가 주어졌을 때, 이 패치를 아주 미세하게 (u, v)만큼 이동시켰을 때 원본 패치와의 픽셀 밝기 차이(SSD)를 나타내는 에러 함수 E(u,v)는 다음과 같이 정의됩니다:

error function

• w(x,y): 중심 픽셀에 가중치를 주는 윈도우 함수 (보통 가우시안)
• I(x+u, y+v): (u,v)만큼 이동된 이미지
• I(x,y): 원본 이미지

이 수식 자체는 비선형적이며, 모든 (u,v) 방향에 대해 일일이 이동시켜가며 값을 구해야 하므로 계산이 거의 불가능합니다.

Step 2. 1차 테일러 급수 근사 (Taylor Series Expansion)

이동량 (u,v)가 아주 작다고 가정하면, 비선형적인 이동 이미지 I(x+u, y+v)를 1차 테일러 급수를 이용해 그래디언트(미분값)의 선형 결합으로 근사할 수 있습니다:

linear combination

• I_x = \frac{\partial I}{\partial x} (x방향 미분)
• I_y = \frac{\partial I}{\partial y} (y방향 미분)

이 근사식을 원래의 에러 함수 E(u,v)에 대입하면 $(x,y) 항이 깔끔하게 소거됩니다:

error function

 

완전제곱식을 전개하면 다음과 같은 2차 다항식이 도출됩니다:

error function

Step 3. 행렬 형태(Quadratic Form)로의 변환

이제 위의 다항식을 선형대수학의 이차형식(Quadratic form)인 행렬의 곱셈 형태로 묶어냅니다. 이 과정이 마법이 일어나는 순간입니다:

error function

 

괄호 안에 있는 2x2 행렬을 구조 텐서(Structure Tensor) 또는 해리스 행렬 M이라고 정의합시다:

harris matrix M

 

그러면 에러 함수는 아주 단순한 행렬 수식으로 치환됩니다: (여기서 벡터 $\mathbf{u} = \begin{bmatrix} u \\ v \end{bmatrix}$ 입니다.)

error function

Step 4. 기하학적 해석과 고유값 문제(Eigenvalue Problem)

수학적으로 위와 같은 이차형식은 3차원 공간에서 타원면(Ellipsoid) 또는 그릇(Bowl) 형태의 곡면을 만들어냅니다.

우리의 목표는 어느 방향 u로 이동해야 에러 E가 가장 크게(혹은 작게) 변하는가?를 찾는 것입니다. 방향의 공정성을 위해 이동 벡터의 크기를 1 단위 원(u^2 + v^2 = 1)로 제한해 봅시다.

 

선형대수학의 스펙트럴 정리(Spectral Theorem)에 따르면, 대칭 행렬(Symmetric matrix) M에 대한 이차형식:

 

의 최댓값과 최솟값은 바로 행렬 M의 고유값(Eigenvalue)과 정확히 일치합니다.

 

행렬 M을 고유값 분해(Eigendecomposition)하면 다음과 같이 쓸 수 있습니다:

 

이 좌표계를 고유벡터(Eigenvector)의 축으로 회전시키면, 복잡했던 에러 함수는 단순히 두 고유값에 지배되는 아주 직관적인 타원의 방정식으로 변모합니다:

 

조금만 u가 변하더라도 E가 크게 변하려면 두 고유값들이 커야한다. 이는 어느 방향으로 움직여도 error가 커지는 corner의 정의와 일치한다.

 

Scale-Invariance Feature Detection.

 

다양한 크기의 해바라기가 존재한다.

 

이전 글의 마지막에서 봤듯, harris corner detector는 scale variant합니다. 즉, corner detection window의 크기에 따라 검출할 수 있는 corner와 아닌 corner가 나뉘는 것입니다(큰 물체는 큰 window size, 작은 물체는 작은 window size). 이런 scale variant를 해결하기 위해 2차원 위치(x,y)만 탐색하던 기존 방식에서 벗어나, feature를 추출하는 영역의 크기(region size)까지 변수로 삼아 3차원 탐색을 수행합니다:

크기에 따라 검출되는 corner가 달라지며, 이를 고려하여 3차원 탐색이 이뤄져야한다.

 

아래의 그림은 1차원 단면 신호(블록 형태의 pulse) 위에 LoG 필터를 씌웠을 때의 response입니다:

highest response whem the signal has the same characteristic scale as the filter.

 

탐지하고자 하는 signal의 실제 크기(characteristic scale)와 filter의 퍼짐 정도(σ)가 정확히 일치할 때 가장 강력한 response가 도달함을 알 수 있습니다. 이를 2차원 이미지로 옮기면 다음과 같습니다:

we need to search over characteristic scales

 

오른쪽 그래프는 가로축 σ(필터의 크기)를 서서히 키워나가며 pixel response를 세로축 그래프로 그린 것입니다. blob의 둥근 크기와 필터의 폭이 일치하는 지점(약 σ=4.5)에서 거대한 peak가 발생합니다. 결론적으로 컴퓨터는 객체의 크기를 미리 알 수 없으므로, 가능한 여러 스케일(σ)의 필터를 모두 씌워보며 가장 강한 반응이 나오는 필터 크기를 채택해야 합니다.

 

* 그런데 왜 갑자기 LoG일까? Harris detector는 scale variant합니다. 따라서 scale factor σ가 있는 LoG filter를 사용해야 하며, LoG 필터는 구조적으로 가운데가 움푹 파이거나 솟아오른 둥근 종 모양을 띕니다. 따라서 이미지 내에서 자신과 비슷하게 생긴 둥근 형태(blob)를 만났을 때 가장 강하게 반응합니다.

 

* 그렇다면 blob을 feature로 사용하는건가? corner가 unique한 feature인 것은 맞습니다. 하지만, corner를 검출하는 데 있어서 harris를 사용하면 scale variant하므로, LoG를 이용해 blob의 형태를 갖는 feature를 찾는 문제로 변경한 것입니다. 즉 corner를 찾는 문제에서 blob을 찾는 문제로 바뀐것입니다.

 

* 그러면 corner를 scale invariant하게 찾고 싶다면 어떻게 해야할까? 먼저 이미지를 여러 scale(σ)에 대해 나열하여 3차원 tensor를 만듭니다. 그 후 각각의 scale에 대해 독립적으로 harris corner detector로 corner를 검출한 후, 그리고 찾아낸 corner 지점들에 대해서만, 여러 scale에 대해 LoG의 response를 측정합니다. response가 peak가 되는 scale을 해당 corner의 scale로 측정합니다.

 

다음은 아까 해바라기 그림에 대해서 각기 다른 크기의 LoG filter를 적용하고, 그 response를 시각화한 결과입니다:

작은 필터 크기(σ=2.1 or 4.2)를 갖는 LoG는 full size와 3/4 size에서 target pattern의 크기와 맞지 않기 때문에, 강한 response가 발생하지 않는다.

 

중간 필터 크기(σ=6 or 9.8)을 갖는 LoG는 각각 3/4 size와 full size에서 target pattern과의 크기가 맞아서 강한 response가 발생한다.

큰 필터 크기(σ=15.5 or 17)을 갖는 LoG는 두 이미지에서의 target pattern보다 너무 크기 때문에 강한 response가 발생하지 않는다.

 

이를 한 번에 정리하면 다음과 같습니다:

summary

 

위 그림을 통해 downsampling의 중요성을 알 수 있습니다. LoG의 σ를 6에서 60으로 키우려면, 수학적으로 filter의 크기도 13x13에서 100x100 이상으로 어마어마하게 키워야합니다. 커진 행렬로 conv 연산을 하면 연산량이 폭발하여 실시간 처리가 불가능해질 수 있습니다.

 

그래서 filter를 키우는 대신, filter의 크기는 작게 고정하고, 원본 이미지의 가로 세로 크기를 1/2, 1/4로 계속 축소시키는 방식을 사용합니다. 큰 해바라기가 들어있는 이미지를 축소하면 해바라기가 작아지므로, 작은 필터로도 충분히 response를 잡아낼 수 있기 때문입니다. 이렇게 만든 다중 해상도 이미지 layer를 gaussian pyramid라고 합니다.

 

구현은 다음과 같습니다:

scale-invariance corner detection: Implementation

 

아래는 예시입니다:

ex

 

How to efficiently implement LoG filter?

 

LoG 연산은 2차 미분이라서 너무 무겁고 느립니다. 따라서 DoG, Difference of Gaussian을 이용해 이를 근사합니다.

 

fig

 

위 그래프를 보면, 폭이 좁은 gaussian(작은 σ)에서 폭이 넓은 gaussian(큰 σ)을 단순히 빼 버리면, LoG와 유사한 종 모양의 그래프가 나옵니다. scale pyramid를 만들기 위해 이미지에 gaussian blur를 적용한 다음, 무거운 2차 미분(LoG) 필터를 굳이 새로 돌릴 필요 없이, 미리 만들어둔 두 gaussian blurred images를 서로 빼기만 하면, LoG를 씌운 것과 거의 똑같은 결과를 얻을 수 있는 근사 기법입니다:

Difference of Gaussian