利用向量范數解決簡單的碎片拼接

【摘要】碎片在生活當中是很常見的事物，在現實生活中許多完整的物品如果處理不當很容易成為碎片。因此，碎片的復原在人們的日常生活中具有極其重要的意義，尤其在司法物證復原、歷史文獻修復以及軍事情報獲取等領域都起到了關鍵的作用。本文旨在，從利用數學思想，將碎片進行模型化，引入向量范數進行數學建模，并利用計算機使碎片得到自動復原。

【關鍵詞】碎片復原 模型 向量范數

【中圖分類號】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-），男，內蒙古呼和浩特人，現內蒙古大學數學科學學院在校本科生。