2013高教社杯数模B题

2013高教社杯全国大学生数学建模竞赛

承 诺 书

我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。

我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： J3705 所属学校（请填写完整的全名）： 西京学院 参赛队员 (打印并签名) ：1. 郑 浩 2. 蒲 骏 3. 章锦炜 指导教师或指导教师组负责人 (打印并签名)： 刘苍毅

（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容

请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）

日期： 2013 年 9 月 13 日 赛区评阅编号（由赛区组委会评阅前进行编号）：

2013高教社杯全国大学生数学建模竞赛

编 号 专 用 页

评 阅 人 评 分 备 注 赛区评阅编号（由赛区组委会评阅前进行编号）：

赛区评阅记录（可供赛区评阅时使用）：

全国统一编号（由赛区组委会送交全国前编号）：

全国评阅编号（由全国组委会评阅前进行编号）：

碎纸片的拼接复原模型

摘要

碎纸片的拼接复原问题，是随着计算机的发展和碎纸机的应用在图像识别和处理方面的一个新课题。破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域具有广阔应用，用计算机代替人工拼接是提高拼接效率的最有效途径。

针对问题一，我们运用特征匹配的排序思想编程。分析碎片页面的左页边距特征，首先确定序首；根据不同碎片边缘之间像素的差异，记录并分析碎片的边缘数值特征，用禁忌搜素算法编程，从而实现了无人工干预复原碎片。

问题二分两个部分，对于中文碎片，用Matlab分析其页面汉字的位图和边缘特征，用页边距把碎片分作11行，再根据汉字中心确定每一行所包含碎片，继而根据文字边缘特征信息配合人工干预复原碎片。对于英文碎片，由于英文字母的四线三格的特性，我们根据页边距将碎片分划为11行，再利用碎片中英文的像素分布求出四线三格的位置，继而根据边缘特征信息配合手工干预完成拼接。但由于英文碎片变小后边缘特征匹配的算法存在一定局限性，所以人工干预次数达到百次。

问题三是对双面碎片拼接还原。由于大量的隐形的四线三格信息很难精确的统计，所以我们在完成了基本的页边距匹配、位图信息匹配、边缘特征匹配后仍存在大量未定型数据，由于碎片包含有效信息不足，双面碎片牵扯过多，导致后面的人工干预量较大。

关键词：特征匹配，Matlab，禁忌搜素算法，碎片还原，位图特征，边缘特征

1

一、问题重述

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

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

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

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

二、模型假设

1、假设碎纸机破碎纸片时纸片没有任何损耗。

2、假设所有碎纸片的原文档均有页边距且页边距大于字间距。 3、假设所有碎纸片的源文档页面没有污点。

4、假设属于同一张文档的所有碎纸片上显示内容的字号和字体是相同的。

三、符号说明 A L 碎纸片图像在Matlab中对应的矩阵 矩阵左侧空白列的个数 汉字的高度 有效汉字的中心 英文字母的中心 汉字的实际高度像素值 H Pc Pe Max(Height)、Min(Height) 2

四、问题一 模型的建立与求解

4.1 模型分析

常规碎纸片拼接复原方法一般利用碎片边缘的尖点特征、尖角特征、面积特征等集合特征，搜索与之匹配的相邻碎纸片并拼接[1]，而这种方法并不适用于本题中所有碎纸片形状完全一样的情况。

由于本问题中碎纸片均来自同一页印刷文字文件，碎纸片之间没有任何损耗，且仅考虑纵切的情况。根据观察，我们假设原文档存在页边距，且页边距大于字间距，所以我们首先遍历每一张碎纸片，选取左侧空白列最大的碎纸片作为最左一列；其次，根据每一张碎纸片的最右侧列与其他碎纸片进行相似匹配，选取相似度最高的一组，即两张碎纸片连接处同一行像素差值最小；最后按照相似度高低从左到右依次进行匹配。

4.2 模型建立

1、用Matlab读取碎片图像，每个碎片图像生成一个i行j列的矩阵A，矩阵每一个元素对应图像的RGB值，取值范围0~255。

2、按列遍历每一张碎片图像的矩阵，记录矩阵左侧空白列的个数为Ln，选取列数最多的碎片图像max为复原图象的最左列。左页边距示意如图1： （Ln）图1 左页边距示意图

3

am?1b13、用该像素矩阵的右边像素矩阵Aij逐个与剩余的像素矩阵的左边像素矩阵Aij做

差值求最小值处理，即：

am?1b1 （1） min?Aij?Aij3若求得最小值，则图像矩阵A11与其匹配，反之则循环式（1）直至得到最小值为止。

