碎纸片的拼接复原
摘要
本文主要解决碎纸片拼接复原问题。利用附件所给碎纸片的数据，运用蚁群优化算法、Adaboost算法、Harris角点检测算法，利用Matlab软件编程求解，得到碎纸片拼接复原结果。
针对问题一，依据文字所在行的几何特征，先将文字进行二值化处理，得到文字的数据信息。运用蚁群优化全局匹配方案完成整体匹配，利用回溯的Best-First搜索算法，得到最佳候选匹配对，由于碎纸片形状相似，Best-First搜索算法会大大降低拼接效率，最后建立蚁群优化算法模型对复原结果进行优化，得到中、英文拼接复原图（见附录一）及顺序表（见表2、表3）。
针对问题二，先对附件3、附件4中的碎纸片进行像素特征分析，将每一个矩形像素特征区域的白色区域设为0、黑色区域设为1，利用Adaboost算法对碎纸片进行分类处理，再依据矩形像素特征进行匹配，得到拼接复原中文、英文图片。对每次匹配循环进行人工干预得出碎纸片的拼接复原顺序图（见附录二）及顺序表（见表4、表6）。
针对问题三，在对比经典角点检测算法的基础上，利用附件5中图片的信息，运用Harris角点检测的多层匹配图像拼接算法，得到图片的角点信息。采用标准互相关联法和互信息法对Harris角点进行粗匹配，之后根据特征点周围的边缘信息过滤为匹配点，再用RANSAC进行精确匹配，得到一幅完整的拼接复原图像。最后，运用神经网络边缘检测算法进行优化，快速的获取准确的碎纸片的拼接复原顺序图（见附录三）及顺序表（见表8、表9）。
关键词：蚁群优化算法 Adaboost算法 Harris角点检测神经网络
1 问题重述
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：
（1）对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。
（2）对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原并针对附件过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。
（3）上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。
2 问题分析
2.1问题一的分析
若对中、英文各一页文件的纵切碎纸片拼接复原，需考虑复原的碎纸片之间的边界衔接、字迹线条、图片属性、文字的行高、文字行间距及文字断线等信息。利用碎纸片文字所在行的几何特征，先对文字进行二值化处理。借助蚁群优化算法的全局匹配方案，完成整体匹配。再运用回溯Best-First搜索算法，得到最佳候选匹配对。考虑到碎片形状特征相似度高等原因，不合理的候选匹配对可能大量存在，导致拼接效率大大降低。再建立蚁群优化算法进行优化，利用Matlab编程得到碎纸片拼接复原结果。
2.2问题二的分析
若将中、英文各一页文件的纵切碎纸片拼接复原，利用Adaboost算法，先将附件3、附件4中给出的碎纸片分别进行编号，再将所有待匹配碎纸片进行初始化，然后进行错误率分析，根据误差分析结果来调整权重，得到分类结果。对所有碎片分类结果进行矩形像素特征分析，最后由矩形像素特征匹配出碎纸片的原图，对于匹配的循环进行人工干预得出碎纸片的排列顺序表。
2.3问题三的分析
若对双面打印文件的碎纸片拼接复原，需考虑正反面文字的对应情况，先用人工干预的方式对文件的部分碎纸片拼接复原。图像拼接复原需考虑图像特征，本文基于碎纸片的角点特征，利用附件5给出的一页英文印刷文字双面打印文件的碎纸片数据，在对
比经典角点检测算法的基础上，运用Harris角点检测的多层匹配的图像拼接算法，采用标准互相关联法对Harris角点进行粗匹配，之后根据特征点周围的边缘信息过滤为匹配点，再用RANSAC进行精确匹配，得到一幅完整的拼接复原图像。出于对结果准确性以及拼接快速性的考虑，运用BP神经网络边缘检测算法将结果进行优化。最后，利用数学期望、方差等统计特性参数对检测出来的边缘图像进行质量评价。
3模型假设
（1）假设碎纸片在复原过程中没有损坏、丢失的现象；
（2）假设碎纸机横、纵切割文件规则，不出现异常状况；
（3）假设模型计算的碎纸片拼接复原结果是唯一的；
（4）假设附件所给中、英文文件碎纸片数据不混淆；
（5）假设同一附件中纸片切割的大小、形状相同；
4符号说明
5 模型建立与求解
5.1模型一的建立与求解
5.1.1模型一的建立
常规文档碎纸片计算机拼接方法一般利用碎纸片边缘的尖点特征、尖角特征、面积特征，搜索与之匹配的相邻碎纸片进行拼接，这种基于边界几何特征的拼接方法并不适用于边缘性状相似的碎纸片。题中给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切）的形状相似，拼接时如果只利用碎纸片的边界特征，拼接效果并不理想。
对边缘相似的碎纸片的拼接，理想的计算机拼接过程应与人工拼接过程类似，即拼接时不但要考虑待拼接碎纸片边缘是否匹配，还要判断碎片内的字迹断线或碎片内的文字内容是否匹配以及理解碎片内文字图像含义。利用现有的技术，完全可以获取碎纸片文字所在行的几何特征信息，比如文字行的行高、文字行的间距及文字断线等信息。现
有技术对碎纸片拼接复原的流程图，如图一所示：
图一碎纸片拼接复原流程图
二维碎片自动拼接问题主要有两种方案：基于轮廓的拼接和基于内容的拼接。本文利用文字的特征运用蚁群优化的全局匹配对碎纸片自动拼接。正确合理参与拼接的碎片之间有一定的空间约束，不合理的拼接则可能会不满足这些约束而在候选匹配队之间造成矛盾。全局匹配是指在局部拼接的基础上，利用候选匹配队之间的矛盾剔除一些不合理的匹配，从而构建一个彼此两两相容的候选匹配对集合，从而完成整体的匹配。这里提到的不合理，是从全局的角度考虑的。
初步全局匹配完成后，用回溯的Best-First搜索算法将局部匹配得到的候选匹配对按照相似性度量进行排序，找出最佳候选匹配对。再用蚁群优化算法进行优化。回溯的Best-First搜索算法流程图如图二所示：
图二 基于回溯的Best-First 搜索算法
在实际的碎片拼接过程中，由于碎片形状特征相似等原因，不合理的候选匹配对大量存在。因此回溯会大大降低拼接的效率。本文再用蚁群优化算法进行优化求得结果。 ◆ 基于蚁群优化的全局匹配
如果完成了局部匹配，则构建了这样一个候选匹配对集合。但对于一组碎片的全局匹配来说，用于全局匹配的候选匹配对只需要一部分的正确候选匹配对，而不是全部。可以采用蚁群优化形成一个匹配路径，来选取用于全局匹配的候选匹配对。这个路径所含的候选匹配对刚好包含多个碎片。
当所考虑的问题服从问题相关约束时，可用成分的集合的一个子集来表示，这类问题被称作子集问题。这里所求的匹配路径上的候选匹配对是候选匹配对集合的一个子集，因此，全局匹配也可以看作有特殊约束的子集问题。从另一个角度，全局匹配也可以看做是一个求解整体没有矛盾的最小拼接代价的最有问题。所以，全局匹配路径的构建，可以借鉴ACO 算法用于解决自己问题的方法。设M 为候选匹配对集合，i M 表示其中一个候选匹配对。i c 表示i M 的匹配代价，
i y 表示在路径构建中i M 被选中的状态，
如果i M 被选中，那么i y 的值为1，否则为0：2(1)/2l n C l l ==-表示候选匹配对的个数，
l 表示碎片的个数。则基于ACO 的全局回复重建问题定义如下：
1
min ()n
i i i f y c y ==∑，{0,1}i y =，（ 1,2....i n =）
被选中的候选匹配对之间必须是相容的。 ◆ 图的构建以及数据初始化
在构建图(,)c G C L =中，成分集合C 对应着候选匹配对的集合，而连接集合L 不完全连接候选匹配对，与一个相容性列表相关联。用ij λ表示候选匹配对i M 和j M 之间的相容系数，i S 表示候选匹配对i M 的局部相似性度量，i R 表示i M 的信息素信息素初始化如下：
min
max min
0.10.8i i S S R S S -=+
⨯-
其中min S 表示所选匹配对中相似性度量的最小值，max S 为最大值[0.1,0.9]i R ∈。 候选匹配对的匹配代价也是同相似性度量相关联的,ACO 算法中的路程代价通常表示成整数所以本文中的匹配代价也采用类似表示:
min
max min
9080i i S S c S S -=-
⨯- [10,90]i c ∈
◆ 路径构建与信息素更新
人工蚂蚁根据信息素的浓度的大小，在路径中节点的领域并集中选择下一个访的节点。当前位于节点i 的人工蚂蚁k 选择j 作为下一个访问节点的概率是：
k
i i ij
k ij
i ij
l N R P R ηη
∈=
∑
k i j N ∈
其中： 1
i k k i
l l N G ==
,max{}
ij i j c c α
η=
k l G 是人工蚂蚁k 访问过的节点l 的领域，α是一个调节启发式比重的参数，,i c 和j
c 是节点i 和j 的匹配代价。每次路径构建完成后，人工蚂蚁只在当前最优路径的节点上释放信息素。释放信息素的多少可用下式表示。
min
i i a R R c ←+
max i R R ← max i ifR R >
min c i T ∈
其中，a 为信息素释放比例系数，min c 为当前最优路径代价，max R 信息素最大值，
min c T 为当今最优路径。
路径中的候选匹配对必须是彼此两两相容的,而矛盾的普遍存在导致很多人工蚂蚁构建路径失败。路径构建失败必然产生很多不完全路径, 对这些路径上的节点进行信息素更新, 以此来实现信息的蒸发：
(1)j j R R ρ←-
min max ,j j R R ifR R ←<
min c j T ∈
其中，ρ为信息素蒸发系数，满足(0,1)ρ∈，min R 为信息素的最小值。 路径构建过程中，下一节点的选取都是在已选节点的邻域中进行的，如果以构建路径中候选匹配对已包含所有碎片，则构建路径成功。
每迭代一次，信息素列表都更新一次如果迭代次数超过迭代次数下限min k , 并且信息素列表的标准差与上一次迭代相比没有变化, 则停止迭代,或者迭代次数已经达到 迭代上限max k
, 则停止迭代。
在局部匹配的基础上，如表1所示设置参数进行试验：
表中，m 为蚂蚁的数量，ρ表示信息素蒸发系数， a 表示信息素释放比例，α表示启发式比重参数，max R 表示最大信息浓度，min R 表示最小信息浓度，max k 表示最大迭代次数，min k 表示最小迭代次数。
5.1.2
模型一的求解
本文选取附件1中碎纸片（中、英文）的数据，运用蚁群优化算法，利用Matlab 软件编程（见附录一）求解，得到中文拼接复原图（见附录一），英文拼接复原图（见附录一）。中、英文拼接复原顺序见下表2，英文拼接复原顺序见下表3：
5.2.1模型二的建立
对于碎纸机既纵切又横切的情形，要求设计碎纸片拼接复原模型和算法，并针对附件3、4给出的中、英文各一页文件的碎片数据进行拼接复原。相对于问题一中的只有纵切的情形，本问既纵切又横切的情形在日常生活中更为普遍，相对来说解决这类问题更具有实际意义。本问运用Matlab 软件通过Adaboost 算法建立数学模型进行求解。 第一步，将附件3、4中给出的碎纸片进行编号()()(){}1122,,,,...,n n x y x y x y 。其中，i x 为输入待匹配碎纸片，i y 是分类类别标志，{}0,1i
Y y ∈,其中，0表示空白区域，1表示
黑色区域，n 为一共的待匹配碎纸片数量。
第二步，指定循环的次数T ，T 将决定最后强分类器中弱分类器的数目。
第三步，初始化权值：wl , 12i m =为样本中空白区域的初始化权值，1
2n 为样本中的
黑色区域初始化权值，其中，m 为样本中的空白区域所占像素数，n 为样本中黑色区域所占像素数。 第四步，对 1....t T
=
归一化权值：
,,,1t i
t i n
t i
j w q w ==
∑
◆ 对每个特征 f ，匹配一个弱分类器(),,,h x f p q ；计算对应所有特征的
弱分类器的加权()qt 错误率f ε。
(,,,)f i i i
i q h x f p y εθ=-∑
◆ 选取具有最小错误率
f
ε 的弱分类器(),,,h
x f p q 加入到强分类器中。
◆ 按照这个最佳弱分类器，调整权重：
11,,i e t i t i t w w β-+=
其中 0i e =，表示
i
x 被正确的分类， 1i
e
= 表示i x 被错误分类。
1t
t t
εβε=
- 进行T 轮匹配完毕，最后得到强分类器为：
11
1()0.5()0T T
t t t
t t h x H x otherwise αα==⎧
≥⎪=⎨⎪⎩
∑∑1
log
t t
αβ=
对于每一个碎纸片，含有大量的矩形像素特征（一般有上万个）设像素特征为
()1,2,3,...,i b i T =。在这个庞大的像素特征集合中只有一小部分像素特征能够用来构建
高效的分类器。我们通过前面的算法，在每一轮循环中从众多的矩形特征中选择最佳矩形像素特征。最佳特征对应的弱分类器的表达式为：
1()()0t t t t
t if p f x p h x otherwise
θ<⎧=⎨
⎩ 其中，()t f x 是矩形像素特征的特征值，
t θ为弱分类器的阈值，t p 表示不等式方向，t p 可取 1±。
由多个最佳弱分类器按照一定权值组合而成的较为复杂的分类器为强分类器。
11
1()0.5()0T T
t t t t t h x or H x otherwise ααθ
==⎧
≥⎪=⎨⎪⎩
∑∑ 其中
x 为待匹配碎纸片，()t h x 为构成该强分类器的第t 个弱分类器。上式右边为该
强分类器的阈值。()H x 的判断结果为0或者1，1表示接受，即矩形像素特征匹配成
功；0表示拒绝，即矩形像素特征匹配失败。级联分类器是由多个强分类器组成。如下图三所示：
图三碎纸片匹配流程图
目标纸片配对成功以后匹配成功以后进行下一轮循环，得到下一循环的匹配纸片，最终得到附件3、附件4给出碎纸片的拼接复原图。在循环过程中运用记号的方式进行人工干预，得到碎纸片的排列顺序。
5.2.2模型二的求解
利用附件3、附件4的数据，运用Adaboost算法，借助Matlab软件求解，得到中文拼接复原图（见附录二），英文拼接复原图（见附录二）。中文拼接复原顺序见下表4，英文拼接复原顺序见下表5：
对于模型二得到的结果图像（附录二）通过人工干预的方式进行检验，发现图像中有一处碎片不能确定复原位置，通过表格得到该碎片为049.bmp。得到正确的碎片排列顺序为表，结果见下表6：
图像特征是用于区分一个图像内部特征的基本属性。图像的特征信息很多，包括像素灰度特征、区域特征、色彩特征、轮廓特征、边缘特征以及角点特征等。图像的特征提取范围很广，从图像中提取什么样的特征，需要根据具体要求和应用来定。角点特征是图像拼接算法中最常用的匹配方法。本文基于文字角点特征，借助计算机技术，采用harris 角点检测的多层匹配图像拼接算法对碎纸片进行拼接复原。 5.3.1模型三的建立
角点检测算法较为典型的有Moravec 角点检测算法，SUSAN 角点算法和Harris 角点检测算法。
Moravec 角点检测算法
Moravec 角点检测算法的思想是：在图像中设计一个局部检测窗口，当该窗口沿各个方向作微笑移动时，考虑窗口的平均能量变化，当该能量变化值超过设定的阈值时，就将窗口的中心像素点提取未角点。其步骤为：
（1）计算各像素点的兴趣值。如图四所示的是以像素点（,x y ）为中心的5 5窗口，记像素点（,
x y ）的灰度为(,)f x y ，令图像的每个像素点（,x y ）在下图4个方向
相邻像素灰度差的平方和分别为1234,,,v v v v ，取四个中的最小值作为兴趣值。
图四 窗口示意图
(2)设定阈值，将兴趣值大于该阈值的像素点作为候选角点。
(3)在候选角点中先取局部极大值作为需要的特征点。这是因为在一定大小的窗口内，可以有多个符合该阈值的候选角点，所以要去掉不是最大兴趣值的候选点，只保留兴趣值最大的点。
Harris 角点检测算法
Harris 角点检测算法是Moravec 算法的改进。Harris 算法受信号处理中自相关函
数的启发，用一阶导数来描述亮度变化，并给出与自相关函数相关联系的矩阵M 。M 阵的特征值是自相关函数的一阶曲率。如果两个曲率值都很高，那么就认为该点是角点特征。
Harris 角点检测算法原理： Harris 算子的数学表达式：
2,(,)(,)[(,)(,)]x y
E u v w x y I x u y v I x y =++-∑
式中，(,)w x y 为窗函数，2
[(,)(,)]I x u y v I x y ++-为图像灰度值得梯度值。(,)
w x y 可为矩形窗或高斯窗。它的二阶泰勒级数展开式可以近似为(,)[,]u E u v u v M v ⎡⎤
=⎢⎥⎣⎦
其中，M 是2⨯2矩阵：
2
2
2
222
x y x x y
x y x I I I A M e C I I I δ+⎡⎤⎡⎤==⊗⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦
C B 其中，x I ，y I 分别为图像x ，y 方向的梯度值。E 的变化与局部自相关函数密切相关，矩阵M 描述了E 在原点的形状。若1λ，2λ是M 地 特征值，那么1λ，2λ与局部自相关函数的主要曲率成比例，都可以用来描述旋转不变性。
求解矩阵：
（1） 计算灰度图像各点的梯度：(1,0,1)
(1,0,1)
x T x I I I I =⊗-⎧⎪⎨=⊗-⎪⎩
（2） 构造自相关矩阵：22x y x y A I w
B I w
C I I w
⎧=⊗⎪=⊗⎨⎪
=⊗⎩ 由式可得对称矩阵A M C ⎡⎤=⎢⎥⎣⎦
C B 是一个二阶实对称矩阵，必然存在两个特征值1λ和
2λ。
（3） 提取特征点：符合两个特征值都是极大值的条件时，该点就为特征值。
SUSAN 角点检测算法
SUSAN 算子的基本原理是能过一个以点为中心的局部区域内亮度值的分布情况判断平滑区域、边缘和角点。
如图六所示，用一个近似为圆形的模板放置在图像上，如果存在一个区域，使该区域对应图像的每一个像素的灰度值与圆心的灰度值相同或接近。就定义该区域为核相似区。
图五 模板图和简单图像示例图
本文在求解过程时利用两张碎纸片的吻合度，吻合度大的碎纸片有可能拼接在一起，吻合度最高的碎纸片可以拼接复原。模板a 、b 、c 、d 都符合两张碎纸片的吻合度，模板e 完全不吻合。
具体检测时，用给定的圆形模板扫描整个图形，比较模板内每一像素点与中心像素的灰度值，并给定阈值来判别该像素是否属于USAN 区域。
三种检测结果比较分析可知在对简单物体的检测时，检测到的角点与Harris 算法很接近，在对复杂物体检测时，显然Harris 检测到的角点与Harris 检测到的角点更为到位，Harris 角点检测算法是一种比较有效的特征点检测方法，效率更高。
特征点匹配是指找出需要配准的两幅图片中正确匹配的特征点。本文围绕Harris 角点的互相关阀和互信息法来设计特征匹配算法。 标准互相关法
互相关匹配方法不直接利用特征点邻域的灰度值来匹配，而是依据特征点邻域像素灰度值得互相关系数为匹配原则进行匹配。相关系数为：
1
2
[()()]
i
i I x I
x CC -=
∑
式中，1I 和2I 分别为两幅图像中特征点相关联窗口内像素的灰度值，CC 是相关系数，w 表示窗口大小。
计算相关系数的同时进行了归一化处理，
1
1
2
2[()][()]
i
i wcc I x I I
x u I E -+-=
∑
式中， 1I 和2I 分别为图像1I 和2I 特征点相关窗口内像素灰度值的均值：
11
1()i
i w
I I x N
∈=
∑
221
()i i w
I I x N ∈=∑
◆ 互信息法
在图像配准中，当图像间的空间位置达到完全一致时，图像之间表达的信息达到最大，互信息最大的位置就是图像的配准位置。互信息法常用于多态图像配准。互信息法用熵来定义，设图像I 的灰度随机变量为A ,其灰度取值范围为123{,,,....}k a a a a ，灰
度概率分布为123{(),
(),(),....()}k p a p a p a p a ，则图像I 的熵为：
1
()()log ()k k k k H A p a p a ==-∑
设图像A I 、B I ，其灰度随机变量分别为A 、B ，灰度随机变量为(,)A B
则图像A I 、B I 的互信息I 可以定义如下：
(:)()(|)()(|)M A B H A H A B H B H B A =-=-
式中，(|)H A B 和(|)H B A 分别为给定B 时A 的条件熵和给定A 时B 的条件熵。 互信息法不需要对不同的成像模式中的图像强度做任何假设，而而是根据图像亮度在各自图像中的相对出现概率以及两幅图像重叠区域的共同出现概率来度量不同图像之间的对应关系。 ◆ 变换矩阵的估计：
经过图像特征的匹配后，需要估计两幅图像之间的变换矩阵。若,()i i x y 为匹配集合中一对匹配点对的坐标，则这对匹配点可以建立如下关系：
01234567m m m H m m m m m ⎡⎤
⎢⎥=⎢⎥⎢⎥⎣⎦
1
'012'34567
11i i i i x m m m x y m m m y m m ⎡⎤⎡⎤⎡⎤
⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥
⎣⎦⎣⎦⎣⎦ 1
'01267'3456711i i i i i i i i i i m x m y m x m x m y m x m y m y m x m y ++⎧=⎪++⎪⎨++⎪=⎪++⎩
只要联立四对点建立方程组就能求出其中的参数，求解变换矩阵就是建立图像间匹
配点之间的联系的过程。变换矩阵的算法是一种基于代数距的最小化方法。本文提取的特征点包含有错匹配点对，选取的估计方法一定有较好的容错能力，本文选用RANSAC 来作为变换矩阵的估计方法。 RANSAC 算法的基本思想：
RANSAC 是一种鲁棒性的数据拟合算法，具有容错能力强的特点。RANSAC 算法充分利用所测得所有数据，并根据阈值把他们分成内点和外点。其简化的流程图如图五所示：
图五 RANSAC 算法流程图
RANSAC 算法用内点来进行参数估计，剔除不合理的数据，从而得到一个最优的结果。 基于神经网络边缘的检测
图像的边缘是图像的最基本特征，边缘是指其周围像素灰度有阶跃变化的像素的集合。边缘检测是图像分析识别必不可少的环节，是一种重要的图像处理技术，但传统的算子算法存在着噪声和细节之间等的矛盾。本文基于BP 神经网络的数字图像边缘检测
可以较好地对碎纸片拼接复原。
◆ 初始值的确定
在设计中运用算法是BP 算法，根据梯度下降法来进行权值得调节。BP 模型中，神经元的函数为Sigmoid 函数。即：
1()1x F x e
-=
+ 其函数的导数为：'
()()(1())F x F x F x =-
此函数的最大值为x 取零时，其导数的取值为1/4，即神经元的节点函数的导数最大的点为零点，因此在BP 算法中，权值调节最大的点应该是零点。
对于网络的初始权值、阈值，通常的做法是从[-1,1]或[0,1]区间上随机选取一组数作为初始权值进行训练。
◆ 向量的归一化处理
设计中的特征向量维数较大，且大部分的值大于1，为了加快速度，对特征向量进行了归一化处理。另外，设计中进行的图像边缘检测是基于8位的图像的，其每个像素的灰度值都在[0,255]之间。特征向量可看成行向量，表示为：
012(,,....)n X x x x x =
归一化后的向量为： '
''''
012(,,,....)n X
x x x x =
其中，
'max()
i
j x X x = 0,1,2.....i n =;0,1,2,.....j n =
在8位的图像中，最大的灰度值是255（白色），所以在设计的实际处理过程中，归
一化结果为： '
255
i x X = 0,1,2.....i n =
由于归一化的原因，输出层计算的结果也是在[0,1]之间的，这个不是作为输出图像的像素的灰度值。在计算出输出层的结果后，再乘以255，就是输出图像像素的实际灰度值。
◆ 网络误差的确定
在神经网络学习之前，要定义网络的误差函数。通常使用的网络误差为均方差。即本文中对碎纸片拼接复原后质量的评价。
均差定义为：2
1
1()2N i j j E t R ==-∑
图像边缘检测质量的评价
图像质量的定位主要采用主观视觉的方法来确定图像的质量。主观评价主要有两种度量尺度：绝对尺度和相对尺度。
其核心是利用统计学的样本、方差等统计特性来描述边缘检测图像质量的。
数学期望：0
1()n
i i E X X n ==∑
方差：
2
2
1
1
()()1n
i i D X S X X n ===--∑
5.3.2模型三的求解
利用附件5的数据，运用Matlab 软件求解得到拼接复原后的英文拼接复原图（见附录三）及拼接复原顺序表，见下表8：
6 模型的评价与推广
6.1模型的优点
（1）模型解决了人工拼接复原文件效率低，难以短时间完成任务的问题。
（2）本文建立的模型结合发展的计算机技术，带来碎纸片拼接复原效率、准确率的提高，对我国传统文化典籍的传承、国防事业的发展及司法管理力度的提高具有重要意义。
（3）本文模型是对基于不规则碎片拼接复原模型的发展，利用文字的几何特征提出了拼接算法模型。
6.2模型的缺点
（1）题目要求对碎纸片拼接复原，模型执行程序对纸片进行拼接处理，程序编写复杂度较高。
（2）蚁群算法受起止点位置和障碍分布的影响，环境改变时蚂蚁容易陷入不可行点，甚至出现路径迂回和死锁。
6.3模型的推广
汉字识别应用领域越来越广，在生活中越来越重要,这就对识别系统的资源消耗和实时性提出更高的要求。本文建立的模型可推广应用于汉字识别系统，资源消耗少(不需要硬件加速)、识别速度快，有着很好的应用前景。
7 参考文献
[1] 秦襄培，《MATLAB图像处理宝典》，北京：电子工业出版社，2011年。
[2] Mark M.Meerscheart，《数学建模方法与分析（原书第二版）》，北京:机械工业出版社，2005年。
[3] Alex.ren,AdaBoost算法原理,
https://www.doczj.com/doc/e519024447.html,/cvlabs/archive/2010/04/16/1713119.html ，2013年9月
14日。
[4] 赵林亮,蚁群算法原理与应用1,
https://www.doczj.com/doc/e519024447.html,/view/c689205e804d2b160b4ec0a6.html, 2013年9月14日。
[5] 王沫然，《MATLAB 5.X与科学计算》，北京：清华大学出版社，2000年。
[6] 何仁斌，神经网络算法简介，
https://www.doczj.com/doc/e519024447.html,/view/faf4b94069eae009591bec05.html， 2013年9月15日。
[7] 肖锋，基于BP神经网络的数字图像边缘检测算法的研究，
https://www.doczj.com/doc/e519024447.html,/p-5035906335971.html，2013年9月15日。
8 附录
附录一：
模型一的程序：
clear all
nums = '000.bmp';
PicOut='c.jpg';
P(1,:,:)=imread('F:\MATLAB7\B\附件1\000.bmp');
P(2,:,:)=imread('F:\ MATLAB7B\附件1\001.bmp');
P(3,:,:)=imread('F:\ MATLAB7B\附件1\002.bmp');
P(4,:,:)=imread('F:\ MATLAB7B\附件1\003.bmp');
P(5,:,:)=imread('F:\ MATLAB7B\附件1\004.bmp');
P(6,:,:)=imread('F:\ MATLAB7B\附件1\005.bmp');
P(7,:,:)=imread('F:\ MATLAB7B\附件1\006.bmp');
P(8,:,:)=imread('F:\ MATLAB7B\附件1\007.bmp');
P(9,:,:)=imread('F:\ MATLAB7B\附件1\008.bmp');
P(10,:,:)=imread('F:\ MATLAB7B\附件1\009.bmp');
P(11,:,:)=imread('F:\ MATLAB7B\附件1\010.bmp');
P(12,:,:)=imread('F:\ MATLAB7B\附件1\011.bmp');
P(13,:,:)=imread('F:\ MATLAB7B\附件1\012.bmp');
P(14,:,:)=imread('F:\ MATLAB7B\附件1\013.bmp');
P(15,:,:)=imread('F:\ MATLAB7B\附件1\014.bmp');
P(16,:,:)=imread('F:\ MATLAB7B\附件1\015.bmp');
P(17,:,:)=imread('F:\ MATLAB7B\附件1\016.bmp');
P(18,:,:)=imread('F:\ MATLAB7B\附件1\017.bmp');
P(19,:,:)=imread('F:\ MATLAB7B\附件1\018.bmp');
s1=size(P);
x=s1(1)
y=s1(2)
z=s1(3)
%判断那张是最后一张图像
for i=1:x-1
psum(i)=0;
for j=1:y
if (P(i,j,z)~=255)
psum(i)=psum(i)+1;
end
end
end
%将最后一张图像移至最后
for i=1:x-1
if (psum(i)==0)
t=P(19,:,:);
P(19,:,:)=P(i,:,:);
P(i,:,:)=t;
end
end
%判断那张是第一张图像
for i=1:x-1
psum(i)=0;
for j=1:y
if (P(i,j,1)~=255)
psum(i)=psum(i)+1;
end
end
end
%将第一张图像移至最前面
for i=1:x-1
if (psum(i)==0)
t=P(1,:,:);
P(1,:,:)=P(i,:,:);
P(i,:,:)=t;
end
end
for k=1:x %求出第k张图片与剩余图片的吻合度
for i=k:x-1
psum(i)=0;
for j=1:y
if(P(k,j,z)~=255 && P(i+1,j,1)~=255) psum(i)=psum(i)+1;
end
end
end
%吻合度最高的图片应为下一张
for i=k:x-1
if (psum(i)==max(psum) && i~=k)
t=P(k+1,:,:);
P(k+1,:,:)=P(i+1,:,:);
P(i+1,:,:)=t;
2016年高教社杯全国大学生数学建模竞赛题目 （请先阅读“全国大学生数学建模竞赛论文格式规范”） A题系泊系统的设计 近浅海观测网的传输节点由浮标系统、系泊系统和水声通讯系统组成（如图1所示）。某型传输节点的浮标系统可简化为底面直径2m、高2m的圆柱体，浮标的质量为1000kg。系泊系统由钢管、钢桶、重物球、电焊锚链和特制的抗拖移锚组成。锚的质量为600kg，锚链选用无档普通链环，近浅海观测网的常用型号及其参数在附表中列出。钢管共4节，每节长度1m，直径为50mm，每节钢管的质量为10kg。要求锚链末端与锚的链接处的切线方向与海床的夹角不超过16度，否则锚会被拖行，致使节点移位丢失。水声通讯系统安装在一个长1m、外径30cm的密封圆柱形钢桶内，设备和钢桶总质量为100kg。钢桶上接第4节钢管，下接电焊锚链。钢桶竖直时，水声通讯设备的工作效果最佳。若钢桶倾斜，则影响设备的工作效果。钢桶的倾斜角度（钢桶与竖直线的夹角）超过5度时，设备的工作效果较差。为了控制钢桶的倾斜角度，钢桶与电焊锚链链接处可悬挂重物球。 图1 传输节点示意图（仅为结构模块示意图，未考虑尺寸比例）系泊系统的设计问题就是确定锚链的型号、长度和重物球的质量，使得浮标的吃水深度和游动区域及钢桶的倾斜角度尽可能小。 问题1某型传输节点选用II型电焊锚链22.05m，选用的重物球的质量为1200kg。现将该型传输节点布放在水深18m、海床平坦、海水密度为1.025×103kg/m3的海域。若海水静止，分别计算海面风速为12m/s和24m/s时钢桶和各节钢管的倾斜角度、锚链形状、浮标的吃水深度和游动区域。 问题2在问题1的假设下，计算海面风速为36m/s时钢桶和各节钢管的倾斜角度、锚链形状和浮标的游动区域。请调节重物球的质量，使得钢桶的倾斜角度不超过5度，锚链在锚点与海床的夹角不超过16度。 问题3 由于潮汐等因素的影响，布放海域的实测水深介于16m~20m之间。布放点的海水速度最大可达到1.5m/s、风速最大可达到36m/s。请给出考虑风力、水流力和水深情况下的系泊系统设计，分析不同情况下钢桶、钢管的倾斜角度、锚链形状、浮标的吃水深度和游动区域。
2013高教社杯全国大学生数学建模竞赛 承诺书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）：重庆邮电大学 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 2013 年 9 月 13 日赛区评阅编号（由赛区组委会评阅前进行编号）：
2013高教社杯全国大学生数学建模竞赛 编号专用页 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）：
碎纸片的拼接复原 摘要 本文研究的是碎纸片的拼接复原问题。由于人工做残片复原虽然准确度高，但有着效率低的缺点，仅由计算机处理复原，会由于各类条件的限制造成误差与错误，所以为了解决题目中给定的碎纸片复原问题，我们采用人机结合的方法建立碎纸片的计算机复原模型解决残片复原问题，并把计算机通过算法复原的结果优劣情况作为评价复原模型好坏的标准，通过人工后期的处理得到最佳结果。 面对题目中给出的BMP格式的黑白文字图片，我们使用matlab软件的图像处理功能把图像转化为矩阵形式，矩阵中的元素表示图中该位置像素的灰度值，再对元素进行二值化处理得到新的矩阵。题目每一个附件中的碎纸片均为来自同一页的文件，所以不需考虑残片中含有未知纸张的残片以及残片中不会含有公共部分。鉴于残片形状分为“长条形”与“小长方形”，残片内容分为中文、英文，纸张的打印类型分为“单面型”、“双面型”，所以我们根据残片的类型对矩阵做不同处理。 针对问题一中给出的“长条形”碎纸片：对图片转化后的矩阵进行边缘检测，发现每一张图片的两短边在一定范围内全是白色，而仅有2张图片的长边在一定范围内全是白色，说明我们需要对长边进行拼接，一边包含全白的长边是原文件纸张的两端。由于考虑到模型应用的推广，我们在此问中的模型包含了图片倒置的情况（仅在问题一中考虑倒置情况，鉴于问题二、三中数据量的增多，二三问不再考虑倒置情况），对图片的长边及矩阵中的第一列和最后一列与其他矩阵的第一列和最后一列进行边缘匹配，根据边缘匹配度来确定图片复原，最后若发现拼接效果有偏差，在进行人工操作。 针对问题二中的“小长方形”碎纸片：由于数据量变多，盲目使用问题一中的方法不能保证准确度，所以这里要进一步约束使当前图片与少量图片进行匹配。观察两种文字的特点，我们可以发现中英文在位置上均有一定的特性，我们利用这种特性将有相同位置特性的碎纸片归类为一组，在问题一方法的基础上做少许修改后代入有相同位置特性的一组碎纸片中，根据边缘匹配度将他们连接、检查并做人工处理可得拼接后的横行纸片，再将横行纸片的长边用同样的方法做边缘匹配可将行与行之间拼接起来，再做人工调整得到最优结果。通过模型的建立求解过程可以发现中英文在本问题的求解方法中有着一定的不同，英文需要更多地人工判断处理。 针对问题三考虑到双面问题以及问题二中英文碎纸片的情况，我们把碎纸片两面匹配度之和作为判断碎纸片是否连接的评价标准，在问题一方法的基础上，在计算机每一步的匹配结果加以人工选择与判断，这样再次处理得到的结果，可以得到同问题二中一样的横行碎纸片，在根据新的横行碎纸片的两面边缘匹配度之和进行同样的操作处理可以将原纸张拼接复原。 关键词：残片复原 matlab图像处理二值化边缘匹配度倒置情况位置特性
2013年全国研究生数学建模竞赛B 题（华为公司合作命题） 功率放大器非线性特性及预失真建模 一、背景介绍 1.问题引入 信号的功率放大是电子通信系统的关键功能之一，其实现模块称为功率放大器（PA ，Power Amplifier ），简称功放。功放的输出信号相对于输入信号可能产生非线性变形，这将带来无益的干扰信号，影响信信息的正确传递和接收，此现象称为非线性失真。传统电路设计上，可通过降低输出功率的方式减轻非线性失真效应。 功放非线性属于有源电子器件的固有特性，研究其机理并采取措施改善，具有重要意义。目前已提出了各种技术来克服改善功放的非线性失真，其中预失真技术是被研究和应用较多的一项新技术，其最新的研究成果已经被用于实际的产品（如无线通信系统等），但在新算法、实现复杂度、计算速度、效果精度等方面仍有相当的研究价值。 本题从数学建模的角度进行探索。若记输入信号)(t x ，输出信号为)(t z ，t 为时间变量，则功放非线性在数学上可表示为))(()(t x G t z =，其中G 为非 线性函数。预失真的基本原理是：在功放前设置一个预失真处理模块，这两个模块的合成总效果使整体输入-输出特性线性化，输出功率得到充分利用。原理框图如 图1所示。 图1 预失真技术的原理框图示意 其中)(t x 和)(t z 的含义如前所述，)(t y 为预失真器的输出。设功放输入-输出传输特性为()G ，预失真器特性为()F ，那么预失真处理原理可表示为 ))(())(()))((())(()(t x L t x F G t x F G t y G t z ==== （1）L F G = 表示为()G 和()F 的复合函数等于()L 。线性化则要求 )())(()(t x g t x L t z ⋅== （2） 式中常数g 是功放的理想“幅度放大倍数”（g>1）。因此，若功放特性()G 已知，则预失真技术的核心是寻找预失真器的特性()F ，使得它们复合后能满足 )())(())()((t x g t x L t x F G ⋅== （3） 如果测得功放的输入和输出信号值，就能拟合功放的特性函数()G ，然后利用（3）式，可以求得()F 。 2.功放的非线性模型 由于各类功放的固有特性不同，特性函数()G 差异较大，即使同一功放，由于输入信号类型、环
2013高教社杯全国大学生数学建模竞赛B题评阅要点[说明]本要点仅供参考，各赛区评阅组应根据对题目的理解及学生的解答，自主地进行评阅。 本题要求对数据提取合适的特征、建立合理有效的碎纸片拼接复原模型。 可以考虑的特征有邻边灰度向量的匹配、按行或按列对灰度求和、行距等。 关于算法模型，必须有具体的算法过程（如流程图、算法描述、伪代码等）及设计原理。 虽然正确的复原结果是唯一的，但不能仅从学生提供的复原效果来评定学生解答的好坏，而应根据所建的数学模型、求解方法和计算结果（如复原率）三方面的内容做出评判。另一方面，评判中还需要考虑人工干预的多少和干预时间节点的合理性。 问题1. 仅有纵切文本的复原问题 由于“仅有纵切”，碎纸片较大，所以信息特征较明显。一种比较直观的建模方法是：按照某种特征定义两条碎片间的（非对称）距离，采用最优Hamilton路或最优Hamilton圈（即TSP）的思想建立优化模型。关于TSP的求解方法有很多，学生在求解过程中需要注意到非对称距离矩阵或者是有向图等特点。 还可能有种种优化模型与算法，只要模型合理，复原效果好，都应当认可。本问题相对简单，复原过程可以不需要人工干预，复原率可以接近或达到100%。 问题2. 有横、纵切文本的复原问题 一种较直观的建模方法是：首先利用文本文件的行信息特征，建立同一行碎片的聚类模型。在得到行聚类结果后，再利用类似于问题1中的方法完成每行碎片的排序工作。最后对排序后的行，再作纵向排序。 本问题的解法也是多种多样的，应视模型和方法的合理性、创新性及有效性进行评分。例如，考虑四邻近距离图，碎片逐步增长，也是一种较为自然的想法。 问题3. 正反两面文本的复原问题 这个问题是问题2的继续，基本解决方法与问题2方法相同。但不同的是：这里需要充分利用双面文本的特征信息。该特征信息利用得好，可以提升复原率。 在阅卷过程中，可以考虑学生对问题的扩展。例如，在模型的检验中，如果学生能够自行构造碎片，用以检验与评价本队提出的拼接复原模型的复原效果，可考虑适当加分。 阅卷时应有程序，程序的运行结果应和论文给出的结果一致。
交巡警服务平台的设置与调度优化分析 摘要 本文以实现警察的刑事执法、治安管理、交通管理、服务群众四大职能为宗旨，利用有限的警务资源，根据城市的实际情况与需求合理地设置了交巡警服务平台、分配各平台的管辖范围及调度警务资源。并分别对题目的各问，作了合理的解答。 问题一： （1）、根据题目所给数据，确定各节点之间的相邻关系和距离，利用Floyd算法及matlab编程求出两点之间的最短距离，使其尽量满足能在3分钟内有交巡警平台警力到达案发结点的原则，节点去选择平台，把节点分配给离节点距离最近的平台管辖，据此，我们得到了平台的管辖区域划分。 （2）、我们对进出该区的13条交通要道实现快速全封锁的问题，我们认定在所有调度方案中，某种方案中耗时最长的的围堵时间最短即最佳方案，利用0-1变量确定平台的去向，并利用线性规划知识来求解指派问题，求得了最优的调度方案。 （3）、在确定增添平台的个数和具体位置的问题中，我们将尽量保证每个节点都有一个平台可以在三分钟内到达作为主要原则来求解。我们先找出到达每个平台的时间都超过三分钟的节点，并尝试在这些节点中选取若干个作为新的平台，求出合理的添加方案。 问题二： （1）、按照设置交巡警服务平台的原则和任务，分析现有的服务平台的设置是否合理，我们以各区覆盖率作为服务平台分布合不合理的评价标准，得到C、D、E、F区域平台设置不合理。并尝试一些新的设置方案使得设置更为合理，最后以覆盖率最低的E区为例，使用一种修改方案得到一个比原方案更合理的交巡警服务平台的设置方案。 （2）、追捕问题要求在最快的时间内抓到围堵罪犯，在罪犯和警察的行动速度一致的前提假设下，我们先设定一个具体较小的时间，编写程序检验在这个时间内是否可以成功抓捕罪犯，不行则以微小时间间隔增加时间，当第一次成功围堵时，这个时间即为最佳围堵方案。 关健字： MATLAB软件，0-1规划，最短路，Floyd算法，指派问题 一、问题重述 “有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。 试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题： （1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。 对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。 根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。 （2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。 如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。 二、模型假设及符号说明 2.1、模型假设 1、假设各服务台职能，警力配备足以处理辖区内正常事故。 2、假设不考虑人口密度对警察办案的具体影响。
2016年高教社杯全国大学生数学建模竞 赛题目 令狐文艳 （请先阅读“全国大学生数学建模竞赛论文格式规范”） A题系泊系统的设计 近浅海观测网的传输节点由浮标系统、系泊系统和水声通讯系统组成（如图1所示）。某型传输节点的浮标系统可简化为底面直径2m、高2m的圆柱体，浮标的质量为1000kg。系泊系统由钢管、钢桶、重物球、电焊锚链和特制的抗拖移锚组成。锚的质量为600kg，锚链选用无档普通链环，近浅海观测网的常用型号及其参数在附表中列出。钢管共4节，每节长度1m，直径为50mm，每节钢管的质量为10kg。要求锚链末端与锚的链接处的切线方向与海床的夹角不超过16度，否则锚会被拖行，致使节点移位丢失。水声通讯系统安装在一个长1m、外径30cm的密封圆柱形钢桶内，设备和钢桶总质量为100kg。钢桶上接第4节钢管，下接电焊锚链。钢桶竖直时，水声通讯设备的工作效果最佳。若钢桶倾斜，则影响设备的工作效果。钢桶的倾斜角度（钢桶与竖直线的夹角）超过5度时，设备的工作效果较差。为了控制钢桶的倾斜角度，钢桶与电焊锚链链接处可悬挂重物球。 图1 传输节点示意图（仅为结构模块示意图，未考虑尺寸比 例）
系泊系统的设计问题就是确定锚链的型号、长度和重物球的质量，使得浮标的吃水深度和游动区域及钢桶的倾斜角度尽可能小。 问题1某型传输节点选用II型电焊锚链22.05m，选用的重物球的质量为1200kg。现将该型传输节点布放在水深18m、海床平坦、海水密度为 1.025×103kg/m3的海域。若海水静止，分别计算海面风速为12m/s和24m/s时钢桶和各节钢管的倾斜角度、锚链形状、浮标的吃水深度和游动区域。 问题2在问题1的假设下，计算海面风速为36m/s时钢桶和各节钢管的倾斜角度、锚链形状和浮标的游动区域。请调节重物球的质量，使得钢桶的倾斜角度不超过5度，锚链在锚点与海床的夹角不超过16度。 问题 3 由于潮汐等因素的影响，布放海域的实测水深介于16m~20m之间。布放点的海水速度最大可达到1.5m/s、风速最大可达到36m/s。请给出考虑风力、水流力和水深情况下的系泊系统设计，分析不同情况下钢桶、钢管的倾斜角度、锚链形状、浮标的吃水深度和游动区域。 说明近海风荷载可通过近似公式F=0.625×Sv2(N)计算，其中S为物体在风向法平面的投影面积(m2)，v为风速(m/s）。近海水流力可通过近似公式F=374×Sv2(N)计算，其中S为物体在水流速度法平面的投影面积(m2)，v为水流速度(m/s）。
基于最小二乘法的碎纸片拼接复原数学模型 摘要 首先对图片进行灰度化处理,然后转化为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。 针对问题二，首先根据每张纸片内容的不同特性，对图片进行聚类分析，将209张图片分为11类；对于每一类图片，按照问题一的模型与算法，即列偏差函数最小则进行左右拼接,对于没有拼接到组合里的碎纸片进行人工干预，我们得到了11组碎纸片拼接而成的图片；对于拼接好的11张图片，按照问题一的模型与算法，即行偏差函数最小则进行上下拼接,对于没有拼接到组合里的碎纸片进行人工干预。我们最终经计算，附件3的拼接结果见表9，附件4的拼接结果见表10。 针对问题三，由于图片区分正反两面，在问题二的基础上，增加图片从下到上的裁截距信息，然后进行两次聚类，从而将所有图片进行分类，利用计算机自动拼接与人工干预相结合，对所有图片进行拼接复原。经计算，附件5的拼接结果见表14和表15 该模型的优点是将图片分为具体的几类，大大的减少了工作量，缺点是针对英文文章的误差比较大。 关键字：灰度处理，图像二值化，最小二乘法，聚类分析，碎纸片拼接
一、问题重述 碎纸片的拼接复原技术在司法鉴定、历史文献修复与研究、军事情报获取以及故障分析等领域都有着广泛的应用。近年来，随着德国“斯塔西”文件的恢复工程的公布，碎纸文件复原技术的研究引起了人们的广泛关注。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。对于一页印刷文档，针对不同的破碎方法，讨论下列三个问题： （1）将给定的一页印刷文字文件纵切，建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。 （2）对于碎纸机既纵切又横切的情形，设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。 （3）对于双面打印文档，研究如何进行碎纸片的拼接复原问题。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。要求尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。 二、模型的基本假设 （1）待拼接的碎纸片来自同一页印刷文字文件。 （2）待拼接复原的碎纸片是规整的矩形。 （3）模型中的碎纸片长度、宽度和面积都相等。 （4）附件中照片都是同标准拍摄。 三、符号说明
基于打车软件的出租车供求匹配度模型研究与分析 摘要 目前城市“出行难”、“打车难”的社会难题导致越来越多的线上打车软件出现在市场上。“打车难”已成为社会热点。以此为背景，本文将要解决分析的三个问题应运而生。 本文运用主成分分析、定性分析等分析方法以及部分经济学理论成功解决了这三个问 题，得到了不同时空下衡量出租车资源供求匹配程度的指标与模型以及一个合适的补贴 方案政策，并对现有的各公司出租车补贴政策进行了分析。 针对问题一，根据各大城市的宏观出租车数据，绘制柱形图进行重点数据的对比分 析，首先确定适合进行分析研究的城市。之后，根据该市不同地区、时间段的不同特点 选择多个数据样本区，以数据样本区作为研究对象，进行多种数据（包括出租车分布、 出租车需求量等）的采集整理。接着，通过主成分分析法确定模型的目标函数、约束条 件等。最后运用spss软件工具对数据进行计算，求出匹配程度函数F 与指标的关系式， 并对结果进行分析。 针对问题二，在各公司出租车补贴政策部分已知的情况下，综合考虑出租车司机以 及顾客两个方面的利益，分别就理想情况与实际情况进行全方位的分析。在问题一的模 型与数据结果基础上，首先分别从给司机和乘客补贴两个角度定性分析了补贴的效果。 重点就给司机进行补贴的方式进行讨论，定量分析了目前补贴方案的效果，得出了如果 统一给每次成功的打车给予相同的补贴无法改善打车难易程度的结论，并对第三问模型 的设计提供了启示，即需要对具有不同打车难易程度和需求量的区域采取分级的补贴政 策。 针对问题三，在问题二的基础上我们设计了一种根据不同区域打车难易程度和需求
量来确定补贴等级的方法。设计了相应的量化指标，以极大化各区域打车难易程度降低 的幅度之和作为目标，建立该问题的规划模型。目的是通过优化求解该模型，使得通过 求得的优化补贴方案，能够优化调度出租车资源，使得打车难区域得到缓解。通过设计 启发式原则和计算机模拟的方法进行求解，并以具体案例分析得到，本文方法相对统一 的补贴方案而言的确可以一定程度缓解打车难的程度。 关键词：主成分分析法，供求匹配度，最优化模型，出租车流动平衡 1
2013全国大学生数学建模B题源程序 第一篇：2013全国大学生数学建模B题源程序 运行前,请将附件所在的目录加入到MATLAB的路径中！！ 都是自己编的，还望大神指教！ 附件1和2的源程序： Clear all I=cell(1,19);%存放二值图片 A=cell(1,19);%存放原始图片 for j=1:19 if j-1<10 imageName=strcat('00',num2str(j-1),'.bmp'); else imageName=strcat('01',num2str(j-11),'.bmp'); end I{j} = imread(imageName); end A=I; %读取图片 for j=1:19 for k=1:1980 for h=1:72 if I{j}(k,h)~=255 I{j}(k,h)=1; else I{j}(k,h)=0; end end end end
%将图片二值化 b=zeros(1,19); for i=1:19 sum=0; for j=1:1980 sum=sum+I{i}(j); end b(i)=sum; end for i=1:19 if b(i)==0 q=i; end %找出原图最左边的碎纸片的编号,并存放在变量q中 for i=0:18 I{i+1}(1)=i; A{i+1}(1)=i; end %对每张图片做标记(即在二值化后的矩阵和原始图片的矩阵的第一个元素处做标记)t=I{q}; I{q}=I{1}; I{1}=t; %交换二值化后的第q张和第一张图片 t=A{q}; A{q}=A{1}; A{1}=t; %交换原始图片的第q张和第一张 for k=1:18 d=zeros(18,1); for i=k+1:19
碎纸片的拼接复原 摘要 本文主要解决碎纸片拼接复原问题。利用附件所给碎纸片的数据，运用蚁群优化算法、Adaboost算法、Harris角点检测算法，利用Matlab软件编程求解，得到碎纸片拼接复原结果。 针对问题一，依据文字所在行的几何特征，先将文字进行二值化处理，得到文字的数据信息。运用蚁群优化全局匹配方案完成整体匹配，利用回溯的Best-First搜索算法，得到最佳候选匹配对，由于碎纸片形状相似，Best-First搜索算法会大大降低拼接效率，最后建立蚁群优化算法模型对复原结果进行优化，得到中、英文拼接复原图（见附录一）及顺序表（见表2、表3）。 针对问题二，先对附件3、附件4中的碎纸片进行像素特征分析，将每一个矩形像素特征区域的白色区域设为0、黑色区域设为1，利用Adaboost算法对碎纸片进行分类处理，再依据矩形像素特征进行匹配，得到拼接复原中文、英文图片。对每次匹配循环进行人工干预得出碎纸片的拼接复原顺序图（见附录二）及顺序表（见表4、表6）。 针对问题三，在对比经典角点检测算法的基础上，利用附件5中图片的信息，运用Harris角点检测的多层匹配图像拼接算法，得到图片的角点信息。采用标准互相关联法和互信息法对Harris角点进行粗匹配，之后根据特征点周围的边缘信息过滤为匹配点，再用RANSAC进行精确匹配，得到一幅完整的拼接复原图像。最后，运用神经网络边缘检测算法进行优化，快速的获取准确的碎纸片的拼接复原顺序图（见附录三）及顺序表（见表8、表9）。 关键词：蚁群优化算法 Adaboost算法 Harris角点检测神经网络
1 问题重述 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题： （1）对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。 （2）对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原并针对附件过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。 （3）上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。 2 问题分析 2.1问题一的分析 若对中、英文各一页文件的纵切碎纸片拼接复原，需考虑复原的碎纸片之间的边界衔接、字迹线条、图片属性、文字的行高、文字行间距及文字断线等信息。利用碎纸片文字所在行的几何特征，先对文字进行二值化处理。借助蚁群优化算法的全局匹配方案，完成整体匹配。再运用回溯Best-First搜索算法，得到最佳候选匹配对。考虑到碎片形状特征相似度高等原因，不合理的候选匹配对可能大量存在，导致拼接效率大大降低。再建立蚁群优化算法进行优化，利用Matlab编程得到碎纸片拼接复原结果。 2.2问题二的分析 若将中、英文各一页文件的纵切碎纸片拼接复原，利用Adaboost算法，先将附件3、附件4中给出的碎纸片分别进行编号，再将所有待匹配碎纸片进行初始化，然后进行错误率分析，根据误差分析结果来调整权重，得到分类结果。对所有碎片分类结果进行矩形像素特征分析，最后由矩形像素特征匹配出碎纸片的原图，对于匹配的循环进行人工干预得出碎纸片的排列顺序表。 2.3问题三的分析 若对双面打印文件的碎纸片拼接复原，需考虑正反面文字的对应情况，先用人工干预的方式对文件的部分碎纸片拼接复原。图像拼接复原需考虑图像特征，本文基于碎纸片的角点特征，利用附件5给出的一页英文印刷文字双面打印文件的碎纸片数据，在对
高教社杯全国高校生数学建模竞赛题目（四套ABCD）当我第一遍读一本好书的时候，我仿佛觉得找到了一个伴侣; 当我再一次读这本书的时候，仿佛又和老伴侣重逢。我们要把读书当作一种乐趣，并自觉把读书和学习结合起来，做到博览、精思、熟读，更好地指导自己的学习，让自己不断成长。让我们一起到学习啦一起学习吧! 2021年高教社杯全国高校生数学建模竞赛题目 A题 CT系统参数标定及成像 CT(Computed Tomography)可以在不破坏样品的状况下，利用样品对射线能量的吸取特性对生物组织和工程材料的样品进行断层成像，由此猎取样品内部的结构信息。一种典型的二维CT系统如图1所示，平行入射的X射线垂直于探测器平面，每个探测器单元看成一个接收点，且等距排列。X射线的放射器和探测器相对位置固定不变，整个放射-接收系统绕某固定的旋转中心逆时针旋转180次。对每一个X射线方向，在具有512个等距单元的探测器上测量经位置固定不动的二 维待检测介质吸取衰减后的射线能量，并经过增益等处理后得到180 组接收信息。 CT系统安装时往往存在误差，从而影响成像质量，因此需要对安装好的CT系统进行参数标定，即借助于已知结构的样品(称为模板)标定CT系统的参数，并据此对未知结构的样品进行成像。 请建立相应的数学模型和算法，解决以下问题： (1) 在正方形托盘上放置两个均匀固体介质组成的标定模板，模板的几何信息如图2所示，相应的数据文件见附件1，其中每一点 的数值反映了该点的吸取强度，这里称为“吸取率”。对应于该模板 的接收信息见附件2。请依据这一模板及其接收信息，确定CT系统旋转中心在正方形托盘中的位置、探测器单元之间的距离以及该CT系统使用的X射线的180个方向。 (2) 附件3是利用上述CT系统得到的某未知介质的接收信息。
2003高教社杯全国大学生数学建模竞赛B 题参考答案 注意：以下答案是命题人给出的，仅供参考。各评阅组应根据对题目的理解及学生的解答，自主地进行评阅。 问题分析： 本题目与典型的运输问题明显有以下不同： 1． 运输矿石与岩石两种物资； 2． 产量大于销量的不平衡运输； 3． 在品位约束下矿石要搭配运输； 4． 产地、销地均有单位时间的流量限制； 5． 运输车辆每次都是满载，154吨/车次； 6． 铲位数多于铲车数意味着最优的选择不多于7个产地； 7． 最后求出各条路线上的派出车辆数及安排。 运输问题对应着线性规划，以上第1、2、3、4条可通过变量设计、调整约束条件实现； 第5条使其变为整数线性规划；第6条用线性模型实现的一种办法，是从1207 10 C 个整数规划中取最优的即得到最佳物流；对第7条由最佳物流算出各条路线上的最少派出车辆数（整数），再给出具体安排即完成全部计算。 对于这个实际问题，要求快速算法，计算含50个变量的整数规划比较困难。另外，这是一个二层规划，第二层是组合优化，如果求最优解计算量较大，现成的各种算法都无能为力。于是问题变为找一个寻求近优解的近似解法，例如可用启发式方法求解。 调用120次整数规划可用三种方法避免：（1）先不考虑电铲数量约束运行整数线性规划，再对解中运量最少的几个铲位进行筛选；（2）在整数线性规划的铲车约束中调用sign 函数来实现；（3）增加10个0－1变量来标志各个铲位是否有产量。 这是一个多目标规划，第一问的目标有两层：第一层是总运量（吨公里）最小，第二层是出动卡车数最少，从而实现运输成本最小。第二问的目标有：岩石产量最大；矿石产量最大；运量最小，三者的重要性应按此序。 合理的假设主要有： 1. 卡车在一个班次中不应发生等待或熄火后再启动的情况； 2. 在铲位或卸点处因两条路线（及以上）造成的冲突时，只要平均时间能完成任务即 可，不进行排时讨论； 3. 空载与重载的速度都是28km/h ，耗油相差却很大，因此总运量只考虑重载运量； 4. 卡车可提前退出系统。 符号：x ij ~ 从i 号铲位到j 号卸点的石料运量 单位 吨； c ij ~ 从i 号铲位到j 号卸点的距离 公里； T ij ~ 从i 号铲位到j 号卸点路线上运行一个周期平均所需时间 分； A ij ~ 从i 号铲位到j 号卸点最多能同时运行的卡车数 辆； B ij ~ 从i 号铲位到j 号卸点路线上一辆车最多可以运行的次数 次； p i ~ i 号铲位的矿石铁含量。 % p =(30,28,29,32,31,33,32,31,33,31) q j ~ j 号卸点任务需求 吨 q =(1.2,1.3,1.3,1.9,1.3)*10000 ck i ~ i 号铲位的铁矿石储量 万吨 cy i ~ i 号铲位的岩石储量 万吨
2012高教社杯全国大学生数学建模竞赛 承诺书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括 我
2012高教社杯全国大学生数学建模竞赛 编号专用页 赛区评阅编号（由赛区组委会评阅前进行编号）：
基于背包算法的太阳能小屋的研究与设计 摘要 本文针对太阳能小屋上光伏电池铺设问题,运用贪婪算法,通过局部最优来逼近整体最优.针对三个问题,分别得出了光伏电池的铺设方案和对应的逆变器选择,架空后光伏电池与水平面夹角的最优解以及小屋对太阳辐射的最大化利用的设计方案. 对于问题一,首先对光伏电池的性价比K 进行了纵向比较,选出了性价比最高的三种光伏电池312,,A B B .为了使剩余面积达到最少,采用整数背包算法,从而 在设计太阳能小屋时,需在建筑物外表面（屋顶及外墙）铺设光伏电池,光伏电池组件所产生的直流电需要经过逆变器转换成220V 交流电才能供家庭使用,并将剩余电量输入电网.不同种类的光伏电池每峰瓦的价格差别很大,且每峰瓦的实际发电效率或发电量还受诸多因素的影响,如太阳辐射强度、光线入射角、环境、建筑物所处的地理纬度、地区的气候与气象条件、安装部位及方式（贴附或架空）等.因此,在太阳能小屋的设计中,研究光伏电池在小屋外表面的优化铺设是
很重要的问题. 附件中提供了相关信息.请参考附件提供的数据,对下列三个问题,分别给出小屋外表面光伏电池的铺设方案,使小屋的全年太阳能光伏发电总量尽可能大,而单位发电量的费用尽可能小,并计算出小屋光伏电池35年寿命期内的发电总量、经济效益（当前民用电价按0.5元/kWh 计算）及投资的回收年限. 在求解每个问题时,都要求配有图示,给出小屋各外表面电池组件铺设分组阵列图形及组件连接方式（串、并联）示意图,也要给出电池组件分组阵列容量及 本题要求我们,根据题目所提供的大同典型气象年气象数据,选择铺设电池的方案,可见光伏电池的发电量或发电效率只考虑受辐射影响即可,其余如坏境、地区气候等受制因素均可不必考虑. （1）对于问题一,有三个子问题需要解决： 第一是要选定光伏电池组件的几种排列方式,利用多重最优化思想,首先要对每种光伏电池的性价比K 进行纵向比较,选出性价比最大的前三种光伏电池,依次是：312,,A B B .用这三种光伏电池对各个平面进行铺设,同时对小部分的空余面积用面积较小的薄膜电池C 进行插空;然后采用整数背包模型,利用Matlab,确定各平面每种光伏电池的最大范围个数;最后对每个平面光伏电池数进行优化,结
承诺书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员(打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人(打印并签名)： 日期：年月日
编号专用页 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）：
太阳能小屋的最优化模型 摘要 本文中我们运用了一种“递进式铺设”方案。将问题进行拆解，把问题转化为五个独立的步骤来解决，在太阳能电池组件铺设过程中，优先选择单位面积经济效益最高的光伏电池组件来进行铺设，进行两次铺设后得到一个较为优化的解。在此方案的基础上，我们对太阳能小屋铺设问题进行了深入研究。 在问题一中，我们通过题目所给的数据对东南西北立面效益最大化的铺设方案进行计算，通过所得结果是否可以盈利来决定是否进行铺设。先利用Excel 软件对附件3所给数据根据各光伏电池组件的阈值进行处理，从而得到每种电池一年中的经济效益。在每个面的铺设方案计算中，均是通过先行铺设单位效益最大的光伏电池组件，对无法铺设到的部分选择单位效益次之的小型光伏电池组件进行铺设，直到无法再进行铺设为止。在由以上步骤进行了多重最优化后，通过光伏电池组件铺设情况及逆变器的电流电压要求选择逆变器的种类和数量。 对于问题二，我们查得大同光伏电池架空安装的最佳倾角为33度，计算出电池板在架空条件下最大情况下的的一边长与正常情况下的比例，然后转化到问题一中的方法进行铺设，进而计算出问题二中铺设光伏电池组件的经济效益及总发电量。 而在问题三中，要获得最多的太阳辐射量就要使在屋顶铺设的光伏电池组件的有效面积最大，因此就要获得最大的屋顶面积及在这种情况下的屋顶形状，于是我们列出线性方程，通过附件7得到限制条件，并通过Lingo求得最优解。最后参考附件七，画出小屋的外形图。 关键词：太阳能小屋递进式铺设单位效益最大化