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

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

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

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.