教育行業(yè)A股IPO第一股(股票代碼 003032)

全國咨詢/投訴熱線:400-618-4000

計(jì)算機(jī)視覺的算法SIFT算法詳細(xì)介紹

更新時(shí)間:2021年06月03日18時(shí)27分 來源:傳智教育 瀏覽次數(shù):

前面我們介紹了Harris和Shi-Tomasi角點(diǎn)檢測算法,這兩種算法具有旋轉(zhuǎn)不變性,但不具有尺度不變性,以下圖為例,在左側(cè)小圖中可以檢測到角點(diǎn),但是圖像被放大后,在使用同樣的窗口,就檢測不到角點(diǎn)了。

SIFT算法01

所以,下面我們來介紹一種計(jì)算機(jī)視覺的算法,尺度不變特征轉(zhuǎn)換即SIFT (Scale-invariant feature transform)。它用來偵測與描述影像中的局部性特征,它在空間尺度中尋找極值點(diǎn),并提取出其位置、尺度、旋轉(zhuǎn)不變量,此算法由 David Lowe在1999年所發(fā)表,2004年完善總結(jié)。應(yīng)用范圍包含物體辨識、機(jī)器人地圖感知與導(dǎo)航、影像縫合、3D模型建立、手勢辨識、影像追蹤和動(dòng)作比對等領(lǐng)域。

SIFT算法的實(shí)質(zhì)是在不同的尺度空間上查找關(guān)鍵點(diǎn)(特征點(diǎn)),并計(jì)算出關(guān)鍵點(diǎn)的方向。SIFT所查找到的關(guān)鍵點(diǎn)是一些十分突出,不會(huì)因光照,仿射變換和噪音等因素而變化的點(diǎn),如角點(diǎn)、邊緣點(diǎn)、暗區(qū)的亮點(diǎn)及亮區(qū)的暗點(diǎn)等。

1.1 基本流程

Lowe將SIFT算法分解為如下四步

  1. 尺度空間極值檢測:搜索所有尺度上的圖像位置。通過高斯差分函數(shù)來識別潛在的對于尺度和旋轉(zhuǎn)不變的關(guān)鍵點(diǎn)。
  2. 關(guān)鍵點(diǎn)定位:在每個(gè)候選的位置上,通過一個(gè)擬合精細(xì)的模型來確定位置和尺度。關(guān)鍵點(diǎn)的選擇依據(jù)于它們的穩(wěn)定程度。
  3. 關(guān)鍵點(diǎn)方向確定:基于圖像局部的梯度方向,分配給每個(gè)關(guān)鍵點(diǎn)位置一個(gè)或多個(gè)方向。所有后面的對圖像數(shù)據(jù)的操作都相對于關(guān)鍵點(diǎn)的方向、尺度和位置進(jìn)行變換,從而保證了對于這些變換的不變性。
  4. 關(guān)鍵點(diǎn)描述:在每個(gè)關(guān)鍵點(diǎn)周圍的鄰域內(nèi),在選定的尺度上測量圖像局部的梯度。這些梯度作為關(guān)鍵點(diǎn)的描述符,它允許比較大的局部形狀的變形或光照變化。

我們就沿著Lowe的步驟,對SIFT算法的實(shí)現(xiàn)過程進(jìn)行介紹:

1.2 尺度空間極值檢測

在不同的尺度空間是不能使用相同的窗口檢測極值點(diǎn),對小的關(guān)鍵點(diǎn)使用小的窗口,對大的關(guān)鍵點(diǎn)使用大的窗口,為了達(dá)到上述目的,我們使用尺度空間濾波器。

高斯核是唯一可以產(chǎn)生多尺度空間的核函數(shù)。-《Scale-space theory: A basic tool for analysing structures at different scales》。

一個(gè)圖像的尺度空間L(x,y,σ),定義為原始圖像I(x,y)與一個(gè)可變尺度的2維高斯函數(shù)G(x,y,σ)卷積運(yùn)算 ,即:

