上傳人：豬***

認(rèn)證信息

認(rèn)證類型：個(gè)人認(rèn)證

認(rèn)證主體：李**（實(shí)名認(rèn)證）

IP屬地：江西

IP屬地：江西 上傳時(shí)間：2022-04-13 格式：DOC 頁(yè)數(shù)：42 大小：2.46MB 積分：12 舉報(bào) 版權(quán)申訴

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

2、差異度矩陣，帶入規(guī)劃模型中，通過LINGO軟件找到中英文碎片的拼接方法，得到復(fù)原序號(hào)如表一、表二，從而得到出中文與英文復(fù)原圖片。 表一:中文碎片的復(fù)原序號(hào)008014012015003010002016001004005009013018011007017000006 表二：英文碎片的復(fù)原序號(hào)003006002007015018011000005001009013010008012014017016004檢驗(yàn)中英文碎片拼接復(fù)原順序準(zhǔn)確性，利用MATLAB搜索算法，可以得到中英文碎片拼接方法。結(jié)果表明兩種方法得出的中英文復(fù)原順序相同，復(fù)原圖片相同，同時(shí)人工檢驗(yàn)中英文復(fù)原圖片中無明顯語法、單詞錯(cuò)誤

3、，證明復(fù)原圖片準(zhǔn)確。針對(duì)問題二，由于每張碎片有左側(cè)、右側(cè)和上側(cè)、下側(cè)，與問題一相同，可以定義兩個(gè)差異度指數(shù)，建立雙目標(biāo)0-1規(guī)劃模型。但由于差異度矩陣過大，決策變量復(fù)雜，我們又建立了改進(jìn)的簡(jiǎn)化模型，定義高度差，運(yùn)用聚類分析方法，按照高度不同將所有碎片分為18類，然后再以第j塊碎片左側(cè)與第i塊碎片右側(cè)的差異度最小為目標(biāo)函數(shù)，以第i塊碎片右側(cè)與第j塊碎片左側(cè)是否相連為決策變量，以每塊碎片右側(cè)一定與某塊碎片左側(cè)相連、每塊碎片左側(cè)一定與某塊碎片右側(cè)相連，滿足高度差閾值為約束條件，建立單目標(biāo)0-1規(guī)劃模型。算法為先提取任意塊碎片邊緣灰度值和高度，得到差異度矩陣，編程將中文碎片按高度分為18類，人工干預(yù)分

4、為11行，再利用問題一中碎片縱向復(fù)原方法，得到中文復(fù)原序號(hào)，畫出中文復(fù)原圖片。（英文復(fù)原模型相似，僅高度差閾值不同）針對(duì)問題三，對(duì)于雙面英文碎片的復(fù)原問題，我們提出了單詞殘缺程度的定義，定量的描述了英文碎片的特征信息，構(gòu)成了算法的核心內(nèi)容，運(yùn)用編程和人工干預(yù)將碎紙片分為11類，每類19個(gè)碎片，在此基礎(chǔ)上利用前兩問所建的0-1規(guī)劃模型，再加上雙面的一些約束條件，得到雙面英文復(fù)原序號(hào)，并繪出英文雙面復(fù)原圖片。 關(guān)鍵詞：差異度指數(shù)；0-1規(guī)劃；LINGO軟件；聚類分析；高度差；殘缺程度； 一、問題重述破碎文件的拼接在司法物證復(fù)原、歷史文獻(xiàn)修復(fù)以及軍事情報(bào)獲取等領(lǐng)域都有著重要的應(yīng)用。傳統(tǒng)上，拼接復(fù)原工

5、作需由人工完成，準(zhǔn)確率較高，但效率很低。特別是當(dāng)碎片數(shù)量巨大，人工拼接很難在短時(shí)間內(nèi)完成任務(wù)。隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們?cè)噲D開發(fā)碎紙片的自動(dòng)拼接技術(shù)，以提高拼接復(fù)原效率。請(qǐng)討論以下問題：1. 對(duì)于給定的來自同一頁(yè)印刷文字文件的碎紙機(jī)破碎紙片（僅縱切），建立碎紙片拼接復(fù)原模型和算法，并針對(duì)附件1、附件2給出的中、英文各一頁(yè)文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。如果復(fù)原過程需要人工干預(yù)，請(qǐng)寫出干預(yù)方式及干預(yù)的時(shí)間節(jié)點(diǎn)。復(fù)原結(jié)果以圖片形式及表格形式表達(dá)。2. 對(duì)于碎紙機(jī)既縱切又橫切的情形，請(qǐng)?jiān)O(shè)計(jì)碎紙片拼接復(fù)原模型和算法，并針對(duì)附件3、附件4給出的中、英文各一頁(yè)文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。如果復(fù)原過程需要人工干

