程紅萍

（西安歐亞學院 陜西 西安　710065）

碎紙片的拼接復原模型和算法研究

程紅萍

（西安歐亞學院 陜西 西安710065）

針對碎紙片的拼接復原問題，主要用灰度圖像值進行彈性匹配，根據(jù)圖片灰度圖像值運用對比度調(diào)制法建立評價函數(shù)模型，運用感興趣區(qū)域圖像融合法和對比度調(diào)制法將各圖片與人工干預的圖片進行評價判斷，采用梯度匹配篩選出與人工干預的圖片相吻合的圖像進行融合，最后匹配得到完整的碎紙片序號復原圖片，經(jīng)實例證明，方法有效可行。

碎紙片拼接；灰度圖像值；梯度融合；人工干預

破碎文件的拼接在司法物證復原、歷史文獻修復以及軍事情報獲取等領域都有著重要的應用。傳統(tǒng)上，拼接復原工作需由人工完成，準確率較高，但效率很低。特別是當碎片數(shù)量巨大，人工拼接很難在短時間內(nèi)完成任務。隨著計算機技術的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術，以提高拼接復原效率［1］。文中以2013年全國大學生數(shù)學建模競賽B題為例，通過建立數(shù)學模型和算法，來研究碎紙片拼接復原問題，并針對附件中給出的中、英文各一頁文件的碎片數(shù)據(jù)進行拼接復原，主要對以下問題逐一研究。

問題一：對于給定的來自同一頁印刷文字文件的碎紙機破碎紙片（僅縱切），建立碎紙片拼接復原模型和算法，并針對附件1、附件2給出的中、英文各一頁文件的碎片數(shù)據(jù)進行拼接復原。如果復原過程需要人工干預，寫出干預方式及干預的時間節(jié)點。復原結果以表格形式表達。

問題二：對于碎紙機既縱切又橫切的情形，請設計碎紙片拼接復原模型和算法，并針對附件3、附件4給出的中、英文各一頁文件的碎片數(shù)據(jù)進行拼接復原。如果復原過程需要人工干預，寫出干預方式及干預的時間節(jié)點。復原結果以表格形式表達。

1　問題分析

要求建立碎紙片復原模型和算法，并針對附件1、附件2給出的中、英文各一頁文件的碎紙片（僅縱切）進行拼接復原。根據(jù)碎片形狀的觀察，可運用圖片的灰度圖像值［2］進行模型的求解，首先將19張所切得的文字碎片分為3類：文字左邊殘缺、文字右邊殘缺、文字完整。為此將19張圖片中每一張圖片文字左邊殘缺記為1；文字右邊殘缺記為1；空白處（無文字）記為0，然后用MATLAB軟件得到19張圖片的灰度圖像矩陣，其次用MATLAB軟件將19張圖片灰度圖像值進行預處理［3］，得到各圖片左右邊文字切口0-1化數(shù)據(jù)，然后再根據(jù)文字圖片0-1化數(shù)值建立殘缺文字匹配度模型［3］，運用相關算法將各圖片的灰度圖像值進行彈性匹配，最后由匹配結果拼接復原出附件1和附件2的完整圖片。

問題二要求對附件3、附件4中既縱切又橫切的兩頁（中、英文）的碎紙片數(shù)據(jù)進行拼接復原。相對于問題一、問題二進一步增加了難度，問題一中的碎紙片僅僅是縱切，文字圖像的拼接處理相對較簡單，而問題二中的碎紙片既有縱切又有橫切。文字圖像拼接復原相對復雜，因而不能直接運用問題一的求解方法來求解問題二。為了更好的處理文字圖像，經(jīng)過分析，在問題一的基礎上改變對文字圖像的處理方法。即與問題一一樣考慮圖片的灰度圖像值，運用MATLAB軟件得到附件3、附件4所有圖片灰度圖像值矩陣。首先采取人工干預確定了附件3、附件4第一行和第一列的圖片，然后根據(jù)圖片灰度圖像值運用對比度調(diào)制法建立評價函數(shù)模型，運用相關算法將各圖片與人工干預的圖片進行評價判斷，采用梯度匹配，篩選出與人工干預的圖片灰度值相吻合的圖像進行融合，最后匹配得到完整的附件3、附件4拼接復原圖。

2　模型建立和求解

2.1問題一模型準備

在問題一建立模型前，首先考慮圖片的灰度圖像值，先運用MATLAB軟件得到各個圖片灰度圖像值矩陣，再次運用MATLAB軟件對附件1、附件2文字圖像的灰度圖像值進行預處理，就可以得到圖像邊界殘缺0-1化數(shù)據(jù)，問題一中每一張碎紙片僅是縱切，所以將附件1、附件2中19張所切得的文字碎片分為3類：文字左邊殘缺、文字右邊殘缺、文字完整。為此將19張圖片中每一張圖片文字左邊殘缺記為1；文字右邊殘缺記為1；空白處（無文字）記為0，同時任意兩張圖片相互匹配必須滿足殘缺文字相對吻合，即標記1與標記1對應，標記0與標記0對應。

