經典的圖像匹配算法----SIFT

2021-02-13 智能算法


一. SIFT簡介

1.1 算法提出的背景:

成像匹配的核心問題是將同一目標在不同時間、不同解析度、不同光照、不同位姿情況下所成的像相對應。傳統的匹配算法往往是直接提取角點或邊緣,對環境的適應能力較差,急需提出一種魯棒性強、能夠適應不同光照、不同位姿等情況下能夠有效識別目標的方法。1999年British Columbia大學大衛.勞伊( David G.Lowe)教授總結了現有的基於不變量技術的特徵檢測方法,並正式提出了一種基於尺度空間的、對圖像縮放、旋轉甚至仿射變換保持不變性的圖像局部特徵描述算子-SIFT(尺度不變特徵變換),這種算法在2004年被加以完善。

1.2 算法思想:

將一幅圖像映射(變換)為一個局部特徵向量集;特徵向量具有平移、縮放、旋轉不變性,同時對光照變化、仿射及投影變換也有一定不變性。

算法實現步驟簡述:

SIFT算法的實質可以歸為在不同尺度空間上查找特徵點(關鍵點)的問題。

1.3 SIFT算法實現物體識別主要有三大工序:

1、提取關鍵點; 

2、對關鍵點附加詳細的信息(局部特徵)也就是所謂的描述器;

3、通過兩方特徵點(附帶上特徵向量的關鍵點)的兩兩比較找出相互匹配的若干對特徵點,也就建立了景物間的對應關係。

二. SIFT算法實現細節

2.1. 構建尺度空間

尺度空間理論基礎:

這是一個初始化操作,尺度空間理論目的是模擬圖像數據的多尺度特徵。高斯核是唯一可以產生多尺度空間的核,一個圖像的尺度空間, L( x,y,σ) ,定義為原始圖像I(x,y)與一個可變尺度的2維高斯函數G(x,y,σ) 卷積運算。尺度是自然存在的,不是人為創造的!高斯卷積只是表現尺度空間的一種形式…

其中 G(x,y,σ) 是尺度可變高斯函數(x,y)是空間坐標,是尺度坐標。σ大小決定圖像的平滑程度,大尺度對應圖像的概貌特徵,小尺度對應圖像的細節特徵。大的σ值對應粗糙尺度(低解析度),反之,對應精細尺度(高解析度)。為了有效的在尺度空間檢測到穩定的關鍵點,提出了高斯差分尺度空間(DOG scale-space)。利用不同尺度的高斯差分核與圖像卷積生成。

下圖所示不同σ下圖像尺度空間:

關於尺度空間的理解說明:

2kσ中的2是必須的,尺度空間是連續的。在  Lowe的論文中 ,將第0層的初始尺度定為1.6(最模糊),圖片的初始尺度定為0.5(最清晰). 在檢測極值點前對原始圖像的高斯平滑以致圖像丟失高頻信息,所以 Lowe 建議在建立尺度空間前首先對原始圖像長寬擴展一倍,以保留原始圖像信息,增加特徵點數量。尺度越大圖像越模糊。

圖像金字塔的建立:

對於一幅圖像I,建立其在不同尺度(scale)的圖像,也成為子八度(octave),這是為了scale-invariant,也就是在任何尺度都能夠有對應的特徵點,第一個子八度的scale為原圖大小,後面每個octave為上一個octave降採樣的結果,即原圖的1/4(長寬分別減半),構成下一個子八度(高一層金字塔)。

由圖片size決定建幾個塔,每塔幾層圖像(S一般為3-5層)。0塔的第0層是原始圖像(或你double後的圖像),往上每一層是對其下一層進行Laplacian變換(高斯卷積,其中σ值漸大,例如可以是σ, k*σ, k*k*σ…),直觀上看來越往上圖片越模糊。塔間的圖片是降採樣關係,例如1塔的第0層可以由0塔的第3層down sample得到,然後進行與0塔類似的高斯卷積操作。

2.2. 關鍵點檢測

為了尋找尺度空間的極值點,每一個採樣點要和它所有的相鄰點比較,看其是否比它的圖像域和尺度域的相鄰點大或者小。如圖所示,中間的檢測點和它同尺度的8個相鄰點和上下相鄰尺度對應的9×2個點共26個點比較,以確保在尺度空間和二維圖像空間都檢測到極值點。 一個點如果在DOG尺度空間本層以及上下兩層的26個領域中是最大或最小值時,就認為該點是圖像在該尺度下的一個特徵點,如圖所示。

