GRAPH-THEORETICAL APPROACH TO COLOR PICTURE SEGMENTATION AND CONTOUR CLASSIFICATION

The segmentation of colour pictures in a graph-theoretical context is considered. The procedure aims at identifying, extracting and classify ing visually important features on the image plane, such as regions of homogeneous colour and chromatic transitions. Well established princi ples of colour theory and graph theory are combined to obtain a unifie d representation of a colour picture. The picture is represented by me ans of a weighted graph, constructed so as to reflect the specificatio n of the colour space employed as well as important relationships betw een picture elements. A spanning tree of the graph is obtained by iter atively minimising a specific picture distortion measure. This tree st ructure describes a hierarchy of partitions on the image plane. Each p artition comprises disjoint regions containing elements with similar a ttribute. Due to the fact that region identification and edge detectio n form dual problems from the graph-theoretical viewpoint, region cont ours defined by such partitions form a hierarchy. To avoid artificial contouring, a specific type of artefact introduced by the segmentation algorithm, the use of higher level information, is considered. It is shown that, when texture (which is taken into account at an intermedia te stage of picture segmentation) is combined with colour as joint sim ilarity attributes of regions, an improved hierarchical description of contours is possible. This facilitates the progressive elimination of the undesirable contours and leads to the visual enhancement of the s egmentation obtained.