모라벡(Moravec) 알고리즘

모라벡(Moravec) 알고리즘.

제곱차의 합SSD(sum of squared difference)

\[\textcolor{Black}{ S(v,u)=\sum_y\sum_x w(y,x)\big(f(y+v,x+u)−f(y,x)\big)^2 \quad (4.1) }\]

f(.,.)는 입력 영상이고 w(.,.)는 마스크이다. 현재 처리 중인 화소가 수식에 명시적으로 나타나지 않는다. 마스크 w(y,x)는 (암시적으로 정해져 있는) 현재 화소를 중심으로 실제 계산에 참여할 곳을 지정한다. w(y,x)는 현재 화소에 씌운 박스형 마스크인데, 박스 내의 화소는 1, 그 외의 모든 화소는 0을 갖는다. 박스 내의 화소에 대해서만 계산을 하는 셈이다. 컨볼루션은 현재 화소에서 한 개의 값만 생성하는 반면, 식 (4.1)은 (v,u)를 변화시켜가며 마스크 화소 각각에 대해 값을 생성한다. 따라서 [그림 4-3(b)]와 같이 S(v,u)라는 맵이 만들어진다.

만일 현재 조사 중인 화소가 c와 같이 변화가 없는 곳인 경우, (v,u)를 변화시키며 주위를 조사하면 S(v,y)는 어느 방향으로든 낮은 값을 갖는다. 화소 c는 변화가 전혀 없으므로 아홉 개의 요소 모두 0을 갖는다. 이제 경계에 위치한 b를 살펴보자. 이곳의 에지는 세로 방향인데 그 방향으로는 낮은 값을 갖는 반면, 에지와 수직인 가로 방향으로 큰 값을 갖는다. 물체의 코너에 해당하는 a는 모든 방향에서 큰 값을 갖는다. 즉, 제곱차의 합이라는 함수 S는 어떤 점이 다른 곳과 얼마나 두드러지게 다른지 측정해 주는 역할을 한다. 물체의 코너는 두드러지게 다른 곳이므로 S를 코너일 가능성 정보로 해석할 수 있다.

모라벡은 [예제 4-1]과 같이 3x3 크기의 박스형 마스크를 사용하였으며, 동서남북 네 방향으로 한 화소만큼 이동시켜 얻은 네 개의 값 즉 (S(0,1), S(0,-1), S(1,0), S(-1,0))만 사용하였다. 그는 어떤 점이 코너라면 네 방향 모두 변화가 커야 한다고 보고, 네 값의 최솟값을 지역 특징일 가능성 값으로 간주하였다. 식 (4.2)는 모라벡이 정의한 ‘특징 가능성’ 값이다.

\[\textcolor{Black}{ C=min⁡ \big(S(0,1),S(0,−1),S(1,0),S(−1,0) \big) \quad (4.2) }\]

출처 - Computer Vision