莊思發(fā),付喜梅

（韶關(guān)學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,廣東韶關(guān)512005）

基于0-1整數(shù)規(guī)劃的碎紙片拼接復(fù)原算法

莊思發(fā),付喜梅

（韶關(guān)學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,廣東韶關(guān)512005）

碎紙片的拼接復(fù)原在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域都有著重要的應(yīng)用.研究利用計(jì)算機(jī)技術(shù)進(jìn)行碎紙片的拼接與復(fù)原是一項(xiàng)十分重要且很有意義的工作.針對(duì)通過(guò)碎紙機(jī)切割形成的規(guī)則碎紙片的拼接復(fù)原工作提出了基于0-1整數(shù)規(guī)劃的橫向排序復(fù)原算法,并對(duì)既有橫切又有縱切的情形提出了分類(lèi)算法.實(shí)驗(yàn)結(jié)果表明算法準(zhǔn)確率高,人工干預(yù)少.

0-1整數(shù)規(guī)劃；碎紙片拼接；排序；分類(lèi)

201 3年“高教社杯”全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽中,B題題目是討論碎紙片的拼接復(fù)原問(wèn)題.碎紙片的拼接復(fù)原在司法物證復(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］.

文字碎片拼接復(fù)原工作主要分為不規(guī)則碎片和規(guī)則碎片兩類(lèi).對(duì)不規(guī)則碎片拼接還原主要采用的算法有邊界檢測(cè)算法、角點(diǎn)檢測(cè)算法、遺傳算法等［2］.例如,何鵬飛在文獻(xiàn)［3］中提出了基于蟻群優(yōu)化算法的全局拼接方法；文獻(xiàn)［4］中的羅智中從文字特征的角度對(duì)碎紙片拼接復(fù)原進(jìn)行了研究.他們的研究原理是基于碎紙片的邊緣的形狀輪廓和碎紙片邊緣表現(xiàn)的色彩圖像.而對(duì)于規(guī)則的碎片,如2013年大學(xué)生數(shù)學(xué)建模競(jìng)賽B題所討論的使用碎紙機(jī)破碎所得的紙片,紙片均呈邊緣齊整的矩形形狀.其輪廓特征一致,上述的研究方法并不適用于此類(lèi)問(wèn)題.像此類(lèi)規(guī)則碎紙片的拼接復(fù)原問(wèn)題,文獻(xiàn)［5-8］均進(jìn)行了深入的研究.值得一提的是,文獻(xiàn)［7］中段寶彬等使用近年來(lái)研究非?；馃岬纳疃染矸e網(wǎng)絡(luò)方法.上述方法在僅有縱切的情況下復(fù)原率均能達(dá)到100%復(fù)原率.但對(duì)于同時(shí)有縱切與橫切的情況下,復(fù)原的準(zhǔn)確率都不高,人工干預(yù)的次數(shù)較多.本文在2013年大學(xué)生數(shù)學(xué)建模競(jìng)賽B題的基礎(chǔ)上對(duì)此類(lèi)中文碎紙片的拼接復(fù)原工作進(jìn)行研究.通過(guò)建立0-1整數(shù)規(guī)劃模型給出了碎紙片橫向拼接的全局優(yōu)化算法,對(duì)于既有縱切又有橫切的碎紙片,采用先分類(lèi)再排序的辦法進(jìn)行復(fù)原.

1 問(wèn)題分析

當(dāng)碎紙片僅有縱切的情形時(shí),每一碎紙片均為長(zhǎng)條形.對(duì)這種碎紙片的拼接復(fù)原等價(jià)于對(duì)所有紙條進(jìn)行左右排序.這個(gè)問(wèn)題相當(dāng)于典型的TSP（旅行商）問(wèn)題,所不同的是它不需要回到起點(diǎn).對(duì)于通過(guò)打印機(jī)輸出的文件,其典型的特征是紙張上下左右均有一定的空白區(qū)域.紙張雖然被縱向切割成了若干條,但這一特征依然保留在了每一紙條中.依此特征,容易找出位于紙張最左側(cè)及最右側(cè)的兩個(gè)紙條.而位于內(nèi)部的其余紙條中,兩紙條若是相鄰的,則它們各自對(duì)應(yīng)的右邊緣與左邊緣信息應(yīng)是相似或相近的.據(jù)此原理,可以定義相應(yīng)的距離以衡量紙條邊緣的相似性,從最左邊的碎片開(kāi)始,逐一將與其相鄰的碎片找出,最終將所有碎片排列正確.

定義1 給定n×1灰度向量x和y,定義x,y的余弦距離如下：

按照以上思路,首先將所有碎紙片的圖片信息讀入計(jì)算機(jī),每一紙條存儲(chǔ)為灰度矩陣數(shù)據(jù)（圖片數(shù)據(jù)均來(lái)源于2013年“高教社杯”全國(guó)大學(xué)生數(shù)據(jù)建模競(jìng)賽B題）.數(shù)據(jù)矩陣中的數(shù)值為圖片的灰度信息值,介于0～255之間,0代表黑色,255代表白色.因此,空白區(qū)域所有數(shù)值均為255.部分介于0與255之間的數(shù)值所占比重不大,它們實(shí)際是位于文字筆劃邊緣地帶,仍可以看成是文字部分.

2 縱切碎紙片的橫向拼接算法

假設(shè)X與Y是兩紙條對(duì)應(yīng)的灰度矩陣,它們?nèi)羰亲笥蚁噜彽?則X的最后一列數(shù)值與Y的第一列數(shù)值必定是相似的,或者說(shuō)灰度值相近.仿照TSP算法的思路,以?xún)伤槠吘壍木嚯x（定義1）來(lái)衡量?jī)杉垪l邊緣的相似度,再根據(jù)相似度的值可以判斷兩碎片是否相鄰,最后給出各碎片的左右排列順序.

