Stereo Matching has been one of the most active research topics in the area of computer vision. Many research works in this field have focused on either improving the accuracy of a resulting disparity map or reducing the processing time in a separate manner. However, there has been relatively little research effort in order to reduce computational complexity or processing time, while improving the accuracy of disparity estimation at the same time. In this thesis, a time efficient approach for real-time stereo matching is proposed. To this end, Dynamic Programming (DP), a popular global energy optimization algorithm, has been chosen to be a framework where the proposed approach is applied, since the DP is able to meet real-time requirements even in a computation-limited environment and thus implies its broad applicability. From extensive experiments, we show that the proposed method can significantly reduce the processing time to the extent that real-time implementation of disparity map estimation can be realized. In addition, a novel modified adaptive support-weight filter that is designed to guarantee reliable estimation of disparity map has also been successfully evaluated in comparison with conventional filters in our experiments. In conclusion, as opposed to most previous works with emphasis on hardware level optimization for the processing time reduction, the proposed approach can provide a time efficient method which is employed at an algorithm level. Further, it can preserve the reliable estimation accuracy by successfully addressing the errors (little increased by the proposed preprocessing time reduction) and even improve the overall estimation accuracy in a resulting disparity map.
스테레오 매칭(Stereo Matching 또는 Stereo Correspondence)은 Robot Vision 분야에서 가장 연구가 활발한 분야의 하나로서, 한 쌍의 2차원 스테레오 영상(즉, 좌영상과 우영상)으로부터 3차원 공간을 이해하거나, 또는 새로운 시점(View Point)의 영상을 생성하는 데에 있어 가장 우선적으로 해결이 되어야 하는 문제 중 하나이다. Dynamic Programming(DP)은 실시간 스테레오 매칭을 위해 널리 사용되고 있는 글로벌 최적화 알고리즘의 하나로서 계산 자원이 제한된 환경에도 적용이 가능하다는 장점을 갖는다. 이러한 DP의 장점은 과거에 비해 강력해진 계산 자원을 갖춘 스마트 폰에서 증강현실(Augmented Reality)이나 시점합성(New View Synthesis) 등의 응용구현하기 위한 플랫폼으로 적용하기에 적합한 특성을 제공할 수 있을 것으로 기대된다. 과거 DP와 관련한 많은 연구들은 알고리즘의 정확도를 개선하거나, 처리속도를 개선하기 위한 목적으로 수행되었다. 좀 더 구체적으로, 정확도는 알고리즘 수준에서 새로운 접근 방법에 의해 개선되어 왔으며, 속도 개선은 거의 대부분 하드웨어의 구조 변경이나 최적화 문제로 분리되어 연구되어 왔다. 이런 이유로 스테레오 매칭 알고리즘의 정확도와 처리속도를 동시에 개선하기 위한 연구는 매우 드물게 발견되며, 더욱이 처리속도 개선을 알고리즘 수준에서 해결하려는 시도는 거의 찾아보기 어렵다. 또한, 이상과 같은 기존 방법들에서 주목할 만한 점은 알고리즘의 정확도를 개선시키는 경우에는 반드시 알고리즘 수준에서 처리속도의 증가를 수반한다는 것이다. 본 논문에서는 우선 공간적 중복성 제거를 통한 스테레오 매칭 알고리즘의 처리 속도 개선 방안을 제안하고, 이를 Dynamic Programming 기반의 스테레오 매칭 알고리즘에 적용하여 제안된 방안의 유효성을 검증하였다. 또한, 공간적 중복성 제거에 부수하는 약간의 에러율 증가에 대처하기 위한 방안을 검토하고, 나아가 기존의 Adaptive Support Weight Filter의 개선 방안을 제시하였다. 이상을 통해, 본 논문에서는 스테레오 매칭 알고리즘의 처리속도와 정확도를 동시에 개선할 수 있는 방안을 제시하였다
우선, 간단한 예비실험 결과를 통해 공간적 중복성 제거시 깊이 영상(Disparity Map)에서 증가하는 에러율의 정도를 확인하였다. 공간적 중복성 제거는 Ground Truth 영상에 다운샘플링을 적용한 후 다시 인터폴레이션을 통해 원영상의 크기로 복원하는 방법을 취하였다. 각각의 모드에서 수직방향으로 1/2 및 1/3 샘플링을 취했고, 마지막으로 수평 및 수직 방향에서 각각 1/2 씩 전체적으로 1/4의 비율로 다운샘플링을 실시하였다. 이를 통해 매우 단순한 방법으로 공간적 중복성을 제거하더라도 증가하는 에러율이 매우 낮은 수준임을 알 수 있었다. 그러나 이러한 공간적 중복성 제거에 따라 감소되는 계산량은 상대적으로 매우 크다. 예컨대, 수직방향으로 1/2 다운샘플링을 적용할 경우, 기존 DP 기반의 화소 단위 스테레오 매칭 알고리즘에서 계산해야 할 매칭 코스트 어레이의 크기는 절반으로 줄어들게 되며, 이를 통해 적어도 이론상으로는 처리시간이 절반으로 단축될 수 있게 된다. 한편, 이러한 다운 샘플링은 수직방향으로만 실시하는 것이 바람직한데, 이유는 수평방향의 다운샘플링은 깊이 해상도(Disparity Resolution)에 영향을 주기 때문이다. 예컨대, 1/N의 샘플링을 수평방향으로 적용하는 경우, 깊이 해상도도 1/N으로 줄어들게 되어 스테레오 매칭의 결과로 생성되는 깊이 영상의 심각한 열화를 초래할 수 있기 때문이다.
제안한 방법의 실험을 위해 레퍼런스 모델로서 Bobick et al. [13]을 참조하여 가장 간단한 형태의 DP를 구현하였다. 비교 대상인 구현예에서는 모두 수직방향의 1/2 다운샘플링을 통해 입력영상을 처리하되, Cost Aggregation 단계에서 서로 다른 필터를 사용하였다. 실험영상은 Middlebury 웹사이트에서 제공하는 가장 대표적인 4가지 영상인 Tsukuba, Venus, Teddy, Cones 등을 사용하였다. 각각의 구현예의 구체적인 구성을 살펴보면, 구현예 1 에서는 DP에 적용되는 파라미터를 더욱 세분화해서 사용하였고, 구현예 2 에서는 여기에 $3\times1$ 가우시안 필터링을 더 적용하였으며, 구현예 3 에서는 $6\times1$ 크기의 ASWF를 구현예 4 에서는 $12\times1$ 크기의 ASWF를 각각 사용하였고, 마지막으로 구현예 5에서는 제안하는 개선된 ASWF를 $12\times1$ 크기로 적용하였다. 예상했던 바와 같이 각각의 구현예에서 상당한 처리시간 감소가 나타나고 있으며, ASWF와 같은 복잡한 필터를 사용한 경우에도 여전히 가장 간단한 DP보다 짧은 처리시간을 나타내고 있는 점은 특히 주목할 만하다. 또한, 실험 결과는 Cost Aggregation 단계에서 적용된 다양한 필터에 의해 정확도가 개선되는 것을 보여주며, 특히 제안된 Modified Adaptive Support Weight Filter (MASWF)에 의한 정확도 개선이 가장 두드러지게 나타났다. Gestalt 원리 중 기존의 유사성과 인접성 외에 연속성이라는 요소를 함께 고려한 MASWF는 레퍼런스 알고리즘에 비해 에러율을 평균 36.55%만큼 낮추었다.
본 논문에서 제안한 알고리즘 수준에서의 처리시간 단축 방법은 Dynamic Programming 기반의 스테레오 매칭 알고리즘뿐만 아니라 일반적으로 처리시간 개선의 요구가 있는 스테레오 매칭 알고리즘에 널리 적용이 가능할 것으로 기대된다.