查看“︁哈里斯邊角偵測”︁的源代码

{{特徵檢測(計算機視覺)導航框}}

'''哈里斯邊角偵測'''(Harris Corner Detector)是被廣泛運用在電腦視覺的演算法，主要是用於從影像中找出代表邊角的特徵點。最早是由Chris Harris 和Mike Stephens在1988年所提出，在當時是莫拉維克邊角偵測器的改進版本<ref name="harris"><cite class="citation conference">Chris Harris and Mike Stephens (1988). "A Combined Corner and Edge Detector". ''Alvey Vision Conference''. '''15'''.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=A+Combined+Corner+and+Edge+Detector&rft.btitle=Alvey+Vision+Conference&rft.date=1988&rft.au=Chris+Harris+and+Mike+Stephens&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHarris+Corner+Detector" class="Z3988"><span style="display:none;">&nbsp;</span></span></ref>。與 莫拉維克邊角偵測器相比，不是對局部小塊區域作45度角移動，而是考量了方向性值直接算出邊角的微分值，這個方法在當時已被證明可以更準確地去分辨出邊角。自從哈里斯邊角偵測器被提出後，後續有很多演算法試著去改良它，而這類的演算法也在很多影像處理的應用上被採用作為前處理。

== 概要介紹 ==
角落的概念就是它相鄰的區域有兩條截然不同方向的邊，換句話說，角落也是兩條邊的接點，而這條邊的附近有劇烈的亮度變化<ref name="derpanis"><cite class="citation conference">Konstantinos G. Derpanis (2004). ''The harris corner detector''. York University.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.btitle=The+harris+corner+detector.&rft.pub=York+University&rft.date=2004&rft.au=Konstantinos+G.+Derpanis&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHarris+Corner+Detector" class="Z3988"><span style="display:none;">&nbsp;</span></span></ref>。邊角是影像重要的特徵，基本上邊角的特性不會受到旋轉、平移以及影像亮度的影響。雖然邊角只是一張影像中的一小部分，但是通常卻代表著一張影像中最重要的特徵，因為它們的資訊相較於整張影像，富有代表性且可以被應用在影像接合，動作追蹤，建立二維馬賽克，立體視覺，以及相關的電腦視覺領域。

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

== 哈里斯邊角偵測的發展  <ref name="harris" /> ==

在不失去一般性的狀況下，我們假設使用的是一張二維的灰階影像。在這裡以<math>I</math>代表這張影像，假設我們現在針對一小塊局度區域<math>(x, y) \in W</math>移動了<math>(\Delta x,\Delta y)</math>，以<math>f</math>代表這兩塊小區域的加總平方差(SSD)，可以寫作
:<math>
f(\Delta x,\Delta y) = \underset{(x,y)\in W}\sum\left(I(x,y) - I(x+\Delta x,y+\Delta y)\right)^2.
</math>

<math>I(x+\Delta x,y+\Delta y)</math> 可以用泰勒展開去近似，以<math> I_x</math>和<math> I_y</math>分別代表<math>I</math>在<math>x</math>和<math>y</math>方向的偏微分，於是可以近似成
:<math>
I(x+\Delta x,y+\Delta y) \approx I(x,y) + I_x(x,y)\Delta x+I_y(x,y)\Delta y,
</math> 
所以<math>f(x,y)</math>可以寫成
:<math>
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.
</math> 

如果以矩陣的形式來表達,
:<math>
f(\Delta x,\Delta y) \approx \begin{pmatrix} \Delta x & \Delta y \end{pmatrix} M \begin{pmatrix} \Delta x \\ \Delta y \end{pmatrix},
</math>
其中<math>M</math>代表結構張量,
:<math>
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}.
</math>

