B题 碎纸片的拼接复原

摘要

图像碎片拼接复原是借助计算机把大量的图像碎片重新拼接成初始图像的完整模型。这一问题在考古、刑侦、古生物学以及壁画保存等方面具有广泛的应用。要从成千上万的图像碎片中找到相互邻接的图像碎片，并最终拼接成完整的模型，需要用计算机和人工干预辅助相结合的方式来完成。

本文就对碎纸片的拼接复原问题进行分析研究，针对单面纵切，单面既纵切又横切，双面既纵切又横切纸片等情况的拼接复原问题，建立了相应的数学模型，并运用、等数学软件，分别对题目所提出的问题进行求解。

对于问题一，我们将碎纸片信息导入软件中，得到每个碎纸片的像素值，并利用该像数值计算出碎纸片间拼接的候选权重，再以该权重值为依据对碎纸片进行配对，得到了碎纸片的拼接顺序，进而实现了仅纵切纸片时中、英文碎片的拼接复原。

对于问题二，我们首先筛选出了左右两侧有空白的碎片,并把剩余碎片的信息导入中,按照问题一中的方法计算出候选权重；利用该候选权重对碎片的编号进行定位，得到了一个定位矩阵并将其导入到中，在中分析该矩阵，可得到一个最优的拼接次序；再进行人工干预，找到左页边的碎片编号并将其置于第一位，然后按照最优连接次序将碎片进行拼接，得一个完整的行碎片。再对行碎片进行拼接，最优选择标准为：同一段落内行间距相同。可以得到按段落划分的几个碎片。此时进行人工干预，人为拼接为完整图片。在本问中，由于中、英文字的差异，在对英文碎片拼接时本文只采用了候选权重法进行处理。

对于问题三，考虑到英文双面的数据过于庞大，本文先对数据进行分类，用软件将处于同一行的碎片提取出来，分别存放在不同的文件夹中；然后再对文件夹内的数据进行候选权重的处理，按照问题二中的方法得到最优排列次序，按该排列次序拼接碎片得到了22个横向碎片，其中有11对正反面，再对这些横向碎片进行计算候选权重的处理，然后确定一个最优排列次序，完成图片的拼接。

关键词：候选权重最优排列次序 行间距 像素

一、问题重述

1.1问题背景

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技

自的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。

1.2问题提出

根据题意本文需要解决的问题有：

（1）对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，写出干预方式及干预的时间节点。

（2）对于碎纸机既纵切又横切的情形，设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，写出干预方式及干预的时间节点。

（3）上述所给碎片数据均为单面打印文件，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。

二、问题分析

2.1问题的重要性分析(社会背景)

众所周知,破碎文件的拼接在一些司法物证复原和军事情报等领域有着重要的应用,重要文件的复原有时能够发挥很大的作用,但是破碎文件拼接复原需由人工完成,准确率虽然很高,可是浪费时间,效率也很低。如何解决以上一系列问题变得非常重要。

2.2有关方面在这个问题上做过的研究

现有文献大部分都是针对二维（或三维）非规则碎片匹配算法的研究，针对碎纸机破碎的规则文件的拼接方面的文献极少，本文基于对所给五个附件碎片数据的处理和分析，针对各具体问题提出了若干数学模型得到了较为满意的解答。

2.3对问题的分析

针对问题一，

首先考虑将碎片导入中，并提取出每张碎纸片边缘上的像素值，然后利用这些像素值寻找到与某单个碎片左右两边相匹配的碎片，最后再进行图片的拼接，得到完整的图片。

针对问题二，

考虑到当前的切割方式，首先进行碎片的横向拼接：先提取出碎片左右边缘的像素值寻找某个碎片左右两侧最匹配的碎片，拼接在一行内。然后再对已拼接完成的行碎片进行纵向拼接，最终得到完整图片。

针对问题三，

由于问题三在横纵切割的基础上又加上了正反面，数据庞大，所以可以先对数据进行分类，将数据按行分类，把处于同一行的数据分在一组。再在组内进行数据处理，来完成行的拼接。最后将拼接好的行组合为完整文章。

三、模型假设

1.破碎纸片的形状规则；

2破碎纸片的信息未丢失；

3本文引用数据、资料均真实可靠。

四、符号说明[1]

五、 模型的建立与求解

5.1．问题一的求解

5.1.1模型一的概述

