Unified Framework for Semiring-Based Arc Consistency and Relaxation Labeling

Abstract

Bibtex entry

@InProceedings{Werner-CVWW07,
  author =       {Tom{\'a}{\vs} Werner and Alexander Shekhovtsov},
  title =        {Unified Framework for Semiring-Based Arc Consistency and Relaxation Labeling},
  booktitle = {12th Computer Vision Winter Workshop, St. Lambrecht, Austria},
  pages =     {27--34},
  year =      {2007},
  editor =    {Michael Grabner and Helmut Grabner},
  month =     {February},
  publisher = {Graz University of Technology},
  annote =    {Constraint Satisfaction Problem (CSP), including its soft
  modifications, is ubiquitous in artificial intelligence and related
  fields. In computer vision and pattern recognition, the crisp CSP
  is more known as the consistent labeling problem and certain soft
  CSPs as certain inference problems in Markov Random Fields. Many
  soft CSPs can be seen as special cases of the semiring-based CSP
  (SCSP), using two abstract operations that form a semiring.
  A fundamental concept to tackle the CSP, as well as the SCSPs with
  idempotent semiring multiplication, are arc consistency algorithms,
  also known as relaxation labeling. Attempts have been made to
  generalize arc consistency for soft CSPs with non-idempotent
  semiring multiplication. We achieve such generalization by
  generalizing max-sum diffusion of Kovalevsky and Koval, used to
  decrease Schlesinger's upper bound on the max-sum CSP. We formulate
  the proposed generalized arc consistency in the semiring framework.
  Newly, we introduce sum-product arc consistency and give its
  relation to max-sum arc consistency and optimal max-sum arc
  consistency.},
}