2013全国数学建模竞赛B题优秀论文要点.pdf
《2013全国数学建模竞赛B题优秀论文要点.pdf》由会员分享,可在线阅读,更多相关《2013全国数学建模竞赛B题优秀论文要点.pdf(28页珍藏版)》请在三一文库上搜索。
1、1 基于最小二乘法的碎纸片拼接复原数学模型 摘要 首先对图片进行灰度化处理, 然后转化为 0-1 二值矩阵,利用矩阵行(列)偏差函 数,建立了基于最小二乘法的碎纸片拼接数学模型,并利用模型对图片进行拼接复原。 针对问题一,当两个数字矩阵列向量的偏差函数最小时,对应两张图片可以左右拼 接。经计算,得到附件1 的拼接结果为: 08,14,12,15,03,10,02,16,01,04,05,09,13,18,11,07,17,00,06。 附件 2 的拼接结果为 : 03,06,02,07,15,18,11,00,05,01,09,13,10,08,12,14,17,16,04。 针对问题二,首先
2、根据每张纸片内容的不同特性,对图片进行聚类分析,将209张 图片分为 11 类;对于每一类图片,按照问题一的模型与算法,即列偏差函数最小则进 行左右拼接 , 对于没有拼接到组合里的碎纸片进行人工干预,我们得到了 11组碎纸片拼 接而成的图片;对于拼接好的11 张图片,按照问题一的模型与算法,即行偏差函数最 小则进行上下拼接 , 对于没有拼接到组合里的碎纸片进行人工干预。我们最终经计算, 附件 3 的拼接结果见表 9,附件 4 的拼接结果见表 10。 针对问题三,由于图片区分正反两面,在问题二的基础上,增加图片从下到上的裁 截距信息,然后进行两次聚类,从而将所有图片进行分类,利用计算机自动拼接与
3、人工 干预相结合,对所有图片进行拼接复原。经计算,附件5 的拼接结果见表14和表 15 该模型的优点是将图片分为具体的几类,大大的减少了工作量,缺点是针对英文文 章的误差比较大。 关键字 :灰度处理,图像二值化,最小二乘法,聚类分析,碎纸片拼接 2 一、问题重述 碎纸片的拼接复原技术在司法鉴定、历史文献修复与研究、军事情报获取以及故障 分析等领域都有着广泛的应用。近年来,随着德国“斯塔西”文件的恢复工程的公布, 碎纸文件复原技术的研究引起了人们的广泛关注。传统上,拼接复原工作需由人工完成, 准确率较高, 但效率很低。特别是当碎片数量巨大, 人工拼接很难在短时间内完成任务。 随着计算机技术的发展
4、,人们试图开发碎纸片的自动拼接技术,以提高拼接复原效率。 对于一页印刷文档,针对不同的破碎方法,讨论下列三个问题: (1)将给定的一页印刷文字文件纵切,建立碎纸片拼接复原模型和算法,并针对附 件 1、附件 2 给出的中、英文各一页文件的碎片数据进行拼接复原。 (2)对于碎纸机既纵切又横切的情形,设计碎纸片拼接复原模型和算法,并针对附 件 3、附件 4 给出的中、英文各一页文件的碎片数据进行拼接复原。 (3)对于双面打印文档, 研究如何进行碎纸片的拼接复原问题。附件 5 给出的是一 页英文印刷文字双面打印文件的碎片数据。要求尝试设计相应的碎纸片拼接复原模型与 算法,并就附件 5 的碎片数据给出拼
5、接复原结果。 二、模型的基本假设 (1) 待拼接的碎纸片来自同一页印刷文字文件。 (2) 待拼接复原的碎纸片是规整的矩形。 (3) 模型中的碎纸片长度、宽度和面积都相等。 (4) 附件中照片都是同标准拍摄。 三、符号说明 表 1 符号说明 符号符号说明 Gray 灰度值 r红色 g 绿色 b蓝色 3 A, B矩阵 i D 裁截距( =1,2,209)i i a 裁截文字长度( =1,2,209)i i b 行间距( =1,2,209)i i c 裁截空白距离( =1,2,209)i i d 字体高度( =1,2,209)i 四、问题分析 将不规则的文档碎纸片进行拼接,一般是利用碎纸片的边缘曲线
6、,尖点、尖角、面 积等几何特征,搜索与之匹配的相邻碎纸片。但对于边缘形状相似的碎纸片,这种基于 边界几何特征的拼接方法失效,拼接时不但要考虑待拼接碎纸片边缘是否匹配,还要判 断碎片内的字迹断线或碎片内的文字内容是否匹配。 本问题给定的碎纸片有以下几个特点: 1、每一张碎纸片都是规整的矩形; 2、所有的碎纸片的长度、宽度都相等,形状是完全一样的; 3、每一张碎纸片里都包含着文字(汉字、英文),不存在空白的碎纸片; 4、不同的碎纸片之间没有重叠部分。 由于碎纸片的形状相同,因而不能针对碎纸片的几何特征建立数学模型;碎纸片间无 重叠,也不能利用图像融合技术进行图像配准。 根据上述分析,我们考虑将图片
7、进行数字化处理,根据每张碎纸片上的边缘文字特征 进行匹配,也就是利用图片边缘文字的像素进行最优化匹配。 五、模型的建立与求解 5.1 问题一的建模与算法 由于碎纸片本身不具有体现其拼接特性的数字特征,我们需要将其数字化、 矩阵化, 将问题转化为矩阵之间的相关性。 4 5.1.1 图片的灰度处理 利用photoshop软件,将附件中所给的BMP 格式的图片转化成JPG格式 ,去除图 片的多彩性。为了对碎纸片进行数字化,我们将图像进行灰度处理,取出图像中每一个 像素点的灰度值,灰度值的大小与像素点颜色的红绿蓝成分有关。 根据文献 1,每个像素点的=0.30+0.59+0.11灰度值红色绿色蓝色,即
8、 0.300.590.11Grayrgb, 其中,,r g b的取值范围是0255。 问题一将同一页印刷文字文件纵切为19 张图片(见图 1) ,根据实际情况,我们将 每张图片设置为198072格式,于是,每张图片对应一个198072的灰度矩阵。 图 1 附件 1 未进行拼接的19 张碎纸片 5 5.1.2 图片的二值化处理 将图片进行灰度处理以后,每个像素的灰度值介于0255之间。灰度值不能直接用 于文字图片的拼接,还须进行二值化处理。 将图片放入直角坐标系,规定:若( ,)x y点的像素灰度值大于或等于T,该点用数值 1表示,并将其设定为白色;若( ,)x y点的像素灰度值小于T,该点用数
9、值0表示,并将 其设定为黑色。由此得到像素点的二值化函数: 1,( ,), ( , ) 0,( ,), Gray x yT w x y Gray x yT 其中,T为预先设定的全局灰度阈值。于是,每张图片的灰度矩阵转化为下列198072 的0,1数字矩阵: 111 72 1980 11980 72 aa A aa , 其中 1, 1, 0, 0. ij a 代表空白的像素点 代表有文字的像素点 5.1.3 最小二乘法 1、图片左右拼接的数学模型 设,A B 分别表示左右放置的两张图片对应的数字矩阵,定义前一个矩阵的最后一 列与后一个矩阵的第一列之间的偏差函数为: 1980 2 1 ( ,)(
10、,72)( ,1), i f A BA iB i 其中,( ,72),( ,1)A iB i分别表示矩阵,AB 第72列和第1列的元素。 对于给定的矩阵 A ,若存在矩阵 B ,使得 A 与B之间的偏差函数 (,)fA B 达 到最小,则称A 与 B 可以匹配,此时A 与 B 对应的图片可以左右拼接。 2、图片上下拼接的数学模型 类似地,设,CD 分别表示上下放置的两张图片对应的数字矩阵,定义上面矩阵的 最后一行与下面矩阵的第一行之间的偏差函数为: 72 2 1 (,)(1980, )(1, ), j h C DCjDj 其中, (1980,),(1,)CjDj 分别表示矩阵,CD 第1980
11、行和第1行的元素。 对于给定的矩阵 C ,若存在矩阵 D ,使得 C 与 D 之间的偏差函数(,)h CD达 6 到最小,则称 C 与 D 可以匹配,此时 C 与 D 对应的图片可以上下拼接。 我们称上述基于数字矩阵之间列(或行)距离的图片拼接模型为最小二乘法拼接复 原模型 。 5.1.4 算法与求解 (一)算法思想 第一步,对附件中的19 幅图片分别进行灰度处理,然后取灰度阈值125T,进行 二值化,得到 19 个0,1数字矩阵,即图片的数字化。 第二步, 对上述 19个数字矩阵进行检测, 若存在一个矩阵的最左侧一列元素全是1, 根据破碎图片的特点,则该图片即为从左边起第一张碎纸片,记为 1
12、 A 。 第三步,计算 1 A与其余 18 张图片对应矩阵的列偏差值。 1980 2 11 1 (,)( ,72)( ,1), i fABAiB i 若存在 2 A,使得 12 (,)fAA达到最小,则 2 A即位第二张图片。 重复上述的步骤,依次得到所有碎纸片的排列,即可拼接成完整图片。 (二)附件 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
13、附件 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 聚类分析 对于碎纸机既纵切又横切的情形,与问题一仅纵切相比,图片变小,因而每张图片 7 包含的信息量明显变小,如果仅利用最小二乘法,碎片之间的匹配不唯一。为了解决这 个问题,我们利用聚类分析法,对碎片先进行分类。 经观察测试,原始文档碎片具有下列
14、特点: (1)字体大小:字体的最大高度和最大宽度一致。 (2)切割的均匀性:同方向的切割线平行,图片大小均相等,沿纵横方向按直线 切割。 (3)文字的行距:文字的行间距等同,段落间距为定值。 为了对 209幅图片进行聚类分析,如图2 所示,我们定义聚类指标如下: i a表示图片上端裁接处的字体长度,我们称之为裁截文字长度; i b为行间距; i c 表示图片上端文字与切割线之间的空白距离,我们称之为裁截空白距离; i d 为字体高 度,其中,=1,2,209i。 图 2 图片聚类指标示意图 令 iii Dab或 iii Dcd,称 i D 为第i张图片的裁截距( =1,2, 209)i, 由图
15、 2,如 1212 ,aa bb ,则 12 DD 。一般地,图片从上往下看,不同的裁截线形成的 裁截文字长度不同,文字间的行间距相同,所以,如果裁接处的文字长度不相等,那么 文字与空白间距之和就不相等。根据 i D 的不同取值,下面对图片进行分类。 根据二值化矩阵的特点以及文字的特征,只要存在文字,则矩阵的某一行元素一定 存在 0 元素,且在文字之间的元素为1。如下图所示: 图 3 文字特征图 利用matlab软件进行编程,将每个图片的裁截文字长度、行间距、裁截空白距离、 字体高度以及裁截距的结果以excel的形式输出到表格之中。 (程序见附录五) 按裁接距进行聚类分析, 使用spss软件分
16、析处理后,得到聚类中心分布图如下所示: 8 表 4 聚类中心 聚类中心 聚类 1 2 3 4 5 6 7 8 9 10 11 V1 7 52 32 120 44 58 133 64 109 69 78 根据表 4 所示的聚类中心,对表格中裁截距进行初步分类。得到聚类结果如下表 所示: 表 5 每个聚类中的案例数 每个聚类中的案例数 聚类1 2.000 2 36.000 3 18.000 4 1.000 5 46.000 6 38.000 7 1.000 8 36.000 9 1.000 10 11.000 11 19.000 有效209.000 缺失.000 根据聚类结果发现,并不能将图片平均
17、分成11 个组。这时需要增加信息量来更好 地进行分类,进一步观察图2,我们可以发现:图片的上端裁截处可能是文字,也可能 为空白。但是裁截距 i D 可能相等,此时通过图片上端裁截处是空白还是文字加以人工分 类。 用matlab将数据导出到excel中并进行分析,结果如下: 图 4 分析结果 -100 -50 0 50 050100150200250 高度 图片数量 9 由图 4 可以看出:图片大体分为 11 个组别,为了得到更精确地聚类结果, 通过spss 软件,我们再次确立聚类中心如下图所示: 表 6 第二次聚类中心 最终聚类中心 聚类 1 2 3 4 5 6 7 8 9 10 11 V1
18、25 2 40 -38 -93 -69 -84 15 34 -23 -10 通过上面两次聚类,确立了两个不同聚类中心。利用第一次确立的裁接距的聚类中 心对图片进行初步分类,然后利用裁截文字或者裁接空白再次进行判别,最终将图片分 成了 11 组。如下表所示:(以上的算法都是在matlab软件下操作,程序见附件六) 表 7 各组图片数量 组别012345678910111213 图片 数量 3188191918181918181810193 由上表可以看出大部分图片已经分出组别,其中有4 个组达到了 19 张图片,有 6 个组有 18 张图片,仅缺少一张图片。此时我们进行人工干预,根据每组图片总数
19、目应 为 19,且每类都应存在可作为文件左右边缘的碎纸片,我们对少量图片进行归类可得到 如下分组结果。如下表: 表 8 聚类后的结果 组别1 2 3 4 5 6 7 8 9 10 11 图 片 编 号 26183341350154 11191891242161071740 2220232414432129322789 28362625314766374533101 495230353958106445360102 546141385177109485671108 576350467384110556880113 656762748290125597083114 9169768110794139
20、649385117 957286881159714575126132119 118788710312811215092137133123 1297910010513412115798138152140 14196120122135124173104153156146 14399142130159127181111158165151 178116147148160136182171166170154 186131168161169144184172174198155 188162179167176149187180175200185 1901631911891991641972011962021
21、94 192177195193203183204206208205207 10 5.2.3 图片的拼接模型、算法与求解 (一)算法思想 下面我们分两步来做, 第一步,对每组碎纸片进行拼接; 第二步,将各组进行拼接。 最终完成文件复原。 在已知文件切为 1119 的碎纸片情况下,将图片进行聚类分析得到了11 个组后。 利用碎纸片左右边缘为空白的特点判断出文件左侧11 个碎纸片,再利用问题一模型和 算法,对每个组进行匹配拼接,可得到11 个拼接好的图片,之后仍然按照问题一的模 型和算法将这 11 张图片拼接成完整的图片。 (二)图片的左边缘确定 根据碎纸片边缘特征, 利用 matlab对图片处理后
22、得到数字化矩阵,根据最小二乘法 进行分析得到 16 个可作为文件左边缘的碎纸片,编号如下:(程序详见附录七) 7,14,29,38,49,61,62,67,71,80,89,94,125,135,143,168。 已知文件分为 1119 的碎纸片 ,那么存在 5 个不是左边缘碎纸片。 根据文件页边距 一定的特点,此时进行人工筛选,明显排除了编号分别62,67,80,135,143 的图片 作为文件左边缘的可能。此刻,我们也得到了左边缘碎纸片的序号: 7,14,29,38,49,61, 71,80,89,94,125,168。 (三)图片的各组拼接 第一步,计算机处理,利用问题一的列偏差函数进行
23、图片拼接,现在我们以表4 中 的第 9 组为例, ,得到如下结果:(程序详见附录八) 图 6 以第 9 组为例的拼接结果1 第二步,人工干预,由于每组有19 个图片,可以明显观察到排序的时候有一个图 片没有出现,而且另一个图片重复出现了两次。此时我们进行人工拼接。得到正确的拼 接结果,图片如下: 图 7 以第 9 组为例的拼接最终结果 其余分组按照相同方法可得到11 组的拼接结果,这里我们不在一一赘述,发现每 组的拼接均无误,这说明我们的分类达到了预期的效果。 11 (四)图片的整体拼接 上一步骤中我们得到了1119的碎纸片拼接而成的11个等大小的纸片,那么接 下来,根据行偏差函数,判断11个
24、纸片的上下拼接顺序,可以得到以下编号的图片可 以上下拼接: 30 8 169 39 15 95 50 62 完成以上组合的拼接后,进行人工干预,完成图片的整体拼接,结果如下(复原图 片详见附录九): 表 9 附件 3 拼接顺序 049054065143186002057192178118190095011022129028091188141 061019078067069099162096131079063116163072006177020052036 168100076062142030041023147191050179120086195026000087018 038148046161
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2013 全国 数学 建模 竞赛 优秀论文 要点
链接地址:https://www.31doc.com/p-5194120.html