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

Fingerprint

Labels
Optical flows
Message passing
Labeling
Computer vision
Costs
Agglomeration
Pixels

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition

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

SPM-BP : Sped-up patchmatch belief propagation for continuous MRFs. / Li, Yu; Min, Dongbo; Brown, Michael S.; Do, Minh N; Lu, Jiangbo.

2015 International Conference on Computer Vision, ICCV 2015. Institute of Electrical and Electronics Engineers Inc., 2015. p. 4006-4014 7410813 (Proceedings of the IEEE International Conference on Computer Vision; Vol. 2015 International Conference on Computer Vision, ICCV 2015).

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

Li, Y, Min, D, Brown, MS, Do, MN & Lu, J 2015, SPM-BP: Sped-up patchmatch belief propagation for continuous MRFs. in 2015 International Conference on Computer Vision, ICCV 2015., 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., pp. 4006-4014, 15th IEEE International Conference on Computer Vision, ICCV 2015, Santiago, Chile, 12/11/15. https://doi.org/10.1109/ICCV.2015.456
Li Y, Min D, Brown MS, Do MN, Lu J. SPM-BP: Sped-up patchmatch belief propagation for continuous MRFs. In 2015 International Conference on Computer Vision, ICCV 2015. Institute of Electrical and Electronics Engineers Inc. 2015. p. 4006-4014. 7410813. (Proceedings of the IEEE International Conference on Computer Vision). https://doi.org/10.1109/ICCV.2015.456
Li, Yu ; Min, Dongbo ; Brown, Michael S. ; Do, Minh N ; Lu, Jiangbo. / SPM-BP : Sped-up patchmatch belief propagation for continuous MRFs. 2015 International Conference on Computer Vision, ICCV 2015. Institute of Electrical and Electronics Engineers Inc., 2015. pp. 4006-4014 (Proceedings of the IEEE International Conference on Computer Vision).
@inproceedings{a43c4193c37a4d5080d19721de6a5ec9,
title = "SPM-BP: Sped-up patchmatch belief propagation for continuous MRFs",
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.",
author = "Yu Li and Dongbo Min and Brown, {Michael S.} and Do, {Minh N} and Jiangbo Lu",
year = "2015",
month = "2",
day = "17",
doi = "10.1109/ICCV.2015.456",
language = "English (US)",
series = "Proceedings of the IEEE International Conference on Computer Vision",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "4006--4014",
booktitle = "2015 International Conference on Computer Vision, ICCV 2015",
address = "United States",

}

TY - GEN

T1 - SPM-BP

T2 - Sped-up patchmatch belief propagation for continuous MRFs

AU - Li, Yu

AU - Min, Dongbo

AU - Brown, Michael S.

AU - Do, Minh N

AU - Lu, Jiangbo

PY - 2015/2/17

Y1 - 2015/2/17

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84973895355&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84973895355&partnerID=8YFLogxK

U2 - 10.1109/ICCV.2015.456

DO - 10.1109/ICCV.2015.456

M3 - Conference contribution

T3 - Proceedings of the IEEE International Conference on Computer Vision

SP - 4006

EP - 4014

BT - 2015 International Conference on Computer Vision, ICCV 2015

PB - Institute of Electrical and Electronics Engineers Inc.

ER -