課件：尺度不變特征變換匹配算法.ppt

尺度不變特征變換匹配算法 Scale Invariant Feature Trans （SIFT）,報告人：邵妍,2012年2月29日,Sift算法簡介,,Sift是David Lowe于1999年提出的局部特征描述子，并于2004年進行了更深入的發展和完善。Sift特征匹配算法可以處理兩幅圖像之間發生平移、旋轉、仿射變換情況下的匹配問題，具有很強的匹配能力。 SIFT算法基于圖像特征尺度選擇的思想，建立圖像的多尺度空間，在不同尺度下檢測到同一個特征點，確定特征點位置的同時確定其所在尺度，以達到尺度抗縮放的目的，剔出一些對比度較低的點以及邊緣響應點以后提取每個穩定關鍵點周圍的局部特征，形成局部描述子并將其用在以后的匹配中。,Sift算法簡介,sift算法特點： SIFT特征是圖像的局部特征，其對旋轉、尺度縮放、亮度變化保持不變性，對視角變化、仿射變換、噪聲也保持一定程度的穩定性。 獨特性(Distinctiveness)好，信息量豐富，適用于在海量特征數據庫中進行快速、準確的匹配。 多量性，即使少數的幾個物體也可以產生大量SIFT特征向量。 經過優化的SIFT算法可滿足一定的速度需求。 可擴展性，可以很方便的與其他形式的特征向量進行聯合。,SIFT算法步驟： 1）檢測尺度空間極值點 2）精確定位極值點 3）為每個關鍵點指定方向參數 4）關鍵點描述子的生成,Sift算法簡介,尺度空間的生成,高斯卷積核是實現尺度變換的唯一線性核，于是一幅二維圖像的尺度空間定義為： 其中， 是尺度可變高斯函數，并且有： （x,y)是空間坐標， 是尺度坐標。 的大小決定圖像的平滑程度，大尺度對應圖像的概貌特征，小尺度對應圖像的細節特征。大的 值對應粗糙尺度(低分辨率)，反之，對應精細尺度(高分辨率)。,,,,,為了有效的在尺度空間檢測到穩定的關鍵點，提出了高斯差分尺度空間（DOG scale-space）。利用不同尺度的高斯差分核與圖像卷積生成。,,高斯差分尺度空間,,,極值點檢測,為了尋找尺度空間的極值點，每一個采樣點要和它所有的相鄰點比較，看其是否比它的圖像域和尺度域的相鄰點大或者小。如圖3所示，中間的檢測點和它同尺度的8個相鄰點和上下相鄰尺度對應的9×2個點共26個點比較，以確保在尺度空間和二維圖像空間都檢測到極值點。,,,精確定位極值點,,,通過上步檢測出了每個尺度上的極值點，現在就需要采用擬合三維二次函數求得極值點在原圖像中的位置。并且為了增強特征點匹配時的穩定性和抗噪能力還需要去除低對比度的關鍵點和邊緣響應點(因為DoG算子會產生較強的邊緣響應)等不穩定的點。,精確定位極值點,,,,,,,,定位極值點： 令極值點A對 進行泰勒展開： （1） 其中， 是到點A的偏移量。對（1）式求X的偏導數，并令偏倒為0，得到 （2） 如果 大于0.5，則意味著這個極值點與另一個采樣點離得更近，需采用插值法求得極值點位置的估計值。,,,,,,,精確定位極值點,,去除低對比度的關鍵點： 將上式（2）帶入公式（1）中即可得 通過觀察實驗結果得出， 小于0.03的極值點均將被丟棄。閾值 越小，則會獲得越多的匹配點個數,,,,,,,,,,,,,,精確定位極值點,,,,,,去除邊緣上的極值點： 曲面上每個點都有兩個主方向，并且沿這兩個主方向的法曲率（即兩個主曲率）分別是曲面在該點法曲率的最大值和最小值。在邊緣上的極值點，垂直于邊緣的方向上，法曲率最大，沿邊緣的方向上，法曲率最小。如果極值點分布在邊緣上，該點的法曲率最大值和最小值之比一般情況下要比非邊緣點的比值大。根據這種思想，我們可以設一個比 值的閾值，當比值大于這個閾值就認為極值點在邊緣上。,精確定位極值點,去除邊緣上的極值點： 首先計算待測極值點的Hessian矩陣： 設 是較大的特征值， 是較小的特征值，則由矩陣性質知： 設 ，則可得： 判斷是否是邊緣點只需判斷上式左邊項是否在某個閾值之下即可。實驗表明一般閾值取r=10時。,,,,,,,,,,,,,,關鍵點方向分配,,,SIFT特征實現旋轉不變性的基本思想是采用“相對”的概念。先為關鍵點賦一個方向，定義的關鍵點描述子均是相對于該方向的，因而可以實現匹配時的旋轉無關性。 為實現尺度無關，根據關鍵點所在尺度選擇與該尺度最相近的高斯平滑圖像L。對L上的每個點L（x，y），計算梯度和方向：,,,,,,,,關鍵點方向分配,,,以關鍵點為中心，劃定一個鄰域，利用所有在此區域內的點的梯度形成一個方向直方圖。直方圖的橫坐標是梯度方向，共 36 項，每項代表了 10 度的范圍；縱坐標是梯度大小，對于歸到橫坐標上任一項內所有的點，將其梯度大小相加，其和作為縱坐標。下圖所示：,,,,,,,,,,,,,,,,,,,,,,,,,,2019/8/23,15,可編輯,,,,,,,,關鍵點方向分配,,,從直方圖中選出縱坐標值最大的一項的方向作為該關鍵點的主方向。如果存在其他方向，縱坐標的大小大于主方向縱坐標大小的 80%，也將其作為該關鍵點的方向。特征點有多個方向的情況下，實際上是在此位置上有多個關鍵點，他們的方向不同。,,,描述子生成,,前面已經為關鍵點賦予了圖像位置、尺度以及方向，這一步將根據關鍵點周圍的局部特征計算得出一個特征描述子。 如下圖所示，在關鍵點周圍取一個鄰域，并對其中點的梯度做高斯加權。這個鄰域分為16個子區域，每個子區域取八個方向。,實 驗,,,,實驗一 特征匹配,實驗簡介： 對兩幅商標圖像進行高斯差分金字塔的構建，并提取出關鍵點，最后通過關鍵點特征向量的歐氏距離作為關鍵點的相似性度量對兩幅圖像的關鍵點進行匹配。,,,,,,,,高斯差分金字塔構建結果,實驗一 特征匹配,實驗一 特征匹配,定位特征點,實驗一 特征匹配,關鍵點匹配,圖1：兩幅相似圖像的匹配結果,圖二：兩幅不相似圖像的匹配結果,數據庫： 100幅二值商標圖像，圖像的分辨率為111x111 在100幅圖像中，大致可以分為十種商標，每種商標分別有10幅由旋轉、縮放等處理得到的相似圖像,實驗二 圖像檢索,實驗二 圖像檢索,待檢索圖像：,檢索結果：,實驗二 圖像檢索,待檢索圖像：,檢索結果：,實驗二 圖像檢索,在該試驗中，隨機抽取10幅待檢索圖像進行檢索的查全率為92%，根據實驗結果可以看出sift特征具有很好的旋轉和尺度不變性，但總體來說，還該實驗存在一定的問題： 1.對于那些很簡單的商標圖像檢索不出關鍵點，或只能檢索出很少的關鍵點，這樣就影響了這種圖像的檢索正確率。 2.還存在一定的誤匹配點,實驗,Thanks!,,,,,,,,,,,,,,,,,,,,,,,,,,2019/8/23,29,可編輯,