基于相似度分析的碎紙片拼接復(fù)原

孫鵬程+耿大猛+常晶晶+王玲

摘 要：現(xiàn)實(shí)生活中，傳統(tǒng)拼接復(fù)原工作需要手動拼接，雖準(zhǔn)確度較高，但拼接難度較大，效率較低，特別是當(dāng)碎片的數(shù)量極大時(shí)，人工手動拼接工作將很難在短時(shí)間內(nèi)完成。基于上述背景，該文利用matlab軟件，對碎紙片二值化矩陣中的邊緣矩陣進(jìn)行提取，為減少拼接工作量，該文通過觀察并計(jì)算出文檔中最左端碎片的排列方式，最后應(yīng)用統(tǒng)計(jì)學(xué)中的相關(guān)系數(shù)最大的條件找到最左端碎片的最佳匹配行，并以此方法完成拼接，得到的拼接結(jié)果較為完整，證明方法拼接效果良好。

關(guān)鍵詞：圖像識別 二值化 相關(guān)系數(shù) 邊緣矩陣

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-3791（2017）01（b）-0040-02

傳統(tǒng)人手撕碎片總是無規(guī)則的，其拼接一般是利用基于碎片幾何特征的方法，但這種方法對邊緣規(guī)則的碎片的拼接效果不是很理想，該文針對目前碎片拼接領(lǐng)域存在的這種不足，進(jìn)行完善并設(shè)計(jì)了拼接邊緣規(guī)則碎片的方法。

該文利用研究出的拼接邊緣規(guī)則碎片的方法，解決2013年數(shù)學(xué)建模國賽B題的碎片拼接問題，對附件中給出的209張橫縱切中英文碎片進(jìn)行二值化處理，然后對得到的邊緣矩陣進(jìn)行相關(guān)分析，依據(jù)相關(guān)性分析完成最終的拼接。

1 圖像處理及分析

灰度變換指黑白圖片的黑白變換或者彩色圖片的色彩變換，一張彩色圖片的像素矩陣中的每個(gè)像素由RGB 3種顏色按照規(guī)定比例混合而成的一種顏色表示，在處理圖像時(shí)，RGB會由于環(huán)境光源太暗而偏小，造成圖像不清晰，若光源太亮，則會導(dǎo)致圖像曝光率太高而泛白，該文通過灰度變換方法，將RGB值調(diào)到合適的程度。灰度RGB的范圍是0～255，表示亮度從深到淺，對應(yīng)圖像中的顏色從黑到白。該文運(yùn)用matlab軟件對209張碎紙片分別進(jìn)行灰度處理。

2 相似度分析

二值化處理是指通過對灰度變換后的圖像設(shè)定閾值而將RGB灰度值分為兩部分，并分別用0、1表示，最終得到二值化矩陣的方法。該文通過對209張既橫切又縱切的碎片進(jìn)行二值化處理，得到每張碎片的上下左右邊緣矩陣，通過matlab編程對邊緣矩陣的數(shù)值進(jìn)行獲取，若碎片中的文字被橫切或縱切，利用統(tǒng)計(jì)方法對所有碎片的上下、左右邊緣矩陣分別進(jìn)行相關(guān)性分析，并計(jì)算出兩邊緣矩陣的相關(guān)系數(shù)，計(jì)算順序?yàn)閺纳系较禄驈淖蟮接遥x取其中相關(guān)系數(shù)最大的兩張碎片即為能夠互相匹配的碎片，計(jì)算方法為，例如：中文碎片049、054、065、143、186、002、057能夠拼接在同在一行，碎片左右邊緣相關(guān)系數(shù)為0.921 4、0.894 7、0.912 3、0.945 3、0.856 8、0.883 6，經(jīng)觀察比較，上述相關(guān)系數(shù)均為同比系數(shù)中最大。圖1、2為兩張完成拼接的碎片，觀察其拼接之后的“斷”“a”，可發(fā)現(xiàn)其邊緣矩陣的相似性。

3 確定文檔首列

