Swift distance transformed belief propagation using a novel dynamic label pruning method. Issue 9 (8th June 2020)

• Record Type: Journal Article
• Authors: Ayoobi, Hamed; Rezaeian, Mehdi
• Is Part Of: IET image processing. Volume 14:Issue 9(2020)
• Page Start: 1822
• Page End: 1831
• Publication Date: 2020-06-08
• Subjects: computer vision -- computational complexity -- image restoration -- random processes -- Markov processes -- belief propagation; SDT‐BP -- distance transformation -- LBP -- message scheduling -- DT‐BP -- MRF model -- distance function -- dynamic label pruning method -- loopy belief propagation -- Markov random field model -- priority‐BP -- swift distance transformed belief propagation -- computational complexity -- mage inpainting -- image processing -- computer vision; Image processing -- Periodicals; 621.36705
• DOI: 10.1049/iet-ipr.2019.1035
• Languages: English
• ISSNs: 1751-9659

Abstract

Abstract : 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 ( KTN log 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.