因切割方式的任意性，即使相连的两个碎片图像也可能不完全匹配。相连两个碎片图像008和014差值如图2所示：

图2 相连2个图的差值

4.3 模型求解：

1、使用Matlab函数readSubImage(见附录4.1)读取附件一中的碎片图像得到矩阵

A(n)1980?72(n?1,2,3,...,19)。

2、使用Matlab函数judgeLeft函数(见附录4.3)分别对19个矩阵从左到右逐列扫描，记录第一次出现值不是255的元素的列数，得到数据如表1：

4

表1 矩阵左侧空白列个数

A1 1

A2 1

A3 1

A4 1

A5 1

A6 1

A7 1

A8 1

A9 12

A10 1

A11 1

A12 1

A13 1

A14 1

A15 1

A16 1

A17 1

A18 1

A19 1

通过上表可知第九张碎片的左边距最大，故我们选取第九张作为起始点，提取其矩阵右边第一列与剩下18个矩阵的左边第一列依次进行比较，取相似度最高的一个矩阵然后取A(n)的右边第一列与剩下的17个左边第一列比较，选取A(n)与矩阵A(9)进行匹配；

相似度最高的与之匹配；以此类推，得出附件一的复原图像（见附录1）；同理可得附件二的复原图像（见附录1）。用Matlab函数judge（见附录4.2）可全部由计算机自动进行复原，复原后的碎片顺序如下表：

表2 附件一复原顺序

列数 编号 列数 编号 列数 编号 1 008 8 016 15 011 2 014 9 001 16 007 3 012 10 004 17 017 4 015 11 005 18 000 5 003 12 009 19 006 6 010 13 013 7 002 14 018 表3 附件二复原顺序

列数 编号 列数 编号 列数 编号 1 003 8 000 15 012 2 006 9 005 16 014 3 002 10 001 17 017 4 007 11 009 18 016 5 015 12 013 19 004 6 018 13 010 7 011 14 008 4.4 模型评价与推广

5

本模型利用左侧页边距定位初始图像，逐个比较图像连接处相似度的方法进行匹配。该方法简单快速精确，且全部由计算机程序实现，无需人工干预。此模型只有在本题这种碎片较少且边缘规整的情况下能获得很高的准确度，但当碎片较多的时候，准确度会有所降低。

该模型可以推广到其他领域，如基于图像融合的全景拍摄、历史文献的修复等。

五．问题二 模型的建立与求解

5.1 问题分析

本题在问题一的基础上加入了横切，碎片图像大幅增多，且每一张图像的信息量大幅减少。因此在问题一模型的基础上加入了人工干预，通过程序与人工干预相结合的方法提高复原的速度与准确性。

5.2 模型建立

1、用Matlab读取碎片图像，生成一个i行j列的矩阵A，矩阵每一个元素对应图像的RGB值，取值范围0~255。

2、按列遍历每一张碎片图像的矩阵，记录矩阵左侧空白列的个数为Ln，选取列数最多的碎片图像max为复原图象的最左列。 （Ln）3、对于汉字，提取所有碎片图像中汉字的像素，经计算处理得到汉字的高度H。遍历每一个碎片矩阵中的汉字像素，对于H大于36像素图像看作有效汉字，计算有效汉字的高度中心Pc。经观察计算，一个碎片图像的有效汉字最多为3个。汉字区域的选取如图3所示：

6

图3 汉字区域示意图

对于英文，由于大写字母占据英文4线三格中的上两格，大写字母只出现于句首、人名、缩写或专有名词，且小写字母中只占中间格的个数占1/2。英文4线三格如图4所示：

图4 英文4线三格图

经观察计算可知碎片图像中英文所在四线三格的每一格占25个像素，每一个图像最多包含3个英文字母。因此提取每一张碎片矩阵中每一行有效像素的个数，根据有效

7

像素的分布，选取英文字母分布最多的区域D，计算英文字母高度的中心Pe。英文有（n）效分布如图5所示：

图5 英文有效像素分布图

4、遍历每一个碎片图像，与已确定最左侧的碎片图像进行中心点的匹配，确定与最左侧图像同一行的碎片图像。根据计算机提供的不同方向上最大相似度的图片，配合人工干预调整每一行左右之间顺序，不同行上下之间的顺序，可迅速求得复原图像。

5.3模型求解

5.3.1 汉字模型的求解

1、用Matlab函数readSubImage(见附件4.1)提取附件3中的209个碎纸片图像矩阵，建立图像矩阵：

kAij(k?1;i?1,2,3,?,19;j?1,2,3,?,11)

