Linear-Time Computation of Segment-Based Stereo Correspondence

In this paper we describe a new stereo correspondence method. This method was proposed for a mobile robot navigation context. The proposed method is based on the work of Oliveira and Wazlavick originally presented in [1]. The original method has a low computational complexity (O(n)), where n is the number of pixels in the image. Despite the low computation time, this method achieves only an average score in the Middlebury evaluation [2], [3] concerning the obtained disparity map. In order to improve this score, we propose a new algorithm based on the original approach combined to a segmentation procedure called Color Structure Code [4]. This new algorithm is able to improve the results without adding significant processing time, and keeping the computational complexity of O(n). The proposed approach is able to calculate 10+ stereo frames per second in a single threaded CPU.