[Vision] Cross Correlation의 해석 (feat. Hessian)

Image Matching에 대해 공부를 하던 중 Cross Correlation에 대한 내용을 학습하게 되었는데 수학적인 지식이 부족한 탓인지 이 부분에서 등장하는 여러 가지 용어가 너무 무섭게 다가왔어요..
그래서 Quadratic Form, Hessian Matrix 등 여러 개념에 대해 알아가면서 Cross Correlation와 좀 더 끈적한 사이가 되어 볼까합니다 :)

---

Cross Correlation

Source Image

Template



위와 같이 원본 Image가 있고 Template Image가 있을 때,
Template를 원본 Image에 매칭시키기 위해서 Cross correlation 기법을 사용해요.

위의 이미지 좌표와 같이 image상에서 template이 어디에 있는가는 무엇을 통해 알 수 있을까요?
$g_1$(image)와 $g_2$(template) 사이의 similarity of intensity values (각 픽셀 값의 유사성 정도)가 높아야 해요.

이 값이 높은 $[u,v]$ offset를 찾아야 하는 것이 목적이에요.
Similarity 비교는 아래와 같은 방법을 사용할 수 있어요.

• SSD : Sum of squared differences
  $SSD = \sum_{m}{(g_2(m) - g_1(m))^2}$
• SAD : Sum of absolute differences
  $SAD = \sum_{m}{|g_2(m) - g_1(m)|}$
• Maximum of differences
  $Max = max_{m}{|g_2(m) - g_1(m)|}$

최종 offset를 구하기 위해선 다음과 같은 식을 활용해요.

$[\hat u, \hat v] = argmax_{u,v} \rho_{12}(u,v)$

$\rho_{12}(u,v) = \frac{\sigma_{g_1g_2}(u,v)}{\sigma_{g_1}(u,v)\sigma_{g_2}}$

여기서 NCC 개념이 등장-!

---

NCC : Normalized Cross Correlation

$\rho_{12}(u,v) = \frac{\sigma_{g_1g_2}(u,v)}{\sigma_{g_1}(u,v)\sigma_{g_2}}$


$\sigma_{g_1g_2}(u,v)$ : template과 (u,v)에서의 image 사이의 분산
$\sigma_{g_1}(u,v)$ : template 에 의해 오버랩되는 image의 영역에서의 표준편차
$\sigma_{g_2}$ : template의 표준편차

이런 식을 통해 $\rho_{12}(u,v)$의 값이 최대가 되는 지점을 찾아가면 원하는 offset를 찾을 수 있어요.

---

근데 위의 과정들은 Pixel 단위에서 연산이 이루어지기 때문에 아주 조금은 부정확한 결과가 나올 수 있어요..!
좀 더 정확한 offset를 구하기 위해 Subpixel Estimation 방법이 나오게 되는데 이 부분부터 내용을 이해하기 힘들었어요..

Subpixel Estimation for Cross Correlation

Pixel 단위를 integer 단위로 본다면 Subpixel은 float 단위로 본다는 의미에요.
그러면 좀 더 정확한 연산 결과를 기대할 수 있겠죠?

처음부터 아래의 식을 진행하는 것이 아니라 NCC를 통해 얻은 offset이 있겠죠?
아마 그 지점 부근이 Maximum값이 존재할 가능성이 큰 지역일테니 해당 offset에서 진행을 해요.

파란 점은 pixel의 이산분포, 빨간 선은 Subpixel의 연속분포라고 생각하면...아하!
그러면 만약 실제로 분포과 위의 그래프처럼 되어있다고 생각을 해볼까요?

최대값을 구하기 위해선 해당 함수의 극점을 알아야해요.
이 다변수 함수를 $\rho(x)$라고 하고 Quadratic Form의 형태를 취해서 나타낼 수 있어요.

Matrix of Quadratic Form

Any n×n real symmetric matrix A determines a quadratic form Q_x in n variables by the formula
출처 : https://en.wikipedia.org/wiki/Quadratic_form#Definitions

위의 내용에 따르면 대칭행렬 A에 대해서 n변수 함수의 Quadratic Form은 해당 n변수 함수에서 정의된 함수를 말하고,
이는 $Q(x)=x^⊺Ax$ 로 표현이 가능하겠네요..!

