21 July 2016 Theoretic derivation of directed acyclic subgraph algorithm and comparisons with message passing algorithm
Author Affiliations +
Abstract
This study investigates the directed acyclic subgraph (DAS) algorithm, which is used to solve discrete labeling problems much more rapidly than other Markov-random-field-based inference methods but at a competitive accuracy. However, the mechanism by which the DAS algorithm simultaneously achieves competitive accuracy and fast execution speed, has not been elucidated by a theoretical derivation. We analyze the DAS algorithm by comparing it with a message passing algorithm. Graphical models, inference methods, and energy-minimization frameworks are compared between DAS and message passing algorithms. Moreover, the performances of DAS and other message passing methods [sum-product belief propagation (BP), max-product BP, and tree-reweighted message passing] are experimentally compared.
© 2016 SPIE and IS&T
Jeongmok Ha, Jeongmok Ha, Hong Jeong, Hong Jeong, } "Theoretic derivation of directed acyclic subgraph algorithm and comparisons with message passing algorithm," Journal of Electronic Imaging 25(4), 043016 (21 July 2016). https://doi.org/10.1117/1.JEI.25.4.043016 . Submission:
JOURNAL ARTICLE
15 PAGES


SHARE
RELATED CONTENT

Hierarchical Markov random fields with stable points
Proceedings of SPIE (June 29 1994)
Metrics for image segmentation
Proceedings of SPIE (July 05 1998)
Markov random fields for texture classification
Proceedings of SPIE (September 30 1991)
Color texture synthesis based on structure
Proceedings of SPIE (September 24 2003)

Back to Top