基于聚类优化模型的碎纸自动拼接方法研究

RESEARCH ON AUTOMATIC RECONSTRUCTION OF RIPPED-UP DOCUMENTS BASED ON CLUSTERING OPTIMISATION MODEL

碎纸自动拼接算法是计算机图形图像应用的一个热点领域。对于碎纸拼接主要由计算机图像预处理、图形图像特征提取和图像匹配三个过程组成。针对中文内容碎纸和英文内容碎纸的区别,给出了两种不同的图像特征提取方法。首先建立聚类模型对碎纸图像中提取的图像特征值进行K-mean聚类得到属于同一行的碎片集合;然后建立旅行商优化数学模型,以拼接方案特征值误差平方和最小为目标函数,实现同一行碎片集合的排序,形成完整一行的图像;最后利用优化数学模型实现不同行图像的排序。实验结果显示:该拼接算法可以给出准确的拼接方案,且求解迅速,无需进行人工干预,实现真正的全自动拼接。

Automatic ripped-up documents reconstruction is a hot field in computer graphics image applications. For ripped-up documents reconstruction,it mainly consists of three processes including computer image preprocessing,graphics image feature extraction and image matching. Aiming at the difference between ripped-up documents with Chinese and English contents,we present in the paper two different image feature extraction methods. First we build clustering model,it is for applying k-means clustering to image feature value extracted from ripped-up document image to obtain the set of fragments belonging to same row; Then we build the optimised travelling salesman problem（ TSP） mathematical model,taking it as the target function that to minimise the error square sum of feature value of splicing scheme to achieve the sorting of the fragment set in same row and to form the image of a complete row; Finally,we employ the optimised mathematical model to implement sorting the images of different rows. Experimental results illustrate that the reconstruction algorithm proposed in the paper can provide accurate splicing scheme with rapid solution and without the need of artificial intervention, thus achieves real fully automated splicing.