陳斯定+++朱燁婷+++徐晶

摘 要：文章詳細闡述了基于Matlab GUI對單面印刷文檔經(jīng)碎紙機破碎的碎片（既縱切又橫切）的恢復(fù)，結(jié)合計算機對碎片的匹配搜索和人工干預(yù)，提高文檔恢復(fù)的效率，達到文檔的恢復(fù)。

關(guān)鍵詞：Matlab GUI；聚類分析；人工干預(yù)

1 概述

破碎文件的拼接在司法物證復(fù)原、歷史文獻修復(fù)以及軍事情報獲取等領(lǐng)域都有著重要的應(yīng)用。傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準確率較高，但效率很低。特別是，當(dāng)碎紙片數(shù)量巨大，人工拼接很難在短時間內(nèi)完成任務(wù)[1-3]。

隨著計算機技術(shù)的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術(shù)，以提高拼接復(fù)原效率。文章基于Matlab GUI對破碎文檔（既縱切又橫切）的復(fù)原實現(xiàn)人機互動，并給出了提高文檔復(fù)原效率的方法。

2 圖像采樣

圖象采樣就是按照圖像空間的坐標測量該坐標測量該位置上像素的灰度值。方法如下：對連續(xù)的f（x，y）進行等間隔采樣，在（x，y）平面上，將圖像均分成均勻的小網(wǎng)格，每個小網(wǎng)格的位置可以用整數(shù)坐標表示，于是采樣值就對應(yīng)于一個M×N數(shù)字矩陣。這樣就獲得了數(shù)字圖像中關(guān)于像素的兩個屬性：位置和灰度。位置由采樣點的兩個坐標確定，也就對應(yīng)了網(wǎng)格行和列；而灰度表明了該像素的明暗程度。Matlab讀入圖象的函數(shù)為imread（filename，format）。而文章討論的碎片圖像格式為bmp的8位灰度圖像，每一像素的取值范圍為0～255。

3 碎片的分類

3.1 碎片特征提取

準確地確定碎片的特征對碎片的分類起著重要作用，原始的碎片圖像中可利用的像素點較多，而碎片圖像中能有效反應(yīng)碎片的特征的像素需要恰到好處地提取。文字的筆畫有粗細之分，由此，不考慮筆畫的粗細，文字的輪廓更能體現(xiàn)碎片的特征。運用邊緣檢測的方法，實現(xiàn)對文字輪廓的確定。

（a） （b）

圖1 邊緣化處理前后對比圖

將每行邊緣輪廓像素通過累加法，得到一個180維的向量。邊緣輪廓像素在180維的向量的每一分量的值呈現(xiàn)一定的規(guī)律，圖2為圖1（a）的累加向量。

3.2 K-Means聚類分析方法

K-Means聚類指基于劃分的聚類分析[4]，事先需要制定將數(shù)據(jù)分為幾類，給定一個有n個個體的數(shù)據(jù)集，將它劃分為K個簇（k？燮n），使每個簇具有較高的相似度，而簇間的相似度較低。它需要滿足以下兩個條件：（1）K類中任意一類不為空集，即每一類至少有一個個體；（2）每一個體都屬于且僅屬于K類中的一類。

其中相似度的計算：根據(jù)一個簇中點的平均值（被看作簇的重心）來進行。K-means聚類算法的描述和處理流程如下：K-means是用于劃分的K均值算法，每個簇的中點用簇中對象的均值表示，其輸入為簇的數(shù)目K和包含n個對象的數(shù)據(jù)集，輸出為K個簇的集合，使得平方誤差準則最小。原理如下：

（1）首先為每個聚類確定一個初始聚類中心，這樣就有K個初始聚類中心；（2）將樣本集中的樣本按照最小距離原則分配到最鄰近聚類；（3）使用每個聚類中的樣本均值作為新的聚類中心；（4）重復(fù)步驟（2）和（3）直到聚類中心不再變化；（5）結(jié)束，得到K個聚類。

將樣本分配到距離他們最近的中心向量，并使目標函數(shù)值最小，K-means算法的目標函數(shù)通常可以表示為：

E=■■P-m■■

式中，E是數(shù)據(jù)集中所有對象的平方誤差和；P是數(shù)據(jù)對象，文章表示給定對象的像素特征值；mi是Ci的均值（P和mi都是多維）；P-m■■表示P與mi之間的度量。通過求這個目標函數(shù)E的最小值來試圖使生成的結(jié)果簇盡可能地緊湊和獨立。

