計(jì)算機(jī)視覺(jué)之一：特征檢測(cè)

計(jì)算機(jī)視覺(jué)之一：特征檢測(cè)

主要內(nèi)容：

1、一個(gè)例子解釋為什么要進(jìn)行特征檢測(cè)

2、圖像特征

3、點(diǎn)特征檢測(cè)：Harris角點(diǎn)、MOPS、SIFT

4、邊緣檢測(cè)：一階微分算子、二階微分算子、Canny算子

一、為什么要檢測(cè)特征？

舉一個(gè)例子：全景圖像拼接，給定兩張圖像，如何拼接成一張大圖？

步驟一：檢測(cè)特征點(diǎn)

步驟二：匹配特征點(diǎn)

步驟三：圖像適配

二、圖像的特征有哪些？

計(jì)算機(jī)視覺(jué)中常用的圖像特征包括：點(diǎn)、邊緣、直線、曲線等

三、點(diǎn)特征檢測(cè)

1、點(diǎn)特征的優(yōu)勢(shì)：

點(diǎn)特征屬于局部特征，對(duì)遮擋有一定魯棒性；

通常圖像中可以檢測(cè)到成百上千的點(diǎn)特征，以量取勝；

點(diǎn)特征有較好的辨識(shí)性，不同物體上的點(diǎn)容易區(qū)分；

點(diǎn)特征提取通常速度很快；

2、什么是好的點(diǎn)特征？

考慮圖像上的一個(gè)小窗口，當(dāng)窗口位置發(fā)生微小變化時(shí)，窗口圖像如何變化？

很明顯，從下圖可以看出，角點(diǎn)是一個(gè)好的點(diǎn)特征，因?yàn)樗厝我夥较蛞苿?dòng)，窗口的灰度變化明顯，所以它可以作為一個(gè)特征來(lái)進(jìn)行區(qū)分和辨別。

3、點(diǎn)特征的數(shù)學(xué)表達(dá)

• 假設(shè)窗口W發(fā)生位置偏移(u,v);
• 比較偏移前后窗口中每一個(gè)像素點(diǎn)的灰度變化值；
• 使用誤差平方和定義誤差函數(shù)E(u,v)

       不同位置點(diǎn)計(jì)算得到的E(u,v)如下圖所示，E(u,v)值隨著u、v變化的效果圖，可以看出，平坦區(qū)域（如天空）的灰度變化不大（下圖3），邊緣區(qū)域沿著邊緣方向的灰度變化.

也很小（下圖2），只有角點(diǎn)處的灰度變化稍微劇烈一點(diǎn)（下圖1）

　　誤差函數(shù)E(u,v)：

將I(u,v)進(jìn)行Taylor展開(kāi)：

進(jìn)一步展開(kāi)，寫(xiě)成：

H稱為自相關(guān)矩陣，和是H的2個(gè)特征值，E(u,v)的變化如下圖所示：

根據(jù)H的2個(gè)特征值大小對(duì)圖像點(diǎn)進(jìn)行分類(lèi)：

角點(diǎn)應(yīng)該滿足的基本性質(zhì)：最小特征值盡量大

角點(diǎn)響應(yīng)：

比更有效的角點(diǎn)響應(yīng)函數(shù)：

四、點(diǎn)特征檢測(cè)：Harris角點(diǎn)

• 算法步驟：

1. 將原圖像I使用w(x,y)進(jìn)行卷積，并計(jì)算圖像梯度I_x與I_y；
2. 計(jì)算每個(gè)圖像點(diǎn)的自相關(guān)矩陣H；
3. 計(jì)算角點(diǎn)響應(yīng)；
4. 選擇R大于閾值且為局部極大值的點(diǎn)作為角點(diǎn)。

• Harris角點(diǎn)改進(jìn)：

Harris檢測(cè)子獲得的角點(diǎn)可能在圖像上分布不均勻（對(duì)比度高的區(qū)域角點(diǎn)多）

改進(jìn)方法：Adaptive non-maximal suppression（ANMS），只保留半徑r內(nèi)角點(diǎn)響應(yīng)比其他點(diǎn)大10%的點(diǎn)作為角點(diǎn)。（Brown，Szeliski and Winder，2005）

• Harris角點(diǎn)的性質(zhì)：

