數學建模中的碎紙片拼接復原要點研究

廖代喜

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

關鍵詞：碎片；拼接；復原；模擬退火算法；系統聚類法

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

1 僅縱切的碎紙片拼接復原要點

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

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

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

2 有橫、縱切的碎紙片拼接復原要點

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

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

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

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

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

3 雙面打印文本的碎紙片拼接復原要點

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

4 總結與展望

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

參考文獻

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

[2]羅智中.基于文字特征的文檔碎紙片半自動拼接[J].計算機工程預測應用，2012，48（5）：207-210.

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