規則碎片拼接算法

李 猛，劉家保

(1.合肥市統計局，合肥230071;2.安徽新華學院 公共課教學部，合肥230088)

如今世界上紙質碎片的拼接技術分人工和計算機自動拼接兩種。由人工完成的拼接復原的正確率高，但效率非常低，當碎片數量多時，人工拼接難以在短時間里完成。隨著計算機技術的發展，現代碎片拼接研究方向主要集中在計算機自動拼接［1－6］，但在處理碎片拼接時，當今主流是采用形狀匹配、邊緣比較、數據庫匹配等技術，對硬件運算能力和儲存能力都有著極高的要求。而很多情況下，并不需要處理太過復雜的碎片，如一般辦公室通常采用的是碎紙機碎紙，所得的碎片形狀比較規則，拼接不需要考慮形狀匹配等因素，因此使用主流的對高硬件運行速度和存儲空間消耗的算法就比較浪費。因此，以文件碎片邊緣的黑白色匹配程度為依據，結合動態規劃［8］理論，以普通家用電腦為硬件基礎，提出了一種簡潔有效的規則碎片自動拼接算法。

1 相關設定與定義

1.1 設 定

(1)無切割誤差。碎紙機在切割文件時沒有誤差，切出來的碎片中文字方向平行于上下邊緣，同一文件碎片大小完全一致;

(2)無打印誤差。紙質文件按同一標準打印出來，行號、字號、行間矩完全一致，中文字體完全一致，英文字體完全一致;

(3)無物理誤差。碎片圖片無污跡，無毛邊等干擾情況;

(4)論文中使用的誤差為根據拼接實驗中碎片的數據選定，可根據實際碎片數據進行更改。

1.2 定 義

(1)兩文件碎片之間的匹配率［5］。讀取每一個碎紙片圖片文件為數據矩陣，選取適當閥值，將其用二值法化為0－1矩陣。任取碎紙片i和碎紙片j進行比較，記:

(2)已分組文件之間的行匹配率。在以將碎片文件分組排序的基礎上，任取第i組和第j組進行比較，記

(3)碎片文字行高估計值。碎片所在行的每行文字所占碎片文件象素行數的最大值與最小值的估計值，簡稱為文字行高估計值。根據一碎片包含文字行數，每一碎片的行高估計值約有4～6個。如圖1中碎片000.bmp 的行高估計值可記為 0，26，56，96，124，165。

圖1 待拼接碎片000.bmp

2 碎片的按行分組

此時，仍可以碎片之間的匹配率為標準，利用貪心法［8］逐行拼接后再按行匹配率進行排序。但通過對中國2013年數學建模競賽B題附件3提供碎片實際拼接結果發現，直接拼接誤差非常大，正確率僅為30.81%。因此，在此采用先按行分組，再進行拼接的方法來降低誤差。

在假定中，碎片文件的四邊平行于原紙張相應邊緣，且其中文字是按同一標準逐行打印而成的。所以從理論上，同行碎片文件的同行文字的行高與行間距都應該是對應相等的(圖2)。

從圖2中可以看出000.bmp，007.bmp，045.bmp行間矩基本相同，因此可以歸成一類。且因為筆劃、字形、灰度等情況可能會產生部分誤差，通過圖形對比，可把誤差額度設置為(－5，5)。

分組算法:

第1步，按每一文件第一行象素全為255，和有多行不為255分類，為避免特殊情況產生誤差，僅有前面連續2行以內不全為255的情況單獨歸為一類。

第2步，將按順序選擇一個未分組文件單獨分為一組，提取每一行漢字所占象素行數的最小值和最大值，可得到3對數據。

第3步，以上述3對數據為基礎，設為上述碎片文件的初始文字行高估計值，以同一類中其它文件的相應數據進行比較，選取方差小于閥值k的文件，將其加入001文件所在組，并將碎片文字行高估計值改為已加入該組的所有碎片文件相應數據的平均值。k的值根據實際需要選定，如根據允許誤差范圍(－5，5)，則可取閥值k=6×25=150。

第4步，以新得到的估計值為標準，重復步驟3，篩選出所有符合條件的文件，歸為一組。

第5步，重復步驟2、3、4，直至完成全部分組。

第6步，根據整張紙片切割的行數m和列數n，對以上各組數據進行現次處理，按每組包含文件個數從大到小排列，以前11為基礎。包含文件個數超過列數n的，以所在組每一碎片文件相應數據與碎片文字行高估計值比較，選出與標準差最小的n個文件，其余文件從組中移出。小于列數n的，以該組的碎片文字行高估計值為基礎，將未分組文件和包含文件個數不超過3個的組包含文件依次比較，選出方差最小的若干個文件加入組中，補足n個。

圖2 待拼接碎片示例圖

以圖2 中000.bmp，001.bmp，007.bmp，045.bmp 4個文件為例。

(1)000.bmp、007.bmp、045.bmp 同屬于多行不全為255 的一類。

(2)按編號順序從000.bmp開始分組處理，此時分組數為0，所以001不屬于任何一組，將其單獨分為1組{000.bmp}。提取碎片文件000.bmp每一行漢字所占象素行數的最小值和最大值，得到一組數據1、26、57、96、125、165，將其設為組{000.bmp}對應碎片所在行的相應數據的初始估計值。經檢測，001.bmp屬于第一行象素值全為255這一類別，此時，沒有與其同一組的碎片文件，因此001.bmp單獨分為一組{001.bmp}。

(3)經檢測007.bmp每一行漢字所占象素行數的最小值和最大值為1、26、59、96、125、165，與初始估計值相比較，方差為4小于閥值k，所以將007.bmp并入組{000.bmp}，取新的碎片文字行高估計值為00.bmp和001.bmp 相應數據的平均值，1、26、58、96、125、165。

