Efficient Sampling of Disparity Space for Fast And Accurate Matching

                           Jan Cech

A simple algorithm is proposed that visits only a small fraction of
disparity space in order to find a semi-dense disparity map. Starting
from a small set of correspondence seeds, it still guarantees matching
accuracy and correctness, even in the presence of repetitive
patterns. Unlike in existing approaches, the success of the proposed
algorithm is based on the fact it solves a global optimization
task. The algorithm can recover from wrong initial seeds to the extent
they can even be random. The quality of correspondence seeds
influences computing time, not the quality of the final disparity
map. We experimentally demonstrate that the proposed algorithm
achieves similar results as an exhaustive disparity space serch but it
is two orders of magnitude faster. This is very unlike the existing
growing algorithms which are fast but erroneous. Accurate unambiguous
dense matching on 2-megapixel images of complex scenes is routinely
obtained in a few seconds on a common PC from a small number of seeds,
without limiting the disparity search range.