6、預(yù)，請(qǐng)寫出干預(yù)方式及干預(yù)的時(shí)間節(jié)點(diǎn)。復(fù)原結(jié)果表達(dá)要求同上。3. 上述所給碎片數(shù)據(jù)均為單面打印文件，從現(xiàn)實(shí)情形出發(fā)，還可能有雙面打印文件的碎紙片拼接復(fù)原問題需要解決。附件5給出的是一頁(yè)英文印刷文字雙面打印文件的碎片數(shù)據(jù)。請(qǐng)嘗試設(shè)計(jì)相應(yīng)的碎紙片拼接復(fù)原模型與算法，并就附件5的碎片數(shù)據(jù)給出拼接復(fù)原結(jié)果，結(jié)果表達(dá)要求同上。二、模型假設(shè)1.假設(shè)每個(gè)碎紙片上的字和字母都沒有發(fā)生扭曲。2.假設(shè)每個(gè)碎紙片的形狀和大小完全相同。3.假設(shè)每個(gè)碎紙片上灰度值的提取都是完全正確的值不等于255的都是黑點(diǎn)三、符號(hào)說明符號(hào)符號(hào)的含義差異度指數(shù)，表示第張碎片右側(cè)和第張碎片左側(cè)的差異度；表示第張碎片右側(cè)第k個(gè)特征點(diǎn)的灰度值；

7、決策變量，當(dāng)=0時(shí)，表示第張碎片右側(cè)和第張碎片左側(cè)的不相連； =1時(shí)，表示第張碎片右側(cè)和第張碎片左側(cè)的相連；表示第j列碎片左側(cè)與差異度最小的第i列碎紙片右側(cè)相連；表示第塊碎片右側(cè)和第塊碎片左側(cè)的差異度；表示第塊碎片下側(cè)和第塊碎片上側(cè)的差異度； 表示第塊碎片右側(cè)第k個(gè)特征點(diǎn)的灰度值； 表示第塊碎片下側(cè)第k個(gè)特征點(diǎn)的灰度值；=0時(shí)，表示第張碎片右側(cè)和第張碎片左側(cè)的不相連；=1時(shí)，表示第張碎片右側(cè)和第張碎片左側(cè)的相連； =0時(shí)，表示第張碎片下側(cè)和第張碎片上側(cè)的不相連； =1時(shí)，表示第張碎片下側(cè)和第張碎片上側(cè)的相連；高度差表示第i塊碎片第一行文字中心到第i碎片上側(cè)邊緣的高度與第j塊碎片第一行文字中心到

8、第j碎片上側(cè)邊緣的高度之間的差值；四、問題一分析與模型建立、求解4.1問題一的分析問題一要求對(duì)于給定的來自同一頁(yè)印刷文字文件的碎紙機(jī)破碎紙片（僅縱切），建立碎紙片拼接復(fù)原模型和算法，并針對(duì)附件1、附件2給出的中、英文各一頁(yè)文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。參考文獻(xiàn)1，由于每列中文和英文碎片都有左側(cè)和右側(cè)，需要考慮每一列碎片的左側(cè)和右側(cè)與其他列的左側(cè)和右側(cè)差異，每列碎片邊緣灰度已知，通過任意列碎片右側(cè)和任意列碎片左側(cè)的差異值可以定義差異度指數(shù)（同一列碎片的左側(cè)與右側(cè)的差異度定義為無窮大），從而得到差異度特征矩陣。然后可以通過0-1規(guī)劃模型，以第j張碎片左側(cè)與第i張碎片右側(cè)的差異度最小為目標(biāo)函數(shù)，以第i

9、張碎片右側(cè)與第j張碎片左側(cè)是否相連為決策變量，以每張碎片右側(cè)一定與某張碎片左側(cè)相連、每張碎片左側(cè)一定與某張碎片右側(cè)相連為約束條件（復(fù)原圖片最左側(cè)一定與最右側(cè)的差異度最?。?，找到中文和英文碎片的拼接復(fù)原順序，MATLAB編程得到復(fù)原序號(hào)，從而得到出中文與英文復(fù)原圖片。為了檢驗(yàn)中文與英文碎片拼接復(fù)原順序是否正確，建立了MATLAB搜索算法模型，可以得到中文與英文碎片拼接方法，MATLAB軟件可以直接畫出中文與英文復(fù)原圖片。結(jié)果表明兩種方法得出的中文與英文復(fù)原順序相同，復(fù)原圖片相同。同時(shí)人工檢驗(yàn)出中文與英文復(fù)原圖片中無明顯語法、詞語和單詞錯(cuò)誤，證明復(fù)原圖片正確。4.2問題一的碎紙片拼接復(fù)原模型建立

