機(jī)器視覺-第5章-特征檢測(cè)與匹配VIP

特征提取與運(yùn)動(dòng)估計(jì)：5.特征檢測(cè)與匹配

Hough變換與形狀檢測(cè)特征匹配

角點(diǎn)檢測(cè)

總結(jié)角點(diǎn)檢測(cè)角點(diǎn)定義角點(diǎn)檢測(cè)算法角點(diǎn)檢測(cè)算法比較1.1角點(diǎn)的定義Part14角點(diǎn)的定義角點(diǎn)是圖像中某些特征比較突出的像素點(diǎn)。分為以下幾種類型：灰度梯度最大值對(duì)應(yīng)的像素點(diǎn)兩條直線或曲線的交點(diǎn)一階梯度值和梯度方向變化率最大的像素點(diǎn)一階導(dǎo)數(shù)值最大但二階導(dǎo)數(shù)值為0的像素點(diǎn)1.2Harris角點(diǎn)檢測(cè)Part15Harris角點(diǎn)是從像素值變化的角度定義的，像素值的局部峰值處就是Harris角點(diǎn)。Harris角點(diǎn)檢測(cè)算法基本思想：選取一個(gè)固定的窗口在圖像上以任意方向滑動(dòng)，如果灰度都有較大的變化，那么就認(rèn)為這個(gè)窗口內(nèi)部存在角點(diǎn)。1.2Harris角點(diǎn)檢測(cè)Part16

1.2Harris角點(diǎn)檢測(cè)Part17

1.2Harris角點(diǎn)檢測(cè)Part18

1.2Harris角點(diǎn)檢測(cè)Part19

任何一個(gè)函數(shù)表達(dá)式，均可由泰勒公式進(jìn)行展開。利用泰勒展開對(duì)窗口內(nèi)的像素變化量進(jìn)行轉(zhuǎn)化，對(duì)灰度變化部分進(jìn)行泰勒展開可得：1.2Harris角點(diǎn)檢測(cè)Part110

1.2Harris角點(diǎn)檢測(cè)Part111

1.2Harris角點(diǎn)檢測(cè)Part112

1.2Harris角點(diǎn)檢測(cè)Part113

1.2Harris角點(diǎn)檢測(cè)Part114Harris角點(diǎn)檢測(cè)步驟：

1.2Harris角點(diǎn)檢測(cè)Part115Harris角點(diǎn)檢測(cè)步驟：

如果需要再3*3或者5*5的領(lǐng)域進(jìn)行非極大值抑制，則局部最大值點(diǎn)即為圖像中的角點(diǎn)。1.2Harris角點(diǎn)檢測(cè)Part116Harris角點(diǎn)檢測(cè)示例：原圖歸一化后的系數(shù)圖像繪制Harris角點(diǎn)1.3SIFT角點(diǎn)檢測(cè)Part117尺度不變特征變換（Scale-InvariantFeatureTransform，SIFT）是一種經(jīng)典特征檢測(cè)算法。該算法在空間尺度中尋找角點(diǎn)，并提取對(duì)應(yīng)的特征向量。SIFT算法將一幅圖像映射（變換）為一個(gè)局部特征向量集；特征向量具有平移、縮放、旋轉(zhuǎn)不變性，同時(shí)對(duì)光照變化、仿射及投影變換也有一定不變性。1.3SIFT角點(diǎn)檢測(cè)Part118SIFT角點(diǎn)檢測(cè)步驟：1、構(gòu)建尺度空間;

2、DoG差分金字塔,對(duì)相鄰兩個(gè)尺度空間的圖像進(jìn)行相減;3、極值檢測(cè)及特征點(diǎn)篩選，去除低響應(yīng)特征點(diǎn)和不穩(wěn)定的特征點(diǎn);4、確定特征點(diǎn)主方向;5、生成特征點(diǎn)描述向量。Part1191、構(gòu)建尺度空間

1.3SIFT角點(diǎn)檢測(cè)Part1202、DoG差分金字塔

