朱晨杰　劉婷　余嘉賓　胡振旭　蔣素瓊　何湘威

【摘 要】本文從數(shù)學(xué)模型的角度出發(fā)，對規(guī)則邊緣的碎紙片拼接問題的行間拼接和分行聚類兩個核心步驟進(jìn)行了解決方案的描述。在行間拼接階段具體建立了基于貪心算法的最優(yōu)二叉樹拼接模型和基于全局優(yōu)化的TSP拼接模型；在分行聚類階段則針對中文和英文不同的規(guī)則給出了基于空白信息特征和基于極值搜索的聚類模型。最后本文還對對應(yīng)的拼接模型在MATLAB中GUI交互界面開發(fā)拼接軟件的功能進(jìn)行了具體的描述。

【關(guān)鍵詞】最優(yōu)二叉樹拼接；TSP拼接；空白信息特征；極值搜索；拼接軟件

【Abstract】From the angle of mathematical model， this paper described the two key steps of joining of regular edge paper piece， that is joining inside the row and clustering between rows.We established the optimal binary tree based on greedy algorithm and TSP model based on global optimization in the stage of former，and obtained Chinese and English piece cluster model based on the blank information features and extremum search respectively.In the end， the paper also describes the function of the corresponding join software in GUI interface of MATLAB.

【Key words】Optimal binary tree join； TSP join； Blank information features； Extreme search； Join software

0 前言

在公安的刑偵工作中，經(jīng)常有破碎的證物需要被拼接還原，如碎紙片文字或圖像等。這項工作若依賴于人力，是十分費(fèi)時費(fèi)力的，因此找到一種機(jī)器方法對這些碎片進(jìn)行自動高效拼接是十分必要的。

國內(nèi)外已有的計算機(jī)自動拼接軟件或算法主要建立在邊緣形狀和圖像信息的匹配上，這些算法對于拼接邊緣形狀不規(guī)則及圖像信息較豐富的對象是比較有效的，但是對于經(jīng)現(xiàn)代碎紙機(jī)處理的規(guī)則邊緣形狀打印紙片則識別度非常低。本文旨在建立數(shù)學(xué)模型對現(xiàn)代打印的規(guī)則大小的碎紙片的拼接過程進(jìn)行科學(xué)的描述，以提高刑偵領(lǐng)域的工作效率。

1 拼接模型的建立

當(dāng)然，近幾年國內(nèi)對此類問題的研究成果頗多，但都側(cè)重于不同算法的正確率比較。而文本將重點描述該規(guī)則紙片拼接問題的數(shù)學(xué)模型建立及有針對性的分別給出中文、英文具體拼接函數(shù)。

在拼接前，我們利用MATLABA讀取圖片的像素信息，并考慮到提高算法的效率，對碎片的灰度矩陣進(jìn)行二值化（1代表白色0代表黑色），得到相應(yīng)的0-1矩陣數(shù)據(jù)。

1.1 行間排序的數(shù)學(xué)模型

本文從優(yōu)化的角度，按貪心算法和全局優(yōu)化依次給出兩種模型來描述行間如何排序。

1.1.1 基于貪心算法的最優(yōu)二叉樹拼接模型

最優(yōu)二叉樹——表示對于一組帶有確定權(quán)值的葉結(jié)點，構(gòu)造的具有最小帶權(quán)路徑長度的二叉樹（示意圖見表1）。

基本思路：

Step1：將每張碎片視為一片葉子，兩碎片間的貼合度視為合并樹葉的指標(biāo)。由給定的n個碎片組成集合F；

Step2：計算F中各碎片間兩兩貼合度矩陣A在A中選取最大貼合度所在的對應(yīng)的碎片編號left、right，構(gòu)造一棵新的二叉樹，將兩碎片拼接而成的新圖片看做一個新的節(jié)點；

Step3：在集合F中刪除碎片left、right，并將新建立的碎片樹xin加入到集合F中；

