哈里斯邊角偵測(Harris Corner Detector)是被廣泛運用在電腦視覺的演算法,主要是用於從影像中找出代表邊角的特徵點。最早是由Chris Harris 和Mike Stephens在1988年所提出,在當時是莫拉維克邊角偵測器的改進版本[1]。與 莫拉維克邊角偵測器相比,不是對局部小塊區域作45度角移動,而是考量了方向性值直接算出邊角的微分值,這個方法在當時已被證明可以更準確地去分辨出邊角。自從哈里斯邊角偵測器被提出後,後續有很多演算法試著去改良它,而這類的演算法也在很多影像處理的應用上被採用作為前處理。
概要介紹
角落的概念就是它相鄰的區域有兩條截然不同方向的邊,換句話說,角落也是兩條邊的接點,而這條邊的附近有劇烈的亮度變化[2]。邊角是影像重要的特徵,基本上邊角的特性不會受到旋轉、平移以及影像亮度的影響。雖然邊角只是一張影像中的一小部分,但是通常卻代表著一張影像中最重要的特徵,因為它們的資訊相較於整張影像,富有代表性且可以被應用在影像接合,動作追蹤,建立二維馬賽克,立體視覺,以及相關的電腦視覺領域。
為了找出影像中的邊角,科學家們提出了很多不同種的邊角測試器包含Kanade-Lucas-Tomasi (KLT) 算子,哈里斯算子是其中最簡單,有效,及可信賴的方法。這兩種受歡迎的方法均是以局部結構矩陣來當作基礎,相較於Kanade-Lucas-Tomasi (KLT)邊角偵測,就算影像經過旋轉或者是亮度的調整,哈里斯邊角偵測具有良好的結果重現性,因此,它更被常使用在立體匹配及影像資料庫檢索。雖然仍有不少的缺點及限制,哈里斯邊角偵測依然在電腦視覺的應用中是相當重要且基礎的技術。
哈里斯邊角偵測的發展 [1]
在不失去一般性的狀況下,我們假設使用的是一張二維的灰階影像。在這裡以
代表這張影像,假設我們現在針對一小塊局度區域
移動了
,以
代表這兩塊小區域的加總平方差(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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/35ce024a9459b5de927019b1161c21f0224f2f77)
可以用泰勒展開去近似,以
和
分別代表
在
和
方向的偏微分,於是可以近似成
![{\displaystyle I(x+\Delta x,y+\Delta y)\approx I(x,y)+I_{x}(x,y)\Delta x+I_{y}(x,y)\Delta y,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/47aa705bb100d02257ceaf7a4cca269c710ef42e)
所以
可以寫成
![{\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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a2b013b8e2c30eb355ee07f45f8651f1249e1db4)
如果以矩陣的形式來表達,
![{\displaystyle f(\Delta x,\Delta y)\approx {\begin{pmatrix}\Delta x&\Delta y\end{pmatrix}}M{\begin{pmatrix}\Delta x\\\Delta y\end{pmatrix}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e884b4ad4ae58ecfcdfea77f9a5c2ca7c5420119)
其中
代表結構張量,
![{\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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d0fa59ff77944e4661dfe0a67b51cf7c09c79690)
一般而言,哈里斯邊角偵測演算法可以分成下列幾個步驟:
- 彩色影像轉換成灰階影像
- 空間微分的計算
- 建構結構張量
- 計算哈里斯響應
- 非極大值抑制
彩色影像轉換成灰階影像
如果輸入是一張彩色影像,第一步便是轉換成灰階影像,可以加快處理速度
空間微分的計算
第二步是計算整張圖的
。
建構結構張量
有了
的資訊後,我們便可以建構結構張量
。
計算哈里斯響應
在這一步,我們會運用下列的近似的式子來計算結構張量矩陣的最小的特徵值:
![{\displaystyle \lambda _{min}\approx {\frac {\lambda _{1}\lambda _{2}}{(\lambda _{1}+\lambda _{2})}}={\frac {det(M)}{trace(M)}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/54a41a283f555687c19e9e724265bdeadb1a563a)
![{\displaystyle trace(M)=m_{11}+m_{22}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97c7514f374fcbdf5d47a80c64951e4536284e2b)
另外一種常見的哈里斯響應是
![{\displaystyle R=det(M)-k(trace(M))^{2}=\lambda _{1}\lambda _{2}-k(\lambda _{1}+\lambda _{2})^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d2b2a1543d99a75cce4c71bdaff196f769f0b30c)
而k是一個由經驗所訂出來的常數,
。
非極大值抑制
由於只靠前面的步驟選出的特徵點很可能會在一小塊區域有很多個,我們希望能在局部區域選出值最大的,因此會設定各個擁有局部最大值的特徵點的距離不能太接近,如此便可以有效選出比較分散在整張圖的特徵點。
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]
更多
參考資料
引用错误:在<references>
标签中name属性为“harris2”的参考文献没有在文中使用
引用错误:在<references>
标签中name属性为“dey2”的参考文献没有在文中使用
引用错误:在<references>
标签中name属性为“derpanis2”的参考文献没有在文中使用
外部連結