1、現(xiàn)在要解決 將顏色的差異性用數(shù)值0,1)的二值矩陣，每一幅圖片都那么拼接處的兩幅圖的對(duì)應(yīng)點(diǎn)的通過匹配度來衡量兩張圖片邊緣處的相似程 因此我們只需要研究二值矩陣的邊緣匹配度即可，只需要構(gòu)建一個(gè)僅僅含有邊緣部分的矩陣C來進(jìn)行研究即可，Ck1i C(k 1)2i或者k1i1.1對(duì)于縱切等長紙片拼接問題的分析在之前的問題中，我們已經(jīng)將縱向撕裂的紙片拼接成縱向等長的長條狀紙片, 縱切紙片的拼接問題。 首先要對(duì)整個(gè)的縱向紙片進(jìn)行數(shù)字化的處理， 矩陣表示出來，然后進(jìn)行二值化處理，得到的是只含有( 對(duì)應(yīng)著一個(gè)獨(dú)立的二值矩陣，兩幅圖如果能夠拼接在一起，像素值會(huì)很接近，因此我們引入匹配度的概念， 度，由于我們所研

2、究的僅僅是圖片的邊緣部分，6 / 5'.對(duì)所有的像素點(diǎn)進(jìn)行求和即可得到相同的Ck2i C(k 1)1i 的時(shí)候，稱為一個(gè)像素點(diǎn)的匹配,點(diǎn)的個(gè)數(shù)。通過C矩陣從而計(jì)算紙片與紙片之間的匹配度，目的是為了得到圖片與圖片之間按照某一種順序拼接而成之后得到的匹配度為最大即可，這是典型哈密頓回路問題， 將節(jié)點(diǎn)看做是紙片，匹配度與費(fèi)用成反比的關(guān)系，要得到匹配度最大此時(shí)的對(duì)應(yīng)費(fèi)用即為最小。最后我們可以建立模型來求解問題，通過前邊部分我們已經(jīng)可以確定邊緣部分的的圖片，以此為基準(zhǔn)，依次按照匹配度與其進(jìn)行匹配，得到匹配度最大的作為拼接圖片，然后進(jìn)行下一次拼接，此時(shí)上一次拼接的圖片應(yīng)該要剔除出去，最后可以依次得

3、到最后的完整圖像。1.問題1基于匹配度的RSSTD問題研究1.1圖像的數(shù)字化處理(1)二值化的處理由于碎紙片的長度特征(碎紙片文件的寬度 彼此之間都相等)，其邊緣所含有 的信息量是最為豐富的，也是我們進(jìn)行匹配所需要的。因此我們對(duì)其進(jìn)行灰度處理，進(jìn)而進(jìn)行二值化的處理，每一條碎片應(yīng)該為408 x48，其像素點(diǎn)的值分別為0 , 1，分別表示顏色的黑與白。 (2)C矩陣的建立C矩陣為408 X 2的矩陣，用以存儲(chǔ)碎紙片的左右邊緣的匹配度，現(xiàn)在可以將問題進(jìn)行化簡，已知起始的碎紙片，然后選擇其他的碎紙片的排列順序， 令其總 的匹配度達(dá)到最大。碎紙片的順序匹配可以簡化為C矩陣之間的邊緣匹配。(3) D矩陣的

4、建立對(duì)于每一個(gè)C矩陣都存在著一個(gè)D矩陣與其相對(duì)應(yīng)， 該矩陣用以存儲(chǔ)每一條邊緣 取值為0的像素點(diǎn)的個(gè)數(shù)，D(i,j),1表示碎紙片的編號(hào)，j=0表示左側(cè)像素點(diǎn)的信息，J=1表示右側(cè)的像素點(diǎn)的信息。例如D(2,1)=100,表示的意思是2號(hào)碎紙片的右側(cè)邊緣有100個(gè)黑色的像素點(diǎn)。(4) 圖片邊緣的選取(5) 碎紙片特征的選取1.2 匹配度的定義為了：為了衡量兩個(gè)碎片之間的匹配程度， 通過行匹配度計(jì)算碎片之間的匹配程度，更加充分的挖掘了碎片邊緣的信息，更為精確。單純的使用像素點(diǎn)的個(gè)數(shù)是極為不準(zhǔn)確的，因此我們使用匹配度Mfi來作為我們的評(píng)價(jià)標(biāo)準(zhǔn)：_ 朮索相同的數(shù)量Mij=4082基于TSP問題的模型建

5、立與求解由匹配度的定義我們可以知道10個(gè)碎片之間的邊緣匹配度，現(xiàn)在可以將問題化 簡：已知起始時(shí)的碎片與其他碎片之間的匹配度，尋找一個(gè)序列使起始碎片與其 他的碎片之間的總的匹配度達(dá)到最大值。模型建立的步驟如下：(1)(2)找到起始的碎片，得到起始碎片與其他碎片的匹配程度 用節(jié)點(diǎn)來表示碎片，以有向線段的長度表示費(fèi)用，費(fèi)用的具體數(shù)值 叫i=1jMii| (ki與匹配度的則成反比關(guān)系)箭頭表示前一條碎片的右側(cè) 邊緣到后一條碎片的左側(cè)邊緣。現(xiàn)在要求找到一條路徑遍歷所有的節(jié)點(diǎn)使得費(fèi)用最小，即為哈密頓 回路如圖一所示。2.1決策變量的分析：我們給出的所有路徑之中只存在有一條哈密頓回路，因此 我們引入決策變量

6、Xij，Xij =1表示(i, j)進(jìn)入了哈密頓回路，反之則表示沒有進(jìn)入到哈密頓回路中。Wij X ijE2.2對(duì)于目標(biāo)函數(shù)的分析：兩紙片之所以能夠拼接在一起是因?yàn)閮杉埰南噜徧?的邊緣匹配度最大，即對(duì)應(yīng)著在該路徑的費(fèi)用最小，min(i, j)其中的(i, j)表示的是一條路徑，即為兩紙片之間的對(duì)應(yīng)的方式,Wij為在該路徑上的費(fèi)用。2.3對(duì)于約束條件的分析：由于該圖形之中只存在有位移的一條哈密頓路徑，所以必然要保證給定的（i,j）只存在一條哈密頓回路，因此需要滿足X 八ij(i,j) EX 八ji(i,j) E（j,i）僅僅只有一次能夠進(jìn)入到哈密頓回路中去。經(jīng)過以上的分析我們可以得到以下的 T