Step4：重復(fù)Step2、Step3兩步，當(dāng)F中只剩下一個節(jié)點，即一張拼接圖片時，這張即為拼接的結(jié)果。

1.1.2 基于全局優(yōu)化的TSP拼接模型

記G=（V，E）為賦權(quán)圖，V={v1，v2…vm}為碎片的頂點集，E=dijvi，vj∈V為各條碎片頂點相互連接組成的邊集，此處即為各條碎片兩兩拼接的集合。每條邊都存在與之相對應(yīng)的權(quán)值，即相鄰碎片拼接時的貼合度為dij，可構(gòu)成n×n階的矩陣，dij>0，dij=+∞，i，j∈V，并設(shè)

其中，i，j表示碎片編號；m表示碎片個數(shù)；S表示圖G的碎片頂點的個數(shù)；基于以上分析，可建立碎片拼接優(yōu)化模型，并直接應(yīng)用Lingo或Matlab軟件即可求解。

1.1.3 兩種模型的比較分析

這兩種模型都是基于對同一行的碎紙片的優(yōu)化拼接，但前者是基于貪心思想的Huffman算法是一種局部優(yōu)化，相比下應(yīng)用旅行商問題的TSP規(guī)劃算法則是一種全局優(yōu)化。二者的收斂性和復(fù)雜度分析都具有良好的理論基礎(chǔ)，能對拼接過程進(jìn)行清晰而準(zhǔn)確的數(shù)學(xué)描述，而不僅僅是一種算法的流程。

1.2 行聚類數(shù)學(xué)模型

在復(fù)雜的碎紙機(jī)形成的碎片中存在著既橫切又縱切的情況，此時就需要先對碎片進(jìn)行正確的分行，再應(yīng)用前文的行間排序模型進(jìn)行拼接。下面我們會根據(jù)中文和英文不同的特征采用兩種模型來實現(xiàn)高效的行聚類。

1.2.1 基于空白特征信息的舍去及拆分的中文碎片行聚類模型

我們知道，如漢字“一”等字高明顯偏短的漢字與標(biāo)點符號“，。”和漢字“吉”中間有非常短的空白導(dǎo)致一個漢字的特征信息被分成兩部分“士”與“口”等。所以接下來我們對提取到的圖片信息進(jìn)行預(yù)處理工作。

Step1：對于空白我們采取當(dāng)空白小于12像素則忽略；

Step2：將被分割的漢字的特征信息進(jìn)行了拼接處理，如“吉”字，他不再被記錄成兩部分信息而是一個整體，基于圖片的分析，我們可得到正常漢字高為40并結(jié)合誤差考慮所以我們將舍去黑像素高度小于25的特征信息（上述12、40及25都是一個指標(biāo)，可以根據(jù)具體數(shù)據(jù)調(diào)試出合適的值）。

Step3：拆分的依據(jù)則主要是檢測空白部分是否大于正常標(biāo)準(zhǔn)（通過對圖片的分析我們可得知標(biāo)準(zhǔn)行間距約為30個像素）并規(guī)定如果大于32個像素則拆分（這里考慮到誤差所以比標(biāo)準(zhǔn)行間距大2個像素）。

Step4：對上步得到的圖片特征信息進(jìn)行聚類?？砂凑諏⒆?、右邊緣的圖片作為該行的標(biāo)準(zhǔn)特征信息進(jìn)行分行聚類，也可先將左右邊緣的圖片進(jìn)行匹配，并合并相同行的特征信息，從而得到更精確的行的特征信息，再依據(jù)這個精確的行特征信息進(jìn)行聚類。

1.2.2 基于極值搜索的英文碎片行聚類模型

如果要處理的是英文碎片，我們可知英文與中文字體提取特征信息的最大區(qū)別是在于中文字體大部分是方塊形而英文是基于四線三格的印刷體，字高不定，因此中文碎片的行聚類模型并不適用于此。但是印刷體的四線三格的位置是一定的，所以我們可以根據(jù)圖片的整體信息如上一行與下一行的相對位置和本行的文字特征結(jié)合起來確定四線三格的位置從而提取英文圖片的特征信息。

