一種形狀規(guī)則碎紙的拼接模型及其仿真

黃永斌

【摘 要】 本文針對形狀規(guī)則的碎紙的拼接問題，提出了一種基于雙三次插值的優(yōu)化模型，并進行了仿真驗證。仿真結(jié)果表示，針對形狀規(guī)則的碎紙拼接問題，本文提出的算法是可行的，可以獲得良好的拼接效果，具有一定的實用價值。

【關(guān)鍵詞】 碎紙拼接 圖像處理 三次插值 優(yōu)化模型

碎紙拼接問題是計算機視覺和模式識別領(lǐng)域內(nèi)的一個熱點問題，主要是通過計算機處理，獲取碎紙片的形狀、顏色等內(nèi)容信息，然后利用這些內(nèi)容信息對碎紙進行自動拼接，恢復(fù)碎紙原始的內(nèi)容。碎紙拼接在情報資料碎片整理、司法技術(shù)鑒定等領(lǐng)域有著很多的應(yīng)用，但大都是人工完成。因此研究碎紙拼接，尤其形狀規(guī)則的碎紙有著重大的實際意義[1]。

1 碎紙拼接問題的分析

對于碎紙拼接問題，無法通過紙片輪廓的提取進行拼接，可以利用的信息主要集中在碎紙的邊緣部分。實現(xiàn)拼接是以尋找各紙片邊緣內(nèi)容間的差異為突破口，選擇合理的方法將紙片中的內(nèi)容完整有效的提取出來。在紙片中的內(nèi)容被提取后，可建立優(yōu)化模型求解拼接方案。

2 數(shù)字圖像處理

獲取紙片信息是將圖像轉(zhuǎn)化為可感知數(shù)據(jù)的過程，需要取樣和量化處理。對圖像進行取樣量化的結(jié)果是圖像被保存為一個實矩陣的形式[2]。一幅圖像各點的像素大小若能用位置的函數(shù)表示，離散取樣后，產(chǎn)生的數(shù)字圖像有m行和n列，則可用以下大小為的緊湊矩陣表示數(shù)字圖像

，

也可用傳統(tǒng)矩陣如下表示為A，而且顯然有

。

灰度數(shù)字圖像每個像素只有一個采樣顏色，從黑色到白色的灰度有256級灰度。將需要拼接的N張碎紙掃描彩色為數(shù)字圖像。將所有彩色數(shù)字圖像轉(zhuǎn)化為灰色數(shù)字圖像，保存為矩陣的形式，其中每個元素為0-256的整數(shù)。

用表示第k塊碎紙，碎紙片量化后得到矩陣，考慮下面碎片拼接的實現(xiàn)，定義n個列向量表示第1列至第n列，則量化所得矩陣為

3 碎紙邊緣信息的提取

定義域是平面上的一個矩形區(qū)域，在x軸和y軸上分別取等分

由此可以定義出上述區(qū)域上的分割矩形的大小為，區(qū)域被分成個矩形。對其中的任意一個有標(biāo)記

此區(qū)域內(nèi)的雙三次插值函數(shù)定義為[3]：

在利用灰度矩陣進行拼接時，若只取邊界上一列來提取圖像的邊緣信息，會因邊緣像素中存在大量噪聲而不能很好刻畫圖片的邊界信息，因此我們?nèi)〉幕叶染仃囎詈?列記為取的前5列，同樣取最后五列記為。

若的右邊緣和的左邊緣應(yīng)當(dāng)拼接在一起，則令，

由于圖像函數(shù)應(yīng)該具有良好的連續(xù)性和光滑性，即選擇RL任意連續(xù)幾列，所得的插值函數(shù)在某固定位置上的取值應(yīng)大小相當(dāng)，否則的右邊緣和的左邊緣不應(yīng)當(dāng)拼接在一起。從RL第一列開始依次選取連續(xù)6列做插值函數(shù)，則可得5個插值函數(shù)，記為：

利用各個插值函數(shù)分別可得在兩張碎片拼接處的像素值

實際計算中，取拼接處在坐標(biāo)系中的橫坐標(biāo)值為。根據(jù)圖像的連續(xù)性假設(shè)和光滑性假設(shè)，利用上述5個值構(gòu)造拼接的匹配度為：

4 拼接模型的建立

紙片有四個邊緣，可知上下邊緣的拼接方法與作用邊緣的拼接方法應(yīng)該相同，因此建立模型時只需要考慮一行碎紙片的拼接即可，將每行拼接好后再將行與行拼接。同時可知，一般紙張的左右邊緣留白較大，因此根據(jù)留白找出一行的左右邊緣再進行后續(xù)拼接，具體尋找過程不再詳述。

可得模型的目標(biāo)函數(shù)：使一行碎紙拼接后匹配度總和最大。也可得約束條件為：（1）每一行中最后一張碎紙的右邊界不能與其他碎紙的左邊界拼接；（2）每一行中的第一張碎紙的左邊界不能與其他碎紙的右邊界拼接；（3）碎紙的右邊界只能與另一張碎紙的左邊界拼接；（4）除第一張外，任意碎紙的左邊界有且僅有一張碎紙的右邊界與之拼接；除最后一張外，任意碎紙的右邊界有且僅有一張碎紙的左邊界與之拼接；（5）碎紙片整體必須構(gòu)成巡回路線，不能含有子巡回[4]。

令表示碎片的右邊緣與碎片左邊緣的相似度，且設(shè)為0-1變量，表示碎片的右邊緣與碎片左邊緣拼接，則表示不能拼接，則根據(jù)約束目標(biāo)函數(shù)和約束條件可建立碎紙片拼接模型為：

5 算法仿真

算例中有30張圖片，分為三行，每行10張碎紙，處于同一行的已知。圖1為部分原始圖片。

將碎紙片進行編號為1-30，利用Matlab軟件進行圖像處理，分別找出三行散亂圖片的左右邊緣，在同一行內(nèi)計算匹配度矩陣。最后根據(jù)拼接模型，利用Lingo[5]軟件進行編程求解，得到每行的拼接結(jié)果。然后采用同樣的方法將三行拼接。拼接的結(jié)果按照編號表示如表1，以圖片表示則如圖2。為顯示整體拼接效果，圖2將原始圖片的黑白部分進行了反轉(zhuǎn)。

最終的拼接結(jié)果為如圖2所示。

6 結(jié)語

仿真實驗證明，本文提出的基于雙三次插值的優(yōu)化模型是可行的。本文先拼行、再拼列和先定位邊緣碎紙片的方法，可以極大簡化問題的難度。利用LINGO軟件建立模型求解能保證結(jié)果的精確性。本文的模型主要針對形狀規(guī)則的碎紙片的拼接問題，具有一定的普適性，可以進行適當(dāng)推廣，具有一定的實用價值。

參考文獻(xiàn)：

[1]賈海燕.碎紙自動拼接關(guān)鍵技術(shù)研究[D].國防科技大學(xué)碩士論文，2005

[2][美]岡薩雷斯，[美]伍茲.數(shù)字圖像處理（第三版），北京：電子工業(yè)出版社，2010

[3]王會鵬，周利莉，張杰.一種基于區(qū)域的雙三次算法[J].計算機工程，2010，36（19）： 216-218

[4]袁新生，邵大宏. LINGO和Excel在數(shù)學(xué)建模中的應(yīng)用.北京：科學(xué)出版社，2007

[5]謝金星，薛毅.優(yōu)化建模與Lindo/Lingo軟件.北京：清華大學(xué)出版社，2005.