Swift Distance Transformed Belief Propagation using a Novel Dynamic Label Pruning Method

Loopy Belief Propagation (LBP) suffers mainly from high computational time, specifically when each node in the MRF model has lots of labels. In this paper, a Swift Distance Transformed Belief Propagation (SDT-BP) method is proposed. Our method employs an efficient dynamic label pruning approach together with distance transformation to boost the running time of the LBP. The proposed dynamic label pruning approach is independent of any specific message scheduling. The resultant solution's energy is less than Priority-BP. Furthermore, SDT-BP guarantees convergence in fewer numbers of iterations. Direct combination of distance transformed belief propagation (DT-BP) with the dynamic label pruning in Priority-BP has O(KTNlogN) computational complexity. However, our proposed method results in O(KTN) complexity. Where N is the number of nodes in the MRF model, K is the number of labels for each node, and T is the number of iterations. We conduct several experiments on image inpainting case studies, to evaluate this method. According to this analysis, DT-BP faces nearly 90\% speedup by preserving the energy of the ultimate solution at almost the same level. Furthermore, this method can be utilized in any MRF model where its distance function is transformable, i.e. in various image processing and computer vision problems.