同一組中的相鄰尺度(由於k的取值關係,肯定是上下層)之間進行尋找,在極值比較的過程中,每一組圖像的首末兩層是無法進行極值比較的,為了滿足尺度變化的連續性,我們在每一組圖像的頂層繼續用高斯模糊生成了3幅圖像,高斯金字塔有每組S+3層圖像。 DOG金字塔每組有S+2層圖像。下圖中s=3

這裡解釋下尺度變化的連續性:

假設s=3,也就是每個塔裡有3層,則k=21/s=21/3,那麼按照上圖可得Gauss Space和DoG space 分別有3個(s個)和2個(s-1個)分量,在DoG space中,1st-octave兩項分別是σ,kσ; 2nd-octave兩項分別是2σ,2kσ;由於無法比較極值,我們必須在高斯空間繼續添加高斯模糊項,使得形成σ,kσ,k2σ,k3σ,k4σ這樣就可以選擇DoG space中的中間三項kσ,k2σ,k3σ(只有左右都有才能有極值),那麼下一octave中(由上一層降採樣獲得)所得三項即為2kσ,2k2σ,2k3σ,其首項2kσ=24/3。剛好與上一octave末項k3σ=23/3尺度變化連續起來,所以每次要在Gaussian space添加3項,每組(塔)共S+3層圖像,相應的DoG金字塔有S+2層圖像。

2.3. 消除錯配點

由於DoG值對噪聲和邊緣較敏感,因此,在上面DoG尺度空間中檢測到局部極值點還要經過進一步的檢驗才能精確定位為特徵點。為了提高關鍵點的穩定性,需要對尺度空間DoG函數進行曲線擬合。利用DoG函數在尺度空間的Taylor展開式:

對上式求導,並令其為0,得到精確的位置, 得

在已經檢測到的特徵點中,要去掉低對比度的特徵點和不穩定的邊緣響應點。去除低對比度的點:把上式代入其中,即在DoG Space的極值點處D(x)取值,只取前兩項可得:

若  ,該特徵點就保留下來,否則丟棄。

邊緣響應的去除

一個定義不好的高斯差分算子的極值在橫跨邊緣的地方有較大的主曲率,而在垂直邊緣的方向有較小的主曲率。主曲率通過一個2×2 的Hessian矩陣H求出:

導數由採樣點相鄰差估計得到。D的主曲率和H的特徵值成正比,令α為較大特徵值,β為較小的特徵值,則

令α=γβ,則

(r + 1)2/r的值在兩個特徵值相等的時候最小,隨著r的增大而增大,因此,為了檢測主曲率是否在某域值r下,只需檢測

if (α+β)/ αβ> (r+1)2/r, throw it out.   在Lowe的文章中,取r=10。

2.4. 關鍵點描述

上一步中確定了每幅圖中的特徵點,為每個特徵點計算一個方向,依照這個方向做進一步的計算, 利用關鍵點鄰域像素的梯度方向分布特性為每個關鍵點指定方向參數,使算子具備旋轉不變性。

為(x,y)處梯度的模值和方向公式。其中L所用的尺度為每個關鍵點各自所在的尺度。至此,圖像的關鍵點已經檢測完畢,每個關鍵點有三個信息:位置,所處尺度、方向,由此可以確定一個SIFT特徵區域。

梯度直方圖的範圍是0~360度,其中每10度一個柱,總共36個柱。隨著距中心點越遠的領域其對直方圖的貢獻也響應減小.Lowe論文中還提到要使用高斯函數對直方圖進行平滑,減少突變的影響。

在實際計算時,我們在以關鍵點為中心的鄰域窗口內採樣,並用直方圖統計鄰域像素的梯度方向。梯度直方圖的範圍是0~360度,其中每45度一個柱,總共8個柱, 或者每10度一個柱,總共36個柱。Lowe論文中還提到要使用高斯函數對直方圖進行平滑,減少突變的影響。直方圖的峰值則代表了該關鍵點處鄰域梯度的主方向,即作為該關鍵點的方向。

直方圖中的峰值就是主方向,其他的達到最大值80%的方向可作為輔助方向,通過對關鍵點周圍圖像區域分塊,計算塊內梯度直方圖,生成具有獨特性的向量,這個向量是該區域圖像信息的一種抽象,具有唯一性。首先將坐標軸旋轉為關鍵點的方向,以確保旋轉不變性。以關鍵點為中心取8×8的窗口。

