角點偵測介紹
在計算機視覺的領域中，偵測角點是可說是關鍵的一環。角點代表了影像中局部區域的特殊結構，找出角點有助於識別物體、影像配準和目標追蹤等方面。本文將介紹角點偵測的基本概念、歷史演進以及一些常見的角點偵測演算法。
什麼是角點？
在一張圖像中，角點是指其周圍區域的灰度變化劇烈的一點。換句話說，角點處存在著至少兩個主要方向的高梯度變化，使得該點成為一個特殊的點，可以協助識別和跟蹤。
角點偵測演算法的歷史
在日常生活中，我們可以很輕易地看見物體的邊角在哪裡，但是對機器來說則並非如此，必須透過對收到的圖像進行分析才能實現，於是數十年來便產生了許多種角點偵測演算法。
若想要在圖像中做角點偵測，我們通常會需要先選定一個觀察的區域，稱為window(即圖一中的紅框)。角點偵測演算法依據其核心精神大致可以分為兩類，以下將先後進行介紹。
 |
| 圖一、一個簡單的觀察邊角的例子。 |
Moravec Corner Detector (1980)
早在1980年，Hans Moravec提出了最早的角點偵測方法之一，稱為Moravec Corner Detector。該方法通過在影像中的不同位置進行窗口的平移，並計算每個位置的局部區域的灰度變化，來識別可能的角點。然而，這種方法對雜訊和光線變化非常敏感。
Harris Corner Detector (1988)
為了改進Moravec的方法，Chris Harris 和 Mike Stephens 在1988年提出了Harris Corner Detector。這種方法引入了一個結構張量函數，通過計算區域的二次矩陣的最小特徵值，評估了每個像素的角點可能性。Harris Corner Detector在角點檢測中取得了顯著的進展，成為了經典的角點偵測演算法。
結構張量：(Ix、Iy是圖像在x、y方向的梯度)
$$M=\sum_{(x,y)\in W} \begin{bmatrix}I_{x}^{2} & I_{x}I_{y} \\ I_{x}I_{y} & I_{y}^{2} \\\end{bmatrix}$$
評分方式：
$$R=det(M)-k(trace(M))^{2}=\lambda_{1}\lambda_{2}-k(\lambda_{1}+\lambda_{2})^2$$
Shi-Tomasi Corner Detector (1994)
Shi-Tomasi Corner Detector是對Harris Corner Detector的改進，提出了一個更穩健的角點評分機制。Shi-Tomasi使用最小特徵值中的較小者作為結構強度的度量，相對於Harris方法更能應對各向異性的情況。
 |
| 圖二、這兩張圖直觀地展示了Harris(左)和Shi-Tomasi(右)的評分機制的差別。 |
此後又有一些對Harris Corner Detector的改良方法被提出，以上方法也被稱為Harris流派，他們的優點是偵測力強、正確率高，缺點則是計算量大，難以應用於有即時性需求的情形。
角點偵測演算法的另一類型是設法直接觀察window中是否存在類似邊角的特徵，其中最早的是由Smith和Brady在1997年發表的SUSAN演算法。
SUSAN（Smallest Univalue Segment Assimilating Nucleus,1997）
相較於基於梯度的方法，SUSAN演算法更加注重局部區域的一致性，其核心精神是比較某一像素點與其周圍區域內其他像素的灰度值，如果某像素與其周邊的灰度值都相似，那麼它就可能是一個平坦(均勻)區域，反之，如果某像素的灰度值與其周邊的大多數像素不同，那麼它就可能是一個角點。(圖三)
 |
| 圖三、這兩張圖中我們不難看出，在均勻區域所得到的灰度相似面積最大，在邊緣附近較小，在角點附近則最小。 |
之後又有其他在window內直接尋找邊角特徵的方法被提出，例如Trajkovic和 Hedley在1998年發表的方法：(圖四)
 |
