NDLI: Hardware-efficient belief propagation

Content Provider	IEEE Xplore Digital Library
Author	Chia-Kai Liang Chao-Chung Cheng Yen-Chieh Lai Liang-Gee Chen Chen, H.H.
Copyright Year	2009
Description	Author affiliation: Nat. Taiwan Univ., Taipei, Taiwan (Chia-Kai Liang; Chao-Chung Cheng; Yen-Chieh Lai; Liang-Gee Chen; Chen, H.H.)
Abstract	Belief propagation (BP) is an effective algorithm for solving energy minimization problems in computer vision. However, it requires enormous memory, bandwidth, and computation because messages are iteratively passed between nodes in the Markov random field (MRF). In this paper, we propose two methods to address this problem. The first method is a message passing scheme called tile-based belief propagation. The key idea of this method is that a message can be well approximated from other faraway ones. We split the MRF into many tiles and perform BP within each one. To preserve the global optimality, we store the outgoing boundary messages of a tile and use them when performing BP in the neighboring tiles. The tile-based BP only requires 1-5% memory and 0.2-1% bandwidth of the ordinary BP. The second method is an O(L) message construction algorithm for the robust functions commonly used for describing the smoothness terms in the energy function. We find that many variables in constructing a message are repetitive; thus these variables can be calculated once and reused many times. The proposed algorithms are suitable for parallel implementations. We design a low-power VLSI circuit for disparity estimation that can construct 440 M messages per second and generate high quality disparity maps in near real-time. We also implement the proposed algorithms on a GPU, which can calculate messages 4 times faster than the sequential O(L) method.
Starting Page	80
Ending Page	87
File Size	1053206
Page Count	8
File Format	PDF
ISBN	9781424439928
ISSN	10636919
DOI	10.1109/CVPR.2009.5206819
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-06-20
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Belief propagation Tiles Bandwidth Iterative algorithms Minimization methods Computer vision Markov random fields Message passing Robustness Very large scale integration
Content Type	Text
Resource Type	Article
Subject	Computer Vision and Pattern Recognition Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Alphabet SOUP: A framework for approximate energy minimization

Stereo matching using hierarchical belief propagation along ambiguity gradient

Convergent Tree-Reweighted Message Passing for Energy Minimization

Wavelet belief propagation for large scale inference problems

Markov Chain Monte Carlo combined with deterministic methods for Markov random field optimization

Efficient belief propagation for early vision

Dynamic Hybrid Algorithms for MAP Inference in Discrete MRFs

Dense photometric stereo using tensorial belief propagation

Distributed message passing for large scale graphical models

Hardware-efficient belief propagation

Similar Documents

Alphabet SOUP: A framework for approximate energy minimization

Stereo matching using hierarchical belief propagation along ambiguity gradient

Convergent Tree-Reweighted Message Passing for Energy Minimization

Wavelet belief propagation for large scale inference problems

Markov Chain Monte Carlo combined with deterministic methods for Markov random field optimization

Efficient belief propagation for early vision

Dynamic Hybrid Algorithms for MAP Inference in Discrete MRFs

Dense photometric stereo using tensorial belief propagation

Distributed message passing for large scale graphical models

Hardware-efficient belief propagation