基于蚁群优化算法的碎纸拼接

J4 ›› 2011, Vol. 33 ›› Issue (7): 67-73.

基于蚁群优化算法的碎纸拼接

何鹏飞1,周宗潭2，胡德文2

(1.91701部队，山西阳泉 045233;2.国防科学技术大学机电工程与自动化学院，湖南长沙 410073)
(

收稿日期:2009-05-17 修回日期:2009-09-03 出版日期:2011-07-21 发布日期:2011-07-25
作者简介:何鹏飞(1985),男，陕西定边人，硕士，助理工程师,研究方向为模式识别。
基金资助:
教育部新世纪人才计划(NCET080147)；国家自然科学基金资助项目(60136018)

Reconstruction of the RippedUp Documents Based on Ant Colony Optimization

HE Pengfei1,ZHOU Zongtan2,HU Dewen2

1.Corps 91701,Yangquan 045233;
2.School of Mechatronics Engineering and Automation,
National University of Defense Technology,Changsha 410073,China)

Received:2009-05-17 Revised:2009-09-03 Online:2011-07-21 Published:2011-07-25

摘要/Abstract

摘要：

对于碎纸拼接问题，找到一个全局一致的最终解决方案是非常关键的。本文提出了一种基于蚁群优化算法（ACO）的全局拼接方法。首先运用基于ψs分析的局部匹配方法进行局部拼接，然后利用局部拼接产生的候选匹配对构建搜索图、信息素与节点相关联。在迭代过程中，利用候选匹配对之间的矛盾和由蚁群构建的全局拼接路径更新信息素：对于在迄今最优路径上的候选匹配对，人工蚂蚁释放信息素；而位于构建失败的路径上的候选匹配对的信息素以一定比例蒸发。候选匹配对的信息素最终向一定方向收敛。最后，根据信息素来筛选候选匹配对。实验证明了这种方法的有效性。

关键词: 碎纸拼接, 蚁群优化算法, 信息素更新

Abstract:

It is crucial to find a globally consistent solution for automatically reconstructing the rippedup documents.In this paper, we propose a global approach for reconstructing the rippedup documents based on Ant Colony Optimization (ACO). At first, partial matching is processed by using the ψs analsys method with a high matching accuracy. The searching graph is constructed according to the ambiguous candidate matches and the pheromone is associated with the node. These pheromones are iteratively updated using the conflict between the candidate matches and the global trace constructed by ants: the pheromone is deposited beside the cadidate matches which are on the bestsofar path, and the pheromone evaporates beside the cadidate matches which are on the failure path. These pheromones converge and the proper cadidate matches are chosen according to the pheromones iteratively updated. The method is proved by the experiments.

Key words: reconstruction of rippedup documents;ant colony optimization;pheromone updating

何鹏飞1,周宗潭2，胡德文2. 基于蚁群优化算法的碎纸拼接[J]. J4, 2011, 33(7): 67-73.

HE Pengfei1,ZHOU Zongtan2,HU Dewen2. Reconstruction of the RippedUp Documents Based on Ant Colony Optimization[J]. J4, 2011, 33(7): 67-73.

[1]	周袅1,2，葛洪伟1,2，袁运浩2,苏树智2 . 基于人工蜂群的连续域蚁群优化算法[J]. J4, 2016, 38(06): 1156-1163.
[2]	赵伟1，蔡兴盛1,2，曲慧雁1. 一种基于惩罚函数和新信息素更新方式的蚁群算法[J]. J4, 2013, 35(3): 103-107.
[3]	童科,毛力. 基于蚁群优化算法求解矩形件排样问题[J]. J4, 2011, 33(7): 158-162.