天天看點

Harris角點檢測原理分析

看到一篇從數學意義上講解Harris角點檢測很透徹的文章,轉載自:http://blog.csdn.net/newthinker_wei/article/details/45603583

主要參考了:http://blog.csdn.net/yudingjun0611/article/details/7991601  Harris角點檢測算子

本文将該文拷貝了過來,并做了一些數學方面的補充,以友善對數學已經生疏的小夥伴們參考了解。由于補充的内容還挺多,是以還是将本文标注為了原創。

我增加的部分在文中用 {{  }} 圈了起來并用紅色字型标注。

正文開始。

Harris角點檢測算子是于1988年由CHris Harris & Mike Stephens提出來的。在具體展開之前,不得不提一下Moravec早在1981就提出來的Moravec角點檢測算子。

1.Moravec角點檢測算子

        Moravec角點檢測算子的思想其實特别簡單,在圖像上取一個W*W的“滑動視窗”,不斷的移動這個視窗并檢測視窗中的像素變化情況E。像素變化情況E可簡單分為以下三種:A  如果在視窗中的圖像是什麼*坦的,那麼E的變化不大。B  如果在視窗中的圖像是一條邊,那麼在沿這條邊滑動時E變化不大,而在沿垂直于這條邊的方向滑動視窗時,E的變化會很大。 C  如果在視窗中的圖像是一個角點時,視窗沿任何方向移動E的值都會發生很大變化。

上圖就是對Moravec算子的形象描述。用數學語言來表示的話就是:

其中(x,y)就表示四個移動方向(1,0)(1,1)(0,1)(-1,1),E就是像素的變化值。Moravec算子對四個方向進行權重求和來确定變化的大小,然和設定門檻值,來确定到底是邊還是角點。

2.Harris角點檢測算子

        Harris角點檢測算子實質上就是對Moravec算子的改良和優化。在原文中,作者提出了三點Moravec算子的缺陷并且給出了改良方法:

1.  Moravec算子對方向的依賴性太強,在上文中我們可以看到,Moravec算子實際上隻是移動了四個45度角的離散方向,真正優秀的檢測算子應該能考慮到各個現象的移動變化情況。為此,作者采用微分的思想(這裡不清楚的話可以複習下高數中的全微分):

其中:

是以E就可以表示為:

2.由于Moravec算子采用的是方形的windows,是以的E的響應比較容易受到幹擾,Harris采用了一個較為*滑的視窗——高斯函數:

3.Moravec算子對邊緣響應過于靈敏。為此,Harris提出了對E進行變形:

對,沒錯,變成了二次型,果然是大牛,更牛的還在後面!其中,

用α,β表示矩陣M的特征值,這樣會産生三種情況:A  如果α,β都很小,說明高斯windows中的圖像接**坦。 B  如果一個大一個小,則表示檢測到邊。 C  如果α,β都很大,那麼表示檢測到了角點。

α,β是什麼?α,β就是橢圓的長短軸的度量,什麼?橢圓哪裡來?橢圓就是那個二次型函數來的!下圖的意思我就不詳細講解了,相信大家能懂。

