A. Deruyver et Y. Hode, CONSTRAINT SATISFACTION PROBLEM WITH BILEVEL CONSTRAINT - APPLICATIONTO INTERPRETATION OF OVER-SEGMENTED IMAGES, Artificial intelligence, 93(1-2), 1997, pp. 321-335
Citations number
20
Categorie Soggetti
Computer Sciences, Special Topics","Computer Science Artificial Intelligence",Ergonomics
In classical finite-domain constraint satisfaction problems, the assum
ption made is that only one value is associated with only one variable
. For example, in pattern recognition one variable is associated with
only one segmented region. However, in practice, regions are often ove
r-segmented which results in failure of any one to one mapping. This p
aper proposes a definition of finite-domain constraint satisfaction pr
oblems with bilevel constraints in order to take into account a many t
o one relation between the values and the variables. The additional le
vel of constraint concerns the data assigned to the same complex varia
ble. Then, we give a definition of the are-consistency problem for bil
evel constraint satisfaction checking. A new algorithm for are consist
ency to deal with these problems is presented as well. This extension
of the are-consistency algorithm retains its good properties and has a
time complexity in O(en(3)d(2)) in the worst case. This algorithm was
tested on medical images. These tests demonstrate its reliability in
correctly identifying the segmented regions even when the image is ove
r-segmented. (C) 1997 Elsevier Science B.V.