基于0-1整數規劃的碎紙片拼接復原算法

莊思發,付喜梅

（韶關學院數學與統計學院,廣東韶關512005）

基于0-1整數規劃的碎紙片拼接復原算法

莊思發,付喜梅

（韶關學院數學與統計學院,廣東韶關512005）

碎紙片的拼接復原在司法物證復原、歷史文獻修復以及軍事情報獲取等領域都有著重要的應用.研究利用計算機技術進行碎紙片的拼接與復原是一項十分重要且很有意義的工作.針對通過碎紙機切割形成的規則碎紙片的拼接復原工作提出了基于0-1整數規劃的橫向排序復原算法,并對既有橫切又有縱切的情形提出了分類算法.實驗結果表明算法準確率高,人工干預少.

0-1整數規劃；碎紙片拼接；排序；分類

201 3年“高教社杯”全國大學生數學建模競賽中,B題題目是討論碎紙片的拼接復原問題.碎紙片的拼接復原在司法物證復原、歷史文獻修復以及軍事情報獲取等領域都有著重要的應用.傳統的拼接復原工作由人工完成,準確率高,但效率低.特別是當碎片數量巨大,人工拼接很難在短時間內完成任務.隨著計算機技術的發展,人們試圖開發碎紙片的自動拼接技術,以提高拼接復原效率［1］.

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

1 問題分析

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

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

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

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

假設X與Y是兩紙條對應的灰度矩陣,它們若是左右相鄰的,則X的最后一列數值與Y的第一列數值必定是相似的,或者說灰度值相近.仿照TSP算法的思路,以兩碎片邊緣的距離（定義1）來衡量兩紙條邊緣的相似度,再根據相似度的值可以判斷兩碎片是否相鄰,最后給出各碎片的左右排列順序.

2.1 啟發式算法

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

算法1 啟發式算法

假設紙張最左邊及最右邊的碎片對應矩陣分別為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中刪除標號l與r;t=1;

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

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

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

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

輸出已排序標號：S.

2.2 全局優化算法

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

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

并規定碎片自身距離為無窮,即aii=∞,i=1,2,…,k.

如此,可得到一個非對稱距離矩陣A=(aij),因對任意一個非最右側碎片Xi來說,位于其右側的碎片

是唯一的,故可設如下決策變量：

以總距離最小為目標,可得如下0-1整數規劃：

該0-1整數規劃容易使用Lingo或MATLAB軟件求得最優結果,而后需要從最優解中回溯碎片排列順序.方法是,先從待排序的碎片中確定首末兩張碎片標號,然后從首碎片開始,依次從最優解中確定其相鄰碎片標號,詳見算法2.

算法2 全局優化算法

假設紙張最左邊及最右邊的碎片對應矩陣分別為Xl與Xr,1≤l,r≤k.

輸 入：Xl,X2,…,Xk

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

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

2) 求解整數規劃(1),得最優解矩陣X=(Xij);

3) for i=2:k–1//回溯碎片標號排列順序

l=Y(i–1);

for j=1:k

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

end

end

輸出Y

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

算法在實際運行過程中,某些碎片邊緣會因相似度過大導致在回溯碎片標號時產生“子圈”,尤其是當碎片既有縱切又有橫切時.當算法第三步的回溯過程到達某一碎片時,下一標號又指向了起點碎片,即最左邊碎片.這將導致輸出結果Y產生重復標號序列而得不到正確的結果.例如,某行排序結果中碎片標號出現了如下的循環:50,55,66,50,55,66,50,55,66,50,55,66,50,55,66,50,55,66,142.

為解決此問題,可考慮在循環中增加一個判斷條件：若某一碎片標號的下一標號指向了起點標號,則將該碎片標號視為新的起點碎片,繼續回溯后序碎片標號.也可考慮將回溯過程進行反向操作,即從最右端碎片標號開始往前回溯它的前一碎片標號.

3 縱橫切碎紙片的拼接復原算法

當碎紙片經既有縱切又有橫切而得到時,此時碎片尺寸較小,包含的信息量也少.此時直接使用算法1或算法2都無法進行處理,比較好的處理辦法是先將問題中的209張碎片進行分類,屬于同一橫切行的碎片為一類.由于中文字符的特點,若碎片是位于相同的橫切行,則它們的字符高度是可以對齊的,也即是說這些碎片的黑白相間的間隔是可以對齊的.據此,可以定義適當的距離再通過聚類分析,將碎片進行行聚類.為能夠得到碎片黑白間隔信息,給出如下定義：

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

聚類時,可用上述定義的余弦距離作為聚類準則.如問題所述,紙張被切成了11行19列的碎片,因此聚類分析類別數應定為11.MATLAB的聚類工具箱提供了豐富的聚類函數,如cluster,pdist,linkage等,可直接使用.但在實際計算時筆者發現聚類的效果并不理想,某些類中只有1到2個碎片被劃入,而某些類中卻被劃入了多達38個碎片.這將導致過多的人工干預.

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

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

對于該209個碎片數據,經過多次的運算與比較,發現當取閾值τ=0.12時分類的結果最好,準確率最高,達到97%.此時209張碎片中僅有6張碎片沒有被歸類.其它閾值會導致某些類別被歸入過多碎片,而某些類別則又出現過少碎片.例如,當τ=0.15時,分類結果中第1類歸入了27張碎片,而第10類僅有9張碎片,準確率僅92%.分類算法見算法3,表1給出了當τ=0.12時的分類結果.

圖1 兩個同行被錯分異類的碎片

最優結果（見表1）中仍有6張碎片沒有被歸類,此時通過人工干預的辦法容易將它們歸入相應的類別中,剩余的6張碎片分別是：14、15、72、90、126及183.經人工干預后,其中14、126及183號碎片歸入第9類,15號碎片歸入第10類,72號碎片歸入第5類,90號碎片歸入第7類.

上述分類方法簡單易操作,正確率高,人工干預少.表2列出了同類文獻不同方法碎紙片拼接復原的準確率，本文的算法3準確率高達97%，明顯優于其他算法.當209張碎片被正確歸入類別后,再使用算法2對屬于同行的碎片進行行排序.因算法2是全局優化算法,故對所有11類的碎片進行行排序的結果能保證百分百的正確率,因此也不需要人工干預.經行排序后可得到經過橫向切割的11條紙條排列序號.再按正確序列輸出圖像,可得到相應的復原效果圖.圖2給出了其中第10類的復原效果圖.最后將11條碎紙條復原效果圖經過簡單的人工排序后可還原成完整的紙張結果,完整結果圖略.

表1 τ=0.12時縱橫切碎紙片分類結果

4 結語

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

表2 各種方法的碎紙片拼接復原準確率

圖2 第10類碎片經算法2的復原效果

［1］薛毅.碎紙片拼接復原的數學方法[J].數學建模及其應用,2013,2（5）:9-13.

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

［3］何鵬飛.基于蟻群優化算法的碎紙拼接［D］.長沙：國防科學技術大學,2009.

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

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

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

［7］段寶彬,韓立新.改進的深度卷積網絡及在碎紙片拼接中的應用[J].計算機工程與應用,2014（9）:176-181.

［8］李蕾,麻思達,潘博淵.基于TSP規劃模型的碎紙片拼接復原問題研究[J].數學建模及其應用,2014,3（2）:12-17.

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

ZHANG Si-fa，FU 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

韶關學院科研項目（SY2016KJ16;S201501019）.

莊思發（1979-），男，廣東揭西人，韶關學院數學與統計學院講師，碩士；研究方向：模式識別、圖像處理等.

（責任編輯：邵曉軍）