碎紙片的拼接復原

劉嘯澤,李 璞,陳 香

（西安電子科技大學,陜西西安,710126）

1 問題重述

破碎文件的拼接在司法物證復原、歷史文獻修復以及軍事情報獲取等領域都有著重要的應用.傳統上，拼接復原工作需由人工完成，準確率較高，但效率很低.特別是當碎片數量巨大，人工拼接很難在短時間內完成任務.隨著計算機技術的發展，我們嘗試使用碎紙片的自動拼接技術，以提高拼接復原效率.

2 符號說明

3 問題一的求解

3.1 模型I —— 貪心算法的設計

貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇.也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解.貪心算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題他能產生整體最優解或者是整體最優解的近似解.

對于一個給定的問題，往往可能有好幾種量度標準.初看起來，這些量度標準似乎都是可取的，但實際上，用其中的大多數量度標準作貪婪處理所得到該量度意義下的最優解并不是問題的最優解，而是次優解.因此，選擇能產生問題最優解的最優量度標準是使用貪婪算法的核心.

一般情況下，要選出最優量度標準并不是一件容易的事，但對某問題能選擇出最優量度標準后，用貪婪算法求解則特別有效.最優解可以通過一系列局部最優的選擇即貪婪選擇來達到，根據當前狀態做出在當前看來是最好的選擇，即局部最優解選擇，然后再去解做出這個選擇后產生的相應的子問題.每做一次貪婪選擇就將所求問題簡化為一個規模更小的子問題，最終可得到問題的一個整體最優解.

首先本文為了使求解過程不致過于復雜，故只為圖片去拼其右邊，所以在拼接時只用考慮為已知圖片去拼接其右邊即可.而貪心算法最為關鍵的是選出最優度衡量標準，本文選取已知圖片的右邊界的灰度向量與待匹配的圖片的左邊界的灰度向量的Euclidean 距離最小作為最優度衡量的指標（如式（5）所示）.并且本文所研究的問題比較特殊，這些圖片的拼接具有唯一性，所以每一步的最優解最終必會導致全局最優解，從而也避免了陷入局部最優解這個陷阱.

（式中 為已確定選取的圖片的右邊界的灰度向量， 為第 i 張圖片的左邊界的灰度向量）

Step 1.首先將每張圖片的左側向內延伸若干個像素點，在這個矩陣內的灰度值均為255，即均為白色，則可以斷定其為這張完整的紙的位于最左側的子圖片，將其放置于 中的 ，作為以確定選取的圖片；

Step 2.將已入 之外的其他圖片剪切至待拼的左側向量庫B 中；

Step 3.根據上述選擇的最優度的衡量指標選擇出與 拼接的最優的匹配向量，從而確定出與 拼接的最優的圖片；

Step 4.判斷待拼的左側向量庫B 中所余向量個數是否大于1，若大于1 表明待拼接圖片尚存，轉入step 2，否則結束.

3.2 模型II —— 基于TSP 問題的0-1 整數規劃模型

針對問題一，主要就是做文字的拼接，而能拼接到一起的兩張圖片在邊沿非常小的一段內具有很強的相似性，本文采用每張圖的灰度值矩陣的最左與最右的兩個列向量作為這張圖的特征值，然后用一張圖的最右的這個列向量去和其他圖的最左的列向量進行匹配，通過這兩個向量的Euclidean 距離。

（式中 表示的是第i 張圖片的右邊的灰度向量與第j 張圖片的左邊的灰度向量之間的Euclidean 距離， 表示第i 張圖片的右邊的灰度向量， 表示第j 張圖片的左邊的灰度向量）來作為評價指標，兩張圖的邊界的灰度向量的Euclidean 距離越小，其匹配程度越好.整張圖的拼接匹配的目標為拼接出來的圖的邊界灰度向量的Euclidean 距離之和最小.而一張完整的紙的兩端均是全白色，故兩端可拼接到一起.因為每張圖的右側只可能緊密連接一張圖，并且每張圖只用一次，故可以將這個問題抽象為一個TSP 問題進行求解.

即我們可以把每一張碎紙片類比成為一個城市。而把兩張圖片之間的Euclidean 距離類比為兩個城市之間的距離。從而將碎紙片的拼接和TSP 求解聯系起來。

TSP 問 題（Travelling Salesman Problem），即 旅 行 商 問題.假設有一個旅行商人要拜訪n 個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發的城市.路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值.

為了求解這個TSP 問題，建立以第j 張圖片的右邊是否與第 張圖片的左邊相連為決策變量，以所有相連接的圖片的右邊的灰度向量與圖片的左邊的灰度向量這兩個向量的距離之和最小為目標函數，建立一個0-1 整數規劃模型，其約束條件具體如下：

