Open AccessSwift distance transformed belief propagation using a novel dynamic label pruning method
Author(s) -
Ayoobi Hamed,
Rezaeian Mehdi
Publication year - 2020
Publication title -
iet image processing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.401
H-Index - 45
eISSN - 1751-9667
pISSN - 1751-9659
DOI - 10.1049/iet-ipr.2019.1035
Subject(s) - belief propagation , speedup , markov random field , pruning , node (physics) , computer science , convergence (economics) , dynamic programming , algorithm , markov chain , inpainting , computational complexity theory , markov decision process , artificial intelligence , markov process , image (mathematics) , mathematics , machine learning , decoding methods , image segmentation , parallel computing , statistics , structural engineering , economic growth , agronomy , economics , biology , engineering
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.