廖代喜

摘 要：基于模擬退火算法與系統(tǒng)聚類法，文章首先依次介紹了僅縱切、既有橫切又有縱切、雙面打印三種情形下的碎紙片拼接復(fù)原要點(diǎn)，然后對(duì)全文進(jìn)行了總結(jié)與展望。

關(guān)鍵詞：碎片；拼接；復(fù)原；模擬退火算法；系統(tǒng)聚類法

碎紙片拼接復(fù)原工作在諸多領(lǐng)域中有著極其重要的應(yīng)用，如歷史文物的考證、司法鑒定以及情報(bào)獲取等。在計(jì)算機(jī)技術(shù)發(fā)展起來(lái)之后，傳統(tǒng)的人工復(fù)原方式導(dǎo)致效率低下的弊端日益凸顯，因此，通過(guò)數(shù)學(xué)建模的方法得到碎紙片自動(dòng)拼接復(fù)原模型以提高拼接效率顯得尤為重要，已有文獻(xiàn)對(duì)此做了一些研究[1-3]。文章以2013年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B題為例，基于模擬退火算法與系統(tǒng)聚類分析，依次介紹僅縱切、既有橫切又有縱切、雙面打印三種情形下的碎紙片拼接復(fù)原要點(diǎn)。

1 僅縱切的碎紙片拼接復(fù)原要點(diǎn)

步驟6： 降溫。選定降溫系數(shù)θ（一般取為接近1的數(shù)）進(jìn)行降溫，即用θT取代T，從而得到新的溫度。

步驟7： 算法終止條件。用選定的終止溫度Te，判斷退火過(guò)程是否結(jié)束。若T

這樣，由于碎紙片較大，圖片信息較明顯，因此不需要人工干預(yù)，復(fù)原率可達(dá)100%。附件2中的英文圖片可類似處理。

2 有橫、縱切的碎紙片拼接復(fù)原要點(diǎn)

對(duì)于既有橫切又有縱切的碎紙片拼接復(fù)原，若利用上一問(wèn)的方法直接對(duì)全部的209張圖片進(jìn)行拼接，一方面必然會(huì)導(dǎo)致算法運(yùn)行效率大大降低；另一方面，由于區(qū)分各圖片間邊界差異的灰度值信息較少，易導(dǎo)致拼接時(shí)重碼率高而復(fù)原率低。因此，我們采用的方法是，首先提取出所有圖片的行特征；然后對(duì)209張圖片建立行聚類模型，對(duì)各行聚類依據(jù)上一問(wèn)的方法將其中圖片重排；最后對(duì)排好序的各行類似的作橫向排序即可將碎片拼接復(fù)原。具體的步驟如下：

第一步，提取圖片的行特征。利用Matlab讀入圖片，將每張圖片轉(zhuǎn)化為一個(gè)180*72的灰度值矩陣；再用Matlab可計(jì)算出中文字符高為40像素點(diǎn)，行間距為31像素點(diǎn)。

第二步，建立行聚類模型。主要思想是：位于同一橫行的圖片，其空白行的分布特征是一致的。所謂空白行是指該行中灰度值等于255的像素點(diǎn)個(gè)數(shù)恰好有72個(gè)（將這樣的行賦值為1，否則賦值為0）；所謂分布特征是指每張圖片的180行中，空白行分布的具體位置或范圍。因此，每張圖片空白行的分布對(duì)應(yīng)一個(gè)180維的向量，不妨稱為特征向量，其中的元素為1或0，第i張圖片的特征向量記為ηi。為了系統(tǒng)聚類法的順利運(yùn)行，此時(shí)需要進(jìn)行人工干預(yù)，即對(duì)含大片空白行圖片的信息根據(jù)字符高度和行間距進(jìn)行補(bǔ)充，得到該圖片新的空白行分布范圍。最后，我們可以利用系統(tǒng)聚類法中的（類與類間）最短距離法進(jìn)行聚類，只不過(guò)此時(shí)圖片間距離為d'（i，j）=‖ηi-ηj‖1。通過(guò)調(diào)整最短距離值，將所有的209張圖片分成11類（行），每類（行）包含19張圖片。然后對(duì)各行聚類依據(jù)上一問(wèn)的方法對(duì)其中圖片進(jìn)行列間重排。由于信息量較少，邊界間區(qū)分度不明顯，有時(shí)需進(jìn)行人工干預(yù)。

第三步，對(duì)拼接好的各行類似的作橫向排序即可將附件3中碎片復(fù)原。

附件4中的英文圖片可類似處理。與上述方法的區(qū)別僅限于由中英文字符本身的特點(diǎn)不同而導(dǎo)致中英文圖片預(yù)處理方式不同以及圖片特征提取方式不同。

3 雙面打印文本的碎紙片拼接復(fù)原要點(diǎn)

對(duì)于雙面打印文本，其解決方法與第二問(wèn)基本相同。先用系統(tǒng)聚類法將全部的418張圖片仍分為11類，每類所含的圖片此時(shí)有38張，再重排得到同一橫行的正反兩面。在采用模擬退火算法求解時(shí)，同一個(gè)初值理論上對(duì)應(yīng)兩個(gè)終值，因此重排時(shí)需要充分利用文本的雙面信息，可選擇使得正反兩面路徑之和最小的排列為復(fù)原方案。由于邊界間區(qū)分度不明顯，有時(shí)亦需進(jìn)行人工干預(yù)。同第二問(wèn)中的第三步，考量正反兩面信息，最后可將附件5中碎片復(fù)原。

4 總結(jié)與展望

從復(fù)原率來(lái)看，文章建立的基于模擬退火算法與系統(tǒng)聚類分析的模型是十分有效的。不足之處在于，對(duì)切割不均勻以及文字傾斜的碎紙片不再適用。因此，建立更具通用性的模型，是我們下一步的目標(biāo)。

參考文獻(xiàn)

[1]王小睿，吳信才，李軍.模擬退火算法的改進(jìn)策略在模板匹配上的應(yīng)用[J]. 維普資訊，1997.

[2]羅智中.基于文字特征的文檔碎紙片半自動(dòng)拼接[J].計(jì)算機(jī)工程預(yù)測(cè)應(yīng)用，2012，48（5）：207-210.

[3]姜啟源，謝金星，葉俊.數(shù)學(xué)模型[M].高等教育出版社，2003.