其中，am?1表示除过最左列剩余矩阵的左边；b1表示最左列矩阵的右边。

2、用Matlab函数leftArray(见附录4.5)对每一张碎片图像左侧空白列的个数进行排序，选取左侧空白列最多的11张图像，作为复原图像的最左列。得到数据如表4所示：

8

表4 复原图像最左列序号

A1 14

A2 89

A3 7

A4 29

A5 38

A6 49

A7 61

A8 71

A9 94

A10 125

A11 168

3、提取碎纸片上的汉字计算其的实际高度像素值，得到：

Max(Height)?42

以像素值42为汉字最大高度，对小于像素值42的方向搜索寻找能构成有效汉字的最小高度，通过扫描搜索碎纸片上的汉字，得到：

Min(Height)?36

4、用Matlab函数calCircle(见附录4.8)提取最左列图像矩阵中的一个矩阵，如：图

3像矩阵A5,1,读取矩阵中的文字“转”和“堪”，文字“转”顶部到碎片顶部部的像素距离

L1?68,文字底部到碎纸片顶部的像素距离L2?109，则文字的实际像素高度

Height?L2?L1?41,文字中线到碎纸片顶部的像素距离L3?88.5，同理可得“堪”的中线到碎纸片底部的像素距离L4?157。取红线之间中点的像素距离，如图6所示：

图6 汉字中心距离示意图

9

以文字中线到碎纸片顶部的像素距离L3?88.5和L4?157为基准，扫描剩余图像矩阵中文字中线到碎纸片顶部像素不大于3个像素的碎片图像矩阵，得到改行的一组像素值，如表：

表5 其中一行的像素距离

20.5000 89.0000 0 20.5000 90.0000 0 21.0000 89.0000 0 21.0000 89.5000 0 21.5000 89.0000 0 21.5000 89.5000 0 22.5000 90.5000 0 89.5000 157.5000 0 20.5000 89.0000 157.5000 20.5000 89.5000 157.5000 21.0000 88.5000 157.5000 21.0000 89.0000 157.0000 21.0000 89.0000 157.5000 21.0000 89.0000 157.5000 21.0000 89.0000 158.0000 21.0000 89.0000 158.0000 21.0000 90.0000 158.0000 21.5000 89.0000 157.5000 23.0000 89.5000 157.5000

3由上表可得与图像矩阵A5,1同一行的剩余18个碎片图像矩阵。

5、用Matlab函数sameRow(见附录4.10)与最左侧的碎片图像矩阵匹配，得到的无序顺序如表6所示：

10

表6 无序的排列表

003 005

012 040

014 031 039 051 073 082 107 115 128 134 135 159 160 169 176 199 203 089 101 102 108 113 114 117 119 123 140 146 151 154 155 185 194 207

001 0007 032 045 053 056 068 070 093 126 137 138 153 158 166 174 175 196 208 006 008 002 006 015 034 013

010

029 037 044 048 055 059 064 075 092 098 104 111 171 172 180 201 206

009 0024 025 035 038 046 074 081 088 103 105 122 130 148 161 167 189 193 011 0022 028 049 054 057 065 091 095 0118 129 141 143 178 186 127 190 192 019 017 042 016

020 036 052 061 063 067 069 072 078 079 098 099 116 131 162 163 177 027 033 060 071 080 083 085 132 133 152 157 165 170 198 200 202 205 043 047 058 077 084 090 094 097 112 121 124 127 136 144 149 164 183 021 066 106 109 110 125 139 145 150 157 173 181 182 184 187 197 204 023 026 030 041 050 062 076 086 087 100 120 142 147 168 147 191 195

0001 018

6、用Matlab函数sortData(见附录4.7)计算每一个图像4个方向的最佳连接矩阵，用Matlab函数DrawH（见附录4.11）和DrawV（见附录4.12）辅助程序人工干预，调整图像矩阵左右之间、上下之间的顺序，既即可得到附件三的碎片复原图（见附录2）。辅助程序DrawH和DrawV如图7、8所示：

图7 DrawH演示(上三图为向左拼接,下三图向右拼接)

11

图8 DrawV演示(左三图向上拼接,右三图向下拼接)

附件三的复原顺序如表7所示：

表7 附件三复原顺序

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

5.3.2 英文模型的求解

1、用Matlab函数readSubImage(见附录4.1)提取附件4中的209个碎纸片图像矩阵，建立图像矩阵：

12

kAij(k?2;i?1,2,3,?,19;j?1,2,3,?,11)

2、用Matlab函数leftArray(见附录4.5)对每一张碎片图像左侧空白列的个数进行排序，选取左侧空白列最多的11张图像，作为复原图像的最左列。

