單面英文碎紙片的拼接復原及算法實現(xiàn)

金明婭，孫丹蕾，趙艷，竇霽虹

(西北大學數學學院，陜西西安710127)

摘要：先對碎片文件的邊緣輪廓色彩灰度值及所包含內容的格式等進行特征分析，再通過定義差異度指數、高度差建立雙目標0-1規(guī)劃模型，運用聚類分析、MATLAB搜索算法和人工干預等相結合，實現(xiàn)單面文件既被橫切也被縱切碎紙片的拼接復原。

關鍵詞：差異度指數；0-1規(guī)劃；MATLAB軟件；聚類分析；高度差

中圖分類號：O242

文獻標識碼：A

文章編號：1004-602X(2015)01-0014-05

收稿日期：2014-11-14

作者簡介：金明婭(1993—)，女，陜西安康人，西北大學數學學院2011級本科生。

Abstract：First,this article analyzed the characteristics about the color grey value on the edge of the fragment file outline and the format of the content contained.Then we defined difference index, height difference and established the double objective 0-1 programming model.At the same time,we used the cluster analysis,MATLAB search algorithm and artificial intervention to achieve single file which transverse and longitudinal cut into a scrap of paper splicing recovery.

1問題分析

破碎文件的拼接在司法物證復原、歷史文獻修復以及軍事情報獲取等領域都有著重要的應用。隨著計算機技術的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術[1]，來提高拼接復原效率。

本文以2013年全國大學生數學建模競賽[2]B題為例，研究單面英文文件既被橫切也被縱切的碎紙片的拼接復原問題。

要對建模B題附件4中的碎紙片進行拼接復原，需建立碎紙片拼接復原模型和算法。由于209塊英文碎片都有左側、右側和上側、下側，每塊碎片邊緣灰度已知，需要同時考慮每塊碎片左右側與其他碎片的差異以及上下側與其他碎片的差異，通過該差異值可定義兩個差異度指數，得到雙目標0-1規(guī)劃模型，進而找到碎片的復原順序。

但由于決策變量較復雜，這種模型不易求解，因而提出改進模型：先定義高度差Hij，運用聚類分析，給定高度差閾值，按照高度不同將所有碎片分為23類，并建立雙目標0-1規(guī)劃模型。結合MATLAB編程和人工干預，將23類碎片處理為11行碎片，再對碎片縱向復原，得到英文復原序號，利用MATLAB編程畫出復原圖片。最后人工檢驗英文復原圖片中無明顯語法、詞語和單詞錯誤，證明復原圖片正確。

2單面英文碎紙片拼接復原初步模型

2.1　提取信息：差異度指數

我們用差異度指數來衡量任意塊碎片右側邊緣與任意塊碎片左側邊緣差異及任意塊碎片下側邊緣與任意塊碎片上側邊緣的差異。定義差異度指數Lij和Uij：Lij表示第i塊碎片右側和第j塊碎片左側的差異度，為第i塊碎片右側與第j塊碎片左側的對應灰度值之差的絕對值的累和。Uij表示第i塊碎片下側和第j塊碎片上側的差異度，為第i塊碎片下側與第j塊碎片上側的對應灰度值之差的絕對值的累和。

公式如下：

2.2　英文碎紙片拼接復原模型

其中：αij=0時，表示第i張碎片右側和第j張碎片左側的不相連；αij=1時，表示第i張碎片右側和第j張碎片左側的相連；βij=0時，表示第i張碎片下側和第j張碎片上側的不相連；βij=1時，表示第i張碎片下側和第j張碎片上側的相連；以此模型可以得到所有碎片的連接方式。

3英文碎片拼接復原改進模型

由于建立的初步模型決策變量較復雜，且兩個差異度矩陣較大，用程序實現(xiàn)較困難，因此在此提出改進模型[3]，只使用一種決策變量，具體建模過程如下：

3.1　提取信息：差異度指數和高度差

