碎紙片的拼接復(fù)原模型和算法研究

程紅萍

（西安歐亞學(xué)院 陜西 西安　710065）

碎紙片的拼接復(fù)原模型和算法研究

程紅萍

（西安歐亞學(xué)院 陜西 西安710065）

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

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

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

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

問(wèn)題二：對(duì)于碎紙機(jī)既縱切又橫切的情形，請(qǐng)?jiān)O(shè)計(jì)碎紙片拼接復(fù)原模型和算法，并針對(duì)附件3、附件4給出的中、英文各一頁(yè)文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。如果復(fù)原過(guò)程需要人工干預(yù)，寫出干預(yù)方式及干預(yù)的時(shí)間節(jié)點(diǎn)。復(fù)原結(jié)果以表格形式表達(dá)。

1　問(wèn)題分析

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

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

2　模型建立和求解

2.1問(wèn)題一模型準(zhǔn)備

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

問(wèn)題一求解流程圖如圖1所示。

圖1　問(wèn)題一求解流程圖

2.1.1附件1模型建立與求解

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

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

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

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

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

表2　附件1文字碎片復(fù)原后的表格

2.1.2附件2模型建立與求解

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

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

同理運(yùn)用灰度圖像值進(jìn)行彈性匹配求解得附件2文字碎片序號(hào)復(fù)原后的表格，見(jiàn)表3，用Matlab復(fù)原文字，復(fù)原字母圖片（略）。

表3　附件2文字碎片復(fù)原后的表格

2.2問(wèn)題二模型準(zhǔn)備

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

其中問(wèn)題二求解流程見(jiàn)圖2。

2.2.1附件3模型建立與求解

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

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

圖2　問(wèn)題二求解流程圖

圖3　灰度融合算法流程

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

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

1）圖像Ii（i，j）的局部對(duì)比度提取：

其中：～I(xiàn)i（i，j）是Ii（i，j）的低通濾波圖像；CL（i，j）是局部對(duì)比度。

2）局部對(duì)比度歸一化：

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

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

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

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

首先對(duì)附件3的所有碎紙片進(jìn)行人工干預(yù)，見(jiàn)圖4。

圖4　人工干預(yù)后第一行的圖

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

圖5　灰度值對(duì)比圖

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

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

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

圖6　復(fù)原步驟部分圖

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

2.2.2附件4模型建立與求解

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

表4　附件3拼接復(fù)原后表格

表5　附件4拼接復(fù)原后表格

3　結(jié)束語(yǔ)

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

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

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

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

［4］周倉(cāng)義，赫孝良.數(shù)學(xué)建模實(shí)驗(yàn)［M］.西安：西安交通大學(xué)出版社，1999.

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

［6］王娟，師軍.圖像拼接技術(shù)綜述［J］.計(jì)算機(jī)應(yīng)用研究，2006，25（7）：1940-1947.

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

［8］樊啟斌，焦雨領(lǐng).變分正則化圖像復(fù)原模型與算法綜述［J］.數(shù)學(xué)進(jìn)展，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稿件編號(hào)：201504192

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

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