📝시작하기전에...
저희는 앞으로 두 영상을 매칭시키기 위해 다음 과정을 거칠 것입니다.

1. 지역특징을 검출한다.👨‍🏫
2. 특징을 기술한다.
3. 특징을 매칭시킨다.

이번 포스팅에서는 지역특징 검출하기에 대해 알아보겠습니다. 그중에서도 모라벡 알고리즘과, 해리스 코너 검출 (Harris corner detector)에 대해 알아보겠습니다.

특징이란❔

---

저희는 영상의 매칭을 위해 특징을 추출해야 합니다. 그렇다면 특징이란 무엇일까요?

1번에서 보라색 사각형이 약간 움직이더라도 갖고 있는 정보에는 변화가 없습니다. 2번의 경우 사각형이 화살표 방향으로 움직이면 역시 변화가 없습니다. 그러나 3번에서 사각형이 어느 방향으로 움직이든 정보가 달라질 것입니다. 즉, 3번이 특징이 됩니다. 영상에서 특징을 추출하는 알고리즘에 대해 알아보겠습니다.

✨모라벡 알고리즘

---

이제 보라색 사각형 네모를 window함수라고 부르겠습니다. window함수를 $(u,v)$만큼 움직인 후, 원래 위치의 값과 얼마나 차이가 나는지를 계산합니다. 이 값이 크면 특징이 되는 것이죠.

window함수❔

window함수는 일부 영역을 선택하기 위해 사용됩니다.
window영역에 해당되면 1, 해당되지 않으면 0을 곱해줍니다.

그렇다면 원래 위치와 움직인 위치의 차이는 어떻게 계산할까요? 바로 제곱차의 합을 의미하는 SSD를 사용하여 계산합니다.

원래 위치와 $(u,v)$만큼 움직인 위치의 차이를 $E(u,v)$라고 할 때, 각 픽셀에서의 차를 구하고 제곱을 합니다. 이때, window함수가 있는 부분만 계산하기 위해 $w(y,x)$곱해줍니다.

SSD를 이용하여 $E(1,0), E(1,1), E(0,1),E(-1,1)$을 계산하고, $E(u,v)$최솟값의 값이 클 때 특징점으로 판단합니다.

🙋‍♀️
즉, 모라벡 알고리즘에서는 4방향으로의 정보의 변화량인 $E(u,v)$을 측정하고, $minE(u,v)$가 클 때 특징이라고 판단합니다.

모라벡 알고리즘의 한계점

• window함수는 사각형이며 1과 0으로만 이루어져 noise에 취약합니다.
• 네방향으로만 이동하여 45도 외의 방향은 고려되지 않습니다.
• $E(u,v)$의 최솟값만 고려하여 다른 값은 고려하지 않습니다.
  
  

✨해리스 코너

---

해리스 코너는 모라벡 알고리즘의 한계점을 보완한 방법입니다.

1. Noise에 취약한 문제
   ✅ window함수로 Gaussian함수를 사용합니다.

2. 45도 외의 방향의 edge는 고려되지 않는 문제
   ✅ 테일러 전개 (Taylor expansion)을 사용하여 모든 방향의 shift를 고려합니다.

3. $E(u,v)$의 최솟값만 고려하여 다른 값은 고려하지 않는 문제
   ✅ $minE(u,v)$대신 $E(u,v)$의 변화값을 고려합니다.
   
   

$(u,v)$의 값이 작을 때, $E(u,v)$는 테일러 전개를 사용하여 나타낼 수 있습니다. 1차 테일러 근사는 다음과 같습니다.

해리스 코너에서는 테일러 전개를 SSD에 적용합니다.



위의 식을 다음과 같이 정리할 수 있습니다. 표시한 부분을 M matrix라고 하겠습니다.

M 행렬에 고유값 분해를 적용하면 gradient방향을 나타내는 고유 벡터와 gradient의 크기를 나타내는 고윳값으로 나타낼 수 있습니다.

고유값과 고유벡터를 이용하여 C(Conerness Score)를 계산하면 특징점을 찾을 수 있습니다. C가 threshold보다 큰 값을 가지면 특징점이 됩니다.

하지만 고유값 분해는 연산이 오래걸리므로 다음 식을 대신 사용할 수 있습니다.

C값이 threshold보다 큰 곳이 픽셀이 아닌 영역으로 나타난다면 Non-maxima suppresion을 이용하여 영역에서 가장 큰 값을 가지는 픽셀만 특징점으로 결정합니다.


이론설명까지 여러 식을 사용하여 해리스 코너에 대해 설명을 했습니다. 차근차근 살펴보면 크게 어려운 내용은 없지만 행렬 연산, 고유값분해 등 몸이 거부반응을 일으킵니다... 해리스 코너의 과정을 살펴보며 간단히 정리해볼까요?

해리스 코너의 과정

1. Gaussian Filter를 사용하여 이미지의 noise를 줄입니다.

2. Image의 gradient를 계산합니다.($f_x,f_y$)

3. M matrix를 계산합니다.
   

4. M matrix에 window함수(Gaussian)를 적용합니다.
   $g(f_x^2), g(f_y^2), g(f_xf_y)$

5. C를 계산합니다.
   

6. C값에 Threshold를 적용하여 특징점을 찾습니다.
   (C값이 threshold보다 클 경우 특징점입니다.)

7. Non-maxima suppresion을 적용하여 특징 중 가장 큰 값만 남깁니다.

👍수고하셨습니다! 특징점을 찾는 방법에 대해 알아보았습니다. 하지만 아직 매칭을 하기에는 특징점에 대한 주변 정보가 부족합니다. 따라서 다음시간에는 특징에 대한 정보를 제공하는 특징기술자에 대해 알아보겠습니다.