基于文字特征的文檔碎紙片拼接軟件設(shè)計

沈釗弘++陳振邦

摘 要：將圖片進(jìn)行灰度處理，再轉(zhuǎn)化為0—1二值矩陣，利用矩陣行（列）偏差函數(shù)，建立基于最小二乘法的拼接模型。針對雙向切割碎片全局搜索的局限性，利用文字的行高和行間距的特征，建立相似度函數(shù)，并人工拼接出邊緣列，再多行并行拼接，然后逐次調(diào)整，最后復(fù)原；針對雙向切割的雙面打印碎片，先在碎紙中找出26個字母及各種標(biāo)點符號的完整字符，制作出模板，再利用該模板進(jìn)行匹配判定，借助人工拼接邊緣列，逐次手動調(diào)整，實現(xiàn)復(fù)原。

關(guān)鍵詞：二值法 最小二乘法 灰度 完整字符

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A 文章編號：1674-098X（2014）04（a）-0195-01

破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報獲取等領(lǐng)域都有著重要的應(yīng)用。傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準(zhǔn)確率較高，但效率很低。特別是當(dāng)碎片數(shù)量巨大，人工拼接很難在短時間內(nèi)完成任務(wù)。隨著計算機技術(shù)的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術(shù)，以提高拼接復(fù)原效率。

將不規(guī)則的文檔碎片進(jìn)行拼接，一般是利用碎紙片的邊緣曲線，尖點、尖角、面積等幾何特征，通過神經(jīng)網(wǎng)絡(luò)算法、蟻群算法等搜索與之匹配的相鄰碎紙片[2]。但對于邊緣形狀相似的碎紙片，這種基于邊界幾何特征的拼接方法就失效了，拼接時不但要考慮邊緣是否匹配，還要判斷碎片內(nèi)的文字內(nèi)容是否匹配。

用碎紙機粉碎的純文本文檔具有以下特點：

（1）所有碎紙片都是規(guī)則的矩形，且形狀完全相同；

（2）幾乎每張碎紙片都包含有文字；

（3）不同碎紙片之間沒有重疊部分；

針對以上特征，該文從文字特征入手，將碎紙片上的邊緣文字特征進(jìn)行匹配，即利用邊緣文字的像素進(jìn)行最優(yōu)化匹配。

1 模型的假設(shè)

（1）待拼接的碎紙片來自同一頁印刷文字文件。

（2）待拼接復(fù)原的碎紙片是規(guī)整的矩形。

（3）模型中的碎紙片長度、寬度和面積都相等。

（4）碎紙片的照片是同標(biāo)準(zhǔn)拍攝的。

2 軟件設(shè)計原理

先用對圖像進(jìn)行灰度值[1]轉(zhuǎn)換，得到每張碎片圖像的數(shù)值矩陣（數(shù)值在0～255），再通過二值法得到灰度閾值，將所有矩陣轉(zhuǎn)換成0-1矩陣。

2.1 單向切割碎片拼接模型的設(shè)計

2.1.1 縱向切割碎片拼接

設(shè)A、B分別為左右放置的兩張圖片對應(yīng)的數(shù)字矩陣，定義前一個矩陣與后一個矩陣的第一列之間的偏差函數(shù)為：

其中A（i，72），B（i，1）分別表示矩陣第72列和第1列的元素。

對于給定的矩陣A，若存在矩陣B，使得A與B之間的偏差函數(shù)達(dá)到最小，則A與B匹配，此時A與B對應(yīng)的圖片可以左右拼接。

2.1.2 橫向切割碎片拼接

類似地，設(shè)C、D分別為左右放置的兩張圖片對應(yīng)的數(shù)字矩陣，定義前一個矩陣與后一個矩陣的第一列之間的偏差函數(shù)為：

其中C（1980，j），D（1，j）分別表示矩陣C、D第1980行和第1行的元素。

對于給定的矩陣A，若存在矩陣B，使得A與B之間的偏差函數(shù)達(dá)到最小，則C與D匹配，此時C與D對應(yīng)的圖片可以左右拼接。

2.2 雙向切割碎片拼接模型的設(shè)計

