Abstract: Reconstruction of rippedup documents was important for judicial authentication，cultural relic reconstruction and military information acquisition，etc．An approach for the reconstruction of regularly rippedup documents was proposed. Firstly, the line spacing of the fragments was automatically extracted. Secondly, meanshift algorithm was adapted to cluster all the fragments. Thirdly, for each cluster, the similarity matrix was constructed based on the grayscale of the edges of the fragments. Lastly, the document with genetic algorithm was reconstructed.Reconstruction of rippedup documents is important for judicial authentication，cultural relic reconstruction and military information acquisition，etc．In this paper，we propose an approach for the reconstruction of regularly rippedup documents. Firstly, the line spacing of the fragments is automatically extracted|Then meanshift algorithm is adapted to cluster all the fragments|Then for each cluster, the similarity matrix is constructed based on the grayscale of the edges of the fragments|Lastly, we reconstruct the document with genetic algorithm.

Key words: Reconstruction of rippedup documents, Line spacing, Clustering, Genetic algorithm, Regular fragments

摘要：  破碎文件的拼接在司法物证复原、 历史文献修复以及军事情报获取等领域都有着重要的应用。针对规则碎纸片的复原问题, 首先自动提取碎片的行间距特征, 采用 M e a n - s h i f t算法对所有碎片进行聚类分析, 然后根据碎片边界的灰度特征, 建立碎片之间的相似性矩阵, 最后采用遗传算法将碎片进行拼接。

关键词:  碎片修复, 行间距, 聚类分析, 遗传算法, 规则碎纸