對于度量，形象地說就是我們主要考慮的樣本間的差異。在數(shù)據(jù)分析和數(shù)據(jù)挖掘的過程中，我們經(jīng)常需要知道個體間差異的大小，進而評價個體的相似性和類別。我們要比較個體x和個體y間的差異，它們都包含了n個維的特征，即x（x1，x2，…，xn），y=（y1，y2，…，yn），如下幾種距離主要衡量兩者的差異，其中d（x，y）越小，即樣本x，y之間的距離越小，樣本x，y越相似，差異度越?。环粗?，越大。

歐幾里得距離（sqEuclidean）：d（x，y）=（■（xi-yi）2）1/2

絕對值距離（cityblock）：d（x，y）=（■xi-yi

特別地當(dāng)xi∈0，1yi∈0，1 此時又稱漢明距離；

余弦距離（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個點，m∈s1為黑色（值為0），則s2中的第m-1，m，m+1個位置中必然存在不為白色的點（值255）；同理：如果此時s2處非邊緣的第n個點，n∈b為黑色（值為0），則s1中的第m-1，m，m+1個位置中必然存在不為白色的點（值255）。

證明：由“.bmp“圖片格式灰度（值0～255）特性即證。

圖3 碎紙片匹配示意圖

因為這是圖像匹配[1]的必要條件，即不滿足這個條件必定不能匹配，滿足條件為可能匹配的碎紙片。假設(shè)滿足條件中的碎紙片矩陣集合為an■，i∈N■，則如果i=1，則這一個唯一確定的匹配。如果i>1，則需要人工干預(yù)，找出匹配度最高的碎紙片。

定理2. 假設(shè)a1和a2分別為“.bmp”圖片格式兩碎紙片的矩陣，s1為a1最右側(cè)列，s2為a2的最左側(cè)列，定義絕對值差異度

d（S1，S2）=■S1i-S2i，其中S1=（S11，S12，…，S1n），S2=（S21，S22，…，S2n）

5 碎片拼接Matlab GUI軟件包

運用前面三節(jié)的內(nèi)容，我們設(shè)計了碎片拼接Matlab GUI軟件包， 根據(jù)聚類分析K均值距離公式的不同，我們設(shè)計了如下參數(shù)設(shè)置界面：

圖4 k-means參數(shù)設(shè)置界面

點擊圖4的確定按鈕后，彈出圖5行內(nèi)拼接界面。

圖5 行內(nèi)拼接界面

完成行內(nèi)拼接后，點擊“下一步”，出現(xiàn)行間拼接界面，最后生成完整的紙張。

圖6 行間拼接界面

參考文獻

[1]莊俊東.基于數(shù)字圖像處理的人民幣碎紙片拼接方法的研究[D].上海交通大學(xué)，2010.

[2]張翠.基于點線的文檔圖片數(shù)字水印與碎紙片拼接[D].中國海洋大學(xué)，2011.

[3]葛巧瑞.自然場景下的文字分割及識別研究[D].西安電子科技大學(xué)，2011.

[4]呂曉玲，謝邦昌.數(shù)據(jù)挖掘方法與應(yīng)用[M].北京：中國人民大學(xué)出版社，2009.endprint

摘 要：文章詳細闡述了基于Matlab GUI對單面印刷文檔經(jīng)碎紙機破碎的碎片（既縱切又橫切）的恢復(fù)，結(jié)合計算機對碎片的匹配搜索和人工干預(yù)，提高文檔恢復(fù)的效率，達到文檔的恢復(fù)。

關(guān)鍵詞：Matlab GUI；聚類分析；人工干預(yù)

1 概述

破碎文件的拼接在司法物證復(fù)原、歷史文獻修復(fù)以及軍事情報獲取等領(lǐng)域都有著重要的應(yīng)用。傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準確率較高，但效率很低。特別是，當(dāng)碎紙片數(shù)量巨大，人工拼接很難在短時間內(nèi)完成任務(wù)[1-3]。

隨著計算機技術(shù)的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術(shù)，以提高拼接復(fù)原效率。文章基于Matlab GUI對破碎文檔（既縱切又橫切）的復(fù)原實現(xiàn)人機互動，并給出了提高文檔復(fù)原效率的方法。

2 圖像采樣

圖象采樣就是按照圖像空間的坐標測量該坐標測量該位置上像素的灰度值。方法如下：對連續(xù)的f（x，y）進行等間隔采樣，在（x，y）平面上，將圖像均分成均勻的小網(wǎng)格，每個小網(wǎng)格的位置可以用整數(shù)坐標表示，于是采樣值就對應(yīng)于一個M×N數(shù)字矩陣。這樣就獲得了數(shù)字圖像中關(guān)于像素的兩個屬性：位置和灰度。位置由采樣點的兩個坐標確定，也就對應(yīng)了網(wǎng)格行和列；而灰度表明了該像素的明暗程度。Matlab讀入圖象的函數(shù)為imread（filename，format）。而文章討論的碎片圖像格式為bmp的8位灰度圖像，每一像素的取值范圍為0～255。

