[硕士论文精品]粒子群图像分割

摘要I改进型粒子群优化算法及其在图像分割中的应用姓名肖高超导师王强专业计算机软件与理论方向人工智能与图像处理年级2005摘要粒子群优化算法PARTICLESWARMOPTIMIZATION,PSO算法源于鸟群和鱼群群体运动行为的研究，是一种基于种群搜索策略的自适应随机优化算法。作为群智能的典型代表，粒子群优化算法已被证明是一种有效的全局优化方法，它收敛速度快、计算简单和容易实现，因而一经提出就受到全世界研究者的广泛重视。目前已经被广泛应用于图像分割、目标函数优化、神经网络训练、模糊控制系统等许多领域，并取得了很好的效果。然而它仍然存在一些缺点容易陷入局部最优以及在演化后期收敛速度迅速减小，因此往往收敛不到全局最优解。图像分割是目标检测和识别过程中的重要步骤，其目的是将感兴趣区域从图像中分割出来，从而为计算机视觉的后续处理提供依据。对图像进行分割的方法有多种，阈值法因实现简单而成为一种有效的图像分割方法。然而要在直方图呈多峰分布的复杂图像中搜索一个最佳多阈值组合对图像进行分割，它的高耗时性无法满足实时性的要求，而阈值的准确确定又是有效分割图像的关键。因此，快速准确地搜索到图像分割的多阈值组合将是问题的难点。然而要快速和准确地确定复杂图像中的多阈值最佳组合，使分割效果好且满足实时性要求，就必须寻求一种高效的算法来解决基于多值阈值法的图像分割问题。本文在前人工作的基础上，对粒子群优化算法及其在图像分割中的应用进行了研究。本文的主要研究内容如下第一部分分别对粒子群优化算法的研究现状和图像分割方法的发展状况以及相关的基本概念进行了介绍，并阐述了本文的主要工作。在第二部分，为了提高粒子群算法的收敛速度同时提高算法的全局搜索性能，本文提出了一种新颖的改进型粒子群优化算法，该算法根据定义的两个因子进化速度因子和聚集程度因子来共同确定并动态改变粒子速度更新公式中的惯性权重。算法为了进一步提高收敛速度，当群体最近几次迭代几乎停止收敛时，将根据适应度大小复制较好的粒子去取代较差的粒子，重新组合成一个较优的粒子群继续优化进程。通过对不同测试函数的仿真实验表明改进型粒子群优化算法能显著地提高了粒子群优化算法的收敛速度和全局搜索性能。同时，本文改进的粒子群优化算法被应用于基于多值阈值法的图像分割实验中，实验表明该算法能快速准确地找到分割阈值的最佳组合，取得好的分割效果且适合多峰直方图的复杂图像。关键词粒子群优化算法图像分割阈值惯性权重摘要IIANIMPROVEDPARTICLESWARMOPTIMIZATIONALGORITHMANDITSAPPLICATIONONIMAGESEGMENTATIONAUTHORGAOCHAOXIAOTUTORQIANGWANGSPECIALTYCOMPUTERSOFTWARERESEARCHDIRECTIONIMAGEPROCESSINGANDARTIFICIALINTELLIGENCEGRADE2005ABSTRACTPARTICLESWARMOPTIMIZATIONPSOALGORITHMISINSPIREDBYSOCIALBEHAVIOROFBIRDFLOCKINGORFISHSCHOOLINGITISAPOPULATIONBASED,SELFADAPTIVESEARCHOPTIMIZATIONTECHNIQUEASAKINDOFSWARMINTELLIGENCE,ITHASBEENPROVENTOBEAPOWERFULGLOBALOPTIMIZATIONMETHODPSOALGORITHMHASATTRACTEDALOTOFATTENTIONFROMRESEARCHERSAROUNDTHEWORLDSINCEITSINTRODUCTION,ASITSADVANTAGESSUCHASRAPIDCONVERGENCETOWARDSANOPTIMUM,SIMPLECOMPUTING,EASYIMPLEMENTATIONNOWITHASALREADYBEENSUCCESSFULLYAPPLIEDINMANYAREAS,SUCHASIMAGESEGMENTATION,FUNCTIONOPTIMIZATION,ARTIFICIALNEURALNETWORKTRAINING,FUZZYSYSTEMCONTROLHOWEVER,PSODOESEXHIBITSSOMEDISADVANTAGESITSOMETIMESISEASYTOBETRAPPEDINLOCALOPTIMA,ANDTHECONVERGENCERATEDECREASEDCONSIDERABLYINTHELATERPERIODOFEVOLUTION,THUSTHEGLOBALOPTIMALSOLUTIONCANTBEACHIEVEDIMAGESEGMENTATIONISREGARDEDASANIMPORTANTSTEPINOBJECTEXAMINATIONANDCHARACTERRECOGNITIONTHEMAINOBJECTIVEISTOEXTRACTOBJECTSOFINTERESTFROMANACQUIREDIMAGE,SOITPROVIDESTHEEVIDENCETOTHESUBSEQUENTPROCESSINGOFCOMPUTERVISIONSEVERALMETHODSAREPROPOSEDFROMDIFFERENTTHEORETICALPOINTOFVIEWFORIMAGESEGMENTATIONIMAGETHRESHOLDSEGMENTATIONISAPOWERFULTOOLFORIMAGESEGMENTATIONFORITSSIMPLICITYHOWEVERTHEPROBLEMOFTIMECONSUMINGCOMPUTATIONWONTMEETREALTIMEREQUIREMENTWHENWETRYTOSEARCHOPTIMUMMULTILEVELTHRESHOLDINGONAMULTIMODALHISTOGRAMOFACOMPLEXIMAGEITSAKEYFOREFFECTIVEIMAGESEGMENTATIONTOEXACTLYDETERMINETHOSETHRESHOLDINGSOITISADIFFICULTPROBLEMFORUSTOQUICKLYANDEXACTLYSEARCHOPTIMUMMULTILEVELTHRESHOLDINGFORIMAGESEGMENTATIONHOWEVER,TOQUICKLYANDEXACTLYDETERMINEOPTIMUMCOMBINATIONOFMULTILEVELTHRESHOLDING,WHICHCANSEGMENTTHEIMAGEEFFICIENTLYANDMEETREALTIMEREQUIREMENT,WEMUSTEXPLOREANEFFECTIVEANDRAPIDALGORITHMTOSOLVETHEPROBLEMOFIMAGESEGMENTATIONBASEDONMULTILEVELTHRESHOLDINGBASEDONTHEFORMERRESEARCH,THEAUTHORSTUDIESTHEIMPROVEMENTOFPARTICLESWARMALGORITHMANDITSAPPLICATIONONIMAGESEGMENTATIONTHEMAINWORKSOFTHEDISSERTATIONCANBEORGANIZEDASFOLLOWSPARTONEINTRODUCESINDETAILTHESTATUSOFPARTICLESWARMALGORITHMANDIMAGESEGMENTATION摘要IIIRESPECTIVELY,FOLLOWEDBYTHERELATIVEBASICCONCEPTANDTHEMAINWORKSOFTHISDISSERTATIONINPARTTWO,INORDERTOSEEKANIMPROVEDPSOWHICHCANGREATLYINCREASETHECONVERGENCEVELOCITYOFALGORITHMANDINCREASETHEGLOBALSEARCHCAPABILITYANOVELIMPROVEDPSOALGORITHMISPRESENTEDINTHISDISSERTATIONTHEALGORITHMDEFINESTWOFACTORS,THEEVOLUTIONSPEEDFACTORANDAGGREGATIONDEGREEFACTOR,WHICHDETERMINEANDCHANGEINERTIAWEIGHTOFVELOCITYUPDATINGFORMULAOFTHEPARTICLEDYNAMICALLYTHECONVERGENCEVELOCITYOFTHISIMPROVEDPSOALGORITHMISENHANCEDTOCONTINUEOPTIMIZINGWHENTHESWARMGOTSTAGNATEDFORLASTFEWITERATIONSBYREPLACINGSOMEWORSTPARTICLESINFITNESSVALUESBYTHECOPIESOFBETTERPARTICLESITISPROVENTHATTHEIMPROVEDALGORITHMHASHIGHPERFORMANCESINCONVERGENCESPEEDANDGLOBALSEARCHCAPABILITYONDIFFERENTBENCHMARKOPTIMIZATIONFUNCTIONSTHEPRESENTEDALGORITHMISAPPLIEDTOIMAGESEGMENTATIONBASEDONMULTILEVELTHRESHOLDINGANDITISPROVENTOBEEFFECTIVEBECAUSETHEEXPERIMENTALRESULTSHOWSTHEALGORITHMCANEXACTLYDETERMINETHEOPTIMUMMULTILEVELTHRESHOLDINGITISSUITABLEFORAMULTIMODALHISTOGRAMOFACOMPLEXIMAGEKEYWORDSPARTICLESWARMOPTIMIZATIONIMAGESEGMENTATIONTHRESHOLDINGINERTIAWEIGHT论文独创性声明本人郑重声明所提交的学位论文是本人在导师的指导下进行的研究工作及取得的成果。除文中已经注明引用的内容外，本论文不含其他个人或其他机构已经发表或撰写过的研究成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律责任。研究生签名日期论文使用授权声明本人完全了解广西师范大学有关保留、使用学位论文的规定。广西师范大学、中国科学技术信息研究所、清华大学论文合作部，有权保留本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布（包括刊登）论文的全部或部分内容。论文的公布（包括刊登）授权广西师范大学学位办办理。研究生签名日期导师签名日期第一章绪论1第一章绪论11研究的背景及其意义随着计算机信息技术的不断发展，人们越来越多的利用计算机来帮助人类获取与处理视觉图像信息。据统计，在人类从外界获取的信息中有80是来自视觉或者说图像信息，这包括图像、图形、视频、文本、数据等，它是人类最有效的信息获取和交流方式，图像也因为其所含的信息量大、表现直观而在多媒体技术中占据重要的地位。所谓图像处理，就是对图像信息进行加工以满足人的视觉心理或应用需求的行为。在对图像处理的研究和应用中，人们往往仅对图像中的某些部分感兴趣，这些感兴趣的部分常称为目标或前景，它们一般对应图像中特定的、具有独特性质的区域。图像分割的目的就是把图像分成各具特性的区域并提取出感兴趣目标的技术和过程。多年来，对图像分割的研究一直是图像技术研究中的热点和焦点，人们对其的关注和投入不断提高，它是一种重要的图像分析技术，是从图像处理到图像分析的关键步骤，也是计算机视觉领域低层次视觉中的主要问题，图像分割结果是图像特性提取和识别等图像理解的基础，对图像的加工主要处于图像处理的层次，图像分割后，对图像的分析才成为可能。另外，图像分割在实际中也得到了广泛的应用，特别是近年来随着计算机技术和图形图像学的飞速发展，使得图像分割技术成为了其它很多研究方向能否顺利发展的一个重要基础。直方图阈值法因实现简单和运算效率高而成为了一种有效的图像分割方法，阈值的确定是阈值法图像分割的关键，然而要在一幅多峰直方图的全灰度范围内搜索一个最佳多阈值组合使分割结果更为准确，问题将变得非常耗时，无法满足图像分割对实时性的要求，这严重阻碍了该方法的发展。因此，寻求一种高效快速的算法来解决基于多值阈值法的图像分割问题将具有重要的意义。粒子群优化算法PARTICLESWARMOPTIMIZATION，PSO是群体智能方法中用于解决全局优化问题的一种有效方法1，其思想是受鸟群觅食行为的启发，研究表明，粒子群优化算法在全局优化问题中，无论是就收敛速度还是全局寻优能力而言，都能表现出了很好的性能。因此本文利用改进的粒子群优化算法来求解多阈值的图像分割问题。12粒子群优化算法的研究现状粒子群优化算法最早由心理学研究者JAMESKENNEDY博士和电气工程师RUSSELLEBERHART博士在1995年共同提出的2，是一种群体智能优化方法。它同遗传算法类似，也是通过个体间的协作和竞争实现全局搜索。粒子群优化算法初始化为一群随机粒子，通过迭代在搜索空间完成寻优，它没有遗传算法的交叉以及变异算子，而是粒子在解空间追随最优的粒子进行搜索。第一章绪论2群体智能已成为人工智能研究的一个重要领域。在美国成立有专门的组织研究群体的仿真。由欧洲联盟资助的群体智能相关研究项目也于2001年在欧洲多个研究机构启动。在国内，国家自然科学基金“十五”期间学科交叉类优先资助领域中认知科学及其信息处理的研究内容就明确列出了群体智能的进化、自适应与现场认知以及复杂系统与复杂性。2001年3月8日在北京召开的第六届全国人工智能联合会议暨“863”计划智能计算机主题学术会议戴汝为院士特邀报告的主要内容就是群体智能的研究进展。到现在，国家自然科学基金委员会基本上每年资助数项粒子群优化算法相关理论和应用的研究。IEEE计算智能协会自2003年起每年举行一次群体智能会议，而粒子群优化算法是会议的重要主题。121粒子群优化算法的研究方向自粒子群优化算法问世以来，由于算法本身的易实现性和计算的快速性，使得很多研究者加入到对这种算法的研究中，目前粒子群优化算法的理论研究与应用研究都取得了很大的进展，对于算法的原理已经有了初步的了解，算法的应用也已经在不同学科中得以实现。这些研究领域主要集中在算法的改进、算法的分析以及算法的应用。下面就这三个方面的研究情况做简单的介绍。在粒子群算法的改进方面，首先是由KENNEDY和EBERHART在1997年提出的二进制PSO算法3，此算法的提出为PSO算法与遗传算法的性能比较提供了一个有用的方式，该算法可用于神经网络的结构。为了提高算法的收敛性能，SHI和EBERHART在1998年对原始PSO算法的速度项引入了参数惯性权重46，并提出在进化过程中动态地调整权重以平衡全局与局部搜索能力。惯性权重较大，全局搜索能力强，局部搜索能力弱，反之，则局部搜索能力增强，而全局搜索能力减弱。动态惯性权重能够获得比固定值更好的寻优结果。动态惯性权重可以在PSO搜索过程中线性变化，也可根据PSO性能的某个测度而动态改变。随后，CLERC等人于1999年在进化方程中引入了另一个称之为收缩因子的参数，目的是保证算法能够收敛78，同时放松了对速度的限制。为了提高基本PSO算法收敛的全局性，保证粒子的多样性是算法的关键。为了保证进化过程中粒子的多样性，SUGANTHAN在标准PSO算法中引入了空间邻域的概念9，将处于同一个空间邻域的微粒群构成一个子粒子群分别进行进化，并随着进化动态地改变阈值以保证群体的多样性；KENNEDY引入邻域拓扑的概念来调整邻域的动态选择，同时引入社会信念将空间邻域与邻域拓扑中的环拓扑相结合以增加邻域间的信息交流，从而提高群体的多样性。LOVBJERG等人于2001年将遗传算法中的子群体概念引入PSO算法中10，同时引入繁殖算子以进行子群体间的信息交流，提高群体的多样性。在粒子群优化算法的行为分析和收敛性分析方面许多学者进行了大量的研究工作。首先是采用代数方法对几种典型的PSO算法的运行轨迹进行了分析，给出了保证收敛性的参数选择范围。在收敛性方面，VANDENBERGHF引用了SOLIS和WETS关于随机性算法的收第一章绪论3敛准则1114，证明了标准PSO算法不能收敛于全局最优解，甚至不能收敛于局部最优解。在粒子群优化算法的应用方面，它已经扩展到了很多领域，从最初的复杂多峰非线性函数的优化、多目标优化等传统问题，到电力系统的分析，动态系统的跟踪与优化、神经网络的权值训练并将其用于复杂系统的建模，非线性系统的优化控制问题等等。算法研究的目的是应用，如何将粒子群算法应用于更多领域非常值得关注。122粒子群优化算法的应用现状实际应用方面，粒子群优化算法已经在优化问题求解、人工神经网络训练、电力系统等诸多领域得到了成功应用。1经典优化问题求解1组合优化。旅行商问题TSP是一类经典的组合优化问题，继蚁群算法之后，粒子群算法通过一定的改进或变形也已经成功用于TSP问题的求解。2约束优化。目前，粒子群优化算法已被有效应用于约束优化问题的求解。例如，工业下料中，要求在固定面积的材料上约束所需毛坯个数而使整块材料浪费最小的优化问题。3多目标优化。粒子群优化算法在多目标优化问题求解中有成功的应用。通过对粒子群算法全局极值和个体极值选取方式的改进，可实现对多目标优化问题最优解集的搜索。2人工神经网络训练应用采用一定的优化算法进行神经网络的训练能够提高神经网络的自学和自组织能力。目前，优化算法对神经网络的训练主要集中在网络连接权重和网络拓扑结构上。神经网络的训练问题属于超高维的优化问题。常用的反射传播算法BP难以克服局部最优问题，而遗传算法由于其复杂的进化操作，优化速度缓慢。研究表明，PSO是一种很有潜力的神经网络训练算法，PSO搜索速度快而且可以得到比较好的优化结果，克服了上述两种算法的缺点。3电力系统中的应用粒子群优化算法在电力系统优化中有着广泛的应用，例如在配电网扩展规划、检修计划、机组组合、负荷经济分配、无菌优化控制、谐波分析与电容配置、参数辨识、优化设计等方面。日本的FUJI电力公司的研究人员将电力企业著名的RPVCREACTIVEPOWERANDVOLTAGECONTROL问题简化为函数的最小值问题，并使用改进的PSO算法进行优化求解。与传统方法如专家系统、敏感性分析相比，实验结果证明了PSO算法在解决该问题上的优势。第一章绪论413图像分割方法概述图像分割是图像处理与模式识别中一项重要而基础的技术手段。其目的是把图像分割成一些有意义的或者应用中感兴趣的区域，这些区域与现实中的各类目标相对应。为了辨识和分析目标，必须将有关区域分离提取出来，在此基础上才有可能对目标的特征进行提取和测量。可以说，图像分割是成功地进行图像分析、理解和描述的前提条件。图像分割算法一般是基于亮度值的两个基本特性之一不连续性和相似性。基于亮度的不连续性分割图像，如边缘生长、边界检测；基于亮度的相似性依据事先制定的准则将图像分割为相似的区域，如阈值分割、区域生长、区域分离与合并15。图像分割理论上通过借鉴其它学科，如小波变换、分行理论、形态学、模糊数学、遗传算法、神经网络、人工智能等领域的研究成果，产生了不少新的分割算法。131基于区域的图像分割法常见的基于区域分割方法有直方图阈值法，区域分割法等。直方图阈值法是一种最常用的区域分割技术，它将灰度根据主观愿望分为两个或多个等间隔或不等间隔灰度区间，它主要是利用图像中要提取的目标物体和背景在灰度上的差异，选择一个合适的阈值，通过判断图像中的每一个像素点的特征属性是否满足阈值的要求来确定图像中该像素点属于目的区还是应该属于背景区域，从而产生二值图像，它对物体与背景有较强对比景物的分割特别有用。而且计算简单，总能用封闭而且连通的边界定义不交叠的区域。阈值法分割的结果依赖于阈值的选择，选择合适的阈值是阈值法分割的关键，阈值分割法实质上就是按照某种规则求出最佳阈值的过程，阈值的确定主要有三种方法全局阈值法、自适应阈值法、最佳阈值法。全局阈值是在整个图像中将灰度阈值的值设置为常数，这是采用阈值确定边界的最简单的方法。如果背景的灰度值在整个图像中可合理地看作为恒定，而且所有物体与背景都具有几乎相同的对比度，那么，只要选择了正确的阈值，使用一个固定的全局阈值一般会有较好的效果。常用的全局阈值选取方法有利用图像灰度直方图的峰谷法，最小误差法，最大类间方差法，最大熵自动阈值法以及其它一些方法。全局阈值能有效分割具有较大灰度差的目标和背景，但当图像的灰度差异不明显或者不同目标的灰度值有重叠时，应采用局部或动态阈值分割方法。另外，这种方法只考虑像素的灰度值，没有考虑空间特性，因此对噪声敏感。自适应阈值是指在许多情况下，物体和背景的对比度在图像中不是各处都一样的，这时很难用统一的一个阈值将物体与背景分开。这时可以根据图像的局部特征分别采用不同的阈值进行分割。实际处理时，需要按照具体问题将图像分成若干子区域分别选择阈值，或者动态地根据一定的邻域范围选择每点处的阈值，进行图像分割。最佳阈值法中阈值的选择需要根据具体问题来确定，一般通过实验来确定。对于给定的图像，可以通过分析直方图的方法确定最佳的阈值，例如当直方图明显呈现双峰情况时，可以选择两个峰值的中点作为最佳阈值。第一章绪论5区域分割法可分为区域生长法和区域分裂合并法，它是利用图像的空间性质，认为分割出来的属于同一区域的像素应具有相似的性质，其概念是相当直观的，这样就可以弥补阈值分割法没有或很少考虑空间关系而使多阈值受到限制的不足。区域生长是一种古老的图像分割方法，该方法一般是先给图像中要分割的目标物体内的一个小块或者说种子区域，再在种子区域基础上不断将其周围的像素点以一定的规则加入其中，达到最终代表该物体的所有像素点结合成一个区域的目的。区域分裂合并法不需要预先指定种子点，它按某一种一致性准则分裂或合并区域，当一个区域不满足一致性准则时被分裂成几个小的区域，当相邻区域性质相似时合并成一个大区域，它研究的重点是分裂和合并准则的设计，这种算法对复杂图像的分割效果较好，但算法复杂，计算量大，分裂可能破坏区域的边界。132基于边缘的图像分割法图像的边缘是图像最基本的特征之一，基于边缘的分割方法可以说是人们最早研究的方法。所谓边缘是指其周围像素灰度有阶跃变化的像素的集合。边缘广泛的存在于物体与背景之间、物体与物体之间，它是图像分割所依赖的重要特征。边缘检测方法试图通过检测不同区域间的边缘来解决图像分割问题。边缘检测方法按照处理的顺序分为串行边缘检测和并行边缘检测两种方法。在串行边缘检测技术中，当前像素点是否属于检测的边缘，取决于先前像素的验证结果；而在并行边缘检测技术中，一个像素点是否属于检测的边缘，取决于当前正在检测的像素点以及该像素点的一些相邻像素点，这样该模型可以同时用于检测图像中的所有像素点，因而称之为并行边缘检测技术。图像中相邻的不同区域间总存在边缘，边缘处像素的灰度值是不连续的，可以利用微分算子进行边缘检测。常用的微分算子有ROBERTS算子，PREWITT算子，SOBEL算子，LAPLACIAN算子，MARR算子，KRISCH算子等。前三种属于一阶微分算子，当区域边界清晰，边缘灰度值变化明显时，可以取得较好的分割效果，但都对噪声较为敏感。LAPLACIAN算子属于二阶微分算子，具有各向同性的特点，但对噪声更加敏感，很少直接用于边缘检测，通常用于边缘像素的区域属性判别和辅助进行边缘的精确定位。为了减轻噪声对LAPLACIAN算子的影响，MARR算子利用人的视觉机理，采用先滤波后求导的检测策略，检测效果优于以上几种算子，但MARR算子在平滑噪声的同时也降低了图像的对比度。KRISCH算子属于非线性微分算子，在保留边缘细节上有一定的优势。133结合区域与边界信息的方法在实际应用中，为取得更好的分割效果，经常把各种分割算法结合起来使用。例如基于区域的分割方法往往会造成图像的过度分割，而单纯的边缘检测有时不能提供好的区域结构，为此可将基于区域的方法和边缘检测结合起来使用。各种分割算法的结合方式是图像分割的重点。第一章绪论6基于形变模型的方法能够综合利用图像的区域和边界信息，是一种高效的图像分割方法，它结合了几何学、物理学和近似理论，通过使用从图像数据获得的约束信息和目标位置、大小、形状等先验知识，可有效的对目标进行分割、匹配和跟踪分析。134其它的图像分割方法近年来，图像分割理论通过借鉴其它学科，产生了不少新的分割方法，如数学形态学、人工神经网络、基于分形的分割方法、可变模型法、基于统计学的方法、遗传算法、人工智能等。数学形态学是以形态结构元素为基础对图像进行分析的数学工具，它的基本思想是用具有一定形态的结构元素去量度和提取图像中的对应形状，以达到对图像分析和识别的目的。数学形态学的基础和所用语言是集合论，它的应用可以简化图像数据，保持它们的基本形状特性，并除去不相干的结构，使其具有天然的并行实现的结构。数学形态学的基本运算有膨胀、腐蚀、开启和闭合。基于这些基本运算还可以推导和组合成各种数学形态学的算法。利用数学形态学开闭运算和混合滤波，根据目标的形状选用算法中的探针，可以取得较好的滤波去噪和目标分割的效果16。14本文的主要工作粒子群优化算法由于简单且收敛速度快，目前已在诸多领域得到成功的应用。研究如何选取控制参数，以及将粒子群改进算法应用于基于阈值法的图像分割中是本文研究的主要内容。本文研究的主要工作如下粒子群优化算法和许多其它优化算法一样，也存在一些控制参数，主要是指惯性权重，如何选取这些参数，对提高算法的收敛速度和寻优精度至关重要。特别是对于一些复杂的优化问题，它们往往要求算法的运算复杂度不能太大，算法迭代次数尽可能少，但目前许多改进的粒子群优化算法，其算法的理解复杂度和实现复杂度往往较高，从而对算法的工程应用造成了较大的障碍。针对这种情况，本文在对粒子群优化算法特性分析的基础上，研究一种不显著增加算法理解复杂度和实现复杂度为前提的，能提高算法的收敛速度同时增强算法的全局搜索能力的惯性权重动态调整方案，提出了一种随迭代次数变化而动态调整惯性权重的粒子群优化算法，该算法由进化速度因子和聚集程度因子共同确定并动态调整粒子速度更新公式中的惯性权重。当算法陷入局部最优时，也就是当群体最近的迭代中适应度几乎没有改变时，将根据适应度大小复制较好的粒子去取代较差的粒子，重新组合成一个较优的粒子群继续优化进程。为了评价改进后的粒子群优化算法的性能，本文选取了一些经典的标准测试函数进行了大量的实验，并同LDWPSO算法和BINJIAO等人提出的IPSO算法进行了比较。通过对不同测试函数的仿真实验表明本文改进的粒子群优化算法显著地提高了粒子群优化算法的收敛速度和全局搜索能力。由于图像分割对实时性要求很第一章绪论7高，如在直方图呈多峰的复杂图像中采用穷举法逐个寻找多个阈值的最佳组合来对图像进行分割，时间上将是无法忍受的。因此，快速又准确地搜索到用来分割图像的最佳多阈值组合将是问题的难点。然而，PSO算法对求解此类问题有明显的优势，它不仅计算简单而且有较好的全局寻优能力，因此本文尝试将改进算法应用到基于信息熵的多阈值图像分割中，通过对两幅复杂多峰的基准图像进行测试，并同其他学者最近文献中算法在同等条件下作了比较。实验表明，改进的PSO算法能够快速准确地搜索到分割的多阈值组合，获得较好的分割结果。15本文的组织结构全文共分为五章，各章内容安排如下第一章为绪论，对粒子群优化算法的研究现状和图像分割方法进行了概述。第二章粒子群优化算法，主要介绍了标准粒子群优化算法的基本原理、数学描述、算法流程、算法参数和算法面临的问题以及算法的发展等。第三章动态改变惯性权重的粒子群优化算法，对本文提出的改进粒子群优化算法进行了详细的介绍，并同其他学者的一些改进算法在求解函数优化问题上作了比较，通过仿真实验证明了本文算法的有效性。第四章DCIWPSO算法在多阈值图像分割中的应用，主要将本文改进算法应用到多阈值图像分割中，通过与其它改进算法对相同两幅基准图像进行测试比较，取得了较好的分割效果，进一步证明了本文算法的有效性。第五章全文总结与展望，对全文作了一个简单的总结，以及粒子群优化算法下一步的研究工作做了简单的展望。第二章粒子群优化算法8第二章粒子群优化算法粒子群优化算法是一种基于群体的随机优化技术。与其它基于群体的进化算法相比，它们均初始化为一组随机解，通过迭代搜寻最优解。不同的是进化计算遵循适者生存原则，而PSO算法模拟社会。将每个可能产生的解表述为群中的一个微粒，每个微粒都具有自己的位置向量和速度向量，以及一个由目标函数决定的适应度。所有微粒在搜索空间中以一定速度飞行，通过追随当前搜索到的最优值来寻找全局最优值。21粒子群优化算法的基本原理粒子群优化算法起源于对一个简化社会模型的仿真。它是受鸟群群体运动行为方式启发而提出的一种具有代表性的集群智能方法。研究者发现鸟群在飞行过程中经常会突然改变方向、散开、聚集，其行为通常不可预测，但其整体总能保持一致性，个体与个体间也保持着最适宜的距离。通过对类似生物群体的行为的研究，发现生物群体中存在着一种社会信息共享机制，它为群体的进化提供了一种优势，这也是PSO算法形成的基础。与基于达尔文“适者生存、优胜劣汰”进化思想的遗传算法不同的是，粒子群优化算法是通过个体之间的协作来寻找最优解，它利用了生物群体中信息共享会产生进化优势的思想。假设这样一个场景一群鸟在随机搜寻食物。在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，但是它们知道当前自己的位置离食物还有多远。那么找到食物的最优策略是什么呢最简单、有效的方法就是搜寻目前离食物最近的鸟的周围区域。PSO算法就是从这种模型中得到启发并用于求解优化问题。PSO算法中，每个优化问题的潜在解都可以想象D维搜索空间上的一个点，我们称之为“粒子”PARTICLE。粒子在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整。所有的粒子都有一个被优化的函数决定的适应度值FITNESSVALUE。在每一次迭代中，粒子都通过跟踪两个“极值”来更新自己第一个就是粒子本身到目前为止发现的最好位置PARTICLEBEST,记为PBEST，叫做个体极值点，这个可以看作是粒子自身的飞行经验；除此之外，全局版PSO的另一个极值点就是到目前为止整个群体中所有粒子发现的最好位置GLOBALBEST,记为GBEST,称为全局极值点。在局部版PSO不用整个种群而是以一部分粒子作为粒子的邻居，因此局部版PSO的另一个极值点就是所有邻居中发现的最好位置LOCALBEST,记为LBEST,称为局部极值点。GBEST和LBEST都可以看作是粒子的同伴的经验。每个粒子使用下列信息决定自己下一步的飞行1当前位置；2当前速度；3当前位置与自己最好位置之间的距离；4当前位置与群体最好位置之间的距离。优化搜索正是在由这样一群随机初始化形成的粒子而组成的一个种群，以迭代的方式进行的。第二章粒子群优化算法922粒子群优化算法的数学描述设群体搜索空间为D维，粒子群中粒子总数为N。其中第I个粒子位置表示为IDIIIXXXX,21，它经历过的最好位置记为IDIIIPPPP,21，或称为IPBEST。群体所有粒子经历过的最好位置的索引号用符号G表示，即GBEST。粒子I的速度用IDIIIVVVV,21表示。在标准的PSO算法中，每个粒子的速度和位置按如下公式进行更新17TIDDTIDTIDTIDTIDXGBESTRCXPBESTRCVV221112111TIDTIDTIDVXX22DDNI1,12321式的第一部分为粒子先前的速度乘一个权值进行加速，表示粒子对当前自身运动状态的信任，依据自身的速度进行惯性运动。其中，为惯性权重INERTIAWEIGHT，它反映了粒子过去的运动状态对当前行为的影响，较大的可以加强算法的全局搜索能力，而较小的能加强局部搜索能力4；第二部分为“认知”部分，表示粒子本身的思考，即一个得到加强的随机行为在将来的出现几率增大，从而实现一个增强学习过程；第三部分为“社会”部分，表示粒子间的信息共享与相互合作。“社会”部分可解释为粒子本身是被其他粒子所模仿，即作为一个种群中粒子运动的参考。1C，2C为正常数，称为加速常数ACCELERATIONCONSTANTS，分别调节受群体认识和个体认知的影响程度，即向全局最好粒子和个体最好粒子方向飞行的最大步长，若太小，则粒子可能远离目标区域，若太大，则会导致突然向目标区域飞去，或飞过目标区域18；1R和2R为两个在1,0范围内的随机数。此外，为了防止粒子远离搜索空间，它们第D维的位置限制在DDXXMAX,MAX区间内，速度限制在DDVVMAX,MAX区间内，其中DVMAX表示粒子第D维的最大飞行速度，DXMAX表示粒子第D维搜索空间的边界值，迭代过程中如位置和速度超过边界范围则取边界值。23粒子群优化算法的基本步骤和流程231PSO算法的基本步骤粒子群优化算法的主要步骤描述如下1初始化粒子群，设定加速常数1C和2C，最大迭代代数，将当前迭代代数置为T1，并对其中每个粒子，随机产生其初始位置和速度；2计算每个粒子的适应度值；3对每个粒子将其适应度值与其所经历过的最好位置PBEST作比较，如果它的新位置更好，那么将其作为它已知的最好位置PBEST；第二章粒子群优化算法104对每个粒子将其适应度值与整个粒子群所经历过的最好位置GBEST作比较，如果这个位置比GBEST好，则设置GBEST为当前这个位置；5按照公式21、22更新每个粒子的速度和位置；6判断终止条件，若满足，则终止寻优；否则，如果没有达到结束条件，让TT1，转到2。终止条件为达到最大迭代次数或评价值小于给定精度。232PSO算法的流程根据基本粒子群算法的主要步骤，可以得出其流程图，如图21。否否是非功过否是是是图21PSO算法流程输出GBEST初始化粒子的速度和位置计算粒子适应度当前位置是否优于PBEST置当前位置为PBEST当前位置是否优于GBEST置当前位置为GBEST根据公式21和22更新粒子的速度和位置是否满足结束条件第二章粒子群优化算法1124粒子群优化算法参数设置粒子群算法同遗传算法类似,是一种基于迭代的优化工具,初始化为一组随机解,通过迭代搜寻最优值，但并没有遗传算法用的交叉以及变异，而是粒子在解空间追随最优的粒子进行搜索,不能保证能找到最优解。应用PSO算法解决优化问题的过程中有两个重要的步骤问题解的编码和适应度函数，PSO算法的一个优势就是采用实数编码，不需要像遗传算法一样是二进制编码（如对问题232221XXXXF的求解，粒子可以直接编码为,321XXX,而适应度函数就是XF），然后就可以利用前面的过程去寻优。这个寻优过程是一个迭代过程，中止条件一般为设置达到的最大迭次次数或者最小误差。PSO算法一个最大优点就是不需要调节太多的参数,但是算法中的少数几个参数却直接影响着算法的性能以及收敛性，下面是PSO算法中的一些参数的作用以及经验设置1粒子数目一般取2040。其实对于大多数问题来说10个粒子已经足够可以取得很好的结果,不过对于比较难的问题或者特殊类别的问题,粒子数可以取到100或200。另外，粒子数目越多，算法搜索的空间范围就越大，也就更容易发现全局最优解。当然，算法运行的时间也越长。2粒子的长度这是由优化问题决定,就是问题解的长度。3粒子的范围由优化问题决定,每一维可设定不同的范围。4粒子最大速率粒子最大速率决定粒子在一个循环中最大的移动距离,通常设定为粒子的范围宽度,例如，上面的例子中,粒子,321XXX，1X属于10,10,那么粒子最大速率的大小就是20。5加速因子1C和2C通常等于2。但在一些文献中也有其他的取值,但是一般以1C等于2C并且范围在0到4之间。6终止条件最大迭代次数以及最小误差要求，终止条件由具体的问题确定。7惯性权重W控制着粒子前一次迭代速度对当前迭代速度的影响，如果W较大，则影响力较大，能够搜索以前所未能达到的区域，整个算法的全局搜索能力加强，有利于跳出局部极小点；而W值较小，则前一动量项的影响较小，主要是在当前解的附近搜索，局部搜索能力较强，有利于算法收敛。8适应度函数PSO算法的适应度函数选择比较简单，通常可以直接把目标函数作为适应度函数。当然，也可以对目标函数进行变换，变换方法可以借鉴遗传算法中的适应度函数变换方法。25粒子群优化算法面临的问题粒子群优化算法的应用已经扩展到很多领域，从最初的复杂多峰非线性函数的优化、多目标优化等传统问题，到电力系统的分析，动态系统的跟踪与优化、神经网络权值的训练并将其用于复杂系统的建模，图像分割的阈值选取问题等等。第二章粒子群优化算法12虽然PSO算法已经在多个领域被有效应用，但其发展历史尚短，还存在很多问题。现将其总结如下1粒子群优化算法是一种概率算法，缺乏系统化、规范化的理论基础，从数学上对于它们的正确性与可靠性的证明还比较困难，所做的工作也比较少，特别是全局收敛性的研究方面。将PSO算法的粒子轨迹由确定性转化为随机性仍然是一个艰巨的课题，这关系到PSO算法收敛性、参数选取等关键问题。2对于具体的实际问题而言，设计算法时，对算法搜索的效率和收敛的全局性之间要作某种平衡，这种平衡很大程度上是根据经验以算法参数的形式给出的，如何在理论上上给出准则，需要对算法进行进一步研究。3粒子群优化算法应用于高维复杂问题优化时，往往会遇到早熟收敛的问题，也就是种群在还没有找到全局最优点时已经聚集到一点停滞不动。这些早熟收敛点，有可能是局部极小点，也有可能是局部极小点邻域的一个点。换言之，早熟收敛并不能保证算法收敛到局部极小点。因而，对算法早熟收敛行为的研究可为算法的进一步改进奠定基础。4粒子群优化算法在拉近或进入最优点区域时的收敛速度比较缓慢。实际上对粒子群优化算法的研究发现，粒子群优化算法早期收敛速度较快，但到寻优的后期，其结果改进则不理想。这主要归因于算法收敛到局部极小，缺乏有效的机制使算法逃离极小点。26粒子群优化算法的发展粒子群算法是一种随机的、并行的优化算法，它不要求被优化函数具有可微、可导、连续等性质，它的优点在于收敛速度快、设置参数少，简单易实现，因此，它受到许多学者的重视和研究。尽管PSO算法收敛速度快，简单易实现，但目前它仍然面临着一些比较困难的问题。所以研究者们针对各种不同的应用问题对基本PSO进行了改进，总结如下261基于惯性因子的PSO算法对于不同的问题，如何确定搜索过程中的全局搜索能力与局部搜索能力的比例关系，对于算法的成功起着至关重要的作用。为此，YUHUISHI4提出了带有惯性权重的改进PSO算法。其进化方程为IDGDIDIDIDIDXPRCXPRCVV221124式中0，称为惯性因子。后来SHI等人又提出了一种随着迭代次数的增加，惯性权重线性递减的方法称为LDWPSO算法5，从而使得算法在初期具有较强的全局收敛能力，而晚期具有较强的局部收敛能力，一定程度上提高了算法的性能。惯性权重满足5090MAXNUMBERTT25其中，MAXNUMBER为设定的最大迭代次数，T为当前迭代次数，惯性权重是当前迭代次数第二章粒子群优化算法13的函数，可将初始化为09，随着迭代次数的增加线性递减到04或更小。文献5利用此方法对4个测试函数进行测试，均取得了很好的效果。对于惯性权重来说，对于不同的问题，其每一代所需要的比例关系并不相同，这样，线性递减关系只对某些问题有效，对于其他问题而言显然不是最佳的。为此，2001年，SHI等人又提出了基于模糊系统的惯性因子的动态调整算法6,单峰函数的处理中取得了良好的效果，但在解决多峰函数问题时，却容易陷入局部最优，且实现也比较困难。另外在2004年，陈震亦提出根据适应度大小对粒子群进行模糊分类，把粒子群分为K个子群；不同的子群使用不同的惯性权值KW，适应度高的子群，使用较大权值；反之，使用较小惯性权值，这种修改一定程度上加快了算法的收敛速度，同时使算法具有跳出局部最优的能力。262自适应PSO算法惯性因子对优化性能的影响表明较大的值有利于跳出局部极小点，而较小的值有利于算法收敛，因此提出了自适应调整的策略，即随着迭代的进行，线性减小的值，然而线性减小只对某些问题有效，为此进一步发展了用模糊规则动态地修改的值6，即需要二个输入、一个输出参数的模糊推理机来动态地修改惯性因子。这二个输入参数分别是当前种群最优性能指标THECURRENTBESTPERFORMANCEEVALUATION,简称CBPE和当前的惯性权重，而输出参数是的调节量。CBPE是PSO算法迄今为止发现的最好候选解的性能测度。CBPE可以有不同的定义方法，但是一般CBPE可以定义为最好候选解的适应度。假设所优化的问题为求解最小值的问题，则NCBPE可用下式计算MINMAXMINCBPECBPECBPECBPENCBPE26其中，MAXCBPE和MINCBPE分别是CBPE的上下限值。模糊推理机的输入、输出的论域定义为三种状态低、中和高，相应的模糊隶属度函数分别是LEFTTRIANGLE,TRIANGLE,RIGHTTRIANGLE,具体定义如下LEFTTRIANGLE的定义CC211此算法流程大体与标准PSO算法一样。通常将设为41，则K由211计算得0729。在算法早期的实验和应用中，建议当采用收敛因子模型时不再限制最大速度MAXV，但后来研究发现设定最大速度限制可以提高算法的性能，因此将MAXV设置为一个极大值如100000。后来的研究再次表明将其限定为MAXX（即每个粒子在每一维上位置的允许的变化范围）可以取得更好的优化结果。264基于遗传思想的PSO算法利用选择的PSO算法。在一般粒子群算法中，每个粒子最优位置的确定相当于隐含的选择机制。因此，ANGELINE将选择算子引入PSO中19，将每个粒子适应度按从大到小的顺序进行排列，选择粒子群中适应度较大的那一半个体，并对他们进行复制，取代群体中第二章粒子群优化算法15适应度较小的那一半个体，组合成一个新的粒子群继续进行迭代，以保证每次迭代的粒子群都具有较好的性能，仿真结果表明这种算法对某些测试函数具有优越性。借鉴杂交的PSO算法。ANGELINE提出了杂交粒子群算法20，粒子被赋予一个杂交概率，这个杂交概率是用户确定的。在每次迭代中，依据杂交概率选取指定数量的粒子随机地两两杂交，生成更优秀的粒子。LOVBJERG等人10的研究结果表明，应用繁殖算子的PSO在某些多峰函数中有更好的执行效率。265协同PSO算法所谓协同进化，是指将解空间中的群体划分为若干子群体，每个子群体代表求解问题的一个子目标，所有子群体在独立进化的同时，基于信息迁移与知识共享，共同进化。文献131