10、先提取碎紙片邊緣差異信息，再進(jìn)行圖片拼接復(fù)原，具體步驟如下: （1）提取信息：差異度指數(shù) 用差異度指數(shù)來衡量任意列右側(cè)邊緣與任意列左側(cè)邊緣差異。 定義差異度指數(shù)，表示第張碎片右側(cè)和第張碎片左側(cè)的差異度，為第i張碎片右側(cè)與第j張碎片左側(cè)的對(duì)應(yīng)灰度值之差的絕對(duì)值的累和。公式如下： （1） 其中：表示第張碎片右側(cè)第k個(gè)特征點(diǎn)的灰度值 表示第j張碎片右側(cè)第k個(gè)特征點(diǎn)的灰度值說明： 和的值已知，將附件1和附件2中19張碎片數(shù)據(jù)帶入MATLAB軟件可以得到每張碎片的1980個(gè)灰度值； 從而得到差異度矩陣如下： (2) 通過MATLAB編程計(jì)算出具體值如下：表一：附件一中文任意碎片差異度差異度1列左側(cè)2列左

11、側(cè)3列左側(cè)4列左側(cè)5列左側(cè)6列左側(cè)7列左側(cè)8列左側(cè)9列左側(cè)10列左側(cè)j列左側(cè)1列右側(cè)Inf1309451161031414481009421119552566110609785949111118.2列右側(cè)123423Inf1265891256523361610002711242311989593527111604.3列右側(cè)127946114084Inf105035104745969281224149025682744101673.4列右側(cè)10625312762995945Inf11333010691111130510320383887112810.5列右側(cè)1107321163981000761

12、15677Inf2230011879210500657564104087.6列右側(cè)120399113365105551124588114916Inf122693874658140324650.7列右側(cè)84410106346744681140798670949380Inf62810080369.8列右側(cè)111607113205109137136976102362111309107605Inf84629112936.9列右側(cè)971811109651168891241121071147860111188398983Inf111394.10列右側(cè)1114841186201092881214711180

13、6910447212446410150090152Inf.i列右側(cè).表二：附件二英文任意碎片差異度差異度1列左側(cè)2列左側(cè)3列左側(cè)4列左側(cè)5列左側(cè)6列左側(cè)7列左側(cè)8列左側(cè)9列左側(cè)10列左側(cè)j列左側(cè)1列右側(cè)Inf853108275276567795622436898542896008949089715.2列右側(cè)68051Inf80085515747494710284586945719976792718356.3列右側(cè)5829562297Inf40226645798885777825198236651169324.4列右側(cè)669776386970269Inf781179226925277768838

14、218572522.5列右側(cè)3489739595546630Inf8305361675461435764150786.6列右側(cè)5764919399767274548276087Inf79089699458075366210.7列右側(cè)667477727719737517986301585575Inf714877492780436.8列右側(cè)70250745807465457731809149252071274Inf7557870757.9列右側(cè)6250663054701424022571430809388231068430Inf75775.10列右側(cè)689017092777477538548212

15、397435887038446184145Inf.i列右側(cè). （2）中文和英文碎紙片拼接復(fù)原模型以第j張碎片左側(cè)與第i張碎片右側(cè)的差異度最小為目標(biāo)函數(shù)，以第i張碎片右側(cè)與第j張碎片左側(cè)是否相連為決策變量，以每張碎片右側(cè)一定與某張碎片左側(cè)相連、每張碎片左側(cè)一定與某張碎片右側(cè)相連為約束條件，建立0-1規(guī)劃模型。 s.t (3)其中：為決策變量，=0時(shí)，表示第張碎片右側(cè)和第張碎片左側(cè)的不相連； =1時(shí)，表示第張碎片右側(cè)和第張碎片左側(cè)的相連；4.3問題一中英文碎片拼接問題模型求解模型求解算法如下： （1）運(yùn)用MATLAB編程提取19列中文和英文碎片左側(cè)和右側(cè)的灰度值，計(jì)算出差異度指數(shù)，得到差異度矩陣，

16、結(jié)果見表一和表二。 （2）運(yùn)用LINGO11.0軟件，將上述0-1規(guī)劃問題的目標(biāo)函數(shù)與約束條件帶入LINGO軟件中（附錄一為中文碎片拼接復(fù)原LINGO算法，附錄二為英文碎片拼接復(fù)原LINGO算法），結(jié)果如表三和表四。 （3）運(yùn)用MATLAB編程（編程見附錄三）得到中文和英文碎片的復(fù)原序號(hào)，結(jié)果見表五和表六，可以直接得到中文和英文復(fù)原圖片，圖片見附錄四和五。表三：中文碎片連接方法決策變量為1X(2,5)X(1,7)X(3,17)X(4,11)X(5,6)X(6,10)X（7,9）X(8,18)X(9,15)X(10,14)實(shí)際連接點(diǎn)01-0400-0602-1603-1004-0505-0906

17、-0807-1708-1409-13決策變量為1X(11,3)X(12,8)X(13,16)X(14,19)X(15,13)X(16,14)X(17,2)X(18,1)X(19,12)實(shí)際連接點(diǎn)10-0211-0712-1513-1814-1215-1316-0117-0018-11表四：英文碎片連接方法決策變量為1X(1,6)X(2,10)X(3,8)X(4,7)X(5,4)X(6,2)X(7,3)X(8,16)X(9,13)X(10,14)實(shí)際連接點(diǎn)00-0501-0902-0703-0604-0305-0106-0207-1508-1209-13決策變量為1X(11,19)X(12,1)