1.   旋轉(zhuǎn)不變：

橢圓轉(zhuǎn)過(guò)一定角度但是其形狀保持不變（特征值保持不變）

2.   光照變化不變：

只使用了圖像導(dǎo)數(shù)，對(duì)于光照線性變化不變

3.   對(duì)比度變化部分不變：

4.   對(duì)于圖像尺度變化不具有不變性：

五、點(diǎn)特征檢測(cè)：MOPS

MOPS：Multi-scale oriented patches

尺度不變：在多層圖像金字塔上檢測(cè)角點(diǎn)，在同一層進(jìn)行匹配

MOPS局限：待匹配的圖像需要尺度近似

六、點(diǎn)特征檢測(cè)：SIFT

Scale Invariant Feature Transform （SIFT）（Lowe，2004）

主要內(nèi)容：

1.SIFT算法特點(diǎn)

2.SIFT算法流程

3.SIFT算法的具體步驟

4.SIFT點(diǎn)的特點(diǎn)

1、SIFT算法的特點(diǎn)：

• 不變性：

——對(duì)圖像的旋轉(zhuǎn)和尺度變化具有不變性；

——對(duì)三維視角變化和光照變化具有很強(qiáng)的適應(yīng)性；

——局部特征，在遮擋和場(chǎng)景雜亂時(shí)仍保持不變性；

• 辨別力強(qiáng)：

——特征之間相互區(qū)分的能力強(qiáng)，有利于匹配；

• 數(shù)量較多：

——一般500*500的圖像能提取約2000個(gè)特征點(diǎn)。

2、SIFT算法的流程：

在高斯差分（Difference of Gaussian，DOG）尺度空間中提取極值點(diǎn)并進(jìn)行優(yōu)化，從而獲取特征點(diǎn)。

3、SIFT算法點(diǎn)檢測(cè)的具體步驟：

——構(gòu)建尺度空間；

——構(gòu)造高斯差分尺度空間；

——DoG尺度空間極值點(diǎn)檢測(cè)；

——特征點(diǎn)精確定位；

——去除不穩(wěn)定點(diǎn)；

• 構(gòu)建尺度空間：模擬圖像數(shù)據(jù)的多尺度特征

其中是尺度可變高斯函數(shù)

尺度參數(shù)決定圖像的平滑程度，大尺度對(duì)應(yīng)圖像的概貌特征，小尺度對(duì)應(yīng)圖像的細(xì)節(jié)特征

• 構(gòu)造高斯差分尺度空間（Difference of Gaussian，DOG）

為了在尺度空間中檢測(cè)穩(wěn)定的關(guān)鍵點(diǎn)，構(gòu)造高斯差分尺度空間

使用DOG的幾個(gè)理由：

          1.   計(jì)算效率高：高斯卷積，減法；

   2.   高斯差分是對(duì)尺度歸一化LoG的一個(gè)很好的近似，而尺度歸一化的LoG空間具有真正的尺度不變性（Lindegerg 1994）；

   3.  實(shí)驗(yàn)比較表明，從尺度歸一化LoG空間中提取的圖像特征的尺度穩(wěn)定性最好，優(yōu)于梯度、Hessian或Harris角點(diǎn)函數(shù)。

DoG尺度空間：

• DoG尺度空間極值點(diǎn)檢測(cè)：

一個(gè)點(diǎn)和它同尺度的8個(gè)相鄰點(diǎn)以及上下相鄰尺度對(duì)應(yīng)的9×2個(gè)點(diǎn)共26個(gè)點(diǎn)比較，以確保在尺度空間和二維圖像空間都檢測(cè)到極值點(diǎn)。
一個(gè)點(diǎn)如果在DOG尺度空間的26個(gè)領(lǐng)域中是最大或最小值時(shí)，就認(rèn)為該點(diǎn)是圖像在該尺度下的一個(gè)特征點(diǎn)。
一個(gè)特征點(diǎn)是在三維尺度空間的局部極值點(diǎn)。

• 特征點(diǎn)精確定位：

一個(gè)特征點(diǎn)是在三維尺度空間的局部極值點(diǎn)。但(x,y)為整數(shù)像素，為離散尺度，需要對(duì)DoG空間擬合進(jìn)行特征點(diǎn)精確定位。

將的特征點(diǎn)處二階Taylor展開(kāi)：