2.1 啟發(fā)式算法

一種易于實(shí)現(xiàn)且計(jì)算速度較快的排序算法是啟發(fā)式算法［1］（算法1）.但該算法的缺點(diǎn)是所得解并非全局最優(yōu),對(duì)于僅有縱切的情形可以很好地解決,復(fù)原率可達(dá)百分百.但面對(duì)既有縱切又有橫切的情形時(shí),缺點(diǎn)就暴露得十分明顯了,在某些碎片行中,復(fù)原率甚至低于50%.

算法1 啟發(fā)式算法

假設(shè)紙張最左邊及最右邊的碎片對(duì)應(yīng)矩陣分別為Xl與Xr,1≤l,r≤k.

輸 入：X1,X2,…,Xk

初始化：令S=zeors(1,k);//0向量,存放排列好的序列；S(1)=l,S(k)=r;R=1,2,…,k;

R(l)=[];R(r)=[];//從R中刪除標(biāo)號(hào)l與r;t=1;

1) 令left=Xt(:,n);minDist=inf;

2) 對(duì)R中每一標(biāo)號(hào)s,令right=Xs(:,1);并計(jì)算:dist=dcos(left,right);//left與right之間的距離

3) 若dist<=minDist,則令minDist=dist;target=s;否則返回2);

4) 若R中標(biāo)號(hào)均已遍歷,則令S(t+1)=target;R(R=target)=[];t=t+1,若t=k–1,則跳到5),否則返回1);

輸出已排序標(biāo)號(hào)：S.

2.2 全局優(yōu)化算法

為使算法有較強(qiáng)的適用性，本文引入0-1整數(shù)規(guī)劃，提出一種全局優(yōu)化算法（算法2）.為了得到全局最優(yōu)解,先計(jì)算出任意兩張碎片之間的左右鄰接距離（定義2）,再將問(wèn)題轉(zhuǎn)化成0-1整數(shù)規(guī)劃問(wèn)題進(jìn)行求解.0-1整數(shù)規(guī)劃的求解,實(shí)際上是在所有可能的排列順序中尋找碎片鄰接總距離最小的排列,顯然,算法時(shí)間復(fù)雜度為O(n!),其中n為待排序的碎片總數(shù).問(wèn)題中待排序的碎片總量不大時(shí)，該算法依然能夠順利并高效的得出最優(yōu)解.

定義2 假設(shè)X1,X2,…,Xk為k個(gè)待排序的m×n灰度矩陣,記Xi(:,t)為Xi的第t列數(shù)據(jù),t=1,2,…,n,i=1,2,…,k.則Xi與Xj之間的距離aij定義為：

并規(guī)定碎片自身距離為無(wú)窮,即aii=∞,i=1,2,…,k.

