Stereo matching - Global matching

본 장에서 Global matching의 한 종류인  dynamic programming 에 대해서 설정하겠습니다.

우선 알고리즘 설명 전에 기본적인 내용에 대해서 먼저 설명을 하고 넘어가겠습니다.

 

지역 정합 방법은  local 특성을 반영하지만 전체적인 특성 반영은 할 수 없습니다. 그럼 전체적인 특성이 무엇이 있는지 부터 알아봐야 겠지요?

 

Ⅰ. Uniqueness

- 정의하면, 반드시 1:1 매칭이 되어야 한다는 것입니다.

    + 서로 다른 물체의 점이 하나의 point에 매칭이 될 수 없다는 것을 의미합니다

- 아래의 그림은 uniquness가 위반되는 case를 그린 것입니다.

    + 좌측 카메라에서의 한점이 우측 카메라서 2point에 매칭점이 생겨서 위반되었다고 하는 것입니다.

Uniqueness 를  위반하는 것을 나타내는 그림

Ⅱ. Ordering

- 정의하면, 모든 관점에서 상응하는 point는 같은 순서로 존재하여야만 함

ordering을 나타내는 그림

- 아래의 그림은 ordering이 위반된 case 입니다.

    + 앞에 사물 'D'로 인해 뒤의 사물이 가려져 Ordering이 틀어졌지요?

orderin을 위반하는 case

Ⅲ. Smoothness

- 정의하면, 말그대로 부드럽다는 뜻이며, 선형적이라는 것입니다,.

    + Dispariry(시차)가 급격하게 변하지 않는 다는 것을 의미합니다.

Smooth 하지 않은 case

- non-continuous 한 영역이 거의 없다는 것을 의미합니다. → 이 말은 폐색영역(occulsion region)이 없다는 뜻

    + 폐색영역이 무엇인지는 아래 그림을 보면 알 수 있습니다.

        > left scanline 이라는 것은 left 영상의 y축 line 1개를 의미한다고 보면 됩니다.

        > 왼쪽에서는 검은색 칸이 보이겠지만 오른쪽 scanline에서는 보이지 않는 pixel 입니다.

        > 반대로 오른쪽에서는 파란색 칸이 보이겠지만 왼쪽 scanline에서는 보이지 않는 pixel 입니다.

        > 이러한 영역에 폐색 영역(occlusion region) 입니다

occulusion 영역에 대한 예시

Ⅳ. Dynamic programming

- Dynamic programming은 scanline 단위로 cost map을 산출하고, 최적의 경로를 찾아가는 알고리즘 입니다.

- 최적의 경로는 ordering constraint를 만족하는 것이구요

dynamic programming의 pseudo-code

- 위의 코드를 바로 보기보다는 아래의 예시를 먼저 보세요

    + 위쪽/왼쪽 1,2,3 을 표시한 것이 scanline의 pixel index입니다.

    + cost를 계산하고 나서,최소 값을 찾습니다.

        > 이떄 cost는 지역 정합 알고리즘의 한 방법으로 계산하시면 됩니다. (※ 이전에도 말했지요?)

        > 이떄에 대각선의 방향은 패널티가 없지만, (1,2) 위치와 (2,1) 위치의 경우에는 패널티 '5'가 더해집니다.

        > 대각선 방향은 (1,1), (2,2) 값이 더해지며, 나머지는 패널티가 더해집니다.

        >  이떄의 3가지 값이 산출되며, 이때에 최소 값은 대각선 방향의 값이 최소 값이 됩니다

    + 다시 아래의 case를 보시지요

        > 아래의 case에서는 (2.1)의 위치에 pixel이 최소값을 가집니다.

        > 해당 픽셀이 선택이 됩니다. 즉, 이때 시차가 '1'이 발생한 것입니다.

    + 정리하면 아래와 같습니다.

        > 우선적으로 지역정합 방법을 통해서, scanline에 대한 cost map을 계산합니다.

        > 그 다음에 dispariy를 계산하기 위해서, 경로를 탐색합니다.

        > (0,0) 위치에서부터 계속적으로 최소값을 더하면서 내려옵니다. 즉 누적되면서 내려옵니다.

        ※ weight 는 패널티라고 보셔도 됩니다.

        ※ 최적의 경로는 당연히 scanline을 위쪽 좌측에 배치하였을때, 대각선으로 지나가는 경로가 가장 best하겠지요. 여기서 벗어나게되면 시차가 발생했다고 봅니다.

        > 그래서 대각선에서 벗어나는 정도가 disparity가 됩니다.

Dynamic programming 계산

- Dynamic programming을 제가 예시로 그린 것이니 참고하시면 도움이 될 것 같습니다.

Dynamic programming 예

 

- 참고로 Dynamic programming방법은 scanline 단위로 수행을 하기 떄문에, y축에는 독립적이여서 오차가 row 단위로 나타나게 됩니다.

Dynamic programming 결과 예시