将单个图片A分割成碎片集合{},为确定碎片的顺序,需识别原始图像中的相邻碎片对,用表示碎片接在后面的可能性,称为候选权重。所有的候选权重组成一个阶的非负矩阵。在所有的碎片序列中，候选权重和为最大（或最小）的序列是接近正确重组的碎片序列。寻找最大（或最小）权重值的碎片序列，对序列中的数值进行分析后，即可确定碎片的排列顺序，进而解决碎片拼接复原的问题。

5.1.2碎片的拼接复原问题求解步骤如下：

步骤1：将碎片导入中，确定出每个碎片的像素值。

步骤2：利用碎片转化后的像素值，计算出碎片间的候选权重。

步骤3：在已得权重矩阵中寻找最大（或最小）权重值，组成两两配对。

步骤4：将已配对完成的碎片按顺序整合为完整图片。

5.1.3候选权重的计算[2]

准确率高的候选权重技术可减少重组次数，提高图像重组效率。本文选择简化相似系数匹配的权重计算方式进行处理。下面给出两个碎片相似系数的定义。碎片和碎片相邻边界像素的候选权重为：

= (1)

则当最小时，表示碎片对为最优配对组。

5.1.4中文碎片重组

步骤1：将碎片按照附件1中所给顺序导入到中，得到数组为，碎片像素为。

步骤2：取第个碎片的第72列像素值，设为。第个碎片的第1列像素值，设为。利用5.1.2中的权重计算公式计算权重，得。矩阵见附录1

步骤3：定位中每行元素的最小值位置，将输入到矩阵中，导出到表格中。此位置表示第个碎片右边所接最优碎片为。矩阵见附录2

步骤4：在中分析，可得有个最优链接次序。此时进行人工干预，找到左页边的碎片的编号，并将其置于第一位，然后按照最优次序排列即可。如下表表1：

表1：中文复原后碎片序号

步骤5：用按照此最优次序拼接图片，得到完整的最优结果。所得复原后图片见附录3

各步骤在[3]中的程序语句见附录4

5.1.5英文碎片重组

英文碎片中的字母与汉字相比变化较少，同样长度的语句中，英文字母可以多次重复，由于汉字变化多的特点，即使被切割成碎片，也很容易通过辨别汉字的一部分来确定，但是一个英文字母在不同的英文单词出现的概率极大，所以切割之后字母重组很容易产生错误的匹配。但是本题中，每列像素值有1980个，数量巨大，足以抵消英文特点所造成错误匹配概率大的问题。所以上述中文处理的方式在这里仍然适用。

方法同上，经过处理可得碎片最优次序排列如下表表2：

表2：英文复原后碎片序号

用按照此最优次序拼接图片，得到完整的最优结果。所得复原后图片见附录5。

5.2问题二的模型建立与求解

5.2.1中文碎片的拼接复原

碎片的横向拼接：

步骤1：将碎片中左右两侧有空白的碎片筛选出来。（原因见注1）

步骤2：将剩余碎片导入到中[4]，得到数组,其像素为。

步骤3：取第个碎片的第最后一列像素值，设为。第个碎片的第一列像素值，设为。利用5.1.2中的权重计算公式计算权重，得。矩阵的一部分见附录6。

步骤4：定位中每行元素的最小值位置，将输入到矩阵中，[5]导出到表格中。此位置表示第x个碎片右边所接最优碎片为。

步骤5：在中分析，可得一个最优链接次序。此时进行人工干预，找到左页边的碎片的编号，并将其置于第一位，然后按照最优次序排列即可（特殊情况见注2）。

步骤6：整合步骤4中序列，用拼接碎片，可得11个横向碎片。例：见下图：

1 2 3 4

箭头表示拼接方向4→3→2→1。其中图3是通过候选权重法所得。其余3块拼接方式为人工干预。

碎片的纵向拼接：

步骤7：根据同一段落文字间行间距相同原理，可设计一个程序寻找到4个段落。然后再进行人为干预，对4个段落进行排序，最终得到最优结果。

步骤8：将此11个横向图片左旋90°。

步骤9：用编程，见附录7，将11个横向碎片拼接为一个完整图片，在右旋90°即可。排列顺序表格如下表3：

表3：第二问中文碎片排列次序表

步骤10：按照矩阵中的数据，可得排列顺序，见附录8。附件3的复原图片见附录9

