碎纸片的拼接复原

admin

       碎纸片的拼接复原
       由于对任意一个字符来讲，笔画是连续的，所以对于一般情况，即使文字被切开，两边的像素还是有联系的，是呈现离散性渐变的。针对此特征，建立了文字连续性模型来求解该问题。而又因为被切开的两边碎片边缘灰度是具有高相关性的，所以，又建立了向量相关模型来求解进行图片拼接。用两种模型分别求解，都得到了对附件一和附件二的正确拼接结果。

       由于附件中的碎片分为正反两面，所以可以建立组合匹配模型将碎片首先将正反面碎片的灰度矩阵上下拼接，每张碎片的拼接方案有两种（灰度矩阵a放在左右镜像处理后的b上或灰度矩阵b放在左右镜像处理后的a上）。拼接过后，边缘灰度向量信息会增加为原来的两倍，这时利用问题二中的全局搜索模型用向量相关性的方法进行匹配拼接。拼接出所有行后，将每一行的下半部分矩阵切割放在上半部分的右边，又可增加横向拼接时的边缘信息，然后各行再次利用向量相关性的方法进行横向拼接，最终得到结果图，但是仍然存在较多的碎片不能正确匹配，需要人工干预。

碎纸片的拼接复原 基本思路
此题的关键是要给出一张纸条和另一张纸条怎么才算是『吻合』，定量的吻合条件是什么？

考虑到一张纸被切成两部分，切边两侧边缘的图像应该是很接近的，于是就将『边缘尽可能接近』作为匹配『吻合』的标准。
『边缘』，那就是1个像素宽度的一条呗。
比如1#纸条的右边1像素宽度的数据，分别去和3#纸条的左边1像素宽度的数据、4#纸条的左边1像素宽度的数据去试验
1#：0 0 0 1 1 1 1 0 0
3#：0 0 0 1 1 0 1 0 0
4#：0 1 0 1 0 0 0 0 0
显然是1#和3#之间更接近一些。如何定量呢？
将1#与3#上每一个对应的像素乘起来，再相加，如果是1对着的是1，那么对和有所贡献，如果1对着是0，则没有，加起来的和越大说明吻合的程度越高。
这种对应数相乘，再把每个乘积加起来的操作，叫dot production
比如(x1,x2,x3)和(y1,y2,y3)的dot production=x1y1+x2y2+x3y3
如果写成矩阵的乘法，x要横着写，y要竖着写：
\left[ \begin{matrix} { x }_{ 1 } & { x }_{ 2 } & { x }_{ 3 } \end{matrix} \right] \quad \left[ \begin{matrix} { y }_{ 1 } \\ { y }_{ 2 } \\ { y }_{ 3 } \end{matrix} \right] ={ x }_{ 1 }{ y }_{ 1 }+{ x }_{ 2 }{ y }_{ 2 }+{ x }_{ 3 }{ y }_{ 3 }

1#和3#计算可以得出=3
1#和4#计算可以得出=1
1#和3#的边缘更接近。

那么接下来的思路就很清晰了，用1#纸条的右边1像素宽度的数据去分别和2#、3#、4#...18#左边1像素宽度的数据分别去试，找到dot_production最大的那个，就是『边缘最接近』的了。
不妨把1#纸条的右边缘1像素宽度数据写成R1，j#纸条的左边缘1像素宽度数据写成Lj，
用矩阵乘法的方式写出来就是：
[R1（横着写）][L1（竖着写）,L2（竖着写）,L3（竖着写）...L18（竖着写）] =[u(1,1),u(1,2),u(1,3),..u(1,18)]

找到[u(1,1),u(1,2),...u(1,18)]里面最大的值，就是1#纸条所对应的右边那一条了。
一个一个的试显然很麻烦，恰好矩阵的乘法可以很好的解决这个问题，
把所有纸条右边1像素宽度的数据写作R，第i#纸条的数据就是Ri，所以R是一个每行有1980，有19列的矩阵
把所有纸条右边1像素宽度的数据写作L，第j#纸条的数据就是Lj，要把L矩阵竖着写，所以要做一个transpose操作，就是竖过来。简单的可以写成L'。
R*L'就是我们所需要知道每个『右边』与每个『左边』的吻合度了，一共有19*19个数字。不妨写成U=R*L'
下图就是这个U矩阵，颜色的深浅表示数字的大小。碎纸片的拼接复原