圖形識(shí)別匹配與三維影像重建課件

1第八章

圖形識(shí)別、匹配與三維影像重建1第八章

圖形識(shí)別、匹配與三維影像重建28.1前言8.2

統(tǒng)計(jì)圖形識(shí)別8.3

影像間的匹配對(duì)應(yīng)

8.4匹配演算法原理8.5三維影像重建8.6二維影像的深度計(jì)算8.4.1動(dòng)態(tài)規(guī)劃式的BSSC解法8.4.2KMP演算法8.6.1稠密式視差估測(cè)8.6.2相機(jī)校正8.3.1Harris角點(diǎn)偵測(cè)法8.3.2

SIFT關(guān)鍵點(diǎn)偵測(cè)法8.3.3點(diǎn)集合匹配法28.1前言8.2統(tǒng)計(jì)圖形識(shí)別8.4.1動(dòng)態(tài)規(guī)劃式的B38.2統(tǒng)計(jì)圖形識(shí)別貝氏決策理論

假設(shè)有二類木頭，A和B，Ａ佔(zhàn)P(A)的比例而B佔(zhàn)P(B)的比例，。已知。利用木頭的紋理X來評(píng)估該木頭的種類。圖8.2.1P(X|A)和P(X|B)的分佈圖

當(dāng)時(shí)，，我們說該木頭為A類，仍會(huì)犯誤判的風(fēng)險(xiǎn)，畢竟仍有機(jī)率值。

38.2統(tǒng)計(jì)圖形識(shí)別貝氏決策理論假設(shè)有二類木頭，A和B，4我們有興趣的是給一個(gè)X值，該木頭屬於A或B的機(jī)率為何？依據(jù)貝氏法則，透過貝氏法則，這個(gè)事後機(jī)率就可由事前機(jī)率P(A)、P(B)、

和求得。此處。圖8.2.2P(A|X)和P(B|X)的分佈圖

當(dāng)，，這時(shí)可判斷該木頭為A，畢竟冒的風(fēng)險(xiǎn)較低，也就是。去掉和的項(xiàng)，當(dāng)時(shí)，我們判斷該木頭為A。4我們有興趣的是給一個(gè)X值，該木頭屬於A或B的機(jī)率為何？依據(jù)5將紋理由一維擴(kuò)充到d維而將木頭的種類由2種擴(kuò)充到t種。令第i類的識(shí)別器為，此處紋理向量而代表第i類木頭，。作用單調(diào)遞增函數(shù)於上，得識(shí)別器圖8.2.3識(shí)別器示意圖如果為最大值，該木頭分類為Tj

5將紋理由一維擴(kuò)充到d維而將木頭的種類由2種擴(kuò)充到t6視窗在影像上的移動(dòng)，可得到強(qiáng)度變化情形：(1)平面：往任何方向移動(dòng)僅造成小變化(2)含一條邊：與邊平行的變化量小；反之則大(3)含角點(diǎn)或獨(dú)立點(diǎn)：往任何方向變化皆大8.3影像間的匹配對(duì)應(yīng)

8.3.1

Harris角點(diǎn)偵測(cè)法

(1)(2)(3)68.3影像間的匹配對(duì)應(yīng)

8.3.1Harris角點(diǎn)偵7令

利用高斯函數(shù)來平滑雜訊的影響，令綜合灰階梯度變化之影響可表示為

7令8函數(shù)E是一種局部自我關(guān)聯(lián)的函數(shù)，矩陣M就是函數(shù)E的代表。矩陣M的兩個(gè)特徵值代表：和皆很?。捍硪暣皟?nèi)為平滑區(qū)和中，一大一?。捍砗贿叺膮^(qū)域和皆很大：代表含角點(diǎn)的區(qū)域圖8.3.1.1矩陣M的特徵值所代表的意義8函數(shù)E是一種局部自我關(guān)聯(lián)的函數(shù)，矩陣M就是函數(shù)E的代表。矩9影響值R=det(M)-k×(trace(M))2決定是否小區(qū)域內(nèi)有角點(diǎn)，判斷的準(zhǔn)則為且：代表平滑區(qū)：代表含一邊的區(qū)域：代表有角點(diǎn)的區(qū)域利用以上方法可以將所有角點(diǎn)找出來。(a)原始影像(b)找出的角點(diǎn)集9影響值R=det(M)-k×(trace(M))2決定10將影像進(jìn)行縮減取樣n次，例如n=2可分成3個(gè)影像尺度，進(jìn)一步利用m個(gè)不同標(biāo)準(zhǔn)差的高斯函數(shù)，例如m=4，高斯函數(shù)標(biāo)準(zhǔn)差分別是