3 碎片的分類

3.1 碎片特征提取

準確地確定碎片的特征對碎片的分類起著重要作用，原始的碎片圖像中可利用的像素點較多，而碎片圖像中能有效反應(yīng)碎片的特征的像素需要恰到好處地提取。文字的筆畫有粗細之分，由此，不考慮筆畫的粗細，文字的輪廓更能體現(xiàn)碎片的特征。運用邊緣檢測的方法，實現(xiàn)對文字輪廓的確定。

（a） （b）

圖1 邊緣化處理前后對比圖

將每行邊緣輪廓像素通過累加法，得到一個180維的向量。邊緣輪廓像素在180維的向量的每一分量的值呈現(xiàn)一定的規(guī)律，圖2為圖1（a）的累加向量。

3.2 K-Means聚類分析方法

K-Means聚類指基于劃分的聚類分析[4]，事先需要制定將數(shù)據(jù)分為幾類，給定一個有n個個體的數(shù)據(jù)集，將它劃分為K個簇（k？燮n），使每個簇具有較高的相似度，而簇間的相似度較低。它需要滿足以下兩個條件：（1）K類中任意一類不為空集，即每一類至少有一個個體；（2）每一個體都屬于且僅屬于K類中的一類。

其中相似度的計算：根據(jù)一個簇中點的平均值（被看作簇的重心）來進行。K-means聚類算法的描述和處理流程如下：K-means是用于劃分的K均值算法，每個簇的中點用簇中對象的均值表示，其輸入為簇的數(shù)目K和包含n個對象的數(shù)據(jù)集，輸出為K個簇的集合，使得平方誤差準則最小。原理如下：

（1）首先為每個聚類確定一個初始聚類中心，這樣就有K個初始聚類中心；（2）將樣本集中的樣本按照最小距離原則分配到最鄰近聚類；（3）使用每個聚類中的樣本均值作為新的聚類中心；（4）重復(fù)步驟（2）和（3）直到聚類中心不再變化；（5）結(jié)束，得到K個聚類。

將樣本分配到距離他們最近的中心向量，并使目標函數(shù)值最小，K-means算法的目標函數(shù)通?？梢员硎緸椋?/p>

E=■■P-m■■

式中，E是數(shù)據(jù)集中所有對象的平方誤差和；P是數(shù)據(jù)對象，文章表示給定對象的像素特征值；mi是Ci的均值（P和mi都是多維）；P-m■■表示P與mi之間的度量。通過求這個目標函數(shù)E的最小值來試圖使生成的結(jié)果簇盡可能地緊湊和獨立。

對于度量，形象地說就是我們主要考慮的樣本間的差異。在數(shù)據(jù)分析和數(shù)據(jù)挖掘的過程中，我們經(jīng)常需要知道個體間差異的大小，進而評價個體的相似性和類別。我們要比較個體x和個體y間的差異，它們都包含了n個維的特征，即x（x1，x2，…，xn），y=（y1，y2，…，yn），如下幾種距離主要衡量兩者的差異，其中d（x，y）越小，即樣本x，y之間的距離越小，樣本x，y越相似，差異度越?。环粗?，越大。

歐幾里得距離（sqEuclidean）：d（x，y）=（■（xi-yi）2）1/2

絕對值距離（cityblock）：d（x，y）=（■xi-yi

特別地當(dāng)xi∈0，1yi∈0，1 此時又稱漢明距離；

余弦距離（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個點，m∈s1為黑色（值為0），則s2中的第m-1，m，m+1個位置中必然存在不為白色的點（值255）；同理：如果此時s2處非邊緣的第n個點，n∈b為黑色（值為0），則s1中的第m-1，m，m+1個位置中必然存在不為白色的點（值255）。

證明：由“.bmp“圖片格式灰度（值0～255）特性即證。

圖3 碎紙片匹配示意圖

因為這是圖像匹配[1]的必要條件，即不滿足這個條件必定不能匹配，滿足條件為可能匹配的碎紙片。假設(shè)滿足條件中的碎紙片矩陣集合為an■，i∈N■，則如果i=1，則這一個唯一確定的匹配。如果i>1，則需要人工干預(yù)，找出匹配度最高的碎紙片。