3、提取碎纸片上的英文计算其所在四线三格的每一格高度，得到：

Max(Height)?25

以像素值25为最大高度，对小于像素值25的方向搜索寻找能构成有效英文部分的最小高度，通过扫描搜索碎纸片上的英文，得到：

Min(Height)?23

4、用Matlab函数calEngCircle(见附录4.9)计算每一个碎片图像中有效英文部分的中点，1张碎片图像中有效英文部分的中点个数最多为3个。

5、用Matlab函数sameData(见附录4.10)依次与最左侧列的碎片图像矩阵进行匹配，得到的无序顺序如表

6、用Matlab函数sortData(见附录4.7)计算每一个图像4个方向的最佳连接矩阵，用Matlab函数DrawH和DrawV辅助人工干预调整图像矩阵左右之间、上下之间的顺序既即可得到附件四的碎片复原图（见附录2）。

附件四的复原顺序如表8：

表8 附件四复原顺序

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 200 031 020 041 108 116 136 073 036 207 135 015 076 043 199 045 173 080 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

5.4 模型的评价与推广

13

该模型首先根据左侧页边距进行复原图像最左列的定位，其次根据图像中有效汉字

的中心位置与图像顶部的距离或有效英文的中心位置与图像顶部的距离确定同一行的图像，最后通过程序计算任意图像相邻4个方向的最佳连接图像，辅助人工进行排序，获得复原图像。整个流程通过计算机程序的运算，可大大降低人工干预的操作量，提高了复原效率，但对于某些含信息量较少的图像，会存在程序无法进行有效匹配的情况，这时需要进行人工干预。

该模型可推广至其他领域，如文物碎片拼接、笔记鉴定等。

六．问题三模型的建立与求解

6.1模型分析

本题在问题一和问题二的基础上对源文档进行了双面打印，碎纸片的图像矩阵数量

增加到了418个，图像所显示的信息量较问题一和问题二增大。大幅增加了图像复原的难度，应用解决问题二的方法难以快速准确的复原图像。因此在本模型中我们先对碎纸片的图像进行分类汇总，然后在运用基于点线拼接模型复原分类汇总的图像，最后人工干预得出最终结果。

6.2 模型建立

先人工干预以英文在四线三格中所占位置的规格和碎纸片中英文的行数归类汇总，分别建立不同规格碎纸片图像库。

Matlab读取各个图像库中的碎片图像，生成一个i行j列的矩阵A，矩阵每一个元素对应图像的RGB值，取值范围0~255。

按列遍历每一张碎片图像的矩阵，记录矩阵左侧空白列的个数为Ln，选取列数最多的碎片图像max为复原图象的最左列。 （Ln）对于英文，由于大写字母占据英文4线三格中的上两格，大写字母只出现于句首、人名、缩写或专有名词，且小写字母中只占中间格的个数占1/2。经观察计算可知碎片图像中英文所在四线三格的每一格占25个像素，每一个图像最多包含3个英文字母。因此提取每一张碎片矩阵中每一行有效像素的个数，根据有效像素的分布，选取英文字母分布最多的区域B（n），计算英文字母高度的中心Pg。

14

遍历每一个碎片图像，与已确定最左侧的碎片图像进行中心点的匹配，确定与最左侧图像同一行的碎片图像。经人工干预调整每一行左右之间顺序，不同行上下之间的顺序，可迅速求得复原图像。

6.3 模型的求解

用Matlab函数imread(见附录)提取各个图像库的碎纸片图像矩阵，可以得到复原的碎纸片的序列号,a面如表9所示，b面如表10所示：

表9 附件五a面复原顺序

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

52b

71a

33a

173a 119b 160a 095b 051a 048b 133b 023a

054a 196a 112b 103b 055a 100a 106a 091b 049a 026a 113b 134b 104b 006b 123b 109b 096a 043b 099b

表10 附件五b面复原顺序

078b 089a 186b 199b 088b 114a 146a 165b 003b 023b 099a

111b 010b 153a 011b 107a 184b 171b 195a 007b 133a 043a

125a 036a 084b 161a 149b 179b 031a 128a 085b 048a 096b

140a 076b 042b 169b 180a 116b 201a 157a 148b 051b 109a

155a 178a 030a 194b 037b 207a 050a 168a 077a 095a 123a

150a 044a 038a 173b 191a 058a 190b 046a 004a 160b 006a

183b 025b 121a 206b 065b 158a 092b 067a 069a 119a 104a

174b 192a 098a 156a 115b 197a 019b 063b 032a 033b 134a