首先進(jìn)行首列的選取，由于第一列每張碎片左邊緣矩陣中空白行列數(shù)為一固定值，據(jù)此條件在209張碎片中選取出第一列中的11張碎片，具體操作方案為：通過matlab編程確定出每張碎片的二值化矩陣，并對這些數(shù)據(jù)進(jìn)行篩選，統(tǒng)計(jì)出209張碎片中的左邊緣空白矩陣的個(gè)數(shù)，得出眾數(shù)為中文11個(gè)，英文14個(gè)，其中左邊緣矩陣個(gè)數(shù)恰為眾數(shù)的碎片即為備選碎片，最后通過人工干預(yù)選出第一列中的11張碎片；其次對選出的11張碎片進(jìn)行排列，對于材料中的中文碎片，可分析每個(gè)漢字縱向最大占有距離為40個(gè)像素點(diǎn)，中文行間距最大占有距離為30個(gè)像素點(diǎn)，如圖3所示，然后將第一列的碎片分為兩類：一類是橫向切割處為漢字；另一類是橫向切割處為空白行。對于第一類，擬采用相關(guān)系數(shù)法進(jìn)行拼接，進(jìn)行縱向排序；對于第二類碎片的拼接方法，根據(jù)兩相鄰行字符之間空白最大占有距離為30個(gè)像素點(diǎn)的條件，用matlab進(jìn)行分析計(jì)算得到與待匹配碎片匹配度最高的碎片。對于材料中的英文碎片，由于每個(gè)英文字母大小不一，故將其放入四線三格中表示，并發(fā)現(xiàn)所有英文字母均占滿四線三格中的第二格，據(jù)此觀察二值化矩陣中，四線三格的中間行所占最大像素點(diǎn)行數(shù)為25，由此確定四線三格的具體分布，如圖4所示，任意一個(gè)英文圖片碎片，通過matlab從文檔上邊界進(jìn)行數(shù)值捕捉，當(dāng)出現(xiàn)任意25行像素矩陣數(shù)值之和最小時(shí)就可以確定出此時(shí)對應(yīng)的這25行中最上邊的一行就是虛擬四線三格中的第2行，具體實(shí)現(xiàn)公式為：，經(jīng)測算，相鄰兩個(gè)四線三格中間行最大垂直距離為40個(gè)像素點(diǎn)，然后再將拼接的碎片進(jìn)行同樣的分類，對于橫向切割處為空白行的碎片，利用相鄰兩四線三格中間行的行間距為40個(gè)像素點(diǎn)的條件，應(yīng)用matlab進(jìn)行分析計(jì)算，得到相配碎片，并綜合所有碎片數(shù)據(jù)，最終得出第一列英文碎片的排列結(jié)果。

另外，中英文第一列縱向匹配若出現(xiàn)一行或多行無字情況，需自行人工干預(yù)，按照原始參數(shù)，對所有無字行進(jìn)行假設(shè)添字。對于添字處理后的中文碎片，依舊根據(jù)兩相鄰字符之間的行間距為30個(gè)像素點(diǎn)的條件，找到其最佳匹配碎片，完成縱向拼接。對于英文碎片的空白行，該文僅對英文字母四線三格中的中間格進(jìn)行添字處理，根據(jù)相鄰兩個(gè)四線三格中間行垂直距離為40個(gè)像素點(diǎn)的條件，找到最佳匹配碎片，完成拼接。

4 所有紙片的拼接復(fù)原

對于已確定的第一列的碎片，需要對每一個(gè)分別進(jìn)行橫向排列，分析全部碎片二值化矩陣信息，提取所有碎片的左右邊緣矩陣。以第一列的每一個(gè)碎片為起點(diǎn)，依舊利用統(tǒng)計(jì)學(xué)中的相關(guān)系數(shù)計(jì)算方法，從左向右進(jìn)行計(jì)算，通過篩選找出與每個(gè)碎片的右邊緣矩陣相關(guān)系數(shù)最大的矩陣，并將其還原為碎片，此碎片即為最佳匹配者。依據(jù)此法，完成對全文拼接。

5 結(jié)論與分析

該文對圖像邊界及其文字進(jìn)行研究，提出了一種基于相似度分析對碎紙片進(jìn)行拼接復(fù)原的方法，該方法利用matlab軟件對二值化圖像的邊緣矩陣進(jìn)行了比較，并利用邊緣矩陣的相關(guān)系數(shù)，找到最佳匹配者，最終完成題材中的碎片拼接難題。該方法減少了大量人工干預(yù)，實(shí)現(xiàn)簡單，不依賴于碎片的幾何特征，可靠性比較好，在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取方面有顯著作用。

參考文獻(xiàn)

[1] 房然然.二維碎片自動拼接技術(shù)研究[D].山東師范大學(xué)，2015.

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

[3] 劉賜德，苗楠茜，常清，等.改進(jìn)的規(guī)則碎片拼接復(fù)原算法[J].南陽師范學(xué)院學(xué)報(bào)，2014（3）：22-24.