L(x,y,σ)=G(x,y,σ)I(x,y) L(x,y,\sigma) = G(x,y,\sigma)* I(x,y) 其中: G(x,y,σ)=12πσ2ex2+y22σ2 G(x,y,\sigma)=\frac{1}{2\pi\sigma^2}e^{-\frac{x^2+y^2}{2\sigma^2}} σ\sigma是尺度空間因子,它決定了圖像的模糊的程度。在大尺度下(σ\sigma值大)表現(xiàn)的是圖像的概貌信息,在小尺度下(σ\sigma值?。┍憩F(xiàn)的是圖像的細(xì)節(jié)信息。

在計(jì)算高斯函數(shù)的離散近似時(shí),在大概3σ距離之外的像素都可以看作不起作用,這些像素的計(jì)算也就可以忽略。所以,在實(shí)際應(yīng)用中,只計(jì)算(6σ+1)*(6σ+1)的高斯卷積核就可以保證相關(guān)像素影響。
下面我們構(gòu)建圖像的高斯金字塔,它采用高斯函數(shù)對圖像進(jìn)行模糊以及降采樣處理得到的,高斯金字塔構(gòu)建過程中,首先將圖像擴(kuò)大一倍,在擴(kuò)大的圖像的基礎(chǔ)之上構(gòu)建高斯金字塔,然后對該尺寸下圖像進(jìn)行高斯模糊,幾幅模糊之后的圖像集合構(gòu)成了一個(gè)Octave,然后對該Octave下選擇一幅圖像進(jìn)行下采樣,長和寬分別縮短一倍,圖像面積變?yōu)樵瓉硭姆种?。這幅圖像就是下一個(gè)Octave的初始圖像,在初始圖像的基礎(chǔ)上完成屬于這個(gè)Octave的高斯模糊處理,以此類推完成整個(gè)算法所需要的所有八度構(gòu)建,這樣這個(gè)高斯金字塔就構(gòu)建出來了,整個(gè)流程如下圖所示:

SIFT原理02

利用LoG(高斯拉普拉斯方法),即圖像的二階導(dǎo)數(shù),可以在不同的尺度下檢測圖像的關(guān)鍵點(diǎn)信息,從而確定圖像的特征點(diǎn)。但LoG的計(jì)算量大,效率低。所以我們通過兩個(gè)相鄰高斯尺度空間的圖像的相減,得到DoG(高斯差分)來近似LoG。
為了計(jì)算DoG我們構(gòu)建高斯差分金字塔,該金字塔是在上述的高斯金字塔的基礎(chǔ)上構(gòu)建而成的,建立過程是:在高斯金字塔中每個(gè)Octave中相鄰兩層相減就構(gòu)成了高斯差分金字塔。如下圖所示:

SIFT算法03

高斯差分金字塔的第1組第1層是由高斯金字塔的第1組第2層減第1組第1層得到的。以此類推,逐組逐層生成每一個(gè)差分圖像,所有差分圖像構(gòu)成差分金字塔。概括為DOG金字塔的第o組第l層圖像是有高斯金字塔的第o組第l+1層減第o組第l層得到的。后續(xù)Sift特征點(diǎn)的提取都是在DOG金字塔上進(jìn)行的
在 DoG 搞定之后,就可以在不同的尺度空間中搜索局部最大值了。對于圖像中的一個(gè)像素點(diǎn)而言,它需要與自己周圍的 8 鄰域,以及尺度空間中上下兩層中的相鄰的 18(2x9)個(gè)點(diǎn)相比。如果是局部最大值,它就可能是一個(gè)關(guān)鍵點(diǎn)?;旧蟻碚f關(guān)鍵點(diǎn)是圖像在相應(yīng)尺度空間中的最好代表。如下圖所示:

SIFT算法03

搜索過程從每組的第二層開始,以第二層為當(dāng)前層,對第二層的DoG圖像中的每個(gè)點(diǎn)取一個(gè)3×3的立方體,立方體上下層為第一層與第三層。這樣,搜索得到的極值點(diǎn)既有位置坐標(biāo)(DoG的圖像坐標(biāo)),又有空間尺度坐標(biāo)(層坐標(biāo))。當(dāng)?shù)诙铀阉魍瓿珊螅僖缘谌龑幼鳛楫?dāng)前層,其過程與第二層的搜索類似。當(dāng)S=3時(shí),每組里面要搜索3層,所以在DOG中就有S+2層,在初使構(gòu)建的金字塔中每組有S+3層。

1.3 關(guān)鍵點(diǎn)定位

由于DoG對噪聲和邊緣比較敏感,因此在上面高斯差分金字塔中檢測到的局部極值點(diǎn)需經(jīng)過進(jìn)一步的檢驗(yàn)才能精確定位為特征點(diǎn)。

