CONSTRAINT SATISFACTION PROBLEM WITH BILEVEL CONSTRAINT - APPLICATIONTO INTERPRETATION OF OVER-SEGMENTED IMAGES

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.