1.3SIFT角點(diǎn)檢測(cè)Part1213、極值檢測(cè)及特征點(diǎn)篩選為了尋找尺度空間的極值點(diǎn)，每一個(gè)像素點(diǎn)都要同其同一尺度空間和相鄰的尺度空間的所有相鄰點(diǎn)進(jìn)行比較，以確保在尺度空間和二維圖像空間都檢測(cè)到極值點(diǎn)。一個(gè)像素點(diǎn)如果比所有相鄰點(diǎn)都大或小，就認(rèn)為該點(diǎn)是圖像在該尺度下的一個(gè)特征點(diǎn)。通過極值比較得到的DoG圖像局部極值點(diǎn)是在離散空間搜索得到的，離散空間的極值點(diǎn)并不是真正的極值點(diǎn)，還需要進(jìn)一步去除低響應(yīng)特征點(diǎn)和不穩(wěn)定的特征點(diǎn)。1.3SIFT角點(diǎn)檢測(cè)Part122

①對(duì)尺度空間DoG函數(shù)曲線擬合以精確確定關(guān)鍵點(diǎn)的位置和尺度；1.3SIFT角點(diǎn)檢測(cè)Part123

1.3SIFT角點(diǎn)檢測(cè)求導(dǎo)并令其為0，得到

②

在已檢測(cè)到的特征點(diǎn)中去除低對(duì)比度與不穩(wěn)定的特征點(diǎn)；Part124③

消除邊緣響應(yīng)：通過利用特征點(diǎn)處的Hessian矩陣；1.3SIFT角點(diǎn)檢測(cè)

Part1251.3SIFT角點(diǎn)檢測(cè)

Part1264、確定特征點(diǎn)主方向

1.3SIFT角點(diǎn)檢測(cè)

Part127在得到特征點(diǎn)的梯度分布特征后，使用直方圖統(tǒng)計(jì)領(lǐng)域內(nèi)像素的梯度和方向。直方圖的峰值方向代表了特征點(diǎn)的主方向。1.3SIFT角點(diǎn)檢測(cè)Part128為了增強(qiáng)特征點(diǎn)近的鄰域點(diǎn)對(duì)關(guān)鍵點(diǎn)方向的作用并減少突變的作用，可以使用高斯函數(shù)對(duì)直方圖進(jìn)行平滑操作。同時(shí)為了得到更精確的方向，還可以對(duì)離散的梯度直方圖進(jìn)行插值擬合。除將直方圖中最大值所在的方向作為該特征點(diǎn)的主方向外，為了增強(qiáng)匹配的魯棒性，保留峰值大于主方向峰值80％的方向作為該特征點(diǎn)的輔方向。1.3SIFT角點(diǎn)檢測(cè)Part1295、生成特征點(diǎn)描述向量1.3SIFT角點(diǎn)檢測(cè)描述子應(yīng)不隨周圍環(huán)境的變化而變化，同時(shí)具有較高的獨(dú)立性，以保證匹配率，其生成有以下三個(gè)步驟：（1）校正旋轉(zhuǎn)主方向，確保旋轉(zhuǎn)不變性；（2）生成128維的特征向量；（3）歸一化處理與門限值處理。Part1301.3SIFT角點(diǎn)檢測(cè)（1）校正旋轉(zhuǎn)主方向，確保旋轉(zhuǎn)不變性；為了保證特征向量的旋轉(zhuǎn)不變性，要將坐標(biāo)軸旋轉(zhuǎn)為特征點(diǎn)的主方向，旋轉(zhuǎn)后鄰域內(nèi)像素的新坐標(biāo)為：

其中，??為主方向角度。Part1311.3SIFT角點(diǎn)檢測(cè)（2）生成128維的特征向量；旋轉(zhuǎn)后以特征值為中心采集16×16的鄰域像素樣本，通過高斯加權(quán)平均后將其分配到對(duì)應(yīng)的4×4大小的子區(qū)域內(nèi)，并把梯度值分配到8個(gè)方向上，因此最終生成一個(gè)4×4×8的128維特征點(diǎn)描述子特征向量。Part1321.3SIFT角點(diǎn)檢測(cè)（3）歸一化處理與門限值處理。