使用尺度空間的泰勒級數(shù)展開來獲得極值的準(zhǔn)確位置, 如果極值點(diǎn)的 灰度值小于閾值(一般為0.03或0.04)就會(huì)被忽略掉。 在 OpenCV 中這種閾值被稱為 contrastThreshold。

DoG 算法對邊界非常敏感, 所以我們必須要把邊界去除。 Harris 算法除了可以用于角點(diǎn)檢測之外還可以用于檢測邊界。從 Harris 角點(diǎn)檢測的算法中,當(dāng)一個(gè)特征值遠(yuǎn)遠(yuǎn)大于另外一個(gè)特征值時(shí)檢測到的是邊界。那在DoG算法中欠佳的關(guān)鍵點(diǎn)在平行邊緣的方向有較大的主曲率,而在垂直于邊緣的方向有較小的曲率,兩者的比值如果高于某個(gè)閾值(在OpenCV中叫做邊界閾值),就認(rèn)為該關(guān)鍵點(diǎn)為邊界,將被忽略,一般將該閾值設(shè)置為10。

將低對比度和邊界的關(guān)鍵點(diǎn)去除,得到的就是我們感興趣的關(guān)鍵點(diǎn)。

1.4 關(guān)鍵點(diǎn)方向確定

經(jīng)過上述兩個(gè)步驟,圖像的關(guān)鍵點(diǎn)就完全找到了,這些關(guān)鍵點(diǎn)具有尺度不變性。為了實(shí)現(xiàn)旋轉(zhuǎn)不變性,還需要為每個(gè)關(guān)鍵點(diǎn)分配一個(gè)方向角度,也就是根據(jù)檢測到的關(guān)鍵點(diǎn)所在高斯尺度圖像的鄰域結(jié)構(gòu)中求得一個(gè)方向基準(zhǔn)。

對于任一關(guān)鍵點(diǎn),我們采集其所在高斯金字塔圖像以r為半徑的區(qū)域內(nèi)所有像素的梯度特征(幅值和幅角),半徑r為: r=3×1.5σ r = 3\times1.5\sigma 其中σ是關(guān)鍵點(diǎn)所在octave的圖像的尺度,可以得到對應(yīng)的尺度圖像。

梯度的幅值和方向的計(jì)算公式為: m(x,y)=(L(x+1,y)L(x1,y)2+(L(x,y+1)L(x,y1))2 m(x,y)=\sqrt{(L(x+1,y)-L(x-1,y)^2+(L(x,y+1)-L(x,y-1))^2}

θ(x,y)=arctan(L(x,y+1)L(x,y1)L(x+1,y)L(x1),y) \theta(x,y) = arctan(\frac{L(x,y+1)-L(x,y-1)}{L(x+1,y)-L(x-1),y})

鄰域像素梯度的計(jì)算結(jié)果如下圖所示:

SIFT算法05

完成關(guān)鍵點(diǎn)梯度計(jì)算后,使用直方圖統(tǒng)計(jì)關(guān)鍵點(diǎn)鄰域內(nèi)像素的梯度幅值和方向。具體做法是,將360°分為36柱,每10°為一柱,然后在以r為半徑的區(qū)域內(nèi),將梯度方向在某一個(gè)柱內(nèi)的像素找出來,然后將他們的幅值相加在一起作為柱的高度。因?yàn)樵趓為半徑的區(qū)域內(nèi)像素的梯度幅值對中心像素的貢獻(xiàn)是不同的,因此還需要對幅值進(jìn)行加權(quán)處理,采用高斯加權(quán),方差為1.5σ。如下圖所示,為簡化圖中只畫了8個(gè)方向的直方圖。

SIFT算法06

每個(gè)特征點(diǎn)必須分配一個(gè)主方向,還需要一個(gè)或多個(gè)輔方向,增加輔方向的目的是為了增強(qiáng)圖像匹配的魯棒性。輔方向的定義是,當(dāng)一個(gè)柱體的高度大于主方向柱體高度的80%時(shí),則該柱體所代表的的方向就是給特征點(diǎn)的輔方向。
直方圖的峰值,即最高的柱代表的方向是特征點(diǎn)鄰域范圍內(nèi)圖像梯度的主方向,但該柱體代表的角度是一個(gè)范圍,所以我們還要對離散的直方圖進(jìn)行插值擬合,以得到更精確的方向角度值。利用拋物線對離散的直方圖進(jìn)行擬合,如下圖所示:

SIFT算法07

獲得圖像關(guān)鍵點(diǎn)主方向后,每個(gè)關(guān)鍵點(diǎn)有三個(gè)信息(x,y,σ,θ):位置、尺度、方向。由此我們可以確定一個(gè)SIFT特征區(qū)域。通常使用一個(gè)帶箭頭的圓或直接使用箭頭表示SIFT區(qū)域的三個(gè)值:中心表示特征點(diǎn)位置,半徑表示關(guān)鍵點(diǎn)尺度,箭頭表示方向。如下圖所示:

SIFT算法08

1.5 關(guān)鍵點(diǎn)描述

通過以上步驟,每個(gè)關(guān)鍵點(diǎn)就被分配了位置,尺度和方向信息。接下來我們?yōu)槊總€(gè)關(guān)鍵點(diǎn)建立一個(gè)描述符,該描述符既具有可區(qū)分性,又具有對某些變量的不變性,如光照,視角等。而且描述符不僅僅包含關(guān)鍵點(diǎn),也包括關(guān)鍵點(diǎn)周圍對其有貢獻(xiàn)的的像素點(diǎn)。主要思路就是通過將關(guān)鍵點(diǎn)周圍圖像區(qū)域分塊,計(jì)算塊內(nèi)的梯度直方圖,生成具有特征向量,對圖像信息進(jìn)行抽象。

