An O(1) disparity refinement method for stereo matching

• We proposed an O(1) disparity refinement method for each pixel.
• Speed evaluation shows constant result due to O(1) computational complexity.
• Accuracy evaluation shows better performance than 2 typical refinement methods.

Disparity refinement is the final step but also the timing bottleneck of stereo matching due to its high computational complexity. Weighted media filter refinement method and non-local refinement method are two typical refinement methods with O(N) computational complexity for each pixel where N indicates the maximum disparity. This paper presents an O(1) disparity refinement method based on belief aggregation and belief propagation. The aggregated belief, which means the possibility of correct disparity value, is efficiently computed on a minimum spanning tree first, and then the belief aggregation is fast performed on another minimum spanning tree in two sequential passes (first from leaf nodes to root, then from root to leaf nodes). Only 2 additions and 4 multiplications are required for each pixel at all disparity levels, so the computational complexity is O(1). Performance evaluation on Middlebury data sets shows that the proposed method has good performances both in accuracy and speed.