碎纸片拼接复原的设计与实现
摘要
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。由于人工拼接效率较低，我们利用MATLAB 软件编写程序，实现碎纸片拼接技术的计算机化，实现批量拼接，以节省人力和时间。
（一）为寻找最吻合拼接方案，利用MATLAB 软件中的imread 函数，实现了碎纸片与矩阵之间的形式转化以便于碎纸图片的拼接比对。数值0至255表示图中某一像素点由黑到白的变化程度。再根据纸张的边界留白较多，通过计算每个矩阵第一列中各向量的元素和，可将所得和数值最大的列向量所在矩阵对应的碎纸片确定为左边界。经计算知：008图为整体图片的左边界。根据使吻合参数ρi , j =∑P {i }k ,72-P {j }k ,1最小的原则，
k =11980
可计算出下一张图片。重复此步骤，以此类推，每次都挑选出剩余图片中与前一幅图片吻合参数ρi , j 最小的作为与之相连接的碎纸图片。最后可得到
行优化。附件3类比于问题一，用相同的方法找到所有碎纸片的左边界，共11张，分作为入手点，利用MATLAB 软件进行图片拼接。但由于碎纸图片的行特征值有误差，故图片大块拼接正确，但与实际情况有细微差别。通过简单的人工检测得到准确行的排列顺序，由于行信息充足，借用第一问最终达到正确拼接效果。结果矩阵如 表12 所示。
第二种情况的关键点是找出准确的行特征，由于汉字与英文书写格式不同，汉字均为方块字，易于定位。而英文由于特殊的书写方式，上下位置不同，不易于找到行特征值。如：英文字母最为密集行中点位置。需将附件4图片对应的矩阵转化为0-1列向量（空白行为0，反之则为1）。利用此方法筛选出位于同一行的碎纸片并进行纸片拼接。后续拼接方法同附件3。结果矩阵如 表13 所示。
（三）结合双面信息处理边界，得到边界特点。根据元音字母中心位置得出行高，从而更准确筛选同行图片。双面信息同时校准，更容易得到拼接顺序，人工干预少。结果矩阵如 表5 所示。
模型一简单易处理，适用于含大量信息的碎纸片拼接且准确度高；模型二针对文字内容的中英文差异分别利用吻合参数和行高作为标准来筛选图片；模型三深入生活实际，考虑日常生活中反正面印刷情况并结合英文印刷特点，实用性高，双面信息同时校准，人工干预少。
关键字：碎纸拼接 MATLAB 吻合参数 灰度
一、问题重述
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：
1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。
2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。
3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。
【数据文件说明】
(1) 每一附件为同一页纸的碎片数据。
(2) 附件1、附件2为纵切碎片数据，每页纸被切为19条碎片。
(3) 附件3、附件4为纵横切碎片数据，每页纸被切为11×19个碎片。
(4) 附件5为纵横切碎片数据，每页纸被切为11×19个碎片，每个碎片有正反两面。该附件中每一碎片对应两个文件，共有2×11×19个文件，例如，第一个碎片的两面分别对应文件000a 、000b 。
【结果表达格式说明】
复原图片放入附录中，表格表达格式如下：
(1) 附件1、附件2的结果：将碎片序号按复原后顺序填入1×19的表格；
(2) 附件3、附件4的结果：将碎片序号按复原后顺序填入11×19的表格；
(3) 附件5的结果：将碎片序号按复原后顺序填入两个11×19的表格；
(4) 不能确定复原位置的碎片，可不填入上述表格，单独列表。
二、模型假设
1、 每张碎纸片的形状都是完全相同的长方形且每张碎纸片形状规则；
2、 文字打印清晰，无缺墨断墨情况；
3、 纸片边缘整齐，无重叠，无损耗；
4、 扫描过程中每张碎纸片的位置都是完全平行的，不会出现倾斜的情况；
5、 假设恰好能完全拼接，即碎片无缺失，也没有其他碎片混杂；
6、 纸片无倒转；
7、 碎片文字均为相同字号，字号大小适中；
8、 文字印刷体行高、行间距相同；
9、页边距非0，但较小。
三、字符说明
1、P {i }表示第i 张图片所转化得到的矩阵；
2、P {i }m , n 表示第i 个图所形成的矩阵的第m 行n 列对应灰度值；
3、P {i }(j ) 表示第i 个图所形成的矩阵的第j 列；
4、ρj , k 表示第j 个图和第k 个图之间的吻合参数（其含义在模型分析中说明），其中两张图的吻合参数越低表示这两张图越吻合；
5、l i 表示图i 的0-1列向量
四、模型分析
本文针对三种碎片拼接类型分别建立数学模型。
模型一简单易处理，适用于单片含大量信息的碎纸片拼接且准确度高；
模型二针对文字内容的中英文差异分别利用吻合参数和行高作为标准来筛选图片，且以缩小比对范围的形式应用于庞大数据量的整理进而进行碎片拼接复原；
模型三深入生活实际，考虑日常生活中反正面印刷情况并结合英文印刷特点，实用性高，准确度大。
问题一：
利用MATLAB 程序中的imread 函数将附件1的19张碎纸片分别转化成矩阵形式，每一张碎纸片都可转化为一个1980⨯72的矩阵。for 循环的使用可以很大程度上节省时间、人力，再根据边界准则通过计算首列数字变化来确定其边界。最后根据吻合参数的大小确定最后的碎纸片拼接顺序。
求解步骤如下：
（图1：问题一求解思路图）
问题二：
同样利用第一问中求得图片左边界的方法，附件3、附件4中两幅图片的左边界。找出与左边界11张图片同行的其余碎纸图片。编程筛选出每行的图片，利用问题一中的方法进行计算机拼接，但由于拼接存在一定的误差，所以部分图片拼接不完整正确，在此情况之下进行人工干预，观察图片内容，根据内容手动移动碎纸图片进行拼接。 求解步骤如下：
（图2：问题二求解思路图）
问题三：
对于有双面打印的碎纸片，根据边缘留白情况，可筛选出22个左边界，并根据字母中点所在行的行高分为11类。并根据行高对其他图片进行筛选分类。引入人工干预，完成效果拼接。
求解步骤如下：
（图3：问题三求解思路图）
五、模型建立与求解
5.1附件1中碎纸片拼接
图片是否能拼接，重点要看边缘的吻合程度，于是我们首先给出定义：
P {i }m , n 表示第i 个图所形成的矩阵的第m 行n 列对应灰度值，则第i 个图与第j 个图所分别形成矩阵的第m 行n 列的差的绝对值， 即ρ=P (i ) m , n -P (j ) m , n
记为第i 个图与第j 个图在边缘点(m , n ) 的吻合参数，其中两张图在该点的吻合参数越低表示这两张图该点越吻合。 对于两图边缘列，则有ρi , j =∑P {i }k ,72-P {j }k ,1，为边缘的吻合参数，其中两张图边缘
k =11980
的吻合参数越低表示这两张图越吻合；
故，我们用
min ∑ρA [i ],A [i +1],
i =118
作为全局的吻合参数，其中的限定条件为当i ≠j 时，A [i ]≠A [j ]
具体求解过程如下：
1）为将19张碎纸片拼凑成一幅完整图片，需对由每一张碎纸片转化得到的数字矩阵进行处理。其中000图转化为矩阵P {1},001图转化为矩阵P {2}，··· ，018图转化为矩阵P {19}。（见数据表1）
2）第i 个图所形成的矩阵的第1列就是第i 个图的左边界，第72列表示第i 个图的右边界，列中数字的变化表示图边缘文字的灰度变化。灰度是指黑白图像中点的颜色深度，范围一般从0到255。白色为255，黑色为0。将每个矩阵首列向量的每个元素相加求和，因为完整图片的左右边界均为空白，故求和数值越大代表空白越多，通过计算找出19个矩阵中，首列数字无变化的（即首列向量和最大的）矩阵为由008图所形成矩阵P {9}。则可确定008图为最后完整图的左边界。
3）再利用for 循环语句将矩阵P {9}的最后一个列向量与另外每个矩阵的第一个列向量元素对应相减，会得到由每个元素差值组成的新向量。再将得到的新向量中的每个元素的绝对值相加求和得到一个数值。不妨将此求和所得数值称为两向量的吻合参数，记为ρ。
4）吻合参数最小的矩阵所对应的碎纸片即为第二张。从而我们得到数学模型： 第二个图为：
ρ9, i =
1≤i ≤19, i ≠9k =1min ∑P {9}1980k ,72-P {i }k ,1
达到该最小值时所对应的矩阵为第i 个矩阵P {i }，我们用t 2(=i ) 表示为所选出的第i 个矩阵的标码，以便后续求解；
5）依据第二张碎纸片所对应矩阵的最后一列与其他矩阵第一列对应元素相减，再绝对值求和进行吻合参数的比较，从而第三个图为：
ρt , i =21≤i ≤19, i ≠9, i ≠t 2k =1min ∑P {t}
19802k ,72-P {i }k ,1
达到该最小值时所对应的矩阵为第i 个矩阵P {i }，我们用t 3(=i ) 表示为所选出的第i 个矩阵的标码，以便后续求解；
以此类推:排序后的第j 个图为：
ρt j -1, i =
1≤i ≤19, i ≠9, i ≠t 2,... i ≠t j -1k =1min ∑P {t1980j -1k ,72}-P {i }k ,1，达到该最小值时所对应的矩阵为第i 个矩阵
P {i }，我们用t j (=i ) 表示为所选出的第i 个矩阵的标码；
6）以此类推，第18个图为：
ρt 17, i =
1≤i ≤19, i ≠9, i ≠t 2,... i ≠t 17k =1min 1980∑P {t17k ,72}-P {i }k ,1，达到该最小值时所对应的矩阵为第i 个矩
阵P {i }，对应第i 个图为排序后第18个图，剩余的一个自然为最后一图即图片右边界。
通过实际拼接实践，我们可以知道，局部拼接复原结果即全局最优拼接复原结果。
最后我们得到附件1的拼接顺序：
（复原图片见附录1.1）
5.2附件2中碎纸片拼接
附件2的处理办法与附件1相同，利用所有矩阵的第一列先找到所有碎纸片中的左边界，再根据吻合参数ρ确定碎纸片的拼接顺序。最后我们得到附件2的拼接顺序：
（复原图片见附录1.2）
由于附件1和附件2中碎纸片的行高较高，所以在吻合参数的计算过程中相对误差很小，利用在MATLAB 软件中编写的程序即可求出附件1和附件2所有碎纸片的正确拼接顺序，故在此问中不涉及人工干预。
5.3附件3中碎纸片拼接
1）利用第一问在MATLAB 中编写程序求出位于左边界的图片的思想，运行程序可以找到附件3中位于第一列中的图片共有11张，分别为049图，061图，168图，038图，071图，014图，094图，125图，029图，007图，089图。恰好符合11⨯19矩阵的格式要求。即说明这11张图片为整体图片第一列的所有组成部分。
2）用MATLAB 编写循环语句，以已经确定的第一列的11张图片为标准分为11类，分别找出与第一列11个图空白行位置相近似的图片归为一类（此时可认为同一类中图片的文字行是对齐的，即同类图片理论上应处在相同水平位置）
与图007（标号为8）空白位置相近的图片有22个，编号为
8 1 15 33 46 54 57 69 71 72 90
154 159 167 175 176 197 209
与图014（标号为15）空白位置相近的图片有57个，编号为
15 4 5 9 10 13 26 28 32 33 40
74 75 83 86 90 94 102 103 106 108 109
120 124 126 129 135 136 141 147 152 153 154 94 127 138 139 41 114 155 52 115 156 61 116 160 71 118 161 166 167 170 171 177 186 195 197 200 204 206
与图029（标号为30）空白位置相近的图片有35个，编号为
30 6 11 17 22 38 45 49 56 60 65
105 107 110 111 112 140 146 151 158 172 173
188 198 202 205 207
与图038（标号为39）空白位置相近的图片有22个，编号为
39 9 10 15 25 26 36 47 72 75 82
104 106 123 131 149 162 168 190 194
与图049（标号为50）空白位置相近的图片有35个，编号为
50 3 12 17 22 23 29 55 58 66 67
111 119 130 140 142 144 146 151 158 174 179
189 191 193 198 205
与图061（标号为62）空白位置相近的图片有22个，编号为
62 7 15 20 21 37 53 64 68 70 72
97 100 117 132 163 164 178
与图071（标号为72）空白位置相近的图片编号有47个
72 9 10 16 17 18 22 26 28 33 34
75 81 84 86 94 106 107 110 111 133 134
154 157 158 166 167 171 174 182 185 188 197
205 206
与图089（标号为90）空白位置相近的图片编号有69个
90 5 9 10 14 16 17 18 22 26 28
57 61 67 71 72 75 81 84 86 94 102
110 111 114 115 118 120 124 126 133 134 140
152 153 154 155 156 157 158 166 167 171 174
188 195 197 198 199 201 203 205 206
与图094（标号为95）空白位置相近的图片编号有22个
95 15 35 43 44 48 59 72 78 85 90
113 122 125 128 137 145 150 165 184
208 67 76 174 181 89 90 92 96 182 185 73 79 57 61 140 146 198 199 33 34 103 106 141 146 182 183 91 98 93 99 182 185 107 110 187 188 80 90 67 71 151 153 201 203 41 208 107 109 147 151 185 186
与图125（标号为126）空白位置相近的图片编号有19个
126 14 15 17 22 67 90 107 110 111 146 158 174 182 183 185 188 198 205
与图168（标号为169）空白位置相近的图片编号有37个
169 2 15 17 19 22 24 27 31 42 51 63 67 77 87 88 101 103 107 110 111 121 140 143 146 148 151 158 174 180 182 185 188 192 196 198 205
由于图片的切割都不完整导致空行较多，故通过程序运行出的结果每一行的符合要求的图片都 19张。
3）有一组恰为19块图，但通过第一问的模型对这19块进行横向拼接时，发现有三块明显不位于同一行，将这三块拿出，分别为, 图014，图016，图089。再找相对较少（22块）的几行，发现其中重复的恰为首列中的某3个图，删去后，得到这几列的19个图分别进行拼接，其中首图为007图的拼接结果为：
图4
（人工干预）我们发现所选图片恰为该行图片，但拼接结果由于碎片边缘笔划变化导致相连部分误差较大，从而出现计算机拼接错误，人工干预将错误部分进行更改后，该行顺序为： 同理，可得到其余行向找出为22块行的拼接顺序，分别为 再处理行中找出35或37个图片的行，首先通过程序将之前已使用过的图片排除，则 首图为图029的行，剩余图片为
用问题一中模型对该21块图进行拼接，发现图139和图150不属于该行，将两图删除后，再次进行拼接，得到上一步中情况（有个别拼接不准确），（人工干预）将其调换位置，得到该行顺序为
表6：
同理，得到首图为图049，图168的两行排列为
再用以上结果筛选47个图的行，剩余图片为
用问题一中模型对该25块图进行拼接，发现图008、图009、图025、图032、图074、图105不属于该行，将两图删除后，再次进行拼接，得到上一步中情况（有个别拼接不准确），（人工干预）将其调换位置，得到该行顺序为:
而对于一行中出现69块和67块的两行，重复较多，于是我们选用另一种方式筛选。 当得到每块图所对应矩阵后，我们将有全空白行记为0，存在黑色部分行记为1，则用mathematica 得到该图片的一个0-1列向量，例如图089的对应0-1列向量为： l 4=( 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)T l 89= (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)T
其中，我们挑选出l 4, l 89, l 40, l 101, l 102几列进行部分对比，左侧为其对应上部几行对比，右
侧为其对应中部几行对比。
l 4 l 89 l 40 l 101 l 102 与左边对应中间行位置
0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 1 0 1 1 1 1 0 0 0 0 1 0 1 1 1 1 0 0 0 0 1 0 1 1 1 1 0 0 0 0
观察所选出l 4, l 89, l 40, l 101, l 102对应图片的0-1列向量对比，不难发现，其1-1对应，0-0对
应较准确。
若两个图片属于同一行，则其空白位置高度应对应相等，字体高度对应相等，针对这一特性，我们对两个列向量做内积后，同行的内积不变，建立模型得：
与图089同行的图片应满足：l i -l 89, (i =0,1, 2,..., 208, i ≠89) 尽量小，我们将结果由小
到大排列，前10个即为与图089同行的图片同样的与图014同行的图片应满足：l i -l 14, (i =0,1, 2,..., 208, i ≠14) 尽量小，我们将结果由小到大排列，前10个即为与图014同行的图片从而对首图为图089和图014的两行又做了筛选，得到
则剩余为首图为图125一行中图片，用问题一中模型排序为
3）完成行图片的拼接，后续只相当于拼接19⨯1矩阵，此时所有图片仅有横切情况，
类似于第一问中仅纵切情况，利用MATLAB 变成完成最后拼接效果。
附件3的拼接顺序：
该模型虽能准确拼出复原后图片，但在每一行挑选过程中不能分别准确的找出对应的19个图片，若对180⨯1的每个列矩阵进行调整，相信可以更准确地快速地拼出图片。
5.4附件4中碎纸片拼接
我们首先希望同样通过附件3的方法，即通过碎纸片左边界留白的情况，筛选出11张图片作为第一列。但是由于英语文章的特殊性，每个单词之间都有一定的间隔，加之碎纸片的高度较小，以至于不止11张纸条的左边界是空白，于是我们引入一种新的方法。首先，当得到每块图所对应矩阵后，如果某行全为空白，则将该行记为0，否则记为1，则用mathematica 将该图片转化为一个0-1列向量。从而筛选1元素较多的即英文字母密集的图片，由这些图片（人工干预）逐次筛选后，所留英文字母密集且行位置不同的，作为我们拼接的起点。再由其确定原因字母的中心行，进而确定出行高，由密集图片行高的不同位置，两边延伸，进行拼接，由于某些行为段落结尾处，其后空白较多，需人工干预，同样可拼接出11行英文字母，最后同附件3的处理方式，对11个行转化成1⨯19矩阵进行拼接。
附件4的拼接顺序
5.5 附件5的拼接复原
对于双面打印的英文印刷图片
1）将碎纸图片转化为1980⨯72的数字矩阵
2）确定附件5中所有碎纸图片中的边界图片，依据为纸张的边界留白更多这一准
则，计算每个矩阵对应列向量和，形成行向量，可将所得行向量元素一次达到最大值的向量所在矩阵对应的碎纸片确定为左边界。
3）又由于所有碎纸图片分为正反两面，每页纸被切为11⨯19个碎片，故经过筛选
之后共得到边界图片22张。其中有11张边界图片为反面的右边界。则这22张碎纸图片可分为11类。每一类的分类标准为两张碎纸图片中字母所在行灰度吻合度最高。依此标准得到的这11类边界分布。
4）每一类的边界有正反两个边界，依据这两张边界图片中字母所占行灰度，在其
他剩余碎纸图片中寻找与之灰度吻合参数最小的作为同一行。由于英文字母本身占格位置的特殊性，误差较汉字来说要大。在进行同行碎纸图片拼接时准确率不高。此时，需引入大量的人工干预来进行拼接工作。
5）经过大量的人工干预，最后我们可以得到：
附件5的拼接顺序为
复原图片见附录图3.1和图3.2
六、模型评价与改进
优点：
1．问题一模型，简单、易操作。适用于单张碎片所含文字信息量大的图片拼接复原；
2．问题二模型，对于碎片上信息量较少，但数量庞大的情况，以减少比对范围来达到理想拼接复原效果，且效率较高；
3．问题三中模型，考虑了现实生活中的所有考虑因素，并运用MATLAB 软件编程得出了结果，应此结果准确性高，误差小，切合生活实际；
4．实现碎纸片拼接技术的计算机化，实现批量拼接，以节省人力和时间。
5．假设合理，模型具有坚实可靠的数学基础。
缺点：
1. 假设条件很多，这就直接导致与实际情况仍有一定的差距，同时许多实际因素尚未纳入考虑的范围之内，没有考虑周全，因此导致一系列计算数据误差较大。
2. 因为缺乏某些现实统计数据的支持，导致人为主观因素在模型的建立计算过程中的影响举足轻重，因此在选择处理方法时也受到条件上的众多限制。故此模型并不完全贴合实际，不利于实际的应用。
3. 由于时间关系，一些改进思路来不及实现。
模型改进：
1. 对于分类不够精确这一问题，我们应用mathematica 软件对英文字母进行识别（程序见附录末），已识别出a , e , o , s , c 这些在英文书写中出现频率较高且仅占用中间行的字母，以此易于定位，可以提高分类的精确度，从而解决了这一问题。
七、参考文献
[1].蔡旭辉 刘卫国 蔡立燕 ，MATLAB 基础与应用教程，人民邮电出版社，2009.8;
[2].尚明姝，基于特征点约束关系的图像拼接算法[J]，电视技术，第36 卷第13 期:2012;
[3]. 姜丽凤 巩建学, 基于特征点的图像拼接算法研究与实现, 电脑开发与应用, 第24 卷 第6期： 2011年;
[4].姜启源，数学模型（第四版），北京：高等教育出版社，2003.8;
[5].罗智中，基于文字特征的文档碎纸片半自动拼接，计算机工程与应用，2012;
[6].方静，基于特征点的图像拼接算法优缺点比较，电脑知识与技术，第9卷，第07期：2013.3。
附录
一：（针对问题一）
附件1图片生成程序：
clc
clear
p=cell(1,18);
for i=1:10
imageName=strcat('I:\题目\附件1\00',num2str(i-1),'.BMP');
p{i} = imread(imageName);
end
for i=11:19
imageName=strcat('I:\题目\附件1\0',num2str(i-1),'.BMP');
p{i} = imread(imageName);
end
sump=[];
Answer=[];
for i=1:19
Answer(i)=i;
end
for i=1:19
sump(i)=(sum(p{i}(:,1))+sum(p{i}(:,2)));
end
A=find(sump==max(sump));
C=Answer(A);
Answer(A)=1;
Answer(1)=C;
B=p{A};
p{A}=p{1};
p{1}=B;
for i=2:19
sump=[];
for j=i:19
a=p{i-1}(:,72);
b=p{j}(:,1);
s=abs(a-b);
sump(j)=sum(s);
for k=1:(i-1)
sump(k)=9999999;
end
end
A=find(sump==min(sump));
C=Answer(A);
Answer(A)=Answer(i);
Answer(i)=C;
B=p{A};
p{A}=p{i};
p{i}=B;
end
Answer-1
q=[p{1}];
for i=2:19
q=[q,p{i}];
end
imshow(q)
附件1复原结果图片：
图1.1
附件2图片生成程序：
clc
clear
p=cell(1,18);
for i=1:10
imageName=strcat('I:\题目\附件2\00',num2str(i-1),'.BMP');
p{i} = imread(imageName);
end
for i=11:19
imageName=strcat('I:\题目\附件2\0',num2str(i-1),'.BMP');
p{i} = imread(imageName);
end
sump=[];
Answer=[];
for i=1:19
Answer(i)=i;
end
for i=1:19
sump(i)=(sum(p{i}(:,1))+sum(p{i}(:,2)));
end
A=find(sump==max(sump));
C=Answer(A);
Answer(A)=1;
Answer(1)=C;
B=p{A};
p{A}=p{1};
p{1}=B;
for i=2:19
sump=[];
for j=i:19
a=p{i-1}(:,72);
b=p{j}(:,1);
s=abs(a-b);
sump(j)=sum(s);
for k=1:(i-1)
sump(k)=9999999;
end
end
A=find(sump==min(sump));
C=Answer(A);
Answer(A)=Answer(i);
Answer(i)=C;
B=p{A};
p{A}=p{i};
p{i}=B;
end
Answer-1
q=[p{1}];
for i=2:19
q=[q,p{i}];
end
imshow(q)
附件2复原结果图片
图1.2
二：（针对问题二）
附件3图片生成程序：
clc
clear
%%%%%%%%%%%%%%%%%%%%%%%%%%读入图片%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% p=cell(1,209);
for i=1:10
imageName=strcat('J:\题目\附件3\00',num2str(i-1),'.BMP');
p{i} = imread(imageName);
end
for i=11:100
imageName=strcat('J:\题目\附件3\0',num2str(i-1),'.BMP');
p{i} = imread(imageName);
end
for i=101:209
imageName=strcat('J:\题目\附件3\',num2str(i-1),'.BMP');
p{i} = imread(imageName);
end
%%%%%%%%定义下标变量%%%%%%%%
Answer=[1:19;20:38;39:57;58:76;77:95;96:114;115:133;134:152;... 153:171;172:190;191:209]
%%%%%%%%%%%%%%%%%%%%%%%%%%找第一列图片%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% sump=[];
for i=1:207
sump(i)=199999-(sum(p{i}(:,1))+sum(p{i}(:,2))+sum(p{i}(:,3))+sum(p{i}(:,4)));
end
[s,firstLine]=sort(sump);
disp('第一列的图片是：')
FL=firstLine(1:11); %%%%FL表示第一列元素，共11个, 及11大类 std=255*72; %一个作为空行标准的数字
yiyong=FL; %定义一个集合，记录应经用过的图片
%%%%%%%%%%%%%%%%%%%%%%%%%%对剩下图片进行分类%%%%%%%%%%%%%%%%%%%%%%%%%%%% for y=1:11
j=FL(y); %j表示第j 个第一列元素
s=sum(p{j},2); %行求和
%%&&%%找第一行非空白的行数%%%%
i=1;
while i
if s(i)==std
i=i+1;
else
a=i; %a即为第一个有字行
break
end
end
%%接着往后找，找第一个有字行字后的空白行%%
while i
if s(i)~=std
i=i+1;
else a1=i; %第一个空白行记为a1
break
end
end
i=i+1;
while i
if s(i)==std
i=i+1;
else a2=i-1;break %最后一个空白行记为a2
end
end
L1=[];
L1(1)=j;
m=2;
for k=1:209
s=sum(p{k},2);
x=0;
for n=a1+2:a2-2
if s(n)==std
x=x+1;
end
end
if x==a2-a1-3
L1(m)=k;%L1就是图片的序号
m=m+1;
end
end
Y=strcat('第',num2str(y),'类可能的图片编号为：'); disp(Y)
L1 %求出了可能为同一行的纸片
L1=[L1(1),setdiff(L1(:),FL(:))'];%除去其中已经用过的的图片 yiyong=[L1,yiyong]; %将用过的图片存在集合yiyong 中
%%%%%%%%%%%%%用第一问的方法横排拼图%%%%%%%%%%%%%%%%%%%%%%%%%%%
z=size(L1,2);
for x=1:z
fank(:,:,x)=p{L1(x)};
end
X=1:z;
for i=2:z
sump=[];
for j=i:z
for w=1:180
a=double(fank(w,72,i-1));
b=double(fank(w,1,j));
s(w)=abs(a-b);
sump(j)=sum(s);
end
for k=1:(i-1)
sump(k)=9999999;
end
end
[b,A]=sort(sump);
C=X(A(1));
X(A(1))=X(i);
X(i)=C;
B=fank(:,:,A(1));
fank(:,:,A(1))=fank(:,:,i);
fank(:,:,i)=B;
end
%%%%%%%%输出图片%%%%%%%%
X-1;
m=[fank(:,:,1)];
for i=2:z
m=[m,fank(:,:,i)];
end
subplot(11,1,y)
imshow(m)
end
length(unique(yiyong))
附件3复原结果图片
图1.3
附件4图片生成程序：
Mathematica 生成0-1列向量
allp={};
Do[{pt={},
Do[
{hang={},
Do[hang=Append[hang,255-pm[[k,i,j,1]]],
{j,ln}],
pt=Append[pt,hang]},
{i,hn}],
allp=Append[allp,pt]},
{k,pn}]
hangh={};
kongh={};
tempk={37,45,89,98,99,100,125,138,190,199};
Do[
{tempp=allp[[tempk[[k]]]];
hang={};
Do[
{temp=Sum[tempp[[i,j]],{j,1,ln}],
If[temp 0,hang=Append[hang,i]]},{i,hn}],
Print[hang],
m=Length[hang]-3;
kong={};
If[hang[[1]] 1,k1=hang[[1]],k1=100],
Do[
{n1=hang[[i]],
n2=hang[[i+1]],
n3=hang[[i+2]],
n4=hang[[i+3]],
If[n2 n1+1&&n4 n3+1&&n3 n2+1,
{If[k1
},{i,m}],
Print[kong],
n=Length[kong]-1;
Do[
{kongh=Append[kongh,kong[[i+1,1]]-kong[[i,2]]],
hangh=Append[hangh,kong[[i,2]]-kong[[i,1]]]
},{i,n}]
},{k,Length[tempk]}]
hanghn=Round[Sum[hangh[[i]],{i,1,Length[hangh]}]/Length[hangh]]
konghn=Round[Sum[kongh[[i]],{i,1,Length[kongh]}]/Length[kongh]]
Matlab 拼出复原图片
clc
clear
%%%%%%%%读入图片%%%%%%%%%%%%
p=cell(1,209);
for i=1:10
imageName=strcat('I:\题目\附件4\00',num2str(i-1),'.BMP');
p{i} = imread(imageName);
end
for i=11:100
imageName=strcat('I:\题目\附件4\0',num2str(i-1),'.BMP');
p{i} = imread(imageName);
end
for i=101:209
imageName=strcat('I:\题目\附件4\',num2str(i-1),'.BMP');
p{i} = imread(imageName);
end
%%%%%%%%%%%%%图片%%%%%%%%%%%%%%%%%%%
Answer=[191,075,011,154,190,184,002,104,180,064,106,004,149,032,204,065,039,067,147;...
201,148 170 196 198 094 113 164 078 103 091 080 101 026 100 006 017 028 146;... 086 051 107 029 040 158 186 098 024 117 150 005 059 058 092 030 037 046 127;... 019 194 093 141 088 121 126 105 155 114 176 182 151 022 057 202 071 165 082;... 159 139 001 129 063 138 153 053 038 123 120 175 085 050 160 187 097 203 031;... 020 041 108 116 136 073 036 207 135 015 076 043 199 045 173 079 161 179 143;... 208 021 007 049 061 119 033 142 168 062 169 054 192 133 118 189 162 197 112;... 070 084 060 014 068 174 137 195 008 047 172 156 096 023 099 122 090 185 109;... 132 181 095 069 167 163 166 188 111 144 206 003 130 034 013 110 025 027 178;... 171 042 066 205 010 157 074 145 083 134 055 018 056 035 016 009 183 152 044;... 081 077 128 200 131 052 125 140 193 087 089 048 072 012 177 124 000 102 115;] Answer=Answer+1;
Answer=Answer';
i=0;
m0=[];
for j=i*19+1:(i+1)*19
m0=[m0,p{Answer(j)}];
end
i=1
m1=[];
for j=i*19+1:(i+1)*19
m1=[m1,p{Answer(j)}];
end
i=2;
m2=[];
for j=i*19+1:(i+1)*19
m2=[m2,p{Answer(j)}];
end
i=3;
m3=[];
for j=i*19+1:(i+1)*19
m3=[m3,p{Answer(j)}];
end
i=4;
m4=[];
for j=i*19+1:(i+1)*19
m4=[m4,p{Answer(j)}];
end
i=5;
m5=[];
for j=i*19+1:(i+1)*19
m5=[m5,p{Answer(j)}];
end
i=6;
m6=[];
for j=i*19+1:(i+1)*19
m6=[m6,p{Answer(j)}];
end
i=7;
m7=[];
for j=i*19+1:(i+1)*19
m7=[m7,p{Answer(j)}];
end
i=8;
m8=[];
for j=i*19+1:(i+1)*19
m8=[m8,p{Answer(j)}];
end
i=9;
m9=[];
for j=i*19+1:(i+1)*19
m9=[m9,p{Answer(j)}];
end
i=10;
m10=[];
for j=i*19+1:(i+1)*19
m10=[m10,p{Answer(j)}];
end
m=[m0;m1;m2;m3;m4;m5;m6;m7;m8;m9;m10];
imshow(m)
附件4复原结果图片：
图1.4
a=cell(1,208);
for i=1:10
imageName=strcat(' I:\题目\附件5\00',num2str(i-1),'a.BMP');
a{i} = imread(imageName);
end
for i=11:100
imageName=strcat(I:\题目\附件5\0',num2str(i-1),'a.BMP');
a{i} = imread(imageName);
end
for i=101:208
imageName=strcat(' I:\题目\附件5\',num2str(i-1),'a.BMP');
a{i} = imread(imageName);
end
b=cell(1,208);
for i=1:10
imageName=strcat(' I:\题目\附件5\00',num2str(i-1),'b.BMP');
b{i} = imread(imageName);
end
for i=11:100
imageName=strcat(' I:\题目\附件5\0',num2str(i-1),'b.BMP');
b{i} = imread(imageName);
end
for i=101:208
imageName=strcat(' I:\题目\附件5\',num2str(i-1),'b.BMP');
b{i} = imread(imageName);
end
图3.1
图3.2
Mathematica---识别a,e,o,s,c 的位置
SetDirectory["e:\\hr\\b\\附件4"];
pm=Table[file=Which[sFromCharacterCode[IntegerDigits[s]+48],10 s FromCharacterCode[IntegerDigits[s]+48],s>=100,FromCharacterCode[I
ntegerDigits[s]+48]];Import[file".bmp","Data"],{s,0,208}]
hn=Length[pm[[1]]]
ln=Length[pm[[1,1]]]
pn=Length[pm]
allp={};
Do[{pt={},
Do[
{hang={},
Do[hang=Append[hang,pm[[k,i,j,1]]],
{j,ln}],
pt=Append[pt,hang]},
{i,hn}],
allp=Append[allp,pt]},
{k,pn}]
SS=Import["E:\\hr\\data\\字母\\s.xls"];
ahn=Length[AA];
aln=Length[AA[[1]]];
pps=0.99
k=10;
seat={};
Do[
Do[
{n=Sum[allp[[k,i+l-1,j+m-1]]*AA[[l,m]],{l,1,ahn},{m,1,aln}]/Sqrt[Sum[allp[[k,i+l-1,j+m-1]]^2,{l,1,ahn},{m,1,aln}]]/Sqrt[Sum[AA[[l,m]]^2,{l,1,ahn},{m,1,aln}]],
If[n pps,{a={i,j},seat=Append[seat,a]}]
},{j,ln-aln}],{i,hn-ahn}]
chn=Length[CC];
cln=Length[CC[[1]]];
Do[
Do[
{n=Sum[allp[[k,i+l-1,j+m-1]]*CC[[l,m]],{l,1,chn},{m,1,cln}]/Sqrt[Sum[allp[[k,i+l-1,j+m-1]]^2,{l,1,chn},{m,1,cln}]]/Sqrt[Sum[CC[[l,m]]^2,{l,1,chn},{m,1,cln}]],
If[n pps,{a={i,j},seat=Append[seat,a]}]
},{j,ln-cln}],{i,hn-chn}]
ehn=Length[EE];
eln=Length[EE[[1]]];
Do[
Do[
{n=Sum[allp[[k,i+l-1,j+m-1]]*EE[[l,m]],{l,1,ehn},{m,1,eln}]/Sqrt[Sum[allp[[
k,i+l-1,j+m-1]]^2,{l,1,ehn},{m,1,eln}]]/Sqrt[Sum[EE[[l,m]]^2,{l,1,ehn},{m,1,eln}]],
If[n pps,{a={i,j},seat=Append[seat,a]}]
},{j,ln-eln}],{i,hn-ehn}]
ohn=Length[OO];
oln=Length[OO[[1]]];
Do[
Do[
{n=Sum[allp[[k,i+l-1,j+m-1]]*OO[[l,m]],{l,1,ohn},{m,1,oln}]/Sqrt[Sum[allp[[k,i+l-1,j+m-1]]^2,{l,1,ohn},{m,1,oln}]]/Sqrt[Sum[OO[[l,m]]^2,{l,1,ohn},{m,1,oln}]],
If[n pps,{a={i,j},seat=Append[seat,a]}]
},{j,ln-oln}],{i,hn-ohn}]
shn=Length[SS];
sln=Length[SS[[1]]];
Do[
Do[
{n=Sum[allp[[k,i+l-1,j+m-1]]*SS[[l,m]],{l,1,shn},{m,1,sln}]/Sqrt[Sum[allp[[k,i+l-1,j+m-1]]^2,{l,1,shn},{m,1,sln}]]/Sqrt[Sum[SS[[l,m]]^2,{l,1,shn},{m,1,sln}]],
If[n pps,{a={i,j},seat=Append[seat,a]}]
},{j,ln-sln}],{i,hn-shn}]
seat
- 31 -