Method Of Color Image Segmentation Based On Graph Theory

Color image segmentation is the basis of almost all the mid-level andhigh-level works of color image processing. Whether in the mid-level works ofimage analysis, or in the high-level works of image understanding, the procedure ofimage segmentation is always carried out as the first step, followed by other stepssuch as feature extraction, pattern recognition, etc. Moreover, the quality of imagesegmentation will give a direct influence on the result of its subsequential steps. Thus,studies of high quality color image segmentation methods have always gained a lotof attention in the field of image processing. However, so far the problem of colorimage segmentation has not been well solved yet.Color image segmentation methods based on Graph Theory are amongthose solutions that have achieved best performance. In general, this kind ofmethods transforms the problem of image segmentation into the problem ofgraph optimization, and realizes image segmentation by optimizing the graph usingGraph Theory. There are mainly two types of this kind of methods-MinimalSpanning Tree, and Minimized Cut.Both of the two types-Minimal Spanning Tree and Minimized Cut arediscussed in detail in this thesis. For the first type-Minimal Spanning Tree (MST),a new method of segmenting color images using local thresholds is proposed.Unlike the traditional methods that employ a global threshold, the proposedmethod calculates alocal threshold during the process of constructing MST,according to the change of homogeneities of merging regions. Then by usingthis local threshold, two final regions can be segmented from the original image.The above process is repeated to segment the remaining regions in the originalimage, and stops when no region remains. Experiments show that the proposedmethod is superior to the traditional ones.For the second type- Minimized Cut (Min. Cut), its modified form,Normalized Cut, can be used to overcome the drawback of Min. Cut that favors to segment isolated pixels. But the problem of minimizing Normalized Cut isNon-deterministic Polynomial Complete (NP Complete), and only theapproximation to its solutions can be gotten. Recently someone proposed a fuzzyiteration method of Normalized Cut to segment gray-level images, whichstrategically avoided the NP Complete problem of minimizing Normalized Cut. Inthis thesis, a method of utilizing the fuzzy iteration method of Normalized Cut tosegment color images is devised, including choosing proper measurement of colorsimilarity, and using linear chain instead of matrix to calculate Normalized Cut.Experiments show that the devised method works well on segmenting color images.