Sparse Recursive Cost Aggregation Towards O(1) Complexity Local Stereo Matching

The complexity of the local stereo matching methods mainly increases with disparity search range and cost aggregation step. Joint elimination of the those complexity factors is a challenging task as a consequence of the contradicting nature of the methods attacking the reduction on the complexity factors. In this paper, that challenge is addressed and for the disparity search range reducing approaches, an efficient cost aggregation method is proposed by reformulating the filtering scheme of the recursive edge-aware filters which have been proved to be efficient approaches for cost aggregation. The proposed method is exploited by a hierarchical stereo matching approach. In that manner, fixed number of disparity candidates are tested for each pixel, regardless of the search space and the cost aggregation for each candidate is performed with constant complexity. The experimental results validate that the proposed approach has linear complexity with the image size and show that in practice it speeds up the recursive approaches almost four times with 0.01-0.96% decrease in matching accuracy. Compared to the state-of-the-art techniques, the proposed method is possibly the fastest approach with a competitive accuracy based on Middlebury benchmarking.