基于矩陣邊緣特征向量比較法的碎紙片拼接復原

溫躍飛

摘 要 對于采用縱橫切割，邊緣幾何特征幾乎相同的碎片，我們采用矩陣邊緣列向量的相似性來進行兩兩匹配，在出現(xiàn)無法正確匹配時進行必要的人工干預，最終實現(xiàn)碎片的拼接復原。由于平時的切割不可能全部都是縱向切割，所以將橫縱切割的單面和雙面的碎片轉換成縱向切割進行拼接。

關鍵詞 邊緣特征向量 窮舉法 灰色關聯(lián)分析 文字行特征 人工干預

中圖分類號：TP391 文獻標識碼：A

0引言

破碎文件的復原工作在司法物證復原，歷史文獻的修復和軍事情報的獲取等領域都具有重要的意義，傳統(tǒng)的人工修復雖然準確率高，但是效率很低，特別是在紙片的數量較多，破碎程度較大的情況下，光靠人工復原可能很難再短時間內完成拼接工作，這樣就會影響物證復原，文獻修復和情報獲取的進度。是否可以在計算機的幫助下，試著對碎紙片進行拼接，從而加快人工復原的速度，提高復原的效率。平面碎片匹配復原技術的研究有著重要的理論和現(xiàn)實意義，己成為模式識別、計算機視覺等領域的重要研究課題。本文采用計算機編程和人工干預的方法實現(xiàn)對橫縱切割碎紙片的拼接。

1縱向切割碎紙片的拼接復原模型

1.1模型流程圖

1.2獲取數據

將碎片的文件導入到MATLAB，由軟件讀取出每張圖片文件的像素信息，并且這些信息可以由MATLAB轉換為一個數字矩陣。

程序語句：

Imread（‘圖片路徑＼*.bmp）

通過MATLAB處理得到的數字矩陣可以得到每個矩陣的邊緣特征向量，之后可以利用得到的邊緣特征向量進行兩兩比較。

1.3數據預處理和模型的建立

由MATLAB得到數字矩陣之后，選取數字矩陣的左右邊緣向量L，R，向量里的數字“0”代表圖片中黑色的點，“255”代表圖片中白色的點，介于“0”和“255”之間的數字代表圖片中灰色的點?？梢员容^任意一張圖片的右邊和其余每張圖片的左邊，如果兩張圖片是相鄰的圖片，那么左邊圖片的右邊緣所表示的向量R和右邊圖片的左邊緣所表示的向量L應該是相關聯(lián)的，同樣的，如果兩張圖片不是相鄰的，那么右邊緣和左邊緣應該是不能匹配的，也就是說是不關聯(lián)的，這樣就可以篩選出兩張相鄰的圖片。在此模型中，在進行拼接之前進行人工干預，通過觀察碎片的邊緣留白的距離，字體邊緣的整齊程度以及圖片上內容，可以確定出哪張圖片為完整圖片中的最左邊的縱切碎片。

在確定了最左邊的縱切碎片之后，通過MATLAB讀取該碎片的像素數字矩陣的右邊緣特征向量R0，并和剩下的圖片的左邊緣特征向量進行比較，選出能夠匹配的那張圖片（設為R1），接著再比較1圖片的右邊緣向量R1和剩下圖片的左邊緣向量，再次選出能夠匹配的那張圖片，以此類推，可以將所有圖片都匹配出來，即完成了拼接的工作。

2橫縱切割單面碎紙片的拼接復原模型

通過對數據矩陣的觀察可以看出，如果兩個片段是屬于同一行的，那么它們的圖案中從最上方開始往下檢測，第一次出現(xiàn)全部都是白色像素值255的數字矩陣中的行數應該是相同的。

上圖是兩張碎片圖片，從他們的部分數字矩陣可以看出他們出現(xiàn)第一個一行全部都是白色像素點的行的行數h是相同的，都是在“上”字和“風”字的最下沿。說明這兩張圖片有很大的可能是在同一行的，剩下的圖片可以采用同樣的方法進行分類。