如此,可得到一個(gè)非對(duì)稱(chēng)距離矩陣A=(aij),因?qū)θ我庖粋€(gè)非最右側(cè)碎片Xi來(lái)說(shuō),位于其右側(cè)的碎片

是唯一的,故可設(shè)如下決策變量：

以總距離最小為目標(biāo),可得如下0-1整數(shù)規(guī)劃：

該0-1整數(shù)規(guī)劃容易使用Lingo或MATLAB軟件求得最優(yōu)結(jié)果,而后需要從最優(yōu)解中回溯碎片排列順序.方法是,先從待排序的碎片中確定首末兩張碎片標(biāo)號(hào),然后從首碎片開(kāi)始,依次從最優(yōu)解中確定其相鄰碎片標(biāo)號(hào),詳見(jiàn)算法2.

算法2 全局優(yōu)化算法

假設(shè)紙張最左邊及最右邊的碎片對(duì)應(yīng)矩陣分別為Xl與Xr,1≤l,r≤k.

輸 入：Xl,X2,…,Xk

初始化：Y=zeros(1,k);

1) 確定序列中最左邊碎片Xl與最右邊碎片Xr,置Y(1)=l,Y(k)=r;

2) 求解整數(shù)規(guī)劃(1),得最優(yōu)解矩陣X=(Xij);

3) for i=2:k–1//回溯碎片標(biāo)號(hào)排列順序

l=Y(i–1);

for j=1:k

若xlj=1,則Y(i)=j;

end

end

輸出Y

因每一碎片包含的文字信息較多,碎片的邊緣信息量大,故只有縱切的情形下算法效率與準(zhǔn)確率都比較高,且不需要人工干預(yù).

算法在實(shí)際運(yùn)行過(guò)程中,某些碎片邊緣會(huì)因相似度過(guò)大導(dǎo)致在回溯碎片標(biāo)號(hào)時(shí)產(chǎn)生“子圈”,尤其是當(dāng)碎片既有縱切又有橫切時(shí).當(dāng)算法第三步的回溯過(guò)程到達(dá)某一碎片時(shí),下一標(biāo)號(hào)又指向了起點(diǎn)碎片,即最左邊碎片.這將導(dǎo)致輸出結(jié)果Y產(chǎn)生重復(fù)標(biāo)號(hào)序列而得不到正確的結(jié)果.例如,某行排序結(jié)果中碎片標(biāo)號(hào)出現(xiàn)了如下的循環(huán):50,55,66,50,55,66,50,55,66,50,55,66,50,55,66,50,55,66,142.

為解決此問(wèn)題,可考慮在循環(huán)中增加一個(gè)判斷條件：若某一碎片標(biāo)號(hào)的下一標(biāo)號(hào)指向了起點(diǎn)標(biāo)號(hào),則將該碎片標(biāo)號(hào)視為新的起點(diǎn)碎片,繼續(xù)回溯后序碎片標(biāo)號(hào).也可考慮將回溯過(guò)程進(jìn)行反向操作,即從最右端碎片標(biāo)號(hào)開(kāi)始往前回溯它的前一碎片標(biāo)號(hào).

3 縱橫切碎紙片的拼接復(fù)原算法

當(dāng)碎紙片經(jīng)既有縱切又有橫切而得到時(shí),此時(shí)碎片尺寸較小,包含的信息量也少.此時(shí)直接使用算法1或算法2都無(wú)法進(jìn)行處理,比較好的處理辦法是先將問(wèn)題中的209張碎片進(jìn)行分類(lèi),屬于同一橫切行的碎片為一類(lèi).由于中文字符的特點(diǎn),若碎片是位于相同的橫切行,則它們的字符高度是可以對(duì)齊的,也即是說(shuō)這些碎片的黑白相間的間隔是可以對(duì)齊的.據(jù)此,可以定義適當(dāng)?shù)木嚯x再通過(guò)聚類(lèi)分析,將碎片進(jìn)行行聚類(lèi).為能夠得到碎片黑白間隔信息,給出如下定義：

定義3給定m×n灰度矩陣X,稱(chēng)m×1向量θ=θ(X)為X的示性向量,其各分量θi(1≤ i≤ m)按如下方式取值：若X的第i行數(shù)據(jù)全為255（共n個(gè)）,則θi=0,否則θi=1.

