[0006] 本发明的目的对形状规则、无任何轮廓信息可用的文档碎片拼接，提供一种高效、快速的基于0-1规划的文档碎片拼接方法。
[0007] 本发明所涉及的基于0-1规划的文档碎片拼接方法，采用以下步骤：
[0008] (1).首先将所有纵向分隔的碎片进行扫描，存入电脑并自动为全部n张碎片编号，记为i＝1…n,每张碎片的大小为M×N，M为碎片的高度，N为碎片的宽度；
[0009] (2).读取每张碎片的像素值，得到碎片的像素矩阵Ai，其中Ai的每一个元素为0到255之间的整数，表示像素的灰度值，255表示像素为白色，随着数字的减小，颜色变暗，0表示像素为黑色；
[0010] (3).定义两张碎片i,j之间的距离为：碎片i的右边缘和碎片j的左边缘像素值差的绝对值之和，记做rij,i＝1…n,j＝1…n；
[0011] 用aik表示Ai的最后一列的第k个元素，ajk表示Aj第一列的第k个元素，则碎片i和碎片j之间的距离：
[0012] (4).引入0-1变量xij,i＝1…n,j＝1…n，xij只有两个取值：0和1，用xij＝1表示碎片i和碎片j左右相接，xij＝0表示碎片i和碎片j左右不相接，只要确定了xij的取值即可判断碎片i是否和碎片j左右相接；
[0013] (5).如果碎片i和碎片j左右相接，则碎片i的右边缘和碎片j的左边缘像素值应该相近，因此碎片i和碎片j的距离应该很小，正确的拼接方式应该使得所有相邻的碎片之间的距离之和最小，即所求的xij应该使得 达到最小；
[0014] (6).xij还应满足以下两条：
[0015] 1)碎片i右侧只能接一张碎片，即对每一个i有且仅有一个xij＝1，由于xij只有0和1两个取值，因此他们的和应该等于1，即应成立：
[0016] 2)碎片j也只能接在一张碎片的右侧，即对每一个j有且仅有一个xij＝1，应成立[0017] (7).我们得到0-1规划模型：
[0018]
[0019] (8).利用计算机求出xij,i＝1…n,j＝1…n.若xij＝1，则碎片i右接碎片j，进而确定碎片的拼接顺序，完成碎片的拼接。
[0020] 上述的发明主要针对碎纸机产生的文档碎片进行拼接，这种碎片形状规则、无任何轮廓信息可用，文档碎片拼接具有相当的难度。
[0021] 同样道理，对于横向切割的文档，通过计算碎片i的下边缘和碎片j的上边缘之间的距离，建立0-1规划模型，解出xij,i＝1…n,j＝1…n.若xij＝1，则碎片i下接碎片j，进而确定碎片的拼接顺序。横向切割如遇到行与行之间的空白，可以根据上述方法确定的拼接顺序，结合人工调整完成文档的拼接。
[0022] 与现有技术相比，本发明的碎片拼接方法，其突出特点是：利用数字化方法解决了无任何边缘信息可用的文档碎片的拼接，通过引入0-1变量的方法判断任意两个碎片是否相接，最优化方法的引入使得碎片拼接正确率高且拼接速度快。附图说明:
[0023] 图1为整理后的拼接示意图，其中，灰色竖条为碎片间的间隔，数字表示碎片的编号。具体实施方式：
[0024] 文档被纵向切割成17条碎片，扫描之后存储为BMP格式的图片，标记为1，2，…，17，每张图片的大小为582×25。
[0025] 读取每张碎片的像素值，得到矩阵Ai,i＝1…17，其中Ai是一个582×25的矩阵。
[0026] 用aik表示Ai的最后一列的第k个元素，ajk表示Aj第一列的第k个元素。计算碎片i和碎片j之间的距离：
[0027]
[0028] 为了描述第i张碎片右边是否和第j张碎片相接，引入0-1变量如下：
[0029]
[0030] 最优的拼接方式应该使得所有相邻的碎片之间的距离之和最小，我们根据所有相邻的碎片之间的距离之和最小得到目标函数：
[0031]
[0032] 第i张碎片右侧只能接一张碎片，同时第j张碎片也只能接在一张碎片的右侧，我们以此得到约束条件：
[0033]
[0034] 利用0-1规划软件lingo求解，运行1秒钟即可得到：
[0035] x1,6＝x2,10＝x3,8＝x4,7＝x5,4＝x6,2＝x7,3＝x8,16＝x9,13
[0036] ＝x10,14＝x11,9＝x12,1＝x13,15＝x14,11＝x15,17＝x16,12＝x17,5＝1,[0037] 即碎片1右边接6，碎片2右边接10，……，碎片16右边接12，碎片17右边接碎片5，碎片左右相接呈环状，容易看出4、5为文档的左右边缘，在4、5处断开，整理得碎片拼接顺序如下表：
[0038]
[0039] 按表中整理好的序号，进行拼接，拼接后的文档见图1。
