碎紙片的拼接復原數學模型的構建

畢楷明

（東北大學理學院，沈陽110819）

1 模型一

考慮以為空間拼接情況，為了獲取拼接圖像所必須的數據，文章以像素為單位離散所得碎片：

利用VC++使用了Windows.H頭文件并調用RGB等結構定義獲得不同像素點的g值[1]，生成了多個灰度矩陣。

由于本題主要研究碎片的拼接，故只需考慮碎片的邊緣部分，故分別提取全部碎片的最左側和最右側的g值列向量：

文章分別找出其中最左側g值列向量的值全為255（即像素全白）的和最右側g值列向量的值全為255的兩個碎片，于是左側g值全為255的碎片對應左一位置，同理右側g值全為255的碎片對應左一位置。再考慮剩余的碎片（本文中考慮18個碎片）的對號入座問題，使最左側碎片分別與其他碎片的最左側灰度g值列向量進行相同y值下作差，得到不同碎片的G差。

先求出左一位置碎片最右側g值列向量：

再找出其他碎片的最左側g值列向量：

于是這些列向量分別與左一位置碎片最右側g值列向量對應位置相減得：G 差

再對每個G差左一，No內的元素對每兩個可能相鄰的邊緣灰度向量求歐式距離，量化兩個碎片間的像素差異：

對于剩余的碎片來說，此平方差值越小，它的邊緣像素與左一位置碎片的相似度越高，也就能說明這兩個碎片越有可能是相接的。

帶入數據求出余下碎片與左一位置碎片的灰度差向量平方和值 S左一，No。

利用matlab軟件對其進行描點[2]，所得圖像可得出該碎片左一位置的灰度差向量平方和值S左一，No最小，也就意味著該碎片與左一碎片的相接邊緣像素灰度差異最小，于是確定其為左二位置碎片。同理可以依次類推，得到一維空間上圖像的拼接結果。

2 模型二

考慮二維空間上拼接情況，依然以像素為單位離散所得碎片，并提取每個像素點的灰度，生成灰度矩陣。

其中 1≤i≤180，1≤j≤72

對這209個矩陣進行按行分組，由于同一橫行碎片的灰度橫坐標i之間具有一定的一致性，而同一橫行的灰度縱坐標j之間則有較大的差異性，即同一橫行的碎片字與字之間的行距的位置相同。為把同一橫行的元素分成一組，故文章考慮通過求平均值的方法將180×72的矩陣，轉為180×1的列向量，以便于找出不同碎片之間的共性，利用同一橫行的一致性把碎片分成11組。

其中1≤j≤72

在分組的過程中，文章采取隨機抽一個碎片作為本體提取信息（灰度列向量分布），再從剩余的樣本中找到與它屬于同一組的其他碎片，然后將這些碎片分為一組，再抽取下一個本體。為了方便描述所提取的灰度列向量分布，定義連續空白長度l白為向量中灰度值恒為255的連續的像素點的個數，再定義連續灰體長度l灰為向量中灰度值恒不為255的連續的像素點的個數。

由于列向量的像素點個數為180個，故有：

并且連續空白與連續空白之間是相交叉的，于是利用上述方法提取的信息可以轉換為一個長度向量L，向量里的每個元素都是l白和l灰，且他們是相間的。同樣地提取除本體以外的198個碎片的長度向量LNo，將這198個長度向量分別與11個本體做匹配，取向量間歐式距離最小的本體碎片為匹配成功。

利用VC++語言實現上述算法，得出二維空間上碎片的排布。

現問題已被簡化為一維空間的碎片拼接問題，按照模型一的方法可以完成拼接，但由于圖片的隨機性，很可能會由于段落的空白造成實驗結果的失誤，所以，在設計算法中，將每張圖片的平均灰度值作為基準對照本，然后進行對其他圖片的灰度平均值遍歷，計算出來的數據，在設定的置信區間，為從遇到新灰度開始，到另一種類型灰度的結束，比如從一個小于255灰度255結束，為通過可以拼合的圖像相應的且邊緣的差值均值，從而獲得一個相對合理的誤差限，從而完成二維空間上的碎片拼接。

3 模型三

利用二值化方法將碎紙片中信息轉化為灰度值僅有黑白二值的圖像，并將匹示，概論達到百分之九十五則視為匹配成功[4]。

基于已知碎紙片具體的灰度值可利用Otsu法實現閾值的選取。任取其中一張，計算該組的閾值。再利用統計學方法得到二值化后邊緣處的吻合概率對碎紙片進行匹配，依次將每組碎紙片完成橫向匹配。

任取碎片中1組，將整組中所有字母作為目標，空白作為背景，記t為目標與背景的分割閾值，目標像素占所在組總像素比例為?0，平均灰度值為μ0，空白背景像素數占總組比例為?1，平均灰度為μ1。則總組的總平均灰度為

從最小灰度值到最大灰度值遍歷t，當t使得值：

最大時t即為分割的最佳閾值。該式實際是類間方差值，閾值t分割出的目標和背景兩部分構成整組碎紙片。因方差是灰度分布均勻性的一種度量，方差值越大說明碎紙片匹配的兩部分差別越大，當部分目標點錯分為背景或部分背景點錯分為目標點都會導致兩部分差別變小，因此使類間方差最大的分割意味著吻合概率最小。

記f（i，j）為N×M紙片（i，j）點處的灰度值，灰度級為μ，不妨假設f（i，j）取值[0，m-1]。記p（k）為灰度值為k的頻率，則有

假設用灰度值t為閾值分割出的目標與背景分別為：{f（i，j）≤t}和{f（i，j）＞t}，于是目標部分比例為：

求得該組碎紙片的最佳閾值g的公式為：

利用VC++語言進行計算求得閾值h=210。

碎紙片中字母本身灰度值低于閾值210的令為0，灰度值高于閾值210的令為1，即

利用二值化的結果將碎紙片進行邊緣匹配，因為邊緣處字母信息若為不完整的，則相鄰碎片均含有連續的字母信息，即二值化后相鄰碎紙片的邊緣部分將顯示出連續的規律，由于種種因素二值化閾值的選取可能會使極小部分字母的像素點不能完全取值為255，即被作為空白背景處理，故實際中計算吻合概率時無法達到百分之百。由于經此處理的像素點極為少數，則在進行匹配過程中若有其中一個字母或符號將不能匹配在一起，此時空白背景區域也會受到影響無法連接在一起，如此一來只要不匹配的碎紙片拼接在一起時的吻合概率將會加倍降低，故在碎紙片邊緣處字母吻合包括白色背景間的吻合與字母間的吻合，概率達到百分之九十五以上則說明匹配成功。

符號說明

[1]李琳娜.Visual C++開發技術大全[M].北京：清華大學出版社，2010.

[2]樓順天.MATLAB 7.x程序設計語言[M].西安：西安電子科技大學出版社，2007.

[3]李航.統計學習方法[M].北京：清華大學出版社，2012.

[4]盤梅森.榮求生SOFM神經網絡的圖像融合的二值化方法[M].2007：1-6.