上傳人：奔***

認證信息

認證類型：個人認證

認證主體：常**（實名認證）

IP屬地：河北

IP屬地：河北 更新時間：2024-03-15 格式：doc 頁數(shù)：42 大?。?.46MB 人氣指數(shù)：12 舉報 版權(quán)申訴

1、1碎紙片的拼接復(fù)原問題摘要為解決碎紙片的拼接復(fù)原問題，我們通過定義差異度指數(shù)、高度差，建立01規(guī)劃模型，使用聚類分析、MATLAB搜索算法和人工干預(yù)等相結(jié)合，得到了所有附件復(fù)原序號和復(fù)原圖片。針對問題一，首先提取附件1、2中所有碎片左側(cè)和右側(cè)邊緣灰度，通過任意列碎片右側(cè)和任意列碎片左側(cè)的邊緣灰度差值可以定義差異度指數(shù)，從而得到差異度特征矩陣，然后建立01規(guī)劃模型，以第i張碎片右側(cè)與第j張碎片左側(cè)差異度最小為目標函數(shù)，以第i張碎片右側(cè)與第

2、j張碎片左側(cè)是否相連為決策變量，以每張碎片右側(cè)一定與某張碎片左側(cè)相連、每張碎片左側(cè)一定與某張碎片右側(cè)相連為約束條件。算法為先提取任意張碎片邊緣灰度值，得到差異度矩陣，帶入規(guī)劃模型中，通過LINGO軟件找到中英文碎片的拼接方法，得到復(fù)原序號如表一、表二，從而得到出中文與英文復(fù)原圖片。表一:中文碎片的復(fù)原序號008014012015003010002016001004005009013018011007017000006表二：英文碎片的復(fù)原

3、序號003006002007015018011000005001009013010008012014017016004檢驗中英文碎片拼接復(fù)原順序準確性，利用MATLAB搜索算法，可以得到中英文碎片拼接方法。結(jié)果表明兩種方法得出的中英文復(fù)原順序相同，復(fù)原圖片相同，同時人工檢驗中英文復(fù)原圖片中無明顯語法、單詞錯誤，證明復(fù)原圖片準確。針對問題二，由于每張碎片有左側(cè)、右側(cè)和上側(cè)、下側(cè)，與問題一相同，可以定義兩個差異度指數(shù)，建立雙目標01規(guī)劃模型

4、。但由于差異度矩陣過大，決策變量復(fù)雜，我們又建立了改進的簡化模型，定義高度差，運用聚類分析方法，按照高度不同將所有碎片分為18類，然后再以第j塊碎片左側(cè)與第i塊碎片右側(cè)的差異度最小為目標函數(shù)，以第i塊碎片右側(cè)與第j塊碎片左側(cè)是否相連為決策變量，以每塊碎片右側(cè)一定與某塊碎片左側(cè)相連、每塊碎片左側(cè)一定與某塊碎片右側(cè)相連，滿足高度差閾值為約束條件，建立單目標01規(guī)劃模型。算法為先提取任意塊碎片邊緣灰度值和高度，得到差異度矩陣，編程將中文碎片按

5、高度分為18類，人工干預(yù)分為11行，再利用問題一中碎片縱向復(fù)原方法，得到中文復(fù)原序號，畫出中文復(fù)原圖片。（英文復(fù)原模型相似，僅高度差閾值不同）針對問題三，對于雙面英文碎片的復(fù)原問題，我們提出了單詞殘缺程度的定義，定量的描述了英文碎片的特征信息，構(gòu)成了算法的核心內(nèi)容，運用編程和人工干預(yù)將碎紙片分為11類，每類19個碎片，在此基礎(chǔ)上利用前兩問所建的01規(guī)劃模型，再加上雙面的一些約束條件，得到雙面英文復(fù)原序號，并繪出英文雙面復(fù)原圖片。關(guān)鍵詞：

6、差異度指數(shù)；01規(guī)劃；LINGO軟件；聚類分析；高度差；殘缺程度；3ij?=1時，表示第i張碎片右側(cè)和第j張碎片左側(cè)的相連；ij?ij?=0時，表示第i張碎片下側(cè)和第j張碎片上側(cè)的不相連；ij?=1時，表示第i張碎片下側(cè)和第j張碎片上側(cè)的相連；ijH高度差表示第i塊碎片第一行文字中心到第i碎片上側(cè)邊緣的高度iH與第j塊碎片第一行文字中心到第j碎片上側(cè)邊緣的高度jH之間的差值；四、問題一分析與模型建立、求解4.1問題一的分析問題一要求對于

7、給定的來自同一頁印刷文字文件的碎紙機破碎紙片（僅縱切），建立碎紙片拼接復(fù)原模型和算法，并針對附件1、附件2給出的中、英文各一頁文件的碎片數(shù)據(jù)進行拼接復(fù)原。參考文獻[1]，由于每列中文和英文碎片都有左側(cè)和右側(cè)，需要考慮每一列碎片的左側(cè)和右側(cè)與其他列的左側(cè)和右側(cè)差異，每列碎片邊緣灰度已知，通過任意列碎片右側(cè)和任意列碎片左側(cè)的差異值可以定義差異度指數(shù)（同一列碎片的左側(cè)與右側(cè)的差異度定義為無窮大），從而得到差異度特征矩陣。然后可以通過01規(guī)劃模

8、型，以第j張碎片左側(cè)與第i張碎片右側(cè)的差異度最小為目標函數(shù)，以第i張碎片右側(cè)與第j張碎片左側(cè)是否相連為決策變量，以每張碎片右側(cè)一定與某張碎片左側(cè)相連、每張碎片左側(cè)一定與某張碎片右側(cè)相連為約束條件（復(fù)原圖片最左側(cè)一定與最右側(cè)的差異度最小），找到中文和英文碎片的拼接復(fù)原順序，MATLAB編程得到復(fù)原序號，從而得到出中文與英文復(fù)原圖片。為了檢驗中文與英文碎片拼接復(fù)原順序是否正確，建立了MATLAB搜索算法模型，可以得到中文與英文碎片拼接方法，

9、MATLAB軟件可以直接畫出中文與英文復(fù)原圖片。結(jié)果表明兩種方法得出的中文與英文復(fù)原順序相同，復(fù)原圖片相同。同時人工檢驗出中文與英文復(fù)原圖片中無明顯語法、詞語和單詞錯誤，證明復(fù)原圖片正確。4.2問題一的碎紙片拼接復(fù)原模型建立先提取碎紙片邊緣差異信息，再進行圖片拼接復(fù)原，具體步驟如下:（1）提取信息：差異度指數(shù)用差異度指數(shù)來衡量任意列右側(cè)邊緣與任意列左側(cè)邊緣差異。定義差異度指數(shù)ijC，表示第i張碎片右側(cè)和第j張碎片左側(cè)的差異度，為第i張碎