1)每張圖片的右邊只有一張圖片與之相連；

2)每張圖片的左邊只有一張圖片與之相連.

運用LINGO 求解上述0-1 整數規劃模型，結果會呈現為一個封閉的圓環，出現這種情況的原因是因為在一整頁紙的首尾都是空白的，其兩張圖片的邊緣的灰度向量之間的距離會非常小，故會連接成一個圓環.所以需確定頁面從哪里切開.通過MATLAB將每張圖片的左側向內延伸若干個像素點，在這個矩陣內的灰度值均為255，即均為白色，則可以斷定其為這張完整的紙的位于最左側的子圖片.所以將該圓環從這張圖片的左側切開即可.

4 問題二的求解

4.1 多目標的0-1 整數規劃模型

問題二是問題一進行了復雜化，每張圖片變小了，從而邊緣的信息量也變少了，而且每張圖片不僅需要考慮左右拼接，還需要考慮上下拼接.為了使問題的求解簡化，可以只考慮每張圖用其灰度值矩陣的最左和最下去和其他圖片的最右和最上的向量進行匹配，通過這兩組向量的Euclidean 距離之和最小來衡量其匹配程度.

但是考慮到在這一問中圖片變小了，導致邊緣的信息量也隨之變小，所以再確定一個目標——最上面一行字到該圖片上沿的距離 盡可能的相同，從而可以建立一個多目標的0-1 整數規劃模型.

本文建立以第i 張圖片的右邊是否與第j 張圖片的左邊相連，第i張圖片的下邊是否與第k張圖片的上邊相連為決策變量，以相接處的兩組灰度值矩陣的邊界向量的Euclidean 距離之和最小，處于同一行的圖片的特征值之差的絕對值的最大值最小為目標函數，建立一個多目標的0-1 整數規劃模型，其約束條件具體如下：

1)每張圖片的右邊只有一張圖片與之相連；

2)每張圖片的左邊只有一張圖片與之相連；

3)每張圖片的上邊只有一張圖片與之相連；

4)每張圖片的下邊只有一張圖片與之相連.

具體模型如式（6）所示：

這是一個多目標的0-1 整數規劃問題，對于最優解的求取存在一定難度，并且過程會比較復雜.所以為了求解這個問題，需要將其轉化為單目標問題，故選擇特征值 作為指標來進行聚類，這樣在同一類內就轉化為了單目標的整數規劃問題.

4.2 圖片的聚類

為了優化上述的多目標的0-1 整數規劃模型，從其第二目標引入的原因入手.由于元素即子圖片過多，從而僅用一個指標來評價匹配的程度使得誤匹配率上升，所以可以采用聚類的思想，使得待匹配的子集盡量的小，從而使問題較準確地求解.

考慮到漢字大部分都是比較規整的占據一個比較方正的空間，并且在打印中，行距為固定的，一行字的高也是固定的，如圖3 所示，即d、D 是固定的，所以對于漢字本文選取作為該圖片的特征值，依此作為漢字的聚類標準.

對于英文單詞，由于有些小寫字母并不規整，所以英文的聚類標準并不能用漢字的聚類標準.考慮到比較特殊的字符有g、j、p、q、y 這五個，分析所有圖片，可以將每張圖片的灰度值矩陣從左向右求和，從而做出其投影（如圖4 所示），而行線應畫在其投影的斜率較大的地方.行線的確定如圖4 所示.

根據每張圖片最左邊的白色區域最早結束的距離可以尋找出這11 行的行首，然后對剩下的每張圖片計算其各自的，根據其數值進行聚類，具體步驟如下：

4.3 每一類內的拼接

根據聚類結果，在每一類內包含有19 張圖片，且這一類中為完整圖片的一行內，所以可以利用問題一中的模型進行對其進行拼接.

對11 行分別利用問題一中的0-1 整數規劃模型進行求解，代入數據，利用LINGO 求解之，再利用問題一中相同的方法，將所得的一個封閉圓環，進行分割，從而拼出11 個橫條出來.

而在拼接英文有一行非常特殊，在這行靠右的部分其上部是一句話的結尾，并且英文單詞之間的距離比較大，尤其是一句話結束的部分其間隔比較大，這樣匹配會出現很多誤匹配，尤其是邊沿信息量非常小甚至沒有的片段，所以在這里需要人工介入，根據計算機拼接出來的三段，進行人工拼接。

[1] 卓金武，MATLAB 在數學建模中的應用，北京航空航天大學出版社，2011.4；

[2] 張志涌，精通MATLAB R2011a，北京航空航天大學出版社，2011.