SPM-BP: Sped-up patchmatch belief propagation for continuous MRFs

Yu Li, Dongbo Min, Michael S. Brown, Minh N. Do, Jiangbo Lu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Markov random fields are widely used to model many computer vision problems that can be cast in an energy minimization framework composed of unary and pairwise potentials. While computationally tractable discrete optimizers such as Graph Cuts and belief propagation (BP) exist for multi-label discrete problems, they still face prohibitively high computational challenges when the labels reside in a huge or very densely sampled space. Integrating key ideas from PatchMatch of effective particle propagation and resampling, PatchMatch belief propagation (PMBP) has been demonstrated to have good performance in addressing continuous labeling problems and runs orders of magnitude faster than Particle BP (PBP). However, the quality of the PMBP solution is tightly coupled with the local window size, over which the raw data cost is aggregated to mitigate ambiguity in the data constraint. This dependency heavily influences the overall complexity, increasing linearly with the window size. This paper proposes a novel algorithm called sped-up PMBP (SPM-BP) to tackle this critical computational bottleneck and speeds up PMBP by 50-100 times. The crux of SPM-BP is on unifying efficient filter-based cost aggregation and message passing with PatchMatch-based particle generation in a highly effective way. Though simple in its formulation, SPM-BP achieves superior performance for sub-pixel accurate stereo and optical-flow on benchmark datasets when compared with more complex and task-specific approaches.

Original languageEnglish (US)
Title of host publication2015 International Conference on Computer Vision, ICCV 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages4006-4014
Number of pages9
ISBN (Electronic)9781467383912
DOIs
StatePublished - Feb 17 2015
Event15th IEEE International Conference on Computer Vision, ICCV 2015 - Santiago, Chile
Duration: Dec 11 2015Dec 18 2015

Publication series

NameProceedings of the IEEE International Conference on Computer Vision
Volume2015 International Conference on Computer Vision, ICCV 2015
ISSN (Print)1550-5499

Other

Other15th IEEE International Conference on Computer Vision, ICCV 2015
CountryChile
CitySantiago
Period12/11/1512/18/15

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition

Fingerprint Dive into the research topics of 'SPM-BP: Sped-up patchmatch belief propagation for continuous MRFs'. Together they form a unique fingerprint.

  • Cite this

    Li, Y., Min, D., Brown, M. S., Do, M. N., & Lu, J. (2015). SPM-BP: Sped-up patchmatch belief propagation for continuous MRFs. In 2015 International Conference on Computer Vision, ICCV 2015 (pp. 4006-4014). [7410813] (Proceedings of the IEEE International Conference on Computer Vision; Vol. 2015 International Conference on Computer Vision, ICCV 2015). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICCV.2015.456