18、X(13,15)X(14,11)X(15,18)X(16,19)X(17,5)X(18,17)X(19,12)實(shí)際連接點(diǎn)10-1811-012-1413-1014-1715-1816-0417-1618-11得到連接方法以后，可以使用MATLAB編程（見附錄三）得到中文和英文碎片的復(fù)原序號(hào)如下表： 表五:中文碎片的復(fù)原序號(hào)008014012015003010002016001004005009013018011007017000006表六：英文碎片的復(fù)原序號(hào)003006002007015018011000005001009013010008012014017016004 用MATLAB編程（附

19、錄四）可以直接拼接出中文和英文碎片復(fù)原圖片，程序結(jié)果截圖如圖一： 圖一：復(fù)原圖片程序結(jié)果截圖 中文與英文碎片復(fù)原的圖片見附錄四和五。 復(fù)原過程不需要人工干預(yù)，可完全通過LINGO軟件和MATLAB編程實(shí)現(xiàn)。4.4中文和英文碎片拼接復(fù)原方法檢驗(yàn) 為了檢驗(yàn)差異度指數(shù)和0-1規(guī)劃模型得出的復(fù)原順序和復(fù)原圖片的準(zhǔn)確性，利用MATLAB搜索算法模型： （4） 已通過MATLAB編程得到第i張碎片右側(cè)和第j張碎片左側(cè)的差異度，見表一與表二。對(duì)表一和表二按照列搜索，依次搜索找到與第j列碎片左側(cè)相連的差異度最小的第i列碎紙片右側(cè)（即），即第i列碎紙片右側(cè)與第j列碎片左側(cè)相連，對(duì)于每一列碎紙片需要搜索19次，共

20、需要搜索361次，使用MATLAB搜索算法即可實(shí)現(xiàn)（編程見附錄三 )可以得到中文和英文碎紙片的連接方式，如下表：表七：中文碎紙片連接方式第i列右側(cè)連接第j列左側(cè)017-000016-001010-002015-003001-004004-005000-006011-007000-006005-009第i列右側(cè)連接第j列左側(cè)003-010018-011014-012009-013008-014012-015002-016007-017013-018表八：英文碎紙片連接方式第i列右側(cè)連接第j列左側(cè)011-000005-001006-002000-003016-004000-005003-00601

21、0-008002-007001-009第i列右側(cè)連接第j列左側(cè)013-010018-011008-012009-013012-014007-015017-016014-017015-018 通過對(duì)比這兩種模型得到的結(jié)果發(fā)現(xiàn)：中文和英文碎片連接方式完全相同，兩種方法得出的中文與英文復(fù)原順序相同，復(fù)原圖片相同。同時(shí)人工檢驗(yàn)出中文與英文復(fù)原圖片中無明顯語法、詞語和單詞錯(cuò)誤，證明中文和英文復(fù)原圖片正確。0-1規(guī)劃模型清晰明了，同時(shí)運(yùn)算簡(jiǎn)單，運(yùn)算速度快。MATLAB搜索算法搜索次數(shù)較多，運(yùn)算速度慢一些，但結(jié)果準(zhǔn)確。所以我們使用0-1規(guī)劃模型解決問題一，使用MATLAB搜索算法檢驗(yàn)結(jié)果。五、問題二分析與模

22、型建立、求解 5.1問題二的分析問題二要求對(duì)于碎紙機(jī)既縱切又橫切的情形，建立碎紙片拼接復(fù)原模型和算法，并針對(duì)附件3、附件4給出的中、英文各一頁(yè)文件的碎片數(shù)據(jù)進(jìn)行拼接復(fù)原。由于209塊中文和209塊英文碎片都有左側(cè)、右側(cè)和上側(cè)、下側(cè)，與問題一相同，可以定義兩個(gè)差異度指數(shù)。根據(jù)問題一得到雙目標(biāo)0-1規(guī)劃模型，由于決策變量較復(fù)雜，這種模型不是很易求解，矩陣太大，也不易計(jì)算，因此提出了改進(jìn)模型。 改進(jìn)模型，定義高度差，表示第i塊碎片第一行文字中心到第i碎片上側(cè)邊緣的高度與第j塊碎片第一行文字中心到第j碎片上側(cè)邊緣的高度之間的差值。運(yùn)用聚類分析，給定高度差閾值，按照高度不同將所有碎片分為18類。然后再以

