【正文】 mij i jkP E k E k?? ? ?? (1) (1)式中 ijP 為任意第 i 張碎片和第 j 張碎片的邊緣匹配度， ()iEk為第 i 張碎片邊緣的第 k 個像素點坐標灰度值． 針對左右拼接的情況，匹配度可進一步表示為： 1 (1 ( ) ( ) )mij ir jlkP E k E k?? ? ?? 1 (1 ( ) ( ) )mji il jrkP E k E k?? ? ?? 其中 ijP 表示第 i 張碎片的右邊緣和第 j 張碎片的左邊緣拼接的匹配度， ()irEk表示第i 張碎片右邊緣第 k 個像素點坐標灰度值， ()jlEk表示第 j 張碎片左邊緣第 k 個像素點坐標灰度值．類似地， jiP 表示第 j 張碎片右邊緣和第 i 張碎片左邊緣拼接的匹配度， ()ilEk表示第 i 張碎片左邊緣第 k 個像素點坐標灰度值， ()jrEk表示第 j 張碎片右邊緣第 k 個像素點坐標灰度值． 同理，上下邊緣拼接的匹配度可表示為： 1 (1 ( ) ( ) )mij id jukQ E k E k?? ? ?? 1 (1 ( ) ( ) )mji iu jdkQ E k E k?? ? ?? 其中， ijQ 為碎片 i 下邊緣與碎片 j 上邊緣的匹配度， jiQ 為碎片 j 下邊緣與碎片 i 上邊緣的匹配度， u 代表上邊緣， d 代表下邊緣． 以下內(nèi)容省略 ?? 方向場匹配 (1) 基本原理 由文字筆畫的連續(xù)性可知筆畫的外邊緣輪廓線也是光滑的，為描述筆畫外邊緣輪廓線的光滑性，引入斜率的概念，若邊緣上相匹配的像素點有相同的斜率（如圖 3 中 b 若12kk? ，表示有相同的斜率 ），則認為該組像素點屬于同一筆畫． 內(nèi)江師范學院本科畢業(yè)論文 5 DCBA 圖 3 方向場匹配過程示意圖 在判斷斜率是否相同之前首先應判斷像素點是否匹配，如圖 3 中像素點 A 分別與對應碎片的像素點 B C D、 、 的灰度值進行比較，只有在灰度值相同的情況下，才進一步計算兩對應像素點的斜率，如在圖 3 中僅判斷 A 點斜率與 ,BC點的斜率是否相同． 以下內(nèi)容省略 ?? 5 碎紙片拼接復原模型的建立 縱切碎片的單一橫向拼接 建模思路 匹配度形象的反映了碎片拼接時的契合程度，因此可利用匹配度的高低表示碎片拼接復原的效果．哈密頓通路是經(jīng)過圖中所有頂點一次且僅一次的通路，而碎片的拼接復原過程就是根據(jù)起始碎片與其余各碎片的匹配度將其依次排列的過程，則以碎片為點，碎片之間的匹配度為邊的權值，縱切碎片的拼接復原問題可轉化為尋找該有向完全圖的哈密頓通路問題． 始末碎片 根據(jù)書寫或打印規(guī)律，縱切碎片的左右邊緣有空白列，即灰度值全為 0．則可將左邊緣灰度值全為 0 的碎片作為候選的起始碎片，右邊緣灰度值全為 0 的碎片作為候選的末尾碎片，當根據(jù)灰度值全為 1 的原則選擇始末碎片時，可分為兩種情況： (1) 若邊緣灰度值全為 0 的碎片恰為兩片，則分別以這兩片為始末碎片； (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)