特征提取與運動估計：5.特征檢測與匹配

Hough變換與形狀檢測特征匹配

角點檢測

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

1.2Harris角點檢測Part17

1.2Harris角點檢測Part18

1.2Harris角點檢測Part19

任何一個函數表達式，均可由泰勒公式進行展開。利用泰勒展開對窗口內的像素變化量進行轉化，對灰度變化部分進行泰勒展開可得：1.2Harris角點檢測Part110

1.2Harris角點檢測Part111

1.2Harris角點檢測Part112

1.2Harris角點檢測Part113

1.2Harris角點檢測Part114Harris角點檢測步驟：

1.2Harris角點檢測Part115Harris角點檢測步驟：

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

2、DoG差分金字塔,對相鄰兩個尺度空間的圖像進行相減;3、極值檢測及特征點篩選，去除低響應特征點和不穩定的特征點;4、確定特征點主方向;5、生成特征點描述向量。Part1191、構建尺度空間

1.3SIFT角點檢測Part1202、DoG差分金字塔

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

①對尺度空間DoG函數曲線擬合以精確確定關鍵點的位置和尺度；1.3SIFT角點檢測Part123

1.3SIFT角點檢測求導并令其為0，得到

②

在已檢測到的特征點中去除低對比度與不穩定的特征點；Part124③

消除邊緣響應：通過利用特征點處的Hessian矩陣；1.3SIFT角點檢測

Part1251.3SIFT角點檢測

Part1264、確定特征點主方向

1.3SIFT角點檢測

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

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

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

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

2、定位特征點3、選取特征點主方向;4、生成特征點描述向量。1.4SURF角點檢測Part1371、構建尺度空間;

SURF使用改進的Hessian矩陣來構造所有可能的特征點，定義如下：

1.4SURF角點檢測Part138判別式為：

1.4SURF角點檢測Part1392、定位特征點;

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

在以特征點為中心的一個圓形范圍內，把一定角度內存在的像素點的上下左右四個方向的離散小波特征之和賦予對應的區域。之后旋轉賦值，找到值最大的扇形，將其方向設為主方向。1.4SURF角點檢測Part1414、生成特征點描述向量;

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

FAST特征檢測算法

FAST特征檢測步驟：1.5ORB角點檢測Part144

1.5ORB角點檢測Part145④循環上述操作，對每個像素執行相同的操作。1.5ORB角點檢測Part146

1.5ORB角點檢測Part147因為FAST特征點只需要比較像素間亮度的差異，所以運算速度非常快，但是它也存在一些問題，因此ORB特征檢測算法中對其不足之處加以如下改進：①FAST特征點數量大且不確定，而算法要求對圖像提取固定數量的特征。因此，可以預先設定好要提取的角點數量N，對原始的FAST角點分別計算Harries響應值，只選取前N個具有最大響應值的角點。1.5ORB角點檢測Part148②FAST角點計算時固定選取半徑為3的圓窗口，不具備尺度不變性。為滿足特征點尺度不變性的要求，首先構建圖像金字塔，然后在金字塔的每層進行角點檢測，最終選取在所有尺度圖像上提取的角點。

③FAST角點不具備方向性。ORB算法利用灰度質心法來解決這個問題，具體方法是分別計算區域圖像中灰度值作為權重在x軸與y軸上的質心，并通過這兩個質心長度的比值確定方向。1.5ORB角點檢測Part1492、BRIEF向量創建算法

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

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

2.3篩選閾值法Part258

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

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

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

370

3.2Hough線變換Part

371因此，笛卡兒坐標系內的一個點對應Hough空間的一條直線。3.2Hough線變換Part

372同理，笛卡兒坐標系內的一條直線對應于Hough空間的一個點。