由于雙向切割處理量較大，2.1的拼接方法復(fù)原率較低，因此，再考慮文本的打印特征，即行高和行間距。

首先對每張圖的文字像素進(jìn)行數(shù)據(jù)處理，逐行搜索（記第j行的白點數(shù)），當(dāng)白點數(shù)出現(xiàn)突變時，說明搜索到文字圖像的分界線，記錄下該行及相應(yīng)點數(shù)，作為行高特征數(shù)據(jù)，即

取每張圖的文字特征數(shù)集

具體實現(xiàn)原理如下圖所示，將像素值積分后得到綠色多峰曲線，再進(jìn)行平滑處理（如藍(lán)色曲線所示），從而得到行高值。

利用以上得到的數(shù)據(jù)，設(shè)兩圖片的邊界向量分別為m、n，則代入相關(guān)系數(shù)[3]求法可得到相關(guān)度函數(shù)L，即

以此作為判斷依據(jù)，從人工拼接得到的邊界列開始搜索，實現(xiàn)拼接。

2.3 雙向切割的雙面打印碎片拼接模型的設(shè)計

本功能只適用于英文文本。

首先制作26個字母及標(biāo)點符號的完整字符模板，通過聯(lián)通區(qū)域法，對存在完整字符的圖片駐點掃描，同為白色區(qū)域且位置相鄰的點構(gòu)成一個區(qū)域，搜索得到完整字符的數(shù)據(jù)矩陣。

再根據(jù)不同字體的需要，設(shè)置相似度閾值（即碎片與模板的相似程度閾值），拼接過程同2.2。

3 結(jié)語

從仿真實驗的結(jié)果可以看出，單向切割碎片的拼接功能能實現(xiàn)100%復(fù)原，雙向切割碎片的拼接能實現(xiàn)86%復(fù)原，雙向切割雙面打印碎片的拼接能實現(xiàn)96%的復(fù)原，因此該軟件能大幅度地提高拼接效率，為情報人員及相關(guān)工作人員節(jié)省時間和精力。但是，由于軟件的數(shù)學(xué)模型是通過一定的簡化所建立的，因此軟件的功能也具有一定的局限性，必須符合所有碎片只來自同一張紙的情況，工作人才可以使用此軟件。另外，軟件的后兩個功能人不能實現(xiàn)全自動，這也是該軟件需要改進(jìn)的地方。

參考文獻(xiàn)

[1] 李利軍，李云偉.基于圖像灰度的拼接技術(shù)研究[J].計算機與數(shù)學(xué)工程，2007， 35（9）：128-130.

[2] 賈海燕，朱良家，周宗潭，等.一種碎紙自動拼接中的形狀匹配方法[J].計算機仿真，2006，23（11）：180-183.

[3] 盛驟，謝式千.概率論與數(shù)理統(tǒng)計[M].4版.北京：高等教育出版社，2012.endprint

摘 要：將圖片進(jìn)行灰度處理，再轉(zhuǎn)化為0—1二值矩陣，利用矩陣行（列）偏差函數(shù)，建立基于最小二乘法的拼接模型。針對雙向切割碎片全局搜索的局限性，利用文字的行高和行間距的特征，建立相似度函數(shù)，并人工拼接出邊緣列，再多行并行拼接，然后逐次調(diào)整，最后復(fù)原；針對雙向切割的雙面打印碎片，先在碎紙中找出26個字母及各種標(biāo)點符號的完整字符，制作出模板，再利用該模板進(jìn)行匹配判定，借助人工拼接邊緣列，逐次手動調(diào)整，實現(xiàn)復(fù)原。

關(guān)鍵詞：二值法 最小二乘法 灰度 完整字符

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A 文章編號：1674-098X（2014）04（a）-0195-01

破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報獲取等領(lǐng)域都有著重要的應(yīng)用。傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準(zhǔn)確率較高，但效率很低。特別是當(dāng)碎片數(shù)量巨大，人工拼接很難在短時間內(nèi)完成任務(wù)。隨著計算機技術(shù)的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術(shù)，以提高拼接復(fù)原效率。

