Regular Articles

Theoretic derivation of directed acyclic subgraph algorithm and comparisons with message passing algorithm

[+] Author Affiliations
Jeongmok Ha, Hong Jeong

Pohang University of Science and Technology (POSTECH), Department of Electrical Engineering, Cheongam-Ro 77, Pohang, Republic of Korea

J. Electron. Imaging. 25(4), 043016 (Jul 21, 2016). doi:10.1117/1.JEI.25.4.043016
History: Received December 4, 2015; Accepted June 21, 2016
Text Size: A A A

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.

Figures in this Article
© 2016 SPIE and IS&T

Citation

Jeongmok Ha and Hong Jeong
"Theoretic derivation of directed acyclic subgraph algorithm and comparisons with message passing algorithm", J. Electron. Imaging. 25(4), 043016 (Jul 21, 2016). ; http://dx.doi.org/10.1117/1.JEI.25.4.043016


Access This Article
Sign in or Create a personal account to Buy this article ($20 for members, $25 for non-members).

Some tools below are only available to our subscribers or users with an online account.

Related Content

Customize your page view by dragging & repositioning the boxes below.

Related Book Chapters

Topic Collections

PubMed Articles
Advertisement
  • Don't have an account?
  • Subscribe to the SPIE Digital Library
  • Create a FREE account to sign up for Digital Library content alerts and gain access to institutional subscriptions remotely.
Access This Article
Sign in or Create a personal account to Buy this article ($20 for members, $25 for non-members).
Access This Proceeding
Sign in or Create a personal account to Buy this article ($15 for members, $18 for non-members).
Access This Chapter

Access to SPIE eBooks is limited to subscribing institutions and is not available as part of a personal subscription. Print or electronic versions of individual SPIE books may be purchased via SPIE.org.