，將不同高斯函數(shù)與3個(gè)影像尺度作迴積運(yùn)算：接著對(duì)兩相鄰的尺度做DOG:

8.3.2

SIFT關(guān)鍵點(diǎn)偵測(cè)法10將影像進(jìn)行縮減取樣n次，例如n=2可分成3個(gè)影像尺度11圖8.3.2.1

DOG金字塔11圖8.3.2.1DOG金字塔12考慮每個(gè)像素與周圍8個(gè)像素及上下層同位置周圍9個(gè)像素做比較，如果該像素為極值，則設(shè)為候選關(guān)鍵點(diǎn)。圖8.3.2.2

DOG金字塔找極值12考慮每個(gè)像素與周圍8個(gè)像素及上下層同位置周圍9個(gè)像素做比13以每個(gè)候選關(guān)鍵X點(diǎn)當(dāng)原點(diǎn)，算出

其中的三維座標(biāo)，令座標(biāo)時(shí)有極值點(diǎn)D(

)。

代表一個(gè)極值點(diǎn)，如果內(nèi)的三個(gè)座標(biāo)值都小於0.5;若大於0.5則依照該方向來內(nèi)插出新的候選關(guān)鍵整數(shù)點(diǎn)，繼續(xù)用新的候選關(guān)鍵點(diǎn)計(jì)算二階泰勒展開式求值。若，代表此區(qū)域的對(duì)比較低，應(yīng)移除此關(guān)鍵點(diǎn)。13以每個(gè)候選關(guān)鍵X點(diǎn)當(dāng)原點(diǎn)，算出14除掉邊上的候選關(guān)鍵點(diǎn)，先求出赫斯矩陣

H的特徵值和可計(jì)算如下:可得14除掉邊上的候選關(guān)鍵點(diǎn)，先求出赫斯矩陣15令且，得到得判斷式令，若判斷式成立，移除邊上的候選關(guān)鍵點(diǎn)。15令且，得到16以剩餘關(guān)鍵點(diǎn)為中心的區(qū)塊，計(jì)算區(qū)塊內(nèi)每個(gè)像素的梯度值

與梯度方向關(guān)鍵點(diǎn)的旋轉(zhuǎn)不變性(RotationInvariant)。

16以剩餘關(guān)鍵點(diǎn)為中心的區(qū)塊，計(jì)算區(qū)塊內(nèi)每個(gè)像素的梯度值17圖8.3.2.3決定關(guān)鍵點(diǎn)的特徵向量17圖8.3.2.3決定關(guān)鍵點(diǎn)的特徵向量18圖8.3.2.4

SIFT流程圖18圖8.3.2.4SIFT流程圖19(a)輸入的腦血管影像(b)

SIFT演算法選取到的關(guān)鍵點(diǎn)圖8.3.2.519(a)輸入的腦血管影像(b)SIFT演算法選取到的關(guān)20另一種作法是尋找轉(zhuǎn)移矩陣T，使ToF與有最小誤差。令，，代表中的與中的之距離

引入最大可能(Maximum-likelihood)的觀念，得

其中p(d)為一常態(tài)分佈(NormalDistribution)。匹配的精神就是找一個(gè)T使得上式有最大值。

8.3.3點(diǎn)集合匹配法

20另一種作法是尋找轉(zhuǎn)移矩陣T，使ToF與218.4匹配演算法原理

8.4.1動(dòng)態(tài)規(guī)劃式的BSSC解法BSSC(BandedString-to-StringCorrection)之目的為在樣本和正本之間找出最大的匹配點(diǎn)與匹配點(diǎn)的位置。圖8.4.1.1匹配結(jié)果將和想像成特徵值。因?yàn)橐暡畹年P(guān)係，只能與範(fàn)圍內(nèi)的特徵匹配到。