Part1331.3SIFT角點(diǎn)檢測(cè)針對(duì)非線性光照，相機(jī)飽和度變化造成某些方向的梯度值過大，而對(duì)方向的影響微弱的問題，可對(duì)歸一化后的特征向量L各分量設(shè)置閾值(一般取0.2)來截?cái)噍^大的梯度值，大于閾值的分量則賦值為閾值，小于閾值的則保持不變。之后再進(jìn)行一次歸一化處理，以提高特征的鑒別性。1.3SIFT角點(diǎn)檢測(cè)Part134SIFT角點(diǎn)檢測(cè)示例：原圖SIFT角點(diǎn)檢測(cè)后1.4SURF角點(diǎn)檢測(cè)Part135為了解決SIFT中計(jì)算速度較慢，無法滿足系統(tǒng)實(shí)時(shí)性要求的問題，

對(duì)SIFT進(jìn)行改進(jìn)，產(chǎn)生了一種對(duì)SIFT特征點(diǎn)加速的SURF(SpeededUpRobustFeatures,加速穩(wěn)健特征)特征點(diǎn)。SURF算法步驟與SIFT大致類似，但使用Hessian矩陣的行列式值作為特征點(diǎn)檢測(cè)并用積分圖加速運(yùn)算；使用基于2D離散小波變換響應(yīng)構(gòu)造描述子，并有效利用積分圖SURF的描述子，從而有效提升算法的檢測(cè)速度。1.4SURF角點(diǎn)檢測(cè)Part136SURF角點(diǎn)檢測(cè)步驟：1、構(gòu)建尺度空間;

2、定位特征點(diǎn)3、選取特征點(diǎn)主方向;4、生成特征點(diǎn)描述向量。1.4SURF角點(diǎn)檢測(cè)Part1371、構(gòu)建尺度空間;

SURF使用改進(jìn)的Hessian矩陣來構(gòu)造所有可能的特征點(diǎn)，定義如下：

1.4SURF角點(diǎn)檢測(cè)Part138判別式為：

1.4SURF角點(diǎn)檢測(cè)Part1392、定位特征點(diǎn);

先將Hessian矩陣變換過的像素點(diǎn)與其尺度空間鄰域范圍的點(diǎn)比較，比較方式與SIFT算法相同。初步定位極值為特征點(diǎn)，隨后將亮度比較低以及邊界上的等一些錯(cuò)誤的點(diǎn)進(jìn)行剔除，得到特征點(diǎn)的精確定位。1.4SURF角點(diǎn)檢測(cè)Part1403、選取特征點(diǎn)主方向;

在以特征點(diǎn)為中心的一個(gè)圓形范圍內(nèi)，把一定角度內(nèi)存在的像素點(diǎn)的上下左右四個(gè)方向的離散小波特征之和賦予對(duì)應(yīng)的區(qū)域。之后旋轉(zhuǎn)賦值，找到值最大的扇形，將其方向設(shè)為主方向。1.4SURF角點(diǎn)檢測(cè)Part1414、生成特征點(diǎn)描述向量;

在特征點(diǎn)的附近選取4×4大小的矩形部分。每個(gè)矩形內(nèi)選擇25個(gè)像素點(diǎn)，利用小波變換計(jì)算4個(gè)特征，即可以用4×4×4=64維的向量描述一個(gè)像素點(diǎn)。1.5ORB角點(diǎn)檢測(cè)Part142SURF檢測(cè)速度相對(duì)于SIFT雖然有明顯改進(jìn)，但在沒有GPU的環(huán)境中很難保證實(shí)時(shí)性，而ORB（OrientedFASTandRotatedBRIEF）特征檢測(cè)則可以大大提高特征點(diǎn)檢測(cè)的速度，同時(shí)還保持了特征旋轉(zhuǎn)和尺度的不變性。ORB檢測(cè)算法由FAST特征檢測(cè)算法和BRIEF向量創(chuàng)建算法兩部分組成。1.5ORB角點(diǎn)檢測(cè)Part1431、