110a 124b 094b 034a 166b 154b 016b 075b 074b 071b 113a

066a 022a 061b 181b 001b 028b 177b 167a 126b 052a 026b

108a 120b 137b 198b 151b 012a 053b 117b 176a 062a 049b

018b 144a 045a 087a 170b 017b 202a 008b 185a 129b 091a

029a 079a 138a 132b 041a 102b 021b 068b 000b 118b 106b

189b 014a 056b 093a 070b 064b 130a 188a 080b 101a 100b

081b 059a 131b 072b 139b 208a 163a 127a 027a 015b 055b

164b 060a 187b 175a 002a 142a 193b 040a 135b 205a 103a

020a 147a 086b 097a 162b 057a 073b 182b 141a 082b 112a

047a 152a 200b 039b 203b 024a 159a 122a 204b 145a 196b

36b 005a 143b 083a 090a 013a 035a 172a 105a 009b 054b

6.4 模型的评价与推广

该模型针对双面碎片数据，通过页边距特征提取、位图信息提取、边缘特征提取等计算机辅助操作进行筛选，能有效排除部分碎片，配合人工干预能完成碎片的拼接。但由于碎片信息量不足，相连条件过多，在存在大量碎片的情况下，程序难以快速精准的给出方案，需要大量借助人工干预。

15

七、参考文献

[1].罗智中.基于文字特征的文档碎纸片半自动拼接.计算机工程与应用，05：1-1， 2012 [2]袁家祖，灰色系统理论及其应用，北京：科学出版社，1992。 [3]贾海燕.碎纸自动拼接关键技术研究.2005.11

[4]王俊杰，刘家茂.图像拼接技术[J].计算机科学，2003，30(6):141-144.

[5]杨恒，梁德群.基于图像信息测度的多尺度边缘检测方法模式识别与人工智能，1999，11(1):442-446

[6]吴建国，数学建模案例精编，

北京：中国水利水电出版社，2005。

16

附录

附录1

附件一复原图：

17

附件二复原图：

附录2

附件三复原图：

18

附件四复原图：

19

附录3

附件五复原图a：

20

附件五复原图b：

21

22

附录4

附录4.1

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 读取目录下所有图像 % 参数:

% filePath 图像所在路径 % 返回值:

% data 所有图像的值,存储在cell中 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function data = readSubImage(docPath)

%遍历目录下所有文件

tempPath = sprintf( '%s\\\\*.bmp',docPath); fileName = dir(tempPath);

%依次读入所有图像

for i=1:length(fileName)

filePath = sprintf( '%s\\\\%s',docPath,fileName(i).name); data{i} = imread(filePath); end

附录4.2

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 拼接图像,显示图像，试用于1*n的碎片 % 参数:

% data 图像RGB数据 % 返回值:

% array 拼接出的序号，此程序序号从0开始，即0为000 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function array = judge(data)

%计算有多少个子图 temp = size(data); dataNum = temp(2);

%根据子图左页边距的像素遍历，计算最大空白像素的列的序号 maxPix = 0; leftIndex = 0; for i = 1:dataNum

temp = judgeLeft(data,i); if maxPix < temp maxPix = temp; leftIndex = i; end end

%记录拼接后的第一个子图序号 array(1) = leftIndex;

%拼接

23

for n = 1:dataNum - 1 minCount = 0; index = 0;

for i = 1:dataNum

length = size(array); %记录已经拼接的个数 flag = 0;

%如果已经取过了，则跳过，跳2层 for j = 1:length(2); if array(j) == i flag = 1; break; end end

if flag == 1 continue; end

%比较二值化后有多少个不同点

count = calPoint(data,array(length(2)),i,2);

%记录最小值

if minCount == 0

minCount = count; index = i; end

if minCount > count minCount = count; index = i; end end

%当前拼接长度

length = size(array);

array(length(2)+1) = index; end

%显示图像

fullData = data{array(1)}; for i = 2:dataNum

fullData = [fullData,data{array(i)}]; end

imshow(fullData);

%将排列减1，即以前从1开始，现在从0开始 array = array - 1;

附录4.3

24

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 按列判断左页边距像素 % 参数:

% data 图像RGB数据

% col 最左边子图像的序号，从1开始 % 返回值:

% result 子图像出现的第一个非白色的像素所在列 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function result = judgeLeft(data,col)

%计算图像像素

dataSize = size(data{col});

%返回为0则表示该列完全是空白的，即错误结果 result = 0;

%按列遍历第一个出现的非白色像素 for i = 1:dataSize(2) for j = 1:dataSize(1)

