碎紙片的拼接復(fù)原數(shù)學(xué)模型的構(gòu)建

畢楷明

（東北大學(xué)理學(xué)院，沈陽(yáng)110819）

1 模型一

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

利用VC++使用了Windows.H頭文件并調(diào)用RGB等結(jié)構(gòu)定義獲得不同像素點(diǎn)的g值[1]，生成了多個(gè)灰度矩陣。

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

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

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

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

于是這些列向量分別與左一位置碎片最右側(cè)g值列向量對(duì)應(yīng)位置相減得：G 差

再對(duì)每個(gè)G差左一，No內(nèi)的元素對(duì)每?jī)蓚€(gè)可能相鄰的邊緣灰度向量求歐式距離，量化兩個(gè)碎片間的像素差異：

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

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

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

2 模型二

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

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

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

其中1≤j≤72

在分組的過程中，文章采取隨機(jī)抽一個(gè)碎片作為本體提取信息（灰度列向量分布），再?gòu)氖Ｓ嗟臉颖局姓业脚c它屬于同一組的其他碎片，然后將這些碎片分為一組，再抽取下一個(gè)本體。為了方便描述所提取的灰度列向量分布，定義連續(xù)空白長(zhǎng)度l白為向量中灰度值恒為255的連續(xù)的像素點(diǎn)的個(gè)數(shù)，再定義連續(xù)灰體長(zhǎng)度l灰為向量中灰度值恒不為255的連續(xù)的像素點(diǎn)的個(gè)數(shù)。

由于列向量的像素點(diǎn)個(gè)數(shù)為180個(gè)，故有：

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

利用VC++語言實(shí)現(xiàn)上述算法，得出二維空間上碎片的排布。

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

3 模型三

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

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

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

從最小灰度值到最大灰度值遍歷t，當(dāng)t使得值：

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

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

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

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

利用VC++語言進(jìn)行計(jì)算求得閾值h=210。

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

利用二值化的結(jié)果將碎紙片進(jìn)行邊緣匹配，因?yàn)檫吘壧幾帜感畔⑷魹椴煌暾?，則相鄰碎片均含有連續(xù)的字母信息，即二值化后相鄰碎紙片的邊緣部分將顯示出連續(xù)的規(guī)律，由于種種因素二值化閾值的選取可能會(huì)使極小部分字母的像素點(diǎn)不能完全取值為255，即被作為空白背景處理，故實(shí)際中計(jì)算吻合概率時(shí)無法達(dá)到百分之百。由于經(jīng)此處理的像素點(diǎn)極為少數(shù)，則在進(jìn)行匹配過程中若有其中一個(gè)字母或符號(hào)將不能匹配在一起，此時(shí)空白背景區(qū)域也會(huì)受到影響無法連接在一起，如此一來只要不匹配的碎紙片拼接在一起時(shí)的吻合概率將會(huì)加倍降低，故在碎紙片邊緣處字母吻合包括白色背景間的吻合與字母間的吻合，概率達(dá)到百分之九十五以上則說明匹配成功。

符號(hào)說明

[1]李琳娜.Visual C++開發(fā)技術(shù)大全[M].北京：清華大學(xué)出版社，2010.

[2]樓順天.MATLAB 7.x程序設(shè)計(jì)語言[M].西安：西安電子科技大學(xué)出版社，2007.

[3]李航.統(tǒng)計(jì)學(xué)習(xí)方法[M].北京：清華大學(xué)出版社，2012.

[4]盤梅森.榮求生SOFM神經(jīng)網(wǎng)絡(luò)的圖像融合的二值化方法[M].2007：1-6.