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

摘要

本发明属信息技术领域，涉及一种基于0-1规划的块状文档碎片拼接方法，特别涉及一种碎纸机纵、横切割的块状文档碎片拼接复原方法。采用以下步骤：碎片预处理:扫描，读取每张碎片的像素值，求碎片间的距离；判断任意两碎片是否左右相接:设计0-1规划模型：；st.利用计算机求出.若x_ij＝1，则碎片i右接碎片j。将所有碎片左右相接成一个长条，根据文档左右两边存在页边距的特征，将长条在存在页边距的碎片处断开成长度相同的m条碎片。同样的办法，再将所有碎片上下相接，完成文档的拼接复原。本发明利用数字化方法解决了碎纸机切割的块状文档碎片的拼接，最优化方法的引入使得碎片拼接正确率高且拼接速度快。

主权项

一种基于0‑1规划的块状文档碎片拼接方法，其特征在于采用以下步骤：a. 碎片预处理（1）首先将经过碎纸机纵、横切割得到的n张文档碎片编号，分别扫描后以图片格式存入电脑，记为i=1…n，调整图片方向使其文字内容为从左到右的方向，每张碎片的高度为M；（2）读取每张碎片的像素值，得到碎片的像素矩阵A_i，其中A_i的每一个元素为0到255之间的整数，表示像素的灰度值；（3）定义两张碎片i, j之间的距离为：碎片i的右边缘和碎片j的左边缘像素值差的绝对值之和，记做；用a_ik表示A_i的最后一列的第k个元素，a_jk表示A_j第一列的第k个元素，则碎片i和碎片j之间的距离：；b. 判断任意两碎片是否左右相接（1）引入0‑1变量，只有两个取值：0和1，用表示 i和j左右相接，表示i和j左右不相接；（2）建立0‑1规划模型正确的拼接方式应该使得所有相邻的图片之间的距离之和最小，因此有目标函数：；由于第i张图片右侧只能接一张图片，同时第j张图片也只能接在一张图片的右侧，因此应满足约束条件利用计算机求出，若x_ij＝1，则碎片i右接碎片j；c. 根据步骤b中x_ij的求解结果将所有碎片左右相接成一个长条，根据文档左右两边存在页边距的特征，将长条在存在页边距的碎片处断开成长度相同的m条碎片，每条碎片的像素矩阵记为B_i，，每条碎片的宽度为N；定义任意两行碎片i, j之间的距离为：碎片i的下边缘和碎片j的上边缘像素值差的绝对值之和，记做；用b_ik表示B_i的最后一行的第k个元素，b_jk表示B_j第一行的第k个元素，则第i条碎片和第j条碎片之间的距离：；d. 判断m条碎片是否上下相接（1）引入0‑1变量，用y_ij＝1表示碎片 i和碎片j上下相接，y_ij＝0表示碎片i和碎片j上下不相接；（2）建立0‑1规划模型：如果碎片i和碎片j上下相接，则碎片i的下边缘和碎片j的上边缘像素值应该相近，即所求的x_ij应该使得达到最小；碎片i下侧只能接一张碎片，即应成立：；碎片j也只能接在一张碎片的下侧，即应成立；（3）利用计算机求出. 若y_ij＝1，则碎片i下接碎片j，进而将所有碎片上下相接，完成文档的拼接复原。