16*16的圖中其中1/4的特徵點梯度方向及scale,右圖為其加權到8個主方向後的效果。圖左部分的中央為當前關鍵點的位置,每個小格代表關鍵點鄰域所在尺度空間的一個像素,利用公式求得每個像素的梯度幅值與梯度方向,箭頭方向代表該像素的梯度方向,箭頭長度代表梯度模值,然後用高斯窗口對其進行加權運算。

圖中藍色的圈代表高斯加權的範圍(越靠近關鍵點的像素梯度方向信息貢獻越大)。然後在每4×4的小塊上計算8個方向的梯度方向直方圖,繪製每個梯度方向的累加值,即可形成一個種子點,如圖右部分示。此圖中一個關鍵點由2×2共4個種子點組成,每個種子點有8個方向向量信息。這種鄰域方向性信息聯合的思想增強了算法抗噪聲的能力,同時對於含有定位誤差的特徵匹配也提供了較好的容錯性。

計算keypoint周圍的16*16的window中每一個像素的梯度,而且使用高斯下降函數降低遠離中心的權重。

在每個4*4的1/16象限中,通過加權梯度值加到直方圖8個方向區間中的一個,計算出一個梯度方向直方圖。這樣就可以對每個feature形成一個4*4*8=128維的描述子,每一維都可以表示4*4個格子中一個的scale/orientation. 將這個向量歸一化之後,就進一步去除了光照的影響。

2.5. 關鍵點匹配

生成了A、B兩幅圖的描述子,(分別是k1*128維和k2*128維),就將兩圖中各個scale(所有scale)的描述子進行匹配,匹配上128維即可表示兩個特徵點match上了。

實際計算過程中,為了增強匹配的穩健性,Lowe建議對每個關鍵點使用4×4共16個種子點來描述,這樣對於一個關鍵點就可以產生128個數據,即最終形成128維的SIFT特徵向量。此時SIFT特徵向量已經去除了尺度變化、旋轉等幾何變形因素的影響,再繼續將特徵向量的長度歸一化,則可以進一步去除光照變化的影響。 當兩幅圖像的SIFT特徵向量生成後,下一步我們採用關鍵點特徵向量的歐式距離來作為兩幅圖像中關鍵點的相似性判定度量。取圖像1中的某個關鍵點,並找出其與圖像2中歐式距離最近的前兩個關鍵點,在這兩個關鍵點中,如果最近的距離除以次近的距離少於某個比例閾值,則接受這一對匹配點。降低這個比例閾值,SIFT匹配點數目會減少,但更加穩定。

為了排除因為圖像遮擋和背景混亂而產生的無匹配關係的關鍵點,Lowe提出了比較最近鄰距離與次近鄰距離的方法,距離比率ratio小於某個閾值的認為是正確匹配。因為對於錯誤匹配,由於特徵空間的高維性,相似的距離可能有大量其他的錯誤匹配,從而它的ratio值比較高。Lowe推薦ratio的閾值為0.8。但作者對大量任意存在尺度、旋轉和亮度變化的兩幅圖片進行匹配,結果表明ratio取值在0. 4~0. 6之間最佳,小於0. 4的很少有匹配點,大於0. 6的則存在大量錯誤匹配點。(如果這個地方你要改進,最好給出一個匹配率和ration之間的關係圖,這樣才有說服力)作者建議ratio的取值原則如下:

ratio=0. 4 對於準確度要求高的匹配;

ratio=0. 6 對於匹配點數目要求比較多的匹配;

ratio=0. 5 一般情況下。

也可按如下原則:當最近鄰距離<200時ratio=0. 6,反之ratio=0. 4。ratio的取值策略能排分錯誤匹配點。

當兩幅圖像的SIFT特徵向量生成後,下一步我們採用關鍵點特徵向量的歐式距離來作為兩幅圖像中關鍵點的相似性判定度量。取圖像1中的某個關鍵點,並找出其與圖像2中歐式距離最近的前兩個關鍵點,在這兩個關鍵點中,如果最近的距離除以次近的距離少於某個比例閾值,則接受這一對匹配點。降低這個比例閾值,SIFT匹配點數目會減少,但更加穩定。

參考文獻:http://blog.csdn.net/abcjennifer/article/details/7639681

免責聲明:本文系網絡轉載。版權歸原作者所有。如涉及版權,請聯繫刪除!

