基于聚類分析的碎紙復(fù)原算法

付苗苗，張　露，寧瑩瑩，黃　嬋，吳夢杰

(長春師范大學(xué)數(shù)學(xué)學(xué)院，吉林長春 130032)

?

基于聚類分析的碎紙復(fù)原算法

付苗苗，張露，寧瑩瑩，黃嬋，吳夢杰

(長春師范大學(xué)數(shù)學(xué)學(xué)院，吉林長春 130032)

[摘要]本文針對單面印刷文件縱向切割、單面印刷文件橫縱交錯切割和雙面印刷文件橫縱交錯切割的碎紙片三個問題，運用灰度矩陣、特征匹配和蟻群算法，分別給出碎紙還原方案。

[關(guān)鍵詞]灰度矩陣；邊緣去噪；鄰域平均法；圖像特征匹配；蟻群算法

1問題的設(shè)立與分析

本文主要研究邊緣規(guī)則的碎紙片有效快速拼接的方法。首先進行簡單說明，分析討論對象是統(tǒng)一的宋體四號、固定值12、首行縮進2字符的文字文件。文字文件經(jīng)掃描之后調(diào)整像素為1024×1600的圖片，切割成類似于碎紙機碎紙效果的小碎片。僅縱向切割碎紙片像素為128×1600，切割成8個碎紙片；橫縱交錯切割碎紙片像素為128×200，切割成64個碎紙片；正反面橫縱交錯切割成64個碎紙片，生成128張圖片，碎紙片圖片保存格式為*.jpg，a表示正面，b表示反面。

問題一：單面印刷文件縱向切割的碎紙片拼接?，F(xiàn)實中的數(shù)字圖像在數(shù)字化和傳輸過程中常常會受到設(shè)備與外界環(huán)境噪聲干擾等影響，因此要先對碎紙片圖片的邊緣進行去噪，在這里采用鄰域平均法對圖像邊緣進行降噪處理。構(gòu)建每個碎紙圖片的二值矩陣，在一定程度上降低了計算的復(fù)雜程度。然后對每個碎紙片的左右邊緣相似度進行分析，通過兩兩比較圖片左右相似程度對碎紙片進行排序與拼接，最后得以復(fù)原文件內(nèi)容。

問題二：單面印刷文件橫縱交錯切割的碎紙片的拼接。由于這種切割方法導(dǎo)致碎紙文片數(shù)量相對較多，所以先判別出最左邊的碎片，然后對剩下的圖片進行特征值匹配(這里的特征值就是指像素點對應(yīng)的值)。由于碎紙片是由文件橫縱交錯切割而成，不僅需要考慮碎片的左右邊緣的特征，還應(yīng)考慮碎片上下邊緣的特征，通過比較碎紙片四周邊緣的相似度，對碎紙片進行排序拼接，使得文件復(fù)原。

問題三：雙面印刷文件橫縱交錯切割。碎紙片的數(shù)量在問題二的基礎(chǔ)上又增加了一倍，在拼接技術(shù)上增加了難度。這里采用蟻群算法(ACA)的SIFT特征點匹配原理來解決問題。首先提取碎紙圖片四周邊緣的特征值，然后采用蟻群算法進行快速對比匹配排序，最后對碎紙片拼接使文件得以復(fù)原。

2模型的假設(shè)與符號說明

2.1模型的假設(shè)

假設(shè)一：原文件左右兩側(cè)均存在頁邊距。

假設(shè)二：不考慮掃描文件存儲為圖片時，光線強度對碎紙片灰度的影響。

假設(shè)三：文件中所給的碎紙片形狀相同，且它們之間能夠完全無縫拼接。

假設(shè)四：文件的文字高度和寬度一樣，間距相同，字體大小和字體樣式相同。

2.2符號的定義(表1)

表1　符號定義表

3模型的建立與求解

我們要將一個完整的文件掃描圖片進行切割而成的大小相同的碎紙片，首先這些碎紙片滿足了假設(shè)條件，我們將其打亂，重新編號，以達到碎紙片拼接的目的。圖1、圖2、圖3為分解文件之后的碎紙片圖像前三張。

圖2　縱向切割2

圖3　縱向切割3

3.1問題一：單面印刷文件縱向切割的碎紙片拼接

3.1.1步驟流程

圖4　問題一步驟流程圖

3.1.2圖像轉(zhuǎn)化為二值矩陣

二值圖像(binary image)是指一副二值圖像的二維矩陣僅由0、1兩個值構(gòu)成的。其中“0”表示黑色，“1”表示白色。每個像素點對應(yīng)的顏色不是黑色就是白色，其灰度值沒有中間過渡的圖像。二值圖像一般用來描述文字或者圖形，其優(yōu)點是占用空間少。 因此，針對問題一，我們先將對應(yīng)的碎紙圖片用MATLAB調(diào)用im2bw()函數(shù)對導(dǎo)入的碎紙圖片求解其二值矩陣。二值矩陣部分?jǐn)?shù)據(jù)如表2所示。

