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

Hamed Ayoobi, Mehdi Rezaeian

Research output: Contribution to journalArticleAcademicpeer-review

1 Downloads (Pure)


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.

Original languageEnglish
Pages (from-to)1822-1831
Number of pages10
JournalIET Image Processing
Issue number9
Publication statusPublished - 20-Jul-2020


  • 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
  • mage inpainting
  • image processing

Cite this