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