{{

轉載注:NewThinker_wei:

關于矩陣知識的一點補充:好長時間沒看過線性代數的話,這一段比較難了解。可以看到M是實對稱矩陣,這裡簡單溫習一下實對稱矩陣和二次型的一些知識點吧。

1. 關于特征值和特征向量:

特征值的特征向量的概念忘了就自己查吧,這裡隻說關鍵的。對于實對稱矩陣M(設階數為n),則一定有n個實特征值,每個特征值對應一組特征向量(這組向量中所有向量共線),不同特征值對應的特征向量間互相正交;(注意這裡說的是實對稱矩陣,不是所有的矩陣都滿足這些條件)

2. 關于對角化:

對角化是指存在一個正交矩陣Q,使得  Q’MQ 能成為一個對角陣(隻有對角元素非0),其中Q’是Q的轉置(同時也是Q的逆,因為正交矩陣的轉置就是其逆)。一個矩陣對角化後得到新矩陣的行列式和矩陣的迹(對角元素之和)均與原矩陣相同。如果M是n階實對稱矩陣,則Q中的第 j 列就是第 j 個特征值對應的一個特征向量(不同列的特征向量兩兩正交)。

3. 關于二次型:

對于一個n元二次多項式,f(x1,x2....xn) = ∑ ( aij*xi*xj ) ,其中 i 和 j 的求和區間均為 [1,n] ,

可将其各次的系數 aij 寫成一個n*n矩陣M,由于 aij 和 aji 的對稱等價關系,一般将 aij 和 aji 設為一樣的值,均為 xi*xj 的系數的二分之一。這樣,矩陣M就是實對稱矩陣了。即二次型的矩陣預設都是實對稱矩陣

4. 關于二次型的标準化(正交變換法):

二次型的标準化是指通過構造一個n階可逆矩陣 C,使得向量 ( x1,x2...xn ) = C * (y1,y2...yn),把n維向量 x 變換成n維向量 y ,并代入f(x1,x2....xn) 後得到 g(y1,y2...yn),而後者的表達式中的二次項中不包含任何交叉二次項 yi*yj(全部都是*方項 yi^2),也即表達式g的二次型矩陣N是對角陣。用公式表示一下 f 和 g ,(下面的表達式中 x 和 y都代表向量,x' 和 y' 代表轉置)

f = x' * M * x ;

g = f = x' * M * x = (Cy)' * M * (Cy) = y' * (C'MC) * y = y' * N * y  ;

是以 C‘MC = N。正交變換法,就是直接将M對角化得到N,而N中對角線的元素就是M的特征值。正交變換法中得到的 C 正好是一個正交矩陣,其每一列都是兩兩正交的機關向量,是以 C 的作用僅僅是将坐标軸旋轉(不會有放縮)。 

OK,基礎知識補充完了,再來說說Harris角點檢測中的特征值是怎麼回事。這裡的 M 是

将M對角化後得到矩陣N,他們都是2階矩陣,且N的對角線元素就是本文中提到的 α 和 β。

本來 E(x,y) = A*x^2 + 2*C*x*y + B*y^2 ,而将其标準後得到新的坐标 xp和yp,這時表達式中就不再含有交叉二次項,新表達式如下:

 E(x,y) = Ep (xp,yp) = α*xp^2 + β*yp^2,

我們不妨畫出 Ep (xp,yp) = 1 的等高線L ,即

 α*xp^2 + β*yp^2 = 1 ,

可見這正好是(xp,yp)空間的一個橢圓,而α 和 β則分别是該橢圓長、短軸*方的倒數(或者反過來),且長短軸的方向也正好是α 和 β對應的特征向量的方向。由于(x,y)空間隻是 (xp,yp)空間的旋轉,沒有放縮,是以等高線L在(x,y)空間也是一個全等的橢圓,隻不過可能是傾斜的。

現在就能了解下面的圖檔中出現的幾個橢圓是怎麼回事了,圖(a)中畫的正是高度為 1 的等高線,(其他”高度“處的等高線也是橢圓,隻不過長短軸的長度還要乘以一個系數)。其他的幾幅圖檔中可以看到,“*坦”區域由于(高度)變化很慢,等高線(橢圓)就比較大;而”邊緣“區域則是在一個軸向上高度變化很快,另一個與之垂直的軸向上高度變化很慢,是以一個軸很長一個軸很短;“角點”區域各個方向高度都變化劇烈,是以橢圓很小。我們人眼可以直覺地看到橢圓的大小胖瘦,但如何讓計算機識别這三種不同的幾何特征呢?為了能區分出角點、邊緣和*坦區域我們現在需要用α 和 β構造一個特征表達式,使得這個特征式在三種不同的區域有明顯不同的值。一個表現還不錯的特征表達式就是:

(αβ) - k(α+β)^2

表達式中的 k 的值怎麼選取呢?它一般是一個遠小于 1 的系數,opencv的預設推薦值是 0.04(=0.2的*方),它*似地表達了一個門檻值:當橢圓短、長軸的*方之比(亦即α 和 β兩個特征值之比)小于這個門檻值時,認為該橢圓屬于“一個軸很長一個軸很短”,即對應的點會被認為是邊緣區域。

對于邊緣部分,(假設較大的特征值為β)由于 β>>α且α<kβ,是以特征式 :

(αβ) - k(α+β)^2 ≈ αβ - kβ^2  <  (kβ)β - kβ^2 = 0

即邊緣部分的特征值小于0 ;

對于非邊緣部分,α 和 β相差不大,可認為 (α+β)^2 ≈ 4αβ,是以特征式:

(αβ) - k(α+β)^2 ≈ αβ - 4kαβ =  ( 1 - 4k ) * αβ

由于 k 遠小于1,是以 1 - 4k ≈ 1,這樣特征式進一步*似為:

(αβ) - k(α+β)^2 ≈  αβ

在角點區域,由于α 和 β都較大,對應的特征式的值也就很大;而在*坦區域,特征式的值則很小。

是以,三種不同區域的判别依據就是: 如果特征表達式的值為負,則屬于邊緣區域;如果特征表達式的值較大,則屬于角點區域;如果特征表達式的值很小,則是*坦區域。

最後,由于αβ和(α+β)正好是M對角化後行列式和迹,再結合上面補充的基礎知識第2條中提到的行列式和迹在對角化前後不變,就可以得到 (αβ) - k(α+β)^2 = det(M) - k*Tr(M)^2,這就是Harris檢測的表達式。

轉載注解完畢,下面接原文。

}}

有人又要問了,你怎麼知道我檢測到α,β算大還是算小?對此天才哈裡斯定義了一個角點響應函數:

其中(這些都是線性代數裡的知識):

我們驚喜的發現,R為正值是,檢測到的是角點,R為負時檢測到的是邊,R很小時檢測到的是*坦區域。至于他怎麼想出來的,我就不得而知了......

 Harris角點檢測算法有諸多優點:A  旋轉不變性,橢圓轉過一定角度但是其形狀保持不變(特征值保持不變)

B  對于圖像灰階的仿射變化具有部分的不變性,由于僅僅使用了圖像的一介導數,對于圖像灰階*移變化不變;對于圖像灰階尺度變化不變

當然Harris也有許多不完善的地方:A  它對尺度很敏感,不具備幾何尺度不變性。

B  提取的角點是像素級的。以至于後來又有許多牛人提出了更多更完善的檢測算子,且聽下回分解!

---------------------------------

業精于勤而荒于嬉 行成于思而毀于随

---------------------------------