表2二值矩陣表

3.1.3圖像邊緣去噪——鄰域平均法

現(xiàn)實中的數(shù)字圖像在數(shù)字化和傳輸過程中常受到成像設(shè)備與外部環(huán)境噪聲干擾等影響，稱為含噪圖像或噪聲圖像。所以，我們采用鄰域平均法對圖像進行邊緣去噪，在像素點的某一鄰域內(nèi)取像素的均值來代替該點的像素。將已經(jīng)進行二值化的碎紙片圖片左右邊緣進行去噪處理，消弱噪聲點起到平滑作用，減小相似度誤差，增大匹配準(zhǔn)確度。設(shè)f(i,j)為給定的含有噪聲的圖像上像素點對應(yīng)的值，經(jīng)過鄰域平均處理后的圖像上像素點對應(yīng)的值為g(x,y)，則鄰域平均法也可以用數(shù)學(xué)公式表達(S=[1024*1600])：

3.1.4邊緣相似度

邊緣相似度是比較待測圖像邊緣上各個點與對應(yīng)的標(biāo)準(zhǔn)圖像邊緣上各個點之間的位置差距，用來判斷對應(yīng)的各個點的相似程度。將含噪圖像通過噪聲抑制算法處理后的待測邊緣圖像設(shè)為BY，對于BY上的一個邊緣點x(i,j)，其邊緣相似度可以定義為：

根據(jù)公式，可總結(jié)出每個點的相似程度。通過計算待測圖像邊緣點與對應(yīng)的標(biāo)準(zhǔn)圖像邊緣點之間的位置差距來比較。如果兩個點完全重合，則對應(yīng)的兩個點相似程度最大，計算公式的值為1；如果相差k個像素點，根據(jù)計算公式對應(yīng)的兩個點的相似程度則降低e-k；如果出現(xiàn)的不是待測圖像邊緣上的點，卻檢測成了邊緣點，或者是待測圖像邊緣上的點，卻沒檢測出來，根據(jù)計算公式顯示default。每個碎紙片圖像邊緣相似度可以定義為圖像邊緣上所有點的邊緣相似度的平均值。

其中，M為待測邊緣圖像中邊緣上的點的總個數(shù)。

3.1.5基于MATLAB比較邊緣相似程度進行排序

通過比較每個碎紙片圖像的左右邊緣相似程度，得出排列順序，如表3所示。

表3　問題一的碎紙拼接順序表

采用MATLAB拼接技術(shù)，調(diào)用imread()函數(shù)進行拼接。

3.2問題二：單面印刷文件橫縱交錯切割的碎紙片的拼接

3.2.1步驟過程

圖5　問題二步驟流程圖

3.2.2圖像特征匹配

簡而言之，特征匹配就是根據(jù)圖像的特征進行匹配拼接，如果說我們進行的是不規(guī)則圖形的拼接，就可以根據(jù)圖形的邊緣形狀來進行篩選，而這里我們用規(guī)則的碎紙片轉(zhuǎn)化成圖像進行拼接，同樣也是需要提取和分析圖像的特征，例如圖6和圖7所示的兩個碎紙片。

圖6橫縱交錯切割1

圖7　橫縱交錯切割2

圖8　對應(yīng)圖4特征分析

圖9　對應(yīng)圖5特征分析

圖8中p3板塊有文字；圖9中q1、q3板塊有文字，q2板塊有部分文字，這分別就是圖8和圖9的圖像特征，而且顯然圖像特征不匹配。

下面用程序來判斷碎紙片圖像邊緣是否有匹配，建立如下模型：

該模型表示第一張圖片最后一列的第i個特征值與其它張圖第一列的第i個特征值比較，并且還對后一張碎紙片圖像的第一列的第i+1，i-1個特征點進行比較。

3.2.3基于MATLAB比較邊緣特征點匹配程度進行排序和拼接

通過比較每個碎紙片的左右上下邊緣的特征點的匹配程度，對碎紙片排序如表4所示。

表4　問題二的碎紙拼接順序表

(橫向續(xù)表)

(橫向續(xù)表)

(橫向續(xù)表)

調(diào)用MATLAB拼接函數(shù)進行拼接，恢復(fù)原文件。

3.3問題三：雙面印刷文件橫縱交錯切割

3.3.1步驟過程

圖10　問題三步驟流程圖

3.3.2基于ACA搜索的碎紙片圖像SIFT特征點匹配

蟻群算法(ACA)，又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機率型算法，其靈感來源于螞蟻。螞蟻群體在尋找食物過程中，當(dāng)一只螞蟻找到食物后會釋放信息素，周圍的螞蟻就會知道這個地方有食物，從四面八方不同的路徑找到食物，最短路徑上慢慢會聚集很多的螞蟻。自然界中螞蟻搜索食物的過程是一個不斷聚類過程，食物就是聚類中心，用數(shù)學(xué)語言來表述就是：Xi是一只螞蟻，螞蟻分別聚集到j(luò)個聚類中心Cj(j=1,2,…,k)Xi到Cj的距離為dij，采用如下歐式距離計算。