if data{col}(j,i) ~= 255 result = i; return; end end end

附录4.4

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 计算相邻子图不同像素点的个数 % 参数:

% data 图像RGB数据 % a 左子图所在的序号 % b 右子图所在的序号

% mode 1为向左 2为向右 3为向上 4为向下 % 返回值:

% count 相邻子图不同像素点的个数

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function count = calPoint(data,a,b,mode)

%计算子图的尺寸

dataSize = size(data{1});

%遍历最佳阀值

count = 0; %记录该阀值有多少个不同点 A = data{b}; %记录右图的图像数据 B = data{a}; %记录左图的图像数据

if mode == 1

%比较有多少个不同点

25

for i = 1:dataSize(1)

if A(i,dataSize(2)) ~= B(i,1);

count = count+1; %记录不同点的个数 end end end

if mode == 2

for i = 1:dataSize(1)

if A(i,1) ~= B(i,dataSize(2));

count = count+1; %记录不同点的个数 end end end

if mode == 3

for i = 1:dataSize(2)

if A(dataSize(1),i) ~= B(1,i);

count = count+1; %记录不同点的个数 end end end

if mode == 4

for i = 1:dataSize(2)

if A(1,i) ~= B(dataSize(1),i);

count = count+1; %记录不同点的个数 end end end

附录4.5

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 计算左侧图像的序号 % 参数:

% data 图像RGB数据 % 返回值:

% Array 计算出的左侧序号，从1开始记录，1即000

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function LeftArray = leftArray(data)

%计算有多少个子图 temp = size(data); dataNum = temp(2);

%根据子图左页边距的像素遍历，记录最大空白像素的列的序号 for i = 1:dataNum

templeftArray(i) = judgeLeft(data,i); end

26

%降序排序,index为排序后对源数据的所引致

[sortLeftArray,index] = sort(templeftArray,'descend');

%取前m个索引数,即第一列的序号 for i = 1:11

LeftArray(i) = index(i); end

附录4.6

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 计算子图某一方向空白点的像素个数 % 参数:

% data 图像RGB数据 % num 图像编号

% mode 1为向左 2为向右 3为向上 4为向下 % 返回值:

% count 空白像素点的个数

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function count = calWhitePoint(data,num,mode)

%计算子图的尺寸

dataSize = size(data{1});

count = 0; %记录有多少个不同点

A = data{num};

if mode == 1

%比较有多少个不同点 for i = 1:dataSize(1) if A(i,1) == 255

count = count+1; %记录白色点的个数 end end end

if mode == 2

for i = 1:dataSize(1)

if A(i,dataSize(2)) == 255

count = count+1; %记录白色点的个数 end end end

if mode == 3

for i = 1:dataSize(2) if A(1,i) == 255

count = count+1; %记录白色点的个数 end end

27

end

if mode == 4

for i = 1:dataSize(2)

if A(dataSize(1),i) == 255

count = count+1; %记录白色点的个数 end end end

附录4.7

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 计算每一图与其他图的不同点的个数 % 参数:

% data 图像RGB数据 % 返回值:

% l 与左图的距离 % r 与右图的距离 % u 与上图的距离 % d 与下图的距离

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [l,r,u,d] = sortData(data)

%计算有多少个子图 temp = size(data); dataNum = temp(2);

%遍历每一个图

for i = 1: dataNum for j = 1:dataNum

%计算与其他图不同点的个数 ll(j) = calPoint(data,i,j,1); rr(j) = calPoint(data,i,j,2); uu(j) = calPoint(data,i,j,3); dd(j) = calPoint(data,i,j,4); end %排序

[sortll,indexll] = sort(ll,'descend'); [sortrr,indexrr] = sort(rr,'descend'); [sortuu,indexuu] = sort(uu,'descend'); [sortdd,indexdd] = sort(dd,'descend'); %存储

l{i} = indexll; r{i} = indexrr; u{i} = indexuu; d{i} = indexdd; end

28

附录4.8

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 计算每一个中文子图中心点的位置，1个子图最多3个有效字 % 参数:

% data 图像RGB数据 % 返回值:

% arr 每一个子图有效字的中心点位置

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function arr = calCircle(data)

%记录每一个图片的黑色 ud = zeros(209,180) ;

%结果，因为一个子图最多有3个 arr = zeros(209,3);

%按行遍历，记录每一行是否有黑色 for i = 1:209 for x = 1:180 for y = 1:72

if data{i}(x,y) ~= 255 %当前行有黑色 ud(i,x) = 1; break; end end end end

%记录超过36个像素的字的中心位置，存入数组 for num = 1:209 co = 0; count = 0; for i = 1:179