FAST特征檢測(cè)算法

FAST特征檢測(cè)步驟：1.5ORB角點(diǎn)檢測(cè)Part144

1.5ORB角點(diǎn)檢測(cè)Part145④循環(huán)上述操作，對(duì)每個(gè)像素執(zhí)行相同的操作。1.5ORB角點(diǎn)檢測(cè)Part146

1.5ORB角點(diǎn)檢測(cè)Part147因?yàn)镕AST特征點(diǎn)只需要比較像素間亮度的差異，所以運(yùn)算速度非?？欤撬泊嬖谝恍﹩栴}，因此ORB特征檢測(cè)算法中對(duì)其不足之處加以如下改進(jìn)：①FAST特征點(diǎn)數(shù)量大且不確定，而算法要求對(duì)圖像提取固定數(shù)量的特征。因此，可以預(yù)先設(shè)定好要提取的角點(diǎn)數(shù)量N，對(duì)原始的FAST角點(diǎn)分別計(jì)算Harries響應(yīng)值，只選取前N個(gè)具有最大響應(yīng)值的角點(diǎn)。1.5ORB角點(diǎn)檢測(cè)Part148②FAST角點(diǎn)計(jì)算時(shí)固定選取半徑為3的圓窗口，不具備尺度不變性。為滿足特征點(diǎn)尺度不變性的要求，首先構(gòu)建圖像金字塔，然后在金字塔的每層進(jìn)行角點(diǎn)檢測(cè)，最終選取在所有尺度圖像上提取的角點(diǎn)。

③FAST角點(diǎn)不具備方向性。ORB算法利用灰度質(zhì)心法來解決這個(gè)問題，具體方法是分別計(jì)算區(qū)域圖像中灰度值作為權(quán)重在x軸與y軸上的質(zhì)心，并通過這兩個(gè)質(zhì)心長度的比值確定方向。1.5ORB角點(diǎn)檢測(cè)Part1492、BRIEF向量創(chuàng)建算法

BRIEF是一種二進(jìn)制編碼描述子，描述向量由0和1組成。這里0和1的確定是通過比較關(guān)鍵點(diǎn)附近兩個(gè)像素灰度值的大小關(guān)系進(jìn)行的。BRIEF描述子的優(yōu)點(diǎn)在于速度快，但缺點(diǎn)是不具備尺度不變性與旋轉(zhuǎn)不變性，且對(duì)噪聲比較敏感，因此ORB算法同樣對(duì)其進(jìn)行了一些。1.5ORB角點(diǎn)檢測(cè)Part150具體改進(jìn)方法：