其中，Xi表示螞蟻，Cj表示聚類中心，m表示維數(shù)，P表示加權(quán)因子。假設(shè)算法中螞蟻對自己所走過的有記憶，則可根據(jù)2張待拼接碎紙片圖像上互信息濃度選擇轉(zhuǎn)移方向，從而引導(dǎo)螞蟻根據(jù)互信息濃度測度最大值的方向移動。信息素計算公式：

其中，計算公式中α為信息素的相對重要程度，β為啟發(fā)式因子的相對重要程度，ρ為信息素蒸發(fā)系數(shù)，1-ρ為信息素的持久性系數(shù)，τ為窗口信息素含量，η為啟發(fā)函數(shù)，N為循環(huán)遍歷次數(shù)。

圖像特征匹配是將從兩個或多個圖像中提取出來的圖像特征或者說特點用參量描述出來，并通過參量的相關(guān)算法來進行圖片匹配的一種方法。所以要先對帶匹配的兩張碎紙片圖像進行處理，然后提取滿足特定要求的特征集或特征區(qū)，然后將其進行對應(yīng)匹配，生成一組新的對應(yīng)特征對集，最后利用這組特征對之間的對應(yīng)關(guān)系計算出全局變換參數(shù)?；趫D像特征的匹配方法可以克服利用圖像灰度信息進行匹配的缺點，由于圖像的特征點比較像素要少很多，大大減少了匹配過程中的計算量；特征點的匹配度量值對位置的變化比較敏感，可以大大提高匹配的精確程度；特征點的提取過程可以減少噪聲的影響，對灰度變化和圖像變形等都有較好的適應(yīng)能力。

3.3.3基于MATLAB結(jié)合算法對碎紙片進行排序拼接

經(jīng)過計算得到如下拼接順序與效果：a面，即正面拼接順序如表4所示；b面，即反面拼接順序如表5所示。

表5　問題三的碎紙片拼接順序表

(橫向續(xù)表)

(橫向續(xù)表)

(橫向續(xù)表)

4總結(jié)

4.1碎紙復(fù)原的優(yōu)點

首先，本文解決問題的方法簡單清晰，并且可以通過Matlab軟件快速求解，有較強的理論性和實用性，通過實際的操作，驗證了其可靠性。其次，全文貫徹邊緣去噪，在相對精確的數(shù)據(jù)基礎(chǔ)上比較碎紙片圖像邊緣的相似度，是保證圖像拼接成功的基礎(chǔ)。最后，碎紙片拼接復(fù)原的模型是基于文字信息構(gòu)建的，先對碎紙片圖像進行二值化，使研究數(shù)據(jù)簡單化，再對圖像二值矩陣的邊緣相似度進行分析，查找排列順序，自動拼接，相比較全人工拼接還是快一些的。

4.2改進

鄰域平均處理可實現(xiàn)去噪的效果，模版尺寸越大，減少噪聲的效果越好。但卻犧牲了圖像的清晰度，因此可以換取另外一種較好的邊緣去噪的方法或者使用更好的掃描設(shè)備。由于采用了建立圖像二值矩陣的方法，還原效果不夠精確，不如直接使用灰度值進行邊緣比較。

[參考文獻]

[1]姜啟源.數(shù)學(xué)模型[M].北京:高等教育出版社,2007.

[2]韓中庚.數(shù)學(xué)建模方法及其應(yīng)用[M].北京:高等教育出版社,2009.

[3]陳杰.MATLAB寶典[M].北京:電子工業(yè)出版社,2013.

[4]賈海燕.一種碎紙自動拼接中的形狀匹配方法[J].計算機仿真,2006,23(11):180-183.

[5]羅智中.基于文字特征的文檔碎紙片半自動拼接[J].計算工程與應(yīng)用,2012,48(5):207-210.

Shredding Restored Algorithm Based on Clustering Analysis

FU Miao-miao, ZHANG Lu, NING Ying-ying, HUANG Chan, WU Meng-jie

(School of Mathematics,Changchun Normal University, Changchun Jilin 130032,China)

Abstract:This paper studied the effective and fast splicing method of regular boundary on the scraped paper.On according to the actual example :the printing files of single-sided with longitudinal cutting and transverse and longitudinal staggered cutting ,even the printing files of double side with staggered vertical and horizontal cutting, we give the shredding restored algorithm, respectively.

Key words:gray matrix; edge-noise-removing; neighborhood average method; image feature matching; ant colony algorithm

[收稿日期]2016-04-07

[基金項目]國家級大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃項目“碎紙復(fù)原技術(shù)”(102052015003)。

[作者簡介]付苗苗(1971- )，女，教授，博士，從事應(yīng)用數(shù)學(xué)研究。

[中圖分類號]TP391

[文獻標(biāo)識碼]A

[文章編號]2095-7602(2016)06-0029-07