nbhkdz.com冰点文库

2013年B题全国数学建模二等奖论文(原创)

时间:2013-10-06


碎纸片的拼接复原
摘要

破碎文件的拼接在司法物证复原、 历史文献修复以及军事情报获取等领域都有着重要的 应用。但是人工完成效率很低,所以引入计算机复原,计算机虽然准确率不及人工高,但是 可以大大减轻工作强度。 本论文主要是对纸张形状为矩形切割规范并且纸张上的文字标准的 碎纸片的拼接复原的研究。 问题一:首先根据图片的灰度矩阵找出第一张(最左侧)图片,根据小差值优先匹配依 次排出相邻图片。碎纸片复原后的顺序如附件一、二所示。 问题二: 首先根据图片的灰度矩阵最左侧 n 列灰度值求和最大, 可找出第一列 (最左侧) 图片,共 11 张。根据 “行间”的位置特征作为凝聚点进行聚类分析,将所有图片分为 11 类,即 11 行。应用小差值优先匹配将这每行的图片进行拼接,得到 11 个行图片,再次应用 小差值优先匹配把这 11 个行图片拼接成完整的图片。碎纸片复原后的顺序如附件三、四所 示。 问题三:同问题二方法一致,找出第一列(最左侧)图片(正反两面共有 22 张图片) , 将这些“行间”的位置特征作为凝聚点进行聚类分析,所有的图片分为 11“大行” ,将这些 图片配对的正反面进行上边缘“粘接”处理,按照小差值优先匹配将这每行的粘接形成的 19 图片(如图一所示)进行拼接,得到 11 个行图片之后,再次应用小差值优先匹配把这 11 个行图片拼接成完整的图片。碎纸片复原后的顺序如附件五所示。 观察上述三个问题的处理方法可知, 三个问题的解决办法主干思想完全相同, 都是小差 值优先匹配解决,并且清晰简练。但是由于问题的逐渐深入和复杂程度的增加,仅靠这一个 简单的方法并不能在实际中解决问题,于是增加约束条件减小搜索范围,如:找出“行间” 位置,并作为凝聚点进行聚类分析,然后就可以很大程度上减小出错的概率。

关键词:聚类分析、MATLAB R2012a、小差值优先匹配、灰度矩阵

1

1、问题重述

破碎文件的拼接在司法物证复原、 历史文献修复以及军事情报获取等领域都有着重要的 应用。传统上,拼接复原工作需由人工完成,准确率较高,但效率很低。特别是当碎片数量 巨大,人工拼接很难在短时间内完成任务。随着计算机技术的发展,人们试图开发碎纸片的 自动拼接技术,以提高拼接复原效率。请讨论以下问题: (1). 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片(仅纵切) ,建立碎纸片 拼接复原模型和算法,并针对附件 1、附件 2 给出的中、英文各一页文件的碎片数据进行拼 接复原。如果复原过程需要人工干预,请写出干预方式及干预的时间节点。复原结果以图片 形式及表格形式表达(见【结果表达格式说明】。 ) (2). 对于碎纸机既纵切又横切的情形,请设计碎纸片拼接复原模型和算法,并针对 附件 3、附件 4 给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人 工干预,请写出干预方式及干预的时间节点。复原结果表达要求同上。 (3). 上述所给碎片数据均为单面打印文件,从现实情形出发,还可能有双面打印文 件的碎纸片拼接复原问题需要解决。 附件 5 给出的是一页英文印刷文字双面打印文件的碎片 数据。 请尝试设计相应的碎纸片拼接复原模型与算法, 并就附件 5 的碎片数据给出拼接复原 结果,结果表达要求同上。

2、问题分析
分析本问题可知, 第一问是解决此类问题的基本方法, 第二问及第三问相比第一问逐渐 变得复杂, 但主要解决思路与第一问相同, 只是在第一问的基础上需要应用其他方法缩小搜 索范围,但主体方法并未改变。 针对问题一:对于给定的来自同一页印刷文字文件的碎纸机破碎纸片(仅纵切) ,建立 碎纸片拼接复原模型和算法。 MATLAB 软件[1][2]中应用 imread 函数读取附件一及附件二中 在 的图片,可以获得相应的灰度矩阵,从矩阵中可以清楚地看到图片中每个像素的灰度值。观 察图片边缘及灰度矩阵边缘可以得出: 图片被切割后会在这张图片被切割两侧生成相似的两 个列矩阵,可以猜测这两个列矩阵相似程度越高则这两张图片可以拼接复原的概率就越大。 为表示两列矩阵的相似程度, 对这两列矩阵进行对应行相减取绝对值最后求和, 所求得的和 越小两矩阵越相似即复原概率越大。 最左边一张图片的最左侧全为空白, 即最左侧矩阵所有
2

行求和值最大,可以得到最左侧的图片,然后可以拼接出整张图片。 针对问题二:对于碎纸机既纵切又横切的情形,请设计碎纸片拼接复原模型和算法。 方法一: 应用第一问中的小差值优先匹配, 求出所有图片边缘矩阵的对应行相减取绝对 值最后求和,然后逐个比较,此时会发现由于图片小且图片中字数较少,灰度矩阵所给出的 信息就会比较少, 并且应用小差值优先匹配所求和会有大量数值相差不是很大图片出现, 出 现过多的候选项,这会对判断哪张图片可以复原产生很大的影响,甚至会出现无法选择,因 为部分图片是正好没有切割文字, 此时计算机是无法判断哪张可以复原的, 就需要对方法一 进行补充提供更多的约束条件或是进行人工干预,所以得出了以下的方法二。 方法二:此方法主体方法也是应用小差值优先匹配,针对上述出现过多的候选项情况, 观察附件三及附件四中的图片会发现, 虽然所给的图片小且文字数目少, 但是观察可知这些 图片全部大小一致但是“行间” (两行文字之间的空白处)所出现的位置是不同的,记录这 几行的位置,将其余图片所生成的矩阵对比,若特殊的几行出现在相同的位置,则可将这些 图片分为一“大行” (这些图片的行间距出现的位置相同) 。然后将“大行”内的图片应用第 一问中的小差值优先匹配进行拼接,可将这些行拼出。紧接着人工干预将所得的行分为 11 行(如果所得到的行多余 11 行) ,最后将这是 11 行转置成 11 列,按照第一问的方法进行即 可拼出完整的图片。 针对问题三:该问题比第二问更复杂,但是更贴合于实际情况,即实用性很强。仔细观 察附件 5 中的图片,可以观察到,每张图片的 a 面和 b 面, “行间”所处的位置是相同的。 这样,可以“行间”所处的位置进行聚类,聚为 11 类,同第二问方法一样,先分行,然后 再每行拼接出来,转置成列,应用小差值优先匹配将这 11 列拼接,即可得出完整图片。 但是行分完后,猜测每行有英语碎纸片,由于英文字母本身所能获得的信息量较少,且 每行的图片过多,在按照第二种方法处理时,会出现过多接近值,甚至会出现错误排列, 再仔细观察及阅读题意可以得出, 一行图片的正面确定且结果正确时, 反面是自然形成 的,这样就只用到了一面数据量,若此时将两张图片的正反面以上边缘相接展开,形成高度 是原高两倍的行图片,这样就会同时应用到正反两面的边缘数据,提高筛选时的准确率。同 理,在每一行都拼完后,在进行“大行”相拼的时候,可以将这个行的正反两面以右边缘相 接展开, 又会形成长度是原长两倍的行, 也同时应用到正反两面的边缘数据提高筛选时的准 确率。

3

得到图形如一所示:

…a …b

…a(b) …a(b) …a (b)…a (b) …b(a) …b(a) …b (a)…b (a)
图一(正反面粘接)