描述符與特征點(diǎn)所在的尺度有關(guān),所以我們在關(guān)鍵點(diǎn)所在的高斯尺度圖像上生成對應(yīng)的描述符。以特征點(diǎn)為中心,將其附近鄰域劃分為ddd*d個(gè)子區(qū)域(一般取d=4),每個(gè)子區(qū)域都是一個(gè)正方形,邊長為3σ,考慮到實(shí)際計(jì)算時(shí),需進(jìn)行三次線性插值,所以特征點(diǎn)鄰域的為3σ(d+1)3σ(d+1)3\sigma(d+1)*3\sigma(d+1)的范圍,如下圖所示:

SIFT算法09

為了保證特征點(diǎn)的旋轉(zhuǎn)不變性,以特征點(diǎn)為中心,將坐標(biāo)軸旋轉(zhuǎn)為關(guān)鍵點(diǎn)的主方向,如下圖所示:

SIFT算法10

計(jì)算子區(qū)域內(nèi)的像素的梯度,并按照σ=0.5d進(jìn)行高斯加權(quán),然后插值計(jì)算得到每個(gè)種子點(diǎn)的八個(gè)方向的梯度,插值方法如下圖所示:

SIFT算法11

每個(gè)種子點(diǎn)的梯度都是由覆蓋其的4個(gè)子區(qū)域插值而得的。如圖中的紅色點(diǎn),落在第0行和第1行之間,對這兩行都有貢獻(xiàn)。對第0行第3列種子點(diǎn)的貢獻(xiàn)因子為dr,對第1行第3列的貢獻(xiàn)因子為1-dr,同理,對鄰近兩列的貢獻(xiàn)因子為dc和1-dc,對鄰近兩個(gè)方向的貢獻(xiàn)因子為do和1-do。則最終累加在每個(gè)方向上的梯度大小為: weight=wdrk(1dr)(1k)dcm(1dc)1mdon(1do)1n weight = w*dr^k(1-dr)^{(1-k)}dc^m(1-dc)^{1-m}do^n(1-do)^{1-n} 其中k,m,n為0或?yàn)?。 如上統(tǒng)計(jì)448=1284*4*8=128個(gè)梯度信息即為該關(guān)鍵點(diǎn)的特征向量,按照特征點(diǎn)的對每個(gè)關(guān)鍵點(diǎn)的特征向量進(jìn)行排序,就得到了SIFT特征描述向量。

1.6 總結(jié)

SIFT在圖像的不變特征提取方面擁有無與倫比的優(yōu)勢,但并不完美,仍然存在實(shí)時(shí)性不高,有時(shí)特征點(diǎn)較少,對邊緣光滑的目標(biāo)無法準(zhǔn)確提取特征點(diǎn)等缺陷,自SIFT算法問世以來,人們就一直對其進(jìn)行優(yōu)化和改進(jìn),其中最著名的就是SURF算法。



猜你喜歡:

人工智能之個(gè)性化推薦之路

深度相機(jī)是什么?深度相機(jī)常見技術(shù)

如何解決分類中解決類別不平衡問題?

語言模型-BERT:bert算法介紹

傳智教育人工智能培訓(xùn)課程

0 分享到:
和我們在線交談!