哈里斯邊角偵測

哈里斯邊角偵測(Harris Corner Detector)是被廣泛運用在電腦視覺的演算法，主要是用於從影像中找出代表邊角的特徵點。最早是由Chris Harris 和Mike Stephens在1988年所提出，在當時是莫拉維克邊角偵測器的改進版本。與 莫拉維克邊角偵測器相比，不是對局部小塊區域作45度角移動，而是考量了方向性值直接算出邊角的微分值，這個方法在當時已被證明可以更準確地去分辨出邊角。自從哈里斯邊角偵測器被提出後，後續有很多演算法試著去改良它，而這類的演算法也在很多影像處理的應用上被採用作為前處理。

概要介紹

角落的概念就是它相鄰的區域有兩條截然不同方向的邊，換句話說，角落也是兩條邊的接點，而這條邊的附近有劇烈的亮度變化。邊角是影像重要的特徵，基本上邊角的特性不會受到旋轉、平移以及影像亮度的影響。雖然邊角只是一張影像中的一小部分，但是通常卻代表著一張影像中最重要的特徵，因為它們的資訊相較於整張影像，富有代表性且可以被應用在影像接合，動作追蹤，建立二維馬賽克，立體視覺，以及相關的電腦視覺領域。

為了找出影像中的邊角，科學家們提出了很多不同種的邊角測試器包含Kanade-Lucas-Tomasi (KLT) 算子，哈里斯算子是其中最簡單，有效，及可信賴的方法。這兩種受歡迎的方法均是以局部結構矩陣來當作基礎，相較於Kanade-Lucas-Tomasi (KLT)邊角偵測，就算影像經過旋轉或者是亮度的調整，哈里斯邊角偵測具有良好的結果重現性，因此，它更被常使用在立體匹配及影像資料庫檢索。雖然仍有不少的缺點及限制，哈里斯邊角偵測依然在電腦視覺的應用中是相當重要且基礎的技術。

哈里斯邊角偵測的發展

在不失去一般性的狀況下，我們假設使用的是一張二維的灰階影像。在這裡以$I$代表這張影像，假設我們現在針對一小塊局度區域$(x,y)\in W$移動了$(\mathrm{\Delta }x,\mathrm{\Delta }y)$，以$f$代表這兩塊小區域的加總平方差(SSD)，可以寫作

$f(\mathrm{\Delta }x,\mathrm{\Delta }y)=\sum (x,y)\in W{(I(x,y)-I(x+\mathrm{\Delta }x,y+\mathrm{\Delta }y))}^2.$

$I(x+\mathrm{\Delta }x,y+\mathrm{\Delta }y)$ 可以用泰勒展開去近似，以$I_x$和$I_y$分別代表$I$在$x$和$y$方向的偏微分，於是可以近似成

$I(x+\mathrm{\Delta }x,y+\mathrm{\Delta }y)\approx I(x,y)+I_x(x,y)\mathrm{\Delta }x+I_y(x,y)\mathrm{\Delta }y,$

所以$f(x,y)$可以寫成

$f(\mathrm{\Delta }x,\mathrm{\Delta }y)\approx \sum (x,y)\in W{(I_x(x,y)\mathrm{\Delta }x+I_y(x,y)\mathrm{\Delta }y)}^2.$

如果以矩陣的形式來表達,

$f(\mathrm{\Delta }x,\mathrm{\Delta }y)\approx \left(\begin{array}{cc}\mathrm{\Delta }x& \mathrm{\Delta }y\end{array}\right)M\left(\begin{array}{c}\mathrm{\Delta }x\\ \mathrm{\Delta }y\end{array}\right),$

其中$M$代表結構張量,

$M=\sum (x,y)\in W\left[\begin{array}{cc}{I}_x^2& I_x{I}_y\\ I_x{I}_y& I_y^2\end{array}\right]=\left[\begin{array}{cc}\sum (x,y)\in W{I}_x^2& \sum (x,y)\in W{I}_x{I}_y\\ \sum (x,y)\in W{I}_x{I}_y& \sum (x,y)\in W{I}_y^2\end{array}\right].$

哈里斯邊角偵測的流程

一般而言，哈里斯邊角偵測演算法可以分成下列幾個步驟:

1. 彩色影像轉換成灰階影像
2. 空間微分的計算
3. 建構結構張量
4. 計算哈里斯響應
5. 非極大值抑制

彩色影像轉換成灰階影像

如果輸入是一張彩色影像，第一步便是轉換成灰階影像，可以加快處理速度

空間微分的計算

第二步是計算整張圖的$I_x(x,y),I_y(x,y)$ 。

建構結構張量

有了$I_x(x,y),I_y(x,y)$的資訊後，我們便可以建構結構張量$M$。

計算哈里斯響應

在這一步，我們會運用下列的近似的式子來計算結構張量矩陣的最小的特徵值:

${\lambda }_{min}\approx \frac{{\lambda }_1{\lambda }_2}{({\lambda }_1+{\lambda }_2)}=\frac{det(M)}{trace(M)}$

$trace(M)=m_{11}+m_{22}$

另外一種常見的哈里斯響應是

$R=det(M)-k(trace(M){)}^2={\lambda }_1{\lambda }_2-k({\lambda }_1+{\lambda }_2{)}^2$

而k是一個由經驗所訂出來的常數，$k\in [0.04,0.06]$。

非極大值抑制

由於只靠前面的步驟選出的特徵點很可能會在一小塊區域有很多個，我們希望能在局部區域選出值最大的，因此會設定各個擁有局部最大值的特徵點的距離不能太接近，如此便可以有效選出比較分散在整張圖的特徵點。

改進的偵測演算法

1. 哈里斯-拉普拉斯邊角偵測

2. Differential Morphological Decomposition Based Corner Detector

3. Multi-scale Bilatera Structure Tensor Based Corner Detector

應用

1. 影像對齊，影像縫合，影像配準

2. 建立二維馬賽克

3. 三維場景建模及重建

4. 動作偵測

5. 物體識別

6. 基于内容的影像檢索

7. 影片追蹤

更多

• Template:Link-en
• Template:Link-en
• Corner detection
• Template:Link-en
• Computer vision
• List of computer vision topics

外部連結

• "Learn OpenCV by Examples : Harris Corner Detection"Template:Wayback
• "Harris Corner Detection - OpenCV Documentation"Template:Wayback
• "Harris Corner Detection - OpenCV-Python Tutorials"Template:Wayback