將不規(guī)則的文檔碎片進(jìn)行拼接，一般是利用碎紙片的邊緣曲線，尖點、尖角、面積等幾何特征，通過神經(jīng)網(wǎng)絡(luò)算法、蟻群算法等搜索與之匹配的相鄰碎紙片[2]。但對于邊緣形狀相似的碎紙片，這種基于邊界幾何特征的拼接方法就失效了，拼接時不但要考慮邊緣是否匹配，還要判斷碎片內(nèi)的文字內(nèi)容是否匹配。

用碎紙機粉碎的純文本文檔具有以下特點：

（1）所有碎紙片都是規(guī)則的矩形，且形狀完全相同；

（2）幾乎每張碎紙片都包含有文字；

（3）不同碎紙片之間沒有重疊部分；

針對以上特征，該文從文字特征入手，將碎紙片上的邊緣文字特征進(jìn)行匹配，即利用邊緣文字的像素進(jìn)行最優(yōu)化匹配。

1 模型的假設(shè)

（1）待拼接的碎紙片來自同一頁印刷文字文件。

（2）待拼接復(fù)原的碎紙片是規(guī)整的矩形。

（3）模型中的碎紙片長度、寬度和面積都相等。

（4）碎紙片的照片是同標(biāo)準(zhǔn)拍攝的。

2 軟件設(shè)計原理

先用對圖像進(jìn)行灰度值[1]轉(zhuǎn)換，得到每張碎片圖像的數(shù)值矩陣（數(shù)值在0～255），再通過二值法得到灰度閾值，將所有矩陣轉(zhuǎn)換成0-1矩陣。

2.1 單向切割碎片拼接模型的設(shè)計

2.1.1 縱向切割碎片拼接

設(shè)A、B分別為左右放置的兩張圖片對應(yīng)的數(shù)字矩陣，定義前一個矩陣與后一個矩陣的第一列之間的偏差函數(shù)為：

其中A（i，72），B（i，1）分別表示矩陣第72列和第1列的元素。

對于給定的矩陣A，若存在矩陣B，使得A與B之間的偏差函數(shù)達(dá)到最小，則A與B匹配，此時A與B對應(yīng)的圖片可以左右拼接。

2.1.2 橫向切割碎片拼接

類似地，設(shè)C、D分別為左右放置的兩張圖片對應(yīng)的數(shù)字矩陣，定義前一個矩陣與后一個矩陣的第一列之間的偏差函數(shù)為：

其中C（1980，j），D（1，j）分別表示矩陣C、D第1980行和第1行的元素。

對于給定的矩陣A，若存在矩陣B，使得A與B之間的偏差函數(shù)達(dá)到最小，則C與D匹配，此時C與D對應(yīng)的圖片可以左右拼接。

2.2 雙向切割碎片拼接模型的設(shè)計

由于雙向切割處理量較大，2.1的拼接方法復(fù)原率較低，因此，再考慮文本的打印特征，即行高和行間距。

首先對每張圖的文字像素進(jìn)行數(shù)據(jù)處理，逐行搜索（記第j行的白點數(shù)），當(dāng)白點數(shù)出現(xiàn)突變時，說明搜索到文字圖像的分界線，記錄下該行及相應(yīng)點數(shù)，作為行高特征數(shù)據(jù)，即

取每張圖的文字特征數(shù)集

具體實現(xiàn)原理如下圖所示，將像素值積分后得到綠色多峰曲線，再進(jìn)行平滑處理（如藍(lán)色曲線所示），從而得到行高值。

利用以上得到的數(shù)據(jù)，設(shè)兩圖片的邊界向量分別為m、n，則代入相關(guān)系數(shù)[3]求法可得到相關(guān)度函數(shù)L，即

以此作為判斷依據(jù)，從人工拼接得到的邊界列開始搜索，實現(xiàn)拼接。

2.3 雙向切割的雙面打印碎片拼接模型的設(shè)計

本功能只適用于英文文本。

首先制作26個字母及標(biāo)點符號的完整字符模板，通過聯(lián)通區(qū)域法，對存在完整字符的圖片駐點掃描，同為白色區(qū)域且位置相鄰的點構(gòu)成一個區(qū)域，搜索得到完整字符的數(shù)據(jù)矩陣。

再根據(jù)不同字體的需要，設(shè)置相似度閾值（即碎片與模板的相似程度閾值），拼接過程同2.2。