23、第j塊碎片左側(cè)與第i塊碎片右側(cè)的差異度最小和第i塊碎片與第j塊碎片高度差最小為雙目標(biāo)函數(shù)，以第i塊碎片右側(cè)與第j塊碎片左側(cè)是否相連為決策變量（），以每塊碎片右側(cè)一定與某塊碎片左側(cè)相連（），每塊碎片左側(cè)一定與某塊碎片右側(cè)相連（）為約束條件，建立雙目標(biāo)0-1規(guī)劃模型。找到18類中英文碎片，結(jié)合MATLAB編程和人工干預(yù)，將18類碎片處理為11行碎片，再利用問題一中碎片縱向復(fù)原的方法，得到中英文復(fù)原序號(hào)，從而MATLAB編程畫出中文與英文復(fù)原圖片。同時(shí)人工檢驗(yàn)出中文與英文復(fù)原圖片中無明顯語法、詞語和單詞錯(cuò)誤，證明復(fù)原圖片正確。5.2問題二碎紙片拼接復(fù)原模型建立5.2.1問題二碎紙片拼接復(fù)原初步模型

24、先提取碎紙片邊緣差異信息，再進(jìn)行圖片拼接復(fù)原，具體步驟如下: （1）提取信息：差異度指數(shù) 用差異度指數(shù)來衡量任意塊碎片右側(cè)邊緣與任意塊碎片左側(cè)邊緣差異及任意塊碎片下側(cè)邊緣與任意塊碎片上側(cè)邊緣的差異。定義差異度指數(shù)：表示第塊碎片右側(cè)和第塊碎片左側(cè)的差異度，為第i塊碎片右側(cè)與第j塊碎片左側(cè)的對(duì)應(yīng)灰度值之差的絕對(duì)值的累和。表示第塊碎片下側(cè)和第塊碎片上側(cè)的差異度，為第i塊碎片下側(cè)與第j塊碎片上側(cè)的對(duì)應(yīng)灰度值之差的絕對(duì)值的累和。 公式如下：（5） (6)其中：表示第塊碎片右側(cè)第k個(gè)特征點(diǎn)的灰度值； 表示第j塊碎片右側(cè)第k個(gè)特征點(diǎn)的灰度值； 表示第塊碎片下側(cè)第k個(gè)特征點(diǎn)的灰度值； 表示第j塊碎片上側(cè)第k個(gè)

25、特征點(diǎn)的灰度值；說明： 、和、的值已知，將附件3和附件4所有碎片數(shù)據(jù)帶入MATLAB軟件可以得到每塊碎片的左側(cè)、右側(cè)和上側(cè)、下側(cè)灰度值； 從而得到兩個(gè)差異度矩陣如下： (7) (8)（2）中文和英文碎紙片拼接復(fù)原模型以第j塊碎片左側(cè)與第i塊碎片右側(cè)的差異度最小和第j塊碎片上側(cè)與第i塊碎片下側(cè)的差異度最小為雙目標(biāo)函數(shù)，以第i塊碎片右側(cè)與第j塊碎片左側(cè)是否相連為決策變量（）和第i塊碎片下側(cè)與第j塊碎片上側(cè)是否相連為決策變量（），以每塊碎片右側(cè)一定與某塊碎片左側(cè)相連（）、每塊碎片下側(cè)一定與某塊碎片上側(cè)相連（），任意兩塊碎片之間可能不相連、可能左右相連、可能上下相連（）為約束條件，建立雙目標(biāo)0-1規(guī)劃

26、模型。 (9)其中：=0時(shí)，表示第張碎片右側(cè)和第張碎片左側(cè)的不相連； =1時(shí)，表示第張碎片右側(cè)和第張碎片左側(cè)的相連； =0時(shí)，表示第張碎片下側(cè)和第張碎片上側(cè)的不相連； =1時(shí)，表示第張碎片下側(cè)和第張碎片上側(cè)的相連； 此模型可以得到所有碎片的連接方式。5.2.2問題二中英文碎片拼接復(fù)原改進(jìn)模型由于建立的初步模型有決策變量較復(fù)雜，而且兩個(gè)差異度矩陣較大，用程序?qū)崿F(xiàn)較困難，因此在此提出改進(jìn)模型，只使用一種決策變量，具體建模過程如下：（1）提取信息：差異度指數(shù)和高度差定義差異度指數(shù)與初步模型定義相同，但改進(jìn)模型中不在使用差異度指數(shù)，定義高度差，表示第i塊碎片第一行文字中心到第i碎片上側(cè)邊緣的高度與第j

27、塊碎片第一行文字中心到第j碎片上側(cè)邊緣的高度之間的差值。公式如下： （10）（2）中文碎紙片拼接復(fù)原模型以第j塊碎片左側(cè)與第i塊碎片右側(cè)的差異度最小和第i塊碎片與第j塊碎片高度差最小為雙目標(biāo)函數(shù)，以第i塊碎片右側(cè)與第j塊碎片左側(cè)是否相連為決策變量（），以每塊碎片右側(cè)一定與某塊碎片左側(cè)相連（），每塊碎片左側(cè)一定與某塊碎片右側(cè)相連（）為約束條件，建立雙目標(biāo)0-1規(guī)劃模型。 (11)其中：為決策變量，=0時(shí)，表示第張碎片右側(cè)和第張碎片左側(cè)的不相連； =1時(shí)，表示第張碎片右側(cè)和第張碎片左側(cè)的相連； 為了將雙目標(biāo)轉(zhuǎn)化為單目標(biāo)問題，可以給定高度差閾值，給定高度范圍給所有碎片進(jìn)行分類，共18類，可以將此模型

