PatchMatch Filter: Edge-Aware Filtering Meets Randomized Search for Visual Correspondence

Jiangbo Lu, Yu Li, Hongsheng Yang, Dongbo Min, Weiyong Eng, Minh N. Do

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


Though many tasks in computer vision can be formulated elegantly as pixel-labeling problems, a typical challenge discouraging such a discrete formulation is often due to computational efficiency. Recent studies on fast cost volume filtering based on efficient edge-aware filters provide a fast alternative to solve discrete labeling problems, with the complexity independent of the support window size. However, these methods still have to step through the entire cost volume exhaustively, which makes the solution speed scale linearly with the label space size. When the label space is huge or even infinite, which is often the case for (subpixel-accurate) stereo and optical flow estimation, their computational complexity becomes quickly unacceptable. Developed to search approximate nearest neighbors rapidly, the PatchMatch method can significantly reduce the complexity dependency on the search space size. But, its pixel-wise randomized search and fragmented data access within the 3D cost volume seriously hinder the application of efficient cost slice filtering. This paper presents a generic and fast computational framework for general multi-labeling problems called PatchMatch Filter (PMF). We explore effective and efficient strategies to weave together these two fundamental techniques developed in isolation, i.e., PatchMatch-based randomized search and efficient edge-aware image filtering. By decompositing an image into compact superpixels, we also propose superpixel-based novel search strategies that generalize and improve the original PatchMatch method. Further motivated to improve the regularization strength, we propose a simple yet effective cross-scale consistency constraint, which handles labeling estimation for large low-textured regions more reliably than a single-scale PMF algorithm. Focusing on dense correspondence field estimation in this paper, we demonstrate PMF's applications in stereo and optical flow. Our PMF methods achieve top-tier correspondence accuracy but run much faster than other related competing methods, often giving over 10-100 times speedup.

Original languageEnglish
Article number7588057
Pages (from-to)1866-1879
Number of pages14
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Issue number9
StatePublished - 1 Sep 2017

Bibliographical note

Funding Information:
This study is supported by the HCCS grant at ADSC from Singapore’s A*STAR. D. Min was supported by Basic Science Research Program through the National Research Foundation of Korea(NRF)(2015R1D1A1A01061143). Dongbo Min is the corresponding author.

Publisher Copyright:
© 2017 IEEE.


  • Approximate nearest neighbor
  • edge-aware filtering
  • optical flow
  • stereo matching


Dive into the research topics of 'PatchMatch Filter: Edge-Aware Filtering Meets Randomized Search for Visual Correspondence'. Together they form a unique fingerprint.

Cite this