聚類(lèi)時(shí),可用上述定義的余弦距離作為聚類(lèi)準(zhǔn)則.如問(wèn)題所述,紙張被切成了11行19列的碎片,因此聚類(lèi)分析類(lèi)別數(shù)應(yīng)定為11.MATLAB的聚類(lèi)工具箱提供了豐富的聚類(lèi)函數(shù),如cluster,pdist,linkage等,可直接使用.但在實(shí)際計(jì)算時(shí)筆者發(fā)現(xiàn)聚類(lèi)的效果并不理想,某些類(lèi)中只有1到2個(gè)碎片被劃入,而某些類(lèi)中卻被劃入了多達(dá)38個(gè)碎片.這將導(dǎo)致過(guò)多的人工干預(yù).

造成這個(gè)結(jié)果的原因是對(duì)于文章段落的末尾碎片部分,原本是在同行的碎片,卻因位于行末的碎片下半部分幾乎全是空白,與位于行首的碎片相差過(guò)大而被誤分至其它類(lèi)中.如圖1中給的例子,兩個(gè)碎片本是在紙張中同一行位置所切出的,但在聚類(lèi)時(shí)會(huì)被分至不同類(lèi)別.

為避免這樣的現(xiàn)象,采用分類(lèi)而非聚類(lèi)的方法.即先從所有碎片中找出位于最左側(cè)或最右側(cè)的11張碎片作為已知類(lèi)別的樣本,再將所有剩余樣本歸于所屬類(lèi)別中,最后利用算法2對(duì)相應(yīng)類(lèi)別的碎片進(jìn)行行排序.實(shí)際計(jì)算過(guò)程中,為進(jìn)一步消除空白行的影響,每一灰度矩陣的示性向量,只取其上半部分,而忽略其下半部分,而且使用最右側(cè)碎片作為已知類(lèi)別.如果某一個(gè)碎片的示性向量與某已知類(lèi)別的距離小于給定的閾值?時(shí),則認(rèn)為其屬于該類(lèi)別.

對(duì)于該209個(gè)碎片數(shù)據(jù),經(jīng)過(guò)多次的運(yùn)算與比較,發(fā)現(xiàn)當(dāng)取閾值τ=0.12時(shí)分類(lèi)的結(jié)果最好,準(zhǔn)確率最高,達(dá)到97%.此時(shí)209張碎片中僅有6張碎片沒(méi)有被歸類(lèi).其它閾值會(huì)導(dǎo)致某些類(lèi)別被歸入過(guò)多碎片,而某些類(lèi)別則又出現(xiàn)過(guò)少碎片.例如,當(dāng)τ=0.15時(shí),分類(lèi)結(jié)果中第1類(lèi)歸入了27張碎片,而第10類(lèi)僅有9張碎片,準(zhǔn)確率僅92%.分類(lèi)算法見(jiàn)算法3,表1給出了當(dāng)τ=0.12時(shí)的分類(lèi)結(jié)果.

圖1 兩個(gè)同行被錯(cuò)分異類(lèi)的碎片

最優(yōu)結(jié)果（見(jiàn)表1）中仍有6張碎片沒(méi)有被歸類(lèi),此時(shí)通過(guò)人工干預(yù)的辦法容易將它們歸入相應(yīng)的類(lèi)別中,剩余的6張碎片分別是：14、15、72、90、126及183.經(jīng)人工干預(yù)后,其中14、126及183號(hào)碎片歸入第9類(lèi),15號(hào)碎片歸入第10類(lèi),72號(hào)碎片歸入第5類(lèi),90號(hào)碎片歸入第7類(lèi).

上述分類(lèi)方法簡(jiǎn)單易操作,正確率高,人工干預(yù)少.表2列出了同類(lèi)文獻(xiàn)不同方法碎紙片拼接復(fù)原的準(zhǔn)確率，本文的算法3準(zhǔn)確率高達(dá)97%，明顯優(yōu)于其他算法.當(dāng)209張碎片被正確歸入類(lèi)別后,再使用算法2對(duì)屬于同行的碎片進(jìn)行行排序.因算法2是全局優(yōu)化算法,故對(duì)所有11類(lèi)的碎片進(jìn)行行排序的結(jié)果能保證百分百的正確率,因此也不需要人工干預(yù).經(jīng)行排序后可得到經(jīng)過(guò)橫向切割的11條紙條排列序號(hào).再按正確序列輸出圖像,可得到相應(yīng)的復(fù)原效果圖.圖2給出了其中第10類(lèi)的復(fù)原效果圖.最后將11條碎紙條復(fù)原效果圖經(jīng)過(guò)簡(jiǎn)單的人工排序后可還原成完整的紙張結(jié)果,完整結(jié)果圖略.