①解決旋轉(zhuǎn)不變性問題：在使用灰度質(zhì)心法計(jì)算出FAST關(guān)鍵點(diǎn)的方向后，依據(jù)這個(gè)方向旋轉(zhuǎn)啟發(fā)式搜索得到的256對(duì)匹配點(diǎn)對(duì)，獲得描述子的旋轉(zhuǎn)不變性。②解決尺度不變性問題：在關(guān)鍵點(diǎn)所在的圖像金字塔上進(jìn)行描述子的計(jì)算。③解決噪聲敏感問題：在ORB的方案中，不再使用像素對(duì)，代之使用9×9的圖像塊，通過塊中像素值之和替代原有單一像素值進(jìn)行計(jì)算，改善對(duì)噪聲的敏感性。1.5ORB角點(diǎn)檢測(cè)Part151ORB角點(diǎn)檢測(cè)示例：原圖ORB角點(diǎn)檢測(cè)后1.6角點(diǎn)檢測(cè)算法比較Part152Harris角點(diǎn)是經(jīng)典角點(diǎn)之一，主要用于檢測(cè)圖像中線段的端點(diǎn)或兩條線段的交點(diǎn)，需要通過閾值比較判斷是不是Harris角點(diǎn)，在實(shí)際項(xiàng)目中判斷閾值應(yīng)根據(jù)實(shí)際情況和工程經(jīng)驗(yàn)給出。SIFT角點(diǎn)檢測(cè)模仿了實(shí)際生活中的物體近大遠(yuǎn)小、近清晰遠(yuǎn)模糊的特點(diǎn)，構(gòu)建了高斯金字塔，并且在光照、噪聲、視角、縮放和旋轉(zhuǎn)等干擾下依然有良好的穩(wěn)定性，但是由于計(jì)算速度慢，無法用于實(shí)時(shí)系統(tǒng)。1.6角點(diǎn)檢測(cè)算法比較Part153SURF角點(diǎn)檢測(cè)的特點(diǎn)是直接使用方框?yàn)V波去逼近高斯差分空間，這種逼近可以借助積分圖像輕松計(jì)算出方框?yàn)V波器的卷積，但是應(yīng)用在沒有GPU的環(huán)境中仍然很難保證算法的實(shí)時(shí)性。ORB角點(diǎn)檢測(cè)以計(jì)算速度快著稱，其核心思想是將圖像中與周圍像素存在明顯差異的像素點(diǎn)作為關(guān)鍵點(diǎn)。特征匹配特征匹配定義特征匹配方法2.1特征匹配定義Part255特征匹配就是在不同的圖像中尋找同一物體的同一特征點(diǎn)。因?yàn)槊總€(gè)特征點(diǎn)都有唯一標(biāo)識(shí)符即描述子，所以特征匹配就是在多個(gè)圖像中尋找具有相似描述子的特征點(diǎn)。根據(jù)描述子特點(diǎn)的不同，可以將相似描述子的尋找方法分為兩類：一類是計(jì)算描述子之間的歐氏距離，如SIFT特征點(diǎn)、SURF特征點(diǎn)等；另一類是計(jì)算描述子之間的漢明距離，如ORB特征點(diǎn)。2.1特征匹配定義Part256特征匹配最簡(jiǎn)單直觀的方法就是暴力匹配法，即計(jì)算某個(gè)特征點(diǎn)描述子與其他所有特征點(diǎn)描述子之間的距離，然后將距離排序，取距離最近的特征點(diǎn)作為匹配點(diǎn)。這種方法簡(jiǎn)單粗暴，匹配結(jié)果也不可避免地會(huì)出現(xiàn)大量的誤匹配，因此該算法需要進(jìn)行改進(jìn)去除誤匹配結(jié)果。常見的改進(jìn)方法有篩選閾值法、交叉匹配法、KNN匹配法、RANSAC匹配法。2.2暴力匹配法Part257

2.3篩選閾值法Part258

2.4交叉匹配法Part259過一次暴力匹配之后，反過來使用被匹配到的特征點(diǎn)進(jìn)行匹配，如果匹配到的仍然是第一次匹配的點(diǎn)的話，那么這次匹配正確；否則其是誤匹配點(diǎn)，可直接去掉。例如，第一次特征點(diǎn)A經(jīng)過暴力匹配匹配到了特征點(diǎn)B；反過來，對(duì)特征點(diǎn)B使用暴力匹配進(jìn)行匹配，如果匹配的結(jié)果是特征點(diǎn)A，那么匹配是正確的，否則匹配錯(cuò)誤。2.5KNN匹配法Part260