$Q$가 $u, v$에 대한 다변수 함수라면 다음과 같이 풀어 쓸 수 가 잇어요.

모든 항이 2차인 이차 형식이 충족하는 것을 알 수가 있긴한데 그러면 대칭행렬 A는 어디서 구할 수 있을까요??

여기서 Hessian Matrix가 등장하게 됩니다.

---

Hessian Matrix

다변수 함수 $f(x_1,x_2, ... x_n)$ 에 대해서 Hessian Matrix는 아래와 같아요.

${\displaystyle \mathbf {H} _{f}={\begin{bmatrix}{\dfrac {\partial ^{2}f}{\partial x_{1}^{2}}}&{\dfrac {\partial ^{2}f}{\partial x_{1}\,\partial x_{2}}}&\cdots &{\dfrac {\partial ^{2}f}{\partial x_{1}\,\partial x_{n}}}\\[2.2ex]{\dfrac {\partial ^{2}f}{\partial x_{2}\,\partial x_{1}}}&{\dfrac {\partial ^{2}f}{\partial x_{2}^{2}}}&\cdots &{\dfrac {\partial ^{2}f}{\partial x_{2}\,\partial x_{n}}}\\[2.2ex]\vdots &\vdots &\ddots &\vdots \\[2.2ex]{\dfrac {\partial ^{2}f}{\partial x_{n}\,\partial x_{1}}}&{\dfrac {\partial ^{2}f}{\partial x_{n}\,\partial x_{2}}}&\cdots &{\dfrac {\partial ^{2}f}{\partial x_{n}^{2}}}\end{bmatrix}}}$

일단 위의 행렬의 성분에 대해 먼저 알아볼게요.

정의 그대로 일단 다변수 함수에서 각 변수에 대한 이계도함수(2차 미분)를 성분으로 가지는 행렬이에요.
계속 이계도함수 이계도함수하는데 이계도함수가 가지는 특징은 뭐가 있을까요?
위 2차함수의 그래프에서 알 수 있듯이 해당 함수를 두 번 미분해서 얻은 이계도함수 값은 함수의 곡률(볼록한 정도)를 나타내요.
음수라면 위로 볼록하겠죠?

오께이

이제 그럼 Hessian Matrix가 대칭인 이유를 보면
클레로의 정리 에 따라 $dxdy와 dydx$가 같기 때문에 Hessian Matrix는 대칭인 것을 쉽게 확인할 수 있어요.

• 클레로의 정리
  $f$가 영역 $D$에서 점 (a,b)를 포함한 함수라고 하자. $f$가 연속인 이계 편도함수를 가질 때
  $f_{xy}(a,b) = f_{yx}(a,b)$가 성립한다.

Hessian Matrix가 Quadratic Form에서 가지는 특징이 또 있는데,
바로 Hessian Matrix의 고유값의 부호에 따라 Quadratic Form의 정부호성을 판별을 할 수가 있어요.

정부호성..? 끊임 없이 생소한 개념의 연속이었슴미다..

---

정부호성

이변수 함수 $f(x,y) = x^2 + y^2 + 2xy$ 에도 일반적인 이차 함수와 같이 극값을 가지고 있어요.
근데 극값 말고도 안장점이라는 것도 가지고 있는데,
이는 보는 차원에 따라 극소점이 될 수도, 극대점이 될 수도 있는 점이랍니다.

일단 이 함수를 미분해서 극값을 구해볼까요?

$\frac{df}{dx} = 2x + 2y$
$\frac{df}{dy} = 2y + 2x$

미분값이 0이 되기 위해선 $x,y = 0$ 여야지 될 것 같네요.
극소인지, 극대인지, 안장점인지는 모르겠지만 일단 이 세 가지 개념을 포괄하는 임계점을 구했어요!

근데 $f(x,y) = x^2 + y^2 + 2xy = (x+y)^2$ 이고, 이 함수는 음수 값이 없겠죠?
그리고 $f(0,0)=0$ 인 것으로 미루어보아 이 함수는 $x,y =0$에서 $0$를 극소점을 가지는 것을 알 수가 있어요.
이와 같이 해당 함수에서 다른 좌표에서의 값이 임계점에서의 값보다 모두 큰 경우를 양의 정부호라고 해요.