相關焦點

  • 3分鐘教會你選擇合適的圖像識別算法
    :上圖我們截取了執行touch語句的部分日誌(截圖不存在於當前設備畫面中),可以看到,在識別圖像的過程中,Airtest嘗試用了SURFMatching、TemplateMatching和BRISKMatching這幾個算法去查找,並且還分別告訴了我們這幾個算法的執行結果是什麼。
  • OpenCV-Python SIFT尺度不變特徵變換|三十九
    因此,在2004年,不列顛哥倫比亞大學的D.Lowe在他的論文《尺度不變關鍵點中的獨特圖像特徵》中提出了一種新算法,即尺度不變特徵變換(SIFT),該算法提取關鍵點並計算其描述算符。 (改論文易於理解,被認為是學習SIFT的最佳材料。因此,本文只是該論文的簡短摘要)。 SIFT算法主要包括四個步驟。
  • 你真的理解圖像處理算法SIFT嗎?
    上面已經提到過2004年的這篇論文是非常經典的一篇論文,尤其是在圖像識別領域,即使是在以深度學習為主流研究方向的現在,SIFT算法仍然具有其優勢,在一些相關領域仍然被廣泛使用,研究人員對SIFT算法的改進依舊如火如荼,截止目前為止,Distinctive Image Features from Scale-Invariant Keypoints已經被引用26,427次,如此多的引用率足以表明該篇論文的重要程度
  • OpenCV-Python 特徵匹配|四十四
    目標在本章中,我們將看到如何將一個圖像中的特徵與其他圖像進行匹配。我們將在OpenCV中使用Brute-Force匹配器和FLANN匹配器Brute-Force匹配器的基礎蠻力匹配器很簡單。它使用第一組中一個特徵的描述符,並使用一些距離計算將其與第二組中的所有其他特徵匹配。並返回最接近的一個。
  • 圖像匹配幾種常見算法與實踐
    2.特徵匹配3.深度學習去找目標圖像匹配是指通過一定的匹配算法在兩幅或多幅圖像之間識別同名點。應用:遙感(製圖更新),計算機視覺應用程式,醫療用圖像註冊。圖像匹配主要可分為以灰度為基礎的匹配和以特徵為基礎的匹配。模板匹配是基於像素的匹配,用來在一副大圖中搜尋查找模版圖像位置的方法。和 2D 卷積一樣,它也是用模板圖像在輸入圖像(大圖)上滑動,並在每一個位置對模板圖像和與其對應的輸入圖像的子區域進行比較。OpenCV 提供了幾種不同的比較方法。
  • Python實現圖像的全景拼接
    其中用到了計算機視覺和圖像處理技術有:關鍵點特徵檢測、局部不變特徵、關鍵特徵點匹配、RANSAC(Random Sample Consensus,隨機採樣一致性)和透視變形。import cv2 as cv # 導入opencv包import numpy as np # 導入numpy包,圖像處理中的矩陣運算需要用到# 檢測圖像的SIFT關鍵特徵點def sift_keypoints_detect(image): # 處理圖像一般很少用到彩色信息,通常直接將圖像轉換為灰度圖 gray_image
  • 圖像處理十大經典算法
    圖像處理,是對圖像進行分析、加工、和處理,使其滿足視覺、心理以及其他要求的技術。
  • 圖像配準:從SIFT到深度學習
    這些方法有三個步驟:關鍵點檢測和特徵描述,特徵匹配,圖像變換。簡單的說,我們選擇兩個圖像中的感興趣點,將參考圖像(reference image)與感測圖像(sensed image)中的等價感興趣點進行關聯,然後變換感測圖像使兩個圖像對齊。
  • OpenCV-Python 特徵匹配 + 單應性查找對象|四十五
    我們使用了queryImage,找到了其中的一些特徵點,我們使用了另一個trainImage,也找到了該圖像中的特徵,並且找到了其中的最佳匹配。簡而言之,我們在另一個混亂的圖像中找到了對象某些部分的位置。此信息足以在trainImage上準確找到對象。
  • 你真的理解圖像處理經典算法 SIFT 嗎?最深入、最全面綜述:尺度不變特徵轉換
    上面已經提到過2004年的這篇論文是非常經典的一篇論文,尤其是在圖像識別領域,即使是在以深度學習為主流研究方向的現在,SIFT算法仍然具有其優勢,在一些相關領域仍然被廣泛使用,研究人員對SIFT算法的改進依舊如火如荼,截止目前為止,Distinctive Image Features from Scale-Invariant Keypoints
  • 圖像特徵點|SIFT特徵點之圖像金字塔
    ,但SIFT除了計算比較耗時以外,其他方面的優點讓其成為特徵點提取算法中的一顆璀璨的明珠。SIFT算法的介紹網上有很多比較好的博客和文章,我在學習這個算法的過程中也參看網上好些資料,即使評價比較高的文章,作者在文章中對有些比較重要的細節、公式來歷沒有提及,可能寫博客的人自己明白,也覺得簡單,因此就忽略了這些問題,但是對剛入門的人來說,看這些東西,想搞清楚這些是怎麼來的還是比較費時費力的。比如SIFT算法中一個重要的操作:求取描述子的主方向。
  • 一種改進的高精度視頻幀間匹配算法
    特徵法[1]是圖像匹配算法中的一種經典方法,其原理是選取圖像中的典型特徵作為運動估計的基本單元,這種方法比較接近於人的視覺特性,主要受制於特徵提取的穩定性和特徵定位的精確性。而SIFT (scale in-variant feature transform)特徵[2,3]是一種對尺度、旋轉、亮度、仿射、噪音等都具有不變性的圖像局部特徵。
  • 將門好聲音 | BMVC 2019:系統性評估特徵匹配相關算法
    實驗結果揭示了最新算法與經典算法在多個層面上的性能對比。然後根據實驗結果設計出幾個高性能的匹配系統,這些新提出的方法在公開數據集上遠超傳統算法。邊佳旺,阿德萊德大學博士生在讀。導師為Ian Reid和沈春華教授。研究方向包括圖像匹配,深度學習,以及Visual SLAM。
  • 詳解計算機視覺中的特徵點檢測:Harris / SIFT / SURF / ORB
    ,該像素置0Moravec角點檢測的缺點只在四個方向上計算灰度值變化,導致角點響應函數在多處都有較大響應對於每個點只考慮E的最小值,導致算法對邊緣有很強的反應1988年,Harris和Plessey對Moravec的方法進行了改進,提出了經典的Harris角點檢測算法。
  • 圖像處理基本思想和算法研究
    圖像處理基本思想和算法研究 剛開始想把這部分內容命名為「基本算法」,意在介紹圖像處理中的一些基本算法,後來仔細想想決定不這麼寫,因為圖像處理是一個非常大的概念,圖像處理不等於人臉識別,也不等於模式識別,直接介紹諸如圖像處理基本算法之類的內容很容易寫成空話,沒有什麼實際意義。
  • 特徵點匹配
    如何從圖像中提取特徵點「 此篇介紹圖像的特徵點匹配算法,包括ORB特徵點算法介紹、特徵點匹配以及RANSAC優化
  • 基於深度學習算法和傳統立體匹配算法的雙目立體視覺
    比較關鍵的技術有相機標定技術、圖像立體匹配以及空間點的三維坐標計算三項。    左右視圖即來自於左右眼睛或攝像頭的圖像,我們網路的訓練用到的左右視圖是來自Middlebury資料庫中供立體匹配算法研究的一組參考圖像。
  • MATLAB比較圖像的相似度-圖像搜索算法
    關注我們獲得更多精彩內容一、圖像相似度計算相關原理通過圖片進行搜索相似圖標的算法實現是:利用感知「感知哈希算法」,就是每一張圖片都按照某種桂林生成唯一的「標識」,通過對「標識」進 比較,那麼可以判斷兩張照片是相似以及相似程度。
  • 經典工具 | 使用SIFT預測錯義突變的有害性
    SIFT就是這樣一個應用於基因組學研究的經典工具。   SIFT可預測多種生物體的基因組變異,主要是錯義突變的影響與效應,最大的特點是物種豐富,是一個經典的、普適性的研究工具。https://sift.bii.a-star.edu.sg/sift4g/   需要查看自己研究的生物體是否具有SIFT資料庫,再注釋變異文件 (VCF)。
  • 巧解圖像處理經典難題之圖像配準
    相近領域:圖像融合,圖像拼接,圖像分割,超解析度,圖配準,點雲配準,SLAM使用方法:相似性測度,配準精度,配準算法,小波變換,互信息,仿射變換,特徵提取,特徵點匹配,相位相關根據算法本質的分類圖像配準最本質的分類是:1.基於灰度的圖像配準;2.基於特徵的圖像配準。具體的圖像配準算法是基於這兩點的混合或者變體的算法。