版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
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è)差異度最小為目標(biāo)函數(shù),以第i張碎片右側(cè)與第
2、j張碎片左側(cè)是否相連為決策變量,以每張碎片右側(cè)一定與某張碎片左側(cè)相連、每張碎片左側(cè)一定與某張碎片右側(cè)相連為約束條件。算法為先提取任意張碎片邊緣灰度值,得到差異度矩陣,帶入規(guī)劃模型中,通過LINGO軟件找到中英文碎片的拼接方法,得到復(fù)原序號如表一、表二,從而得到出中文與英文復(fù)原圖片。表一:中文碎片的復(fù)原序號008014012015003010002016001004005009013018011007017000006表二:英文碎片的復(fù)原
3、序號003006002007015018011000005001009013010008012014017016004檢驗中英文碎片拼接復(fù)原順序準(zhǔn)確性,利用MATLAB搜索算法,可以得到中英文碎片拼接方法。結(jié)果表明兩種方法得出的中英文復(fù)原順序相同,復(fù)原圖片相同,同時人工檢驗中英文復(fù)原圖片中無明顯語法、單詞錯誤,證明復(fù)原圖片準(zhǔn)確。針對問題二,由于每張碎片有左側(cè)、右側(cè)和上側(cè)、下側(cè),與問題一相同,可以定義兩個差異度指數(shù),建立雙目標(biāo)01規(guī)劃模型
4、。但由于差異度矩陣過大,決策變量復(fù)雜,我們又建立了改進的簡化模型,定義高度差,運用聚類分析方法,按照高度不同將所有碎片分為18類,然后再以第j塊碎片左側(cè)與第i塊碎片右側(cè)的差異度最小為目標(biāo)函數(shù),以第i塊碎片右側(cè)與第j塊碎片左側(cè)是否相連為決策變量,以每塊碎片右側(cè)一定與某塊碎片左側(cè)相連、每塊碎片左側(cè)一定與某塊碎片右側(cè)相連,滿足高度差閾值為約束條件,建立單目標(biāo)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è)的差異度最小為目標(biāo)函數(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張碎
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2013年全國大學(xué)生數(shù)學(xué)建模競賽國家一等獎?wù)撐?b題碎紙片的拼接復(fù)原的研究
- 數(shù)學(xué)建模優(yōu)秀論文模板(全國一等獎模板)
- 全國電工杯數(shù)學(xué)建模全國一等獎?wù)撐?風(fēng)電功率預(yù)測問題
- 全國一等獎erp沙盤
- 全國大學(xué)生數(shù)學(xué)建模競賽一等獎?wù)撐?012年葡萄酒的評價
- 2010數(shù)學(xué)建模國家一等獎?wù)撐?b)
- 數(shù)學(xué)建模國家一等獎優(yōu)秀論文
- 隨機事件的概率教學(xué)設(shè)計(全國一等獎)
- 隨機事件的概率教學(xué)設(shè)計全國一等獎
- 2010數(shù)學(xué)建模國家一等獎?wù)撐?b題)
- 2013年全國大學(xué)生數(shù)學(xué)建模競賽國家一等獎?wù)撐?c題古塔的變形
- 一等獎
- 2012全國數(shù)學(xué)建模論文a題(葡萄酒)省一等獎
- 碎紙片的拼接國家二等獎優(yōu)秀論文
評論
0/150
提交評論