数字图像并行边界分割技术的研究

. . . . 数字图像并行边界分割技术的研究 专业：自动化 班级：2007级2班 ：武耀冲目 录 引言31图像与图像分割51.1图像和数字图像51.2图像技术的发展61.3图像分割在图像工程中的地位71.4 图像分割的研究意义91.5 图像分割的研究现状与发展趋势102 图像分割的基本理论122.1图像分割的定义122.2图像分割的体系结构122.3图像分割方法分类132.3.1 阈值分割方法142.3.2 边缘检测方法142.3.3 区域提取方法162.3.4 结合特定理论工具的分割方法182.4图像分割的质量评价183 图像的并行边界分割技术203.1基本概念203.2经典算法203.2.1微分算子边缘检测203.2.2边界闭合243.2.3边缘拟合253.2.4哈夫变换284 结合微分算子与边界闭合的图像分割304.1 边缘检测304.1.1 拉普拉斯高斯算子检测图像边缘314.1.2 Sobel算子检测图像边缘324.2图像的二值化处理344.3图像的边界闭合354.4实验结果与分析36结 论39致 40参考文献41附录 源程序代码4347 / 50摘 要图像分割是图像分析的第一步，是计算机视觉的基础，是图像理解的重要组成部分，也是图像处理、模式识别等多个领域中一个十分重要且又十分困难的问题。在图像处理过程中，原有的图像分割方法都不可避免的会产生误差，这些误差会影响到图像处理和识别的效果。并行边界分割技术作为一种求解问题的高效并行的全局搜索方法。以其固有的并行性和自适应性，使之非常适于大规模搜索空间的寻找，已广泛应用于许多学科与工程领域。这种技术在计算机视觉领域中的应用也正日益受到重视，为图像分割问题提供了有效的方法。 本文对并行边界分割技术的基本概念和研究进展进行了综述；重点阐述了微分算子边缘检测与边界闭合相结合的图像分割方法，重点研究了两种算子Sobel算子和LoG算子。并基于Matlab软件进行了仿真实现。实验结果表明基于并行边界分割技术的边界闭合方法分割速度快，轮廓区域分割明显，分割质量较高，达到了预期目的。关键词：图像处理；图像分割；边缘检测；二值化；微分算子；边界闭合AbstractImage segmentation is the first step of image analysis and the basic of computer vision. It is an important part of the image understanding, which is a very important and difficult problem in the field of image processing, pattern recognition.In image processing process, the original method of image segmentation can produce inevitable errors and these errors can affect the effect of image processing and identification .Parallel boundary segmentation technology is a sort of efficient，paralled，global search method with its inherent virtues of parallel and self-adaptive characters. It is suitable for searching the optimization result in the large search space. Now it has been applied widely and perfectly in many study fields and engineering areas.These methods are paid more and more attention in computer vision field，which offer effective method for image segmentation.This paper discusses the current situation of the parallel technology in the image segmentation. The image segmentation method based on differential edge detect and boundary closing is deseribed importantly .Sobel and LoG are studied importantly .the simulation is realized based on Matlab.The experimental results show that this method works well in segmentation speed,the outline of the division and separate areas of high quality and achieve the desired effect.Keywords:Image processing;image segmentation;edge detection;Binarization; differential operator; boundary closing引言数字图像处理技术是一个跨学科的领域。随着计算机科学技术的不断发展，图像处理和分析逐渐形成了自己的科学体系，新的处理方法层出不穷，尽管其发展历史不长，但却引起各方面人士的广泛关注。首先，视觉是人类最重要的感知手段，图像又是视觉的基础，因此，数字图像成为心理学、生理学、计算机科学等诸多领域的学者们研究视觉感知的有效工具。其次，图像处理在军事、遥感、气象等大型应用中有不断增长的需求。图像分割是图像分析的第一步，是计算机视觉的基础，是图像理解的重要组成部分，也是图像处理、模式识别和人工智能等多个领域中一个十分重要且又十分困难的问题。所谓图像分割就是要将图像表示为物理上有意义的连通区域的集合，也就是根据目标与背景的先验知识，对图像中的目标、背景进行标记、定位，然后将目标从背景或其他伪目标中分离出来。由于这些被分割的区域在某些特性上相近，因而图像分割常用于模式识别与图像理解以与图像压缩与编码两大类不同的应用目的。由分割产生的区域是图像容的一种表示，它是对图像进行视觉分析和模式识别的基本前提，分割结果的质量直接影响到以后的图像分析、识别和解释的质量，具有重要的意义。图像分割的目的在于根据某些特征(如灰度级、频谱、纹理等)将一幅图像分成若干有意义的区域，使得这些特征在某一区域表现一致或相似，而在不同区域间表现出明显的不同。图像分割的应用非常广泛，几乎出现在有关图像处理的所有领域，如:工业自动化、在线产品检验、生产过程控制、文档图像处理、图像编码、遥感和生物医学图像分析、保安监视，以与军事、体育、农业工程等方面。在各种图像应用中，只要需对图像目标进行提取、测量等都离不开图像分割。虽然人们对图像分割已进行了大量的研究，但还没有一种适合于所有图像的通用的分割算法。所以，图像分割一直以来都是图像技术中的研究热点。因此，从原理、应用和应用效果等方面来深入研究图像分割技术，对于提高图像分析和图像理解系统的性能以与提高图像处理技术的应用水平都具有十分重要的意义。 图像分割是图像处理中的一项关键技术，自20世纪70年代起一直受到人们的高度重视，至今已提出上千种分割算法，但因尚无通用的分割理论，现提出的分割算法大都是针对具体问题的，并没有一种适合所有图像的通用分割算法。另外，还没有制定出选择适用分割算法的标准，这给图像分割技术的应用带来许多实际问题。最近几年又出现了许多新思路、新方法或改进算法，对一些经典方法和新出现的方法作了概述并将图像分割方法分为阈值分割方法、边缘检测方法、区域提取方法和结合特定理论工具的分割方法4类。 其中边缘检测方法是本文要详细介绍的，所谓图像的边缘是指图像局部区域亮度变化显著的部分，该区域的灰度剖面一般可以看作是一个阶跃，既从一个灰度值在很小的缓冲区域急剧变化到另一个灰度相差较大的灰度值。图像的边缘部分集中了图像的大部分信息，图像边缘的确定与提取对于整个图像场景的识别与理解是非常重要的，同时也是图像分割所依赖的重要特征，边缘检测主要是图像的灰度变化的度量、检测和定位，自从1959提出边缘检测以来，经过五十多年的发展，已有许多中不同的边缘检测方法。在我们常用的几种用于边缘检测的算子中LoG算子常常会产生双边界；而其他一些算子如Sobel算子又往往会形成不闭合区域。本文主要讨论了LoG算子和Sobel算子在边缘检测中，获取封闭边界区域进而进行图像分割的算法。1图像与图像分割1.1图像和数字图像图像就是用各种观察系统以不同的形式和手段观察客观世界而获得的，可以直接的或间接的作用于人眼而产生视知觉的实体1。科学研究和试验表明，人类从外界获得的信息75%来自于视觉系统，也就是说，人类的大部分信息都是从图像中获得的。图像是人们从出生以来体验到的最重要、最丰富、信息量获得最大的部分。图像能以各种各样的形式出现，例如，可视和不可视的，抽象的和实际的，适于计算机处理的和不适于计算机处理的。就其本质来说，可以将图像分为两大类：一类是模拟图像，包括光学图像、照相图像和电视图像等，例如，在生物医学研究中，人们在显微镜下看到的图像就是一幅光学模拟图像，照片、用线条画的图、绘画也都是模拟图像。模拟图像处理速度快，但精度和灵活性差，不易查找和判断。另一类是将连续的模拟图像经过离散化处理后变成计算机能够识别的点阵图像，成为数字图像2。严格的数字图像是一个经过等距离矩形网格采样，对幅度进行等间隔量化的二维函数，因此，数字图像就是实际上就是被量化的二维采样数组。与模拟图像相比，数字图像具有以下显著特点：(1)精度高：目前的计算机技术可以将一幅模拟图像数字化为任意的二维数组，即数字图像可以由无限个像素组成，每个像素的亮度可以量化为12位（即4096个灰度级），这样的精度使数字图像与彩色图像的效果相差无几；(2)处理方便：由于数字图像本质上是一组数据，所以可以用计算机对它进行任意方式的修改，例如，放大、缩小、改变颜色、复制和删除某一部分等；(3)重复性好：模拟图像（例如，照片）即便使用非常好的底片和相纸，也会随着时间的流逝而褪色、发黄，而数字图像可以储存在光盘中，上百年后再用计算机重现也不会有丝毫的改变。1.2图像技术的发展图像处理是人类视觉延续的重要手段，可以使人们看到任意波长上所测得的图像。例如，借助的伽马相机、X光机，人们可以看到红外和超声图像；借助CT，人们可以看到物体部的断层图像；借助相应工具，人们可以看到立体图像和剖视图像。几十年前，美国在太空探索中拍回了大量的月球图片，但是由于种种环境因素的影响，这些图片是非常不清晰的，为此，人们对这些照片进行了一些图像处理手段，使照片中的重要信息得以清晰再现。正是这一方法产生的效果引起了巨大的轰动，从而促进了图像处理技术的蓬勃发展3。总体来说，图像处理技术的发展大致经历了初创期、发展期、普与期和实用化期四个阶段。初创期开始于20世纪60年代，当时的图像采用像素型光栅进行扫描显示，大多采用中、大型机进行处理。在这一时期，由于图像存储成本高，处理设备造价高，因而其应用面很窄。20世纪70年代进入发展期，开始大量采用中、小型机进行处理，图像处理也渐渐改用光栅扫描显示方式，特别是出现了CT和卫星遥感图像，对图像处理的发展起到了很好的促进作用。到了20世纪80年代，图像处理技术进入普与期，此时的微机能够担当起图形图像处理的任务。VLSI的出现更使得处理速度大大提高，其造价也进一步降低，极促进了图像图像系统的普与和应用。20世纪90年代是图像技术的实用化时期，图像处理的信息量巨大，对处理速度的要求极高。21世纪的图像处理技术要向高质量化方面发展，主要体现在以下几点：a高分辨率、速度高：图像处理技术发展的最终目标是要实现图像的实时处理，这在移动目标的生成、识别和跟踪上有着重要意义；b立体化：立体化包括的信息量最为丰富和完整，未来采用数字全息技术将有助于达到这个目的；c智能化:其目的是实现图像的智能生成、处理、识别和理解。1.3图像分割在图像工程中的地位图像图形是人类交流和认识客观世界主要媒体，科学研究和统计表明，视觉系统帮助人类从外界获得34以上的信息，而图像图形带给我们的正是视觉世界中的所有信息。视觉信息所起的客观作用是其他信息不能替代的，百闻不如见就是一个非常形象的例子。图像图形是现代信息化社会的重要支柱4。图像图形科学是一门理论与现代高科技相结合来系统地研究各种视觉原理、技术和应用的综合性很强的交叉学科。图像图形技术在广义上是各种与视觉有关技术的总称。它包括利用计算机和其他电子设备观察世界而获得数据与对数据处理并且显示这些数据的理论和技术。图像图形科学具有涉与面广、容丰富、跨行业、跨学科的特点。从它的研究方法来看，它与数学、物理学、生理学、心理学、电子学、计算机科学等许多学科科以相互借鉴；从它的研究围来看，它与人工智能、神经网络、遗传算法、模糊逻辑等理论和技术都有密切的联系；它的发展应用与医学、军事、遥感、通信、影视、文档处理和工业自动化等许多领域也是不可分割的。它是最活跃和令人振奋的边缘学科之一。图像图形技术已经迅速渗透到人类生活和社会发展的各个方面，图像图形技术无论在科学研究、工业生产、文化娱乐、管理部门都得到越来越多的重视。目前，它已在工业检测、高空侦察、制导、文件处理、动画、虚拟现实、生物医学、人体科学、艺术、远程教育、科学可视化、计算机辅助设计、遥感、航天等方面得到越来越多的应用。进入2l世纪以来，其发展更为迅速。图像技术在广义上是各种与图像有关技术的总称。图像技术种类很多，跨度很大，但可以将它们归在一个整体框架图像工程之下。图像工程是一个对整个图像领域进行研究与应用的新学科。它的容非常丰富，根据抽象程度和研究方法不同可分为三个各有特点的分层：图像处理，图像分析和图像理解5。 图1图像分割在图像工程中的地位在对图像的研究与应用中，人们往往对图像中的某些部分感兴趣。这些部分常称为目标或前景(其他部分称为背景)。它们一般对应图像中特定的、具有独特性质的区域。为了辨识和分析目标，需要将它们分离提取出来，在此基础上才有可能对目标进一步利用。图像分割就是指把图像分成各具特性的区域并提取出感兴趣目标的技术过程。这里特性可以是像素的灰度、颜色、纹理等，预先定义的目标可以对应单个区域，也可以对应多个区域。 图像分割是由图像处理进到图像分析的关键步骤，在图像工程中占据重要的位置。一方面，它是目标表达的基础(见图1)，对特征测量有重要的影响。另一方面，因为图像分割与其基于分割的目标表达、特征提取和参数测量等将原始图像转化为更加抽像更加紧凑的形式，使得更高层的图像分析和理解成为可能6。1.4 图像分割的研究意义图像分割是数字图像处理中的一项关键技术，它使得其后的图像分析，识别等高级处理阶段所要处理的数据量大大减少，同时又保留有关图像结构特征的信息。由于分割中出现的误差会传播至高层次处理阶段，因此分割的精确程度是至关重要的，多年来一直受到研究人员的高度重视，被认为是计算机视觉中的一个瓶颈。图像分割是一种重要的图像技术，在不同领域中有时也用其它名称：如目标轮廓(object delineation)技术，阈值化(threshold)技术，图像区分或求差(image discrimination)技术，目标检测(target detection)技术，目标识别(target recognition)技术，目标跟踪(target tracking)技术等，这些技术本身或其核心实际上也就是图像分割技术。图像分割是图像处理、分析的一项基本容。 图像分割的应用非常广泛，几乎出现在有关图像处理的所有领域，并涉与各种类型的图像。图像分割在工业自动化、在线产品检验、生产程控、文件图像处理、遥感图像、保安监视、以与军事、体育、农业工程等方面都有广泛的应用。例如：在遥感图像中，合成孔径雷达图像中目标的分割、遥感云图中不同云系和背景分布的分割等；在医学应用中，脑部MR图像分割成灰质（GM）、白质（WM）、脑脊髓（CSF）等脑组织和其它脑组织区域（NB）等；在交通图像分析中，把车辆目标从背景中分割出来等；在面向对象的图像压缩和基于容的图像检索中将图像分割成不同的对象区域等。在各种图像应用中，只要需对图像目标进行提取，测量等都离不开图像分割。图像分割的准确性将直接影响后续任务的有效性，因此图像分割具有十分重要的意义。1.5 图像分割的研究现状与发展趋势对图像分割来说，如果不利用关于图像或所研究目标的先验知识，任何基于数学工具的解析方法都很难得到很好的效果。因此，在更多的时候，人们倾向于重新设计一个针对具体问题的新算法来解决所而临的图像分割问题。这在只有少量图像样本的时候，利用各种先验知识，设计一个具有针对性的算法进行图像分割是比较容易的。但是当需要构建一些实用的机器视觉系统时，所面临的将是具有一定差异性、数量庞大的图像库，此时如何很好的利用先验知识，设计一个对所有待处理图像都实用的分割算法将是一件非常困难的任务。其次，由于缺乏一个统一的理论作为基础，同时也缺乏对人类视觉系统(human vision system，HVS)机理的深刻认识，构造一种能够成功应用于所有图像的统一的图像分割算法，到目前为止还是难以实现的。遗憾迄今为止还没有一个完善的理论来指导如何根据图像的特点来选择合适的法7。现实生活中在分割一幅图像时，多是依据经验和直觉去选择方法，通过反复实践来找到一种最佳的方法。与计算机科学技术的确定性和准确性相比，图像分割更像是一种艺术行为，有经验的人能比较容易的选用出适当的方法，使不同的图像都得到最佳的分割效果。但是，当要处理的图像十分庞大时，图像分割就像是流水线上的一道简单工序，这种艺术行为就显得无能为力了。随着图像技术和多媒体技术的发展，包括图像、音频和视频等信息的多媒体数据己经广泛用于Internet和企事业信息系统中，而且越来越多的商业活动、信息表现和事务交易中都将包括多媒体数据，自然也就包含了大量的图像，基于容的图像检索(intent based image retrieval，CBIR)的广泛应用就是一个例子，这些常常都是以图像分割作为基础的。纵观图像分割技术这些年的发展，其中有几个明显的趋势：第一，大量学者致力于将新的概念、新的方法引入图像分割领域，如这几年逐渐引起人们重视的模糊算法、神经网络与遗传算法、小波分析、粗集理论、数学形态学等理论都先后被应用于图像分割领域，为该领域中的研究注入了新的活力，有效的解决了原有理论的一部分缺陷，改善了分割效果，更重要的是为图像分割问题的最终解决开拓了新的思路。随着基础理论研究的深化，这一趋势是必将会继续下去。第二，人们非常重视多种分割算法的有效结合。综合使用2种或2种以上的方法，能够部分克服单独的图像分割算法难以对一般图像取得令人满意的分割效果的问题，占据了分割领域中现有文献的大部分，而采取什么样的结合方式才能体现各种方法的优点，弥补各自的不足，取得好的预期效果，在未来将仍是人们关注的主要问题之一。第三，针对特定领域的特殊问题，利用这些领域的专业知识来辅助解决图像分割问题，越来越多的吸引了研究人员的注意力。相应的，对图像分割作为一个统一对象的研究在逐渐弱化。医学图像处理中的病理图像分割、工业图像分割、安全图像处理中的信息提取、军事图像处理中的雷达图像分割与卫星图像分割、交通图像处理中的车牌识别等都是近几年来图像分割领域中讨论较多的热点问题。2 图像分割的基本理论2.1图像分割的定义在图像的研究和应用中，人们往往只对一幅图像中的某些部分感兴趣，这些感兴趣的部分一般对应图像中特定的、具有特殊性质的区域（可以对应单个区域，也可以对应多个区域），称之为目标或前景；而其它部分称为图像的背景8。为了辨识和分析目标，需要把目标从一幅图像中孤立出来，这就是图像分割要研究的问题。所谓图像分割，从广义上来讲，是根据图像的某些特征或特征集合（包括灰度、颜色、纹理等）的相似性准则对图像像素进行分组聚类，把图像平面划分成若干个具有某些一致性的不重叠区域。这使得同一区域中的像素特征是类似的，即具有一致性；而不同区域间像素的特征存在突变，即具有非一致性4。从集合的角度出发，图像分割定义如下：设R代表整个图像区域,对R的分割可看作将R分成若干个满足一下5个条件的非空子集（子区域） ， ， ，。(1)即分割成的所有子区域的并应能构成原来的区域R。(2)对所有的i和j与i j，有即分割成的各子区域互不重叠。(3)对于；有。即分割得到的属于同一区域的像素应具有某些一样的特性。(4)对于，有。即分割得到的属于不同区域的像素应具有不同的性质。(5)对于；是连通的区域。即同一子区域的像素应当是连通的。2.2 图像分割的体系结构图像工程可分三个层次:图像处理(像素)、图像分析(目标)和图像理解(符号)。图像分割是从图像处理进到图像分析的关键步骤，也是进一步理解的基础。图像分割的体系结构可以用图2表示。基本分割算法图像分割分割技术分割评价现代分割算法基本分割算法现代分割算法图2图像分割的体系结构2.3图像分割方法分类关于图像分割技术，由于问题本身的重要性和困难性，从20世纪70年代超图像分割问题就吸引了很多研究人员为之付出了巨大的努力。虽然到目前为止，还不存在一个通用的完美图像分割方法，但是对于图像分割静一般性规律，则基本上已经达成了共识，已经产生了相当多的研究结果和方法。在国外学者对图像分割进行的研究中，产生了大量的有价值的成果，根据研究的角度不同大致有以下的分类方法。根据应用目的不同，图像分割可分为粗分割和细分割两大类。对于模式识别应用，一个物体对象部的细节与颜色(或灰度)渐变应被忽略，而且一个物体对象只应被表示必一个或少数几个分割区域，即粗分割；而对于基于区域或对象的图像压缩与编码，其分割的目的是为了得到色彩信息一致的区域，以利于高效的区域编码，若同一区域含有大量变化细节，则难以编码，因此，图像需要细分割，即需要捕捉图像的细微变化。根据分割方法的不同，图像分割可被粗略地分为三类：基于直方图的分割技术(阈值分割、聚类等）、基于邻域的分割技术(边缘检测、区域增长)、基于物理性质的分割技术(利用光照特性和物体表面特征等)。 图像分割方法是多种多样的，本文将现将分割方法分为四类：(1)阈值分割方法；(2)边缘检测方法；(3)区域提取方法；(4)结合特定理论工具的分割方法9。2.3.1 阈值分割方法 阈值分割方法的历史可追溯到近40年前，现已提出了大量算法，对灰度图像的取阈值分割就是先确定一个处于图像灰度取值围之中的灰度阈值，然后将图像中各个象素的灰度值都与这个阈值相比较，并根据比较结果将对应的象素分为两类。这两类象素一般分属图像的两类区域，从而达到分割的目的10。从该方法中可以看出，确定一个最优阈值是分割的关键。现有的大部分算法都是集中在阈值确定的研究上。阈值分割方法根据图像本身的特点，可分为单阈值分割方法和多阈值分割方法；也可分为基于象素值的阈值分割方法、基于区域性质的阈值分割方法和基于坐标位置的阈值分割方法。若根据分割算法所有的特征或准则，还可以分为直方图与直方图变换法、最大类空间方差法、最小误差法与均匀化误差法、共生矩阵法、最大熵法、简单统计法与局部特性法、概率松驰法、模糊集法、特征空间聚类法、基于过渡区的阈值选取法等。2.3.2 边缘检测方法图像最基本的特征是边缘，它是图像局部特性不连续（或突变）的结果。例如，灰度值的突变、颜色的突变、纹理的突变等&边缘检测方法是利用图像一阶导数的极值或二阶导数的过零点信息来提供判断边缘点的基本依据，经典的边缘检测方法是构造对图像灰度阶跃变化敏感的差分算子来进行图像分割。如Roberts算子，Sobel算子算子，Prewitt算子，Canny算子等。根据检测边缘采用方式的不同，边缘检测方法大致包括以下几类：基于局部图像函数的方法、多尺度方法、图像滤波法、基于反应扩散方程的方法、多分辨分法、基于边界曲线拟合方法、状态空间搜索法、动态规划法、边界跟踪法、哈夫变换法等。这类方法主要基于图像灰度级的不连续性，它通过检测不同均匀区域之间的边界来实现对图像的分割，这与人的视觉过程有些相似。依据执行方式的不同，这类方法通常又分为串行边缘检测技术和并行边缘检测技术。串行边缘检测技术首先要检测出一个边缘起始点，然后根据某种相似性准则寻找与前一点同类的边缘点，这种确定后继相似点的方法称为跟踪。根据跟踪方法的不同，这类方法又可分为轮廓跟踪、光栅跟踪和全向跟踪三种方法。全向跟踪可以克服由于跟踪的方向性可能造成的边界丢失，但其搜索过程会付出更大的时间代价。串行边缘检测技术的优点在于可以得到连续的单像素边缘，但是它的效果严重依赖于初始边缘点，由不恰当的初始边缘点可能得到虚假边缘;较少的初始边缘点可能导致边缘漏检。并行边缘检测技术通常借助空域微分算子，通过其模板与图像卷积完成，因而可以在各个像素上同时进行，从而大大降低了时间复杂度。常见并行边缘检测方法有如下儿种:Roberts算子，Laplacian算子，Sobel算子，Prewitt算子，LoG算子和canny算子等。上述算法和其他边缘检测算法虽然在检测的准确性和边缘定位精度上有所差异，但是他们都有一个共同的缺点:不能得到连续的单像素边缘，而这对于分割来说是至关重要的。所以，通常在进行上述边缘检测之后，需要进行一些边缘修正的工作，如边缘连通、去除毛刺和虚假边缘。常用的方法包括启发式连接、相位编组法和层次记号编组法等。与串行边缘检测算法一样，边缘修正算法的代价也非常高此外，也有人使用Facet模型或Hough变换检测边缘，但是这两种方法的复杂度往往是让人难以忍受的。 与这些传统的边缘检测算法相比，Snake模型从另一个角度探讨了边缘检测问题。首先，给出一条封闭曲线作为初始的边缘轮廓。此后，一方面使用像梯度场这样的图形信息作为外力，让曲线尽量靠近真实边缘;另一方面使用曲线长度、平滑程度等作为力，约束曲线的形变。在这两种力量的共同作用下，最终得到精确的、连续的物体边缘。这种方法省去了对边缘的繁琐的后处理，但是这却是以提供初始轮廓为代价的。由于图形信息所提供的外力场是很微弱的，所以初始轮廓应当比较接近真实边缘，否则，算法可能无法收敛到真实边缘。2.3.3 区域提取方法区域提取法有两种基本形式：一种是从单个象素出发，逐渐合并以形成所需的分割区域；另一种是从全图出发，逐渐分裂切割至所需的分割区域。在实际中使用的通常是这两种基本形式的结合。根据以上两种基本形式，区域提取法可以分为区域生长法和分裂合并法。1.区域生长方法：区域生长方法从若干种子点或种子区域出发，按照一定的生长准则，对邻域像素点进行特征判别，将特征相似的相邻像素合并为同一区域；以合并像素为生长点，继续重复以上操作，最终形成具有相似特征的像素的最通集合。其中种子点可采用人机交互或自动方法设定。用于区分不同物体像素的性质包括平均灰度值、纹理或颜色信息。相似性准则可以取像素的灰度值与邻域的灰度均值比较，若差值在接受围则进行合并。这种方法若不考虑像素间的连通性和邻近性，会出现毫无意义的分类结果。这里依次用图像的每一个像素的灰度值和标准阈值相减，判断结果是否小于标准差，是则将该点和种子点合并，不是则保持像素点的灰度值不变。2.区域分裂合并法：区域分裂合并法首先将图像分割为初始的区域，然后按性质相似的准则，反复分开特性不一致的区域、合并具有一致特性的相邻区域，直至形成一区域图。这种方法能充分组合图像的全局和局部信息。下面给出一种用金字塔形四叉树数据结构指导下的分割方法，其步骤如下：(1)确定均匀性测试准则T，将原始图像构造成四叉树数据结构。(2)将图像四叉树结构中的某一中间层作为初始的区域划分。如果对任何区域R，有T()=false，则把区域分裂成四个子区，若任一四分之一子区，有H()=false，则再将该子区一分为四个区域。如果对任一恰当的四个子区有H (UUU)=true，则再把四个子区合并成一个区。重复上述操作，直到不可再分或再合为止。(3)若有不同大小的两个相邻区域和，满足H(U) =true，则合并这两个区域。区域分裂一合并法能够较好的保持原图像的特性，这点优于区域增长法处理。但也存在区域初始划分和选择区域性质一致性度量、边界模糊性度量两个重要的问题。而且算法结构本身与对数据结构的要求都比较复杂，因此计算量很大。区域提取法的缺点是往往会造成过度分割 ，即将图像分割成过多的区域。2.3.4 结合特定理论工具的分割方法图像分割至今为止尚无通用的自身理论)近年来，随着各学科许多新理论和新方法的提出，人们也提出了许多与一些特定理论、方法和工具相结合的分割技术。（1）基于数学形态学的分割技术其基本思想是用具有一定形态的结构元素去量度和提取图像中的对应形状以达到对图像分析和识别的目的。（2）基于模糊技术的图像分割方法基于模糊集合和逻辑的分割方法是以模糊数学为基础，利用隶属决图像中由于信息不全面、不准确、含糊、矛盾等造成的不确定性问题，该方法在医学图像分析中有广泛的应用。（3）基于人工神经网络技术的图像分割方法基于神经网络的分割方法的基本思想是通过训练多层感知机来得到线性决策函数，然后用决策函数对象素进行分类来达到分割的目的。（4）遗传算法在图像分割中的应用遗传算法是基于进化论自然选择机制的、并行的、统计的、随机化搜索方法。对此，科学家们进行了大量的研究工作，并成功地将它们运用于各种类型的优化问题，在分割复杂的图像时，人们往往采用多参量进行信息融合，在多参量参与的最优值的求取过程中，优化计算是最重要的，把自然进化的特征应用到计算机算法中，将能解决很多困难。遗传算法的出现为解决这类问题提供了新而有效的方法，它不仅可以得到全局最优解，而且大量缩短了计算时间11。2.4图像分割的质量评价一般认为对于图像分割方法的评价可以通过分析和实验两种方式来进行，因此，分割评价方法可以分为分析法和实验法两大类。分析法是直接分析分割算法的原理与性能；而实验法是通过对彩色图像的分割结果来评价算法。尽管利用分析法的评估可以免除一些试验因素的影响，但是，并不是所有的性能都能够通过分析而得到， 而且仅仅从算法本身的原理与性能出发的分析，往往缺乏足够的说服力，相对而言，实验评估的方法更具有实际意义。有关分割方法的实验已提出了不少，大致又可以分为“优度法”和“偏差法”两类。优度法是建立在人的视觉基础上的某些特性图像为依据的。偏差法则往往需要首先提供一个理想的分割图像作为比较标准，依此来计算实际分割与理想分割的差别。Chahnav等人对图像分割算法的评价就是一种典型的“偏差法”。其理想分割图像是若干个操作人员的分割结果，以此为标准，比较计算机分割结果是否与这些标准一致。实际中，由于目标图像的不可预知性以与能手工分割的专家分割差异的存在和专家的稀缺性，可供比较的理想分割图像样本很难得到并被统一认定。因此，这类方法在使用上有很大的局限性。实验优度法在没有正确分割的先验知识的情况下， 根据分割图形计算某种优度量值来评价分割算法的好坏。常用的优度量值是区域一致性、区域对比度、区域形状参数等。3 图像的并行边界分割技术3.1基本概念并行边界技术是指用并行的方法通过对目标边界的检测来实现图像分割的技术。它有着悠久的历史，早在1965年就有人提出检测边缘的算子其后有关的研究就一直不断12。 并行边界技术采用的方法原理与人的视觉过程有些相似。人们对场景中亮度或其他性质变化较快的部位比较敏感，一般当人观察场景时总先注意到其中不同物质的相交处，并可以很快得出每个物体各自的轮廓。人在进行这个工作时常常是同步开展的，即同时检测轮廓的各部分。并行边界技术在确定图像中边界区域时也是同步进行的（在确定一组点是否组成一段边界时不需先考虑其他点是否为边界点）。从某种意义上说，图像部分信息都集中在区域的边界上，边界的确定对场景的理解非常重要。采用并行边界技术进行图像分割主要有两个步骤：1检测目标的边界点;2组成目标的边界。 图像分割第一个步骤可采用微分算子来直接检测，也可建立边缘模型通过拟合来间接检测，第二个步骤往往比较复杂。对实际有噪声的图像，仅用微分算子检测出的边缘点并不能组成封闭的边界而将目标从背景中分离出来。这就需要有种算法能够闭合边界，下面将介绍并行图像分割的几种经典算法。3.2经典算法3.2.1微分算子边缘检测边缘的检测常借助空域微分算子进行，通过将其模板与图像卷积完成。灰度边缘是灰度值不连续(或突变)的结果，这种不连续常可利用求导数方便地检测到。一般常用一阶和二阶导数来检测边缘，其原理可用图2来说明。图3 边缘与导数常见的边缘剖面有两种:阶梯状(如图(a)和图(b)所示)；脉冲状(如图(c)所示)。阶梯状的边缘处于图像中两个具有不同灰度值的相邻区域之间，脉冲状主要对应细条状的灰度值突变区域，而屋顶状的边缘上升下降沿都比较缓慢。由于采样的缘故，实际数字图像中的边缘总有一些模糊，即边缘有一定的宽度，所以这里垂直上下的边缘剖面都表示成有一定坡度。对真实的边缘来说，描述它的主要参数有五个:位置；朝向；幅度；均值；斜率。下面分析一下导数与边缘的关系。在图(a)中，灰度值都为零。这表明可用一阶导数的幅度值来检测边缘的存在，幅度峰值一般对应边缘位置。进一步，在图(a)中，灰度值剖面的二阶导数在一阶导数的阶跃上升区有一个向上的脉冲，而在一阶导数的阶跃下降区有一个向下的脉冲。在这两个阶跃之间有一个过零点，它的位置正对应原图像中边缘的位置。这表明可用二阶导数的过零点也可到检测边缘位置，而且定位较为准确，用二阶导数在过零点附近的符号还确定各个边缘像素是在图像边缘两旁的暗区还是明区。分析图(b)可得到相似的结论。区别是这里图像由明变暗，所以与图(a)相比，剖面左右对换，一阶导数上下对换，二阶导数左右对换。图(c)中，脉冲状的剖面边缘与图(a)的一阶导数形状一样，所以图(c)的一阶导数形状与图3(a)的二阶导数形状一样，这表明通过检测一阶导数的上下峰值可确定脉冲边缘的围。图(c)的两个二阶导数过零点正好分别对应脉冲的上升沿和下降沿，这表明通过检测脉冲剖面的两个二阶导数过零点也可确定脉冲状边缘的围。图(d)中，屋顶状边缘的剖面可看作是将脉冲状边缘底部展开得到的，或者说是模糊围较大的边缘，所以它的一阶导数可看作是将图(c)中脉冲剖面的一阶导数和下降沿拉开得到的。通过检测屋顶状边缘剖面的一阶导数过零点也可以确定出屋顶边缘中心位置。屋顶状边缘也可看作由两个斜坡状边缘组合而成。由此可见，图像中目标的边界可通过求取它们的导数来确定。导数可用微分算子来计算，实际数字图像处理中求导数是用差分近似微分来进行的。下面是几种常见的微分算子的比较。Roberts算子：边缘定位准，但是对噪声敏感。适用于边缘明显且噪声较少的图像分割。Roberts边缘检测算子是一种利用局部差分算子寻找边缘的算子,Robert算子图像处理后结果边缘不是很平滑。经分析，由于Robert算子通常会在图像边缘附近的区域产生较宽的响应，故采用上述算子检测的边缘图像常需做细化处理，边缘定位的精度不是很高。（2）Prewitt算子：对噪声有抑制作用，抑制噪声的原理是通过像素平均，但是像素平均相当于对图像的低通滤波，所以Prewitt算子对边缘的定位不如Roberts算子。（3）Sobel算子：Sobel算子和Prewitt算子都是加权平均，但是Sobel算子认为，邻域的像素对当前像素产生的影响不是等价的，所以距离不同的像素具有不同的权值，对算子结果产生的影响也不同。一般来说，距离越远，产生的影响越小。（4）Isotropic Sobel算子：加权平均算子，权值反比于邻点与中心点的距离，当沿不同方向检测边缘时梯度幅度一致，就是通常所说的各向同性。在边沿检测中，常用的一种模板是Sobel 算子。Sobel 算子有两个，一个是检测水平边沿的；另一个是检测垂直平边沿的 。Sobel算子另一种形式是各向同性Sobel(Isotropic Sobel)算子，也有两个，一个是检测水平边沿的 ，另一个是检测垂直平边沿的 。各向同性Sobel算子和普通Sobel算子相比，它的位置加权系数更为准确，在检测不同方向的边沿时梯度的幅度一致。由于建筑物图像的特殊性，我们可以发现，处理该类型图像轮廓时，并不需要对梯度方向进行运算，所以程序并没有给出各向同性Sobel算子的处理方法。由于Sobel算子是滤波算子的形式，用于提取边缘，可以利用快速卷积函数，简单有效，因此应用广泛。美中不足的是，Sobel算子并没有将图像的主体与背景严格地区分开来，换言之就是Sobel算子没有基于图像灰度进行处理，由于Sobel算子没有严格地模拟人的视觉生理特征，所以提取的图像轮廓有时并不能令人满意。上面的算子是利用一阶导数的信息，属于梯度算子畴。 Laplacian算子：这是二阶微分算子。其具有各向同性，即与坐标轴方向无关，坐标轴旋转后梯度结果不变。但是，其对噪声比较敏感，所以，图像一般先经过平滑处理，因为平滑处理也是用模板进行的，所以，通常的分割算法都是把Laplacian算子和平滑算子结合起来生成一个新的模板。Laplacian算子一般不以其原始形式用于边缘检测，因为其作为一个二阶导数，Laplacian算子对噪声具有无法接受的敏感性；同时其幅值产生算边缘，这是复杂的分割不希望有的结果；最后Laplacian算子不能检测边缘的方向；所以Laplacian在分割中所起的作用包括：（1）利用它的零交叉性质进行边缘定位；（2）确定一个像素是在一条边缘暗的一面还是亮的一面；一般使用的是高斯型拉普拉斯算子（Laplacian of a Gaussian,LoG)，由于二阶导数是线性运算，利用LoG卷积一幅图像与首先使用高斯型平滑函数卷积改图像，然后计算所得结果的拉普拉斯是一样的。所以在LoG公式中使用高斯函数的目的就是对图像进行平滑处理，使用Laplacian算子的目的是提供一幅用零交叉确定边缘位置的图像；图像的平滑处理减少了噪声的影响并且它的主要作用还是抵消由Laplacian算子的二阶导数引起的逐渐增加的噪声影响7。3.2.2边界闭合常根据一个小区域所点有进行，所以得到的边缘位置在一定情况下可以算到像素的部，即达到亚像素级。边缘不同，模型参数也可不同。边缘为阶跃型，则模型主要参数为阶跃的幅度和方向;如果为脉冲型，则还要加上脉冲宽度参数;如果为屋顶状(斜面)，则还要加上斜度参数。对复杂边缘的拟合可采用将对简单边缘拟合方法推广来实现。在有噪声时，得到的边缘像素常常是孤立的或仅分小段连续的。换句话说，在检测得到的边缘图中，有些是真正的边界像素，有些则是噪声点。有时可采用闭值化的方法把它们分离开。另外还常有真正的边界像素未能检测出来的情况。为将图像中不同的区域分开，需要将边缘像素连接起来组成区域的封闭边界。前述的边缘检测算子都是并行工作的，如果边界闭合也能并行完成。则分割基本上可以并行实现。下面介绍一种利用像素梯度的幅度和方向并行地进行边界闭合的方法。边缘像素连接的基础是它们的梯度之间有一定的相似性。用梯度算子对图像处理可得到像素两方面的信息:1.梯度的幅度;2.梯度的方向。事实上，对复杂的场景上述边界闭合方法的效果是有限的。注意这里是否将边缘点连接起来的决定可以并行处理，即一个像素是否与它邻域中的另一个像素连通的决定并不需要在其他判断后作出。将这个方法推广，也可用于连接相距较近的间断边缘段和消除独立的(常由噪声干扰产生的)短边缘段。3.2.3边缘拟合边缘拟合的中心思想：若边缘点很稀疏，则需要用某个解析函数如分段线性或高阶样条曲线来拟合边缘。称为边缘拟合。常根据图像一小块区域来建立拟合模型。常用方法有：（1）迭代端点拟合的分段线性方法；（2）灰度阶跃边缘；（3）灰度斜变边缘。(1)迭代端点拟合（iterative endpoint fitting）图4 迭代端点拟合模型图Step1：首先确定一个散布在两个特定边缘点A和B之间的边缘点集合P；Step2：首先从A到B引一条直线，然后计算其他边缘点到该直线的垂直距离；Step3：将距离最大的点标记为C，然后将P分为包含A和C之间的边缘点集合和包含C和B之间的边缘点集合；Step4：重复step2和step3，知道边缘点集合的点到线距离小于某固定距离。Step5：对每个边缘点集合采用直线拟合。（2） 灰度阶跃边缘模型 图5理想阶跃边缘模型图Step1:基于三种常用网络，确定以点P为中心的图像区域QStep2:设其满足理想阶跃模型（3-1）模型有三个未知值，s 和t；Step3：用该模型去拟合实际图像区域，则最小平方拟合误差为：（3-2）Step4：假设=，则有：（3-3）（3-4）（3-5）（3） 灰度渐变边缘模型如下图 图6 灰度渐变边缘模型Step1：将一幅图像表示成一系列相邻但不相交的子区域集合Q；Step2：对每一个区域建立一个斜面方程模型： （3-6）Step3：用拟合，则最小拟合误差为：（3-7）Step4：如果Q是3*3的子图像，则拟合即Prewitt模板（3-8）（3-9）（3-10）Step5：将一幅图像表示成一些列斜面集合后图像的边缘即不同斜面的交界则边缘问题转换为如何确定不同斜面与求它们的交线问题。3.2.4哈夫变换哈夫变换方法是利用图像全局特性而直接检测目标轮廓，即可将边缘像素连接起来组成区域封闭边界的一种常见方法。在预先知道区域形状的条件下，利用哈夫变换可以方便地得到边界曲线而将不连续的边缘像素点连接起来。哈夫变换的主要优点是受噪声和曲线间断的影响较小。利用哈夫变换还可以直接分割出某些已知形状的目标，并有可能确定边界到亚像素精度。哈夫变换方法是利用图像得全局特性而对目标轮廓进行直接检测的方法，在已知区域形状的条件下，哈夫变换可以准确地捕获到目标的边界（连续的获不连续的），并最终以连续曲线的形式输出变换结果，该变换可以从强噪声环境中将已知形状的目标准确得分割提取出来。哈夫变换的核心思想就是: 点线的对偶性(duality)。通过变换将图像从图像控件转换到参数空间,在图像空间中一条过点(x,y)的直线方程为y=px+q,通过代数变换可以转换为另一种形式p=-px+y,即参数空间中过点(p,q)的一条直线,如果在图像空间中保持直线的斜率和截距的不变,其在参数空间必定过点(p,q),这也就说明,在图像空间中共线的点对应参数空间共点的线. 哈夫变换就是根据上述点线的对偶性把在图像空间中存在的直线检测问题转换为参数空间中存在的点检测问题,后者的处理要比前者简单易行得多,只需简单地累加统计即可实现对边缘的检测.哈夫变换不仅能检测直线等一阶曲线的目标,对于园、椭圆等高阶的曲线都可以检测出来。如圆的方程为：(3-11)其参数空间是一个3D空间A(a，b，r)，原理与检测直线上的点一样，只是复杂性增加了。如果圆的半径r己知，则问题又回到了2D空间A(a，b)。哈夫变换对已知目标的检测过程受随机噪声和曲线中断等不利因素的影响很小，而且分割出的目标是直接放到另一个“干净”的缓存中的，因此可以做到零噪声，是相当有优势的。常规的哈夫变换在理论上能对所有可以写出具体解析表达式的曲线进行目标检测，但是在实际处理时，经常待检测的目标不规则或是很难获取甚至根本没有解析式，此时就要采取广义上的哈夫变换来检测目标12。4 结合微分算子与边界闭合的图像分割4.1 边缘检测数字图像的边缘检测是图像风格、目标区域的识别、区域形状提取等图像分析领域中十分重要的基础。边缘检测技术在数字图像处理中非常重要，因为边缘是图像中所要提取的目标和背景的分界线，只有提取出了边缘才能将背景和目标区域分开来。两个既有不容灰度值的相邻区域之间总存在边缘，边缘是灰度值不连续的结果这种不连续通常可以利用求倒数的方法方便的检测到。一般常用一阶导数和二阶导数来检测边缘。边缘检测技术可以按照处理的顺序分为串行边缘检测以与并行边缘检测。在串行边缘检测技术中。当前像素点是否属丁欲检测的边缘，取决于先前像素的验证结果;而在并行边缘检测技术中.一个像素点是否属于欲检测的边缘，取决于当前正在检测的像素点以与该像素点的一些相邻像索点，这样该模型可以同时用于检测图像中的所有像素点，因而称之为并行边缘检测技术。最简单的边缘检测方法是并行微分算子法，它利用相邻区域的像素值不连续的性质，采明一阶或二阶导数来检测边缘点并行边缘检测的基本思想首先是利用边缘增强算子，突出图像中的局部边缘，然后定义系那个数的“边缘强度”，通过设值阈值的方法提取边缘点集。但是优于噪声和图像模糊的愿意，检测到的边界可能会有间断的情况发生。所以边缘检测包含两个容：(1)用边缘算子提取边缘点集；(2)在边缘点集中取出某些边缘点，填充一些边缘点，再将得到的边缘点集连接为线13。4.1.1 拉普拉斯高斯算子检测图像边缘拉普拉斯高斯算子（Laplacian of Gaussian算子，通常缩写为LoG算子）是一种二阶微分算子，将在边缘处产生一个陡峭的零交叉。LoG算子是一个线性的、移不变的算子，它通过寻找图像灰度值中二阶微分是零的点来检测边缘点。对一个连续函数，其在处的LoG算子定义如下：拉普拉斯算子是一个二阶导数算子该算子通常有下列计算公式表示: （4-1）式4-1中表示数字图像中每个像素关于轴和轴的二阶偏导数之和即处理后像素 处的灰度值,是具有整数像素坐标的输入图像。高斯算子如下式所：（4-2）式（4-2）中是方差,是离原点的径向距离,即,为图像的横坐标和纵坐标。高斯拉普拉斯算子是两种算子的结合,既具备高斯算子的平滑特点又具备拉普拉斯算子锐化点。平滑和锐化,积分和微分是一对矛盾的两个侧面,统一在一起后就变成了