Swift distance transformed belief propagation using a novel dynamic label pruning method

Loopy belief propagation (LBP) suffers from high computational time, specifically when each node in the Markov random field (MRF) model has lots of labels. In this study, a swift distance transformed belief propagation (SDT-BP) method is proposed. SDT-BP 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. The direct combination of distance transformed belief propagation (DT-BP) with the dynamic label pruning in Priority-BP has O(KTNlog N) computational complexity. However, the proposed method results in O(KTN) complexity. Where N is the number of nodes, K is the number of labels for each node, and T is the number of iterations. The authors 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 solution at almost the same level. Furthermore, this method can be utilised in any MRF model where its distance function is transformable, i.e. in various image processing and computer vision problems.