一种基于0-1规划的文档碎片拼接方法

摘要

本发明属信息技术领域，涉及一种碎纸片的拼接复原方法，特别涉及一种基于0-1规划的文档碎片拼接方法。本发明的拼接方法为：首先读取每张碎片的像素值并计算任意两张碎片之间的距离，然后通过引入0-1变量x_ij刻画任意两个碎片是否可以相接，以所有相邻的碎片之间的距离之和最小为目标函数建立0-1规划模型，最后利用优化软件lingo对上述模型求解，若x_ij＝1，则碎片i右接碎片j，进而确定碎片的拼接顺序。本发明利用数字化方法解决了无任何边缘信息可用的文档碎片的拼接，通过引入0-1变量的方法判断任意两个碎片是否相接，最优化方法的引入使得碎片拼接正确率高且拼接速度快。

主权项

1.一种基于0-1规划的文档碎片拼接方法，其特征在于采用以下步骤：（1）首先将所有纵向分隔的碎片进行扫描，存入电脑并自动为全部n张碎片编号，记为i=1…n, 每张碎片的大小为M×N，M为碎片的高度，N为碎片的宽度；（2）读取每张碎片的像素值，得到碎片的像素矩阵A_i，其中A_i的每一个元素为0到255之间的整数，表示像素点的灰度值；（3）定义两张碎片i, j之间的距离为：碎片i的右边缘和碎片j的左边缘像素值差的绝对值之和，记做.用a_ik表示A_i的最后一列的第k个元素，a_jk表示A_j第一列的第k个元素，则碎片i和碎片j之间的距离;（4）引入0-1变量，x_ij只有两个取值：0和1，用x_ij＝1表示 i和j左右相接，x_ij＝0表示i和j左右不相接；（5）建立0-1规划模型正确的拼接方式应该使得所有相邻的碎片之间的距离之和最小，因此有目标函数：.由于碎片i右侧只能接一张碎片，同时碎片j也只能接在一张碎片的右侧，因此x_ij应满足约束条件：（6）利用最优化软件lingo求解上述模型，解出. 若＝1，则碎片i右接碎片j，进而确定碎片的拼接顺序。