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, 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 30 1994)
Metrics for image segmentation
Proceedings of SPIE (July 06 1998)
Markov random fields for texture classification
Proceedings of SPIE (October 01 1991)
Globally consistent image mosaicing
Proceedings of SPIE (August 20 2010)

Back to Top