2.5KNN匹配法Part261下圖演示了使用暴力匹配和KNN匹配對(duì)兩幅圖像的特征點(diǎn)進(jìn)行匹配得到的結(jié)果，可以看出，KNN匹配效果明顯優(yōu)于暴力匹配。暴力匹配法KNN匹配法2.6RANSAC匹配法Part262RANSAC（RandomSampleConsensus）算法是一類魯棒匹配算法，在特征存在較多誤匹配時(shí)仍能得到較好結(jié)果。RANSAC算法使用觀測(cè)數(shù)據(jù)（往往含有較大的噪聲或無效點(diǎn)），數(shù)據(jù)參數(shù)化模型及參數(shù)估計(jì)方法來計(jì)算最佳匹配結(jié)果，同時(shí)也可完成魯棒參數(shù)估計(jì)。算法通過反復(fù)選擇數(shù)據(jù)中的一組隨機(jī)子集進(jìn)行參數(shù)估計(jì)來實(shí)現(xiàn)目標(biāo)。2.6RANSAC匹配法Part263①選擇數(shù)據(jù)中的一組隨機(jī)子集作為局內(nèi)點(diǎn)，根據(jù)假設(shè)模型進(jìn)行參數(shù)估計(jì)；②用①中得到的參數(shù)化模型測(cè)試其他所有數(shù)據(jù)，如果某個(gè)點(diǎn)適用于估計(jì)的模型，則認(rèn)為它也是局內(nèi)點(diǎn);③如果有足夠多的點(diǎn)被歸類為假設(shè)的局內(nèi)點(diǎn)，估計(jì)的模型就足夠合理，此時(shí)順序執(zhí)行④；否則返回①，隨機(jī)選擇另一組數(shù)據(jù)子集重復(fù)估計(jì)。RANSAC匹配步驟：2.6RANSAC匹配法Part264④用所有假設(shè)的局內(nèi)點(diǎn)重新估計(jì)模型參數(shù)（如使用最小二乘），并作為最終結(jié)果。⑤通過估計(jì)局內(nèi)點(diǎn)與模型的錯(cuò)誤率來評(píng)估模型。RANSAC匹配步驟：上述過程被重復(fù)執(zhí)行固定的次數(shù)，每次產(chǎn)生的模型或因?yàn)榫謨?nèi)點(diǎn)太少而被舍棄，或因?yàn)闈M足估計(jì)要求而被選用。2.6RANSAC匹配法Part2652.6RANSAC匹配法Part266在圖像匹配中，兩幅圖像中的匹配對(duì)應(yīng)點(diǎn)符合單應(yīng)矩陣變換規(guī)律。單應(yīng)性變換可以由4個(gè)對(duì)應(yīng)的特征點(diǎn)得到單應(yīng)矩陣，將第一幅圖像中的特征點(diǎn)根據(jù)單應(yīng)矩陣求取在第二幅圖像中的重投影坐標(biāo)，比較重投影坐標(biāo)與已匹配的特征點(diǎn)坐標(biāo)之間的距離，如果小于一定的閾值，則該點(diǎn)是正確匹配點(diǎn)，否則其是錯(cuò)誤匹配點(diǎn)需被去除。2.6RANSAC匹配法Part267如圖所示，有幾條直線是SIFT匹配算法的誤判，RANSAC有效地將其識(shí)別，并將正確的模型用線框標(biāo)注出來。Hough變換與形狀檢測(cè)Hough變換原理Hough線變換Hough圓變換3.1Hough變換原理Part

369前面已經(jīng)檢測(cè)到圖像中的特征點(diǎn)信息，但是在許多應(yīng)用場(chǎng)合還需要進(jìn)一步檢測(cè)圖像中的形狀信息，常見的是直線和圓。Hough變換于1962年提出，最初的Hough變換被設(shè)計(jì)用來檢測(cè)直線，后經(jīng)過算法改進(jìn)和擴(kuò)充，Hough變換可以檢測(cè)任意形狀的物體，多為圓和橢圓。Hough變換運(yùn)用空間坐標(biāo)變換，將一個(gè)空間中具有相同形狀的曲線或直線映射到另一個(gè)坐標(biāo)空間上形成峰值，從而把檢測(cè)任意形狀的問題轉(zhuǎn)化為統(tǒng)計(jì)峰值的問題。3.2Hough線變換Part

370

3.2Hough線變換Part

371因此，笛卡兒坐標(biāo)系內(nèi)的一個(gè)點(diǎn)對(duì)應(yīng)Hough空間的一條直線。3.2Hough線變換Part

372同理，笛卡兒坐標(biāo)系內(nèi)的一條直線對(duì)應(yīng)于Hough空間的一個(gè)點(diǎn)。