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

Jeongmok Ha; Hong Jeong

doi:10.1117/1.JEI.25.4.043016

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

Jeongmok Ha, Hong Jeong

Author Affiliations +

Journal of Electronic Imaging, Vol. 25, Issue 4, 043016 (July 2016). https://doi.org/10.1117/1.JEI.25.4.043016

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.

Citation Download Citation

Jeongmok Ha and 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

Published: 21 July 2016

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available