Research Of Color Image Segmentation Based On Mathematical Morphology

Mathematical Morphology is a new method which is used in the fields ofImage Processing and Pattern Recognition. The history of MathematicalMorphology dates back to Eular,Steiner,Crofton in 19 centuries andMinkowski,Matheron, Serra in the 1990's. The "Image Analysis andMathematical Morphology", written by J. Serra in 1982, was a veryimportant landmark in the phylogeny of the Mathematical Morphology. Itindicated that Mathematical Morphology had already become moreintegrated, and was used more in-depth in the practical application. Alongwith the speedy development of Mathematical Morphology, researchers givemore attentions to the Mathematical Morphology, because it is very fast tocarry out the parallel processing, and easy to be implemented by hardware. The fundamental operations of Mathematical Morphology are based onthe Set-theory and the topology. It has the integrated mathematicsfoundations, and is the powerful tool to analyze and describe theSet-Morphology. We can also deduce and combine some applied algorithmswith the fundamental algorithms. These applied algorithms can be used inImage processing because of the simplicity and integrality in mathematics,and be used in the quantificational description and analysis of the geometricalstructure of the images. We can use them to analyze and process the shapesand the structures of the images, including image segmentation, characterpick-up, boundary detection, image filtering, image enhancement, imagerecovery and so on. Lately, there are many new applied algorithms be putforward with the combination of Mathematical Morphology and imageprocessing. These new algorithms accelerate the computation and build thebasis for real-time recognition and image processing. At the present time,Mathematical Morphology is widely used in many fields, such as computervision, signal processing, image analysis, pattern recognition, computationalmethods, data processing and so on.Image segmentation is an important technology in image processing.There are thousands of algorithms we used to process the image segmenting.Image segmentation is to segment image into many regions which are ofdifferent characters, and pick the objects which we are interested in. It is thekey step from image processing to image analysis, and is a fundamentalcomputer vision technology. We could measure the parameters and pick upthe characters based on the image segmentation. And it is possible to processthe image analysis and image comprehension. So it is important to carry outthe image segmentation in the field of image processing. The process of theimage segmentation is to divide a whole image region into many non-nullsub-regions. Each sub-region is interior connected, and the same region hasthe same or similar characters such as grayness, color, texture and so on. Withthe development of image technology, the main attention had been changedfrom gray image to colorful image. People pay more attention to the colorfulimage in the fields of image segmentation. The colorful image is differentfrom the gray image. There is more information in the colorful image such aslightness, tone and saturation. So when we segment an image, we should notonly choose the appropriate algorithms, but also the right color space, so thatwe can segment the image appropriately.There were many classical algorithms had been put forward to resolvethe segmenting problem. These algorithms were divided into four classes,such as Histogram threshold segmentation algorithms, edge detectionalgorithms, region-based algorithms, clustering algorithms. The generalsegmenting algorithm has the specific advantages, but also has thecorresponding disadvantages. The histogram threshold segmentationalgorithms are depended on the threshold value excessively. The edgedetection algorithms can not form the close edges and the detected edges aretrivial excessively. The region-based algorithms depend on the selection ofthe seeds and the search direction. The clustering algorithms can form theuncertain cluster numbers. These defects restrict the actual application in thecorresponding fields.Lately, with the presentation of new theories and new methods in varieddisciplines, and the development of the Morphology in the image processing,researchers use the Morphology more and more into the image segmentation.The processing results well satisfy the user's expectation.This paper uses the watershed-algorithm which belongs to theMathematical Morphology, to segment a two-dimensional color image.Together with the subsequent region merging algorithm andmin-cut/max-flow algorithm, we can pick up the specific object in the colorimage. The process need only a few user's input such as marking lines tospecify the foreground of interested from the background of uninterested, anddo not need the indication of the outline of the foreground and otheradditional constraint conditions. The precision and the calculating speed ofthis algorithm improved more than other methods.Watershed is one of the classic algorithms in the field of topography. Thewatershed used in this paper base on the immersing simulation, waspresented by Vincent and Soille in 1991. The computation speed ofimmersing simulation based algorithm is the fastest in ordinal watersheds.Image is regard as the topographic surface, and we punch a hole in the valleybottom of a certain region. Water will rise from the lowest valley bottomthrough the hole, and inundate the whole district little by little. When waterarrives at the boundaries among some regions, we build a fictitious jam toavoid the convergence of the water from different regions. At the end of theimmersing process, each region is flood and completely surround by water.These jams we build are the watersheds we seek. And with the watersheds,the whole image is divided into different regions. In the actual process, I hadimproved the original theory to fit the actual application. The gradient valuesof the image should be first computed, and order the gradient from smallvalue to big value. I use a FIFO queue to store the level processed. When allthe pixels were labeled, the algorithm finished. After the general process,there are many small regions composed of similar pixels. These small regionsare too trivial to denote obvious characters. So we should make furtherprocess to eliminate the over-segmentation regions.To solve the over-segmenting problem, we should use the region mergingmethods to dispose the small regions, and merge the small regions to somelarge region. With many attempts, I determined to use a easy and idealalgorithm -the merging algorithm based on the region growing.Region-growing based algorithm is divided into two steps. The first step is tomerge minimum regions. In this step, I combined the regions which had fewpixels to its nearest neighbor region. The second step is to merge the similarregions. I used square of the color of two regions to be the measurementvalue, and set a threshold through many experiments. When the measurementvalue is smaller than the threshold, I considered the two regions were similarregions, and merge the two similar regions. Then the two steps were repeated,the algorithm finished until all the similar regions were merged. Aftermerging process, we can obtain some lager regions which are of obviouscharacter. And we put these larger regions as the input of min-cut/max-flowalgorithm.Min-cut/max-flow algorithm was proved by Ford and Fulkerson in 1956.The essential of the algorithm is the equivalence between minimum cut andmaximum flow in a network. I use the original theory of this algorithm, andextend the methods to many sources and many sinks. The regions merged inlast step are regarded as the nodes in a network, and set the user input as thesources and sinks of a network. The search process iteratively repeats threestages. The first stage is "growth" stage. In this stage, the two search treeswere expanded. When an active node in a tree encounters a neighboring nodethat belongs to the other tree, the growth stage terminated. The second stageis "augmentation" stage. The saturated paths should be deleted from the trees,and the two trees had become the forests. The third stage is "adoption" stage.The orphans should be processed in this stage. The algorithm searches a validparent node for each orphan. If there is no valid parent node for an orphan,the orphan node became the free node. When all the orphans were processed,the algorithm should return the first stage to repeat the three steps. After theadoption stage, the algorithm should returns to the growth stage. Thealgorithm terminates when the two search trees can not grow (no active nodes)and the trees are separated by saturated edges. The algorithm made sure that Ican find a maximum flow path, the corresponding minimum cut will separatethe nodes into two classes, and it is the final result we need.The experimental results show that, if we use watershed together withregion merging algorithm, and apply the min-cut/max-flow algorithm toseparate regions, we will segment the precise result. And the efficiency of thealgorithm is very high.