利用向量范数解决简单的碎片拼接

【摘要】碎片在生活当中是很常见的事物，在现实生活中许多完整的物品如果处理不当很容易成为碎片。因此，碎片的复原在人们的日常生活中具有极其重要的意义，尤其在司法物证复原、历史文献修复以及军事情报获取等领域都起到了关键的作用。本文旨在，从利用数学思想，将碎片进行模型化，引入向量范数进行数学建模，并利用计算机使碎片得到自动复原。

【关键词】碎片复原 模型 向量范数

【中图分类号】G64 【文献标识码】A 【文章编号】2095-3089（2014）09-0252-01

由于碎片拼接意义的重要性，设计一个合理的拼接算法是有必要的，本文主要考虑的纸片的拼接复原，为了简化问题，假设所有的碎片的边缘都是整齐的， 碎片上的文字相对于碎片边缘都是平行或垂直的，所有碎片上的像素点都是可识别的，并且都能识别正确，文字的規格是一样的，并且忽略所有匹配过程中可能出现的小概率事件。

碎片的拼接实际上就是碎片边缘拼接，只要两个碎片的拆分的字全部吻合，则可认为，这两个碎片是可以拼接的。这对人来说是非常简单的，可以对于计算机来说却是不可能完成的事，计算机没有人脑智能。这就需要找到一种计算机能处理的方法，在计算机中所有的文字图片都是由一个一个很小的像素点排成的矩阵构成的，而每个像素点都有一个灰度值，而对于普通的word文字来说，我们可以认为它只有黑白两种颜色，为方便起见我们认为黑的程度是一样的（即灰度值一样），而对于计算机来说，矩阵是可以识别、储存并计算的。因此，我们可以把“白”赋值为0，“黑”赋值为1。通过这种方法可以将一个碎片变成一个由0，1构成的数学矩阵。

如图是“捺”的一部分像素矩阵

图（一）

此时判断两个碎片是否吻合，只需判断两个矩阵是否吻合。

通过肉眼观察碎片的边缘断点可以发现如果这一个碎片的一点是白（黑）色，则其相吻合的碎片的相邻一点“大多”也是白（黑）色，即“像素的差异性”小。转换到矩阵来说就是两个矩阵所对应位置上的元素相同。虽然有时两个碎片的分割的边缘断裂之前是一“撇”或一“捺”。肉眼看上去，可能感觉这个碎片的一点的黑色了，另一碎片的相邻点为白色。但是肉眼看上去的一点是由一个像素点的小矩阵构成。则对像素点而言，其“大多数”相邻点的颜色还是相同的。当然，吻合相邻两像素点有不同的情况（也可能出现极端情况，即两碎片其中的一个边缘上恰好为一个完整的文字，但是以这种情况断裂的碎片概率很小），但能够吻合的两碎片所对应的矩阵的边缘向量相似度一定很大。如图（一）如果从第6列和第7列将图像分开，可以看出只有第1行和第5行的第6，7号元素不同，其他都相同。即可构造函数表示两矩阵边缘向量的差异来判断。两矩阵是否吻合，只需看函数值即可。差异越小，吻合的可能性越大。差异化最小的，就正好可以匹配成功。

因此，建模过程如下：

第一步，将碎片编号记为A（i）。

第二步，利用matlab量化碎片为矩阵，并提取矩阵的左右向量记为A（i1），A（i2）。

A（i1）为（a（i）（1），a（i）（2），······，a（i）（n））

A（i2）为（b（i）（1），b（i）（2），······，b（i）（n））

第三步，通过向量的2范式定义差异函数：

f（A（il），A（j2））=■

第四步，比较向量间的差异值，差异值越小，则两矩阵越有可能匹配成功。

这样利用以上算法，很容易在计算机上实现纸片的碎片拼接工作，而且此方法简单易实现，故可以利用向量的2范数进行碎片拼接。

作者简介：

李琦（1992-），男，内蒙古呼和浩特人，现内蒙古大学数学科学学院在校本科生。