基于Matlab GUI碎紙機破碎文檔的恢復

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

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

關鍵詞：Matlab GUI；聚類分析；人工干預

1 概述

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

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

2 圖像采樣

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

3 碎片的分類

3.1 碎片特征提取

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

（a） （b）

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

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

3.2 K-Means聚類分析方法

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

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

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

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

E=■■P-m■■

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

對于度量，形象地說就是我們主要考慮的樣本間的差異。在數據分析和數據挖掘的過程中，我們經常需要知道個體間差異的大小，進而評價個體的相似性和類別。我們要比較個體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

特別地當xi∈0，1yi∈0，1 此時又稱漢明距離；

余弦距離（cosine）：d（x，y）=（■xi，yi）/（（■xi2）1/2（■yi2）1/2）

4 碎片匹配

根據碎片鄰接原理以及圖片格式的性質，我們給出了如下定理：

定理1. 假設a1和a2分別為“.bmp”圖片格式兩碎紙片的矩陣（如圖5），s1為a1最右側列，s2為a2的最左側列，如果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]的必要條件，即不滿足這個條件必定不能匹配，滿足條件為可能匹配的碎紙片。假設滿足條件中的碎紙片矩陣集合為an■，i∈N■，則如果i=1，則這一個唯一確定的匹配。如果i>1，則需要人工干預，找出匹配度最高的碎紙片。

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

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

5 碎片拼接Matlab GUI軟件包

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

圖4 k-means參數設置界面

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

圖5 行內拼接界面

完成行內拼接后，點擊“下一步”，出現行間拼接界面，最后生成完整的紙張。

圖6 行間拼接界面

參考文獻

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

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

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

[4]呂曉玲，謝邦昌.數據挖掘方法與應用[M].北京：中國人民大學出版社，2009.endprint

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

關鍵詞：Matlab GUI；聚類分析；人工干預

1 概述

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

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

2 圖像采樣

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

3 碎片的分類

3.1 碎片特征提取

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

（a） （b）

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

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

3.2 K-Means聚類分析方法

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

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

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

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

E=■■P-m■■

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

對于度量，形象地說就是我們主要考慮的樣本間的差異。在數據分析和數據挖掘的過程中，我們經常需要知道個體間差異的大小，進而評價個體的相似性和類別。我們要比較個體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

特別地當xi∈0，1yi∈0，1 此時又稱漢明距離；

余弦距離（cosine）：d（x，y）=（■xi，yi）/（（■xi2）1/2（■yi2）1/2）

4 碎片匹配

根據碎片鄰接原理以及圖片格式的性質，我們給出了如下定理：

定理1. 假設a1和a2分別為“.bmp”圖片格式兩碎紙片的矩陣（如圖5），s1為a1最右側列，s2為a2的最左側列，如果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]的必要條件，即不滿足這個條件必定不能匹配，滿足條件為可能匹配的碎紙片。假設滿足條件中的碎紙片矩陣集合為an■，i∈N■，則如果i=1，則這一個唯一確定的匹配。如果i>1，則需要人工干預，找出匹配度最高的碎紙片。

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

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

5 碎片拼接Matlab GUI軟件包

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

圖4 k-means參數設置界面

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

圖5 行內拼接界面

完成行內拼接后，點擊“下一步”，出現行間拼接界面，最后生成完整的紙張。

圖6 行間拼接界面

參考文獻

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

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

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

[4]呂曉玲，謝邦昌.數據挖掘方法與應用[M].北京：中國人民大學出版社，2009.endprint

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

關鍵詞：Matlab GUI；聚類分析；人工干預

1 概述

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

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

2 圖像采樣

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

3 碎片的分類

3.1 碎片特征提取

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

（a） （b）

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

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

3.2 K-Means聚類分析方法

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

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

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

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

E=■■P-m■■

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

對于度量，形象地說就是我們主要考慮的樣本間的差異。在數據分析和數據挖掘的過程中，我們經常需要知道個體間差異的大小，進而評價個體的相似性和類別。我們要比較個體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

特別地當xi∈0，1yi∈0，1 此時又稱漢明距離；

余弦距離（cosine）：d（x，y）=（■xi，yi）/（（■xi2）1/2（■yi2）1/2）

4 碎片匹配

根據碎片鄰接原理以及圖片格式的性質，我們給出了如下定理：

定理1. 假設a1和a2分別為“.bmp”圖片格式兩碎紙片的矩陣（如圖5），s1為a1最右側列，s2為a2的最左側列，如果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]的必要條件，即不滿足這個條件必定不能匹配，滿足條件為可能匹配的碎紙片。假設滿足條件中的碎紙片矩陣集合為an■，i∈N■，則如果i=1，則這一個唯一確定的匹配。如果i>1，則需要人工干預，找出匹配度最高的碎紙片。

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

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

5 碎片拼接Matlab GUI軟件包

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

圖4 k-means參數設置界面

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

圖5 行內拼接界面

完成行內拼接后，點擊“下一步”，出現行間拼接界面，最后生成完整的紙張。

圖6 行間拼接界面

參考文獻

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

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

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

[4]呂曉玲，謝邦昌.數據挖掘方法與應用[M].北京：中國人民大學出版社，2009.endprint