定義差異度指數Lij，與初步模型定義相同，但改進模型中不再使用差異度指數Uij，定義高度差Hij，表示第i塊碎片第一行文字中心到第i碎片上側邊緣的高度Hi與第j塊碎片第一行文字中心到第j碎片上側邊緣的高度Hj之間的差值。公式如下：

3.2　英文碎紙片拼接復原模型

其中：αij為決策變量，αij=0時，表示第i張碎片右側和第j張碎片左側的不相連；αij=1時，表示第i張碎片右側和第j張碎片左側的相連。

為了將雙目標轉化為單目標問題，可以給定高度差閾值Hij≤1，在給定高度范圍對所有碎片進行分類，共23類，可以將此模型簡化，目標函數與約束條件如下：

再結合人工干預可得到碎片的連接方式。

4英文碎片拼接復原模型算法

①找到每塊碎紙片第一行文字中心到碎紙片上側邊緣的高度。

第一步：將每塊碎紙片帶入MATLAB軟件中可得到由碎紙片上每個像素點灰度值組成的矩陣s1x(x=1，…，209)，將所有矩陣歸一化：

第二步：對灰度矩陣S1從上到下進行行搜索，找到每塊碎片第一行文字的中心位置；

第三步：通過MATLAB軟件編程計算第i塊碎紙片第一行文字中心到碎紙片上側邊緣的高度Hi；

②確定高度差閾值，進行聚類分析，將209塊碎片按照每塊碎片第一行文字中心到碎片上側邊緣的高度分為23類[4]。如表1。

表1　按高度不同對英文碎片的分類

高度(像素)=39.9±0.5的碎片1,23,39,51,53,64,73,84,86,88,90,98,125,126,129,139,140,194,201高度(像素)=44.3±0.5的碎片3,13,19,32,75,116,154,178高度(像素)=48.7±0.5的碎片2,121,130,161高度(像素)=52.2±0.5的碎片103,141高度(像素)=57.6±0.5的碎片48,76,107,181,192高度(像素)=62.0±0.5的碎片155高度(像素)=66.4±0.5的碎片12,65,185,191高度(像素)=70.9±0.5的碎片105高度(像素)=75.3±0.5的碎片24,91,100,123,209高度(像素)=79.8±0.5的碎片97,110,157,173,186高度(像素)=84.2±0.5的碎片87高度(像素)=106.4±0.5的碎片160高度(像素)=110.8±0.5的碎片33,40,66,205高度(像素)=124.1±0.5的碎片68,148,15高度(像素)=128.5±0.5的碎片5

③對每一類碎片，運用MATLAB軟件畫圖，可以畫出23行文字，對每行文字出現(xiàn)的奇異碎片進行剔除。通過人工干預，可以得到11行文字。

④對這11行文字，進行縱向拼接復原，在此基礎上通過人工干預將11行文字進行調試和拼接，可以得到英文的復原序號和復原圖片。

算法偽代碼[5]如下：

PROC

{

//讀入數據，根據文件類型進行導入操作

//FileType是導入文件的類型，指文件是否為分離成了兩面的文件

//FileType={Single|Double}；

//DATA內包含了文件的索引號及文件的Bitmap數據

DATA=Load_File_Data(‘FileName’，F(xiàn)ileType)；

//根據得到的數據對數據進行分類

//SortType決定分類檢索方向

DATA_SORTED=Calc_Feature(DATA，SortType)；

//計算數據差異度，得到DATA內部邊緣差異度矩陣

[DIF_ROWDIF_COL]=Calc_Dif(DATA)；

//對所得數據進行最小化差異操作，并返回最小化鏈接關系

[FIG_DATAFIG_CON]=

SORT(DIF_ROW，DIF_COL，DATA_SORTED)；

//在次校訂所得數據關系(此處可加入人工校驗過程)

CONN_DATA=RESHAPE(FIG_DATA，F(xiàn)IG_CON，DATA_SORTED)；

//由整合的數據進行分析整合成最終圖像，返回圖像句柄

handle=DRAW_MAP(CONN_DATA)；

}