(4)依次將045.bmp 相應數據與之比較，最終將文件分為兩組{000.bmp，001.bmp，045.bmp}和{001.bmp}。

每組內碎紙片的排序為:以分組數據為基礎，對每一組文件，以同組文件之間的匹配率為標準，應用貪心法，將同組碎片文件排序。對已排序數據，以不同組文件之間的組匹配率為基礎，應用貪心法，將各組進行排序。

3 人工較正和計算機輔助人工較正

在碎片過多的情況下，計算機拼接可能會由于打印、筆劃、字型的不同等原因產生一定的誤差，此時就需要通過手工對已處理結果進行較正。但受視力、思考速度等身體條件影響，在需要較正碎片量較大的情況下，人工較正可能會產生速度較慢、有一定誤差等問題。

對此，在人工較正過程中，仍可以使用計算機進行輔助，用以加快較正速度，減少較正工作量。在處理過程中，可以采用遍歷法，仍以碎片之間的匹配律為基礎，讓計算機按順序推薦出與錯拼的文件最匹配的5個(根據需要可自由選擇數目)文件，便于快速較正誤差。

4 拼接實驗

試驗以中國2013年數學建模競賽B題提供文件為實驗對象，使用MATLAB程序作為編程工具［7］。

4.1 僅縱向切割的碎片拼接

此時所有碎片均為一行，跳過行分組階段，直接應用貪心法進行排序，即可直接得到正確順序。此種情況下因計算匹配率時相應象素點數量較大，因而所得匹配率數據值可信度高，拼接結果錯誤率極小，一般不需要人工較正。

4.2 縱橫切碎片拼接的問題

第1步，把所有碎片按前面的分組算法分組。以附件3為例，得表1:

表1 分組后得到的碎片組合

此處根據實際情況可適當調整閥值、誤差區域。

第2步，對每一組分別排序，得表2:

表2 每一分組內部的碎片排序結果

第3步，人工較正。縱橫切割的碎片在計算匹配率時進行比較的象素點較少，因此出錯的可能性相對僅縱切的情況較高，偶爾需要進行人工較正。

通過上述結果，觀察可得，上述結果中094號碎片與201號碎片不在正確的位置上，因為只有兩個錯誤碎片，將094和201交換所在組重新排序即可。

若錯誤碎片也可采用計算機輔助，利用程序依次將094以外的其它碎片遍歷一遍，得到與094匹配率最高的5個文件034、058、090、149、164，人工對比發現034號碎片與094號拼接最符合要求。同理可找到與201最適碎片005。

第4步，行間排序。利用兩行之間的行匹配率，應用貪心法進行排序，得到表3正確順序。

表3 附件3碎片附原順序

5 傾斜切割的理論算法

從理論上來說，碎紙機切割縱橫切割相結合，但實際上由于紙張變形、文件放置、機器精度等問題，很難做到標準的垂直和平行切割，在實際情況中難免會出現一些誤差。這時仍可根據碎片文件之間的匹配率進行拼接，但如前所述，直接拼接誤差太大所有仍然要先考慮分組。以下僅針對文件產生一定傾斜角的情況從理論上提出分組，其余情況可依此拓展。針對以下3個碎片文件(圖3):

圖3 傾斜切割所得到的文件碎片

現采用兩種思路進行行分組:

(1)對碎片一分析，得到圖片傾斜角大小，由此判斷出與文字方向平行的空白行位置與相應行數。文字傾斜時因其上下兩行文字高度始終改變，縱橫切割拼接方法中按一行文字高度分組的方法就不適用了。這里采用相連接的兩碎片左右文字的銜接度來分組。由于文字傾斜時一行文字所占最大值與最小值始終改變，因此采用按列抽樣的方法。如對上面第一個碎片，抽取最左側n列，取一行文字所占象素位置，逐列取其最大值和最小值(為避免誤差，對一行文字最高處明顯與前后不符的列舍去)，分別取其平均值，設為碎片文件左側行高參數的估計值。同理，可得到碎片文件右側參數的估計值。在允許一定的誤差情況下，根據前一文件最右側參數的估計值和最右側參數估計值的比較進行行分組即可。

(2)在掃描碎片文件時通過手動，將碎片中文字方向恢復為水平，如上面碎片文件可掃描為圖4:

圖4 將文字方向調為水平后得到的文件碎片

此時可將文件按斜行分組，且每兩個碎片要以如下兩個標準進行拼接:兩個碎片文件之間的匹配律;前一碎片文件最右側文字行高與后一文件最左側文字行高相匹配。

［1］羅智中.基于線段掃描的碎紙片邊界檢測算法研究［J］.儀器儀表學報，2011，32(2):289-294

［2］王欣潔.基于灰度矩陣的中文碎紙片的拼接復原算法［J］.智能計算機與應用，2013，3(6):95-97

［3］徐雅平，王運生.碎紙片的拼接復原［J］.上海商學院學報，2013，4(5):79-84

［4］李曉霞，高志鵬，張蕊倚，等.關于中英文的碎紙片拼接復原問題研究［J］.運城學報2013，31(5):12-15

［5］楊雯雯，陶佳琪，鄭路通，等.單頁單面漢字縱橫切碎片拼接復原算法［J］.運城學報2013，31(5):16-20

［6］羅智中.基于文字特征的文檔碎紙半自動拼接［J］.計算機工程與應用，2012，48(5):207-210

［7］王沫然.MATLAB6.0與科學計算［M］.北京:電子工業出版社，2011

［8］THOMASH C，CHARLESE L，RONALD L R.Introduction to Algorithms算法導論［M］.北京:機械工業出版社，2010