NCC(Normalized Cross Correlation)

NCC는 image processing에서 특히 template matching에 많이 이용됩니다.

template matching이란 입력으로 들어온 source image에서 원하는 template를 찾는 것을 말합니다.

template의 정의는 간단히 말하면 어떤 형태나 패턴이라고 말할 수 있습니다.

예를들면 얼굴인식이나 번호판 인식같은 물체인식을 template matching이라 볼 수 있습니다.

자세한 내용은 위키를 참고하세요 http://en.wikipedia.org/wiki/Template

template matching은 template image와 같은 사이즈의 window를 가지고 source image의 모든 subimage들과 비교하면서 유사도가 가장 높은 부분을 찾게 되는데,

크기가 같은 두 이미지 유사도를 구하는 방법 중 하나가 바로 NCC가 되는 것이죠.

그 유사도를 구하는 수학적 원리는 다음과 같습니다.

먼저 각 픽셀들을 벡터라고 생각합니다. (r,g,b) 이런식으로요.

그리고 벡터를 정규화(normalize)합니다.(벡터의 길이을 1로 만드는 작업이지요)

자 그렇다면 이 벡터들을 서로 내적했을 때 나올 수 있는 가장 큰 값은 얼마일까요????

바로 1입니다. 같은 두 벡터를 내적하는 경우죠.

반대로 가장 작은 값은 -1로 방향이 전혀 반대인 경우입니다.(하지만 r,g,b값은 음수가 없으므로 0이 최소)

결국 두 픽셀이 유사할수록 큰 값이 나오게 되는 것이죠.

다음은 NCC를 구하는 식입니다.

n : 픽셀의 개수

f (x,y): source image의 일부분인 subimage의 [x,y] 픽셀

t (x,y): template image의 [x,y] 픽셀

f bar : subimage 픽셀들의 평균

t bar : template image 픽셀들의 평균

omega f : subimage 픽셀들의 표준편차

omega t : template image 픽셀들의 표준편차

source image의 크기가 100px*100px 이고 

template image는 10px*10px 이라면

sub image의 총 개수는 100*100/10*10 = 100개, 크기는 10px*10px이 되는겁니다.

이렇게 template image와 유사도가 가장 높은 subimage를 찾아서 그 부분을 template과 매칭시키면 물체 인식이 되는 것입니다!

물론 이미지상에 물체가 존재하지 않을 경우를 생각해서 유사도가 threshold(임계값)을 넘어가는 경우에만 인식하도록 하는 것이 좋겠죠.