定理2. 假設(shè)a1和a2分別為“.bmp”圖片格式兩碎紙片的矩陣，s1為a1最右側(cè)列，s2為a2的最左側(cè)列，定義絕對值差異度

d（S1，S2）=■S1i-S2i，其中S1=（S11，S12，…，S1n），S2=（S21，S22，…，S2n）

5 碎片拼接Matlab GUI軟件包

運用前面三節(jié)的內(nèi)容，我們設(shè)計了碎片拼接Matlab GUI軟件包， 根據(jù)聚類分析K均值距離公式的不同，我們設(shè)計了如下參數(shù)設(shè)置界面：

圖4 k-means參數(shù)設(shè)置界面

點擊圖4的確定按鈕后，彈出圖5行內(nèi)拼接界面。

圖5 行內(nèi)拼接界面

完成行內(nèi)拼接后，點擊“下一步”，出現(xiàn)行間拼接界面，最后生成完整的紙張。

圖6 行間拼接界面

參考文獻

[1]莊俊東.基于數(shù)字圖像處理的人民幣碎紙片拼接方法的研究[D].上海交通大學(xué)，2010.

[2]張翠.基于點線的文檔圖片數(shù)字水印與碎紙片拼接[D].中國海洋大學(xué)，2011.

[3]葛巧瑞.自然場景下的文字分割及識別研究[D].西安電子科技大學(xué)，2011.

[4]呂曉玲，謝邦昌.數(shù)據(jù)挖掘方法與應(yīng)用[M].北京：中國人民大學(xué)出版社，2009.endprint

摘 要：文章詳細闡述了基于Matlab GUI對單面印刷文檔經(jīng)碎紙機破碎的碎片（既縱切又橫切）的恢復(fù)，結(jié)合計算機對碎片的匹配搜索和人工干預(yù)，提高文檔恢復(fù)的效率，達到文檔的恢復(fù)。

關(guān)鍵詞：Matlab GUI；聚類分析；人工干預(yù)

1 概述

破碎文件的拼接在司法物證復(fù)原、歷史文獻修復(fù)以及軍事情報獲取等領(lǐng)域都有著重要的應(yīng)用。傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準確率較高，但效率很低。特別是，當(dāng)碎紙片數(shù)量巨大，人工拼接很難在短時間內(nèi)完成任務(wù)[1-3]。

隨著計算機技術(shù)的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術(shù)，以提高拼接復(fù)原效率。文章基于Matlab GUI對破碎文檔（既縱切又橫切）的復(fù)原實現(xiàn)人機互動，并給出了提高文檔復(fù)原效率的方法。

2 圖像采樣

圖象采樣就是按照圖像空間的坐標測量該坐標測量該位置上像素的灰度值。方法如下：對連續(xù)的f（x，y）進行等間隔采樣，在（x，y）平面上，將圖像均分成均勻的小網(wǎng)格，每個小網(wǎng)格的位置可以用整數(shù)坐標表示，于是采樣值就對應(yīng)于一個M×N數(shù)字矩陣。這樣就獲得了數(shù)字圖像中關(guān)于像素的兩個屬性：位置和灰度。位置由采樣點的兩個坐標確定，也就對應(yīng)了網(wǎng)格行和列；而灰度表明了該像素的明暗程度。Matlab讀入圖象的函數(shù)為imread（filename，format）。而文章討論的碎片圖像格式為bmp的8位灰度圖像，每一像素的取值范圍為0～255。

3 碎片的分類

3.1 碎片特征提取

準確地確定碎片的特征對碎片的分類起著重要作用，原始的碎片圖像中可利用的像素點較多，而碎片圖像中能有效反應(yīng)碎片的特征的像素需要恰到好處地提取。文字的筆畫有粗細之分，由此，不考慮筆畫的粗細，文字的輪廓更能體現(xiàn)碎片的特征。運用邊緣檢測的方法，實現(xiàn)對文字輪廓的確定。

（a） （b）

圖1 邊緣化處理前后對比圖

將每行邊緣輪廓像素通過累加法，得到一個180維的向量。邊緣輪廓像素在180維的向量的每一分量的值呈現(xiàn)一定的規(guī)律，圖2為圖1（a）的累加向量。

3.2 K-Means聚類分析方法

K-Means聚類指基于劃分的聚類分析[4]，事先需要制定將數(shù)據(jù)分為幾類，給定一個有n個個體的數(shù)據(jù)集，將它劃分為K個簇（k？燮n），使每個簇具有較高的相似度，而簇間的相似度較低。它需要滿足以下兩個條件：（1）K類中任意一類不為空集，即每一類至少有一個個體；（2）每一個體都屬于且僅屬于K類中的一類。