按照如上图片正反连接在一起后应用小差值优先匹配加以适当的人工干预, 拼出完整行 图片。这样可以确定 11 张行图片,将这 11 张图片转置成 11 个列图片,之后再次应用小差 值优先匹配拼出完整图片。

3、模型假设
(1)假设所有复原图片中位于同一面的文字的行间距相同。 (2)假设页面上的文字全部是统一字体且页面排版相同。 (3)假设页面整洁干净无黑点等干扰项。 (4)第一列文字距离纸张左边缘的距离大于两相邻文字间的距离。

4、符号说明及名词定义
符号说明: k: 第 k 张图片 n: 图片具有 n 行 I: 两张图片边缘拼接能力,值越小,越容易拼接。

Ak :第 k 张图片所对应的灰度矩阵。

AK (i, j ) ; AK 矩阵的第 i 行第 j 列所对应的元素。
名词定义: “行间” 相邻两行文字之间固定存在的空白区域, : 即文字排版时所设计的隔开每行的
4

空白区域。它与这行中是否存在文字无关。 小差值优先匹配: 在 n 张图片中取出每张图片的最左和最右侧的两个列灰度矩阵, 然 后任一两张图片进行下列运算: 第一张图片的最右侧矩阵与第二张图片的最左侧灰度矩阵对 应行相减,取绝对值最后求和,这个值越小,表明这两张图片边缘灰度值越接近,即两张图 片的边缘小差值优先匹配,拼接的概率越大。

5、模型建立与求解
5.1 第一问模型建立与求解: 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片(仅纵切) ,建立碎纸片拼接复 原模型和算法。 在 MATLAB 软件中应用 imread 函数[1] [2]读取附件一中的 19 张图片, 得到 19 个灰度矩阵

A k (i, j ), (k ? [a, b], i ? [1, n], k ? [1, m]) 。
建立目标函数为:

? ? n ? max ?? Ak ?i ,1? ? ( k ? 1) ? a ? k ?b ? ? i ?1 ? Ik ? ? ? n ? ? min Ak1 ?i , n ? ? Ak ?i ,1? ? ? ??a ? k ? k1 ?? ? k1 ? k ? k 2 ??...? ? k i ? k ? b ??? i ?1 ? ?
······························(1) ······························ 按算法如下: (1) 找出第一张图片:

( k ?1)

?n ? I 1 ? max ?? Ak ?i ,1? ? a ? k ?b ? i ?1 ?

················ ···············(2)

因为一张完整纸张上的字体第一列都会距离页面最左端有一定的距离以方便阅读和美 观,所有最左边的图片最左端会对应一列全白,即所生成的矩阵第一列全为 255,此时对该 矩阵所有行求和会得到最大值 504900。应用以上结论,对所有图片的灰度矩阵第一列进行 求和,所得值最大的即为最左边一张照片,即

?n ? I 1 ? m a x ? Ak ?i ,1? ? 。对所有图片的灰 ? a ? k ?b ? i ?1 ?

度矩阵第一列进行求最大值的结果为第 008 张图片为最左边一张图片。
5

(2) 找出第 k 张照片:

?n ? Ik ? min Ak1 ?i , n ? ? Ak ?i ,1? ? ? ? a ? k ? k1 ?? ? k1 ? k ? k 2 ??...? ? k i ? k ? b ? ? ? i ?1 ?
················ ···············(3) 观察图片边缘及灰度矩阵边缘可以得出:图片被切割后会在这张图片被切割两侧生成 两个相似的列矩阵,即这两个列矩阵相似程度越高则这两张图片可以拼接复原的概率就越 大,这里将此方法命名为小差值优先匹配。 为比较图片边缘相似程度,将所有图片的最左侧及最右侧矩阵取出,即 Ak ?i ,1? 和 Ak ?i , 72 ? 对这两列矩阵进行对应行相减取绝对值最后求和, 所求得的和越小两矩阵越相似, 即匹配概

?n ? min ? Ak ?i ,1? ? (k=2) 率越大,即 I k ? 。[3]此时和最小的即 ? A ?a ? k ? k1 ??? k1 ? k ? k 2 ??...?? ki ? k ?b ? ? k1 ?i , n ? ? i ?1 ?
为第 2 张图片。 以此类推,应用程序 1 即可求出第 3、4、5……19 张图片。 顺序如表格一所示: 表格一 8 14 12 15 3 10 2 16 1 4 5 9 13 18 11 7 17 0 6

(3)MATLAB 拼接 19 张图片 由程序 2 所求出图片顺序在 MATLAB 中用 imtool 函数[4]将图片按顺序合并。完整图片 的排列顺序即完整图如附件一所示。 第一问中的英文图片按上述(1) (2) (3)操作即可得出合并后的图片。完整图片的排 列顺序即完整图如表格二所示。 表格二

3

6

2

7

15

18

11

0

5

1

9

13

10

8

12

14

17

16

4

运行程序二即为按照上述步骤操作后得出的完整图片。

6

5.2 第二问模型建立与求解: 对于碎纸机既纵切又横切的情形,请设计碎纸片拼接复原模型和算法,并针对附件 3、 附件 4 给出的中、英文各一页文件的碎片数据进行拼接复原。 根据第一问模型改进后建立第二问目标函数为:

? ?n q ? max ??? Ak ?i , p ? ? ? a?k ?b ? ? i?1 p?1 ? ? ? Ik ? ? min ?Dkp , Dkq ? ? ?n ? min Ak1 ?i ,n ? ? Ak ?i ,1? ? ? ? ?a?k ? k1 ??? k1 ? k ? k2 ??...??ki ? k ?b ? ? ? ? i?1 ? ? ?
················ ···············(4) 要解决这个问题,要将这些碎纸片首先按照一定特征聚类,缩小搜索范围,应用到的 这种方法叫做聚类分析。 5.2.1 聚类分析 [5] :聚类分析(cluster analysis)是一组将研究对象分为相对同质的群组 (clusters)的统计分析技术。 聚类分析区别于分类分析(classification analysis) ,后者是有监 督的学习。 选取若干个样品作为凝聚点,计算每个样品和凝聚点的距离,进行初始分类,然后根 据初始分类计算其重心,再进行第二次分类,一直到所有样品不再调整为止。动态聚类法计 算简单, 分类迅速, 占用计算机内存少, 特别是当样品数较大时, 采用动态聚类法比较有利; 但动态聚类法的分类结果与最初凝聚点的选择有关, 有较大的不确定性。 聚类过程如图二所 示:

选凝聚点

初始分类

分类是否合理

最终分类

修改分类 图二 本题中所应用到的聚类方法为:最短距离法,此论文中,为便于理解,将最短距离理
7

解为灰度值接近,即两边缘小差值优先匹配,记为小差值优先匹配。 以下用 d ij 表示样品 X i 与 X j 之间距离, Dij 表示类 Gi 与 G j 之间的距离。 用 定义类 Gi 与

G j 之间的距离为两类最近样品的距离,即
Dij ?
Gi ?Gi ,G J ?G j

min

d ij

················ ···············(4)

设类 G p 与 G q 合并成一个新类记为 G r ,则任一类 G k 与 G r 的距离是:

Dkr ?

X i ?Gi , X j ?G j

min

d ij ? min ? min d ij , min d ij ? ? min ?Dkp , Dkq ? ? X ?G , X ?G ? X i ?Gk , X j ?Gq ? i k j p ?
················ ···············(5)

最短距离法聚类的步骤如下: (1)定义样品之间距离,计算样品两两距离,得一距离阵记为 D( 0) ,开始每个样品自 成一类,显然这时 Dij ? d ij 。 (2)找出 D( 0) 的非对角线最小元素,设为 D pq ,则将 G p 和 G q 合并成一个新类,记为

G r ,即 Gr ? ?G p , Gq ?。
(3)给出计算新类与其它类的距离公式:

Dkr ? min ?Dkp , Dkq ?

················ ···············(6)

将 D( 0) 中第 p、q 行及 p、q 列用上面公式并成一个新行新列,新行新列对应 G r ,所得 到的矩阵记为 D(1) 。 (4)对 D(1) 重复上述对 D( 0) 的(2)(3)两步得 D( 2) ;如此下去,直到所有的元素并 、 成一类为止。如果某一步 D(k ) 中非对角线最小的元素不止一个,则对应这些最小元素的类 可以同时合并。 最短距离法也可用于指标(变量)分类,分类时可以用距离,也可以用相似系数。但 用相似系数时应找最大的元素并类, 也就是把公式 Dik ? min( Dip , Diq ) 中的 min 换成 max。

8

按算法解决步骤如下: 5.2.2 对于碎纸机既纵切又横切的情形,请设计碎纸片拼接复原模型和算法,观察附件 三中的图片,可以发现这些图片存在以下两个规律: (1)一些图片的整个左端有很大一部分空白,初步参测这几张图片为整张图片的第一 列。 将附件三中的 209 张图片用 MATLAB 用 imread 函数读出 209 个灰度矩阵,因为这些图 片的整个左端有很大一部分空白,所以这几张图片前 11 列都是灰度值 255,对这 11 列所有 的元素进行求和可得 255*11*180=504900,然后对所有图片的前 11 列求和 值为 504900 的所有图片,
[7][8]

,并筛选出数

?n ? I ? max ?? Ak ?i ,1? ?(k ? 1) a ? k ?b ? i ?1 ?
并将这些图片作为第一列。筛选结果如下

···············(7) ···············

007、014、029、038、049、061、071、089、 、094、125、168(.bmp)这 11 张图片构 成了完整图片的第一列。 (2)这 209 图片全部大小一致但是行间距(两行文字之间的空白)所出现的位置是不 同的, “行间”出现的位置不同且只有固定的几种。表现在灰度矩阵中就是整个同一行的图 片会出现相同的某几行数值全为 255,对这些矩阵进行行求和,利用 MATLAB 将值为 19*255=4854 的行记为 1 [9],值小于 4854 的记为 0,可以清晰的得出“行间”的位置,在 此处记录两个完整的“行间” ,利用这些位置特征将这 209 张图片分为 11 类,即 11“大行” 。

Dkr ? min ?Dkp , Dkq ?
MATLAB 实现分“大行”过程: 将附件 3 中求出的 209 图片,全部进行每行求和,并利用 MATLAB 将值为 19*255=4854 的行记为 1,值小于 4854 的记为 0,可以得出这 209 张图片的“行间”位置记录矩阵。将 以上 11 张图片的“行间”位置作为参考,利用这些图片分成 11 行。由于图片较小从中能获 取的数据量较少, 所以再用小差值优先匹配后会的发现拼错的概率比较大, 所以在此对模型 进行改进,同上,找出图片最右侧一列,然后从右往左开始拼接,最后将这两列图片合并选 取各种准确的排列,如此,可以降低排列出错的概率。 (3)对这 11 行中的 19 张图片,进行行方向上的拼接。
9

应用上述聚类分析最短距离分析中提出的小差值优先匹配进行拼接,由于纸片较小可 以获得的信息量非常少,尽管已经将范围缩小到 19 张,但是仍然会出现拼接错误出现如下 图一所示情况:

图一

然后,按照上述方法找出最右侧图片,从右往左拼接图片如图二所示 图二

