基于人機交互界面的碎紙片拼接復原

摘 要：2013年的全國大學生數學建模競賽提出了碎紙片的拼接復原的問題，然而絕大多數論文都先設置了不同篩選條件對碎片進行篩選得到最有可能處于同一行的碎片，然后再逐行對得到的碎片進行手工調整得到完整的還原圖，筆者認為這種方法效率不是很高并且存在一些難以克服的精度問題，從而在本文中給出了一種通過人機交互界面的優化模型來實現碎片復原的思路和算法，其復原效率可達到90%或95%以上。

關鍵詞：人機交互；像素矩陣；優化模型；匹配度 ；距離

針對2013年全國大學生數學建模B題提出的碎紙片拼接復原問題，在將問題二和問題三中的209張碎片信息導入MATLAB之后，我們會得到每張碎片對應一個大小的像素灰度矩陣[1]，每一個元素對應一個像素點，變化范圍為0-255，其中0對應純白色，255對應純黑色，這樣，碎片的所有信息都存在于這些像素點中，下面的問題就是如何利用這些像素點中的信息，提高復原效率。

然而，大多數論文的思路是先對這些碎片的像素矩陣進行一些信息處理，例如文獻[2]和文獻[3]中所給出的算法，考慮到原圖片中文字每行之間會留有一定空白，從而可以找出每張碎片中出現空白部分的多少，（如果某張碎片的像素矩陣中有連續幾行的元素值全部為0，就表示該碎片的對應位置都是空白，沒有文字出現）、亦或是找出每張碎片從文字部分變為空白部分的位置等等，利用這些條件及聚類分析的思想，先得到最有可能處于同一行中的碎片，再逐行對這些碎片進行拼接復原。但筆者認為這種做法過于繁瑣，理由如下：

（1）不論篩選條件如何精確完善，一次拼接成功的概率是非常小的，必須要有人工干預過程，而每一次人工調整碎片位置之后，都要人工強制調整程序中碎片的位置編號，再進行一次復原，通過肉眼判斷調整之后的復原情況，比較繁瑣；

（2）在通過肉眼的判斷碎片是否匹配的過程中，若發現某個地方的碎片不匹配，是很難確定不匹配碎片在整張復原圖中的具體位置的，例如是第幾行的第幾列的碎片位置出現了錯誤，因為肉眼只能判斷大致的位置，不能確定具體的行標和列標，如果不能知道具體的碎片位置，就無法進行人工調整；

（3）即使知道了不匹配碎片的具體位置，知道了該位置的碎片編號，要想知道處于該位置正確碎片的編號，我們需要對還未參與完成復原的碎片再進行一次篩選或聚類，再一次得到最有可能處于同一行的碎片編號，而每一次碎片位置的人工強制改動，都對其之后的復原造成影響，即“牽一發而動全身”；

（4）對于那些因人工干預而被暫時剔除的碎片，我們是很難確定這張碎片究竟應該擺放在哪一行的，因為根據我們的思路，這張碎片的信息和該行的其他碎片信息最為匹配，但通過肉眼的判斷后這張碎片是不處于這一行的，筆者通過實驗發現，這樣的碎片處于哪一行的可能性非常多，這說明篩選條件存在局限性，因為真正處于同一行的碎片的像素信息很有可能呈現出很大差異；

（5）這種思路應用性不強，因為每一次人工干預后計算機都將給出所有位置的碎片編號，而其中若有一個位置的碎片出現錯誤，其之后的所有碎片都將出現錯誤，出現“錯上加錯”的現象，而對于那些碎片形狀或大小更為復雜的情況來說，其人工干預次數必定非常之多，從以上分析容易看出，上述思路的工作量是比較大的。

為了更好的解決該類的碎片復原問題，筆者建立了優化模型[4]，利用基于人機交互界面的算法，避免了上述思路出現的問題，有效地提高了復原效率。

1 人機交互界面的模型與算法

對于附件3和附件4中的碎紙片來說，不僅要考慮圖片之間行與行的匹配，還要考慮到列與列之間的匹配。由于問題2的圖片的像素矩陣提供的信息量較少，其大小為180×72，較問題1的像素矩陣的大小減少了11倍，故不能僅僅考慮一側的元素。盡管對于每一張圖片來說，它與周圍的圖片共有四種拼接可能，但如果考慮每張碎片四條邊的話，對于相鄰的圖片存在重復計算的過程，故對于每一塊碎圖片而言，選擇其左側和上側的邊緣，觀察其與其他圖片的匹配情況。引入距離的定義，將位于第i行第j列的編號為k的碎紙片的像素矩陣的最左側一列的元素與其左側圖片像素矩陣的最右側一列的元素的歐氏距離，記為左側距離 ；同理，將第i行第j列的碎紙片的像素矩陣的最上側一行元素與其上側圖片像素矩陣的最下側一行的元素的歐氏距離，記為上側距離 。則對于每一張圖片的像素矩陣 而言，它都有一個距離特性 ，即 。考慮編程與人工干預相結合的方式進行求解，具體工作如下：

1.1 歐式距離的引入

引入距離值 的指標，作為確定每一位置應擺放哪張碎片的依據指標

其中，Sij表示在確定第i行第j列位置應擺放哪張碎片時，剩下還未被確定位置的碎片序號集合； 表示位于第i行第j列位置的編號為k的碎紙片的像素矩陣的最左側一列的元素與其左側圖片像素矩陣的最右側一列的元素的歐式距離； 表示位于第i行第j列位置的碎紙片的像素矩陣的最上側一行元素與其上側圖片像素矩陣的最下側一行的元素的歐式距離； 表示第i行的第j列位置的編號為k的圖片與上邊左邊圖片的距離之和；Aij表示的是第i行第j列位置的碎片的像素矩陣，大小為180×72；row和col表示的是在像素矩陣中的行標和列標。

