应用遗传算法的平面曲线最优多边形拟合

应用遗传算法的平面曲线最优多边形拟合 Z, 4({ 应用遗传算法的平面曲线最优多边形拟合 窆墨至吐重顾伟康,rPI.L} 浙江大学信电系信息与智能系统研究所(杭州310o27) 0 摘要平面曲线的多边形拟合是模式识别和计算机视觉研究中非常重要的一类算法.该文提出了一种利用遗传 算法(GA)的最优多边形拟寺算法:由线的分段拟合操作被方位地编码为基因串.一种基于面积和模型简单度的全 局拟台度量用作GA的适值函数.该文算法可姒在无需事先给定分段数目厦最太允许偏的奈件下自动确定这 些参量进行多边彤拟寺.文中给出的妾验结果 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明了算法的可行性和有效性= OptimalPolygonalApproximationofPhnarCurveUsingGe- neticAlgorithm LiHongdongYeXiuqingGuWeikang Abstract:Pulygonalapproximationofpl&/1atcI]/aeeisaneffe*:tiverep re~ntationforshapeanalysisandpattern recog~itionThispaperprovidesanPwmethodforoptimalpolygonalapproximationthattakingusageofgenetic algorithms(GAs)Aglobalureoftheclosenesshelweenthepdygonaltothecu1%,eacBa吕thefitnessfunc— tinnofGAs.ByasimpleanddirectcodingofchH)m? e.theoptimalsolutionisthenobwined.wherenoini— nalarguments(sucha8thenumberofverticesore/T~rtolerance)needtobeven.s0meexperimentalresultsthat demons/ralethepracticahfoofourmethodarealsosho,*ninthispaper. 1引言 平面曲线的乏望理型盒培模式识别和计算机视觉研究 中非常莺要的一个研究课题.周为分段的多边形拟合提供 r平面曲线紧致的描述,达到了符号特征提取和信息压缩 的目的. 目前,研究者尤麒感兴趣的是基于全局拟台度量的蛙 优多边形拟合.寻找某平面曲线一个唯一的最佳的多边形 描述在模式识别及计算机视觉研究中均有重要的实用价 值.比如用于文字识别中的轮廓匹配,工程图纸自动矢量化 和录入,计算机动画变形操作,计算机视觉运动估计中的寻 求最优对应等 所谓”最优”多边形拟台,其具体古义有如下两种提法: 一 是在事先给定多边形结点数目的条件下,通过适当调整 结点的位置,使拟合的误差尽量小;另一种是给定拟台误差 限,在满足拟台误差小于限的前提下.确定多边形边数 及结点位置,实现最优化拟台 文献[I一81中发展r多种多边形拟合的算法.Duda和 Hart最早提出了在满足局部逼近误差上限条件下进行逐段 细分的SPLIT方法.随后Pavlids和Horowltz提出了满足 容差条件下递归运用分裂和合并操作的SPLIT—MERGE算 法:他们还证明了用泼法求得的多边结点数目不会太于最 优值的两倍.Davis根据K一曲率,发展了先确定角点位置, 再连成多边形的算法:近年来,Dunha道了一种最优拟 台算法,该算法能够在给定起始结点和终止结点位置及最 长的边长条件下,运用动态规划算法最优地确定结点数目 及位置.lmai等人在1992年推广丁Dumham的算法,并采 用宽度优先搜索(BVS)的方法求解.Sato1992年利用动态 规划进行给定结点数日的最优逼近,用所谓”发现最长分 支”法确定结,该算法复杂度较高一RayI等在1993年提出 4219995计算机工程与应用 r一种最优算法,该算法用L1一Norm误差束度量逼近程 度,可以在线性时间内完成操作J.S.WuI11993年给出了几 种用面积差异作指标的算法,在给定误差上限情况下,采用 贪婪(greedy)吃进的搜索策略,能确定最小的边数:A Pikaz和I.DinstelnII于1995年提出一种新算法,用弧弦度 量拟台情况,用BFS搜索最短路径确定最优结点位置,取 得了较好的结果.P.CChung等在1994年进行了应用竞 争Hopfield厢(CHNN)进行多边形拟台的尝试,他们用弧弦 距没计了一个能量函数,在给定结点数目前提下,算法可以 正确地得到所需解 分析现有的多边形拟合算法.不难发现其中大多具有 以下的特点: (1)算法都需要人工事先确定若干参数.比如多边形结 数目,最大允许误差等参数,而确定这些参数需要通过人 1_干预运用经验,及多次反复尝试. (2)算法大多只利用局部的一致性度量,比如弦弧距 最长线段,K曲率等,而非全局的最优拟台,因而只能称作 “准摄优”算法: (3)算法基奉上用串行迭代过程确定最优解,收敛缓 慢,而且解的结果不唯一,因其强烈地依赖于起始结点的确 定,这对模式识别是不利的 珐文提出一种应用于GA的简单有效的最优多边形拟 合算法.拟合问题被简单直接地编码成染色体串,一种基于 面积差异和模型复杂度的全局一致性度量设计为适值函 数,通过染色体的交叉变异等算子操作,利用遗传算法的 并行搜索及优化能力,在无需事先给定结点数目及无需确 定起始结点条件下,可自动进行结点数目及位置的确定,实 现了最优化拟台.文中给出试验结果,证明了算法的有效性 和实用性 2用于最优多边形拟合的遗传算法 2.1遗传算法简介 遗传算法IGA]是一种模仿自然选择与进化的基于种 群数目的随机搜索算法.3亿年地球生命进化历程为其提 供了可行性的保证.目前GA已广泛应用于诸如组台优化, 最优搜索等各种领域.目前在模式识别,计算机视觉学科也 有大量的应用报i苴 GA的主要思想是先将待优化的问题用染色体串表达 结构,每串对应一个目标估值,通过遗传算子的作用产生大 量进化了的候选结构,优选适值高的个体进行下一轮的进 化,而最终保留下来的适值最高的个体,正对应于问题的最 优解. 对染色体串进行操作的主要遗传算子包括复制 (COPY),变异(Mutation),交叉(CrossOre0,分别如图1所 示.Holland在1975年提出的的模式型式理论为GA的收 敛提供了理论依据. GA不同于通常的最优搜索算法,主要体现在以下几方 面: fI)GA具有潜在并行性,能够在解空间上并行扩展,可 保证快速寻到最优解. f2)GA是一种随机搜索算法. [3)GA可同时操作一组解结构,因而可有敏避免陷人局 部极小的问题. 圈1主要遗传算子示意图 关于遗传算法原理算法和应用的更详细的讨论,请参 见D.Goldberg的着作. 2.2问题的基因串表达 应用遗传算法求解问题的关键在于寻找特定问题的 基因串编码表达.不同的表达方式对应不同的求解原理,导 致的收敛速度也不相同.该文针对多边形拟台提出一种直 接而简单的编码方法,介绍如下. 下面就重述一遍平面曲线的最优拟合问题并以闭合曲 线为例: 给定一条平面曲线,事先通过链码跟踪,形成一条长度 为N的码串s?,在s(N)中自动确定一条子串V(M),包括每 个元素的位置及M的数值,并且M小于N,如图2所示. 图2平面闭合曲线的编码串 拟合问题用符号表示如下: Input:平面曲线=sls2s3s4…sN OuIput:拟台多边形V(M):vlv2v3vM 要求满足:全局拟台误差最小 对于上问题,考虑最极端的情形.需要进行个节点 的筛选及每个节点位置的调整,才能达到最优意义上的拟 台,其搜索空问之大可想而知. 下面给出一种拟合问题的直接的基因串表述,可方便 运用遗传算法进行最优拟台. 对给定的平面曲线链码串:S(N)=sls2s3sN 首先,考虑到一般情况下,拟台出的多边形边数M(, 故可在s(N)均匀确定P个点,作为韧始基准点.并且要求满 足M<P<N.对于该不等式,可以事先对M的上限作出估计. 从而合理确定P的取值. 这样有子串V?取染色体串长度亦为其中每个元 素的内容取作各自相对于基准位置的偏移量等情况,如此 就可以方便地直接构造出拟台问题的解,举l例说明如下, 00.000000对应原始位置的基准申 I.3.-I.2-2.0.4.-I基准串适当偏移后的某个解. 由于P>M.为了在进化求解过程中丑三I三工三E!工 其中各节点位置分别为:{vl+3,v3,v4,2,v6+4,v8,1l, vi为初始基准位置. 2.3适值函数的选择 对于运用GA求解问题,仅具有台适的基因串表达还 不够,还必须有一个强有力的环境或条件约束,以保证该基 因串向着最有希望的方向进化.这可以通过设计问题特定 的遗传算子实现,不仅实现复杂,而且算法的通用性势必受 到限制=另外一种方法是通过定义恰当的适值函数,用不同 的函数值来奖惩不同表现的染色体串个体,起到控制进化 方向的作用. ofmode1)(I) 其中两项的含义分别如下: (1)所得拟台结果应在全局意义上最佳地逼近原曲线, 用公式(1)中第1项表示. 计算机工程与应用1999543 c2)所得多边形应最简单 公式(1)中第2项表示. 即能以最小的边数来逼近.用3,2实验结果 囤3公式c2]中符号吉义 系数用于折衷两部分的作用.而具体的要最小化的 适值函数公式为: fitncss:ITIin=zl— 其中s-表示每个多边形边与原曲线段问的面积差,经 求和后反映公式(1)中{modelfit.es~)部分,li为每边弦长, 式c2)中后一项反殃模型的简单程度.si,li的定义如图3所 示.由于曲线已用8方向链码量化,故上式中的si,li均可 用链码方法快速计算,整体适值函数的运算量也不大. 3算法实现与实验结果 3.1算法实现 为了验证该文算法,选用共享遗传算法软件GENESIS 作为试验平台,用C语言修改的Evaluation()函数为上节给 出的适值函数,即公式(2】.输入闭合平面曲线的x坐标 序列,首先进行8一方向链码跟踪,获得链码串s),然后在 串中确定长度为P的基准串v(P】,并 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 其位置数组.随 机产生初始的种群,其中染色体串中每个元素的取值为相 对各自基准点的偏移量.设定参数,运行GENESIS直到收 敛,输出收敛时对应的最优串.另外编制一个解码程序.用 于解释最优串的含义,输出拟台多边彤的边敛及各个结点 的位置,以图形显示.完整的GA最优多边形拟合算法实现 如图4. 图4算法藏程框图 441999.5计算机工程与应用 对算法进行仿真实验,获得了满意的效果.以下是部分 实验结果所采用的图象均为128xl28分辨率的二值固.获 得轮廓图后,用8一方向Freeman链码跟踪.事先人工指定染 色体串的初始长度和初始结点的基准位置.基准位置可以 均匀分布在一周上.每条染色体采用环状数据结构,用来反 映曲线的闭合性=初始个体用随机数产生,其中每个基因位 置的数值允许有?D的偏移=确定D的原则是不能偏移太 大,以防止邻接结点交叉现象的发生:并且注意保证在栏个 初始种群中每个基因位置的值都有成为”?”的可能,用以 表示该结点有可能在进化中被删除.初始种群的个体数目 确定在50~200之间. 进行遗传算子操作时采用两点式交叉运算,以加快进 化速度.在”复制”操作中引人一种称为Elitist的策略,目 的是在下一代中保留父代中适应性最好的个体,提高整体 适应性: 臼曰臼图5(正方形拟台结果 水图5(b】汉宇笔划轮廓拟台 图5fa)为一个正方形的拟台过程.初始染色体串长为 8,初始种群个体数目为50,经过2O0代的进化,从图中可 以看到真正的全局最优的结果被找到.图5{b)是对汉字 图形的笔划轮廓提取的实验,左边为输入的文字图象,事先 提取出两个封闭曲线的链码串,分别送入GA算法,右边是 得到的结果,可见对转折较大的图形,算法较好地反映了其 拟合情况.图5{c)是对一个小熊轮廓囝和非洲大陆地图的 拟合结果.初始串长分别为32和19,而结果分别 为18边形和11边形. 圈S(o)Re~ltsofBe盯&Africa 簖 4结束语 该文设计了一个应吊遗传算法的平面曲线最优多边彤 拟台算法.最优多边形的边数和点位置的确定是通过进 化优化一个给出的全局适值函数来实现的.该适值函数折 衷体现了逼近程艘和模型简单程度两方面的因素文中还 针对多边形拟合问题介绍了一种简单的染色捧串编码方 案.通过对不同类型图形的仿真实验,证明该文算法具有实 用性和有救性[定稿日期:1998年5月) 参考文献 lAPikaz.IDinsteinOplinra]Polygonal却p~ximatlon0fDi C?s.PR-199528(3):373—379 2.P.CChunga1.PolygonalApprt~ximationusingACompeti0ve H0eldNeuralNetworkPR一1994;27(11):1505—1512 33.Swuet.Newpalygomrlapp~xJnrationschmforobj~t shapeesemml?.PR一1993;26(4):471,4 4B.KRayDet髑【j【?ofop/Jmalpolygonalfromdigitalcur忡using LINorfI’PR—l993;26f41:505鲫 5.H.CLiu.M.D.StlnathCome.K.DeguchJRedpolygonalapproxi~fionfora nalysisand interpretationofplanarcontourfiguresCVPR1991 9DEGoldberg.GenetleAlgorithmsinSearchOptiizationand Weiley.1989 MachineLe~ingAddison— 10Jb盯0.Geneliealgorithmsprograt~dngEn…r『】encsIEEE Computer.1994:28—43 (上接33页) 试验开始以前将52个字符分成两组.每组26个,分 别进行训练.使每组的识别率达到100%.然后根据生成的 权向量w和V进行网络容错试验.试验中的样本采用训 练样本,分三种情况进行.首先对第一层与中间层的连接 权V进行试验,检测该层权向量的损伤程度对网络识别率 的影响..在该层权向量中随机地选择某些连接权,并将其 切断,即使它们的值变为0.然后利用修改以后的权,也就 是说用这组具有损伤的权向量和训练集内的样本模式对 网络的识别率进行测试,检测网络识别率与该层权损伤率 间的关系,然后恢复第一层的权值.用同样的方法对中间 层和输出层间的权向量w进行测试.并得到该层权向量 的损伤率与网络识别率的关系.最后进行综台试验,即不 分层次在整个网络的权向量中随机切断不同的权向量,并 测试网络的识别率与权向量损伤率的关系.在上的试验 中.为避免试验数据的偶然性,我们用两组不同的训筠;模式 对网络进行训练,每组分别训练3次,共得到6组权向量. 对每组投向量进行以上的试验.每种情况得到6种不同的 数据,然后求出平均值作为宴验结果. 4结果与分析 经过前面的实验,得到三种情况下权向量损伤率与网 络识别率的关系,见囤2.从这些关系曲线可以看出,三层 BP网络具有很好的容错能力.在第一种情况下,当输入层 与中间层权向量的损伤率达15%时对网络识别率并无影 响.而当权损伤率为25%时,网络识别率仍然达92.3%.当 权损伤率超过35%时,网络识别率则下降得很快.第二种 情况下,即改变中间层与输出层间权损伤率的情况下,当 权损伤章在3%以下时,网络识别率不受影响;当权损伤 率超过3%时.网络识别率开始下降.当权损伤率为15% 时.网络识别率为80%,而权损伤率超过20%时,网络识别 率下降得很快.而在综合情况下,整个网络权向量的损伤 率对网络识率的影响基本上界于前两种情况之间,即当 整个网络权向量损伤率为10%时,网络的识另?率不受影 响.在权损伤率在15%以下时,网络仍然有较好的识别率. 另外,为了实验中间层结点的数量与F回络冗余度的关 系,掩们把中间层结点扩大为70个.并对网络做了相同的 实验.从实验中可看出,中间结点的增加扩大了网络的 容错冗余度.另外,阈值的变化对网络的识别率也有较太 的影响: 120 蚤l00 80 曲 40 20 053.01520|b50j黉t摔 围2识别率与损伤率之间的关系 5小结 从以上的实验结果可以证明,BP神经网络具有较好 的容错能力.输出层权向量的损伤率对网络的识别率影响 较大,而中间层权向量的损伤率对网络的识别率影响较 小.当然我们的实验还具有一定的局限性,如网络的学习 样本不够多,即使如此,它仍然对BP网络的容错能力具有 很好的说明. 图2中a为第一层与第二层间权损伤率于识别率的 关系;b为第二层与第三层权问损伤率与识别率的关系;c 为综台识别率.(定稿日期1998年3月) 参考文献 1扬行峻,郑君里人工神经尉络高等教育出版杜,1992 2焦李成神经网络系统理论.西受电子科技大学出版 社,1992 3.靳蕃,范俊渡,谭永东神经网络与神经计算机原理应用 . 西南交通大学出版社,1991 4.PhilipsD.Wassenn~ tieeYork:VanNnRelnl~ld.1989 5.TartuaKhF0I】nd丑lic加ofNeural1%tworks,Addi?n_ WesI~PLlb【iingCompany,1990 6.Yoh-HanPao.AdaptivePatternRecoguizltior,andNeural Networks,Addls~n-WesleyPahlishthgCompanyt1990 计算机工程与应用1999545 园