7、SP模型（1）假設(shè)存在哈密頓回路，回路之中存在著n個(gè)節(jié)點(diǎn)，得到線性規(guī)劃的模型如 下所示：min(i,j)WjXijEX ijX jiij0,1,(i, j)模型的求解：算法如圖所示（1）將碎片放入到一起進(jìn)行混合后選擇起始的紙片并且將其從混合紙片中剔除，記為 叫依次計(jì)算右側(cè)邊緣與其他的碎片Xj左側(cè)邊緣的匹配度幅選擇匹配度最大的碎片，人作為碎片的右側(cè)的碎片，并且將其記為從混合的紙片之中將其剔除掉后重復(fù)（3）-（4）之間的步驟，一直到所有的碎片為空。排序后的碎片順序（豎直方向的排列）第一排35791第二排825614第三排28418N應(yīng)用上邊所得到的 TSP模型，以及算法可以求 根據(jù)TSP模型左右拼接后的圖形第一排17169第二排12382412614251513第三排11242通過求解我們發(fā)現(xiàn)，利用TSP模型以及線性規(guī)劃的知識(shí)可以求解出最優(yōu)解，原因在于匹配度的定義比較好。由于豎直方向的圖片拼接的比較好，所以使得縱向切條的邊緣二值矩陣所包含的信息量比較豐富，能夠很大的提高匹配度的準(zhǔn)確性。從而使得結(jié)果也變得更為準(zhǔn)確。拼接后的視圖如圖所示：R 沁1V因?yàn)樵谖覀兺晡覀冊俑谏鲜龅乃榧埰唇拥倪^程之中,對(duì)