Linear stereo matching (ICCV 2011)

Recent local stereo matching algorithms based on an adaptive-weight strategy achieve accuracy similar to global approaches. One of the major problems of these algorithms is that they are computationally expensive and this complexity increases proportionally to the window size. This paper proposes a novel cost aggregation step with complexity independent of the window size (i.e. O(1)) that outperforms state-of-the-art O(1) methods. Moreover, compared to other O(1) approaches, our method does not rely on integral histograms enabling aggregation using colour images instead of grayscale ones. Finally, to improve the results of the proposed algorithm a disparity refinement pipeline is also proposed. The overall algorithm produces results comparable to those of state-of-the-art stereo matching algorithms.

L. De-Maeztu, S. Mattoccia, A. Villanueva, R. Cabeza, "Linear stereo matching"
, 13th International Conference on Computer Vision (ICCV2011), November 6-13, 2011, Barcelona, Spain
[Pdf] [Supplementay_material] [Bibtex


We propose a novel O(1) cost aggregation strategy that thanks to its symmetric nature outperforms stateof-the-art O(1) costs aggregation methods based integral histogram technique [2]. Compared to previous O(1) solutions, our proposal relies on a completely different approach inspired by the guided filter technique [1] that allows to aggregate costs using colour input stereo pairs (previous O(1) solutions aggregate costs using grayscale images because of memory footprint limitations). The symmetric and colour-based O(1) aggregation strategy proposed not only outperforms state-of-the-art O(1) algorithms, but it also produces on the Middlebury dataset [6] results comparable to non-O(1) adaptive-weight stereo matching (e.g. Adaptive Weights [3]). Thanks to the O(1) nature of our cost aggregation strategy, when the size of the input stereo pair grows, our method enables a dramatic improvement in execution time compared to AW stereo matching algorithm. We also propose a disparity refinement pipeline, that allows to obtain results comparable to top-performing stereo matching algorithms. The first stage of the pipeline removes large erroneous disparity assignments using a method similar to those described in [4]. Afterward, we enforce local consistency of the disparity field by means of the LC technique [5].


Linear stereo: results on the Middlebury dataset [1]

Linear stereo vs AW

Linear Stereo vs AW[3]: measured execution time on a PC


[1] K. He, J. Sun and X. Tang, "Guided image filtering", ECCV 2010

[2] F. Porikli, "Constant time O(1) bilateral  filtering", CVPR 2008

[3] K. Yoon and I. Kweon,  "Adaptive support-weight approach for correspondence search",. PAMI, 28(4), 2006

[4] H. Hirschmüller, "Stereo vision in structured environments by consistent semi-global matching", PAMI 30(2), 2008

[5] S. Mattoccia, "A locally global approach to stereo correspondence", 3DIM 2009, [Pdf] [Additional experimental results]

[6] D. Scharstein and R. Szeliski, "A taxonomy and evaluation of dense two-frame stereo correspondence algorithms",International Journal of Computer Vision, 47(1/2/3):7-42, April-June 2002 / Microsoft Research Technical Report MSR-TR-2001-81, November 2001 - Middlebury Stereo Vision Page,URL: 


last update on: Sep 26, 2011