利用向量范數(shù)解決簡(jiǎn)單的碎片拼接

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

【關(guān)鍵詞】碎片復(fù)原 模型 向量范數(shù)

【中圖分類號(hào)】G64 【文獻(xiàn)標(biāo)識(shí)碼】A 【文章編號(hào)】2095-3089（2014）09-0252-01

由于碎片拼接意義的重要性，設(shè)計(jì)一個(gè)合理的拼接算法是有必要的，本文主要考慮的紙片的拼接復(fù)原，為了簡(jiǎn)化問題，假設(shè)所有的碎片的邊緣都是整齊的， 碎片上的文字相對(duì)于碎片邊緣都是平行或垂直的，所有碎片上的像素點(diǎn)都是可識(shí)別的，并且都能識(shí)別正確，文字的規(guī)格是一樣的，并且忽略所有匹配過程中可能出現(xiàn)的小概率事件。

碎片的拼接實(shí)際上就是碎片邊緣拼接，只要兩個(gè)碎片的拆分的字全部吻合，則可認(rèn)為，這兩個(gè)碎片是可以拼接的。這對(duì)人來說是非常簡(jiǎn)單的，可以對(duì)于計(jì)算機(jī)來說卻是不可能完成的事，計(jì)算機(jī)沒有人腦智能。這就需要找到一種計(jì)算機(jī)能處理的方法，在計(jì)算機(jī)中所有的文字圖片都是由一個(gè)一個(gè)很小的像素點(diǎn)排成的矩陣構(gòu)成的，而每個(gè)像素點(diǎn)都有一個(gè)灰度值，而對(duì)于普通的word文字來說，我們可以認(rèn)為它只有黑白兩種顏色，為方便起見我們認(rèn)為黑的程度是一樣的（即灰度值一樣），而對(duì)于計(jì)算機(jī)來說，矩陣是可以識(shí)別、儲(chǔ)存并計(jì)算的。因此，我們可以把“白”賦值為0，“黑”賦值為1。通過這種方法可以將一個(gè)碎片變成一個(gè)由0，1構(gòu)成的數(shù)學(xué)矩陣。

如圖是“捺”的一部分像素矩陣

圖（一）

此時(shí)判斷兩個(gè)碎片是否吻合，只需判斷兩個(gè)矩陣是否吻合。

通過肉眼觀察碎片的邊緣斷點(diǎn)可以發(fā)現(xiàn)如果這一個(gè)碎片的一點(diǎn)是白（黑）色，則其相吻合的碎片的相鄰一點(diǎn)“大多”也是白（黑）色，即“像素的差異性”小。轉(zhuǎn)換到矩陣來說就是兩個(gè)矩陣所對(duì)應(yīng)位置上的元素相同。雖然有時(shí)兩個(gè)碎片的分割的邊緣斷裂之前是一“撇”或一“捺”。肉眼看上去，可能感覺這個(gè)碎片的一點(diǎn)的黑色了，另一碎片的相鄰點(diǎn)為白色。但是肉眼看上去的一點(diǎn)是由一個(gè)像素點(diǎn)的小矩陣構(gòu)成。則對(duì)像素點(diǎn)而言，其“大多數(shù)”相鄰點(diǎn)的顏色還是相同的。當(dāng)然，吻合相鄰兩像素點(diǎn)有不同的情況（也可能出現(xiàn)極端情況，即兩碎片其中的一個(gè)邊緣上恰好為一個(gè)完整的文字，但是以這種情況斷裂的碎片概率很?。?，但能夠吻合的兩碎片所對(duì)應(yīng)的矩陣的邊緣向量相似度一定很大。如圖（一）如果從第6列和第7列將圖像分開，可以看出只有第1行和第5行的第6，7號(hào)元素不同，其他都相同。即可構(gòu)造函數(shù)表示兩矩陣邊緣向量的差異來判斷。兩矩陣是否吻合，只需看函數(shù)值即可。差異越小，吻合的可能性越大。差異化最小的，就正好可以匹配成功。

因此，建模過程如下：

第一步，將碎片編號(hào)記為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范式定義差異函數(shù)：

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

第四步，比較向量間的差異值，差異值越小，則兩矩陣越有可能匹配成功。

這樣利用以上算法，很容易在計(jì)算機(jī)上實(shí)現(xiàn)紙片的碎片拼接工作，而且此方法簡(jiǎn)單易實(shí)現(xiàn)，故可以利用向量的2范數(shù)進(jìn)行碎片拼接。

作者簡(jiǎn)介：

李琦（1992-），男，內(nèi)蒙古呼和浩特人，現(xiàn)內(nèi)蒙古大學(xué)數(shù)學(xué)科學(xué)學(xué)院在校本科生。