1.2 優化模型

當定義了距離值之后，我們可以發現，距離值越小代表兩張圖之間的匹配程度越高。故建立優化模型：

通過此優化模型所得到每一個位置的k的值即為第i行第j列應排布的碎紙片的編號。

1.3 模型的求解

利用MATLAB軟件[5][6]，算法求解的四大步驟如下：

第一大步：將碎紙片轉化成像素矩陣便于處理：

將附件3和附件4給出的碎紙片通過matlab軟件轉化成像素矩陣，其像素矩陣的大小為180×72；

第二大步：確定起始行列的碎紙片及其順序

通過編程和簡單人工干預的方法，根據碎圖片之間的字形和語句的通順度，將第一行和第一列排好順序。

第三大步：建立交互界面確定后續圖片及其順序

當第一行和第一列的圖片順序已經確定了之后，建立人際交互界面，依次確定每個位置上應擺放哪一張碎片，其搜索順序為：先在一行中依次搜索，到每一行的末尾后轉而執行下一行的搜索。

STEP1：在整個復原過程中一直顯示當前碎片的復原圖，對已經確定好位置的碎片直接在復原圖中顯示，未確定好應擺放哪張碎片的位置上顯示空白；

如圖1所示，初始時刻第一列和第一行的碎片已經確定好，所以圖中顯示了出來，其余位置均顯示空白：

STEP2：輸入1（yes）/0（no） 依次確定每一位置應擺放的碎片

⑴在確定每一位置應擺放哪張碎片時，計算機會自動先把在該位置與周圍碎片距離最小的碎片打印在復原圖中，通過肉眼判斷此時語句是否通順合理，若合理，則鍵入1，否則鍵入0；

如圖2所示，此時要確定第二行第二列位置的碎片編號，此時計算機將在該位置距離最小的碎片打印在復原圖中，并等待用戶鍵入數字（圖3）：

觀察后發現語句通順，故在交互界面中鍵入“1”（圖4）.

⑵若鍵入1，則計算機自動存儲當前碎片的編號，繼續下一位置的碎片匹配工作（如圖5所示，此時發現第二行第二列碎片一次就匹配成功，鍵入“1”后計算機自動打印下一位置的碎片）；若鍵入0，則計算機用在該位置距離次最小的碎片代替當前不能夠匹配的碎片并打印在復原圖中，再次通過肉眼判斷，若成功則存儲當前碎片編號，繼續下一位置碎片匹配的工作，否則重復上述過程，直至有一張碎片在該位置匹配成功為止；

STEP3.重復上述過程依次確定每一位置的碎片編號，但每一次遍歷搜索時，都在還未能匹配成功的碎片中搜索，以減少工作量；

STEP4.當最后一張碎片確定后，整張復原圖也已經全部完成，此時計算機打印每個位置的碎片編號。如圖6所示：

第四大步：完整圖片的檢驗與校準

1.4 模型評價

⑴事實上，用人機交互界面確定每個位置的碎片編號的整個過程是一個動態過程，計算機只能計算出當前位置上每一張碎片在該位置的距離值情況并進行排序，并把按照距離從小到大的順序將碎片打印顯示在該位置上，計算機不能確定當前位置之后的那些位置上應該擺放那些碎片。因為在當前位置的碎片編號確定之前，計算機是無法計算下一位置上碎片的距離值的。

⑵人機交互界面這一動態確定碎片編號的過程能夠保證是在當前已經確定好位置的碎片全部正確的情況下才不斷進行的，不會出現利用篩選條件或聚類分析確定碎片編號時出現的“錯上加錯”的情況。

⑶讀者可能會覺得要鍵入190多次0/1有點繁瑣，但相比而言，其工作量還是比較少的，并且鍵入0的次數非常少，也就是說在每個位置上，基本第一次就能匹配成功，下表1給出了即使對于匹配難度比較大的英文碎片（附件4），需要鍵入“0”的位置：（其余位置上第一次就能匹配成功）

可以看出需要進行第二次匹配的位置只有10個，其余位置上的碎片只需一次就能匹配成功（除去第一行第一列的碎片），其匹配成功率s為：

相比較文獻[4]中的復原效率54.55%而言，其成功率提高了73.12%，證明上述算法確實具有更高的復原效率。

2 結束語

本文采用人機交互界面的方法，較為高效地解決了碎紙片拼接復原的問題，避免了多數獲獎論文中利用篩選條件或聚類分析等方法解決這類問題而出現的例如精度不夠高等等的一些困難，對于更為復雜一些的碎片復原問題具有比較好的應用價值。

[參考文獻]

[1]維基百科.灰度圖象，http：//zh.wikipedia.org/zh-cn/， 2013.9.13.

[2]豆丁文檔.2013年大學生數學建模比賽一等獎論文（B題），[EB/OL].http：//www.docin.com/p-724984523.html，2013.12.

[3]豆丁文檔.2013年大學生數學建模比賽一等獎論文（B題），[EB/OL].http：//www.docin.com/p-726822933.html，2013.12.

[4]姜啟源，謝金星，等.數學建模（第四版）[M].北京：高等教育出版社，2012.12：58-77.

[5]張德豐，周燕.詳解MATLAB在統計與工程數據分析中的應用 [M].北京：電子工業出版社，2010：10-200.

[6]趙東方.數學模型與計算[M].北京：科學出版社，2007：10-240.