Stereo correspondence with compact windows via minimum ratio cycle

One of the earliest and still widely used methods for dense stereo correspondence is based on matching windows of pixels. The main difficulty of this method is choosing a window of appropriate size and shape. Small windows may lack sufficient intensity variation for reliable matching, while large windows smooth out disparity discontinuities. We propose an algorithm to choose a window size and shape by optimizing over a large class of "compact" windows. The word compact is used informally to reflect the fact that the ratio of perimeter to area of our windows is small. We believe that this is the first area based method which efficiently constructs nonrectangular windows. Fast optimization over compact windows is achieved via the minimum ratio cycle algorithm for graphs. The algorithm has only a few parameters which are easy to fix.