== 哈里斯邊角偵測的流程<ref>{{Cite web|url=https://scholar.google.com/scholar?q=++Harris+Operator+Corner+Detection+using+Sliding+Window+Method&btnG=&hl=en&as_sdt=0%252C36|title=Harris Operator Corner Detection using Sliding Window Method - Google Scholar|accessdate=2015-11-29|website=scholar.google.com}}</ref><ref>{{Cite web|url=https://scholar.google.com/scholar?hl=en&q=The+Comparison+and+Application+of+Corner+Detection+Algorithms&btnG=&as_sdt=1%252C36&as_sdtp=|title=The Comparison and Application of Corner Detection Algorithms - Google Scholar|accessdate=2015-11-29|website=scholar.google.com}}</ref> ==
一般而言，哈里斯邊角偵測演算法可以分成下列幾個步驟:

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

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

=== 空間微分的計算 ===
第二步是計算整張圖的<math> I_x( x, y), I_y( x, y) </math> 。

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

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

<math> \lambda _{min} \approx \frac{ \lambda _1 \lambda _2} {(\lambda _1+\lambda _2)} = \frac{det(M)} {trace(M)} </math>

<math> trace(M) = m_{11} + m_{22} </math>

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

<math> R = det(M) - k(trace(M))^2 = \lambda _1 \lambda _2 - k (\lambda _1 + \lambda _2)^2 </math>

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

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

== 改進的偵測演算法<ref>{{Cite journal|title=Improving Harris corner selection strategy|url=http://digital-library.theiet.org/content/journals/10.1049/iet-cvi.2009.0127|last=Bellavia|first=F.|last2=Tegolo|first2=D.|date=2011-03-01|journal=IET Computer Vision|issue=2|doi=10.1049/iet-cvi.2009.0127|volume=5|last3=Valenti|first3=C.|access-date=2018-07-05|archive-date=2018-11-27|archive-url=https://web.archive.org/web/20181127184539/http://digital-library.theiet.org/content/journals/10.1049/iet-cvi.2009.0127|dead-url=no}}</ref><ref>{{Cite book|url=https://link.springer.com/chapter/10.1007/11744023_34|title=Machine Learning for High-Speed Corner Detection|last=Rosten|first=Edward|last2=Drummond|first2=Tom|date=2006-05-07|publisher=Springer Berlin Heidelberg|isbn=978-3-540-33832-1|editor-last=Leonardis|editor-first=Aleš|series=Lecture Notes in Computer Science|pages=430–443|language=en|doi=10.1007/11744023_34#page-1|editor-first2=Horst|editor-last2=Bischof|editor-first3=Axel|editor-last3=Pinz|access-date=2018-07-05|archive-date=2020-08-08|archive-url=https://web.archive.org/web/20200808031526/https://link.springer.com/chapter/10.1007/11744023_34|dead-url=no}}</ref> ==
1. 哈里斯-拉普拉斯邊角偵測<ref>{{Cite web|url=https://scholar.google.com/scholar?q=+A+Comparison+of+Affine+Region+Detectors&btnG=&hl=en&as_sdt=0%252C36|title=A Comparison of Affine Region Detectors - Google Scholar|accessdate=2015-11-29|website=scholar.google.com}}</ref>

2. Differential Morphological Decomposition Based Corner Detector<ref>{{Cite journal|title=Multi scale Harris corner detector based on Differential Morphological Decomposition|url=https://www.researchgate.net/publication/220644165_Multi_scale_Harris_corner_detector_based_on_Differential_Morphological_Decomposition|last=Gueguen|first=L.|last2=Pesaresi|first2=M.|journal=Pattern Recognition Letters|issue=14|doi=10.1016/j.patrec.2011.07.021|volume=32|pages=1714–1719|access-date=2018-07-05|archive-date=2017-10-14|archive-url=https://web.archive.org/web/20171014133620/https://www.researchgate.net/publication/220644165_Multi_scale_Harris_corner_detector_based_on_Differential_Morphological_Decomposition|dead-url=no}}</ref>

3. Multi-scale Bilatera Structure Tensor Based Corner Detector<ref>{{Cite web|url=https://scholar.google.com/scholar?q=A+Multi-scale+Bilateral+Structure+Tensor+Based+Corner+Detector&btnG=&hl=en&as_sdt=0%252C36|title=A Multi-scale Bilateral Structure Tensor Based Corner Detector - Google Scholar|accessdate=2015-11-29|website=scholar.google.com}}</ref>

== 應用 ==
1. 影像對齊，影像縫合，影像配準<ref>{{Cite journal|title=Image registration based on harris corner and mutual information|url=http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=6023066&url=http%253A%252F%252Fieeexplore.ieee.org%252Fxpls%252Fabs_all.jsp%253Farnumber%253D6023066|last=Kang|first=Juan|last2=Xiao|first2=Chuangbai|date=2011-08-01|journal=2011 International Conference on Electronic and Mechanical Engineering and Information Technology (EMEIT)|doi=10.1109/EMEIT.2011.6023066|volume=7|pages=3434–3437|last3=Deng|first3=M.|last4=Yu|first4=Jing|last5=Liu|first5=Haifeng}}</ref>

2. 建立二維馬賽克<ref>{{Cite web|url=https://scholar.google.com/scholar?hl=en&q=Underwater+Mosaic+Creation+using+Video+sequences+from+Different+Altitudes&btnG=&as_sdt=1%252C23&as_sdtp=|title=Underwater Mosaic Creation using Video sequences from Different Altitudes - Google Scholar|accessdate=2015-12-02|website=scholar.google.com}}</ref>

3. 三維場景建模及重建<ref>{{Cite web|url=https://scholar.google.com/scholar?q=Automated+reconstruction+of+3D+scenes+from+sequences+of+images&btnG=&hl=en&as_sdt=0%252C23|title=Automated reconstruction of 3D scenes from sequences of images - Google Scholar|accessdate=2015-12-02|website=scholar.google.com}}</ref>

4. 動作偵測<ref>{{Cite journal|title=Multi-resolution optical flow tracking algorithm based on multi-scale Harris corner points feature|url=http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4598340&tag=1|last=Liu|first=Meng|last2=Wu|first2=Chengdong|date=2008-07-01|journal=Control and Decision Conference, 2008. CCDC 2008. Chinese|doi=10.1109/CCDC.2008.4598340|pages=5287–5291|last3=Zhang|first3=Yunzhou}}</ref>

5. 物體識別<ref>{{Cite web|url=https://scholar.google.com/scholar?q=Object+Recognition+from+Local+Scale-Invariant+Features&btnG=&hl=en&as_sdt=0%252C36|title=Object Recognition from Local Scale-Invariant Features - Google Scholar|accessdate=2015-11-29|website=scholar.google.com}}</ref>

6. 基于内容的影像檢索<ref>{{Cite web|url=https://scholar.google.com/scholar?q=Salient+Points+for+Content+Based+Retrieval+&btnG=&hl=en&as_sdt=0%252C23|title=Salient Points for Content Based Retrieval  - Google Scholar|accessdate=2015-12-02|website=scholar.google.com}}</ref>

7. 影片追蹤<ref>{{Cite web|url=https://scholar.google.com/scholar?q=+Tracking+and+Recognition+of+Objects+using+SURF+Descriptor+and+Harris+Corner+Detection&btnG=&hl=en&as_sdt=0%252C23|title=Tracking and Recognition of Objects using SURF Descriptor and Harris Corner Detection - Google Scholar|accessdate=2015-12-02|website=scholar.google.com}}</ref>

== 更多 ==

* {{link-en|Structure tensor|Structure tensor}}
* {{link-en|Harris affine region detector|Harris affine region detector}}
* [[角检测|Corner detection]]
* {{link-en|Feature detection (computer vision)|Feature detection (computer vision)}}
* [[计算机视觉|Computer vision]]
* [[计算机视觉各主题列表|List of computer vision topics]]

== 參考資料 ==
<references><ref name="harris2"><cite class="citation conference">Chris Harris and Mike Stephens (1988). "A Combined Corner and Edge Detector". ''Alvey Vision Conference''. '''15'''.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=A+Combined+Corner+and+Edge+Detector&rft.btitle=Alvey+Vision+Conference&rft.date=1988&rft.au=Chris+Harris+and+Mike+Stephens&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHarris+Corner+Detector" class="Z3988"><span style="display:none;">&nbsp;</span></span></ref> <ref name="dey2"><cite class="citation conference">Dey, Nilanjan and;  et al. (2012). "A Comparative Study between Moravec and Harris Corner Detection of Noisy Images Using Adaptive Wavelet Thresholding Technique". ''arXiv preprint''. p.&nbsp;1209.1558.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=A+Comparative+Study+between+Moravec+and+Harris+Corner+Detection+of+Noisy+Images+Using+Adaptive+Wavelet+Thresholding+Technique&rft.btitle=arXiv+preprint&rft.pages=1209.1558&rft.date=2012&rft.au=Dey%2C+Nilanjan+and&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHarris+Corner+Detector" class="Z3988"><span style="display:none;">&nbsp;</span></span><span class="citation-comment" style="display:none; color:#33aa33; margin-left:0.3em">CS1 maint: Explicit use of et al. ([[:Category:CS1 maint: Explicit use of et al.|link]]) </span></ref> <ref name="derpanis2"><cite class="citation conference">Konstantinos G. Derpanis (2004). ''The harris corner detector''. York University.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.btitle=The+harris+corner+detector.&rft.pub=York+University&rft.date=2004&rft.au=Konstantinos+G.+Derpanis&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHarris+Corner+Detector" class="Z3988"><span style="display:none;">&nbsp;</span></span></ref></references>

== 外部連結 ==

* [http://opencvexamples.blogspot.com/2013/10/harris-corner-detection.html "Learn OpenCV by Examples : Harris Corner Detection"]{{Wayback|url=http://opencvexamples.blogspot.com/2013/10/harris-corner-detection.html |date=20200627232109 }}
* [http://docs.opencv.org/2.4/doc/tutorials/features2d/trackingmotion/harris_detector/harris_detector.html "Harris Corner Detection - OpenCV Documentation"]{{Wayback|url=http://docs.opencv.org/2.4/doc/tutorials/features2d/trackingmotion/harris_detector/harris_detector.html |date=20200805231218 }}
* [http://opencv-python-tutroals.readthedocs.org/en/latest/py_tutorials/py_feature2d/py_features_harris/py_features_harris.html "Harris Corner Detection - OpenCV-Python Tutorials"]{{Wayback|url=http://opencv-python-tutroals.readthedocs.org/en/latest/py_tutorials/py_feature2d/py_features_harris/py_features_harris.html |date=20160423174843 }}

[[Category:影像科技]]