Hardware-Efficient Belief Propagation

Abstract

Loopy belief propagation (BP) is an effective solution for assigning labels to the nodes of a graphical model such as the Markov random field (MRF), but it requires high memory, bandwidth, and computational costs. Furthermore, the iterative, pixel-wise, and sequential operations of BP make it difficult to parallelize the computation. In this paper, we propose two techniques to address these issues. The first technique is a new message passing scheme named tile-based belief propagation that reduces the memory and bandwidth to a fraction of the ordinary BP algorithms without performance degradation by splitting the MRF into many tiles and only storing the messages across the neighboring tiles. The tile-wise processing also enables data reuse and pipeline, resulting in efficient hardware implementation. The second technique is an O(L) parallel message construction algorithm that exploits the properties of robust functions for parallelization. We apply these two techniques to a VLSI circuit for stereo matching that generates high-resolution disparity maps in near real-time. We also implement the proposed schemes on GPU which is four-time faster than standard BP on GPU.

People

Chia-Kai Liang, MPAC lab

Chao-Chung Cheng, DSPIC Design lab

Yen-Chieh Lai, DSPIC Design lab

Prof. Liang-Gee Chen, DSPIC Design lab

Prof. Homer H. Chen, MPAC lab

Publications

1. C.-K. Liang, C.-C. Cheng, Y.-C. Lai, H. H. Chen, and L.-G. Chen, Hardware-efficient belief propagation, IEEE Trans. CSVT, vol. 21, no. 5, pp. 525 - 537, May. 2011. [PDF][Long version PDF]
2. Y.-C. Lai, C.-C. Cheng, C.-K. Liang, and L.-G. Chen, Efficient message reduction algorithm for stereo matching using belief propagation, in Proc. ICIP, 2010. [PDF]
3. C.-C. Cheng, C.-T. Li, C.-K. Liang, Y.-C. Lai, and L.-G. Chen, Architecture design of stereo matching using belief propagation, in Proc. ISCAS, pp. 4109-4112, 2010. [PDF]
4. C.-K. Liang, C.-C. Cheng, Y.-C. Lai, H. H. Chen, and L.-G. Chen, Hardware-efficient belief propagation, in Proc. CVPR, pp. 80-87, 2009. [PDF][Supplemental PDF]
5. C.-C. Cheng, C.-K. Liang, Y.-C. Lai, H. H. Chen, and L.-G. Chen, Fast belief propagation process element for high-quality stereo estimation, in Proc. ICASSP, pp. 745-748, 2009. [PDF]
6. C.-C. Cheng, C.-K. Liang, Y.-C. Lai, H. H. Chen, and L.-G. Chen, Analysis of belief propagation for hardware realization, in Proc. SIPS, pp. 152-157, 2008.

Downloads

Reference implementation (compatible to the Middlebury MRF library) [ZIP]

Acknowledgements

This project is supported in part by NSC in grant 96-2628-E-002-005-MY2 and Himax Technologies Inc. in grant 96SB20.