Deformable spatial pyramid matching for fast dense correspondences

We introduce a fast deformable spatial pyramid (DSP) matching algorithm for computing dense pixel correspon-dences. Dense matching methods typically enforce both ap-pearance agreement between matched pixels as well as ge-ometric smoothness between neighboring pixels. Whereas the prevailing approaches operate at the pixel level, we pro-pose a pyramid graph model that simultaneously regular-izes match consistency at multiple spatial extents—ranging from an entire image, to coarse grid cells, to every sin-gle pixel. This novel regularization substantially improves pixel-level matching in the face of challenging image vari-ations, while the “deformable ” aspect of our model over-comes the strict rigidity of traditional spatial pyramids. Re-sults on LabelMe and Caltech show our approach outper-forms state-of-the-art methods (SIFT Flow [15] and Patch-Match [2]), both in terms of accuracy and run time. 1