모라벡 알고리즘

모라벡 알고리즘

모라벡 알고리즘은 다음 식과 같다.

                         [식 1] 모라벡 알고리즘

[식1]은 제곱차의 합(SSD-Sum of Squared Difference)를 사용해 화소에 특징점의 여부를 판별하는 식이다.

f(..)는 입력 영상이고, w(..)는 마스크이다. w의 크기는 비교할 범위를 나타내며, 박스 내의 화소에 대해서만 

비교 연산을 하면 된다.

         

         

                             [그림 1] 12x12 이미지

[그림 1]의 이미지는 12×12크기의 이미지 속 삼각형을 나타내는 이미지이다.

현재 점은 b(5, 3)의 위치에 있다고 가정하고 제곱차 합을 계산해 보겠다. 마스크의 크기는 3x3이다.

a, b, c 세 지점에서 S(u,v)맵을 구해보면 다음과 같다.

     

                    [그림 2] a, b, c위치에 따른 S(u,v)맵

[그림 2] 를 보면 세 지점에서 S(u,v)맵이 각각 다르게 나타냄을 확인할 수 있다.

화소 c의 경우 변화가 전혀 없으며 아홉 개의 요소 모두 0을 갖는다. 

화소 b의 경우 에지는 세로 방향인데, 그 방향으로는 낮은 값을 갖는 반면, 에지와 수직인 

가로 방향으로는 큰 값을 갖는다. 물체의 코너에 해당하는 a는 모든 방향에서 모두 큰 값을 갖는것을 확인할 수 있다.

즉, 제곱차의 합은 어떤 점이 다른 곳과 얼마나 두드러지게 다른지 측정해 주는 역할을 한다.

물체의 코너는 두드러지게 다른 곳이므로 S를 코너일 가능성 정보로 해석할 수 있다.

            

                  [그림 3] 원래 영상

       

[그림 4] 9×9 마스크로 측정한 S맵(밝을수록 큰값)

[그림 3]을 보면 a, b, c의 화소에 따라 S맵을 출력한 결과 [그림 4]를 볼 수 있다.

[그림 4]를 보면 화소 a의 경우 사슴의 눈으로, 모든 방향에서 명암의 변화가 심하다. 따라서 S맵의

모든 화소가 큰 값을 갖는다. b는 대각선 방향의 에지에 위치하는데, 에지 방향으로는 낮은 값을 갖지만

에지에 수직한 방향으로는 큰  값을 가진다. 변화가 거의 없는 c는 아주 낮은 값을 갖는다.

모라벡은 3×3 크기의 박스형 마스크를 사용하였으며, 동서남북 네 방향으로 한 화소만큼

이동시켜 얻은 네 개의 값 S(0, 1), S(0, -1), S(1, 0), S(-1, 0)만 사용하였다. 모라벡은 어떤

점이 코너라면 네 방향 모두 변화가 커야 한다고 보고, 네 값의 최소값을 지역 특징일 가능성 값

으로 간주하였다.

            

모라벡 알고리즘은 한 화소에대해 네 방향만 보고 특징점 여부를 계산하고, 

잡음에 대한 대처 방안이 없다는 단점이 존재한다.

참조 : 컴퓨터비전(오일석)