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

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

(西北大學(xué)數(shù)學(xué)學(xué)院，陜西西安710127)

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

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

中圖分類號(hào)：O242

文獻(xiàn)標(biāo)識(shí)碼：A

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

收稿日期：2014-11-14

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

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ù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域都有著重要的應(yīng)用。隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們?cè)噲D開發(fā)碎紙片的自動(dòng)拼接技術(shù)[1]，來提高拼接復(fù)原效率。

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

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

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

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

2.1　提取信息：差異度指數(shù)

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

公式如下：

2.2　英文碎紙片拼接復(fù)原模型

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

3英文碎片拼接復(fù)原改進(jìn)模型

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

3.1　提取信息：差異度指數(shù)和高度差

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

3.2　英文碎紙片拼接復(fù)原模型

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

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

再結(jié)合人工干預(yù)可得到碎片的連接方式。

4英文碎片拼接復(fù)原模型算法

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

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

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

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

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

表1　按高度不同對(duì)英文碎片的分類

高度(像素)=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

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

④對(duì)這11行文字，進(jìn)行縱向拼接復(fù)原，在此基礎(chǔ)上通過人工干預(yù)將11行文字進(jìn)行調(diào)試和拼接，可以得到英文的復(fù)原序號(hào)和復(fù)原圖片。

算法偽代碼[5]如下：

PROC

{

//讀入數(shù)據(jù)，根據(jù)文件類型進(jìn)行導(dǎo)入操作

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

//FileType={Single|Double}；

//DATA內(nèi)包含了文件的索引號(hào)及文件的Bitmap數(shù)據(jù)

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

//根據(jù)得到的數(shù)據(jù)對(duì)數(shù)據(jù)進(jìn)行分類

//SortType決定分類檢索方向

DATA_SORTED=Calc_Feature(DATA，SortType)；

//計(jì)算數(shù)據(jù)差異度，得到DATA內(nèi)部邊緣差異度矩陣

[DIF_ROWDIF_COL]=Calc_Dif(DATA)；

//對(duì)所得數(shù)據(jù)進(jìn)行最小化差異操作，并返回最小化鏈接關(guān)系

[FIG_DATAFIG_CON]=

SORT(DIF_ROW，DIF_COL，DATA_SORTED)；

//在次校訂所得數(shù)據(jù)關(guān)系(此處可加入人工校驗(yàn)過程)

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

//由整合的數(shù)據(jù)進(jìn)行分析整合成最終圖像，返回圖像句柄

handle=DRAW_MAP(CONN_DATA)；

}

5模型結(jié)果

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

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

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

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

干預(yù)的時(shí)間節(jié)點(diǎn)及干預(yù)方式如下：

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

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

得到競賽原題附件四英文碎片拼接復(fù)原復(fù)序號(hào)表2及復(fù)原圖片3：

表2　附件四英文碎片復(fù)原序號(hào)

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英文碎片復(fù)原圖片

參考文獻(xiàn)：

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

[2]全國大學(xué)生數(shù)學(xué)建模競賽組委會(huì)，2013年全國大學(xué)生數(shù)學(xué)建模競賽B題，http：//www.mcm.edu.cn/problem/2013/2013.html，2013.

[3]韓忠庚.數(shù)學(xué)建模方法及其應(yīng)用[M].北京：高等教育出版社，2005.

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

[5]李剛.MATLAB函數(shù)速查手冊(cè)[M].北京：清華大學(xué)出版社，2013.

[責(zé)任編輯畢偉]

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