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

關(guān)鍵詞：人機交互；像素矩陣；優(yōu)化模型；匹配度 ；距離

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

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

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

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

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

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

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

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

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

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

1.1 歐式距離的引入

引入距離值 的指標(biāo)，作為確定每一位置應(yīng)擺放哪張碎片的依據(jù)指標(biāo)

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

1.2 優(yōu)化模型

當(dāng)定義了距離值之后，我們可以發(fā)現(xiàn)，距離值越小代表兩張圖之間的匹配程度越高。故建立優(yōu)化模型：

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

1.3 模型的求解

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

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

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

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

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

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

當(dāng)?shù)谝恍泻偷谝涣械膱D片順序已經(jīng)確定了之后，建立人際交互界面，依次確定每個位置上應(yīng)擺放哪一張碎片，其搜索順序為：先在一行中依次搜索，到每一行的末尾后轉(zhuǎn)而執(zhí)行下一行的搜索。

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

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

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

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

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

觀察后發(fā)現(xiàn)語句通順，故在交互界面中鍵入“1”（圖4）.

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

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

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

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

1.4 模型評價

⑴事實上，用人機交互界面確定每個位置的碎片編號的整個過程是一個動態(tài)過程，計算機只能計算出當(dāng)前位置上每一張碎片在該位置的距離值情況并進行排序，并把按照距離從小到大的順序?qū)⑺槠蛴★@示在該位置上，計算機不能確定當(dāng)前位置之后的那些位置上應(yīng)該擺放那些碎片。因為在當(dāng)前位置的碎片編號確定之前，計算機是無法計算下一位置上碎片的距離值的。

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

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

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

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

2 結(jié)束語

本文采用人機交互界面的方法，較為高效地解決了碎紙片拼接復(fù)原的問題，避免了多數(shù)獲獎?wù)撐闹欣煤Y選條件或聚類分析等方法解決這類問題而出現(xiàn)的例如精度不夠高等等的一些困難，對于更為復(fù)雜一些的碎片復(fù)原問題具有比較好的應(yīng)用價值。

[參考文獻]

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

[2]豆丁文檔.2013年大學(xué)生數(shù)學(xué)建模比賽一等獎?wù)撐模˙題），[EB/OL].http：//www.docin.com/p-724984523.html，2013.12.

[3]豆丁文檔.2013年大學(xué)生數(shù)學(xué)建模比賽一等獎?wù)撐模˙題），[EB/OL].http：//www.docin.com/p-726822933.html，2013.12.

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

[5]張德豐，周燕.詳解MATLAB在統(tǒng)計與工程數(shù)據(jù)分析中的應(yīng)用 [M].北京：電子工業(yè)出版社，2010：10-200.

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