资源描述：
《模拟退火算法在三维重建问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2001年4月西北大学学报(自然科学版)Apr.2001第31卷第2期JournalofNorthwestUniversity(NaturalScienceEdition)Vol.31No.2模拟退火算法在三维重建问题中的应用孙朝晖,周明全,耿国华(西北大学计算机科学系,陕西西安710069)摘要:讨论了目前常用的三维重建的方法,针对这些方法的局限性,提出了一种解决此类问题的方法,即将模拟退火算法应用在三维重建中。实践证明,这种方法是有效的,并且对解决其他类似问题具有一定的启发作用。关键词:三维重建;模拟退火算法;颅骨面貌复原系统中图分类号:TP393文献标识码:A文章编号:10
2、00-274Ⅹ(2001)02-0105-03重建是计算机视觉、模式识别及可视化技术等Fuchs提出了表面积最小法,也就是将有向图中弧领域的经典研究主题。重建的任务就是要从提取到的权置为对应基本三角片的面积。这两种方法均属的采样数据中恢复物体的三维结构,即物体的原型。于全局最优的表面重构方法,计算量较大,于是一些[6]在国家“九五”重点科技攻关项目“计算机辅助的颅作者提出了采用局部路径的判定方法,即先选择骨面貌原复系统”中,三维重建是一个重要问题。所轮廓线上两点构成初始连接边,然后每次选使某种[1]谓计算机辅助颅骨面貌复原,就是根据通过CT度量最优的两点进行连接,最短对角线法就是
3、和核磁共振成像技术提取到的颅骨采样数据,用计Christiansen等提出的以连接边边长最小为原则的算机进行各种处理,最终产生符合原来颅骨的面部方法。图像。但是,上述的每种方法均有局限性,对每种方法计算机辅助的颅骨面貌复原技术是目前国际研都可以找出反例,使得最终结果并非我们所期望的究的热点和难点,因而对三维重建方法的研究就具解,而且,目前的任何目标函数都难以保证在所有情有非常重要的意义。重建三维物体的方法有许多况下都能得到期望解。[2]种,如果从重建过程处理的基本单元的级别来区因此,我们应该寻求一种更好的方法来解决此分,可以分成两大类:切片级重建和体素级重建。切问题。模拟退火算法
4、SA(simulatedannealing)是一[3]片级重建方法是从一组平面轮廓重构出通过这些种求解优化问题的通用算法,它可以通过接受一部[4]轮廓的曲面,而体素级重建方法要首先确定物体分恶劣解而跳出局部最小点的“陷阱”,最终达到全表面在每个体素内的小面片,然后将这些小面片连局最优。起来就构成了物体的表面。比较常用的切片级重建方法为三角面片法,对任意相邻两层等值线上的点1模拟退火算法简介所围成的带状空间区域用三角面元来逼近表示。由于重建表面的构造并不惟一,需要从中选择与物体Metropolis在1953年的时候就提出了一种能[7]表面接近的解,比较普遍的做法是将其转化为组合有效
5、模拟退火过程的算法,该算法是一种随机采优化问题,许多人对此进行了探讨,分别提出了各自样的方法。其大致过程如下:的目标函数和相应的重建算法。按其实现方式,有体先给定粒子相对位置的初始p,作为固体的当[5]积最大法,这是Keppel提出的重建表面所包围的前状态,此状态下的能量为Ep,接着随机选取某一体积为最大为目标函数,求取最佳逼近。与此类似,个粒子,使其位置产生微小的移动,得到一个新的状收稿日期:1999-11-26基金项目:国家“九五”攻关资助项目(95-919-01-03)作者简介:孙朝晖(1969-),女,山东莒南人,西北大学讲师,硕士,从事图形图像处理、数据库、网络和人工智
6、能研究。—106—西北大学学报(自然科学版)第31卷态q,新状态的能量为Eq,这两个状态的能量差为〈Vij,V〉称为水平弧,〈Vij,Vi+1j〉称为垂直弧,任ij+1E=Ep-Eq,新状态q能被接受的概率为何基本三角形的集合可看成是G的一个子图,如果1,E<0;S是G的一个子图,V是G中的顶点,有如下定义:prob,(pq)=-Eet,E≥0。indegrees(V)是S的入度,即S中进入V的弧数;状态q能否取代p,按如下规则判断:outdegrees(V)是S的出度,即S中离开V的弧数。ifprobt(pq)>rand(0,1),则q取代p,否则,那么,可接受
7、表面可描述为:G中的任两行间S有不接受新状态q。且只有一条垂直弧,G中的任两列间S有且只有一退火过程与组合优化问题之间存在着类似性,条水平弧;G中的任意一个顶点Vij,要么indegre-所以人们把Metropolis算法引入到优化过程中来,es(Vij)=outdegrees(Vij)=0,要么indegrees(Vij)于是得到了一种对Metropolis算法进行迭代的组合>0且outdegrees(Vij)>0。优化算法。这种算法模拟固体退火过程,所以称之为“模拟退火算