28、簡(jiǎn)化，目標(biāo)函數(shù)與約束條件如下： （12） 再結(jié)合人工干預(yù)可以得到所有碎片的連接方式。（3）英文碎紙片復(fù)原模型 對(duì)附件四英文碎紙片建立復(fù)原模型與中文碎紙片模型基本相同，但由于中文是方塊字，同一行中文字上下側(cè)邊緣基本對(duì)齊，英文是非方塊字，上下邊緣的灰度值不大，因此應(yīng)該擴(kuò)大改進(jìn)模型的閾值，對(duì)英文碎片進(jìn)行分類，可以將高度差閾值調(diào)節(jié)為，其余約束條件不變，從而得到所有碎片連接方式，得到復(fù)原序號(hào)。5.3問題二中英文碎片拼接復(fù)原模型求解5.3.1模型算法（1）找到每塊碎紙片第一行文字中心到碎紙片上側(cè)邊緣的高度第一步：每塊碎紙片帶入MATLAB軟件中可以得到一個(gè)像素點(diǎn)的灰度矩陣，將每個(gè)矩陣歸一化： 第二步：對(duì)灰

29、度矩陣從上到下進(jìn)行行搜索，找到每塊碎片第一行文字的中心位置第三步：通過MATLAB軟件編程（附錄三）計(jì)算第i塊碎紙片第一行文字中心到碎紙片上側(cè)邊緣的高度。（2）確定高度差閾值，給定18個(gè)高度范圍，進(jìn)行聚類分析，將209塊碎片按照每塊碎片第一行文字中心到碎片上側(cè)邊緣的高度分為18類，結(jié)果見表九。（3）對(duì)每一類碎片，運(yùn)用MATLAB軟件畫圖，可以畫出18行文字，對(duì)每行文字出現(xiàn)的奇異碎片進(jìn)行剔除。通過人工干預(yù)，可以得到11行文字。（4）對(duì)這11行文字，運(yùn)用問題一算法，進(jìn)行縱向拼接復(fù)原，在此基礎(chǔ)上通過人工干預(yù)將11行文字進(jìn)行調(diào)試和拼接，可以得到附件三和附件四中英文的復(fù)原序號(hào)和復(fù)原圖片。5.3.2模型結(jié)

30、果（1）附件三中文碎片拼接復(fù)原模型結(jié)果表九：18類不同高度范圍的中文碎片高度（像素）=0+0.5的碎片編號(hào)無高度（像素）=的碎片編號(hào)6，11,38,45，49,56,59，60,65,76,93,高度（像素）=的碎片編號(hào)9，10，25，26，36，39，47，75，82，89，104，106，123，131，149，162，168，190，194高度（像素）=的碎片編號(hào)1，8，33，35，43，44，46，48，54，57，69，71，78，85，91，94，95，98，113，122，125，127，128，137，138，139，145，150，154，159，165，167，175，17

31、6，184，197，209高度（像素）=的碎片編號(hào)7，20，21，37，53，62，64，68，70，73，79，80，97，100，117，132，163，164，178高度（像素）=的碎片編號(hào)16，18，28，34，61，81，84，86，133，134，153，157，166，171，199，201，203，206高度（像素）=的碎片編號(hào)17,22,111,146,158,182,183,185,188,205高度（像素）=的碎片編號(hào)14,67，107,110,126,140,151,174,198高度（像素）=的碎片編號(hào)5,41,102,103,109，114,115,118,120,

32、124,141,147,152,155,156,186,195,208高度（像素）=的碎片編號(hào)2,19,24,27,31,42,51,63,77,87,88,101,121,143,148,169,180,192,19高度（像素）=的碎片編號(hào)4，13,32,40,52,74,83,108,116,129,135,136,160,161,170,177,200高度（像素）=的碎片編號(hào)204高度（像素）=的碎片編號(hào)30高度（像素）=的碎片編號(hào)3,23,29,50,58,66,92,119,130,142,144,187,191,193高度（像素）=的碎片編號(hào)12,55,96,179,189高度（像

33、素）=的碎片編號(hào)72高度（像素）=的碎片編號(hào)90高度（像素）=的碎片編號(hào)15注：此表中的碎片編號(hào)均比實(shí)際大1，由于MATLAB編程從1開始計(jì)數(shù)。對(duì)18類中任意一類碎片運(yùn)用MATLAB編程可以畫出任意一行中文，舉例如圖二： 圖二：某一類中文文字行排列 MATLAB編程畫出18行中文，對(duì)每行中文出現(xiàn)的奇異碎片進(jìn)行剔除。通過人工干預(yù)和問題一中縱向排列法，可以得到11行有順序的中文，舉例如圖三： 圖三：某一行有順序的中文文字排列干預(yù)的時(shí)間節(jié)點(diǎn)及干預(yù)方式如下：干預(yù)時(shí)間節(jié)點(diǎn)：MATLAB編程排出18行后，對(duì)第18行的第14張碎片、第89張、第71張、第29張、第203張進(jìn)行人工干預(yù)；將高度（像素）=的第4