樣本=正本=給一個(gè)例子如下：圖8.4.1.1的搜尋範(fàn)圍就是黑色粗邊框住的範(fàn)圍而得到的最佳匹配就是鋸齒形的路徑上之黑圓點(diǎn)集。218.4匹配演算法原理

8.4.1動(dòng)態(tài)規(guī)劃式的BSS22匹配算子取代算子R

刪除算子D

D(a)=的花費(fèi)定為1插入算子I

I()=a的花費(fèi)定為1a

b，R(a)=b的花費(fèi)定為1a=b，R(a)=b的花費(fèi)定為0圖8.4.1.1一共含有下列十四個(gè)運(yùn)算(1)I()=P1(2)R(T1)=P2(3)R(T2)=P3(4)D(T3)=(5)D(T4)=(6)I()=P4(7)R(T5)=P5(8)R(T6)=P6(9)D(T7)=(10)D(T8)=(11)I()=P7(12)I()=P8(13)R(T9)=P9(14)R(T10)=P1022匹配算子取代算子Rab，R(a)=b的花費(fèi)定為23動(dòng)態(tài)規(guī)劃核心式子Edit[0,k]=kEdit[k,0]=k表示將T[1…i]轉(zhuǎn)換成P[1…j]的花費(fèi)。edit(Ti,Pj)表示R(Ti)=Pj的花費(fèi)edit(Ti,)表示D(Ti)=的花費(fèi)edit(,Pj)表示I()=Pj的花費(fèi)BSSC的時(shí)間複雜度為n為正本長(zhǎng)度，為視差23動(dòng)態(tài)規(guī)劃核心式子Edit[0,k]=kE248.4.2KMP演算法樣本先進(jìn)行事前處理利用樣本中子字串(Substring)與前置字串(PrefixString)的吻合度，並記錄其吻合的長(zhǎng)度於陣列J[]中。i12345678910P[i]acacaaacacJ[i]0012311234P[3]=a=P[1]

J[3]=1P[3…5]=aca=P[1…3]

J[5]=3P[7…10]=acac=P[1…4]

J[10]=4KMP字串匹配演算法T

[]=cccacacaaacaccaaT[i]P[i]，。T[4…13]=P[1…10]。T[5]P[1]，T[6]=P[1]

T[6…8]=P[1…3]

T[9]P[4]，J[4]=2

P[1…J[4]-1]=P[1]=T[9-J[4]+1…8]=T[8]陣列J[]提供了一個(gè)跳躍的機(jī)制，讓匹配動(dòng)作可一直往右前進(jìn)。

KMP的時(shí)間複雜度為O(m+n)248.4.2KMP演算法樣本先進(jìn)行事前處理i123456258.5三維影像重建

8.5.1稠密式視差估測(cè)

問題定義

稠密式視差估測(cè)是在L上的所有像素中和R上的所有像素中找到一個(gè)對(duì)應(yīng)。二階段式的分割與克服方法

圖8.5.1.1稠密視差估測(cè)示意圖

(DenseDisparityEstimation)258.5三維影像重建

8.5.1稠密式視差估測(cè)問題定26第一階段的分割與克服方法

1.利用Marr-Hildreth測(cè)邊法得到主要特徵像素集：

L上第N/2列中的主要特徵集可表示為：R上第N/2列中的主要特徵集可表示為：2.和的匹配工作

其中26第一階段的分割與克服方法

1.利用Marr-Hildr27圖8.5.1.2和的匹配其中取代算子：27圖8.5.1.2和28(a)右遮蔽花費(fèi)(b)左遮蔽花費(fèi)

圖8.5.1.3右遮蔽花費(fèi)和左遮蔽花費(fèi)示意圖

3.加入消去法則

若兩兩匹配位置的差，形成之序列為，則-2的視差偏移不太正常，可以予以去除。假設(shè)在列時(shí)的平均視差偏移序列為。若新進(jìn)來的視差偏移序列為，則16的視差偏移可予以去除。

28(a)右遮蔽花費(fèi)(b)左遮蔽花費(fèi)圖8.5.129第二階段的分割與克服方法