5模型結果

對23類中任意一類碎片運用MATLAB編程可以畫出任意一行英文，舉例如圖1。

可以畫出23行英文，對每行英文出現(xiàn)的奇異碎片進行剔除。通過人工干預和基于碎片左右側差異度指數的縱向排列方法，可以得到11行有順序的英文，舉例如圖2。

圖1　某一類英文文字行排列

圖2　某一行有順序的英文排列

干預的時間節(jié)點及干預方式如下：

干預時間節(jié)點：MATLAB編程排出23行后，對第209塊碎片、第8塊、第62塊、第180塊、第5塊進行人工干預；將高度(像素)=75.3±0.5的碎片與高度(像素)=79.8±0.5人工干預。

干預方式：將這五個塊碎片分別帶入剩下的12行英文中，將每個碎片左側和右側邊緣灰度值這12行英文碎片的邊緣灰度值進行比較，找到差異度最小的連接方式，發(fā)現(xiàn)要把編號209的碎片歸入高度(像素)=8.9±0.5，將高度(像素)=17.7±0.5的碎片與高度(像素)=79.5±0.5人工干預成一行。

得到競賽原題附件四英文碎片拼接復原復序號表2及復原圖片3：

表2　附件四英文碎片復原序號

bath day No news is good news.

Procrastination is the thief of time.Genius is an infinitecapaaty for taking pains.Nothing succeeds like success.Ifyou can't beat em, join em.After a storm comes a calm.Agood beginning makes a good ending.

One hand washes the other.Talk of the Devil, and he isbound to appear.Tuesday's child is full of grace.You can'tjudge a book by its cover.Now drips the saliva, will becometomorrow the tear.All that glitters is not gold.Discretionis the better part of valour.Little things please little minds.Time flies.Practice what you preach.Cheats never prosper.

The early bird catches the worm.It's the early bird thatcatches the worm.Don't count your chickens before they arehatched.One swallow does not make a summer.Every pic-ture tells a story.Softly, softly, catchee monkey.Thought is already is late, exactly is the earliest time.Less is more.

A picture paints a thousand words.There's a time anda place for everything.History repeats itself.The more themerrier.Fair exchange is no robbery.A woman's work is never done.Time is money.

Nobody can casually succeed,it comes from the thorough self-control and the will.Not matter of the today will drag tomorrow.They that sow the wind, shall reap the whirlwind.Rob Peter to pay Paul.Every little helps.In for a penny, in for a pound.Never put off until tomorrow what you can do today.There's many a slip twixt cup and lip.The law is anass.If you can't stand the heat get out of the kitchen.The boy is father to the man.A nod's as good as a wink to a blindhorse.Practice makes perfect.Hard work never did anyoneany harm.Only has compared to the others early, diligently

圖3英文碎片復原圖片

參考文獻：

[1]羅智中.基于文字特征的文檔碎紙片半自動化拼接[J].計算機工程與應用，2012:207-211.

[2]全國大學生數學建模競賽組委會，2013年全國大學生數學建模競賽B題，http：//www.mcm.edu.cn/problem/2013/2013.html，2013.

[3]韓忠庚.數學建模方法及其應用[M].北京：高等教育出版社，2005.

[4]龔純.精通MATLAB最優(yōu)化計算[M].北京：電子工業(yè)出版社，2009.

[5]李剛.MATLAB函數速查手冊[M].北京：清華大學出版社，2013.

[責任編輯畢偉]

Computer-aided Single English File Fragments Reassembly

JIN Ming-ya,SUN Dan-lei,ZHAO YAN,DOU Ji-hong

(Department of Mathematics,Northwest University,Xi'an 710127,China)

Key words：difference degree index; 0-1 programming; MATLAB software; clustering analysis; height difference