赛题解析

题目

2013年B题 碎纸片的拼接复原

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

    接下来讨论这个问题：对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法。

我们在全国大学生数学建模竞赛上可以下载到这道题目所给的图片数据。
全国大学生数学建模竞赛官网: 历年赛题.
如果对数学建模历年所有题目感兴趣也欢迎下载我整理好的资料:全套

解题思路

    我们首先会得到一张完整诗歌图片的19张等长纵切片，这些图片被完全打乱了顺序。我们所要做的就是创建一个合理的模型来实现对所有碎片的重排序与拼接。
    首先我们知道，我们得到的碎片如果不是在左右两边，那么它的左右两边都是有可能有不完整的汉字的。如果我们把这些图片转换成0-1像素矩阵（0表示黑色，1表示白色），那么任意两个处于中间位置的图片，位于左方图片的最右边与右方图片的最左边，每一行对应的值基本是相等的。此时我们用列向量相减的方法，得到另一个列向量，它表示任一碎片的最左边与另一张碎片的最右边像素列向量每一行对应的差值，再求和以此来表示两张碎片之间的”距离”。之后我们再对这些”距离”进行排序，找到最小的那个，就表示这个”距离”对应的两张碎片是相临的。

算法细节

1. 用imread函数读取图片并转换成0-1矩阵（0表示黑色，1表示白色）。
2. 首先计算每张图片的第一列与最后一列的总和，找出第一张图片（最左边）和最后一张图片（最右边）。
3. 从左边的开始，以此计算它与剩下的每个碎片的最右边的”距离”，再找出最小的那个，就代表它们相邻。
4. 我在这设置了一个类似于C语言指针的变量p，这里p始终指向当前处理的碎片，即要找出与它右相邻的另一张碎片。（p表示一组行向量的下标，具体见代码。）
5. 继续的进行第4步，直到p指向之前已经找到的最右边的碎片。
6. 将对应的矩阵按顺序拼接起来，然后用imshow函数输出显示。

这套算法我是用matlab实现的，但是由于本人对matlab的理解过于浅薄，对矩阵运算理解的还不够，所以希望各位大神多多指出我的不足。

运行结果

Matlab源码

此处展示以上解析的源码，如何运用最小距离方法将分成19列的碎纸片拼接成一张完整的图片。

clc
clear
close all
%1、把碎片的矩阵进行提取
%2、把矩阵转换为向量（行和或者行平均）
%3、对11*19个向量运用聚类（系统聚类：向量之间的距离用相关系数、类与类之间的距离用ward）
%4、对每一类用第一题中的算法进行分类
pic1=zeros(1980,72,19);
pic3=zeros(1980,1368);
for i=0:18
    s=strcat(int2str(i),'.bmp');
    pic1(:,:,i+1)=imread(s);
end
%%%将图片二值化
for i=1:19
    for j=1:1980
        for p=1:72
            if pic1(j,p,i)~=255
                pic1(j,p,i)=1;
            else
                pic1(j,p,i)=0;%黑色为0，白色为1
            end
        end
    end
end
r=zeros(19);
for i=1:19
    for j=i:19
        r(i,j)=sum(abs(pic1(:,1,i)-pic1(:,end,j)));
    end
end
for i=1:19
    for j=1:i
        r(i,j)=sum(abs(pic1(:,end,i)-pic1(:,1,j)));
    end
end
for i=1:19
    r(i,i)=inf;
end
for i=1:19
   if pic1(:,1,i)==0
       first_pic=i;%找到第一张图片
   end
   if pic1(:,end,i)==0
       end_pic=i;%找到最后一张图片
   end
end
r1=1980*ones(1,19);
rank_pic=zeros(1,19);
p1=first_pic;
xuhao=1;
rank_pic(xuhao)=first_pic;
cjl=0;%当这个值为0时说明没有重复，从第一个排序向量开始一开始p1=first,之后我们都要判定当前计算的i值是否已经出现过，如果出现过那么就跳过不计算。
while p1~=end_pic
    for i=1:19
        for j=1:i
            if i==rank_pic(j)
                cjl=1;
            end
        end
        if i~=p1 && cjl==0
            r1(i)=sum(sum(abs(pic1(:,end,p1)-pic1(:,1,i))));
        end
        cjl=0;
    end
    [~,label]=min(r1);
    p1=label;
    cjl=0;
    r1=1980*ones(1,19);%将R1重新初始化！！！！
    xuhao=xuhao+1;%序号递增
    rank_pic(xuhao)=label;%将当前得到的最短距离放入排好的序列
end
pic2=pic1(:,:,rank_pic(1));
for i=1:18
    pic2=[pic2 pic1(:,:,rank_pic(i+1))];
end
[m,n]=size(pic2);
pic2=1-pic2;
imshow(pic2);

如果想要交流更多数据建模比赛的经验
欢迎关注我的公众号**夏虫不可语冰也**
同时也欢迎访问我的个人网站 www.cjl946.com

今天的文章数学建模-关于碎纸片的拼接复原的理解（2003年建模国赛B题 附Matlab源码）分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。