到最小，则称C与D可以匹配，此时C与D对应的图片可以上下拼接。
我们称上述基于数字矩阵之间列（或行）距离的图片拼接模型为最小二乘法拼接复原模型。
5.1.4算法与求解
（一）算法思想
第一步，对附件中的19幅图片分别进行灰度处理，然后取灰度阈值T?125，进行二值化，得到19个0,1数字矩阵，即图片的数字化。
第二步，对上述19个数字矩阵进行检测，若存在一个矩阵的最左侧一列元素全是1，根据破碎图片的特点，则该图片即为从左边起第一张碎纸片，记为A1。
第三步，计算A1与其余18张图片对应矩阵的列偏差值。
1980i?1f(A1,B)???A1(i,72)?B(i,1)?2,
A2即位第二张图片。 若存在A2，使得f(A1,A2)达到最小，则
重复上述的步骤，依次得到所有碎纸片的排列，即可拼接成完整图片。 （二）附件1、2的拼接复原结果 附件1和附件2的拼接顺序如下表：（附件1的算法程序见附录一，复原图片见附录二；附件2的算法程序见附录三，复原图片见附录四）
表2 附件1拼接顺序
8 14 12 15 3 10 2 16 1 4 5 9 13 18 11 7 17 0 6 表3 附件2拼接顺序
3 6 2 7 15 18 11 0 5 1 9 13 10 8 12 14 17 16 4 5.2问题二的模型建立与算法 5.2.1图片的数字化处理
步骤一：将附件所给的BMP格式图片转换成JPG格式的图片； 步骤二：对图片进行灰度处理； 步骤三：然后进行二值化处理；
最后，得到209张图片的数字化矩阵。 5.2.2聚类分析
对于碎纸机既纵切又横切的情形，与问题一仅纵切相比，图片变小，因而每张图片
6
包含的信息量明显变小，如果仅利用最小二乘法，碎片之间的匹配不唯一。为了解决这个问题，我们利用聚类分析法，对碎片先进行分类。
经观察测试，原始文档碎片具有下列特点：
（1）字体大小：字体的最大高度和最大宽度一致。
（2）切割的均匀性：同方向的切割线平行，图片大小均相等，沿纵横方向按直线切割。
（3）文字的行距：文字的行间距等同，段落间距为定值。
为了对209幅图片进行聚类分析，如图2所示，我们定义聚类指标如下：
ai表示图片上端裁接处的字体长度，我们称之为裁截文字长度； bi为行间距；ci表示图片上端文字与切割线之间的空白距离，我们称之为裁截空白距离；di为字体高度，其中，i=1,2,?,209。
图2 图片聚类指标示意图
令Di?ai?bi或Di?ci?di，称Di为第i张图片的裁截距(i=1,2,?,209)，
由图2，如a1?a2,b1?b2，则D1?D2。一般地，图片从上往下看，不同的裁截线形成的裁截文字长度不同，文字间的行间距相同，所以，如果裁接处的文字长度不相等，那么文字与空白间距之和就不相等。根据Di的不同取值，下面对图片进行分类。
根据二值化矩阵的特点以及文字的特征，只要存在文字，则矩阵的某一行元素一定存在0元素，且在文字之间的元素为1。如下图所示：
图3 文字特征图
利用matlab软件进行编程，将每个图片的裁截文字长度、行间距、裁截空白距离、字体高度以及裁截距的结果以excel的形式输出到表格之中。（程序见附录五）
按裁接距进行聚类分析，使用spss软件分析处理后，得到聚类中心分布图如下所示：
7
表4 聚类中心 聚类中心 1 V1 7 2 52 3 32 4 120 5 44 聚类 6 58 7 133 8 64 9 109 10 69 11 78 根据表4所示的聚类中心，对表格中裁截距进行初步分类。得到聚类结果如下表所示：
表5 每个聚类中的案例数
每个聚类中的案例数 聚类 1 2 3 4 5 6 7 8 9 10 11 有效 缺失 2.000 36.000 18.000 1.000 46.000 38.000 1.000 36.000 1.000 11.000 19.000 209.000 .000 根据聚类结果发现，并不能将图片平均分成11个组。这时需要增加信息量来更好地进行分类，进一步观察图2，我们可以发现：图片的上端裁截处可能是文字，也可能为空白。但是裁截距Di可能相等，此时通过图片上端裁截处是空白还是文字加以人工分类。
用matlab将数据导出到excel中并进行分析，结果如下：
50 0 高度 0 -50 -100 图片数量 图4 分析结果
8
50 100 150 200 250
由图4可以看出：图片大体分为11个组别，为了得到更精确地聚类结果，通过spss软件，我们再次确立聚类中心如下图所示：
表6 第二次聚类中心 最终聚类中心 聚类 1 V1 25 2 2 3 40 4 -38 5 -93 6 -69 7 -84 8 15 9 34 10 -23 11 -10 通过上面两次聚类，确立了两个不同聚类中心。利用第一次确立的裁接距的聚类中心对图片进行初步分类，然后利用裁截文字或者裁接空白再次进行判别，最终将图片分成了11组。如下表所示：（以上的算法都是在matlab软件下操作，程序见附件六）
表7 各组图片数量 组别 0 图片3 数量 1 18 2 8 3 19 4 19 5 18 6 18 7 19 8 18 9 18 10 18 11 10 12 19 13 3 由上表可以看出大部分图片已经分出组别，其中有4个组达到了19张图片，有6个组有18张图片，仅缺少一张图片。此时我们进行人工干预，根据每组图片总数目应为19，且每类都应存在可作为文件左右边缘的碎纸片，我们对少量图片进行归类可得到如下分组结果。如下表：
表8 聚类后的结果
组别 1 2 11 22 28 49 54 57 65 91 95 118 129 141 143 178 186 188 190 192 2 6 19 20 36 52 61 63 67 69 72 78 79 96 99 116 131 162 163 177 3 1 18 23 26 30 41 50 62 76 86 87 100 120 142 147 168 179 191 195 4 8 9 24 25 35 38 46 74 81 88 103 105 122 130 148 161 167 189 193 5 3 12 14 31 39 51 73 82 107 115 128 134 135 159 160 169 176 199 203 9 6 34 42 43 47 58 77 84 90 94 97 112 121 124 127 136 144 149 164 183 7 13 16 21 66 106 109 110 125 139 145 150 157 173 181 182 184 187 197 204 8 5 10 29 37 44 48 55 59 64 75 92 98 104 111 171 172 180 201 206 9 0 7 32 45 53 56 68 70 93 126 137 138 153 158 166 174 175 196 208 10 15 17 27 33 60 71 80 83 85 132 133 152 156 165 170 198 200 202 205 11 4 40 89 101 102 108 113 114 117 119 123 140 146 151 154 155 185 194 207 图 片 编 号
5.2.3图片的拼接模型、算法与求解
（一）算法思想
下面我们分两步来做，第一步，对每组碎纸片进行拼接；第二步，将各组进行拼接。最终完成文件复原。
在已知文件切为11×19的碎纸片情况下，将图片进行聚类分析得到了11个组后。利用碎纸片左右边缘为空白的特点判断出文件左侧11个碎纸片，再利用问题一模型和算法，对每个组进行匹配拼接，可得到11个拼接好的图片，之后仍然按照问题一的模型和算法将这11张图片拼接成完整的图片。
（二）图片的左边缘确定 根据碎纸片边缘特征，利用matlab对图片处理后得到数字化矩阵，根据最小二乘法进行分析得到16个可作为文件左边缘的碎纸片，编号如下：（程序详见附录七）
7，14，29，38，49，61，62，67，71，80，89，94，125，135，143，168。 已知文件分为11×19的碎纸片,那么存在5个不是左边缘碎纸片。根据文件页边距一定的特点，此时进行人工筛选，明显排除了编号分别62，67，80，135，143的图片作为文件左边缘的可能。此刻，我们也得到了左边缘碎纸片的序号：
7，14，29，38，49，61， 71，80，89，94，125，168。 （三）图片的各组拼接
第一步，计算机处理，利用问题一的列偏差函数进行图片拼接，现在我们以表4中的第9组为例，，得到如下结果：（程序详见附录八）
图6 以第9组为例的拼接结果1
第二步，人工干预，由于每组有19个图片，可以明显观察到排序的时候有一个图片没有出现，而且另一个图片重复出现了两次。此时我们进行人工拼接。得到正确的拼接结果，图片如下：
图7 以第9组为例的拼接最终结果
其余分组按照相同方法可得到11组的拼接结果，这里我们不在一一赘述，发现每组的拼接均无误，这说明我们的分类达到了预期的效果。
10
2013全国数学建模竞赛B题优秀论文