問題一求解流程圖如圖1所示。

圖1　問題一求解流程圖

2.1.1附件1模型建立與求解

根據(jù)附件1，運用MATLAB軟件對文字圖像的灰度圖像值進行處理后得到相關數(shù)據(jù)，相關數(shù)據(jù)如表1所示：

表1　文字圖像0-1化的表格

根據(jù)表1中殘缺文字的標記數(shù)據(jù)建立殘缺文字匹配度模型：

其中dsi表示文字左邊殘缺，dsi表示文字右邊殘缺，i表示文字總行數(shù)。

為了求解模型，運用灰度圖像值進行彈性匹配法［4］求解得附件1碎紙片序號復原后的表格（見表2），用Matlab復原文字，復原文字圖片（略）。

表2　附件1文字碎片復原后的表格

2.1.2附件2模型建立與求解

根據(jù)對附件2中字母圖像的灰度圖像值處理，得到相關數(shù)據(jù)，數(shù)據(jù)表格同表 1，用 Matlab對文字轉換，得到具體表格，根據(jù)表格建立與2.1.1中相同的匹配度模型：

其中dvi表示字符左邊殘缺，dvi表示字符右邊殘缺，i表示字符總行數(shù)。

同理運用灰度圖像值進行彈性匹配求解得附件2文字碎片序號復原后的表格，見表3，用Matlab復原文字，復原字母圖片（略）。

表3　附件2文字碎片復原后的表格

2.2問題二模型準備

在問題二建立模型前，由于附件3、附件4的圖片既有橫切又有縱切，圖片預處理相對復雜，首先考慮圖片的灰度圖像值，介入人工干預首先運用MATLAB軟件得到各個圖片灰度圖像值矩陣，拼接處附件3、附件4第一行與第一列的圖片，然后建立模型進行圖片的拼接復原。

其中問題二求解流程見圖2。

2.2.1附件3模型建立與求解

運用Matlab將附件3中圖片導入程序，并提取圖片各邊灰度值，再根據(jù)其灰度值進行圖像融合匹配［5］。

為了拼接復原附件3的圖片，采用圖像梯度融合。步驟流程圖如圖3所示。

圖2　問題二求解流程圖

圖3　灰度融合算法流程

為了拼接復原附件3、附件4的圖片，文中采用了感興趣區(qū)域圖像融合方法和對比度調(diào)制法［6］?；诟信d趣區(qū)域融合算法可以看作是一種適應的加權平均法。分割出一幅圖片的感興趣區(qū)域，即將一幅圖片的感興趣區(qū)域嵌入到另一幅圖片。Ii（i，j）和Ij（i，j）為待融合的圖像，ROI為像Ii（i，j）分割出的感興趣區(qū)，則融合圖像I（i，j）可表示為：

對比度調(diào)制法就是利用一幅圖包含的細節(jié)信息提取其對比度，調(diào)制另一幅圖像的灰色分布，實現(xiàn)圖像融合。步驟如下：

1）圖像Ii（i，j）的局部對比度提?。?/p>

其中：～Ii（i，j）是Ii（i，j）的低通濾波圖像；CL（i，j）是局部對比度。

2）局部對比度歸一化：

3）圖像調(diào)制：將歸一化對比度 CLN（i，j）與另一副圖像相乘得到融合圖像：

4）映射量化：得到融合圖像后重新量化，使之灰度范圍與顯示設備動態(tài)范圍R（對于一般顯示器為0～255，即R=255）相匹配，得到最后的融合圖像為：

而基于像素灰度級的方法：一般是取出待匹配圖像的重疊部分有特征的像素，通過評價函數(shù)給出待匹配圖像與基準圖像之間的相似度值。常用的評價函數(shù)有互相關函數(shù)。對于待配準圖像與基準圖像之間的互相關 （Cross-correlation）函數(shù)為：

如果兩幅圖像完全匹配則互相關系數(shù)達到最大值。還有利用兩幅圖像灰度差值平方和最小的評價函數(shù)來進行配準。函數(shù)如下：E=Σ［I（x，y）-I′（x′，y′）］2，使得取得最小值的像素區(qū)域位置，即為最佳匹配位置。根據(jù)最小差平方和函數(shù)。更為簡便的方法就是取像素點絕對差值和最小即：E=Σ|I（x，y）-I′（x′，y′）|

首先對附件3的所有碎紙片進行人工干預，見圖4。

圖4　人工干預后第一行的圖

將圖3、圖4兩張圖片用Matlab進行組合后，即人工干預初步復原圖片。由圖片可以得到我們?nèi)斯じ深A后的圖片，由于工作量大，不能全部通過人工干預得到拼接復原圖，所以為了在人工復原圖的基礎上拼接出完整的復原圖，運用圖片相鄰邊的灰度值進行梯度融合，并在圖5的基礎上進行逐個圖片梯度融合，最終復原圖片由各個部分圖片進行梯度融合所得，對此在人工干預確定的圖片基礎上對其鄰邊圖片進行灰度值梯度匹配。建立了部分梯度匹配模型。