그러면 나머지는 쉽죠?
임계점의 값이 가장 큰 경우가 음의 정부호에요.

이를 우리가 원하는 함수에 적용시켜 볼게요.

$Q(x)=\begin{bmatrix}u&v\end{bmatrix} \begin{bmatrix}a &b\\b&c\end{bmatrix}\begin{bmatrix}u\\v\end{bmatrix}$

$= au^2 + cv^2 + 2buv$

$= a(u+\frac{b}{a}v)^2 + (c - \frac{b^2}{a})v^2$이므로

양의 정부호가 되려면 $a > 0$ 이고 $ac>b^2$ 여야 해요.
음의 정부호가 되려면 $a < 0$ 이고 $ac>b^2$ 여야 하죠.
안장점이 되려면 $ac<b^2$ 면 돼요.

이러한 위치에서의 특징은 2차 미분 값이 0이라는 점이에요.
Hessian Matrix를 통해 2차 미분 값을 구하고 이 값이 0에 가까운 지점을 찾으면 픽셀 값의 변화가 큰 지점이겠죠?

---

이렇게 Hessian Matrix로 정부호성을 판단하는데 사용이 된다고 해요.
다시 본론으로 돌아와서 우리는 이제 목적 함수를 다음과 같이 정의할 수 있어요.

$\rho(x) = (x-x^*)^TA(x-x^*) + a$

• $x^*$ : 우리가 얻으려는 maximum값의 위치로 볼 수 있겠고
• $x$ : 아까 말했 듯이 NCC를 통해 얻은 offset이에요.
• A : 2x2 Hessian Matrix고,
• $a$ : 1D 변수이에요.

자 이 식을 미분해서 극값을 구해볼까요?

$\frac{d\rho(x)}{dx} = 2A(x-x^*)$ <- 이 부분은 행렬 미분 공식인 듯 합니다..

At maximum : $\frac{d\rho(x^*)}{dx} = 0$

여기서 2A를 새로운 Hessian Maxtrix로 치환을 해주고 다시 표현해볼게요.

$\frac{d\rho(x)}{dx} = H_\rho(x-x^*)$

-> $H_\rho^{-1}*\frac{d\rho(x)}{dx} = (x-x^*)$

-> $x^* = x - H_\rho|_x^{-1}*\frac{d\rho(x)}{dx}|_x$

가 될 것이고 각 요소를 살펴보면 아래와 같아요.

$x = \begin{bmatrix}\hat u\\\hat v\end{bmatrix}$

$\frac{d\rho(x)}{dx}|_x = \begin{bmatrix}\rho_i\\\rho_j\end{bmatrix}_x$

$H_\rho|_x^{-1} = \begin{bmatrix}\rho_{ii}&\rho_{ij}\\\rho_{ji}&\rho_{jj}\end{bmatrix}_x$

여기서 $\rho$ 값들은 Hessian 성분들의 이차 미분을 위한 Sobel Operator에요.

왜 Sobel 연산을 하였더니 저런 형태의 행렬을 취하는지, Sobel Operator는 뭔지
한 번 알아볼게요.

---

Sobel Operator

Sobel Operator는 이미지에서 Edge를 Detection 하는데 사용되는 검출기라고 해요.
기본적으로 3x3 Matrix의 형태를 가지는데 정확한 값은 아래와 같아요.

$x ~filter=\begin{bmatrix}-1&0&1\\-2&0&2\\-1&0&1\end{bmatrix},~~~~~~ ~y~filter=\begin{bmatrix}1&2&1\\0&0&0\\-1&-2&-1\end{bmatrix}$

얘네들로 Edge 검출을 어떻게 한다는 걸까요?

출처 :
https://www.youtube.com/watch?v=5YAA7vS6kVU&t=2459s
https://ko.wikipedia.org/wiki/%ED%97%A4%EC%84%B8_%ED%96%89%EB%A0%AC
https://m.blog.naver.com/enewltlr/220918689039
https://bskyvision.com/661