基于文檔結構特征的碎紙片拼接復原畢業(yè)論文模板(存儲版)
【正文】 碎片； (2) 若邊緣灰度值全為 0 的碎片超過兩片，則將始末碎片兩兩組合，并選出所有組合進行拼接復原，得到多個復原結果； 特別地，若縱切碎片的邊緣無空白列，即無灰度值全為 0 的邊緣，則選擇左邊緣與其他碎片邊緣匹配度總和最低的碎片為起始碎片，選擇右邊緣與 其他碎片邊緣匹配度總和最低的碎片為末尾碎片．若匹配度最低的碎片有兩片以上，仍采取兩兩組合的方式． 模型建立 假設文件僅為完全縱向切割，以碎片為點，碎片之間的匹配度為邊的權值建立有向a b 內(nèi)江師范學院本科畢業(yè)論文 6 完全圖 ( , )G V E? ，如圖 7 所示： DECBA 圖 8 以碎片為頂點的有向完全圖 其中 {1,2,..., }Vn? 為點集， E 為邊集， ()ijDP? 為匹配矩陣，則哈密頓通路的權值和 Z 可表示為： ij ijijZ Px??? 其中， ijP 為第 i 張碎片右邊緣與第 j 張碎片左邊緣的匹配度， ijx 為 01 變量，其值為 1 時表示 ij 是最優(yōu)拼接邊，值為 0 時表示 ij 不是最優(yōu)拼接邊． 根據(jù)哈密頓通路經(jīng)過完全有向圖所有頂點一次且僅一次 [5]的原理，可得到以下約束： t 1 , 1 ,tj itv t vx j v x i v??? ? ? ???； (2) =1ijxn?? (3) 其中，式 (6)表示哈密頓通路經(jīng)過碎片節(jié)點僅一次，式 (7)表示哈密頓通路通過所有碎片節(jié)點，構成一條通路． 根據(jù)上述分析，以權值和最大為目標函數(shù)，以哈密頓通路原理為約束條件尋找一條最優(yōu)路徑．則縱切碎片拼接復原的數(shù)學模型為： tM ax1,. . 1,=1ij ijijtjvittvijZ P xx j vs t x i vxn????? ???? ????? ?????? (4) 橫縱切碎片的擴散拼接 建模思路 當碎紙機既橫向又縱向切割時，碎片不僅可以左右拼接，還可以上下拼接，這時匹配度 ijP 的計算可表示為橫向匹配度 ijP 和縱向匹配度 ijQ 的加總．隨機選取一張碎片作為起始節(jié)點進行拼接，由切割特征，除邊緣碎片外，每張碎片都可在四個方向上與其余碎片拼接，所以 可根據(jù)四個方向的 可采用擴散的方式從內(nèi)到外層層拼接． 內(nèi)江師范學院本科畢業(yè)論文 7 模型建立 假設文件僅為完全橫向和完全縱向切割，碎片邊緣的匹配度可分為橫向匹配度和縱向匹配度，則各邊權值和 Z 可表示為： ij ij ij iji j i jZ P x Q y?????? 其中， ijP 為橫向匹配度， ijQ 為縱向匹配度， ijx 和 ijy 分別表示左右拼接和上下拼接時的 01 變量，值為 1 表示 ij 是最優(yōu)拼接邊，值為 0 表示 ij 不是最優(yōu)拼接邊． 以所有碎片在該十字隊列中出現(xiàn)一次且僅有一次為約束條件，以權值和最大為目標函數(shù)尋找一條最優(yōu)路徑．則橫縱切碎片拼接復原的數(shù)學模型為： M a x1 , , ( ) 11 , , ( )1 , , ( ) 1..1 , , ( )( 1 ) , ( ) ( )( 1 ) , ( ) ( )ij ij ij iji j i jtjtvittvtjtvittvijijZ P x Q yx j v r jx i v r i ny j v c isty i v c i mx m n r i r jy n m c i c j????????? ? ? ???? ? ???? ? ???? ? ? ???? ? ???? ? ?????????? (5) 模型 (9)中約束條件 主要 刻畫所有碎片節(jié)點排列一次且僅一次， ijy 是 縱向拼接時的01 變量，表示碎片邊緣上下拼接時 ij 邊是否為最優(yōu)拼接． ,mn分別表示碎片最終按 m (11)行 n (19)列進行拼接， ()ci 指在拼接過程中放入矩陣的行坐標， ()ri 指放入矩陣的列坐標． 6 碎紙片拼接模型求解 文中數(shù)據(jù)來源于 20xx 年高教杯全國大學生數(shù)學建模競賽，此次實驗使用 B 題附件中的相關數(shù)據(jù) [6]． 縱切碎片的單一橫向拼接 問題求解 (1) 算法 思想 貪心算 法 [7] 總是做出當前看起來最好的選擇，通過尋找局部最優(yōu)從而找到整體最優(yōu) ．針對本問題，在確定起始碎片之后， 右邊緣與起始碎片匹配度最高的碎片即為局部最優(yōu)解。 橫縱切碎片的擴散拼接 ...........................................................錯誤 !未定義書簽。為此給各位指導老師帶來的不便表示歉意。 6 碎紙片拼接復原模型的建立 ........................................................................ 5 縱切碎片的單一橫向拼接 ............................................................................................ 5 建模思路 .................................................................................................................. 5 始末碎片 .................................................................................................................. 5 模型建立 .................................................................................................................. 5 橫縱切碎片的擴散拼接 ................................................................................................ 6 建模思路 .................................................................................................................. 6 模型建立 .................................................................................................................. 7 7 碎紙片拼接模型求解 .................................................................................... 7 縱切碎片的單一橫向拼接問題求解 ............................................................................ 7 橫縱切碎片的擴散拼接模型求解 ................................................................................ 8 結束語 ......................
研究報告相關推薦
鄂ICP備17016276號-1