34、行碎片人工干預(yù)。干預(yù)方式：將這五個(gè)塊碎片分別帶入剩下的12行中文中，將每個(gè)碎片左側(cè)和右側(cè)邊緣灰度值這12行中文碎片的邊緣灰度值進(jìn)行比較，找到差異度最小的連接方式；將高度（像素）=的第4行碎片按照邊緣灰度人工干預(yù)成兩行。 通過人工干預(yù)和MATLAB編程結(jié)合得到附件三中文碎片復(fù)原序號(hào)如下表： 表十：附件三中文碎片復(fù)原序號(hào)495465143186257192178118190951122129289118814161197867699916296131796311616372617720523616810076621423041231471915017912086195261871838148461

35、612435811891221031301938816725891057471156831322001780332021981513317020585152165276014128315982199135127316020316913439315110711517694348418390471214212414477112149971361641275843125131821091971618411018766106150211731571812041391452964111201592180483775554420610104981721715972081381581266817545174

36、0137535693153701663219689146102154114401512071551401851081174101113194119123（2） 英文碎片拼接復(fù)原模型結(jié)果 MATLAB變成可以按照高度不同將英文碎片分為22類，由于分類表格較大，將英文碎片分類表格作為附錄6,。 對(duì)18類中任意一類碎片運(yùn)用MATLAB編程可以畫出任意一行英文，舉例如圖四： 圖四：某一類英文文字行排列 可以畫出18行中文，對(duì)每行中文出現(xiàn)的奇異碎片進(jìn)行剔除。通過人工干預(yù)和問題一的縱向排列方法，可以得到11行有順序的中文，舉例如圖五： 圖五：某一行有順序的英文排列干預(yù)的時(shí)間節(jié)點(diǎn)及干預(yù)方式如下：干預(yù)時(shí)間節(jié)點(diǎn)

37、：MATLAB編程排出22行后，對(duì)第209塊碎片、第8塊、第62塊、第180塊、第5塊進(jìn)行人工干預(yù)；將高度（像素）=的碎片與高度（像素）=人工干預(yù)。干預(yù)方式：將這五個(gè)塊碎片分別帶入剩下的12行中文中，將每個(gè)碎片左側(cè)和右側(cè)邊緣灰度值這12行中文碎片的邊緣灰度值進(jìn)行比較，找到差異度最小的連接方式，發(fā)現(xiàn)要把編號(hào)209的碎片歸入高度（像素）=，把；將高度（像素）=的碎片與高度（像素）=人工干預(yù)成一行。得到附件四英文碎片拼接復(fù)原復(fù)序號(hào)如下表：表十一：附件四英文碎片復(fù)原序號(hào)1917511154190184210418064106414932204653967147201148170196198941131

38、647810391801012610061728146865110729401581869824117150559589230374612719194931418812112610515511417618215122572027116582159139112963138153533812312017585501601879720331204110811613673362071351576431994517379161179143208217496111933142168621695419213311818916219711270846014681741371958471721569623991

39、229018510913218195691671631661881111442063130341311025271781714266205101577414583134551856351691831524481771282001315212514019387894872121771240102115復(fù)原圖片見附錄七和附錄八。 六、問題三分析與模型建立、求解6.1問題三的分析 問題三要求解決雙面打印文件的碎紙片拼接復(fù)原問題。附件5給出的是一頁(yè)英文印刷文字雙面打印文件的碎片數(shù)據(jù)。要求設(shè)計(jì)相應(yīng)的碎紙片拼接復(fù)原模型與算法，并就附件5的碎片數(shù)據(jù)給出拼接復(fù)原結(jié)果。根據(jù)問題二，根據(jù)單詞的殘缺程度給定運(yùn)用MA

40、TLAB編程和人工干預(yù)將碎紙片分為11類，在此基礎(chǔ)上對(duì)于建立0-1規(guī)劃模型:以第j塊碎片右側(cè)與第k塊碎片左側(cè)的差異度最小為目標(biāo)函數(shù)，以第j塊碎片右側(cè)與第k塊碎片左側(cè)是否相連為決策變量（），以每塊碎片右側(cè)一定與某塊碎片左側(cè)相連（），每塊碎片左側(cè)一定與某塊碎片右側(cè)相連（），某塊碎片a、b面一定與某塊碎片a、b面中任意一面相連或不相連（或），為約束條件，建立0-1規(guī)劃模型。按以上模型可將分成的11類分別按橫向排好序，得到11個(gè)長(zhǎng)紙條。然后回到第一問的模型，可將11個(gè)長(zhǎng)紙條按縱向排好序，即可得到復(fù)原圖片。6.2問題三碎紙片拼接復(fù)原模型建立（1） 提取信息第一步：提取每個(gè)碎紙片的殘缺程度和正面和反面的邊

