您现在的位置:首页 > >

基于蚁群算法的双面文字碎片拼接复原

发布时间:

龙源期刊网 http://www.qikan.com.cn 基于蚁群算法的双面文字碎片拼接复原 作者:李艺颖 来源:《科技视界》2013 年第 28 期 【摘 要】对于来自于碎纸机的既横切又纵切的矩形双面文字碎片,我们采用了蚁群算法 进行全局的拼接。当碎片正反面均有文字时,这种情况相当于扩展了搜寻信息的广度,同时对 已匹配信息提出了正反面的约束条件。正反两面的求解则意味着问题从寻找单维度的局部最优 解转向三维向量域内全局最优解的获得,也就意味着问题从单纯的文字碎片的方向匹配转向寻 找最优化的全局匹配。通过实践证明,蚁群算法在双面文字碎片拼接上具有良好效果。 【关键词】蚁群算法;文字碎片;双面文字;碎片拼接 0 引言 对破碎文件拼接技术的研究是一个很有实用价值的研究课题,比如,对司法物证的复原、 历史文献修复及军事情报获取等。但传统拼接方法主要由人工完成,准确率虽高但效率很低; 而本文旨在利用计算机开发碎片文字的自动拼接技术,也就是从许多散乱的文字碎片中,借助 于计算机编程和少量人工干预,实现碎片拼接。另外,传统意义上都是研究对边缘不规则的碎 片的复原技术,即利用曲率和角度拼接碎片,而本文着重研究的是基于双面文字的边缘规则的 碎片复原,通过蚁群算法达到既保证准确率又提高效率的目的。 1 基于蚁群算法的碎片拼接模型 ACO(蚁群算法) 为了能够在对文字碎片拼接过程中寻找局部最优解的同时,又能够将全局的文件碎片匹配 关系最优化。我们决定使用基于全局最短路径搜寻的 ACO 算法。 蚁群算法(ant colony optimization, ACO):是一种用来在图中寻找优化路径的机率型算 法。它由 Marco Dorigo 于 1992 年在其博士论文中提出,灵感来源于蚂蚁在寻找食物过程中发 现路径的行为。蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质。 蚁群优化算法已应用于许多组合优化问题,包括蛋白质折叠或路由车辆的二次分配问题,很多 派生的方法已经应用于实变量动力学问题,随机问题,多目标并行的实现。它也被用于产生货 郎担问题的拟最优解。在图表动态变化的情况下解决相似问题时,他们相比模拟退火和遗传算 法方法有优势;蚁群算法可以连续运行并适应实时变化。第一蚁群优化算法被称为“蚂蚁系 统”,它旨在解决货郎担问题,目标是要找到一系列城市的最短遍历路线。总体算法相对简 单,它基于一组蚂蚁,每次只完成一次城市间的遍历。在每个阶段,蚂蚁根据一些规则选择从 一个城市移动到另一个:它必须访问每个城市一次;一个越远的城市被选中的机会越少(能见 度更低);在两个城市边际的一边形成的信息素越浓烈,这边被选择的概率越大;如果路程短 龙源期刊网 http://www.qikan.com.cn 的话,已经完成旅程的蚂蚁会在所有走过的路径上沉积更多信息素,每次迭代后,信息素轨迹 挥发。 2 双面文字碎片复原的实现 在详细研究蚁群算法后,我们借鉴其生物学意义对模型进行了抽象。如范围、环境、觅食 规则、移动规则、避障规则、信息素规则等,即我们使用蚁群算法解决问题要归纳以下信息: ●范围 生物学意义:蚂蚁观察到的范围是一个方格世界,蚂蚁有一个参数为速度半径(一般是 3),那么它能观察到的范围就是 3*3 个方格世界,并且能移动的距离也在这个范围之内。 模型抽象:在文字碎片拼接问题的解决模型即为拼接对象的集合。 ●环境 生物学意义:蚂蚁所在的环境是一个虚拟的世界,其中有*铮斜鸬穆煲希褂行畔 素,信息素有两种,一种是找到食物的蚂蚁洒下的食物信息素,一种是找到窝的蚂蚁洒下的窝 的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。 模型抽象:在文字碎片拼接问题的解决模型即为每张文字碎片身上所携带的特征向量组, 随着与它连接的图片的增加进行实时更新。 ●觅食规则 生物学意义:在每只蚂蚁能感知的范围内寻找是否有食物,如果有就直接过去。否则看是 否有信息素,并且比较在能感知的范围内哪一点的信息素最多,这样,它就朝信息素多的地方 走,并且每只蚂蚁都会以小概率犯错误,从而并不是往信息素最多的点移动。蚂蚁找窝的规则 和上面一样,只不过它对窝的信息素做出反应,而对食物信息素没反应。 模型抽象:在文字碎片拼接问题的解决模型即为每一个文字碎片携带的特征向量在进行两 两匹配时的空间标准欧氏距离,即转化后文字碎片之间的相似程度。 ●移动规则 生物学意义:每只蚂蚁都朝向信息素最多的方向移,并且,当周围没有信息素指引的时 候,蚂蚁会按照自己原来运动的方向惯性的运动下去,并且,在运动的方向有一个随机的小的 扰动。为了防止蚂蚁原地转圈,它会记住刚才走过了哪些点,如果发现要走的下一点已经在之 前走过了,它就会尽量避开。 龙源期刊网 http://www.qikan.com.cn 模型抽象:在文字碎片拼接问题的解决模型即为在寻得局部最优解之后不放回的随机组 合,以得到全局最优解的过程。 ●避障规则 生物学意义:如果蚂蚁要移动的方向有*锏沧。崴婊难≡窳硪桓龇较颍⑶矣 信息素指引的话,它会按照觅食的规则行为。 模型抽象:在文字碎片拼接问题的解决模型即为遇到一些特殊情况,例如出现非边界而具 有全白边的文字碎片时的处理规则。主要是停止拼接,进行人工干预。 ●信息素规则 生物学意义:每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多,并随着它走远的距 离,播撒的信息素越来越少。 模型抽象:在文字碎片拼接问题的解决模型即为在全局优化过程中,各个步骤说占据的权 重是不定的,每个步骤对全局的影响有特定的规则。初步认定为越往后的拼接相似度所占全局 优化的比重越大。 实现步骤: (1)初始化信息素强度信息即相似度,每一步连接所占的权重比,初始信息素浓度,起 始蚂蚁总数即初始拼接碎片和个数,遍历过程的步数,信息素浓度和禁忌表。 (2)启动蚂蚁,蚂蚁根据状态转移规则寻找下一节点即根据文字碎片间的连接关系寻找 局部最优解, 更新禁忌表。


热文推荐
猜你喜欢
友情链接: 医学资料大全 农林牧渔 幼儿教育心得 小学教育 中学 高中 职业教育 成人教育 大学资料 求职职场 职场文档 总结汇报