注1：先分析白边出现的原因，有两点，一是碎片为页边角，二是切割时恰好从2个汉字中间切割。

若不剔除白边，在进行权重值计算过程中，会遇到一种情况：在寻找碎片的右边正确拼接碎片时，会出现多个相同的最小值。无法唯一确定谁为正确的。且程序在此处就会中断，无法继续运行。

经分析得出原因为：假设寻找碎片的右边正确拼接碎片，此时有2个（或3个及3个以上）碎片、左边为完全白边，则在进行权重计算过程中会出现，假设为碎片所有配对权重中的最小值，则此时碎片右边所拼接的最优碎片就不能唯一确定，那么在运行找出最小值位置的程序时，会在此处就会中断，无法继续运行。所以要剔除白边进行计算。

例如：附件3中的065与014、071。碎片014、071与碎片065的权重相等，无法唯一确定谁是正确的，抑或是都为非正确的。

注2：排列最优次序过程中会遇到一种情况：假设第个碎片的右边可接碎片有、,为正确碎片，为错误碎片。而系统根据权重所确定的右边所接最优碎片为错误碎片而不是正确的。

经分析得出原因为：若一个汉字的某个笔画恰好被分割在2个碎片中，得到左边碎片的笔画位置处为完全白边是碎片，一边为笔画位置完全黑边的碎片。这就导致了次2个正确组合的碎片间的误差计算较大，而错误碎片（假设有部分完全白边与的白边位置几乎吻合）与间的误差较小，这就导致了计算结果为与接，而非与接。此时只能进行人工干预进行人为拼接。

例如：附件3中的001与087为正确配对组，但是经程序进行计算得001与003为最优配对组。

5.2.2英文碎片的拼接复原

由于英文的另一特点，既不像中文一样方正，经常出现、、等不规则字母，若在同一段落继续使用段落间行间距相同原理，误差会较大。所以选择用候选权重法进行拼接。具体步骤如下:

步骤1~步骤6与中文碎片拼接相同。

步骤7：将11个横向碎片左旋90°，用候选权重法进行计算，方法同5.1.3.

步骤8：用编程，将11个横向碎片拼接为一个完整图片，再右旋90°即可。排列顺序表格如下表4：

表4：第二问英文碎片排列次序表

附件4的复原图片见附录10

5.3问题三的模型建立与求解

因为考虑到英文双面，数据过于庞大，可以先对数据进行分类，用将可能是同一行的碎片提取行出来。分别存放在不同的文件夹。然后再对文件夹内的数据进行候选权重处理。具体步骤如下：

步骤1：将所有碎片导入到中[4]，得到数组,其像素为。

步骤2：在中设计一个程序，寻找到为同一行中的碎片。并分别存放在文件夹中。程序见附录11。

步骤3：取出一个文件夹中的碎片，取其中第个碎片的第最后一列像素值，设为。第个碎片的第一列像素值，设为。利用5.1.2中的权重计算公式计算权重，得。

步骤4：定位中每行元素的最小值位置，将输入到矩阵中，[5]导出到表格中。此位置表示第个碎片右边所接最优碎片为。

步骤5：在中分析，可得一个最优链接次序。此时进行人工干预，找到左页边的碎片的编号，并将其置于第一位，然后按照最优次序排列即可。

步骤6：整合步骤4中序列，用拼接碎片，可得一个横向序列。

步骤7：对剩余文件夹重复步骤3~6。可得到22个横向碎片。其中有11对正反面。

步骤8：对上述22对横向碎片进行候选权重处理。操作同5.2.2中步骤7~8。

最终得到排列顺序表格如下表5和表6：

表5：第三问A面复原后次序表

表6：第三问B面复原后次序表

附件5的复原图片见附录12，未做出附件6的复原图片。

六、模型评价及不足与改进

6.1.1模型评价：

1. 本文中的所有图片碎片都用了MATLAB 软件进行处理，而MATLAB软件功能十分强大，精确度也很高，从这个角度可证明我们结果的可靠性与方法的合理性。

2.本文采用的是半自动的拼接复原的方法，能解决大多数碎纸片的拼接问题，在实践中能广泛运用。

3.本文在对于中、英文碎纸片的拼接复原时，考虑到了中、英文字的差异，进而采用了一些不同的处理方法对其进行拼接复原，具有很强的实际意义。

