基于Matlab GUI碎紙機(jī)破碎文檔解決方式

基于Matlab GUI碎紙機(jī)破碎文檔解決方式1 概述破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域都有著重要的應(yīng)用。傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準(zhǔn)確率較高，但效率很低。特別是，當(dāng)碎紙片數(shù)量巨大，人工拼接很難在短時(shí)間內(nèi)完成任務(wù)。隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們?cè)噲D開(kāi)發(fā)碎紙片的自動(dòng)拼接技術(shù)，以提高拼接復(fù)原效率。文章基于Matlab GUI對(duì)破碎文檔（既縱切又橫切）的復(fù)原實(shí)現(xiàn)人機(jī)互動(dòng)，并給出了提高文檔復(fù)原效率的方法。2 圖像采樣圖象采樣就是按照?qǐng)D像空間的坐標(biāo)測(cè)量該坐標(biāo)測(cè)量該位置上像素的灰度值。方法如下：對(duì)連續(xù)的f（x，y）進(jìn)行等間隔采樣，在（x，y）平面上，將圖像均分成均勻的小網(wǎng)格，每個(gè)小網(wǎng)格的位置可以用整數(shù)坐標(biāo)表示，于是采樣值就對(duì)應(yīng)于一個(gè)MxN數(shù)字矩陣。這樣就獲得了數(shù)字圖像中關(guān)于像素的兩個(gè)屬性：位置和灰度。位置由采樣點(diǎn)的兩個(gè)坐標(biāo)確定，也就對(duì)應(yīng)了網(wǎng)格行和列；而灰度表明了該像素的明暗程度。Matlab讀入圖象的函數(shù)為imread（filename，format）。而文章討論的碎片圖像格式為bmp的8位灰度圖像，每一像素的取值范圍為0255。3 碎片的分類3.1 碎片特征提取準(zhǔn)確地確定碎片的特征對(duì)碎片的分類起著重要作用，原始的碎片圖像中可利用的像素點(diǎn)較多，而碎片圖像中能有效反應(yīng)碎片的特征的像素需要恰到好處地提取。文字的筆畫(huà)有粗細(xì)之分，由此，不考慮筆畫(huà)的粗細(xì)，文字的輪廓更能體現(xiàn)碎片的特征。運(yùn)用邊緣檢測(cè)的方法，實(shí)現(xiàn)對(duì)文字輪廓的確定。（a） （b）圖1 邊緣化處理前后對(duì)比圖將每行邊緣輪廓像素通過(guò)累加法，得到一個(gè)180維的向量。邊緣輪廓像素在180維的向量的每一分量的值呈現(xiàn)一定的規(guī)律，圖2為圖1（a）的累加向量。3.2 K-Means聚類分析方法K-Means聚類指基于劃分的聚類分析【4】，事先需要制定將數(shù)據(jù)分為幾類，給定一個(gè)有n個(gè)個(gè)體的數(shù)據(jù)集，將它劃分為K個(gè)簇（k？燮n），使每個(gè)簇具有較高的相似度，而簇間的相似度較低。它需要滿足以下兩個(gè)條件：（1）K類中任意一類不為空集，即每一類至少有一個(gè)個(gè)體；（2）每一個(gè)體都屬于且僅屬于K類中的一類。其中相似度的計(jì)算：根據(jù)一個(gè)簇中點(diǎn)的平均值（被看作簇的重心）來(lái)進(jìn)行。K-means聚類算法的描述和處理流程如下：K-means是用于劃分的K均值算法，每個(gè)簇的中點(diǎn)用簇中對(duì)象的均值表示，其輸入為簇的數(shù)目K和包含n個(gè)對(duì)象的數(shù)據(jù)集，輸出為K個(gè)簇的集合，使得平方誤差準(zhǔn)則最小。原理如下：（1）首先為每個(gè)聚類確定一個(gè)初始聚類中心，這樣就有K個(gè)初始聚類中心；（2）將樣本集中的樣本按照最小距離原則分配到最鄰近聚類；（3）使用每個(gè)聚類中的樣本均值作為新的聚類中心；（4）重復(fù)步驟（2）和（3）直到聚類中心不再變化；（5）結(jié)束，得到K個(gè)聚類。將樣本分配到距離他們最近的中心向量，并使目標(biāo)函數(shù)值最小，K-means算法的目標(biāo)函數(shù)通?？梢员硎緸椋篍=P-m式中，E是數(shù)據(jù)集中所有對(duì)象的平方誤差和；P是數(shù)據(jù)對(duì)象，文章表示給定對(duì)象的像素特征值；mi是Ci的均值（P和mi都是多維）；P-m表示P與mi之間的度量。通過(guò)求這個(gè)目標(biāo)函數(shù)E的最小值來(lái)試圖使生成的結(jié)果簇盡可能地緊湊和獨(dú)立。對(duì)于度量，形象地說(shuō)就是我們主要考慮的樣本間的差異。在數(shù)據(jù)分析和數(shù)據(jù)挖掘的過(guò)程中，我們經(jīng)常需要知道個(gè)體間差異的大小，進(jìn)而評(píng)價(jià)個(gè)體的相似性和類別。我們要比較個(gè)體x和個(gè)體y間的差異，它們都包含了n個(gè)維的特征，即x（x1，x2，…，xn），y=（y1，y2，…，yn），如下幾種距離主要衡量?jī)烧叩牟町?，其中d（x，y）越小，即樣本x，y之間的距離越小，樣本x，y越相似，差異度越??；反之，越大。歐幾里得距離（sqEuclidean）：d（x，y）=（xi-yi）2）1/2絕對(duì)值距離（cityblock）：d（x，y）=（xi-yi特別地當(dāng)xi∈0，1yi∈0，1 此時(shí)又稱漢明距離；余弦距離（cosine）：d（x，y）=（xi，yi）/（xi2）1/2（yi2）1/2）4 碎片匹配根據(jù)碎片鄰接原理以及圖片格式的性質(zhì)，我們給出了如下定理：定理1. 假設(shè)a1和a2分別為".bmp"圖片格式兩碎紙片的矩陣（如圖5），s1為a1最右側(cè)列，s2為a2的最左側(cè)列，如果a1與a2為鄰接碎紙片（a1為左邊，a2為右邊）的必要條件為：如果非邊緣第m個(gè)點(diǎn)，m∈s1為黑色（值為0），則s2中的第m-1，m，m+1個(gè)位置中必然存在不為白色的點(diǎn)（值255）；同理：如果此時(shí)s2處非邊緣的第n個(gè)點(diǎn)，n∈b為黑色（值為0），則s1中的第m-1，m，m+1個(gè)位置中必然存在不為白色的點(diǎn)（值255）。證明：由".bmp"圖片格式灰度（值0255）特性即證。圖3 碎紙片匹配示意圖因?yàn)檫@是圖像匹配【1】的必要條件，即不滿足這個(gè)條件必定不能匹配，滿足條件為可能匹配的碎紙片。假設(shè)滿足條件中的碎紙片矩陣集合為an，i∈N，則如果i=1，則這一個(gè)唯一確定的匹配。如果i>1，則需要人工干預(yù)，找出匹配度最高的碎紙片。定理2. 假設(shè)a1和a2分別為".bmp"圖片格式兩碎紙片的矩陣，s1為a1最右側(cè)列，s2為a2的最左側(cè)列，定義絕對(duì)值差異度d（S1，S2）=S1i-S2i，其中S1=（S11，S12，…，S1n），S2=（S21，S22，…，S2n）5 碎片拼接Matlab GUI軟件包運(yùn)用前面三節(jié)的內(nèi)容，我們?cè)O(shè)計(jì)了碎片拼接Matlab GUI軟件包， 根據(jù)聚類分析K均值距離公式的不同，我們?cè)O(shè)計(jì)了如下參數(shù)設(shè)置界面：圖4 k-means參數(shù)設(shè)置界面點(diǎn)擊圖4的確定按鈕后，彈出圖5行內(nèi)拼接界面。圖5 行內(nèi)拼接界面完成行內(nèi)拼接后，點(diǎn)擊"下一步"，出現(xiàn)行間拼接界面，最后生成完整的紙張。圖6 行間拼接界面參考文獻(xiàn)【1】莊俊東.基于數(shù)字圖像處理的人民幣碎紙片拼接方法的研究.上海交通大學(xué)，2010.【2】張翠.基于點(diǎn)線的文檔圖片數(shù)字水印與碎紙片拼接.中國(guó)海洋大學(xué)，2011.【3】葛巧瑞.自然場(chǎng)景下的文字分割及識(shí)別研究.西安電子科技大學(xué)，2011.