基于遗传算法的多边形逼近3D数字曲线.pdf

《基于遗传算法的多边形逼近3D数字曲线.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第l6卷第4期计算机辅助设计与图形学学报Vol.l6，No.42004年4月JOURNALOFCOMPUTER-AIDEDDESIGNSCOMPUTERGRAPHICSApr.，2004!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!基于遗传算法的多边形逼近3D数字曲线茹少峰周明全耿国华（西北大学计算机科学系西安7l0069）摘要首先对3D数字曲线进行简单的数据压缩.通过对该曲线上的点列进行二进制编码定义来表示数字曲线的染色体.

2、二进制串中的每一个位称为基因，每一个逼近多边形和染色体形成l-l映射.目标函数使给定曲线和逼近多边形之间的均方差最小.构造了解决该问题的选择、交叉、变异三个算子.所得最优染色体中基因值为l的基因对应数字曲线的分界点.实验结果表明，该方法能够得到精确的逼近结果.关键词多边形逼近；遗传算法；染色体；均方差中图法分类号TP39l.72PolygonalApproximationof3DDigitizedcurvesusingGeneticAlgorithmsRuShaofengZhouMingCuanGengG

3、uohua（DePartmentofComPuterscience，Northuestunioersity，Xi’an7l0069）AbstractAsimpledatareductionisfirstappliedtothedigitizedcurve.ChromosomesaredefinedbyencodingthepointseCuenceintobinarystringstorepresentthedigitizedcurve.Eachbitofbinarystringsiscalledagen

4、e.EachpolygonalapproximationismappedtoauniCuebinarystring.TheobjectionfunctionisdefinedasthemeansCuareerrorsbetweenthegivendigitizedcurveandtheapproximatedpolygonal.Threegeneticoperators，namelyselection，crossoverandmutation，areconstructedtosolvetheproblem

5、.Pointsof3Ddigitizedcurvecorrespondingtogenesofachromosome，eCualtols，aredemarcationones.Experimentalresultsshowthatthisapproachcangetmoreaccurateresultofapproximation.Keywordspolygonalapproximation；geneticalgorithms；chromosome；meansCuareerror种方式：假设得到的初始轮廓

6、线是由n个带有噪声1引言的点组成，（l）给定逼近多边形的顶点数目m，在n个初始点中找m个顶点，使得由这m个顶点组成的物体轮廓线的表示在图像处理、模式识别、计算多边形和初始轮廓线之间的误差范数最小；（2）给定机视觉等领域是一个重要的研究课题，在不同的分逼近误差!，找最少顶点的多边形使得其和初始轮廓辨率下，多边形逼近到初始的轮廓是一种最简单且线的均方差之和不超过!.本文研究第一种方式.常用的表示轮廓线方法.优化的多边形逼近不仅可近20年来，许多学者对于多边形逼近这一课题以压缩表示初始轮廓线的数据，而且还可以保

7、持初做了大量深入的研究，提出了许多算法.Sklansky始轮廓线的重要信息，这样的多边形逼近一般有两等［l］提出了一个通过最小多边形周长决定多边形原稿收到日期：2003-03-2l；修改稿收到日期：2003-ll-04.本课题得到国家自然科学基金（6027l032）和陕西省教育厅专项基金（03Jkl55）资助.茹少峰，男，l962年生，博士研究生，副教授，主要研究方向为数字图像处理、科学计算可视化.周明全，男，l957年生，博士，教授，博士生导师，主要研究方向为计算机图形学、数字图像处理、科学计算可视化.

8、耿国华，女，l955年生，博士，教授，博士生导师，主要研究方向为智能信息处理、算法分析与设计.504计算机辅助设计与图形学学报2004年的顶点的算法；Sklansky等［2］还提出了一个快速的m，使得Pm由初始数字曲线7个点P，i=1，⋯，7Pi扫描算法，该算法用分段的线性逼近到平面数字曲中的m个点组成，且逼近多边形和给定曲线之间的线，目标函数使从轮廓线上的点到多边形边上的最距离均方差最小.大距离最小；Pavlidis［3］应