圖5　灰度值對比圖

根據(jù)人工干預后的已知圖片，然后在灰度值數(shù)據(jù)里提取圖片灰度值與灰度值進行對比，可以得到其中必定有與相符合的圖片灰度值。就可以判斷此圖與圖片相鄰。以此類推，對附件3里面所有圖片逐個篩選進行灰度值匹配，最終得到附件3復原圖片。為了更好的表示相鄰兩邊灰色度匹配程度，選取了圖片1和圖片2的灰色度進行匹配對比。如圖5所示。

由圖5可以看出圖片1右邊與圖片2左邊的灰度值幾乎重合，所以可以確定圖片1右邊與圖片2左邊是相鄰邊，從而可以得到圖片圖片1與圖片2是相鄰關系。

根據(jù)灰度值的相互匹配，在本文的模型求解中，在人工干預得到復原圖片的基礎上，將附件中的圖片導入Matlab軟件中得到圖片的各邊灰度值，從所有灰度值數(shù)據(jù)中篩選與人工干預得到的圖片相匹配的灰度值。以此遞推，不斷在得到已知圖片的基礎上進行文字圖片梯度融合，從而得到拼接復原圖。復原步驟部分圖如圖6所示。

圖6　復原步驟部分圖

由圖6可以看出，圖中方框所圍區(qū)域就是在圖5的基礎上經(jīng)過灰度值匹配后在所有圖片中篩選出的匹配圖片，以此類推，經(jīng)過多次梯度融合，最終得到了附件3的文字拼接復原圖，碎紙片復原后年表格見表4，用Matlab復原圖片，復原圖片（略）。

2.2.2附件4模型建立與求解

由2.2.1中對附件3的文字圖片復原求解可知，首先通過人工干預得到初步復原圖片的第一行與第一列，然后使用灰度值匹配法對圖片進行篩選，使得圖片梯度融合，最后拼接處文字復原圖，同理運用此方法對附件4進行梯度融合求解，步驟同2.2.1，得附件4碎片序號復原后的表格見表5，用Matlab復原英文文字圖片，復原英文印刷文字圖片（圖略）。

表4　附件3拼接復原后表格

表5　附件4拼接復原后表格

3　結束語

本文在求解過程中繪制了流程圖，思路清晰，有利于模型的求解，且在求解過程中運用了灰色度彈性匹配，評價函數(shù)等算法，計算精確。在問題二的求解過程中，進行了人工干預對部分圖片進行復原，進而在部分復原圖片的基礎上匹配得到完整復原圖片，使建模過程簡單化，避免了繁瑣的運算。但是在實際生活中，可能采取人工干預會顯得麻煩，不利于模型的推廣和實際的應用。

［1］2013年全國大學生數(shù)學建模競賽題目 ［EB/OL］（2013-09-11）http：//www.mcm.edu.cn.

［2］百度百科.灰度圖像 ［BE/OL］（2013-09-14）http：//baike. baidu.com/view/1549178.html.

［3］何正風.MATLAB概率與數(shù)理統(tǒng)計分析［M］.北京：機械工業(yè)出版社，2012，322-354.

［4］周倉義，赫孝良.數(shù)學建模實驗［M］.西安：西安交通大學出版社，1999.

［5］知網(wǎng)空間.彈性匹配 ［BE/OL］（2013-09-14）http：//wiki.cnki. com.cn/HotWord/1041106.htm.

［6］王娟，師軍.圖像拼接技術綜述［J］.計算機應用研究，2006，25（7）：1940-1947.

［7］王俊杰.圖像配準的方法［BE/OL］（2013-09-14）http：//www. docin.com/p-211110983.

［8］樊啟斌，焦雨領.變分正則化圖像復原模型與算法綜述［J］.數(shù)學進展，2012，10（5）：531-542.

Scraps of paper splicing model and algorithm research

CHENG Hong-ping
（Xi'an Eurasia University，Xi'an 710065，China）

As for the stitching-recovering of scraps of paper，gray image value is flexibly matched to establish the evaluation function model using contrast modulation method based on image grayscale image values，then using hot spot image fusion method and contrast modulation method to compare each picture with human intervention pictures，using a gradient matching to filter out human intervention consistent picture for image fusion，the last serial number full-recovered picture of scraps of paper is finished.Examples prove that the method is effective and feasible.

scraps of paper recovery；gray image value；gradient fusion；human intervention

TN6

A

1674－6236（2016）06-0081-04

2015-04-18稿件編號：201504192

陜西省教育廳2014年科研課題（14JK2061）

程紅萍（1971—），女，陜西大荔人，碩士，講師。研究方向：數(shù)學建模與優(yōu)化算法。