Hardware-Efficient Belief Propagation

Chia-Kai Liang, Chao-Chung Cheng, Yen-Chieh Lai, Liang-Gee Chen, Homer H. Chen
Institute of Communication Engineering, National Taiwan University, Taipei, Taiwan (R.O.C) 10617
IEEE Transactions on Circuits and Systems for Video Technology, 2009


   title={Hardware-efficient belief propagation},

   author={Liang, C.K. and Cheng, C.C. and Lai, Y.C. and Chen, L.G. and Chen, H.H.},




Download Download (PDF)   View View   Source Source   



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 tech-niques to address these issues. The first technique is a new mes-sage 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) fast 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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2020 hgpu.org

All rights belong to the respective authors

Contact us: