• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

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

• 论文 • Previous Articles     Next Articles

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

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

  1. 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:

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