6.1.2模型不足与改进:

1.在对既纵切又横切碎片的拼接复原问题时，采用了较多的人工干预过程，这还有待改善。

七、参考文献

[1]肖华勇，数学建模竞赛优秀论文精选与点评，西安：西安工业大学出版社，2011.11.

[2]王东平，王清贤，罗永军，李炳龙,等，BMP图像碎片重组中的候选权重方法，计算机应用，2007,27（12）:3062-3066,2007年12月.

[3]贺超英，应用与实验教程，北京：电子工业出版社，2010.1.

[4]周品，赵新芬，数学建模与仿真，北京：国防工业出版社，2009.4.

[5]董臻圃，数学建模方法与实践，北京：国防工业出版社，2006.8.

八、附录

附录清单:

1．矩阵;

2. 矩阵;

3.附件1中文复原图片;

4.各步骤在中的程序语句;

5.附件2英文复原图片;

6. 矩阵;

7程序;

8矩阵;

9附录3中文复原图片;

10附录4英文复原图片;

11程序;

12附录五正反两面复原图片;

附录1

附录2

附录3

附录4

程序如下：步骤2：求候选权重矩阵语句：

>> square_matrix = zeros(19, 19);

>> for i=1:19

col1=x1{i}(:,72);

for j=1:19

col2=x1{j}(:,1);

minus = double(col1)-double(col2);

square = minus'*minus;

square_matrix(i,j)=square;

end

end

>> square_matrix=sqrt(square_matrix/1980);…………(即为C1)

步骤3：求位置矩阵B的语句：

A= square_matrix

>>Amin=min(A’)’；

>>for i=1:19

[x,y]=find(A==Amin(i,1));

B(i,1)=x;

B(i,2)=y;

End

3步骤5：拼接图片语句：

>> h=imread('C:\Users\xiayang\Desktop\附件1\008.bmp');

>> n=imread('C:\Users\xiayang\Desktop\附件1\014.bmp');

>> l=imread('C:\Users\xiayang\Desktop\附件1\012.bmp');

>> o=imread('C:\Users\xiayang\Desktop\附件1\015.bmp');

>> c=imread('C:\Users\xiayang\Desktop\附件1\003.bmp');

>> j=imread('C:\Users\xiayang\Desktop\附件1\010.bmp');

>> b=imread('C:\Users\xiayang\Desktop\附件1\002.bmp');

>> q=imread('C:\Users\xiayang\Desktop\附件1\016.bmp');

>> a=imread('C:\Users\xiayang\Desktop\附件1\001.bmp');

>> d=imread('C:\Users\xiayang\Desktop\附件1\004.bmp');

>> e=imread('C:\Users\xiayang\Desktop\附件1\005.bmp');

>> i=imread('C:\Users\xiayang\Desktop\附件1\009.bmp');

>> m=imread('C:\Users\xiayang\Desktop\附件1\013.bmp');

>> s=imread('C:\Users\xiayang\Desktop\附件1\018.bmp');

>> k=imread('C:\Users\xiayang\Desktop\附件1\011.bmp');

>> g=imread('C:\Users\xiayang\Desktop\附件1\007.bmp');

>> r=imread('C:\Users\xiayang\Desktop\附件1\017.bmp');

>> x=imread('C:\Users\xiayang\Desktop\附件1\000.bmp');

>> f=imread('C:\Users\xiayang\Desktop\附件1\006.bmp');

>> y=[h n l o c j b q a d e i m s k g r x f];

>> imwrite(y,'C:\Users\xiayang\Desktop\附件1\1000.bmp');

附录5

附录6

附表7

>> square_matrix = zeros(177,177);

>> for i=1:177

col1=x{i}(:,72);

for j=1:177

col2=x{j}(:,1);

minus = double(col1)-double(col2);

square = minus'*minus;

square_matrix(i,j)=square;

end

end

>> square_matrix=sqrt(square_matrix/177);

附录8

附录9

附录10

附录11

for i=1:11

for j=1:11

if(a{b{i}}(6)==180)

if(180-a{b{i}}(5)+a{j}(2)==26)

b{i+1}=j

end

else

if(((180-a{b{i}}(5)+a{j}(1))==68)||((180-a{b{i}}(5)+a{j}(1))==69))

b{i+1}=j

end

end

end

end

附录12

B题碎纸片的拼接复原