A fast scanning based message receiving method on four directed acyclic subgraphs

作者：Ha Jeongmok^*; Jeong Hong

来源：Journal of Visual Communication and Image Representation, 2016, 38: 161-174.

DOI：10.1016/j.jvcir.2016.02.014

• Markov random fields
• Labeling problem
• Fast inference method
• Graphical model
• Directed acyclic graph

We propose a message-receiving algorithm on a Directed Acyclic Subgraph (DAS) structure to approximate the solution of general labeling problems extremely quickly. The algorithm divides a graph into four subgraphs to get a joint distribution of all nodes, then passes messages in two fixed directions as inference on DASs. Message receiving is a modified version of message passing. When receiving messages on DAS structure, labeling results can be obtained after just four scans. The proposed algorithm was evaluated by using it to perform three labeling decision applications (binary segmentation, image denoising, and stereo matching). Compared to other highly-accurate iterative algorithms (alpha-expansion, alpha-beta swap, tree-reweighted message passing, sum-product belief propagation, max-product belief propagation, and FastPD), the proposed algorithm shows competitive accuracy but requires much less computational time. The proposed algorithm is appropriate for applications in which iterative schemes are undesirable, but which must get reliable labeling results within a limited time.

• 出版日期2016-7