【中文摘要】 在图像识别技术的实现过程中,图像分割是一个重要的预处理环节,图像分割效果,直接影响着后续的分类、目标识别、图像分析、图像理解等过程的结果。针对着不同的图像特点,目前已经提出了错综复杂的图像分割算法。其中基于图论的图像分割算法是近几年研究的热点,这类算法着眼于全局,更注重局部数据的处理,比一般方法可以获得更佳的效果,并且图论理论有着比较完备的数学理论基础,将其用于图像处理有着较好的应用前景。本文详细介绍了图论算法的基本理论,将一幅图像映射成一个加权的无向图,将像素点映射为节点,相邻的像素之间的视觉性质(比如灰度信息或纹理)的相似度来定义相应的边的权值,图像的分割结果可以通过对图的最小割方法来获得。通过分析近些年基于图论的图像分割的现状可知,目前研究的重点主要是对最优割集准则的设计和优化改进,本文详细研究了Normalized Cut算法,这种算法很好的解决了直接使用最小割方法的缺陷,将这个NP-hard的准则转化为特征方程的求解,在数学上给出了完美的解答,但是这种方法存在着求解大规模矩阵的特征向量的复杂问题,而且随着图像尺寸的增大,计算规模也在增大,分割速度变得很慢,从而使该算法在实际应...更多用中效率大大降低。为此,本文对原有算法进行了如下改进和创新以提高算法的效率:(1)通过小波变换进行高低分辨率图像的映射,大大缩短了Normalized Cut算法消耗时长,并且可以很好的保留原始算法的优点;(2)通过阈值法的初始粗分割,然后应用Normalized Cut算法。本文引入的信息熵算法的改进算法更加准确的确定分割阈值,更有效的分析图像特征,对信息熵的改进也是本文的创新之一,并且改进了区域之间权值矩阵的确定;(3)通过分水岭粗分割,然后映射到区间上利用归一化割进行分割,并且引入灰关联度的理论衡量像素间相似度来指导图像的分割过程;(4)引入区域生长法对图像实现粗分割,重新定义了种子点的选取法则,改进了区域生长的准则,并且考虑到了零星区域的合并,给出了零星区域合并的规则,最大限度的保留了原始图像的特征,然后利用重新定义的区域间的权值函数来构造权值矩阵,最后实现归一化分割。(5)针对最小割集准则存在着易于分割出图像孤立点的问题,参考NormalizedCut算法模型,引入加权割的概念,通过求最小加权割来实现同时达到类间最大相异性和类内最大一致性的图像分割目的。(6)在详细介绍了对最小生成树算法的基本思想、实现算法、分割准则的基础上,分析了该方法的优缺点,优化分割准则,确定目标函数来指导分割过程,定义节点和区域间的权值函数,充分考虑像素点之间的空间关系。
【英文摘要】 Image segmentation is an impotant preprocess part in image recognition process, the segment effects directly affect subsequent image classification, image recognition and image analysis. According to the different characteristics of the image, numerous image segmentation algorithm was proposed in recent years.This kind of algorithm focus on the whole situation and pay much more attention to the process for local data , its effect is better than the generals, and graph theory has a complete foundations of mathematics, its application in image processing has good prospects for development.This paper introduce the basic theory of the algorithm based on graph theory in details, mapping the image into a weighted undigraph and pixel into node,the adjacent pixel's visual nature (such as grey informationl or texture) and it's similarity can be defined as weights,and the effects of the image segmentation can get by using minimum segmentation method to the graph. Analyzing the method of image se...gmentation based on graph theory in recent years, now the focus of research is design and give some improvement for the algorithm of optimal cut criterion. The Normalized Cut algorithm provide a good way to slove the problem in the minimum cut method ,its turn the NP-hard problem into the questiom to finding the solutions of the characteristic equations,the prefect answer can be achieved by math method , but this method exist a complex problem in solving large-scale matrices's eigenvector,moreover,with the the image size increasing, the computation size is increasing,the segmentation speed will get slow, the algorithm's application efficiency would be lowered.For this reason, the following improvement for original algorithm in order to improve the efficiency are proposed.(1) Through wavelet transform to mapping the resolution image, can simplify the computation of the Normalized Cut,and can preferable maintain the advantages of the original algorithm.(2) Firstly use the method of thresholding give an initial rough segmentation,then apply the Normalized Cut algorithm, introduce the improved algorithm of the information entropy to select the threshold, analyse image features more effectively,this point is an improvement of this paper,and give some improvement for the weight matrix between the area.(3) Segment the image with watershed method firstly,use NC method to segment the image between the area,and introduce the Grey Relational degree to compute the similarity between pixels to guide the image segmentation process.(4) First the image was segmented with region growing algorithm, redefined the criterion for seed selection,improved the criterion of region growing.and consider the merge of scattered area, maximum retain the original image character,redefined the weight matrix between the area.(5) For the purpose of avoid isolated point ,give an image segmentation algorithm based on weighted cut, optimizing weighted cut can ensure that the inter-cluster similarity is minimized while intra-cluster similarity is maximized.(6)Based on the introduction of MST algorithm basic theory, segmentation criterion, analyse the advantage and disadvantage of this method, optimize the segmentation criterion,define the objective function to guide the process,define the weighted function between the node and area,fully consider the space relation of pixels.
【中文关键词】 图像分割; 图论; 最小生成树; 归一化割
【英文关键词】 Image segmentation ; Graph theroy ; MST; Normalized Cut
