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

• A fast MAP inference method for the general discrete labeling problems.
• A new graphical model that consists of four directed acyclic subgraphs (DAS).
• Message receiving inference based on four DAS structure.
• Four scanning method that utilizes message receiving inference.
• Extremely high speed and competitive accuracy compared to other MAP inference.

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 (αα-expansion, αα-ββ 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.