3 結(jié)語

從仿真實驗的結(jié)果可以看出，單向切割碎片的拼接功能能實現(xiàn)100%復(fù)原，雙向切割碎片的拼接能實現(xiàn)86%復(fù)原，雙向切割雙面打印碎片的拼接能實現(xiàn)96%的復(fù)原，因此該軟件能大幅度地提高拼接效率，為情報人員及相關(guān)工作人員節(jié)省時間和精力。但是，由于軟件的數(shù)學(xué)模型是通過一定的簡化所建立的，因此軟件的功能也具有一定的局限性，必須符合所有碎片只來自同一張紙的情況，工作人才可以使用此軟件。另外，軟件的后兩個功能人不能實現(xiàn)全自動，這也是該軟件需要改進(jìn)的地方。

參考文獻(xiàn)

[1] 李利軍，李云偉.基于圖像灰度的拼接技術(shù)研究[J].計算機與數(shù)學(xué)工程，2007， 35（9）：128-130.

[2] 賈海燕，朱良家，周宗潭，等.一種碎紙自動拼接中的形狀匹配方法[J].計算機仿真，2006，23（11）：180-183.

[3] 盛驟，謝式千.概率論與數(shù)理統(tǒng)計[M].4版.北京：高等教育出版社，2012.endprint

摘 要：將圖片進(jìn)行灰度處理，再轉(zhuǎn)化為0—1二值矩陣，利用矩陣行（列）偏差函數(shù)，建立基于最小二乘法的拼接模型。針對雙向切割碎片全局搜索的局限性，利用文字的行高和行間距的特征，建立相似度函數(shù)，并人工拼接出邊緣列，再多行并行拼接，然后逐次調(diào)整，最后復(fù)原；針對雙向切割的雙面打印碎片，先在碎紙中找出26個字母及各種標(biāo)點符號的完整字符，制作出模板，再利用該模板進(jìn)行匹配判定，借助人工拼接邊緣列，逐次手動調(diào)整，實現(xiàn)復(fù)原。

關(guān)鍵詞：二值法 最小二乘法 灰度 完整字符

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A 文章編號：1674-098X（2014）04（a）-0195-01

破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報獲取等領(lǐng)域都有著重要的應(yīng)用。傳統(tǒng)上，拼接復(fù)原工作需由人工完成，準(zhǔn)確率較高，但效率很低。特別是當(dāng)碎片數(shù)量巨大，人工拼接很難在短時間內(nèi)完成任務(wù)。隨著計算機技術(shù)的發(fā)展，人們試圖開發(fā)碎紙片的自動拼接技術(shù)，以提高拼接復(fù)原效率。

將不規(guī)則的文檔碎片進(jìn)行拼接，一般是利用碎紙片的邊緣曲線，尖點、尖角、面積等幾何特征，通過神經(jīng)網(wǎng)絡(luò)算法、蟻群算法等搜索與之匹配的相鄰碎紙片[2]。但對于邊緣形狀相似的碎紙片，這種基于邊界幾何特征的拼接方法就失效了，拼接時不但要考慮邊緣是否匹配，還要判斷碎片內(nèi)的文字內(nèi)容是否匹配。

用碎紙機粉碎的純文本文檔具有以下特點：

（1）所有碎紙片都是規(guī)則的矩形，且形狀完全相同；

（2）幾乎每張碎紙片都包含有文字；

（3）不同碎紙片之間沒有重疊部分；

針對以上特征，該文從文字特征入手，將碎紙片上的邊緣文字特征進(jìn)行匹配，即利用邊緣文字的像素進(jìn)行最優(yōu)化匹配。

1 模型的假設(shè)

（1）待拼接的碎紙片來自同一頁印刷文字文件。

（2）待拼接復(fù)原的碎紙片是規(guī)整的矩形。

（3）模型中的碎紙片長度、寬度和面積都相等。

（4）碎紙片的照片是同標(biāo)準(zhǔn)拍攝的。

2 軟件設(shè)計原理

先用對圖像進(jìn)行灰度值[1]轉(zhuǎn)換，得到每張碎片圖像的數(shù)值矩陣（數(shù)值在0～255），再通過二值法得到灰度閾值，將所有矩陣轉(zhuǎn)換成0-1矩陣。

