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

沈釗弘++陳振邦

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

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

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

破碎文件的拼接在司法物證復(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ù)原效率。

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

用碎紙機(jī)粉碎的純文本文檔具有以下特點(diǎn)：

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

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

（3）不同碎紙片之間沒(méi)有重疊部分；

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

1 模型的假設(shè)

（1）待拼接的碎紙片來(lái)自同一頁(yè)印刷文字文件。

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

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

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

2 軟件設(shè)計(jì)原理

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

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

2.1.1 縱向切割碎片拼接

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

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

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

2.1.2 橫向切割碎片拼接

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

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

破碎文件的拼接在司法物證復(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ù)原效率。

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

用碎紙機(jī)粉碎的純文本文檔具有以下特點(diǎn)：

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

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

（3）不同碎紙片之間沒(méi)有重疊部分；

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

1 模型的假設(shè)

（1）待拼接的碎紙片來(lái)自同一頁(yè)印刷文字文件。

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

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

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

2 軟件設(shè)計(jì)原理

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

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

2.1.1 縱向切割碎片拼接

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

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

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

2.1.2 橫向切割碎片拼接

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

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

破碎文件的拼接在司法物證復(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ù)原效率。

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

用碎紙機(jī)粉碎的純文本文檔具有以下特點(diǎn)：

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

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

（3）不同碎紙片之間沒(méi)有重疊部分；

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

1 模型的假設(shè)

（1）待拼接的碎紙片來(lái)自同一頁(yè)印刷文字文件。

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

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

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

2 軟件設(shè)計(jì)原理

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

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

2.1.1 縱向切割碎片拼接

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

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

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

2.1.2 橫向切割碎片拼接

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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