哈里斯邊角偵測

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

概要介紹

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

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

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

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

 

  可以用泰勒展開去近似,以  分別代表   方向的偏微分,於是可以近似成

 

所以 可以寫成

 

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

 

其中 代表結構張量,

 

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

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

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

彩色影像轉換成灰階影像

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

空間微分的計算

第二步是計算整張圖的 

建構結構張量

有了 的資訊後,我們便可以建構結構張量 

計算哈里斯響應

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

 

 

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

 

而k是一個由經驗所訂出來的常數, 

非極大值抑制

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

改進的偵測演算法[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]

更多

參考資料

  1. ^ 1.0 1.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」的參考文獻沒有在文中使用

外部連結