Accelerated Belief Propagation for hardware implementation

Disparity map plays an important role in 3DTV and FTV systems. Despite recent advances, state-of-the-art algorithms fail to generate a precise disparity map rapidly enough for VLSI real time processing. Belief Propagation (BP) is a popular global optimization algorithm and has several advantages for hardware implementation. However, it requires high bandwidth, memory and computational costs. Tile-based BP is an efficient improved BP for hardware implementation. Boundary messages loaded from different directions have been performed with different iterations. As a result, energy cost of different pixels within a tile will converge with different speed, yielding the biasing problem. In this paper, firstly, a Balance-convergence method to remove biasing problem in tile-based BP is presented. Additionally, a novel reduced message-update method to remove redundant computational costs during message-update based on tile-based BP is introduced. Compared with the original BP and the leading hardware-oriented fast method, the proposed method can reduce additions by 30 times and 2 times respectively.