每張圖片轉換成數字矩陣之后，如果其中某一行的數字全部都是255，那么說明原圖片中這一行全部都是白色，即說明這一行沒有漢字或字母。每張圖片轉換成數字矩陣之后，矩陣的每行有72個數字，我們定義為，當一行全部都是255時，即=18360，然后計算代表每張圖片的數字矩陣中第一次出現(xiàn)總和為18360的行數h，其中如果有行數h相同的，那么基本上可以確定它們是屬于一行的。

那么此時就可以得到N個類，每個類當中都有M個片段，而這M個片段都是在一行的，這M個片段可以看成是把一個橫行作為整體的圖片縱切后得到碎片，這就回歸到了縱向的問題，可以利用縱向中的模型將每一類中的M個片段復原成一個橫行的整體。復原完成后的N個完整的橫行，將這N個完整的橫行旋轉90度得到新的N個完整的縱行，又可以看成這N個片段是由一個整體縱切得到的，再次回歸到縱向切割問題，利用縱向切割的模型可以將最后的N個片段復原，得到原本完整的圖片。

3橫縱切割雙面碎紙片的拼接復原模型

由于一般正反兩面切割問題中的碎紙片數量龐發(fā)，也信息量較復雜。首先，無法確定在這些碎片中哪些是屬于正面的，哪些是屬于反面的，這樣就不能直接用橫縱切割問題所才用的先分類的方法了，因為如果直接對行進行分類的話，很有可能將正反兩面的一行分到了一起，這樣仍然無法將屬于同一行的碎片分類出來，所以只能先從整體出發(fā)，用人工干預找出一些明顯屬于最邊緣的碎片。當找到了一定數量的最邊緣碎片的時候就能利用灰色關聯(lián)分析法對與最邊緣碎片相關聯(lián)的碎片進行篩選了。

3.1利用灰色關聯(lián)分析法對最邊緣附近的碎片進行篩選

灰色關聯(lián)分析法可對樣本數據量較小的系統(tǒng)進行綜合分析，且計算量很小。但這種方法中的某些參數如指標權重和分辨系數需要人為指定。必要時，可將上述幾種綜合評價與決策方法結合起來使用。比如，可先用層次分析法確定指標權重，然后再用灰色關聯(lián)分析法，可取得精度較高的結果。

根據灰色關聯(lián)分析，可以在剩下的碎片中找出跟邊緣碎片關聯(lián)度最大的碎片，剩下的碎片都可以用這樣的方法進行拼接?？梢岳没疑P聯(lián)分析法找出一些行或者列的片段，這樣在之后的拼接中就可以運用橫縱切割問題中的模型了。

3.2拼接實驗

經過灰色關聯(lián)分析的處理之后已經得到了一些行或者列的片段，這樣其實就將正反兩面切割問題轉化為了橫縱切割問題中的問題，在找到行（或列）的片段之后，就將這些行（或列）的片段作為一個大類，將每個大類進行旋轉，得到縱列（若得到的是列就不用旋轉了），得到縱列后就轉化為縱向切割問題了，那么利用程序一就可以將縱列復原拼接了。

這樣就可以正確復原正反兩面中的一面，那么另一面也就正確的復原了。

4總結

采用MATLAB讀取圖片像素信息的方法，可以很好的保持圖片原有的信息，同時能夠準確的將圖片的信息以矩陣的形式反映給讀者，有較強的實用性。另外，用矩陣的形式來表達也有利于采用邊緣邊緣特征向量比較的方法。

在考慮橫縱切割問題的時候充分利用縱向切割問題所建立的模型，通過將原本橫縱切割的碎紙片先進行橫行的拼接，使其轉換成N個大類，再將得到的橫向的片段旋轉90度得到轉換成縱向的片段，利用縱向切割的模型來解決。節(jié)約了重新編寫對應橫縱切割問題的程序的時間，同時也充分的利用了兩個問題之間的連貫性，以縱向切割為基礎，利用已經得到的結論來解決更加困難的問題。

參考文獻

[1] 馬艷， 張治輝（著）.種邊緣檢測算子的比較.工礦自動化出版社，2004.1：54～P55.

[2] 賈海燕，朱良家，周宗潭，胡德文（著）.一種碎紙自動拼接中的形狀匹配方法[J]. 計算機仿真，2006.3：66.

[3] 孫文方，趙亦工. 基于有限Radon變換的圖像紋理方向的檢測. 計算機應用，2005.25（z1）.