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

溫躍飛

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

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

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

0引言

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

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

1.1模型流程圖

1.2獲取數據

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

程序語句：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

根據灰色關聯分析，可以在剩下的碎片中找出跟邊緣碎片關聯度最大的碎片，剩下的碎片都可以用這樣的方法進行拼接。可以利用灰色關聯分析法找出一些行或者列的片段，這樣在之后的拼接中就可以運用橫縱切割問題中的模型了。

3.2拼接實驗

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

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

4總結

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

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

參考文獻

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

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

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