表1 τ=0.12時(shí)縱橫切碎紙片分類(lèi)結(jié)果

4 結(jié)語(yǔ)

研究利用計(jì)算機(jī)技術(shù)進(jìn)行碎紙片的拼接與復(fù)原是一項(xiàng)十分重要且很有意義的工作.本文針對(duì)通過(guò)碎紙機(jī)切割而成的中文碎片提出了分類(lèi)與排序算法,排序算法準(zhǔn)確率高達(dá)100%,而分類(lèi)算法的準(zhǔn)確率高達(dá)97%,較k-均值聚類(lèi)法高出近25個(gè)百分點(diǎn).但也有如下兩方面的缺點(diǎn)：一是算法依賴(lài)于中文字符排列比較齊整的特點(diǎn),對(duì)于字符高度不一的英文碎片不適應(yīng)；二是算法對(duì)不同類(lèi)型的紙張復(fù)原效果不一.若被切割的紙張是全文字類(lèi)型的,則效果較為理想.但若文件中出現(xiàn)插圖、表格等類(lèi)型時(shí),因含有較多空白碎片,導(dǎo)致算法同樣需要較多的人工干預(yù).這些缺點(diǎn)有待日后進(jìn)一步深入研究.

表2 各種方法的碎紙片拼接復(fù)原準(zhǔn)確率

圖2 第10類(lèi)碎片經(jīng)算法2的復(fù)原效果

［1］薛毅.碎紙片拼接復(fù)原的數(shù)學(xué)方法[J].數(shù)學(xué)建模及其應(yīng)用,2013,2（5）:9-13.

［2］陳玉成,田嬌.一種等大小矩形碎紙片拼接還原方法[J].廈門(mén)理工學(xué)院學(xué)報(bào),2014,22（3）:103-108.

［3］何鵬飛.基于蟻群優(yōu)化算法的碎紙拼接［D］.長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué),2009.

［4］羅智中.基于文字特征的文檔碎紙片半自動(dòng)拼接[J].計(jì)算機(jī)工程與應(yīng)用,2012（5）:207-210.

［5］魯嘉琪.基于文字信息的碎紙片拼接復(fù)原算法[J].現(xiàn)代電子技術(shù),2014（4）:28-31.

［6］李明珺,徐暉,江彩云,等.基于Matlab研究碎紙片的拼接復(fù)原[J].贛南師范學(xué)院學(xué)報(bào),2014,35（6）:19-22.

［7］段寶彬,韓立新.改進(jìn)的深度卷積網(wǎng)絡(luò)及在碎紙片拼接中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2014（9）:176-181.

［8］李蕾,麻思達(dá),潘博淵.基于TSP規(guī)劃模型的碎紙片拼接復(fù)原問(wèn)題研究[J].數(shù)學(xué)建模及其應(yīng)用,2014,3（2）:12-17.

Algorithm for Reconstruction of Shredded Paper Based on 0-1 Integer Programming

ZHANG Si-fa，F(xiàn)U Xi-mei
（School of Mathematics and Statistics,Shaoguan University,Shaoguan 512005,Guangdong,China）

The recovery of shredded paper has important application in judicial evidence recovery,historical document restoration and military intelligence acquisition.It is a very important and meaningful task to use computer technology for splicing and recovering of shredded paper.A sorting algorithm based on 0-1 integer programming is proposed for the splicing recovery of regular shredding pieces formed by shredder cutting,the classifying algorithm for the case of existing crosscutting and slitting is presented either.The experimental results show that the algorithm has high accuracy and less human intervention.

0-1 integer programming；reconstruction of shredded paper；sorting；classify

O221.4；TP391.41

A

1007-5348（2017）09-0009-06

2017-04-14

韶關(guān)學(xué)院科研項(xiàng)目（SY2016KJ16;S201501019）.

莊思發(fā)（1979-），男，廣東揭西人，韶關(guān)學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院講師，碩士；研究方向：模式識(shí)別、圖像處理等.

（責(zé)任編輯：邵曉軍）