41、緣灰度值，如下： 表示第張碎紙片面的左邊緣，表示第張碎紙片面的右邊緣； 表示第張碎紙片面的右邊緣， 表示第張碎紙片面的右邊緣；第二步：對(duì)個(gè)碎紙片，先根據(jù)單詞的殘缺程度進(jìn)行分類。（把同一張碎紙片的正反面看成兩張不同的碎紙片），再進(jìn)行人工干預(yù)，最終可以分成11類，其中每類包括38張碎紙片（通過觀察可以得到每張碎片a面和b面的單詞殘缺程度相同，因此每類中必包括19張碎紙片的正反面）第三步：分好類后，將以上38張中屬于同一塊碎紙片的正反面相鄰排在一起，如：001a-001b-005a-005b-007a-007b.再重新編號(hào)，依次記為。從第一步已提取的信息中，提取每一類中：(第張碎紙片的殘缺值)(第張

42、碎紙片的右邊緣灰度列向量)（）(第張碎紙片的左邊緣灰度列向量) （） （2）附件五碎紙片拼接復(fù)原模型 首先根據(jù)問題一定義表示表示第j張碎片右側(cè)和第k張碎片左側(cè)的差異度，為第j張碎片右側(cè)與第k張碎片左側(cè)的對(duì)應(yīng)灰度值之差的絕對(duì)值的累和。公式如下： 以第j塊碎片右側(cè)與第k塊碎片左側(cè)的差異度最小為目標(biāo)函數(shù)，以第j塊碎片右側(cè)與第k塊碎片左側(cè)是否相連為決策變量（），以每塊碎片右側(cè)一定與某塊碎片左側(cè)相連（），每塊碎片左側(cè)一定與某塊碎片右側(cè)相連（），某塊碎片a、b面一定與某塊碎片a、b面中任意一面相連或不相連（或），為約束條件，建立0-1規(guī)劃模型。 （13） 其中：為決策變量，=0時(shí)，表示第j張碎片右側(cè)和第k

43、張碎片左側(cè)的不相連； =1時(shí)，表示第j張碎片右側(cè)和第k張碎片左側(cè)的相連； 按以上模型可將分成的11類分別按橫向排好序，得到11個(gè)長(zhǎng)紙條。然后回到第一問的模型，可將11個(gè)長(zhǎng)紙條按縱向排好序，即可得到復(fù)原圖片。6.3問題三碎紙片拼接復(fù)原模型求解6.3.1模型算法（1） 首先根據(jù)英文字母的字體特征和書寫特征對(duì)每塊碎紙片進(jìn)行分類。1. 每個(gè)單詞最多占一行，一行占三個(gè)格子； 經(jīng)計(jì)算每塊碎紙片大概可以容納三個(gè)單詞，每個(gè)單詞占像素點(diǎn)為602. 定義每塊碎紙片的上邊緣單詞的殘缺程度： （14）意義：Q=0或1，上邊緣可容納一個(gè)完整的單詞。 Q越小，上邊緣單詞殘缺程度越大。 以Q來表示每個(gè)碎片的特征。3. 以上

44、提供信息比較精細(xì)，將具有相同特征的分為一類，通過MATLAB編程和人工干預(yù)，可分為11類。其中：， ， ， ， ， ， ， ， ，可以根據(jù)以上Q值結(jié)合人工干預(yù)可得分類，見下表：表十二：附件五英文分類Q1164047020029081189110125108066078018183150155136147111140Q2193159073021163130016031053177146202092190050035019171201Q3205145082118015101071048062052023129119160095009033133051Q41750390971320720930341

45、6119818119908720617319408315611169Q5103196112106055100113096049026099091104006123054134043109Q6142024057102208064154179012028114017158058207013197184116Q71872000861381310569408413706118604512103803014398153042Q8040122182068127188075128117167165008067046168172063195157Q9060152147079059014124036120022

46、089144025044178005192010076Q10002203162041139070166149151001088170065191037090115107180Q111352041410000270800740851761260031850690040771050320071484.對(duì)每一類運(yùn)用0-1規(guī)劃模型，結(jié)合MATLAB編程和人工干預(yù)進(jìn)行排序，可以先將11行進(jìn)行行排序，然后按照問題一列拼接復(fù)合模型排序。6.3.2模型結(jié)果表十三：附件五單面英文復(fù)原序號(hào)136b047a020a164b081b189b029a018b108a066a110a147b183b150a155a140a125a111b078b005a152a147a060a059a014a079a144a120b022a124a192a025b044a178a076b036a010b089a143b200b086b187b131b056b138a045a137b061b94b98a121a038a