其中相似度的計算：根據(jù)一個簇中點的平均值（被看作簇的重心）來進行。K-means聚類算法的描述和處理流程如下：K-means是用于劃分的K均值算法，每個簇的中點用簇中對象的均值表示，其輸入為簇的數(shù)目K和包含n個對象的數(shù)據(jù)集，輸出為K個簇的集合，使得平方誤差準則最小。原理如下：

（1）首先為每個聚類確定一個初始聚類中心，這樣就有K個初始聚類中心；（2）將樣本集中的樣本按照最小距離原則分配到最鄰近聚類；（3）使用每個聚類中的樣本均值作為新的聚類中心；（4）重復(fù)步驟（2）和（3）直到聚類中心不再變化；（5）結(jié)束，得到K個聚類。

將樣本分配到距離他們最近的中心向量，并使目標函數(shù)值最小，K-means算法的目標函數(shù)通?？梢员硎緸椋?/p>

E=■■P-m■■

式中，E是數(shù)據(jù)集中所有對象的平方誤差和；P是數(shù)據(jù)對象，文章表示給定對象的像素特征值；mi是Ci的均值（P和mi都是多維）；P-m■■表示P與mi之間的度量。通過求這個目標函數(shù)E的最小值來試圖使生成的結(jié)果簇盡可能地緊湊和獨立。

對于度量，形象地說就是我們主要考慮的樣本間的差異。在數(shù)據(jù)分析和數(shù)據(jù)挖掘的過程中，我們經(jīng)常需要知道個體間差異的大小，進而評價個體的相似性和類別。我們要比較個體x和個體y間的差異，它們都包含了n個維的特征，即x（x1，x2，…，xn），y=（y1，y2，…，yn），如下幾種距離主要衡量兩者的差異，其中d（x，y）越小，即樣本x，y之間的距離越小，樣本x，y越相似，差異度越小；反之，越大。

歐幾里得距離（sqEuclidean）：d（x，y）=（■（xi-yi）2）1/2

絕對值距離（cityblock）：d（x，y）=（■xi-yi

特別地當(dāng)xi∈0，1yi∈0，1 此時又稱漢明距離；

余弦距離（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個點，m∈s1為黑色（值為0），則s2中的第m-1，m，m+1個位置中必然存在不為白色的點（值255）；同理：如果此時s2處非邊緣的第n個點，n∈b為黑色（值為0），則s1中的第m-1，m，m+1個位置中必然存在不為白色的點（值255）。

證明：由“.bmp“圖片格式灰度（值0～255）特性即證。

圖3 碎紙片匹配示意圖

因為這是圖像匹配[1]的必要條件，即不滿足這個條件必定不能匹配，滿足條件為可能匹配的碎紙片。假設(shè)滿足條件中的碎紙片矩陣集合為an■，i∈N■，則如果i=1，則這一個唯一確定的匹配。如果i>1，則需要人工干預(yù)，找出匹配度最高的碎紙片。

定理2. 假設(shè)a1和a2分別為“.bmp”圖片格式兩碎紙片的矩陣，s1為a1最右側(cè)列，s2為a2的最左側(cè)列，定義絕對值差異度

d（S1，S2）=■S1i-S2i，其中S1=（S11，S12，…，S1n），S2=（S21，S22，…，S2n）

5 碎片拼接Matlab GUI軟件包

運用前面三節(jié)的內(nèi)容，我們設(shè)計了碎片拼接Matlab GUI軟件包， 根據(jù)聚類分析K均值距離公式的不同，我們設(shè)計了如下參數(shù)設(shè)置界面：

圖4 k-means參數(shù)設(shè)置界面

點擊圖4的確定按鈕后，彈出圖5行內(nèi)拼接界面。

圖5 行內(nèi)拼接界面

完成行內(nèi)拼接后，點擊“下一步”，出現(xiàn)行間拼接界面，最后生成完整的紙張。

圖6 行間拼接界面

參考文獻

[1]莊俊東.基于數(shù)字圖像處理的人民幣碎紙片拼接方法的研究[D].上海交通大學(xué)，2010.

[2]張翠.基于點線的文檔圖片數(shù)字水印與碎紙片拼接[D].中國海洋大學(xué)，2011.

[3]葛巧瑞.自然場景下的文字分割及識別研究[D].西安電子科技大學(xué)，2011.

[4]呂曉玲，謝邦昌.數(shù)據(jù)挖掘方法與應(yīng)用[M].北京：中國人民大學(xué)出版社，2009.endprint