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) 不能确定复原位置的碎片，可不填入上述表格，单独列表。
整体求解过程概述(摘要)
文字碎纸片拼接复原是一项在司法物证复原、历史文献修复以及军事情报获取等领域有着广泛应用的工作。所以对文字碎纸片的研究的重要性不言而喻。本文研究的目的皆在建立数学模型与算法，解决碎片复原中的三个问题，使得对三种不同特点碎片复原的人工干预次数较少，尽可能实现碎片复原的全自动化。
问题一，对纵切碎片复原。我们建立模型一，给出了基于旅行商问题的拼接策略。我们发现，碎片的拼接问题就是找到碎片最好的排列，找到一个排列类似于在一个图中找到一条路径。基于此，我们将碎片拼接问题抽象为一个图论问题，将碎片看做图中的顶点，碎片与碎片之间的匹配程度（匹配距离）看做图的边权。由此我们将碎片的拼接问题转化为一个哈密尔顿路径问题（不回到源点的旅行商问题）。 在问题一中的匹配距离为碎片边界横向匹配距离，即为一种衡量碎片与碎片在左右方向上边界图像匹配程度的指标，匹配距离越短，说明两碎片边界越相似，匹配程度越好。 模型一可用lingo与matlab编程求解。由于旅行商问题的求解是整体寻优，得到的结果为全局最优解，所以其准确性较高。对附件1与附件2的碎片还原结果我们没有进行人工干预。
问题二，对既纵切又横切的碎片复原。我们建立模型二，给出基于文本行特征的碎片行分组算法，对行分组碎片进行横向拼接得到复原的碎片行，再对碎片行进行纵向拼接，得到最终复原结果。这两种拼接策略均为模型一中基于旅行商问题的拼接策略。 其中，文本行特征即为文本行之间的规整性，利用文本行的规整性不仅可以对碎片进行行分组，而且还可以提高文本纵向拼接的准确度。 我们根据模型二，对附件3碎片还原的结果没有人工干预；在对附件4碎片还原时在行分组碎片横向拼接后有人工干预，即偶尔人工调整个别碎片还原结果。
问题三，对双面碎片复原。我们建立模型三，该模型中对碎片的行分组以及横向拼接同模型二中的方法，但考虑到碎片有两面，所用到的匹配距离需要替换为正反面匹配（两面的匹配距离之和）。此外，在对碎片行做纵向拼接时与模型二中的方法略有不同，由于碎片有双面信息，我们将模型一中基于旅行商问题的拼接策略扩展为多旅行商（2个旅行商）问题的拼接策略，即一条旅行商路径代表纸张的一面，另一条旅行商路径代表纸张的另一面。 对于模型三，由于采用了正反面匹配距离，用到了两面信息，其可用于拼接的信息量相对于单面碎片而言增大了一倍，所以对附件5碎片还原结果没有人工干预。 综上所述，我们建立的碎片复原模型与算法人工干预次数较少，对碎片复原工作有一定的参考价值。
模型假设：
本文研究的碎片具有如下特征。
所有碎片来自同一张纸。
所有碎片能够拼出完整的一张纸。
所有碎片尺寸大小相等，边缘轮廓为规则的矩形。
所有碎片中的文字颜色一致，且与背景颜色有较大反差。
所有碎片图片只有两种颜色，文字颜色与背景颜色。
所有碎片中的文字边缘清晰，已被去除噪音。
所有碎片中的文字是从左至右、从上至下书写的。
所碎片都已摆放端正，即碎片中的文字端正。
所有碎片中的文本行距相等。
问题分析：
问题一是对被纵切的碎片还原的问题，考虑到碎片的拼接问题是找到碎片与碎片之间最好的排列问题，由此，我们想到将碎片看做一个完全图的顶点，将碎片拼接转化为一个不回到源点的旅行商问题，即找到一条能够走过所有顶点（每个顶点只被访问一次）并且使得边权值之和符合要求的路径。基于此，我们建立了模型一，给出了基于旅行商问题的碎片拼接策略。
问题二是对既被纵切又被横切的碎片还原。先考虑纵切，此时就可用问题一的解决方法来处理，也就是说，对一些在同一行的碎片可用问题一的拼接策略解决。再考虑到横切，其实也与纵切无异，同样地，我们可以将拼接好的碎片行用问题一的拼接策略拼接起来得到最终的还原纸张。所以对问题二的处理过程中，我们首先需要先找到一些同在一行的碎片。在本文中我们结合文字行距特征给出了碎片分组的算法。基于此，我们建立了模型二。
问题三是对双面碎片的还原，我们可以用解决问题二的方法得到一些拼接好的碎片行，用类似问题一的方法将碎片行拼接起来，但此时由于碎片有正反面之分，我们所用的拼接策略是基于多旅行商问题（2个旅行商）的。基于此，我们建立了模型三。
综上所述，本文所研究的三个问题是环环相扣的，由此我们对三个问题分别建立的模型也具有这样的特点。即模型二是由若干模型一构成的，而模型三是由若干模型一与变化后的模型一构成的。 此外，对碎片与碎片间匹配程度的衡量，我们引入匹配距离（匹配距离越小，匹配程度越好），将匹配距离作为完全图的距离，如此一来模型一即为边权值之和最小的旅行商路径模型。而在模型二与模型三中，匹配距离根据文字特征与碎片特征而略有所不同。
模型的建立与求解整体论文缩略图
全部论文请见下方“ 只会建模 QQ名片” 点击QQ名片即可
程序代码：
MODEL:
SETS:
CITY / 1.. 11/: U; ! U( I) = sequence no. of city;
LINK( CITY, CITY):
DIST, ! The distance matrix;
X; ! X( I, J) = 1 if we use link I, J;
ENDSETS
DATA: !Distance matrix, it need not be symmetric;
dist=@OLE('C:\Users\Administrator\Desktop\sec.xlsx','data');
ENDDATA
!The model:Ref. Desrochers & Laporte, OR Letters, Feb. 91;
SUBMODEL SUB_LosT:
[OBJ_LosT] MIN = @SUM( LINK: DIST * X);
ENDSUBMODEL
SUBMODEL SUB_CON:
@FOR( CITY( K):
! It must be entered;
@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;
! It must be departed;
@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;
! Weak form of the subtour breaking constraints;
! These are not very powerful for large problems;
@FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:
U( J) >= U( K) + X ( K, J) -
( N - 2) * ( 1 - X( K, J)) +
( N - 3) * X( J, K)));
! Make the X's 0/1;
@FOR( LINK: @BIN( X));
! For the first and last stop we know...;
@FOR( CITY( K)| K #GT# 1:
U( K) <= N - 1 - ( N - 2) * X( 1, K);
U( K) >= 1 + ( N - 2) * X( K, 1));
ENDSUBMODEL
CALC:
N = @SIZE( CITY);
@solve(SUB_LosT,SUB_CON);
@text('C:\Users\Administrator\Desktop\程序\output.txt')=x;
endcalc
%计算碎片之间距离
clear
clc
clear
b=[53 208 70 93 126 137 138 153 175 0 32 45 56 68 166 174 196 7 158
]';%每行或列都不一样
a1=imread('D:\Program Files\matlab\附件3\000.bmp');
N=19;
[m,n]=size(a1);
aa=zeros(m,n,N);
for i=1:N
if b(i)<10
imageName=strcat('D:\Program Files\matlab\附件3\','0','0',int2str(b(i)),'.bmp');
elseif b(i)<100
imageName=strcat('D:\Program Files\matlab\附件3\','0',num2str(b(i)),'.bmp');
else
imageName=strcat('D:\Program Files\matlab\附件3\',num2str(b(i)),'.bmp');
end
aa(:,:,i) = imread(imageName);
end
[m,n]=size(a1);
d=zeros(N,N);
for i=1:N
for j=1:N
if i~=j
s=abs(aa(:,n,i)-aa(:,1,j));
d(i,j)=d(i,j)+sum(s');
else
d(i,j)=0;
end
end
end
%%%计算匹配度（距离）以及对图片进行匹配分类
clc
clear
%b=[32 45 83 110 113 116 128 144 147 148 179]';%找到的右端
%b=[20 21 71 82 133 147 160 172 192 202 209]';%找到的左端
%b33=[55 90 100 115 137 144 147 213 215 223 233 245 288 293 298 300 315 375 382 396 409 10];%右端
b33=[4 6 14 24 36 79 84 89 91 106 166 173 187 200 219 264 299 309 324 346 353 356];%左端
a1=imread('000a.bmp');
b=0:208;
[m,n]=size(a1);
[H,N]=size(b);
a=zeros(m,n,N*2);
%读取a的
for i=1:N
if b(i)<10
imageName=strcat('0','0',int2str(b(i)),'a.bmp');
elseif b(i)<100
imageName=strcat('0',num2str(b(i)),'a.bmp');
else
imageName=strcat(num2str(b(i)),'a.bmp');
end
a(:,:,i) = imread(imageName);
end
%读取b的
for i=1:N
if b(i)<10
imageName=strcat('0','0',int2str(b(i)),'b.bmp');
elseif b(i)<100
imageName=strcat('0',num2str(b(i)),'b.bmp');
else
imageName=strcat(num2str(b(i)),'b.bmp');
end
a(:,:,i+209) = imread(imageName);
end
%图的向量矩阵
t=zeros(180,2*11*29);
for i=1:2*11*19
for j=1:m
ss=0;
for l=1:n
ss=ss+(a(j,l,i)==0);
end
t(j,i)=ss;
end
end
dt=diff(t);
[ma,ind]=max(dt);
%找出下限
t=zeros(180,2*11*19);
for i=1:2*11*19
for j=1:m
ss=0;
for l=1:n
ss=ss+(a(j,l,i)==255);
if a(j,l,i)==255
ae(j,l,i)=1;
else
ae(j,l,i)=0;
end
end
t(j,i)=ss;
end
end
dt=diff(t);
[u3,r3]=sort(dt);
[ma,ind]=max(dt);
%补齐空白
N=63;
ind=ind+1;
for i=1:2*11*19
z=fix(ind(i)/N);
ind(i)=ind(i)-z*N;
if ind(i)<=N/3
for j=1:ind(i)
t(j,i)=0;
end
for k=0:1
for j=ind(i)+k*N:ind(i)+k*N+N/3
t(j,i)=1;
end
for j=ind(i)+k*N+N/3:ind(i)+k*N+N
t(j,i)=0;
end
end
for j=ind(i)+2*N:ind(i)+2*N+N/3
t(j,i)=1;
end
for j=ind(i)+2*N+N/3:180
t(j,i)=0;
end
elseif ind(i)>N/3&ind(i)<=N*2/3
for j=1:ind(i)
t(j,i)=0;
end
for k=0:1
for j=ind(i)+k*N:ind(i)+k*N+N/3
t(j,i)=1;
end
for j=ind(i)+k*N+N/3:ind(i)+k*N+N
t(j,i)=0;
end
end
if ind(i)+2*N+N/3>180
for j=ind(i)+2*N:180
t(j,i)=1;
end
else
for j=ind(i)+2*N:ind(i)+2*N+N/3
t(j,i)=1;
end
for j=ind(i)+2*N+N/3:180
t(j,i)=0;
end
end
elseif ind(i)>2*N/3&ind(i)<N
for j=ind(i)-2*N/3:ind(i)
t(j,i)=0;
end
for j=1:ind(i)-2*N/3
t(j,i)=1;
end
k=0;
for j=ind(i)+k*N:ind(i)+k*N+N/3
t(j,i)=1;
end
for j=ind(i)+k*N+N/3:ind(i)+k*N+N
t(j,i)=0;
end
k=1;
for j=ind(i)+k*N:ind(i)+k*N+N/3
t(j,i)=1;
end
if ind(i)+k*N+N<180
for j=ind(i)+k*N:ind(i)+k*N+N/3
t(j,i)=1;
end
for j=ind(i)+k*N+N/3:ind(i)+k*N+N
t(j,i)=0;
end
for j=ind(i)+k*N+N:180
t(j,i)=1;
end
else
for j=ind(i)+k*N:ind(i)+k*N+N/3
t(j,i)=1;
end
for j=ind(i)+k*N+N/3:180
t(j,i)=0;
end
end
end
end
%求匹配度最大的每行
s3=[];
for k=1:2*11
for i=1:2*11*19
s3(i,k)=0;
for j=1:180
if b33(k)<=209&i<=209
if t(j,b33(k))==t(j,i)&t(j,(b33(k)+209))==t(j,i+209)
s3(i,k)=s3(i,k)+1;
end
elseif b33(k)<=209&i>209
if t(j,b33(k))==t(j,i)&t(j,(b33(k)+209))==t(j,i-209)
s3(i,k)=s3(i,k)+1;
end
elseif b33(k)>209&i<=209
if t(j,b33(k))==t(j,i)&t(j,(b33(k)-209))==t(j,i+209)
s3(i,k)=s3(i,k)+1;
end
else
if t(j,b33(k))==t(j,i)&t(j,(b33(k)-209))==t(j,i-209)
s3(i,k)=s3(i,k)+1;
end
end
end
end
end
[ma4,ind4]=max(s3');
s31=zeros(22,60);
for i=1:22
a=sum(ind4==i);
s31(i,1:a)=find(ind4==i);
end
for i=1:22
for j=1:60
if s31(i,j)~=0
s32(i,j)=s3(s31(i,j),i);
end
end
end
[r32,u32]=sort(s32');
[r3,u3]=sort(s3);