Unified Framework for Semiring-Based Arc Consistency and Relaxation Labeling

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F07%3A03134580" target="_blank" >RIV/68407700:21230/07:03134580 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Unified Framework for Semiring-Based Arc Consistency and Relaxation Labeling

Original language description

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 generalizationby 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.

Czech name

Unified Framework for Semiring-Based Arc Consistency and Relaxation Labeling

Czech description

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 generalizationby 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.

Type

D - Article in proceedings

CEP classification

JD - Use of computers, robotics and its application

OECD FORD branch

—

Project

—

Continuities

R - Projekt Ramcoveho programu EK

Publication year

2007

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

CVWW 2007: Proceedings of the 12th Computer Vision Winter Workshop

ISBN

978-3-902465-60-3

ISSN

—

e-ISSN

—

Number of pages

8

Pages from-to

—

Publisher name

Verlag der Technischen Universität Graz

Place of publication

Graz

Event location

St. Lambrecht

Event date

Feb 6, 2007

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—