%如果连续小于36则清零

if count < 36 && ud(num,i+1) ~= 1 count = 0; end

%大于36则记录中心位置

if count >= 36 && ud(num,i+1) ~= 1 co = co+1;

arr(num,co) = i - count/2; count = 0; end

%如果连续则计数器+1

if ud(num,i) == 1 && ud(num,i+1) == 1 count = count + 1; end

29

end end

附录4.9

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 计算每一个英文子图中英文所在四线三格中间格子的位置 % 参数:

% data 图像RGB数据 % 返回值:

% arr 每一个子图英文所在四线三格中间格子的位置 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function arr = calEngCircle(data)

%记录每一个图片的黑色 ud = zeros(209,180) ;

%结果，因为一个子图最多有3个英文字符 arr = zeros(209,3);

%按行遍历，记录每一行是否有黑色 for i = 1:209 for x = 1:180 count = 0; for y = 1:72

if data{i}(x,y) ~= 255 %当前行有黑色 count = count + 1; end end

ud(i,x) = count; end end

%记录超过36个像素的字的中心位置，存入数组 for num = 1:209

co = 0; %记录第几个字母 count = 0; %记录黑色个数 sum = 0;

for i = 1:179

if ud(num,i) > 12 && ud(num,i+1) > 12 sum = sum + ud(num,i); count = count + 1; end

%遇到23个以上黑色的时候

if ud(num,i+1) <= 12 && count >= 23 %记录

co = co + 1;

arr(num,co) = i - count / 2;

%清零

30

sum = 0; count = 0; end

%如果下一个为白色且没有连续23个黑色，则清零 if ud(num,i+1) <= 12 && count < 23 sum = 0; count = 0; end end

if co == 0 ud(num,:) end end

附件4.10

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 已知最左列的情况下求同一行的数据 % 参数:

% data 图像RGB数据

% arr 子图像的中心点数组

% leftArray 最左列的坐标 1x11的数组 % 返回值

% Array 返回无序的行

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function Array = sameRow(data,arr,leftArray)

%控制变量 n1= 0; n2= 0; n3= 0; n4= 0; n5= 0; n6= 0; n7= 0; n8= 0; n9= 0; n10= 0; n11= 0;

%使每一行的每一个分别减最左列的，如果相差小于3，则代表是同一行 for i = 1:209 flag = 0; for j = 1:3 for k = 1:3

if arr(i,j)~= 0 && (abs(arr(i,j) - arr(leftArray(1),k))<3 || (n1> 1 && abs(arr(i,j) - arr(Array(1,n1),k))<3))

31

n1 = n1 + 1; Array(1,n1) = i; flag = 1; break; end

if arr(i,j)~= 0 && (abs(arr(i,j) - arr(leftArray(2),k))<3 || (n2> 1 && abs(arr(i,j) - arr(Array(2,n2),k))<3)) n2 = n2 + 1; Array(2,n2) = i; flag = 1; break; end

if arr(i,j)~= 0 && (abs(arr(i,j) - arr(leftArray(3),k))<3 || (n3> 1 && abs(arr(i,j) - arr(Array(3,n3),k))<3)) n3 = n3 + 1; Array(3,n3) = i; flag = 1; break; end

if arr(i,j)~= 0 && (abs(arr(i,j) - arr(leftArray(4),k))<3 || (n4> 1 && abs(arr(i,j) - arr(Array(4,n4),k))<3)) n4 = n4 + 1; Array(4,n4) = i; flag = 1; break; end

if arr(i,j)~= 0 && (abs(arr(i,j) - arr(leftArray(5),k))<3 || (n5> 1 && abs(arr(i,j) - arr(Array(5,n5),k))<3)) n5 = n5 + 1; Array(5,n5) = i; flag = 1; break; end

if arr(i,j)~= 0 && (abs(arr(i,j) - arr(leftArray(6),k))<3 || (n6> 1 && abs(arr(i,j) - arr(Array(6,n6),k))<3)) n6 = n6 + 1; Array(6,n6) = i; flag = 1; break; end

if arr(i,j)~= 0 && (abs(arr(i,j) - arr(leftArray(7),k))<3|| (n7> 1 && abs(arr(i,j) - arr(Array(7,n7),k))<3)) n7 = n7 + 1; Array(7,n7) = i; flag = 1; break; end

if arr(i,j)~= 0 && (abs(arr(i,j) - arr(leftArray(8),k))<3 || (n8> 1 && abs(arr(i,j) - arr(Array(8,n8),k))<3)) n8 = n8 + 1;

