Dynamic Programming 을 이용한 Stereo Matching (이론)

Disparity Space Image (DSI)

DSI란, Reference 이미지와 Target 이미지의 특정 row를 따라 patch를 옮겨가며 pairwise match score를 나타낸 것이다.

이러한 DSI는 모든 row에 대해서 생성되어 총 $r$개의 $c \times c$ size의 DSI가 생성된다.

위의 생성된 DSI를 보면 Left scanline과 Right scanline으로 이루어져 있으며, DSI의 대각선보다 약간 오른쪽에 검정색 선이 존재하는 것을 볼 수 있다. 이 선이 disparity에 대한 정보를 닮고 있으므로 아래와 같이 선 주위만 사용하여 disaprity를 계산한다.

DSI and Scanline Consistency

Left scanline의 모든 pixel에 disparity를 할당하는 것이 결과적으로 DSI를 통해 연결된 path를 찾는 것과 같다.

Lowest Cost Path

왼쪽 이미지는 Occlusion과 Disocclusion일 발생하지 않은 Path를 의미하고, 가운데 이미지는 Occlusion이 오른쪽 이미지는 Disocclusion이 발생한 Path를 의미한다.

Occlusion : Reference 이미지에는 보이지만 Target 이미지에는 보이지 않는 영역
Disocclusion : Target 이미지에는 보이지만 Reference 이미지에는 보이지 않는 영역

Dealing with Occlusions

위와 같은 방식으로 Occlusion과 Disocclusion을 검출할 수 있음.

Search Over Correspondeces

Matching : 대각선
Occlusion : 왼쪽
Disocclusion : 오른쪽

위의 방식으로 매 Path를 결정할 때마다 dissimilarity에 따라 direction을 결정한다. 이러한 방식으로 optimal한 path를 찾기 위해 Dynamic Programming 기법을 사용한다.

Optimal Path using Dynamic Programming

1. DSI를 이용하여 cost matrix를 구한다.

$C_b=Cost(i, j-1)+O_{cc_{penalty}}$
$C_c=Cost(i-1, j-1)+DSI(p)$
$C_a=Cost(i, j-1)+O_{cc_{penalty}}$

$C_a,C_b,C_c$는 각각 수평, 수직, 대각선 방향의 누적연산을 나타내며, 대각선 방향의 경로는 DSI이 누적되지만, 수평 혹은 수직방향의 경로의 경우 DSI 상의 값 대신 penalty 값을 누적한다. 이와 같이 계산된 cost matrix의 값 중 최소값을 최적화된 disaprity의 값으로 선택한다.

2. Back Tracking

cost matrix의 각 위치에서 그 전으로부터 진행방향을 저장했다면, 최종 disparity 값은 역방향으로 경로를 추적하여 쉽게 얻을 수 있다.

Streaking

cost matrix를 계산할 때 사용하는 penalty의 값은 Back tracking 과정에서 경로선택에 큰 영향을 미친다. penalty 값이 작다면 수평 또는 수직방향의 경로가 선택될 가능성이 높고 크다면 대각성 방향의 경로가 선택될 가능성이 높아진다. 일반적인 영상은 동일한 disparity를 가지는 부분이 많기 때문에 보통 큰 penalty를 사용하고 이는 물체의 수평/수직 방향으로 진행되어야하는 경계부분에서 대각선 방향으로 경로가 결정되는 문제가 발생하며 이를 Streaking이라고 부른다.

참고
https://velog.io/@dbgpwl34/ComputerVision-Stereo-Using-Dynamic-Programming
https://scienceon.kisti.re.kr/commons/util/originalView.do?cn=JAKO201029335103010&dbt=JAKO&koi=KISTI1.1003%2FJNL.JAKO201029335103010