在二段匹配的子區(qū)間中，再進(jìn)一步找出個(gè)別的像素配對(duì)圖8.5.1.4二子區(qū)間匹配2.利用平均視差偏移量d，可將第二階段的工作轉(zhuǎn)成BSSC問題的解決上R算子：D算子：類似於前面定義的左遮蔽花費(fèi)I算子：類似於前面定義的右遮蔽花費(fèi)W為事前定義好的小視窗29第二階段的分割與克服方法在二段匹配的子區(qū)間中，圖8.30圖8.5.1.5對(duì)應(yīng)的BBSC搜尋空間30圖8.5.1.5對(duì)應(yīng)的BBSC搜尋空間31圖8.5.1.6輸入的二張影像

(a)影像L

(b)影像R

圖8.5.1.7得到的視差圖

圖8.5.1.8重建後的三維五角大廈圖31圖8.5.1.6輸入的二張影像(a)影像L(b)328.5.2相機(jī)校正我們有三個(gè)座標(biāo)系統(tǒng)，世界座標(biāo)系統(tǒng)(WorldCoordinateSystem)、相機(jī)座標(biāo)系統(tǒng)(CameraCoordinatesSystem)和二維的影像系統(tǒng)(ImageSystem)。根據(jù)三角比例關(guān)係，可得其中f為焦距長(zhǎng)。

328.5.2相機(jī)校正我們有三個(gè)座標(biāo)系統(tǒng)，世界座標(biāo)系統(tǒng)(W33圖8.5.2.1

相機(jī)座標(biāo)系統(tǒng)和影像座標(biāo)系統(tǒng)影像平面鏡心理論上為投射到影像座標(biāo)系統(tǒng)的理想位置。

因?yàn)橥哥R輻射效應(yīng)，實(shí)際投射到的影像座標(biāo)系統(tǒng)的位置應(yīng)為。滿足下式

33圖8.5.2.1相機(jī)座標(biāo)系統(tǒng)和影像座標(biāo)系統(tǒng)影像平面鏡34上兩式中的誤差項(xiàng)和可表示成在光學(xué)透鏡的輻射失真(RadialDistortion)的影響下，內(nèi)部參數(shù)滿足，我們令，只關(guān)心的求解。

前面所提的為實(shí)數(shù)，但在數(shù)位影像的座標(biāo)系統(tǒng)一般皆為整數(shù)座標(biāo)。假設(shè)感應(yīng)器(Sensor)的

方向共有個(gè)感應(yīng)器。是影像在x方向的解析度。令34上兩式中的誤差項(xiàng)和可表示成35而為影像的中心座標(biāo)。和的關(guān)係可表示如下其中s

為待解的放大係數(shù)。已知投影到影像座標(biāo)系統(tǒng)的理想位置為。進(jìn)而得到同理可得且35而為影像的中心座標(biāo)。36

再利用三維世界座標(biāo)系統(tǒng)和二維影像座標(biāo)系統(tǒng)的關(guān)係可得旋轉(zhuǎn)矩陣

R

分別對(duì)x軸、y軸和z軸達(dá)到任一角度的旋轉(zhuǎn)，可寫成下式至此，已經(jīng)六個(gè)外部參數(shù)(ExtrinsicParameters)分別為、、、、和及五個(gè)內(nèi)部參數(shù)(IntrinsicParameters)分別為、、、和。接下來要利用數(shù)值的方法求解這些參數(shù)。36再利用三維世界座標(biāo)系統(tǒng)和二維影像37先解出五個(gè)外部參數(shù)，在二維影像座標(biāo)上取一經(jīng)過原點(diǎn)的向量，且在相機(jī)座標(biāo)上取一平行的向量，所以得令則我們得到再利用五組世界座標(biāo)

和五組底片上的真實(shí)座標(biāo)就可解出、、、、。

37先解出五個(gè)外部參數(shù)，在二維影像座標(biāo)上取一經(jīng)過原點(diǎn)的向量38令則旋轉(zhuǎn)矩陣可改寫成利用中每一行向量與列向量為單位長(zhǎng)，可得下式其中。

38令39

因?yàn)镽為正交矩陣，任兩行的內(nèi)積必為零。將R的第一行和第二行做內(nèi)積，可以得到

此等式可解得的兩個(gè)解，如下前面曾推導(dǎo)過暫時(shí)將和設(shè)為零，得