32

Array(8,n8) = i; flag = 1; break; end

if arr(i,j)~= 0 && (abs(arr(i,j) - arr(leftArray(9),k))<3 || (n9> 1 && abs(arr(i,j) - arr(Array(9,n9),k))<3)) n9 = n9 + 1; Array(9,n9) = i; flag = 1; break; end

if arr(i,j)~= 0 && (abs(arr(i,j) - arr(leftArray(10),k))<3 || (n10> 1 && abs(arr(i,j) - arr(Array(10,n10),k))<3)) n10 = n10 + 1; Array(10,n10) = i; flag = 1; break; end

if arr(i,j)~= 0 && (abs(arr(i,j) - arr(leftArray(11),k))<3 || (n11> 1 && abs(arr(i,j) - arr(Array(11,n11),k))<3)) n11 = n11 + 1; Array(11,n11) = i; flag = 1; break; end end

if flag == 1 break; end end end

附件4.11

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 根据左右方向的最佳匹配顺序输出备选图像供人工干预 % 提供的图像编号从1开始 % 参数:

% data 图像RGB数据 % l 向左的最佳匹配 % r 向右的最佳匹配

% num 待输出的图像编号，从1开始

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function DrawH(data,l,r,num)

l1 = [data{l{num}(209)},data{num}]; l2 = [data{l{num}(208)},data{num}]; l3 = [data{l{num}(207)},data{num}];

r1 = [data{num},data{r{num}(209)}]; r2 = [data{num},data{r{num}(208)}];

33

r3 = [data{num},data{r{num}(207)}];

subplot(2,3,1),imshow(l1),title(l{num}(209)); subplot(2,3,2),imshow(l2),title(l{num}(208)); subplot(2,3,3),imshow(l3),title(l{num}(207)) subplot(2,3,4),imshow(r1),title(r{num}(209)) subplot(2,3,5),imshow(r2),title(r{num}(208)) subplot(2,3,6),imshow(r3),title(r{num}(207))

附件4.12

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 根据上下方向的最佳匹配顺序输出备选图像供人工干预 % 提供的图像编号从1开始 % 参数:

% data 图像RGB数据 % u 向上的最佳匹配 % d 向下的最佳匹配

% num 待输出的图像编号，从1开始

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function DrawV(data,u,d,num)

u1 = [data{u{num}(209)};data{num}]; u2 = [data{u{num}(208)};data{num}]; u3 = [data{u{num}(207)};data{num}];

d1 = [data{num};data{d{num}(209)}]; d2 = [data{num};data{d{num}(208)}]; d3 = [data{num};data{d{num}(207)}];

subplot(1,6,1),imshow(u1),title(u{num}(209)) subplot(1,6,2),imshow(u2),title(u{num}(208)) subplot(1,6,3),imshow(u3),title(u{num}(207)) subplot(1,6,4),imshow(d1),title(d{num}(209)) subplot(1,6,5),imshow(d2),title(d{num}(208)) subplot(1,6,6),imshow(d3),title(d{num}(207))

34

r3 = [data{num},data{r{num}(207)}];

subplot(2,3,1),imshow(l1),title(l{num}(209)); subplot(2,3,2),imshow(l2),title(l{num}(208)); subplot(2,3,3),imshow(l3),title(l{num}(207)) subplot(2,3,4),imshow(r1),title(r{num}(209)) subplot(2,3,5),imshow(r2),title(r{num}(208)) subplot(2,3,6),imshow(r3),title(r{num}(207))

附件4.12

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 根据上下方向的最佳匹配顺序输出备选图像供人工干预 % 提供的图像编号从1开始 % 参数:

% data 图像RGB数据 % u 向上的最佳匹配 % d 向下的最佳匹配

% num 待输出的图像编号，从1开始

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function DrawV(data,u,d,num)

u1 = [data{u{num}(209)};data{num}]; u2 = [data{u{num}(208)};data{num}]; u3 = [data{u{num}(207)};data{num}];

d1 = [data{num};data{d{num}(209)}]; d2 = [data{num};data{d{num}(208)}]; d3 = [data{num};data{d{num}(207)}];

subplot(1,6,1),imshow(u1),title(u{num}(209)) subplot(1,6,2),imshow(u2),title(u{num}(208)) subplot(1,6,3),imshow(u3),title(u{num}(207)) subplot(1,6,4),imshow(d1),title(d{num}(209)) subplot(1,6,5),imshow(d2),title(d{num}(208)) subplot(1,6,6),imshow(d3),title(d{num}(207))

34

本文来源：https://www.bwwdw.com/article/eyo6.html