2.1 單向切割碎片拼接模型的設(shè)計

2.1.1 縱向切割碎片拼接

設(shè)A、B分別為左右放置的兩張圖片對應(yīng)的數(shù)字矩陣，定義前一個矩陣與后一個矩陣的第一列之間的偏差函數(shù)為：

其中A（i，72），B（i，1）分別表示矩陣第72列和第1列的元素。

對于給定的矩陣A，若存在矩陣B，使得A與B之間的偏差函數(shù)達(dá)到最小，則A與B匹配，此時A與B對應(yīng)的圖片可以左右拼接。

2.1.2 橫向切割碎片拼接

類似地，設(shè)C、D分別為左右放置的兩張圖片對應(yīng)的數(shù)字矩陣，定義前一個矩陣與后一個矩陣的第一列之間的偏差函數(shù)為：

其中C（1980，j），D（1，j）分別表示矩陣C、D第1980行和第1行的元素。

對于給定的矩陣A，若存在矩陣B，使得A與B之間的偏差函數(shù)達(dá)到最小，則C與D匹配，此時C與D對應(yīng)的圖片可以左右拼接。

2.2 雙向切割碎片拼接模型的設(shè)計

由于雙向切割處理量較大，2.1的拼接方法復(fù)原率較低，因此，再考慮文本的打印特征，即行高和行間距。

首先對每張圖的文字像素進(jìn)行數(shù)據(jù)處理，逐行搜索（記第j行的白點數(shù)），當(dāng)白點數(shù)出現(xiàn)突變時，說明搜索到文字圖像的分界線，記錄下該行及相應(yīng)點數(shù)，作為行高特征數(shù)據(jù)，即

取每張圖的文字特征數(shù)集

具體實現(xiàn)原理如下圖所示，將像素值積分后得到綠色多峰曲線，再進(jìn)行平滑處理（如藍(lán)色曲線所示），從而得到行高值。

利用以上得到的數(shù)據(jù)，設(shè)兩圖片的邊界向量分別為m、n，則代入相關(guān)系數(shù)[3]求法可得到相關(guān)度函數(shù)L，即

以此作為判斷依據(jù)，從人工拼接得到的邊界列開始搜索，實現(xiàn)拼接。

2.3 雙向切割的雙面打印碎片拼接模型的設(shè)計

本功能只適用于英文文本。

首先制作26個字母及標(biāo)點符號的完整字符模板，通過聯(lián)通區(qū)域法，對存在完整字符的圖片駐點掃描，同為白色區(qū)域且位置相鄰的點構(gòu)成一個區(qū)域，搜索得到完整字符的數(shù)據(jù)矩陣。

再根據(jù)不同字體的需要，設(shè)置相似度閾值（即碎片與模板的相似程度閾值），拼接過程同2.2。

3 結(jié)語

從仿真實驗的結(jié)果可以看出，單向切割碎片的拼接功能能實現(xiàn)100%復(fù)原，雙向切割碎片的拼接能實現(xiàn)86%復(fù)原，雙向切割雙面打印碎片的拼接能實現(xiàn)96%的復(fù)原，因此該軟件能大幅度地提高拼接效率，為情報人員及相關(guān)工作人員節(jié)省時間和精力。但是，由于軟件的數(shù)學(xué)模型是通過一定的簡化所建立的，因此軟件的功能也具有一定的局限性，必須符合所有碎片只來自同一張紙的情況，工作人才可以使用此軟件。另外，軟件的后兩個功能人不能實現(xiàn)全自動，這也是該軟件需要改進(jìn)的地方。

參考文獻(xiàn)

[1] 李利軍，李云偉.基于圖像灰度的拼接技術(shù)研究[J].計算機與數(shù)學(xué)工程，2007， 35（9）：128-130.

[2] 賈海燕，朱良家，周宗潭，等.一種碎紙自動拼接中的形狀匹配方法[J].計算機仿真，2006，23（11）：180-183.

[3] 盛驟，謝式千.概率論與數(shù)理統(tǒng)計[M].4版.北京：高等教育出版社，2012.endprint