【作者】 王彤；

【导师】 李文辉；

【作者基本信息】 吉林大学 ， 计算机应用技术， 2006， 硕士

【摘要】 图像分割是图像处理中的一项关键技术,自20世纪70年代起一直受到人们的高度重视,是由图像处理到进一步图像分析的关键步骤,也是一种基本的计算机视觉技术。对图像分割的研究在图像处理领域具有重要的意义,随着技术进步,彩色图像使用越来越频繁,彩色图像包含的信息远远多于单色图像所包含的信息。它不仅提供明亮度信息,还包括色调和饱和度,所提供的信息量更丰富,分割后的结果也更具有利用价值,因此,彩色图像分割越来越引起人们的关注。属于数学形态学范畴的分水岭(Watershed)算法,是一种有效的图像分割手段,该方法本质上是利用图像的区域特性来分割图像的,本文正是利用分水岭(Watershed)变换算法,同时结合分割后的区域合并过程及针对分割后形成的各块使用最小切割-最大流算法,最终分割一副彩色图像,实现前景和背景的分离,从而找到了一种实用、有效的分割方法。更多还原

【Abstract】 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.更多还原