One of the most challenging problems in stereo vision is to find corresponding image points in stereo image pair. In this thesis, a robust stereo disparity estimation algorithm is proposed and its experimental results are presented. The proposed algorithm combines the area-based search and the dynamic programming search. The robust disparity values are determined in some area by the area-based search according to certain criteria. The other areas where disparity values are not determined by the window-based search are estimated by dynamic programming.
The proposed algorithm consists of three subparts - segmentation of homogeneous region and background, adaptive window search, and dynamic programming search. Most of the stereo algorithms may fail to find exact disparity value of homogeneous regions. Therefore, our algorithm extracts non-textured homogeneous region whose variance is less than a certain threshold by ordered seed filling algorithm. Adequate disparity value for such region is assigned by interpolation using the reliable disparity of the region boundary.
We use adaptive-size window for the disparity estimation. The window size is determined adaptively from local variance for every pixel in a picture. If the matched result by the window search is not credible, the pixel point is reserved to a dynamic programming for more reliable estimation. We form the disparity space image for the unreliable pixel points, and applied the dynamic programming algorithm to them. The optimal path is obtained by tracing the path that has the minimum cost, so that final disparity value is acquired.
Experiment results for several stereo images show that the proposed algorithm outperforms the window or dynamic programming only methods. We construct the left image with the right image according to the disparity value. Then, we compare the reconstructed left image with the original left image, and calculate the PSNR (Peak Signal-to-Noise Ratio) results in most of the images.
There are several contributions of the proposed algorithm as follows: Firstly, robust points whose disparity values are measured with the adaptive-size window are distributed over a whole image. Therefore, the error caused by incorrect disparity is not propagated to the whole area. Secondly, the dynamic programming improves the spatial resolution of the disparity map. Thirdly, non-textured homogeneous regions are extracted and adequate disparity values are assigned to them so that we can avoid large errors in these areas. The proposed algorithm may be applicable for multimedia or broadcasting technologies such as a depth keyer.
스테레오비전(Stereo Vision)에서 가장 난해한 문제 중의 하나가 좌우 영상의 대응점을 찾는 것이다. 본 논문에서는 효율적인 양안시차(disparity) 추정 알고리즘을 제안하였고 실험 결과를 제시하였다. 제안된 알고리즘은 적응 윈도우를 사용한 영역기반 스테레오 정합법과 양안시차 공간 이미지에 기반한 다이내믹 프로그래밍(dynamic programming) 기법을 사용한다. 윈도우 기반 탐색 시 어떤 제시 조건에 의해 화면의 일부 영역에서 양호한 양안시차 값이 구해진다. 윈도우 기반 탐색으로 양안시차가 결정되지 않은 나머지 영역에서는 다이내믹 프로그래밍법으로 탐색을 한다.
제안된 알고리즘은 1) 균질영역(homogeneous region)과 배경영역의 분할, 2) 적응 크기 윈도우(adaptive size window) 탐색, 3) 다이내믹 프로그래밍 탐색의 세 부분으로 구성된다. 대부분의 스테레오 알고리즘은 화면의 변화가 적은 균질 영역에서는 정확한 양안시차를 추정하기 어렵다. 따라서 제안된 알고리즘에서는 텍스처가 희박한 균질 영역의 분산 값이 어떤 범위를 넘지 않는 것을 이용하여 ordered seed filling 알고리즘으로 추출한다. 추출된 영역 내부의 양안시차는 경계 영역의 값으로부터 보간(interpolation)하여 적당한 값으로 채워 넣는다. 배경영역은 판별 조건에 의해 추출되어 처리 된다.
양안시차 추정을 위해 적응 크기 윈도우를 사용한다. 윈도우의 크기는 화면내의 각 화소에 대한 분산 값으로부터 적절한 크기가 결정된 후 그 크기의 윈도우로 양안시차를 추정한다. 윈도우 탐색으로 구해진 양안 시차가 신뢰성이 있는가를 판별하여 그렇지 않으면 보다 정확한 추정을 위해 다이내믹 프로그래밍 파트로 넘긴다. 추정해야 할 화소에 대해 양안시차 공간 이미지를 형성하여 다이내믹 프로그래밍을 적용시키며 최소 비용을 가지는 경로를 추적하여 최적의 경로를 결정한 후 이에 의해 최종 양안시차 값이 구해진다.
여러 개의 실제 스테레오 이미지들에 대해 시뮬레이션 한 결과, 제안된 알고리즘에 의한 것이 윈도우만을 사용하거나 다이내믹 프로그래밍만을 사용했을 때보다 성능이 우수하였다. 구해진 양안시차 값을 이용하여 우안 화상으로부터 좌안 화상을 재구성하고 원래의 좌안 화상과 비교하여 신호 대 잡음비(PSNR)를 계산하였다. 일반적으로 제안된 알고리즘에 의한 결과가 대부분의 이미지에서 좋은 PSNR을 가짐이 확인되었다.
본 논문에 의한 성과를 들어 보면, 1) 적응 크기 윈도우에 의해 구해진 신뢰성 있는 양안시차 값은 화면의 일부에 편중되지 않고 전체에 분포해 있으므로, 잘못 구해진 양안시차에 의해 오류가 넓은 영역에 전파되는 것을 방지할 수 있고, 2) 객체의 경계 영역을 윈도우 기법에 의해 추정하면 무뎌지기 쉽지만 제안된 알고리즘에서는 다이내믹 프로그래밍이 이 부분을 대부분 담당하므로 경계에서의 또렷한 양안시차가 구해져 결과적으로 양안시차 맵(map)의 공간 해상도가 증가되며, 3) 텍스처가 희박한 균질 영역이 추출되어 적합한 양안시차 값이 할당되므로 오류가 적어지며, 4) 계산량이 적당하여 하드웨어로 구현 가능하다. 양안시차 추정은 스테레오 비전의 기반기술의 하나이며 제안된 알고리즘은 멀티미디어나 방송기술 분야에 요소 기술로 적용될 수 있는데, 두 영상을 합성하는 ‘깊이를 이용한 키어’(depth keyer) 가 하나의 예이다.