對(duì)上式求導(dǎo)，并令其為0，得到精確的位置（偏移量）：

若中的三個(gè)變量任意一個(gè)偏移量大于0.5，說(shuō)明精確極值點(diǎn)更接近于另一個(gè)特征點(diǎn)，則更換特征點(diǎn)重復(fù)上述精確定位流程。

• 去除不穩(wěn)定特征點(diǎn)：

——去除對(duì)比度低的點(diǎn)：

計(jì)算極值點(diǎn)取值，若，則保留該特征點(diǎn)，否則丟棄。

——去除邊緣點(diǎn)：

DoG算子會(huì)產(chǎn)生較強(qiáng)的邊緣響應(yīng)，利用Harris檢測(cè)子判斷。

若，則保留該特征點(diǎn)，否則丟棄。

4、SIFT點(diǎn)的特點(diǎn)：

• 視角和旋轉(zhuǎn)變化不變性：

• 光照不變性：

• 尺度不變性：

七、點(diǎn)特征檢測(cè)：小結(jié)

• 根據(jù)自相關(guān)矩陣特征值檢測(cè)角點(diǎn)(Harris)； Harris角點(diǎn)具有旋轉(zhuǎn)、光照不變性，但不具有尺度不變性。
• 高斯差分尺度空間中檢測(cè)尺度不變特征點(diǎn)(SIFT)； SIFT具有尺度不變性。
• Harris與SIFT的機(jī)理不同，因此可以聯(lián)合使用，互為補(bǔ)充。

八、邊緣檢測(cè)

主要內(nèi)容：

1.圖像梯度

2.一階微分算子

3.二階微分算子

4.Canny算子

1、為什么要檢測(cè)邊緣？

一個(gè)例子：基于邊緣的圖像編輯

2、圖像邊緣的產(chǎn)生

物體的邊界、表面方向的改變、不同的顏色、光照明暗的變化

3、邊緣檢測(cè)——圖像梯度

圖像梯度的定義：  

水平梯度：

垂直梯度：

圖像梯度指向灰度變化最快的方向：

梯度幅值表示邊緣的強(qiáng)弱：

邊緣是一階倒數(shù)的極大值點(diǎn)：

4、邊緣檢測(cè)——一階微分算子

使用差分近似一階微分算子：

直接對(duì)圖像使用差分容易受到噪聲影響：

解決方法：先平滑，再微分

由，可將平滑和微分合為一個(gè)算子

二維高斯微分：

實(shí)際應(yīng)用中：對(duì)二維高斯微分進(jìn)行數(shù)值近似：Prewitt算子、Sobel算子

Prewitt算子：去噪+ 增強(qiáng)邊緣

Sobel算子：去噪+ 增強(qiáng)邊緣（給四鄰域更大的權(quán)重）

使用一階微分算子提取邊緣流程：
1. 使用Prewitt或Sobel算子對(duì)圖像進(jìn)行卷積；
2. 將梯度幅值大于閾值的點(diǎn)標(biāo)記為邊緣；
3. (optional)將邊緣細(xì)化為一個(gè)像素寬度。

5、邊緣檢測(cè)——二階微分算子

如果不使用細(xì)化，如何獲得單像素寬度邊緣？

邊緣是一階倒數(shù)的極大值點(diǎn)

邊緣是二階倒數(shù)的過(guò)零點(diǎn)
注意：僅僅等于0不夠，常數(shù)函數(shù)也為0，必須存在符號(hào)改變

對(duì)平滑圖像做二階微分：

二維高斯微分：

Laplacian of Gaussian (LoG)算子：首先用Gauss函數(shù)對(duì)圖像進(jìn)行平滑，抑制噪聲，然后對(duì)經(jīng)過(guò)平滑的圖像使用Laplacian算子
LoG算子等效于：Gaussian平滑+ Laplacian二階微分

LoG因其形狀，也稱為Mexican hat

LoG算子與一階微分算子的比較：

LoG算子的特點(diǎn)：
· 正確檢測(cè)到的邊緣：?jiǎn)蜗袼貙挾龋ㄎ粶?zhǔn)確；
· 形成許多封閉的輪廓，這是一個(gè)主要問(wèn)題；
· 需要更加復(fù)雜的算法檢測(cè)過(guò)零點(diǎn)。

