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

黃永斌

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

【關鍵詞】 碎紙拼接 圖像處理 三次插值 優化模型

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

1 碎紙拼接問題的分析

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

2 數字圖像處理

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

，

也可用傳統矩陣如下表示為A，而且顯然有

。

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

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

3 碎紙邊緣信息的提取

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

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

此區域內的雙三次插值函數定義為[3]：

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

若的右邊緣和的左邊緣應當拼接在一起，則令，

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

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

實際計算中，取拼接處在坐標系中的橫坐標值為。根據圖像的連續性假設和光滑性假設，利用上述5個值構造拼接的匹配度為：

4 拼接模型的建立

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

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

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

5 算法仿真

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

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

最終的拼接結果為如圖2所示。

6 結語

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

參考文獻：

[1]賈海燕.碎紙自動拼接關鍵技術研究[D].國防科技大學碩士論文，2005

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

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

[4]袁新生，邵大宏. LINGO和Excel在數學建模中的應用.北京：科學出版社，2007

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