Stability principle in stereoscopic matching gives us reliable, versatile, simple, parameter-free, predictable, and fast algorithms.

Radim Sara,
CMP Prague, Czech Republic

Matching is stable if it obeys certain simple local constraints. Stability is a notion naturally capturing the competition among candidate matches for being selected. Roughly speaking, stable matching is one in which each selected match dominates its potential competitors. Great versatility is possible since the choice of the dominance relation is only very weakly constrained. Finding a stable matching is not an optimization problem in the classical sense, no global cost functional is involved. But stable matching does have interesting and useful global properties.

In this talk I will define stability and show the existence and uniqueness theorem. A simple and fast algorithm will be given for finding stable matching under the ordering constraint. The algorithm has no parameters except for matching window size and disparity search interval. I will show on real examples how well stable matching can cope with very wide disparity search interval and half-occluded regions. I will also show stable matching is not biased by large objects in the scene which means it captures fine details and does not miss small objects.

I will then generalize the result to epsilon-delta stable matching which (is supposed to) possess robust properties. Finally, I will go even further and outline the avenues stability principle opens up for sparse matching problems, multicriterial or multisource matching, non-unique matchings, and in matchings based on a combination of local rules rather than on classical correlation measures.