| 圖四、此方法是比較參考點和圓形window上直徑的兩個端點之間的灰度，在找過每條直徑之後取最小值。 |
以上介紹的兩種方法雖然在速度上比Harris有所提升，但仍然存在精度下降、抗雜訊能力差、缺乏尺度不變性、或者速度還是不夠快等方面的問題。
尺度不變性
SIFT (Scale-Invariant Feature Transform)
在角點檢測的同時，尺度不變性是一個關鍵的考慮因素。David Lowe在1999年提出的SIFT演算法在角點檢測的基礎上引入了高斯差分金字塔，使其具有尺度不變性，同時提供了強大的特徵描述。
ORB (Oriented FAST and Rotated BRIEF)
ORB演算法是一種結合FAST和BRIEF的角點偵測方法，它在提供良好檢測性能的同時，引入了方向性和旋轉不變性。ORB被廣泛應用於實時追蹤和配準等應用場景。
進入二十一世紀，為了進一步提升速度，其中一種思路是盡可能快的排除掉不是角點的點，另一種思路則是利用越來越強大的GPU，把演算法設計成可以平行化處理的形式。
快速角點檢測演算法
FAST (Features from Accelerated Segment Test, 2006)
為了應對實時應用的需求，Edward Rosten 在2006年提出了FAST演算法。FAST通過加速區域的分割測試，即在一個像素周圍的16個點上進行強度比較，以迅速識別可能的角點。FAST是一種足夠高速的角點檢測方法，被廣泛應用於即時視頻處理和圖像配準等場景。
儘管FAST演算法真的非常快，但它的精度也下降得很厲害，於是後來又有幾種以FAST的快速識別為基礎，稍微犧牲速度(仍遠遠快過傳統演算法)以提升精度的改進，例如BRISK等等，而到了最近的CCDA演算法，已經稱得上是又快又準。
 |
| 圖五、各種演算法的速度、精度比較。 |
深度學習在角點偵測的應用
近年來，深度學習技術的崛起對角點偵測產生了顯著的影響。一些基於卷積神經網路（CNN）的方法能夠學習到更複雜的特徵表示，使得角點檢測更加精確和可靠。然而，這些方法通常需要大量的訓練數據和計算資源。
總而言之，角點偵測作為影像處理和計算機視覺中的重要一環，歷經多個階段的演進，每個方法都在不同方面有其優勢，在實際應用中，應基於應用場景、計算能力和準確性等多方面的考慮選擇合適的角點偵測方法。無論如何，角點偵測的這些方法都為影像處理和計算機視覺領域的發展做出了卓越的貢獻。
撰稿人：劉徹
參考資料
1. H. Moravec (1980). "Obstacle Avoidance and Navigation in the Real World by a Seeing Robot Rover"
2. C. Harris and M. Stephens (1988). "A combined corner and edge detector" In Alvey vision conference (Vol. 15, No. 50, pp. 10-5244).
3. J. Shi and C. Tomasi (June 1994). "Good Features to Track" In 1994 Proceedings of IEEE conference on computer vision and pattern recognition (pp. 593-600). IEEE.
4. S. M. Smith and J. M. Brady (May 1997). "SUSAN – a new approach to low level image processing" International journal of computer vision, 23(1), 45-78.
5. M. Trajkovic and M. Hedley (1998). "Fast corner detection" Image and vision computing, 16(2), 75-87.
6. E. Rosten and T. Drummond (2006). “Machine Learning for High-Speed Corner Detection” In Computer Vision–ECCV 2006: 9th European Conference on Computer Vision, Graz, Austria, May 7-13, 2006. Proceedings, Part I 9 (pp. 430-443). Springer Berlin Heidelberg.
7. E. Rublee , V. Rabaud , K. Konolige, G. Bradski (2011) “ORB: an efficient alternative to SIFT or SURF” In 2011 International conference on computer vision (pp. 2564-2571). Ieee.
8. Peng, Z., Wu, J., & Fan, G. (2019). "CCDA: a concise corner detection algorithm." Machine Vision and Applications, 30, 1029-1040.
留言
張貼留言