對于英文圖片我們依據(jù)上述將圖片讀入并二值化的圖片數(shù)值化信息矩陣，統(tǒng)計每一行的白色像素點的個數(shù)，并將其從圖相中描繪出來，如下所示（以第一張英文圖片為例）。

從上面的趨勢圖中易知start1，end1與start2，end2兩對點分別為原圖中兩行英文字的四線中的中間兩根線，因為白色像素點最少，反映到圖中便是曲線極速降低，故我們建立此曲線的極值搜索模型來確定四線的位置。

Step1：搜索所有的極小值。判斷依據(jù)為p（x）<=p（x-1）且p（x）

Step2：然后在每個片段中找出相距為15-25之間的極小值點對，如果該片段中只有一組點對，則該點對即為我們要找的改行的標(biāo)志對。如果該片段中多于一組點對符合條件我們則從中篩選出黑色像素聚集最多的點對成為該片段的標(biāo)志對，數(shù)值體現(xiàn)為相加之和最小。

Step3：將上步得到的每個碎片的四線特征結(jié)合全局的角度調(diào)整誤差，即可進(jìn)行分行聚類。

2 在MATLAB軟件GUI交互界面開發(fā)拼接軟件

為提高用戶體驗，我們利用MATLAB實現(xiàn)GUI交互界面，旨在解決復(fù)雜的算法邏輯與簡單快捷的使用之間的矛盾?，F(xiàn)從以下幾個模塊分別闡述：

一鍵導(dǎo)入功能：只要將待排序的碎片掃描圖放入一個文件夾內(nèi)，即可按該導(dǎo)入按鈕，找到文件夾的路徑，將碎片導(dǎo)入到軟件后臺。

圖片信息類型選擇功能：不同的圖片，對應(yīng)的信息特征也不同，如中文字體和英文字體的拼接特征點不同，通過圖片信息類型選擇功能，可大大提高算法的效率，讓本軟件有針對性地采取相應(yīng)的措施，對癥下藥。

算法選擇功能：當(dāng)碎片信息成功導(dǎo)入到后臺，用戶可自由選擇拼接的算法，當(dāng)然我們提供了一個默認(rèn)算法，并針對相應(yīng)的碎片信息智能計算出最優(yōu)方案。

一鍵導(dǎo)出功能：將拼接好的圖片按照用戶指定的格式等信息導(dǎo)出到用戶指定的位置方便用戶對拼接結(jié)果的存儲。

人工干預(yù)功能：當(dāng)碎紙片拼接完成后，某些部位出現(xiàn)嚴(yán)重的偏差，人眼可直接看出時，我們提供人工干預(yù)的功能。只要用鼠標(biāo)左擊相應(yīng)位置，并拖動圖片到適當(dāng)位置即可。大大提高了碎紙片拼接的精確度。

3 結(jié)語

本文從數(shù)學(xué)模型的角度出發(fā)，對規(guī)則邊緣的碎紙片拼接問題的行間拼接和分行聚類兩個核心步驟進(jìn)行了有針對性的解決方案的描述，并對其應(yīng)用功能的實現(xiàn)作了初步的實踐說明。在碎片拼接的理論上是對規(guī)則邊緣類別拼接的數(shù)學(xué)描述的空白補(bǔ)充，在拼接實踐上也提供了一個可行簡便的平臺來實現(xiàn)該理論，未來就是在如何改進(jìn)算法正確率及提高交互界面用戶體驗上進(jìn)行進(jìn)一步的探索。

【參考文獻(xiàn)】

[1]Kenneth H.Rosen.離散數(shù)學(xué)及其應(yīng)用[M].北京：機(jī)械工業(yè)出版社，2015，1.

[2]劉浩，韓晶.MATLAB R2014a完全自學(xué)一本通[M].電子工業(yè)出版社，2015，1.

[責(zé)任編輯：王楠]