基于遗传算法的散乱点云最小包围盒求解

《基于遗传算法的散乱点云最小包围盒求解》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2013年8月第39卷第8期北京航空航天大学学报JournalofBeijingUniversityofAeronauticsandAstronauticsAugust2013V01．39No．8基于遗传算法的散乱点云最小包围盒求解孙殿柱史阳刘华东李延瑞(山东理工大学机械工程学院，淄博255091)摘要：提出一种将遗传算法和0’Rourke算法相融合的最小包围盒求解算法，以O’Rourke算法中的体积函数作为遗传算法的目标函数，采用遗传算子指导解的搜索方向，通过新种群的迭代生成过程缩小搜索区域与体积误差，种群迭代结束后对最优个体解码获得最小包围盒．实验结果表明，该算法可在满足最小包围盒体积

2、精度的同时显著提高算法的运行效率，能够有效处理各种复杂散乱点云数据的最小包围盒快速求解问题．关键词：散乱点云；最小包围盒；遗传算法；体积函数中图分类号：TP391．72文献标识码：A文章编号：1001—5965(2013)08-0995-04SolutionofminimumboundingboxofscatteredpointsbasedongeneticalgorithmSunDianzhuShiYangLiuHuadongLiYanrui(SchoolofMechanicalEngineering，ShandongUniversityofTechnology，Zibo255091，C

3、hina)Abstract：AnalgorithmofminimumboundingboxcombininggeneticalgorithmwithO’Rourke’Salgo—rithmwasproposed，whichregardedthevolumefunctioninO’Rourke’Salgorithmastheobjectivefunctionandusedtheevolutionaryfactorstoguidethesearchingdirections．Throughtheprocessofthepopulation’Sit-erativegeneration，thisa

4、lgorithmnarrowedthesearchareaandthevolumeerror．Whentheiterativeprocesswasover，theminimumboundingboxwasobtainedbydecodingtheoptimalindividuals．Theexperimentalre-suitsshowthatthealgorithmcanimprovealgorithmicefficiencyandsatisfythevolumeaccuracysimultaneous-ly．Thealgorithmcandealwithsortsofproblemsr

5、elatedtominimumboundingboxfastsolvingofcomplexscatteredpointcloud．Keywords：scatteredpoints；minimumboundingbox；geneticalgorithm；volumefunction三维物体的最小包围盒在铸造模具分型、产品包装设计、碰撞检测、图像处理和模式识别等领域具有广泛的应用。。4；．目前，常见的三维物体最小包围盒求解算法主要包括O’Rourke算法。2、投影旋转法。列和主元分析法。4一。3类．O’Rourke算法是一种基于三维物体凸包的最小包围盒求解算法，该算法能够准确求解物体的最小包

6、围盒，时间复杂度为O(n3)．投影旋转法基于“长方体的3个互相垂直面，当且仅当其面积最小时，长方体体积最小”．将三维物体的轴向包围盒分别围绕3个坐标轴旋转，确定各面最小投影矩形获得最小包围盒．但是确定某个最小面积的矩形后，包围盒围绕其它轴旋转时会改变已确定投影矩形的边长，使矩形的面积改变，所以不能同时满足包围盒3个互相垂直面的面积最小条件．主元分析法利用协方差矩阵确定散乱点云的主元向量，将主元向量作为坐标轴求解散乱点云的轴向包围盒，但当散乱点云各维相关度较小时，该方法难以得到最优的主元向量，造成较大的误差．鉴于三维物体可以转化为散乱点云表示，本文结合O’Rourke收稿Et期：2012-0

7、8．16；网络出版时间：2013-04—1017：08网络出版地址：WWWcnki．net／kcms／detail／11．2625V．20130410．1708．002．html基金项目：国家自然科学基金资助项目(51075247)；山东省自然科学基金资助项目(ZR2010EM008)作者简介：孙殿柱(1956一)，男，山东烟台人，教授，dianzhus@sdut．edu．ca．996北京航空航天大学学报2013年算法能