2013年数学建模(B题)碎纸片的拼接复原模型
承诺书
我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛
参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网
站下载）。
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、
网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果
或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在
正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如
有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。
我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开
展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）：
所属学校（请填写完整的全名）：
参赛队员 (打印并签名) ：1.
2.
3.
指导教师或指导教师组负责人 (打印并签名)：
（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内
容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）
日期： 2013 年 9 月 10 日赛区评阅编号（由赛区组委会评阅前进行编号）：
编号专用页
赛区评阅编号（由赛区组委会评阅前进行编号）：
全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：
碎纸片的拼接复原模型
摘 要： 本文针对碎纸片的拼接复原问题，提出了互相关匹配模型。首先对附
件图片数值化处理并建立矩阵；然后根据图像页边距特点定位最左边和最右边的碎片；按照每张碎片中的文字部分所在位置，提取同一行碎片，利用互相关函数
1
1
()()
()()
11)T T j
k j
k jk
jk f
t f t f
t f t ρρ--=
=
-≤≤∑∑
横向拼合。
在第一问中，附件一、二仅作横向相关性比较即可；在第二、三问中，需要提取同一行碎片横向拼接，并将横向拼合完整的碎片进行竖向拼合，经过人工干预得到结果。
最终结果见附录。
关键词：拼接复原；互相关；矩阵；数值化；人工干预
一、问题重述
在司法物证复原、历史文献修复以及军事情报获取等领域的破碎文件的拼接上，传统的拼接复原工作需由人工完成，准确率较高，但效率很低。尤其是当碎片数量巨大时，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。我们需要用算法分别设计出附件1至附件5的拼接方法及拼接结果。
二、模型假设
1. 忽略实际拼接中边缘的整齐性；
2. 不需要考虑实际拼接中破碎文件大小是否一致；
3. 忽略碎片边缘的损耗，认为拼接后是完整的图片；
4. 在模型的建立过程中重视算法与建模思想，淡化程序的编写；
5. 文字的行间距一定。
三、符号说明
jk ρ 互相关系数（11jk ρ-≤≤）
()j f t 相关像素数组1
()k f t 相关像素数组2 i P 图像像素值矩阵 i Q 处理后图像像素值矩阵 ,mn mn a b 矩阵元素
四、问题的分析
1. 已知条件的分析
第一，对碎片尺寸和数量的分析。
附件1和附件2的图片尺寸均为721980?，碎片数量均为19；附件3、附件4和附件5的图片尺寸均为72180?，碎片数量均为1119?。由于纵列有11个，像素值180，总值111801980?=，因此，所有拼接后的图像尺寸一致，均为1368?1980。
第二，对碎片边界的分析。
对于附件1、2，所有碎片上行和下行像素值为白。其中，一张碎片位于最左端，最左列像素值均为白；一张碎片位于最右端，最右列像素值均为白。
对于附件3、4、5，拼接后图像四边像素值为白，碎片也存在边像素值全为白的情况，因此需要分类讨论。
切割线为长度完全相等的直线，因此切割线两边应有很大的相似度，灰度值相似。
第三，对碎片正反性的分析。
附件5存在正反面情况，同一块用a 、b ，但根据题意分析，我们无法确定碎片的正反，即a 可能是正面，也可能是反面。因此拼合时，应当注意统一序号在同一平面出现的单一性，例如，000a 在设定正面出现以后，000b 一定在反面。
第四，对碎片像素白色行的分析 对于中文，同一行的所有碎片文字是横向对齐的，因此白色开始的位置是一样的。因此可以提取出同一行的碎片。
2. 拼接方法的分析
由于碎片是长方形，有四条边，因此边的拼接有优先顺序。由于长边特征较为明显，采样点多，因此优先横向拼接，然后纵向拼接。当电脑拼接无法完成时，采取人工干预。
五、模型的分析与求解
1. 方法的确立
根据对问题的分析，我们得知此问题需要计算离散序列之间的相关性，因此我们需要使用互相关系数计算和矩阵的计算。 2. 模型的建立 1. 1图像数字化
由于电脑中图像的大小是由像素数量表示，而每个像素点均由一个数值表示，因此利用matlab 读取灰度图像的像素值，第n 副图用矩阵表示为：
在第一问中，n=72，m=1980；
在第二问、第三问中，n=72，m=180。 1. 2数据预处理
由于互相关函数需要比较正负范围相等的数组，因此我们将n P 的每个数值减去
max 2a ，使mn a 在 [-max 2a ，max 2
a
]范围内，即 127.5127.5127.5127.5127.5127.5127.5127.5
127.5m n A ?---??
?
--- ?
=
?
?
---??
(111212122212)
a (0255)n n i m m mn a a a a a P a a a a ??
?
?=≤≤ ? ???…………………
1112121
22212127.5127.5127.5127.5127.5
127.5127.5127.5
127.5n n i i m m mn a a a a a a Q P A a a a ---??
?--- ?=-= ?
?
---?
?………………
…
1112121
22212
(127.5127.5)n n m m mn b b b b b b b b b b ?? ? ?=-≤≤ ?
?
?
?…………………
1. 3相关性的计算
由于碎片大小完全一致，切割线完全竖直且交界处长度完全相等，并且切割线无损，图像可以完全拼接，因此相邻两个图形交接处相似。由于图像已经数字化处理，因此可以由边界相应像素数值的相关性来确定两张图是否相邻。对于相关性的计算，我们使用互相关函数。互相关函数公式为：
1
1
()()
()()
11)T T j
k j
k jk jk f
t f t f
t f t ρρ--=
=
-≤≤∑∑
公式中，分子表示的是两组离散数值的相似程度，分母则起到归一化作用，相邻两边的数组分别为序列)()(t f t f k j 、。
当1jk ρ→时，两组数相似程度最大，即两张图片最有可能相邻； 当1jk ρ→-时，两组数相似程度最小，即两张图片不相邻。 根据这个公式，即可算出两个图边缘的相关度。 1. 4图像的拼接 1. 4. 1 第一问
附件一：
首先，根据图像页边距白边特点定位最左边为白色的碎片，
i P 的第一列列向量为11211255255(0255)255m a a a a -?? ?- ?≤≤ ? ?-??…，将i=1,2，……19分别带入计算，仅当i=15时，112112552550255m a a a -??
?- ?= ? ?-??
…，因此，最左边碎片为014。 然后，令72()j j f t b =1()k j f t b =，将014矩阵数据带入()j f t 中分别计算jk i ρ，当取
得取max ρ时，i-1即为相邻碎片。同理，即可拼接整幅图。结果见附录。
19801
119801219801()()1()()2()()19j k j k jk
j k i
i f t f t i f t f t i f t f t i ρ---?
?
=?
?==??=∑∑∑…? 同理可得附件二结果。
Matlab 附件一 拼接图
1. 4. 2 第二问
首先，确定最左边碎片。因为碎片存在非左边仍有白边的情况，例如附件4的图002.bmp ，如下图所示。（由于底色是白色与文档背景相同，进行了对比度降低处理。）
附件4-002.bmp
因此，需要提取多组行向量，根据是否均为0确定最左碎片，同理可确定最右碎片。左碎片满足条件如下：
111212122212255255255255255255=025*******r r m m mr a a a a a a a a a ---?????? ? ? ?--- ? ? ?=== ? ? ? ? ? ?---??????
………… 式中，r 的大小由实际图像左边缘白边像素数量决定。在附件3中，r 取15时，满足条件的碎片数量为11。
利用同一行碎片文字垂直位置相同的特点，根据最左边碎片的文字的垂直位置特点，确定图像所在行。
同第二问，分别计算同一行序列的互相关系数，取最大值拼合。然而，这样只能拼接出11个横行碎片，用互相关函数拼接部分碎片后，最后用人工干预完成白边部分的拼合。结果如附件所示。
1. 4. 3 第三问
由于是两面混合，首先忽视两面性，认为所有碎片是在同一平面上，进行整体拼接，则图像应该为2219?个碎片，在进行最左边和最右边计算时会出现22个碎片。
然后根据第二问方法，进行横向碎片的拼接，纵向碎片的拼接。最后进行人工干预。由于图像是由两面组成的，因此两张图片的对称点（第n 列和第20-n 列对称）数字相同字母不同，例如199b 在一个面的第4行、第19列，那么199a 就在另一面的第4行、第1列。因此正反两面的对应行所在位置一致，可以人工将图拼合完整。效果如如下，结果见附件。
Matlab 附件五 拼接图
六、模型评价
模型优点：
1、模型具有坚实可靠的数学基础，经过实践数据分析证明，互相关函数在本题中应用的可行性，简化了对模型问题的分析；
2、模型能较好的优化人工干预次数。
模型缺点：
1、附件3、4、5在拼接时没有完全脱离人工干预；
2、在实际推算中，模型会产生较大的运算量；
3、模型在现实生活中的应用有待优化，因为现实中很少有完全规则的文字碎片。
参考文献：
[1]屈婉玲等编,离散数学,北京：高等教育出版社 ,2008
[2]同济大学数学系编，工程数学——线性代数同济第五版,北京：高等教育出版社，2007
[3](美)奥本海姆等著刘树棠译,信号与系统（第二版）,北京：电子工业出版社 2013
[4]张志涌等编著,精通MATLAB R2011a,北京：北京航空航天大学出版社 ,2011
[5](美)穆尔著，高会生，刘童娜，李聪聪译,MATLAB实用教程（第二版）,北京：电子工业出版社 ,2010
[6](美)莫勒（Moler,C.B）著喻文健译,MATLAB数值计算,北京：机械工业出版社, 2006
[7](美)冈萨雷斯（Gonzalez.R.C.）等著阮秋琦等译,数字图像处理（MATLAB版）,北京：电子工业出版社 ,2005
[8](美)冈萨雷斯等著阮秋琦译,数字图像处理的MATLAB实现（第2版）,北京：清华大学出版社 ,2013
[9](美)罗森著袁崇义等译,离散数学及其应用,北京：机械工业出版社 ,2011
附录
附录一模型结果
附件一效果图附件二效果图
附件4结果：
13
14
附录三效果图 附录四效果图
附录五效果图1 附录五效果图2
附录二部分源程序（由于源程序篇幅过长，打印不便，因此只附上部分程序）
使用软件:Matlab
I000=imread('000.bmp')
I001=imread('001.bmp')
I002=imread('002.bmp')
I003=imread('003.bmp')
I004=imread('004.bmp')
I005=imread('005.bmp')
I006=imread('006.bmp')
I007=imread('007.bmp')
I008=imread('008.bmp')
I009=imread('009.bmp')
I010=imread('010.bmp')
I011=imread('011.bmp')
I012=imread('012.bmp')
I013=imread('013.bmp')
I014=imread('014.bmp')
I015=imread('015.bmp')
I016=imread('016.bmp')
I017=imread('017.bmp')
I018=imread('018.bmp')
P=[I000,I001,I002,I003,I004,I005,I006,I007,I008,I009,I010,I011 ,I012,I013,I014,I015,I016,I017,I018]
% 最左计算函数
function F=borderright(x)
for j=1:1:19
y(j)=0
for i=1:1:1980
if(x(i,72*(j-1)+1)==255)
y(j)=y(j)+0
else
y(j)=y(j)+1
end
end
if(y(j)==0)
F=j
end
end
end
function d=split(x,y,m)
maxx=[0,0]
for j=1:1:19
z(j)=0
if((j~=(m(1)+1))&&(j~=(m(2)+1))&&(j~=(m(3)+1))&&(j~=(m(4)+1))& &(j~=(m(5)+1))&&(j~=(m(6)+1))&&(j~=(m(7)+1))&&(j~=(m(8)+1))&&( j~=(m(9)+1))&&(j~=(m(10)+1))&&(j~=(m(11)+1))&&(j~=(m(12)+1))&& (j~=(m(13)+1))&&(j~=(m(14)+1))&&(j~=(m(15)+1))&&(j~=(m(16)+1)) &&(j~=(m(17)+1))&&(j~=(m(18)+1))&&(j~=(m(19)+1)))
for i=1:1:1980
if((x(i,72*y)<255)&&(x(i,72*(j-1)+1))<255)
z(j)=z(j)+1
else
z(j)=z(j)+0
end
end
else
z(j)=0
end
if(z(j)>maxx(1))
maxx=[z(j),j]
end
end
d=maxx(2)
end
function two(x,a,b)
for i=1:1:a
for j=1:1:b
if(x(i,j)<255)
x(i,j)=0
end
end
end
f3=0
f4=0
f5=0
f3=double(f3)
f4=double(f4)
f5=double(f5)
p=0
bai=0
HENG=[19,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 ;
20,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 70,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 81,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 86,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 132,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 145,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 159,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 171,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 191,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1;
201,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1;]
for k=1:1:11
a=HENG(k,1)
for i=2:1:19
for b=1:1:208
f3=0
f4=0
f5=0
for c=1:1:180
f1=Q(c+a*180,72)
f2=Q(c+b*180,1)
f3=f3+Q(c+a*180,72)*Q(c+b*180,1)
f4=f4+f1*f1
f5=f5+f2*f2
end
r(b)=f3/sqrt(f4*f5)
if r(b)>p
p=r(b)
h=b
end
r(b)=0
end
p=0
HENG(k,i)=h
a=h
for c=1:1:180
bai=bai+Q(c+a*180,72)
end
if ((bai==22950)&&(i==19))
msgbox('àTà2')
end
if ((bai==22950)&&(i<19))
msgbox('1t1t￡?è?1¤?é?¤°é')
break
end
bai=0
end
end
f3=0
f4=0
f5=0
f3=double(f3)
f4=double(f4)
f5=double(f5)
p=0
bai=0
% 初始化数组
%
HENG=[49,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,14 1;
% 61,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,36; %
168,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,18;
% 38,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,74; % 71,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,60; %
14,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,176;
% 94,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,43; %
125,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,145;
% 29,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,59; % 7,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,196; %
89,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,123;]
for k=1:1:11
a=HENG(k,19)
for i=18:-1:1
for b=1:1:208
f3=0
f4=0
f5=0
r(b)=0
if b~=105
for c=1:1:180
f1=Q(c+a*180,1)
f2=Q(c+b*180,72)
f3=f3+Q(c+a*180,1)*Q(c+b*180,72) f4=f4+f1*f1
f5=f5+f2*f2
end
r(b)=f3/sqrt(f4*f5)
if r(b)>p
p=r(b)
h=b
end
end
end
p=0
HENG(k,i)=h
a=h
for c=1:1:180
bai=bai+Q(c+a*180,1)
end
if (bai>22000)&&(i>1)
msgbox('1t1t￡?è?1¤?é?¤°é')
break
end
bai=0
end
end
2013年数学建模碎纸片的拼接复原模型
承诺书 我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。 我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。） 日期： 2013 年 9 月 10 日赛区评阅编号（由赛区组委会评阅前进行编号）：
编号专用页 赛区评阅编号（由赛区组委会评阅前进行编号）： 全国评阅编号（由全国组委会评阅前进行编号）： 碎纸片的拼接复原模型 摘要：本文针对碎纸片的拼接复原问题，提出了互相关匹配模型。首先对附件图片数值化处理并建立矩阵；然后根据图像页边距特点定位最左边和最右边的碎片；按照每张碎片 中的文字部分所在位置，提取同一行碎片，利用互相关函数 横向拼合。 在第一问中，附件一、二仅作横向相关性比较即可；在第二、三问中，需要提取同一行碎片横向拼接，并将横向拼合完整的碎片进行竖向拼合，经过人工干预得到结 果。 最终结果见附录。 关键词：拼接复原；互相关；矩阵；数值化；人工干预
规则碎纸片的拼接复原
论 文 检 测 报 告 报告编号： 5d95e0aadf5149a5a9ef1ecb397c466d 送检文档： 规则碎纸片的拼接复原 论文作者： 陈芳芳 文档字数： 2981 检测时间： 2015-01-07 12:39:34 检测范围： 论文库，中文期刊库（涵盖中国期刊论文网络数据库、中文科技期刊数据库、中文重要学术期刊库、中国重要社科期刊库、中国重要文科期刊库、中国中文报刊报纸数据库等），Tonda论文库（涵盖中国学位论文数据库、中国优秀硕博论文数据库、部分高校特色论文库、重要外文期刊数据库如Emerald、HeinOnline、JSTOR等），资源共享库。 一、检测结果： 总相似比： 36.05% [即复写率与引用率之和] 检测指标： 自写率 63.95%复写率 36.05%引用率 0.0% 相 似 比： 互联网 36.05% 学术期刊 0.0% 学位论文 0.0% 资源共享 0.0% 其他指标： 表格 0 个 脚注 0 个 尾注 0 个
章节抄袭比 36.05% 规则碎纸片的拼接复原 二、相似文献汇总： 序号标题文献来源作者出处发表时间11213年碎纸片拼接复原数模论文互联网互联网 213年碎纸片拼接复原数模论文-豆丁网互联网互联网 32013年全国大学生数学建模竞赛国家一等奖论文B题碎纸片的拼接...互联网互联网 4【图】科密碎纸机 深圳碎纸机 黑金刚碎纸机 可碎光碟 - 罗湖办公...互联网互联网 5一种碎纸自动拼接中的形状匹配方法-《计算机仿真》2006年11期-...互联网互联网 6国家奖碎纸片的拼接还原_百度文库互联网互联网
7基于蚁群优化算法的碎纸拼接-豆丁网互联网互联网 8求2013数学建模题B题(2)的中文原题以及附件3不胜感激_百度知道互联网互联网 9沈阳建筑大学_徐俊杰.郭书恒.唐杰_百度文库互联网互联网 10碎纸机批发,厂家,图片,商贸城-马可波罗网互联网互联网 三、全文相似详情： （红色字体为相似片段、浅蓝色字体为引用片段、深蓝色字体为可能遗漏的但被系统识别到与参考文献列表对应的引用片段、黑色字体为自写片段） 碎纸机，是用来切碎销毁纸张的机器，为了达到废弃文件保密的目的，要把纸张分割成很多的细小纸片，碎纸机切割的纸粒工整利落，能达到保密的效果。随着数据时代发展，大量的政府机关、企事业单位都采用了碎纸机对废弃文件或失效的机密文件进行破碎处理。碎纸方式是指当纸张经过碎纸机处理后被碎纸刀切碎后的形状。市面上有些碎纸机可选择两种或两种以上的碎纸方式。不同的碎纸方式适用于不同的场合，如果是一般性的办公场合则选择段状、粒状、丝状，条状的就可以了。但如果是用到一些对保密要求比较高的场合就一定要用沫状的。随着现代技术的不断发展和市场的需求，现在的碎纸机，除了对纸张的处理，也可以对信用卡、光盘等进行切割。本文研究的只是针对印刷文字文件在碎纸机中被切割的碎片，它是规则的黑白图片，对于非印刷文字文件的碎纸片、彩色碎纸片、形状不规则或边缘有破损的碎纸片等都是该碎纸片拼接技术的重要影响因素。随着科学技术的不断发展，人们对信息交流、存储和销毁的需求也不断的增加。目前，大量政府机关、企事业单位都是用打印机来打印文件，也都采用了碎纸机对废弃文件或失效的机密文件进行破碎处理。当遇到误销毁的文件时，就要靠人工对碎纸片进行拼接，而人工拼接工作量大 ，不仅费力耗时，可能还会出现拼接错误等情况。如果应用当前的图像处理与模式识别技术来开发碎纸片的自动拼接技术，用计算机对所有碎片进行搜索和筛选，对能够在某种指标上匹配的碎片进行拼接复原。这样会大大的提高拼接复原的效率，从而降低了人工的工作量和难度。目前在情报资料碎片整理、司法技术鉴定等领域中, 碎纸的拼接工作大部分都是靠人工的方式完成。虽然国外对这项工作有进行了一些研究, 但是由于碎纸的自动修复技术应用背景的特殊性, 目前几乎没有公开的研究资料可以参考。类似的研究主要是集中在文物碎片的自动修复、虚拟考古、故障分析以及计算机辅助设计、医学分析等领域。所以对规则碎片自动拼接问题的研究，不仅具有广阔的应用前景，而且具有很强的理论意义。问题1：对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（纵切），建立碎纸片拼接复原模型和算法，针对附件1、附件2针对文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。分析：针对问题1，在附件一及附件二中，碎纸片仅纵切 ，则纸片边缘的字有可能出现完整、残缺、标点符、空格四种情况，每个字又由多个像素点组成，故我们利用Matlab图像处理函数imread（）将各个碎片文字像素二值化，并取出代表各个碎片左右两边缘的像素点的列向量，如此在每张碎片左右两边缘所获的值都可组成一组向量，且分别设左边缘 ,右边缘 （ ）。设复原图像的第1列像素为 向量，第72列像素为 向量列，以此类推直到最后一列像素为 。因为原图像的第一列像素全为255（白色），所以可找出 ，从而可以确定 和 对应的 和 ，将该碎纸片数据放入向量A中，再将列向量 逐一与剩下的所有图片的列向量 元素作差，列方向绝对值求和，则和最小的就是能与 匹配的碎片，以此类推。匹配完成后用Matlab图像处
碎纸片拼接复原问题研究
基于旅行商规划模型的碎纸片拼接复原问题研究 摘要 本文分别针对RSSTD(Reconstruction of Strip Shredded Text Document）、RCCSTD(Reconstruction of cross-cut Shredded Text Document)和Two-Sides RCCSTD三种类型的碎纸片拼接复原问题进行了建模与求解算法设计。首先我们对于RSSTD问题，建立了基于二值匹配度的TSP模型，并将其转化为线性规划模型，利用贪心策略复原了该问题的中文和英文碎片；然后对于RCCSTD问题，由于中英文字的差别，我们分别建立了基于改进误差评估的汉字拼接模型和基于文字基线的误差评估的英文字拼接模型，并利用误差评估匹配算法，复原了该问题的中文和英文碎片；随后我们针对正反两面的RCCSTD 问题，利用基线的概念将正反两面分行，转化为RCCSTD问题，并复原了该问题的英文碎片。最后，我们对模型的算法和结果进行了检验和分析。 ◎问题一：我们针对仅纵切的情况，首先将图像进行数字化处理，转换为了二值图像，然后得到各图像的边缘，并计算所有碎片与其他碎片边缘的匹配程度。然后，根据两两碎片之间的匹配程度建立了TSP模型，并将其划归为线性规划模型。最终，我们根据左边距的信息确定了左边第一碎片，随后设计了基于匹配度的贪心算法从左向右得到了所有碎片的拼接复原结果。结果表明我们的方法对于中英文
两种情况适用性均较好，且该过程不需要人工干预。 ◎问题二：我们针对既纵切又横切的情况，由于中英文的差异性，我们在进行分行聚类时应采用不同的标准。首先根据左右边距的信息确定了左边和右边的碎片，随后分别利用基于改进误差评估的汉字拼接模型和基于文字基线的误差评估模型，将剩余的碎片进行分行聚类，然后再利用基于误差评估的行内匹配算法对行内进行了拼接，最终利用行间匹配算法对行间的碎片进行了再拼接，最终得到了拼接复原结果。对于拼接过程中可能出现误判的情况，我们利用GUI 编写了人机交互的人工干预界面，用人的直觉判断提高匹配的成功率和完整性。 ◎问题三：我们针对正反两面的情况，首先根据正反基线信息，分别确定了左右两边的碎片，然后利用基线差值将其两两聚类，聚类以后其正反方向也一并确定，随后我们将其与剩余碎片进行分行聚类，最终又利用行内匹配和行间匹配算法得到了最终拼接复原结果。其中，对于可能出现的误判情况，我们同样在匹配算法中使用了基于GUI的人机交互干预方式，利用人的直觉提高了结果的可靠性和完整性。 关键字：碎片复原、TSP、误差评估匹配、基线误差、人工干预
碎纸片的拼接复原的数学模型
碎纸片的拼接复原 摘要 本文主要采用了模糊模型识别、灰度相关、傅里叶变换等方法对碎纸自动拼接进行了深入探讨。 文中主要结合司法物证复原、历史文献修复、军事情报获取这一背景，针对横纵切碎自动拼接展开探究。提出一种基于最大梯度和灰度相关的全景图拼接法。同时采用边界提取法使图像预处理达到最好的效果，期间采用傅里叶变换对图像进行处理，最后再利用匹配准则等方法处理图像的拼接。最终应用模糊模型识别法建立模型，通过隶属函数的建立实现最终的碎纸拼接。期间有些碎纸片计算机无法识别，需要进行人工干预，从而才能得到一副完整的复原图。 图像拼接的主要工作流程可以概括为以下三个步骤： （1） 对图像碎片进行预处理，即对物体碎片数字化，得到碎片的数字图像。 （2） 图像碎片匹配，通过匹配算法找到相互匹配的图像碎片。 （3） 图像碎片的拼接合并，将相互匹配的图像碎片拼接在一起得到最终结果。 ! 针对问题一：将图像导入MATLAB 进行相应的转化，由于数据量较大，所以 对数据进行优化提取。计算提取数据的均值与方差，找出其模糊集，建立符合题意的隶属函数。由于模糊集的边界是模糊的，如果要把模糊概念转化为数学语言，需要选取不同的置信水平(01)λλ≤≤ 来确定其隶属关系，从而实现纵切图像的全景拼接。（如表一、表二） 针对于问题二：由于是横纵切碎纸片，所得图像较多，采用提取像素法对图片进行灰度分析，通过中介量阈值的确定来找出像素点的差别，梯度值在这一过程中也是作为衡量两张碎纸片是否匹配的标准。从而对数据进行处理，最后导入MATLAB 软件实现拼接。（如表三、表四） 针对问题三：它是在问题一和问题二上加深了难度，采用提取像素点，傅里叶变换，灰度相关、模糊相似优先比等方法对问题进行分析，通过（0,1）矩阵的简化运算以及傅里叶变换得到最后的结果，但对于傅里叶变换需说明一点，变换之后的图像在原点平移之前四角是低频，最亮，平移之后中间是低频最亮，也就是说幅角比较大。此过程中同时也需要人工干预，最终实现拼接。（如表五、表六）
2013数学建模B题国家一等奖Matlab程序
附录3：程序源文件 1.duqu_image.m文件 %数据读取预处理文件 %将附件中的图片读取到matlab矩阵中，并保存为image_1，image_2，image_3，image_4，image_5a，image_5b %所有附件均放在文件夹 D:\B 中%%%%%%%%%%%%%%%%%%%%%%%%图片名序列 %图像名称序号 b = [ones(1,10);0 1 2 3 4 5 6 7 8 9]'; image_num= [ strcat( num2str(0*b(:,1)),num2str(0*b(:,1)),num2str(b(:,2)) ), strcat( num2str(0*b(:,1)),num2str(b(:,1)),num2str(b(:,2)) ), strcat( num2str(0*b(:,1)),num2str(2*b(:,1)),num2str(b(:,2)) ), strcat( num2str(0*b(:,1)),num2str(3*b(:,1)),num2str(b(:,2)) ), strcat( num2str(0*b(:,1)),num2str(4*b(:,1)),num2str(b(:,2)) ), strcat( num2str(0*b(:,1)),num2str(5*b(:,1)),num2str(b(:,2)) ), strcat( num2str(0*b(:,1)),num2str(6*b(:,1)),num2str(b(:,2)) ), strcat( num2str(0*b(:,1)),num2str(7*b(:,1)),num2str(b(:,2)) ), strcat( num2str(0*b(:,1)),num2str(8*b(:,1)),num2str(b(:,2)) ), strcat( num2str(0*b(:,1)),num2str(9*b(:,1)),num2str(b(:,2)) ), strcat( num2str(b(:,1)),num2str(0*b(:,1)),num2str(b(:,2)) ), strcat( num2str(b(:,1)),num2str(b(:,1)),num2str(b(:,2)) ), strcat( num2str(b(:,1)),num2str(2*b(:,1)),num2str(b(:,2)) ), strcat( num2str(b(:,1)),num2str(3*b(:,1)),num2str(b(:,2)) ), strcat( num2str(b(:,1)),num2str(4*b(:,1)),num2str(b(:,2)) ), strcat( num2str(b(:,1)),num2str(5*b(:,1)),num2str(b(:,2)) ), strcat( num2str(b(:,1)),num2str(6*b(:,1)),num2str(b(:,2)) ),
2013数学建模国赛B题
3v2013高教社杯全国大学生数学建模竞赛题目 （请先阅读“全国大学生数学建模竞赛论文格式规范”） B题碎纸片的拼接复原 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题： 1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。 2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。 3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。 【数据文件说明】 (1)每一附件为同一页纸的碎片数据。 (2)附件1、附件2为纵切碎片数据，每页纸被切为19条碎片。 (3)附件3、附件4为纵横切碎片数据，每页纸被切为11×19个碎片。 (4)附件5为纵横切碎片数据，每页纸被切为11×19个碎片，每个碎片有正反两面。该附 件中每一碎片对应两个文件，共有2×11×19个文件，例如，第一个碎片的两面分别对应文件000a、000b。 【结果表达格式说明】 复原图片放入附录中，表格表达格式如下： (1)附件1、附件2的结果：将碎片序号按复原后顺序填入1×19的表格； (2)附件3、附件4的结果：将碎片序号按复原后顺序填入11×19的表格； (3)附件5的结果：将碎片序号按复原后顺序填入两个11×19的表格； (4)不能确定复原位置的碎片，可不填入上述表格，单独列表。
数学建模B题 含代码
2013高教社杯全国大学生数学建模竞赛 承诺书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）：华南师范大学增城学院 参赛队员(打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人(打印并签名)： 日期：年月日
赛区评阅编号（由赛区组委会评阅前进行编号）：
2013高教社杯全国大学生数学建模竞赛 编号专用页 赛区评阅编号（由赛区组委会评阅前进行编号）： 全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：
DVD在线租赁 摘要 问题（三）：题目需要我们回答购买各种DVD的数量来使95%的会员能看到他DVD想看到的DVD，并且要怎么分配才能使满意度达到最大；每种建立以总的购买数最小、会员满意度最大为双目标的规划模型。通过确定在一个月内每张DVD的在每个会员中手中的使用率；然后通过c语言程序编程来确定每种DVD 的购买量；建立0-1规划模型；通过LINGO软件使满意度达到最大，来最终确定DVD的分配； 一级，二级目标，将多目标规划转化为单目标；同时将第j种DVD的购买量y的整数约束去掉，求解出最小购买数为张。将最小购买数作为约束条件，优j 化满意度后，得到最大满意度为95%；然后对此时DVD的购买量 y向上取整，得 j 到总购买数为186张。当购买数为186张时，会员满意度达到97%。 三、模型假设 1、租赁周期为一个月，每月租两次的会员可以在月中再租赁一次； 2、同一种DVD每人只能租赁一次； 3、DVD在租赁过程中无损坏； 4、会员每月至少交一次订单； 5、会员只有把前一次所借的DVD寄回，才可以继续下一次租赁 6、月底DVD全部收回，继续下个周期的租赁； 7、随着时间的推移，该网站的会员们的流动情况不会出现大变动。 四、符号说明
碎纸片的拼接复原
全国大学生数学建模竞赛论文格式规范 本科组参赛队从A、B题中任选一题，专科组参赛队从C、D题中任选一题。（全国评奖时，每个组别一、二等奖的总名额按每道题参赛队数的比例分配；但全国一等奖名额的一半将平均分配给本组别的每道题，另一半按每题论文数的比例分配。） 论文用白色A4纸打印；上下左右各留出至少2.5厘米的页边距；从左侧装订。 ●论文第一页为承诺书，具体内容和格式见本规范第二页。 ●论文第二页为编号专用页，用于赛区和全国评阅前后对论文进行编号，具体内容和 格式见本规范第三页。 ●论文题目、摘要和关键词写在论文第三页上（无需译成英文），并从此页开始编写 页码；页码必须位于每页页脚中部，用阿拉伯数字从“1”开始连续编号。注意：摘要应该是一份简明扼要的详细摘要，请认真书写（但篇幅不能超过一页）。 ●从第四页开始是论文正文（不要目录）。论文不能有页眉或任何可能显示答题人身 份和所在学校等的信息。 ●论文应该思路清晰，表达简洁（正文尽量控制在20页以内，附录页数不限）。 ●引用别人的成果或其他公开的资料(包括网上查到的资料) 必须按照规定的参考文 献的表述方式在正文引用处和参考文献中均明确列出。正文引用处用方括号标示参考文献的编号，如[1][3]等；引用书籍还必须指出页码。参考文献按正文中的引用次序列出，其中书籍的表述方式为： [编号] 作者，书名，出版地：出版社，出版年。 参考文献中期刊杂志论文的表述方式为： [编号] 作者，论文名，杂志名，卷期号：起止页码，出版年。 参考文献中网上资源的表述方式为： [编号] 作者，资源标题，网址，访问时间（年月日）。 ●在论文纸质版附录中，应给出参赛者实际使用的软件名称、命令和编写的全部计算 机源程序（若有的话）。同时，所有源程序文件必须放入论文电子版中备查。论文及源程序电子版压缩在一个文件中，一般不要超过20MB，且应与纸质版同时提交。 （如果发现程序不能运行，或者运行结果与论文中报告的不一致，该论文可能会被认定为弄虚作假而被取消评奖资格。） ●本规范中未作规定的，如排版格式（字号、字体、行距、颜色等）不做统一要求， 可由赛区自行决定。 ●在不违反本规范的前提下，各赛区可以对论文增加其他要求（如在本规范要求的第 一页前增加其他页和其他信息，或在论文的最后增加空白页等）。 ●不符合本格式规范的论文将被视为违反竞赛规则，无条件取消评奖资格。 ●本规范的解释权属于全国大学生数学建模竞赛组委会。 [注] 赛区评阅前将论文第一页取下保存，同时在第一页和第二页建立“赛区评阅编号”（由各赛区规定编号方式），“赛区评阅纪录”表格可供赛区评阅时使用（各赛区自行决定是否在评阅时使用该表格）。评阅后，赛区对送全国评阅的论文在第二页建立“全国统一编号”（编号方式由全国组委会规定，与去年格式相同），然后送全国评阅。论文第二页（编号页）由全国组委会评阅前取下保存，同时在第二页建立“全国评阅编号”。 全国大学生数学建模竞赛组委会 2013年8月26日修订
2013年数学建模B题一等奖优秀论文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。 针对问题二，首先根据每张纸片内容的不同特性，对图片进行聚类分析，将209张图片分为11类；对于每一类图片，按照问题一的模型与算法，即列偏差函数最小则进行左右拼接,对于没有拼接到组合里的碎纸片进行人工干预，我们得到了11组碎纸片拼接而成的图片；对于拼接好的11张图片，按照问题一的模型与算法，即行偏差函数最小则进行上下拼接,对于没有拼接到组合里的碎纸片进行人工干预。我们最终经计算，附件3的拼接结果见表9，附件4的拼接结果见表10。 针对问题三，由于图片区分正反两面，在问题二的基础上，增加图片从下到上的裁截距信息，然后进行两次聚类，从而将所有图片进行分类，利用计算机自动拼接与人工干预相结合，对所有图片进行拼接复原。经计算，附件5的拼接结果见表14和表15 该模型的优点是将图片分为具体的几类，大大的减少了工作量，缺点是针对英文文章的误差比较大。 关键字：灰度处理，图像二值化，最小二乘法，聚类分析，碎纸片拼 一、问题重述 碎纸片的拼接复原技术在司法鉴定、历史文献修复与研究、军事情报获取以及故障分析等领域都有着广泛的应用。近年来，随着德国“斯塔西”文件的恢复工程的公布，碎纸文件复原技术的研究引起了人们的广泛关注。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。对于一页印刷文档，针对不同的破碎方法，讨论下列三个问题： （1）将给定的一页印刷文字文件纵切，建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。 （2）对于碎纸机既纵切又横切的情形，设计碎纸片拼接复原模型和算法，并针对附
碎纸片拼接复原数模论文b
碎纸片拼接复原数模论 文b Revised as of 23 November 2020
2013高教社杯全国大学生数学建模竞赛 承诺书 我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。 我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）：重庆XX大学 参赛队员 (打印并签名) ：1. 祝XX 2. 冯XX 3. 周XX 指导教师或指导教师组负责人 (打印并签名)：张XX （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。） 日期： 20XX 年 X 月 XX 日赛区评阅编号（由赛区组委会评阅前进行编号）：
2000年数学建模B题解答
2000年数学建模B题 解答 -CAL-FENGHAI-(2020YEAR-YICAI)_JINGBIAN
钢管订购和运输 摘要：本文建立了一个运输问题的最优化模型。 通过分析题图一，我们利用Floyd算法求出铁路网和公路网各点间最短路线，然后转化成最少运输，去掉了铁路和公路的性质，使运输网络变成一张供需运输价格表，然后建立了一个以总费用为目标函数的非线性规划模型，利用 Lingo 软件，求出问题一的最优解为1278632万元 通过对问题一中lingo运行结果的分析，我们得出S5钢厂钢管的销价的变化对购运计划和总费用影响最大，S1钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大。 问题三模型的建立原理和问题一的相同，利用Lingo 软件，求得最优解为1407149万元. 关键词：Floyd算法，非线性规划，0-1规划
一 问题重述 有7个生产厂，可以生产输送天然气主管道的钢管 721,,S S S 。要沿着 1521A A A →→→ 的主管道铺设, 如题图一所示。图中粗线表示铁路，单细线表示公路，双 细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。为方便计，1km 主管道钢管称为1单位钢管。 一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂i S 在指定期限内能生产该钢管的最大数量为i s 个单位，钢管出厂销价1单位钢管为i p 万元，如下表： 123456780080010002000200020003000160155155160155150160 i i s i p 1单位钢管的铁路运价如下表： 里程(km) ≤300 301～350 351～400 401～450 451～500 运价(万元) 20 23 26 29 32 里程(km) 501～600 601～700 701～800 801～900 901～1000 运价(万元) 37 44 50 55 60 1000km 以上每增加1至100km 运价增加5万元。 公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。 钢管可由铁路、公路运往铺设地点（不只是运 到点，而是管道全线）。 （1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。 （2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。 （3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对题图二按（1）的要求给出模型和结果。 二 问题分析 问题一，首先，所有钢管必须运到天然气主管道铺设路线上的节点 1521,,,A A A
2013年美国数学建模竞赛B题
水资源计划 摘要 本文是要设计一个有效的，可行的，低成本的用水计划，来满足某国2025年的用水需求。我们选择中国为研究对象，根据中国各地区历年的水资源总量并求出其均值，参考各地区历年用水总量来预测2025年的用水总量，将两者相减得出差值，并以此为依据将中国各地区分为缺水地区，不缺水地区，水资源丰富地区三类。经研究分析有两种可行性高的方案。第一种，由水资源丰富地区向缺水地区提供水。第二种，是由沿海缺水城市进行海水淡化并运往其他缺水城市。我们主要考虑经济因素对两种方案进行分析研究，最终得出结论由水资源丰富地区铺设管道向缺水地区提供水为最优方案。并以各省的省会作为核心城市，说明全省的需水和调水情况，并以省会城市或直辖市为顶点构成一个赋权图，即把问题转换为求水资源丰富地区到缺水地区的最短路问题，并用图论的知识来解决问题。在此基础上考虑到此方案会改变就业，生产力，水资源利用等因素，从而对经济，物理，环境产生不同程度的影响，并用层次分析加以研究，最终以报告的方式向政府反映。 关键词：回归分析最小生成树层次分析法
一、问题重述 淡水是世界大部分地区的发展限制。试建立一个数学模型，用来确定一个有效的、可行的和低成本的水资源战略，以满足2025年预计的用水需求，特别是，您的数学模型必须解决存储和输送，去盐碱化和环境保护等问题。如果可能的话，用你的模型探讨此战略在经济，物理和环境等方面的影响。试提供一个非技术性的文件，向政府相关部门介绍你的方法以及其可行性和成本，并说明为什么它是“最好的水战略”。 二、符号说明 ?y：预测得出的2025年用水量； S：输水的造价； 1 S：海水淡化的造价； 2 d1: 输水工程的单位造价； d2：海水淡化的单位造价； 2 R：拟合度. 三、模型假设 1.从2013年到2025年各外部因素对水资源总量无影响，例如：雪灾、地震、 洪水、战争等对环境的影响； 2.各地区海水淡化单位费用相同； 3.不同地区淡水转移的单位费用相同； 4.人们的消费水平及劳动力费用不会随意外事故发生明显改变。 四、问题分析 以下内容以中国为例，考虑到中国的实际国情，我国是世界上12个贫水国家之一，淡水资源还不到世界人均水量的1/4。全国600多个城市半数以上缺
2013国赛B题碎纸片的拼接复原
2013高教社杯全国大学生数学建模竞赛题目 （请先阅读“全国大学生数学建模竞赛论文格式规范”） B题碎纸片的拼接复原 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题： 1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。 2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。 3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。 【数据文件说明】 (1)每一附件为同一页纸的碎片数据。 (2)附件1、附件2为纵切碎片数据，每页纸被切为19条碎片。 (3)附件3、附件4为纵横切碎片数据，每页纸被切为11×19个碎片。 (4)附件5为纵横切碎片数据，每页纸被切为11×19个碎片，每个碎片有正反两面。该附 件中每一碎片对应两个文件，共有2×11×19个文件，例如，第一个碎片的两面分别对应文件000a、000b。 【结果表达格式说明】 复原图片放入附录中，表格表达格式如下： (1)附件1、附件2的结果：将碎片序号按复原后顺序填入1×19的表格； (2)附件3、附件4的结果：将碎片序号按复原后顺序填入11×19的表格； (3)附件5的结果：将碎片序号按复原后顺序填入两个11×19的表格； (4)不能确定复原位置的碎片，可不填入上述表格，单独列表。
2013年全国大学生数学建模竞赛B题全国一等奖论文
碎纸片的拼接复原 【摘要】 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。本文主要解决碎纸机切割后的碎纸片拼接复原问题。 针对第一问，附件1、2分别为沿纵向切割后的19张中英文碎纸片，本文在考虑破碎纸片携带信息量较大的基础上，利用MATLAB对附件1、2的碎纸片图像分别读入，以数字矩阵的方式进行存储。利用数字矩阵中包含图像边缘灰度这一特征，本文采用贪心算法的思想，在首先确定原文件左右边界的基础上，以Manhattan距离来度量两两碎纸片边界差异度，利用计算机搜索依次从左往右搜寻最匹配的碎纸片进行横向配对并达成排序目的。最终，本文在没有进行人工干预，成功地将附件1、2碎纸片分别拼接复原，得到复原图片见附录2.1、2.2，纵切中文及英文结果表分别如下: 思想仍为贪心算法，整体思路为先对209张碎纸片进行聚类还原成11行，再对分好的每行进行横向排序，最后对排序好的各行进行纵向排序。本文在充分考虑汉字与拉丁字母结构特征差异以及每块碎纸片携带信息减少的基础上，创新地提出一种特征线模型来分别描述汉字及拉丁文字母的特征用于行聚类。对于行聚类后碎片的横向排序，本文综合了广义Jaccard系数、一阶差分法、二阶差分法、Spearman系数等来构建扩展的边界差异度模型，刻画碎片间的差异度。对于计算机横向排序存在些许错误的情况，本文给出了人工干预的位置节点和方式。对于横向排序后的各行，由于在一页纸上，文字的各行是均匀分布的，本文基于各行文字的特征线，在确定首行的位置后，估计出其他行的基准线位置，得到一页的基准线网格，并通过各行基准线在基准线网格上的适配实现纵向的排序。最终，本文成功的将附件3、4碎纸片分别拼接复原得到复原图片及结果表见附录1.3、1.4、2.3、2.4，同时本文给出了横向排序中人工干预的位置节点和方式。 针对第三问，附件5为双面文件既横切又纵切后的209张碎片（包含正反面），即包含418张图像。本文整体解决思路同第二问中对于拉丁文碎片的复原类似，并且由于正反两面的特征可以同时作为差异度判断条件，特征信息丰富，综合使用各种差异度函数后可以将各行全部正确排列，无需人工排错，同时正确排序时自然分出两面。以与问题二类似的方法，确定出每一面的第一行后，用基准线网格确定各行的位置并排序。然而由于附件5原件的第3、第4行及第9、第10行的两个切口正好切到了两行行间的空白，同时两面文字高度一致，所以计算机不可能分辨二者是否在同一面，此处必须由人工介入，通过上下文区分。最终，本文成功的将附件5所有碎片分别拼接复原得到复原图片及结果表见附录1.5、1.6、2.5、2.6。对于本问题，本文只在最后模块的上下文判断和横向排列的方法选择时进行了干预，自动化程度高。 本文发现在横向排序中，一、二阶差分法对于样本量大的情况适配成功率很高，而广义Jaccard系数及Spearman系数则对样本量小但特征显著的情况适配的成功率更高。 关键词：图像拼接复原贪心算法差异度相似系数文字基准线 1
碎纸片的拼接复原问题
2013高教社杯全国大学生数学建模竞赛 编号专用页 赛区评阅编号（由赛区组委会评阅前进行编号）： 全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：
碎纸片的拼接复原问题 摘要 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。本文针对已给图像先进行了图片灰度二值化处理得到碎纸片的像素矩阵，提取碎纸片的边缘像素矩阵，对边缘矩阵进行相似度分析，相似度的度量采用向量距离平方和最小化，在相似度度量中设置阈值、对相近相似度的候选纸片进行人工干预、对数据量较大的附件，采用文本特征，如页边距、行距进行筛选，降低计算量，提高计算精度。使用Matlab软件编程实现了上述算法，在对附件的拼接中通过少量的人工干预，可实现纸片的完整拼接，效果较好。 关键词：相似度；文字特征；碎纸片拼接；Matlab；
1 问题重述 1.1 问题的描述 设计一个碎纸片的自动拼接模型，以提高碎纸片的拼接复原效率。 1.2 问题的要求 （1）对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。 （2）对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。 （3）从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。 1.3 问题的分析 对破碎文件这类边缘相似的碎纸片的拼接，理想的计算机拼接过程应与人工拼接过程类似，即拼接时不但要考虑待拼接碎纸片边缘是否匹配，还要判断碎纸片内的字迹断线或碎片内的文字内容是否匹配，然而由于理论和技术的限制，让计算机具备类似人那种识别破碎边缘地字迹断线、以及理解碎片内文字图像含义的智能几乎不太可能。但是分析了基于几何特征的碎纸片自动拼接方法的缺点,研究了碎纸片内文字行特征以及行特征获取方法。利用这些信息进行拼接，其拼接效率无疑比单纯利用边界几何特征方法要好些。 另一方面由于计算机数字分析图像能力的缺陷，让计算机对碎片进行完全意义上的自动化拼接也几乎不大可能，这就需要我们在拼接过程加入人工干扰过程，对一些碎片进一步分析结果舍弃或拼接待选。 2 模型假设和符号系统
2013年数学建模B题碎纸片的拼接复原
B题 碎纸片的拼接复原 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题： 1．对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。 2．对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。 3．上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。 【数据文件说明】
（1）每一附件为同一页纸的碎片数据。 （2）附件1、附件2为纵切碎片数据，每页纸被切为19条碎片。 （3）附件3、附件4为纵横切碎片数据，每页纸被切为 11×19个碎片。 （4）附件5为纵横切碎片数据，每页纸被切为11×19个碎片，每个碎片有正反两面。该附件中每一碎片对应两个文件，共有2×11×19个文件，例如，第一个碎片的两面分别对应文件 000a、000b。 【结果表达格式说明】 复原图片放入附录中，表格表达格式如下： （1）附件1、附件2的结果：将碎片序号按复原后顺序填入 1×19的表格； （2）附件3、附件4的结果：将碎片序号按复原后顺序填入11×19的表格； （3）附件5的结果：将碎片序号按复原后顺序填入两个 11×19的表格；
碎纸片的拼接复原问题大学生数学建模全国一等奖论文
碎纸片的拼接复原问题 摘要 为解决碎纸片的拼接复原问题，我们通过定义差异度指数、高度差，建立0-1规划模型，使用聚类分析、MATLAB搜索算法和人工干预等相结合，得到了所有附件复原序号和复原图片。 针对问题一，首先提取附件1、2中所有碎片左侧和右侧边缘灰度，通过任意列碎片右侧和任意列碎片左侧的边缘灰度差值可以定义差异度指数，从而得到差异度特征矩阵，然后建立0-1规划模型，以第i张碎片右侧与第j张碎片左侧差异度最小为目标函数，以第i张碎片右侧与第j张碎片左侧是否相连为决策变量，以每张碎片右侧一定与某张碎片左侧相连、每张碎片左侧一定与某张碎片右侧相连为约束条件。算法为先提取任意张碎片边缘灰度值，得到差异度矩阵，带入规划模型中，通过LINGO软件找到中英文碎片的拼接方法，得到复原序号如表一、表二，从而得到出中文与英文复原图片。 表一:中文碎片的复原序号 表二：英文碎片的复原序号 片拼接方法。结果表明两种方法得出的中英文复原顺序相同，复原图片相同，同时人工检验中英文复原图片中无明显语法、单词错误，证明复原图片准确。 针对问题二，由于每张碎片有左侧、右侧和上侧、下侧，与问题一相同，可以定义两个差异度指数，建立双目标0-1规划模型。但由于差异度矩阵过大，决策变量复杂，我们又建立了改进的简化模型，定义高度差，运用聚类分析方法，按照高度不同将所有碎片分为18类，然后再以第j块碎片左侧与第i块碎片右侧的差异度最小为目标函数，以第i块碎片右侧与第j块碎片左侧是否相连为决策变量，以每块碎片右侧一定与某块碎片左侧相连、每块碎片左侧一定与某块碎片右侧相连，满足高度差阈值为约束条件，建立单目标0-1规划模型。算法为先提取任意块碎片边缘灰度值和高度，得到差异度矩阵，编程将中文碎片按高度分为18类，人工干预分为11行，再利用问题一中碎片纵向复原方法，得到中文复原序号，画出中文复原图片。（英文复原模型相似，仅高度差阈值不同） 针对问题三，对于双面英文碎片的复原问题，我们提出了单词残缺程度的定义，定量的描述了英文碎片的特征信息，构成了算法的核心内容，运用编程和人工干预将碎纸片分为11类，每类19个碎片，在此基础上利用前两问所建的0-1规划模型，再加上双面的一些约束条件，得到双面英文复原序号，并绘出英文双面复原图片。 关键词：差异度指数；0-1规划；LINGO软件；聚类分析；高度差；残缺程度；