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

葉德華 朱溦

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

關(guān)鍵詞：模糊聚類分析;0-1規(guī)劃模型;碎紙片拼接

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

1 問題概述

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

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

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

2 圖象采集與預(yù)處理

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

3 碎紙片特征提取

針對中文碎紙片的特點，定義碎紙片特征結(jié)構(gòu)體Hi={r，hor，ver，h，w}。

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

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

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

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

相鄰列求差算法。

4 模糊聚類分析

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

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

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

5 行內(nèi)和行間排序

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

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

6 實驗與評價

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

參考文獻

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

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

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

[4] 余錦華，楊維權(quán).多元統(tǒng)計分析與應(yīng)用[M].廣州：中山大學出版社，2005：162-183.