基于模糊聚類分析的碎紙片拼接模型

葉德華 朱溦

摘 要：規則邊界碎紙片拼接在司法實踐中有應用意義，研究采用模糊聚類分析對碎紙片進行行的分類。行分類后，利用帶有字寬評估的0-1規劃模型對行內碎紙片進行排序拼接。行排序完成后，以每行為碎片單位，采用帶有字高評估的0-1規劃模型。

關鍵詞：模糊聚類分析;0-1規劃模型;碎紙片拼接

中圖分類號：O159 文獻標識碼：A

1 問題概述

隨著司法實踐對文檔物證修復的需要，碎紙機的普遍使用，碎紙片文檔的自動或半自動拼接復原技術的研究具有重要意義。一般文檔碎片拼接復原問題，可分為手撕非規則碎片拼接和機器類切割規則碎片拼接兩類。而機器類切割、邊界規則碎片又可以分為縱切和縱橫切，單面文檔和雙面文檔，中文字體、英文字體、混合字體和圖文并茂等特征文檔。

碎片拼接的拼接過程往往可以劃分為4個環節：碎片圖象采集、碎片圖象預處理、匹配程度度量和拼接算法（可以含人工交互）。其中，匹配程度度量和拼接算法實現是關鍵。在匹配度度量上，有帶有罰函數的歐氏距離[1];利用Hamming距離或Jaccard距離[2];利用余弦距離[3];利用碎片邊緣像素的總變差度量距離[4]。拼接算法，主要有利用聚類分析找到同行的碎片，然后轉化為旅行商問題[1-2]。在定義了鄰接距離或度量距離后，轉化為0-1整數規劃問題[3-4]。

文章針對單面縱橫切中文字體的文檔，從人工拼接思考的過程出發，在手動拼接時，總把最有可能歸為一行的碎片先歸納為同一行。在這樣的行中進行行內排序，在排序過程中，根據行內整體匹配度高低，進行碎片的剔除。行排序完成后，以整行為單位再進行行之間的排序。因此，研究采用模糊聚類分析，在聚類閾值的選擇上，采用類間碎紙片的數量盡可能均衡和碎片數估計的方法。而行類中碎紙片的排序，以及以行為單位的行之間的排序，則分別采用帶有字寬評估的0-1規劃模型和帶有字高評估的0-1規劃模型。

2 圖象采集與預處理

為保證圖象有共同的幾何大小，對碎片文檔進行掃描，保存為“.jpg”格式的圖片。然后利用Matlab中的imread（‘filename.jpg’）命令讀入圖象，再利用im2bw（A，thresh）命令進行二值化，參數thresh針對具體的應用場景確定。實驗中使用的是CUMCM2013B題中的附件3.確定thresh=0.5.經過二值化后得到m×n（例子中180×72）的矩陣集{Ai|i=1，2，…}。Ai中元素值為0表示字跡，1表示背景色。

3 碎紙片特征提取

針對中文碎紙片的特點，定義碎紙片特征結構體Hi={r，hor，ver，h，w}。

對每塊碎片的矩陣Ai，采用從左上角順時針歷遍的方式對邊緣像素值前后值求差，計算像素值從1突變到0的頻數fi。得到碎片一周邊緣像素豐富程度。

特殊情況，當碎片四周都是沒有筆畫像素的或都有筆畫像素的，越接近于0;相反，像素恰好是1-0交替出現的，越接近于1。顯然，值越大，越有利于正確地拼接。

用水平像素累積直方圖的方法確定字符行的開始和結束位置。從碎片上方開始記錄直方圖中全1（像素累積是 ）的位置，記為（第片的右側文字行開始或結束位置向量）。同時可以得到漢字高度特征向量（第片的漢字高度向量），計算出平均字高H。

用相鄰列求差法，計算每個碎紙片上邊緣和下邊緣的字符開始和結束位置，分別記為（第片上側文字開始或結束位置向量）和（第片下側文字開始或結束位置向量）。同時，可以得到漢字寬度向量 （第片上側文字寬度）和（第片下側文字寬度），計算出平均字寬 W。

相鄰列求差算法。

4 模糊聚類分析

利用碎片邊緣像素豐富程度（1），設置合理的閾值，可以直接篩選出邊緣沒有文字的碎片集M，模糊聚類對所有碎紙片中去除了M集中的碎片進行。聚類分析的過程是數據標準化，建立模糊相似矩陣，動態聚類。

用相關系數法建立模糊相似矩陣得到R，用二次方法計算R的傳遞閉包t（R），在傳遞閉包t（R）中，根據相似度的值，由大到小進行聚類。

聚類中最佳閾值的確定。策略（1）根據實際問題信息A4紙的寬度和每個碎紙片的寬度，估計出每行中碎紙片的數量，記為。策略（2）設分類中第類的碎紙片數量為，選擇使最小且最接近值的。

5 行內和行間排序

聚類分析后得到每行的碎片類，在行內排列中，采用帶有字寬評估的0-1規劃模型。分別取出碎片Ai的左側和右側邊緣像素值：

行內排序完成后，可以根據文件切碎的大小、是否有中英文混排、是否有圖片等的復雜程度，進行人工干擾。確保行排序完整無誤后，進行行間的碎片排序。以整行碎片的上下邊緣像素值和漢字高度向量為特征，類似與行內排序，建立帶有字高評估的0-1規劃模型進行拼接，最終完成文檔的拼接。

6 實驗與評價

實驗以2013年高教杯全國大學生數學建模競賽B題中的碎片為數據，以MATLAB R2014a為平臺進行驗證。拼接結果準確完整。研究提出利用模糊聚類分析進行碎片行分組，采用行內碎紙片的數量盡可能均衡和碎片數估計的方法，選擇合理的聚類閾值。然后，利用帶有字寬評估的0-1規劃模型對行內碎片進行排序，采用帶有字高評估的0-1規劃模型對行的碎片進行排序。存在不足，在行內碎片排序中，因切割的多樣性，還是會需要人工干預;算法的速度和準確性對比方面還需要進一步的研究。

參考文獻

[1] 付光輝，華云，陳軍華，等.基于聚類和蟻群算法的橫縱切碎紙片復原算法[J].數學的實踐與認識，2019，49（15）：199-209.

[2] 薛毅.碎紙片拼接復原的數學方法[J].數學建模及其應用，2013，2（Z2）：9-13.

[3] 蔡志杰.碎紙片拼接復原的數學模型與方法[J].高等數學研究，2016，19（04）：107-110.

[4] 余錦華，楊維權.多元統計分析與應用[M].廣州：中山大學出版社，2005：162-183.