观察可以看出图一图二均出现了四处拼接错误, 但两张可以拼出完整的一行, 即此时需要进 行人工干预,干预方式:比较两张图片,排出正确的顺序。后面生成的图片中有少量会出现 错误,干预方式及干预时间与上述图片相似,这里不再重复叙述 (4)对折 11 张“行纸片”进行列方向上的拼接。 对这是一个行纸片转置又形成 11 个列纸片,再次应用小差值优先匹配,即可将这 11 列纸片拼接为完整的一张纸。完整图片的排列顺序即完整图如附件三所示。 运行程序四即为按照上述步骤操作后得出的完整图片。 (5)附件 4 中的英文纸片重复上述步骤(1) (3(4) (2) ,即可得出复原后的图片。完 整图片的排列顺序即完整图如表格三和表格四所示。 表格三 49 61 54 19 65 78 143 67 186 69 2 99 57 162 192 96 178 131 118 79
10

190 63

95 116

11 163

22 72

129 6

28 177

91 20

188 52

144 36

168 38 14 94 125 29 7 71 89

100 148 128 34 13 64 208 156 146

76 46 3 84 182 111 138 83 102

62 161 159 183 109 201 158 132 154

142 24 82 90 197 5 126 200 114

30 35 199 47 16 92 68 17 40

41 81 135 121 184 180 175 80 151

23 189 12 42 110 48 45 33 207

147 122 73 124 187 37 174 202 155

191 103 160 144 66 75 0 198 140

50 130 203 77 106 55 137 15 185

179 193 169 112 150 44 53 133 108

120 88 134 149 21 206 56 170 117

86 167 39 97 173 10 93 205 4

195 25 31 136 157 104 153 85 101

26 8 51 164 181 98 70 152 113

1 9 107 127 204 172 166 165 194

87 105 115 58 139 171 32 27 119

18 74 176 43 145 59 196 60 123

表格四 191 201 086 019 159 020 208 070 132 171 081 075 148 051 194 139 041 021 084 181 042 077 011 170 107 093 001 108 007 060 095 066 128 154 196 029 141 129 116 049 014 069 205 200 190 198 040 088 063 136 061 068 167 010 131 184 094 158 121 138 073 119 174 163 157 052 002 113 186 126 153 036 033 137 166 074 125 104 164 098 105 053 207 142 195 188 145 140 180 078 024 155 038 135 168 008 111 083 193 064 103 117 114 123 015 062 047 144 134 087 106 091 150 176 120 076 169 172 206 055 089 004 080 005 182 175 043 054 156 003 018 048 149 101 059 151 085 199 192 196 130 056 072 032 026 058 022 050 045 133 023 034 035 012 204 100 092 057 160 173 118 099 013 016 177 065 006 030 202 187 079 189 122 110 009 124 039 017 037 071 097 161 162 090 025 183 000 067 028 046 165 203 179 197 185 027 152 102 147 146 127 082 031 143 112 109 178 044 115

运行程序五即为按照上述步骤操作后得出的完整图片。 (见附录)

5.3 第三问模型建立与求解: 上述所给碎片数据均为单面打印文件, 从现实情形出发, 还可能有双面打印文件的碎纸 片拼接复原问题需要解决。 附件 5 给出的是一页英文印刷文字双面打印文件的碎片数据。 请 尝试设计相应的碎纸片拼接复原模型与算法 根据前两问的模型改进优化后建立第三问目标函数:

?n q ? I k1 ? max ??? Ak ?i , p ? ? a ? k ?b ? i ?1 p ?1 ?

···············(8) ···············

11

I k ? min ?Dkp , Dkq ?

··············· ··············(9)
m

I k ? ?? Ak ( i , j ) ? ?? Ak ( i , j )
i ?t1 j ?1 i ?t3 j ?1

t2

m

t4

( k ? k1 ) ··········· ··········(10)

?n ? Ik ? min ?? Ak1 ?i ,n ? ? Ak ?i ,1? ? ( k ? k1 ) ? a ?k ? k1 ??? k1 ? k ? k2 ??...?? ki ? k ?b ? i ?1 ? ?
············· ············(11) 该问题比第二问更复杂,但是更贴合于实际情况,所以实用性很强。 仔细观察附件 5 中的图片,可以观察到,每张图片的 a 面和 b 面, “行间”所处的位置 是相同的,对每一张图片的 a、b 面读取灰度矩阵,对比可知“行间”出现的位置相同。即 在不知正反面的情况下,可先将正反面分为同一行。 按算法解决步骤如下: (1)找出最左侧一列的图片 观察附件。 所有最左边的图片最左端会对应一列全白, 即所生成的矩阵通过灰度矩阵图 可知最多前 11 列全为 255, 此时对该矩阵所有行求和会得到最大值 504900。 应用以上结论, 对所有图片的灰度矩阵第一列进行求和,所得值最大的即为最左边一列照片 (2)所以在进行聚类分析的时候可以先将这些“行间”相同的图片分为一“大行” 。 MATLAB 实现分“大行”过程: 将附件 5 中求出的 518 图片,全部进行灰度矩阵每行求和,并利用 MATLAB 将值为 19*255=4854 的行记为 1,值小于 4854 的记为 0,可以得出这 508 张图片的“行间”位置记 录矩阵。将(1)中求出的最左侧的 11 个图片的“行间”位置作为凝聚点,聚类分析将所有 的图片分成 11“大行” ,每行包含 19X2=38 张图片。这 38 张图片“行间”位置是相同的, 并且这 38 张包括 19 张正反面。 将每一张图片的正反面通过上边缘粘接就会形成一个二倍高 的纸片,这样就会从边缘获取更多的信息量。 (3)每一“大行”的拼接 应用上述聚类分析最短距离分析中提出的小差值优先匹配进行拼接,依次即可排出 11 个行图片。 (4)行与行相连拼出完整图片 应用方法同样是小差值优先匹配,即可以拼出完整的图片。 正反面顺序如表格五、表格六所示

12

表格五(正面)

07 8a 08 9b 18 6a 19 9a 08 8a 11 4b 14 6b 16 5a 00 3a 02 3a 09 9b 13 6b

11 1a 01 0a 15 3b 01 1a 10 7b 18 4a 17 1a 19 5b 00 7a 13 3b 04 3b 04 7a

12 5b 03 6b 08 4b 16 1b 14 9a 17 9a 03 1b 12 8b 08 5a 04 8b 09 6a 02 0a

14 0b 07 6a 04 2a 16 9a 18 0b 11 6a 20 1b 15 7b 14 8a 05 1a 10 9b 16 4b

15 5b 17 8b 03 0b 19 4a 03 7a 20 7b 05 0b 16 8b 07 7b 09 5b 12 3b 08 1b

15 0b 04 4b 03 8b 17 3a 19 1b 05 8b 19 0a 04 6b 00 4b 16 0a 00 6b 18 9b

18 3a 02 5a 12 1b 20 6a 06 5a 15 8b 09 2a 06 7b 06 9b 11 9b 10 4b 02 9a

17 4a 19 2b 09 8b 15 6b 11 5a 19 7b 01 9a 06 3a 03 2b 03 3a 13 4b 01 8b

11 0b 12 4a 09 4a 03 4b 16 6a 15 4a 01 6a 07 5a 07 4a 07 1a 11 3b 10 8a

06 6b 02 2b 06 1a 18 1a 00 1a 02 8a 17 7a 16 7b 12 6a 05 2b 02 6a 06 6a

10 8b 12 0a 13 7a 19 8a 15 1a 01 2b 05 3a 11 7a 17 6b 06 2b 04 9a 11 0a

01 8a 14 4b 04 5b 08 7b 17 0a 01 7a 20 2b 00 8a 18 5b 12 9a 09 1b 17 4b

02 9b 07 9b 13 8b 13 2a 04 1b 10 2a 02 1a 06 8a 00 0a 11 8a 10 6a 18 3b

18 9a 01 4b 05 6a 09 3b 07 0a 06 4a 13 0b 18 8b 08 0a 10 1b 10 0a 15 0a

08 1a 05 9b 13 1a 07 2a 13 9a 20 8b 16 3b 12 7b 02 7b 01 5a 05 5a 15 5a

16 4a 06 0a 18 7a 17 5b 00 2b 14 2b 19 3a 04 0b 13 5a 20 5b 10 3b 14 0a

02 0b 14 7b 08 6a 09 7b 16 2a 05 7b 07 3a 18 2a 14 1b 08 2a 11 2b 12 5a

04 7b 15 2b 20 0a 03 9a 20 3a 02 4b 15 9b 12 2b 20 4a 14 5b 19 6a 11 1b

13 6a 00 5b 14 3a 08 3b 09 0b 01 3b 03 5b 17 2b 10 6b 00 9a 05 4a 07 8b

表格六(反面)

13

00 5a 14 3b 08 3a 09 0a 01 3a 03 5a 17 2a 10 6a 00 9b 05 4b

15 2a 20 0b 03 9b 20 3b 02 4a 15 9a 12 2a 20 4b 14 5a 19 6b

14 7a 08 6b 09 7a 16 2b 05 7a 07 3b 18 2b 14 1a 08 2b 11 2a

06 0b 18 7b 17 5a 00 2a 14 2a 19 3b 04 0a 13 5b 20 5a 10 3a

05 9a 13 1b 07 2b 13 9b 20 8a 16 3a 12 7a 02 7a 01 5b 05 5b

01 4a 05 6b 09 3a 07 0b 06 4b 13 0a 18 8a 08 0b 10 1a 10 0b

07 9a 13 8a 13 2b 04 1a 10 2b 02 1b 06 8b 00 0b 11 8b 10 6b

14 4a 04 5a 08 7a 17 0b 01 7b 20 2a 00 8b 18 5a 12 9b 09 1a

12 0b 13 7b 19 8b 15 1b 01 2a 05 3b 11 7b 17 6a 06 2a 04 9b

02 2a 06 1b 18 1b 00 1b 02 8b 17 7b 16 7a 12 6b 05 2a 02 6b

12 4b 09 4b 03 4a 16 6b 15 4b 01 6b 07 5b 07 4b 07 1b 11 3a

19 2a 09 8a 15 6a 11 5b 19 7a 01 9b 06 3b 03 2a 03 3b 13 4a

02 5b 12 1a 20 6b 06 5b 15 8a 09 2b 06 7a 06 9a 11 9a 10 4a

04 4a 03 8a 17 3b 19 1a 05 8a 19 0b 04 6a 00 4a 16 0b 00 6a

17 8a 03 0a 19 4b 03 7b 20 7a 05 0a 16 8a 07 7a 09 5a 12 3a

07 6b 04 2b 16 9b 18 0a 11 6b 20 1a 15 7a 14 8b 05 1b 10 9a

03 6a 08 4b 16 1a 14 9b 17 9b 03 1a 12 8a 08 5b 04 8a 09 6b

01 0b 15 3a 01 1b 10 7a 18 4b 17 1b 19 5a 00 7b 13 3a 04 3a

08 9a 18 6b 19 9b 08 8b 11 4a 14 6a 16 5b 00 3b 02 3b 09 9a

运行程序六即为按照上述步骤操作后得出的完整图片

模型总结: 纵观以上三个问题,可以发现,题目的复杂性越来越高,也越来越接近与现实生活中 碰到的情况, 即实用性增强, 但是论文中解决三个问题所应用的主体方法小差值优先匹配没 有改变。 小差值优先匹配如图四:

灰度矩阵 左侧空白列 第一列图片

“行间” 聚类分析 大行

小差值优先匹配 复原图 11 行 图四

小差值优先匹配

14

第一问问题直接应用上述模型进行求解,第二问和第三问稍微复杂需要先进行预处理, 第二问中利用 “行间” 位置特征先进行聚类分出行, 第三问同样分出行之后还要分出正反面。 其余步骤均是按照小差值优先匹配来解决。 可见模型的主体清晰有利于模型进化已解决更复 杂的同类问题。

6、
模型优点:

模型优缺点

(1) 模型主体部分简洁清晰,程序简洁干练。 (2) 模型实用性较强,易于向更复杂的现实情况推广。复杂问题只要根据实际情况 增加聚类分析的凝聚点或者挖掘实际情况中所隐含的条件,在小差值优先匹配 模型上增加约束条件就可以简化分类,提高排序正确率,所以模型易于推广。 (3) 在“分行”的关键问题上抓住“行间”这个决定性的影响因素,使每张图片所 处的行唯一确定,提高筛选的准确度。 (4) 充分挖掘了题目中所提供的一切数据条件,如最左端和最右端都考虑,正反面 同时考虑。 模型缺点: (1) 模型在碎片边缘较短且数量较多的情况下,获得数据太少,其准确度下降,需

要太多人工干预。 (2) 模型不具有一般普遍性,它仅适用于边缘为直线的且纸片上文字书写规范的矩

形碎片复原情况,对边缘为是特殊形状的碎片或是文字书写不规范的纸片将不再适用。

7、

模型改进及推广

模型在对数据较少的图片拼接识别准确率不高, 显然模型不能对两张图片是否相邻做出 很好的判断,改进可从以下两反面进行: (1)从图片的最左端和最右端同时开始拼接,使拼接正确的图片尽可能多的出现在这行
15

中。 (2)仅使用一个 I k

?

?n ? ?? Ak1 ?i ,n ? ? Ak ?i ,1? ? 来判断下一张图片, ?a ? k ? k1 ??? k1 ? k ? k 2 ??...?? ki ? k ?b ? i ?1 ? ? min

在图片较小数据量少的情况下容易误判,所以需要再增加约束条件,如同时考虑类平均法、 离差平方和法(Ward 法)等较复杂的算法,可提高准确性。

8、参考文献

[1] 沈恒范. 详解 MATLAB 数字图像处理.北京:电子工业出版社,2010 [2] 张德丰等. MATLAB 数字图像处理.北京:机械工业出版社,2009 [3] 汪晓银.周保平.数学建模与数学实验.北京:科学出版社,2012 [4] 蓝章礼 李益才 李艾星.数字图像处理与图像通信.北京:清华大学出版社,2009 [5] zhx19870705,聚类分析 http://wenku.baidu.com/view/02e3d7c8050876323112125f.html, 2013 年 9 月 15 日 [6] 陈刚 于丹 吴迪.MATLAB 基础与实例进阶.北京:清华大学出版社,2012 [7] 于万波.基于 MATLAB 的图像处理.北京:清华大学出版社,2011 [8] 蒋先刚.数字图像模式识别工程软件设计.北京:中国水利水电出版社,2008 [9] 赵书兰.MATLAB 数字图像处理与分析实例教程.北京:化学工业出版社,2009

16

附录
附件 1 中碎片复原后的顺序及图片: 8 14 12 15 3 10 2 16 1 4 5 9 13 18 11 7 17 0 6

17

附件 2 中碎片复原后的顺序及图片:

3

6

2

7

15

18

11

0

5

1

9

13

10

8

12

14

17

16

4

18

附件 3 中碎片复原后的顺序及图片: 附件 3 行排序(只列了两行的图) 第一行:

19

第二行:

复原后的顺序

20

49 61 168 38 14 94 125 29 7 71 89

54 19 100 148 128 34 13 64 208 156 146

65 78 76 46 3 84 182 111 138 83 102

143 67 62 161 159 183 109 201 158 132 154

186 69 142 24 82 90 197 5 126 200 114

2 99 30 35 199 47 16 92 68 17 40

57 162 41 81 135 121 184 180 175 80 151

192 96 23 189 12 42 110 48 45 33 207

178 131 147 122 73 124 187 37 174 202 155

118 79 191 103 160 144 66 75 0 198 140

190 63 50 130 203 77 106 55 137 15 185

95 116 179 193 169 112 150 44 53 133 108

11 163 120 88 134 149 21 206 56 170 117

22 72 86 167 39 97 173 10 93 205 4

129 6 195 25 31 136 157 104 153 85 101

28 177 26 8 51 164 181 98 70 152 113

91 20 1 9 107 127 204 172 166 165 194

188 52 87 105 115 58 139 171 32 27 119

144 36 18 74 176 43 145 59 196 60 123

附件 4 中碎片复原后的顺序及图片: 191 201 086 019 159 020 208 070 132 171 081 075 148 051 194 139 041 021 084 181 042 077 011 170 107 093 001 108 007 060 095 066 128 154 196 029 141 129 116 049 014 069 205 200 190 198 040 088 063 136 061 068 167 010 131 184 094 158 121 138 073 119 174 163 157 052 002 113 186 126 153 036 033 137 166 074 125 104 164 098 105 053 207 142 195 188 145 140 180 078 024 155 038 135 168 008 111 083 193 064 103 117 114 123 015 062 047 144 134 087 106 091 150 176 120 076 169 172 206 055 089 004 080 005 182 175 043 054 156 003 018 048 149 101 059 151 085 199 192 196 130 056 072 032 026 058 022 050 045 133 023 034 035 012 204 100 092 057 160 173 118 099 013 016 177 065 006 030 202 187 079 189 122 110 009 124 039 017 037 071 097 161 162 090 025 183 000 067 028 046 165 203 179 197 185 027 152 102 147 146 127 082 031 143 112 109 178 044 115

21

附件 3 的行排序(只列了两行的图)

22

附件五中碎片复原后的顺序及图片: 正面顺序:

07 8a 08 9b 18 6a 19 9a 08 8a 11 4b 14 6b 16 5a 00 3a 02 3a 09 9b

11 1a 01 0a 15 3b 01 1a 10 7b 18 4a 17 1a 19 5b 00 7a 13 3b 04 3b

12 5b 03 6b 08 4b 16 1b 14 9a 17 9a 03 1b 12 8b 08 5a 04 8b 09 6a

14 0b 07 6a 04 2a 16 9a 18 0b 11 6a 20 1b 15 7b 14 8a 05 1a 10 9b

15 5b 17 8b 03 0b 19 4a 03 7a 20 7b 05 0b 16 8b 07 7b 09 5b 12 3b

15 0b 04 4b 03 8b 17 3a 19 1b 05 8b 19 0a 04 6b 00 4b 16 0a 00 6b

18 3a 02 5a 12 1b 20 6a 06 5a 15 8b 09 2a 06 7b 06 9b 11 9b 10 4b

17 4a 19 2b 09 8b 15 6b 11 5a 19 7b 01 9a 06 3a 03 2b 03 3a 13 4b

11 0b 12 4a 09 4a 03 4b 16 6a 15 4a 01 6a 07 5a 07 4a 07 1a 11 3b

06 6b 02 2b 06 1a 18 1a 00 1a 02 8a 17 7a 16 7b 12 6a 05 2b 02 6a

10 8b 12 0a 13 7a 19 8a 15 1a 01 2b 05 3a 11 7a 17 6b 06 2b 04 9a

01 8a 14 4b 04 5b 08 7b 17 0a 01 7a 20 2b 00 8a 18 5b 12 9a 09 1b

02 9b 07 9b 13 8b 13 2a 04 1b 10 2a 02 1a 06 8a 00 0a 11 8a 10 6a

18 9a 01 4b 05 6a 09 3b 07 0a 06 4a 13 0b 18 8b 08 0a 10 1b 10 0a

08 1a 05 9b 13 1a 07 2a 13 9a 20 8b 16 3b 12 7b 02 7b 01 5a 05 5a

16 4a 06 0a 18 7a 17 5b 00 2b 14 2b 19 3a 04 0b 13 5a 20 5b 10 3b

02 0b 14 7b 08 6a 09 7b 16 2a 05 7b 07 3a 18 2a 14 1b 08 2a 11 2b

04 7b 15 2b 20 0a 03 9a 20 3a 02 4b 15 9b 12 2b 20 4a 14 5b 19 6a

13 6a 00 5b 14 3a 08 3b 09 0b 01 3b 03 5b 17 2b 10 6b 00 9a 05 4a

反面顺序: 13 6b 00 5a 14 3b 08 3a 09 0a 01 3a 03 5a 17 04 7a 15 2a 20 0b 03 9b 20 3b 02 4a 15 9a 12 02 0a 14 7a 08 6b 09 7a 16 2b 05 7a 07 3b 18 16 4b 06 0b 18 7b 17 5a 00 2a 14 2a 19 3b 04 08 1b 05 9a 13 1b 07 2b 13 9b 20 8a 16 3a 12 18 9b 01 4a 05 6b 09 3a 07 0b 06 4b 13 0a 18 02 9a 07 9a 13 8a 13 2b 04 1a 10 2b 02 1b 06 01 8b 14 4a 04 5a 08 7a 17 0b 01 7b 20 2a 00 10 8a 12 0b 13 7b 19 8b 15 1b 01 2a 05 3b 11 06 6a 02 2a 06 1b 18 1b 00 1b 02 8b 17 7b 16 11 0a 12 4b 09 4b 03 4a 16 6b 15 4b 01 6b 07 17 4b 19 2a 09 8a 15 6a 11 5b 19 7a 01 9b 06 18 3b 02 5b 12 1a 20 6b 06 5b 15 8a 09 2b 06 15 0a 04 4a 03 8a 17 3b 19 1a 05 8a 19 0b 04 15 5a 17 8a 03 0a 19 4b 03 7b 20 7a 05 0a 16 14 0a 07 6b 04 2b 16 9b 18 0a 11 6b 20 1a 15 12 5a 03 6a 08 4b 16 1a 14 9b 17 9b 03 1a 12 11 1b 01 0b 15 3a 01 1b 10 7a 18 4b 17 1b 19 07 8b 08 9a 18 6b 19 9b 08 8b 11 4a 14 6a 16

23

2a 10 6a 00 9b 05 4b

2a 20 4b 14 5a 19 6b

2b 14 1a 08 2b 11 2a

0a 13 5b 20 5a 10 3a

7a 02 7a 01 5b 05 5b

8a 08 0b 10 1a 10 0b

8b 00 0b 11 8b 10 6b

8b 18 5a 12 9b 09 1a

7b 17 6a 06 2a 04 9b

7a 12 6b 05 2a 02 6b

5b 07 4b 07 1b 11 3a

3b 03 2a 03 3b 13 4a

7a 06 9a 11 9a 10 4a

6a 00 4a 16 0b 00 6a

8a 07 7a 09 5a 12 3a

7a 14 8b 05 1b 10 9a

8a 08 5b 04 8a 09 6b

5a 00 7b 13 3a 04 3a

5b 00 3b 02 3b 09 9a

附件五图片: 正面:

24

反面:

以下程序的软件均为 matlabR2012a 程序一: %%%显示第一题中文(附件一)的正常排序 clear all clc %% 读取数据 filepathsrc = 'E:\cumcm2013problems\B\附件 1\';
25

file=dir( 'E:\cumcm2013problems\B\附件 1\*.bmp'); for i = 1:length(file) A{i} = imread([filepathsrc, file(i).name]); end %%找出最左边的纸片 for i=1:19 a=A{i}(:,1); s(i)=sum(a); end [y,x]=max(s) b1{1}(:,72)=A{x}(:,72); N(1)=x; for j=2:19 for i=1:19 t=b1{j-1}(:,72)-A{i}(:,1); s(i)=sum(abs(t)); if s(i)==0 s(i)=+inf; end end [m,n]=min(s); b1{j}(:,72)=A{n}(:,72); N(j)=n; end raw=N-1; %纸片排序:从左到右 a=A{N(1)}; for i=2:19 a=[a A{N(i)}]; end imtool(a)
26

程序二: %%%显示第一题英文(附件二)的正常排序 clear all clc %% 读取数据 filepathsrc = 'E:\cumcm2013problems\B\附件 2\'; file=dir( 'E:\cumcm2013problems\B\附件 2\*.bmp'); for i = 1:length(file) A{i} = imread([filepathsrc, file(i).name]); end %%找出最左边的纸片 for i=1:19 a=A{i}(:,1); s(i)=sum(a); end [y,x]=max(s)

b1{1}(:,72)=A{x}(:,72); N(1)=x; for j=2:19 for i=1:19 t=b1{j-1}(:,72)-A{i}(:,1); s(i)=abs(sum(t)); if s(i)==0 s(i)=+inf; end end [m,n]=min(s);
27

b1{j}(:,72)=A{n}(:,72); N(j)=n; end raw=N-1; %纸片排序:从左到右 a=A{N(1)}; for i=2:19 a=[a A{N(i)}]; end imtool(a)

程序三: %%从左到右和从右到做搜寻 clear all clc %% 读取数据 filepathsrc = 'E:\cumcm2013problems\B\附件 3\'; file=dir( 'E:\cumcm2013problems\B\附件 3\*.bmp'); for i = 1:length(file) A{i} = imread([filepathsrc, file(i).name]); end % 找最左边的纸片,Nz 为所得处于最左边的纸片的序号 for i=1:209 k{i}(:,1:11)=sum(A{i}(:,1:11)); d{i}=sum(k{i}); d1(i)=d{i}(1); if d1(i)==255*180*11 Nz=i end end % Nz=[ 8 15 30 39 50 62 72 90 95 126 169];
28

%% % 找最右边的纸片,Nz 为所得处于最右边的纸片的序号 for i=1:209 k{i}(:,end-10:end)=sum(A{i}(:,end-10:end)); d{i}=sum(k{i}); d1(i)=d{i}(1); if d1(i)==255*180*11 Ny=i end end % Ny 为所得处于最右边的纸片的序号 % Ny=[19 37 44 60 61 75 124 142 146 177 197]; %% 行和用 r_sum 记录 for i=1:209 % i 代表第 i 张纸片 for j=1:180 % j 代表第 j 行之和 r_sum(j,i)=sum(A{i}(j,:)); %r_sum(j,i)表示第 i 张图片的第 j 行之和 if r_sum(j,i)==255*72 r_sum(j,i)=1; else r_sum(j,i)=0; end end end %记录相对应的行的纸片元素的序号 for i=1:209 g(i)=sum(r_sum(80:104,i))+sum(r_sum(149:173,i));%此时为与第 049.bmp 的中间字的上 下行距之和 if g(i)==50 k=i end
29

% 如果第 j 行为白,返回值为 1,否则为 0

end %% %%可以去掉到去掉%,每个 nn 表示,不同行的纸片的系数 %下面对应的是通过人工干预所求同行纸片的系数 %nn=[1 8 33 46 54 57 69 71 94 127 138 139 154 159 167 175 176 197 209]; %x=2;y=18; %nn=[2 19 24 27 31 42 51 63 77 87 88 101 121 143 148 169 180 192 196]; %x=16;y=2; %nn=[3 12 23 29 50 55 58 66 92 96 119 130 142 144 179 187 189 191 193]; %x=5;y=13; nn=[4 13 15 32 40 52 74 83 108 116 129 135 136 160 161 170 177 200 204]; x=3;y=17; %nn=[6 11 30 38 45 49 56 60 65 76 93 99 105 112 172 173 181 202 207]; %x=3;y=8; %nn=[5 41 90 102 103 109 114 115 118 120 124 141 147 152 155 156 186 195 208]; %x=3;y=11; % nn=[7 20 21 37 53 62 64 68 70 73 79 80 97 100 117 132 163 164 178]; %x=6;y=4 %nn=[9 10 25 26 36 39 47 75 82 89 104 106 123 131 149 162 168 190 194]; %x=6;y=8; %nn=[ 14 17 22 67 107 110 111 126 140 146 151 158 174 182 183 185 188 198 205]; %x=8;y=10; %nn=[16 18 28 34 61 72 81 84 86 133 134 153 157 166 171 199 201 203 206]; %x=6;y=5; %nn=[35 43 44 48 59 78 85 91 95 98 113 122 125 128 137 145 150 165 184]; %x=9;y=3; %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% for i=1:19 A1{i}=A{nn(i)}; end b1{1}(:,72)=A1{x}(:,72); %%b1 存储排序后的纸片数据
30

N(1)=x; for j=2:19 for i=1:19 t=double(b1{j-1}(:,72))-double(A1{i}(:,1)); s(i)=sum(abs(t));

if j==i s(i)=+inf; end

% s(find(N==i))=inf; end

for u=1:length(N)

s(N(u))=+inf; end [m,n]=min(s); b1{j}(:,72)=A1{n}(:,72); N(j)=n; end a=A1{N(1)}; for i=2:19 a=[a A1{N(i)}]; end imtool(a) b2{19}(:,1)=A1{y}(:,1); NY(19)=y; for j=1:18 for i=1:19
31

t=double(b2{20-j}(:,1))-double(A1{i}(:,72)); s(i)=sum(abs(t)); if 20-j==i s(i)=+inf; end end for u=length(NY);19 s(NY(u))=+inf; end [m1,n1]=min(s); b2{19-j}(:,1)=A1{n1}(:,1); NY(19-j)=n1; end aY=A1{NY(1)}; for i=2:19 aY=[aY A1{NY(i)}]; end imtool(aY)

程序四 %%%第二问中文人工干预后的碎纸片拼接图片 clear all clc %% 读取数据 filepathsrc = 'E:\cumcm2013problems\B\附件 3\'; file=dir( 'E:\cumcm2013problems\B\附件 3\*.bmp'); for i = 1:length(file) A{i} = imread([filepathsrc, file(i).name]); end z=0;
32

for i=1:209 k{i}(:,1:11)=sum(A{i}(:,1:11)); d{i}=sum(k{i}); d1(i)=d{i}(1); if d1(i)==255*180*11 z=z+1; n(z)=i; end end n % n=[ 8 15 30 39 50 62 72 90 95 126 169]; %% 行和用 r_sum 记录 如果第 j 行为白,返回值为 1,否则为 0

for i=1:209 % i 代表第 i 张纸片 for j=1:180 % j 代表第 j 行之和 r_sum(j,i)=sum(A{i}(j,:)); %r_sum(j,i)表示第 i 张图片的第 j 行之和 if r_sum(j,i)==255*72 r_sum(j,i)=1; else r_sum(j,i)=0; end end end % 找出处于同一行的纸片 for i=1:209 g(i)=sum(r_sum(80:104,i))+sum(r_sum(149:173,i)); if g(i)==50 k=i; end end nn1=[3 12 23 29 50 55 58 66 92 96 119 130 142 144 179 187 189 191 193];
33

% 如果第 j 行为白,返回值为 1,否则为 0

for i=1:19 A1{i}=A{nn1(i)}; end x=5; b1{1}(:,72)=A1{x}(:,72); %%b1 存储排序后的纸片数据 N(1)=x; for j=2:19 for i=1:19 t=double(b1{j-1}(:,72))-double(A1{i}(:,1)); s(i)=sum(abs(t)); if j==i s(i)=+inf; end end for u=1:length(N) s(N(u))=+inf; end [m,n]=min(s); b1{j}(:,72)=A1{n}(:,72); N(j)=n; end s1=[49 54 65 143 186 2 57 192 178 118 190 95 11 22 129 28 91 188 141]; for i=1:19 A1{i}=A{s1(i)}; end raw=N-1; %纸片排序:从左到右 s1=s1+1; a1=A{s1(1)}; for i=2:19 a1=[a1 A{s1(i)}];
34

end imtool(a1) s2=[61 19 78 67 69 99 162 96 131 79 63 116 163 72 6 177 20 52 36]; s2=s2+1; a2=A{s2(1)}; for i=2:19 a2=[a2 A{s2(i)}]; end imtool(a2) s3=[168 100 76 62 142 30 41 23 147 191 50 179 120 86 195 26 1 87 18]; s3=s3+1; a3=A{s3(1)}; for i=2:19 a3=[a3 A{s3(i)}]; end imtool(a3) s4=[38 148 46 161 24 35 81 189 122 103 130 193 88 167 25 8 9 105 74]; s4=s4+1; a4=A{s4(1)}; for i=2:19 a4=[a4 A{s4(i)}]; end imtool(a4) s5=[71 156 83 132 200 17 80 33 202 198 15 133 170 205 85 152 165 27 60]; s5=s5+1; a5=A{s5(1)}; for i=2:19 a5=[a5 A{s5(i)}]; end imtool(a5)
35

s6=[14 128 3 159 82 199 135 12 73 160 203 169 134 39 31 51 107 115 176]; s6=s6+1; a6=A{s6(1)}; for i=2:19 a6=[a6 A{s6(i)}]; end imtool(a6) s7=[94 34 84 183 90 47 121 42 124 144 77 112 149 97 136 164 127 58 43]; s7=s7+1; a7=A{s7(1)}; for i=2:19 a7=[a7 A{s7(i)}]; end imtool(a7) s8=[125 13 182 109 197 16 184 110 187 66 106 150 21 173 157 181 204 139 145]; s8=s8+1; a8=A{s8(1)}; for i=2:19 a8=[a8 A{s8(i)}]; end imtool(a8) s9=[29 64 111 201 5 92 180 48 37 75 55 44 206 10 104 98 172 171 59]; s9=s9+1; a9=A{s9(1)}; for i=2:19 a9=[a9 A{s9(i)}]; end imtool(a9) s10=[7 208 138 158 126 68 175 45 174 0 137 53 56 93 153 70 166 32 196]; s10=s10+1;
36

a10=A{s10(1)}; for i=2:19 a10=[a10 A{s10(i)}]; end imtool(a10) s11=[89 146 102 154 114 40 151 207 155 140 185 108 117 4 101 113 194 119 123]; s11=s11+1; a11=A{s11(1)}; for i=2:19 a11=[a11 A{s11(i)}]; end imtool(a11) aaz=[a1;a2;a3;a4;a5;a6;a7;a8;a9;a10;a11]; imtool(aaz)

程序五 %%%第三题(附件五)的程序 clear all clc %% 读取数据 filepathsrc = 'E:\cumcm2013problems\B\附件5\'; file=dir( 'E:\cumcm2013problems\B\附件5\*.bmp'); for i = 1:length(file) A{i} = imread([filepathsrc, file(i).name]); end % 找最左边的纸片,Nz为所得处于最左边的纸片的序号 z=0; for i=1:418 k{i}(:,1:11)=sum(A{i}(:,1:11)); d{i}=sum(k{i}); d1(i)=d{i}(1); if d1(i)==255*180*11 z=z+1; Nz(z)=i; end end
37

% 找最右边的纸片,Ny为所得处于最右边的纸片的序号 z=0; for i=1:418 k{i}(:,(end-10):end)=sum(A{i}(:,(end-10):end)); d{i}=sum(k{i}); d1(i)=d{i}(1); if d1(i)==255*180*11 z=z+1; Ny(z)=i; end end %求Nz于Ny的相同元素 tz=rem(Nz,2); %0代表b面,1代表a面 rz=fix((Nz-1)./2); ty=rem(Ny,2); %0代表b面,1代表a面 ry=fix((Ny-1)./2); k=0; for i=1:24 for j=1:22 if rz(i)==ry(j) k=k+1; N(k)=rz(i); end end end %% 行和用r_sum记录 for i=1:418 % i代表第N中的第i个元素 for j=1:180 % j代表第j行之和 r_sum(j,i)=sum(A{i}(j,:)); %r_sum(j,i)表示第N(i)张图片的第j行之和 if r_sum(j,i)==255*72 r_sum(j,i)=1; else r_sum(j,i)=0; end end End %%%人工干预后的排序 nz_raw=[78 111 125 140 155 150 183 174 110 66 108 18 29 189 81 164 20 47 136; 89 10 36 76 178 44 25 192 124 22 120 144 79 14 59 60 147 152 5; 186 153 84 42 30 38 121 98 94 61 137 45 138 56 131 187 86 200 143; 199 11 161 169 194 173 206 156 34 181 198 87 132 93 72 175 97 39 83; 88 107 149 180 37 191 65 115 166 1 151 170 41 70 139 2 162 203 90; % 如果第j行为白,返回值为1,否则为0

38

114 184 179 116 207 58 158 197 154 28 12 17 102 64 208 142 57 24 13; 146 171 31 201 50 190 92 19 16 177 53 202 21 130 163 193 73 159 35; 165 195 128 157 168 46 67 63 75 167 117 8 68 188 127 40 182 122 172; 3 7 85 148 77 4 69 32 74 126 176 185 0 80 7 135 141 204 105; 23 133 48 51 95 160 119 33 71 52 62 129 118 101 15 205 82 145 9; 99 43 96 109 123 6 104 134 113 26 49 91 106 100 55 103 112 196 54]; for i=1:19 nf_raw(:,i)=nz_raw(:,20-i); end tz_raw=[0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 0; 1 0 1 0 1 1 0 1 0 1 0 1 1 1 1 0 1 1 1; 0 1 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0; 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0 1 1 0 1; 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1; 1 0 0 0 1 1 1 1 0 0 1 0 0 0 1 1 1 1 1; 1 0 1 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 1; 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 0 1 1; 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 0 1 0 1; 0 1 1 0 1 0 1 0 0 1 1 0 0 1 0 1 0 1 0; 1 1 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 0 0]; for i=1:19 tf_raw(:,i)=tz_raw(:,20-i); end for i=1:19 for j=1:11 if tf_raw(j,i)==0 tf_raw(j,i)=1; else tf_raw(j,i)=0; end end end for i=1:19 %%转化为2代表表面,1代表a面 for j=1:11 if tz_raw(j,i)==0 tz_raw(j,i)=2; end end end for i=1:19 %%转化为2代表表面,1代表a面 for j=1:11 if tf_raw(j,i)==0 tf_raw(j,i)=2; end

39

end end Nz=2*nz_raw+tz_raw; Nf=2*nf_raw+tf_raw; for i=1:19 for j=1:11 rz_show{j,i}=A{Nz(j,i)}; end end Bz=cell2mat(rz_show); for i=1:19 for j=1:11 rf_show{j,i}=A{Nz(j,i)}; end end Bf=cell2mat(rf_show); imtool(Bz) imtool(Bf) %%输出排好顺序的正面的纸片 %%输出排好顺序的反面的纸片

40


2013年全国大学生数学建模竞赛B题全国一等奖论文_图文.doc

2013年全国大学生数学建模竞赛B题全国等奖论文_理学_高等教育_教育专区。2013年...二阶差分法、Spearman 系数等来构建扩展的边界 差异度模型,刻画碎片间的差异度...

2013年数学建模B题一等奖优秀论文1_图文.doc

2013年数学建模B题等奖优秀论文1_数学_自然科学_专业资料。基于最小二乘法的碎纸片拼接复原数学模型 摘要 首先对图片进行灰度化处理,然后转化为 0-1 二值矩阵,...

2013全国大学生数学建模竞赛国家二等奖论文 碎纸片的拼....pdf

2013全国大学生数学建模竞赛国家二等奖论文 碎纸片的拼接复原_理学_高等教育_教育专区。2013全国大学生数学建模竞赛国家二等奖论文B题 碎纸片的拼接复原 ...

2015年全国大学生数学建模竞赛B题二等奖论文_图文.pdf

2015年全国大学生数学建模竞赛B题二等奖论文 - 2015 高教社杯全国大学生数学建模竞赛 承 诺 书 我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生...

2013年高教社杯全国大学生数学建模竞赛B题优秀论文_图文.doc

2013年高教社杯全国大学生数学建模竞赛B题优秀论文_数学_自然科学_专业资料。...5.2.2 模型二的求解 利用附件 3、附件 4 的数据,运用 Adaboost 算法,借助...

13年全国大学生数学建模全国二等奖_图文.doc

2013年全国大学生数学建模B题全国二等奖 2013 高教社杯全国大学生数学建模竞赛...我们授权全国大学生数学建模竞赛组委会,可将我们的论文以任何形式进行公开展 示(...

2013全国数学建模竞赛B题优秀论文_图文.doc

2013全国数学建模竞赛B题优秀论文 - 基于最小二乘法的碎纸片拼接复原数学模型

2013高教社杯全国大学生数学建模竞赛-B题论文_图文.doc

2013高教社杯全国大学生数学建模竞赛-B题论文_教育学_高等教育_教育专区。碎

2012年全国大学生数学建模大赛B题国家二等奖论文_图文.pdf

2012年全国大学生数学建模大赛B题国家二等奖论文 - 2012 高教社杯全国大学生数学建模竞赛 承 诺 书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全...

2013年全国数学建模B题省一等奖_图文.doc

2013年全国数学建模B题省一等奖_行政公文_工作范文_...B 024B03 赵文才 (论文纸质版与电子版中的以上...(由全国组委会评阅前进行编号): 基于最小二乘法的...

2010年全国大学生数学建模竞赛B题优秀论文.doc

2010年全国大学生数学建模竞赛B题优秀论文_理学_高等...二 是使原本五年、

2014数学建模B题论文(国赛二等奖)_图文.doc

2014数学建模B题论文(国赛二等奖) - 2014 高教社杯全国大学生数学建模竞赛 承 诺 书 我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛...

创意平板折叠桌数学建模竞赛B题全国二等奖论文.doc

创意平板折叠桌数学建模竞赛B题全国二等奖论文 - 创意平板折叠桌 摘要 本文讨论

13年全国大学生数学建模竞赛B题碎纸片的拼接复原_图文.doc

13年全国大学生数学建模竞赛B题碎纸片的拼接复原_理学_高等教育_教育专区。13年全国大学生数学建模全国二等奖文章,里面的模型和文章写作方法大家可以相互学习一...

2012数学建模 B题全国二等奖_图文.doc

2012数学建模 B题全国二等奖_数学_自然科学_专业资料。2012全国数学建模竞赛 全国二等奖论文 承 诺 书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们...

2014年全国数学建模A题全国二等奖论文.pdf

2014年全国数学建模A题全国二等奖论文_数学_自然科学_专业资料。2014全国数学...分别表示标称和 实际的位置和速度之差;A,B 是与着陆器位置有关的参数,U、V...

2014年全国大学生数学建模竞赛B题全国二等奖.pdf

2014年全国大学生数学建模竞赛B题全国二等奖_理学_高等教育_教育专区。2014 高教社杯全国大学生数学建模竞赛 承 诺 书 论文编号:B02008013 我们仔细阅读了《全国...

2014全国数学建模大赛B题获奖论文_图文.pdf

2014全国数学建模大赛B题获奖论文_理学_高等教育_教育专区。2014 高教社

2004年全国大学生数学建模大赛B题全国一等奖论文.doc

2004年全国大学生数学建模大赛B题全国等奖论文_数学_自然科学_专业资料。

2005年全国大学生数学建模大赛B题全国一等奖论文.doc

2005年全国大学生数学建模大赛B题全国等奖论文_数学_自然科学_专业资料。承