哈里斯邊角偵測

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

概要介紹

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

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

哈里斯邊角偵測的發展 ^[1]

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

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

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

${\displaystyle I(x+\Delta x,y+\Delta y)\approx I(x,y)+I_{x}(x,y)\Delta x+I_{y}(x,y)\Delta y,}$ 

所以${\displaystyle f(x,y)}$ 可以寫成

${\displaystyle f(\Delta x,\Delta y)\approx {\underset {(x,y)\in W}{\sum }}\left(I_{x}(x,y)\Delta x+I_{y}(x,y)\Delta y\right)^{2}.}$ 

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

${\displaystyle f(\Delta x,\Delta y)\approx {\begin{pmatrix}\Delta x&\Delta y\end{pmatrix}}M{\begin{pmatrix}\Delta x\\\Delta y\end{pmatrix}},}$ 

其中${\displaystyle M}$ 代表結構張量,

${\displaystyle M={\underset {(x,y)\in W}{\sum }}{\begin{bmatrix}I_{x}^{2}&I_{x}I_{y}\\I_{x}I_{y}&I_{y}^{2}\end{bmatrix}}={\begin{bmatrix}{\underset {(x,y)\in W}{\sum }}I_{x}^{2}&{\underset {(x,y)\in W}{\sum }}I_{x}I_{y}\\{\underset {(x,y)\in W}{\sum }}I_{x}I_{y}&{\underset {(x,y)\in W}{\sum }}I_{y}^{2}\end{bmatrix}}.}$ 

哈里斯邊角偵測的流程^[3][4]

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

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

彩色影像轉換成灰階影像

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

空間微分的計算

第二步是計算整張圖的${\displaystyle I_{x}(x,y),I_{y}(x,y)}$  。

建構結構張量

有了${\displaystyle I_{x}(x,y),I_{y}(x,y)}$ 的資訊後，我們便可以建構結構張量${\displaystyle M}$ 。

計算哈里斯響應

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

${\displaystyle \lambda _{min}\approx {\frac {\lambda _{1}\lambda _{2}}{(\lambda _{1}+\lambda _{2})}}={\frac {det(M)}{trace(M)}}}$ 

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

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

${\displaystyle R=det(M)-k(trace(M))^{2}=\lambda _{1}\lambda _{2}-k(\lambda _{1}+\lambda _{2})^{2}}$ 

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

非極大值抑制

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

改進的偵測演算法^[5][6]

1. 哈里斯-拉普拉斯邊角偵測^[7]

2. Differential Morphological Decomposition Based Corner Detector^[8]

3. Multi-scale Bilatera Structure Tensor Based Corner Detector^[9]

應用

1. 影像對齊，影像縫合，影像配準^[10]

2. 建立二維馬賽克^[11]

3. 三維場景建模及重建^[12]

4. 動作偵測^[13]

5. 物體識別^[14]

6. 基于内容的影像檢索^[15]

7. 影片追蹤^[16]

更多

• Structure tensor（英语：Structure tensor）
• Harris affine region detector（英语：Harris affine region detector）
• Corner detection
• Feature detection (computer vision)（英语：Feature detection (computer vision)）
• Computer vision
• List of computer vision topics

參考資料

1. Chris Harris and Mike Stephens (1988). "A Combined Corner and Edge Detector". Alvey Vision Conference. 15. 
2. Konstantinos G. Derpanis (2004). The harris corner detector. York University. 
3. Harris Operator Corner Detection using Sliding Window Method - Google Scholar. scholar.google.com. [2015-11-29]. 
4. The Comparison and Application of Corner Detection Algorithms - Google Scholar. scholar.google.com. [2015-11-29]. 
5. Bellavia, F.; Tegolo, D.; Valenti, C. Improving Harris corner selection strategy. IET Computer Vision. 2011-03-01, 5 (2) [2018-07-05]. doi:10.1049/iet-cvi.2009.0127. （原始内容于2018-11-27）. 
6. Rosten, Edward; Drummond, Tom. Leonardis, Aleš; Bischof, Horst; Pinz, Axel , 编. Machine Learning for High-Speed Corner Detection. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 2006-05-07: 430–443 [2018-07-05]. ISBN 978-3-540-33832-1. doi:10.1007/11744023_34#page-1. （原始内容于2020-08-08） （英语）. 
7. A Comparison of Affine Region Detectors - Google Scholar. scholar.google.com. [2015-11-29]. 
8. Gueguen, L.; Pesaresi, M. Multi scale Harris corner detector based on Differential Morphological Decomposition. Pattern Recognition Letters: 1714–1719. [2018-07-05]. doi:10.1016/j.patrec.2011.07.021. （原始内容于2017-10-14）. 
9. A Multi-scale Bilateral Structure Tensor Based Corner Detector - Google Scholar. scholar.google.com. [2015-11-29]. 
10. Kang, Juan; Xiao, Chuangbai; Deng, M.; Yu, Jing; Liu, Haifeng. Image registration based on harris corner and mutual information. 2011 International Conference on Electronic and Mechanical Engineering and Information Technology (EMEIT). 2011-08-01, 7: 3434–3437. doi:10.1109/EMEIT.2011.6023066. 
11. Underwater Mosaic Creation using Video sequences from Different Altitudes - Google Scholar. scholar.google.com. [2015-12-02]. 
12. Automated reconstruction of 3D scenes from sequences of images - Google Scholar. scholar.google.com. [2015-12-02]. 
13. Liu, Meng; Wu, Chengdong; Zhang, Yunzhou. Multi-resolution optical flow tracking algorithm based on multi-scale Harris corner points feature. Control and Decision Conference, 2008. CCDC 2008. Chinese. 2008-07-01: 5287–5291. doi:10.1109/CCDC.2008.4598340. 
14. Object Recognition from Local Scale-Invariant Features - Google Scholar. scholar.google.com. [2015-11-29]. 
15. Salient Points for Content Based Retrieval - Google Scholar. scholar.google.com. [2015-12-02]. 
16. Tracking and Recognition of Objects using SURF Descriptor and Harris Corner Detection - Google Scholar. scholar.google.com. [2015-12-02]. 

引证错误：在<references>标签中name属性为“harris2”的参考文献没有在文中使用
引证错误：在<references>标签中name属性为“dey2”的参考文献没有在文中使用
引证错误：在<references>标签中name属性为“derpanis2”的参考文献没有在文中使用

外部連結

• "Learn OpenCV by Examples : Harris Corner Detection"（页面存档备份，存于互联网档案馆）
• "Harris Corner Detection - OpenCV Documentation"（页面存档备份，存于互联网档案馆）
• "Harris Corner Detection - OpenCV-Python Tutorials"（页面存档备份，存于互联网档案馆）