6、邊緣檢測(cè)——Canny算子

• Canny算子是最常用的邊緣檢測(cè)算子
• Canny算子是一階微分算子，但是一個(gè)優(yōu)化的方案
  -單像素寬度
  -噪聲抑制
  -邊緣增強(qiáng)
  -邊緣定位
  J.Canny, “A Computational Approach to Edge Detection”, IEEE Trans. on PAMI, 8(6),1986.
  18482 cites
• Canny算子基本流程

（1）高斯平滑濾波器卷積

（2）使用一階有限差分計(jì)算偏導(dǎo)數(shù)的兩個(gè)陣列

相當(dāng)于與模板進(jìn)行卷積運(yùn)算：

當(dāng)然也可以使用高斯微分算子(Prewitt或Sobel)直接與卷積計(jì)算和

（3）邊緣幅值和邊緣方位角

M代表梯度幅值的大小，在存在邊緣的圖像位置處，
M的值變大，圖像的邊緣特征被“增強(qiáng)”。

（4）梯度非極大值抑制

局部極值周?chē)嬖谙嘟鼣?shù)值的點(diǎn)：

非極大值抑制（NMS：Non-Maxima Suppression）
主要思想：

由梯度幅值圖像，僅保留極大值（嚴(yán)格地說(shuō)，保留梯度方向上的極大值點(diǎn)）。

具體過(guò)程：

1.初始化；

2.對(duì)于每個(gè)點(diǎn)，在梯度方向和反梯度方向各找n個(gè)像素點(diǎn)。若不是這些點(diǎn)中的最大點(diǎn)，則將置零，否則保持不變。

• 在梯度方向的沿線上檢測(cè)該點(diǎn)是否為局部極大值；
• 簡(jiǎn)化的情形，只使用4個(gè)方向：【0,45,90,135】；
• 得到的結(jié)果包含邊緣的寬度為1個(gè)像素；

（5）對(duì)NMS結(jié)果進(jìn)行閾值二值化—雙閾值檢測(cè)

• 使用大的閾值，得到：
  -少量的邊緣點(diǎn)
  -許多空隙
• 使用小的閾值，得到：
  -大量的邊緣點(diǎn)
  -大量的錯(cuò)誤檢測(cè)

兩個(gè)閾值T1，T2：T2 >> T1

由T1得到，低閾值邊緣圖：更大的誤檢測(cè)率
由T2得到，高閾值邊緣圖：更加可靠

（6）邊緣連接
1. 將中相連的邊緣點(diǎn)輸出為一幅邊緣圖像；
2. 對(duì)于中每條邊，從端點(diǎn)出發(fā)在中尋找其延長(zhǎng)的部分，直至與中另外一條邊的端點(diǎn)相連，否則認(rèn)為中沒(méi)有它延長(zhǎng)的部分；
3. 將作為結(jié)果輸出。

Canny算子流程效果圖：

· Canny算子的優(yōu)點(diǎn)
-參數(shù)較少
-計(jì)算效率
-得到的邊緣連續(xù)完整
· 參數(shù)的選擇
-Gauss濾波的尺度
-雙閾值的選擇(LOW=HIGH*0.4)

Canny算子的處理效果：

九、總結(jié)

· 根據(jù)自相關(guān)矩陣特征值檢測(cè)角點(diǎn)(Harris)；
· 高斯差分尺度空間中檢測(cè)尺度不變特征點(diǎn)(SIFT)；
· 一階高斯微分算子(Prewitt、Sobel)極值檢測(cè)邊緣；
· 二階高斯微分算子(LoG)過(guò)零點(diǎn)檢測(cè)邊緣；
· 非極大值抑制+雙閾值檢測(cè)邊緣(Canny)。

十、特征檢測(cè)參考文獻(xiàn)

· Harris, C. and Stephens, M. J. A combined corner and edge detector. In Alvey Vision Conference, 1988.
· Lowe, D. G. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 60(2):91–110, 2004.
· Canny, J. A computational approach to edge detection. IEEE Transactions onPAMI, 8(6):679–698, 1986.
· Tuytelaars, T. and Mikolajczyk, K. Local Invariant Feature Detectors: A Survey. Foundations and Trends in Computer Graphics and Vision, 3(3): 177–280, 2007.