查看“︁角检测”︁的源代码

{{Expand English}}
{{FeatureDetectionCompVisNavbox}}
'''角检测'''（{{lang-en|Corner detection}}）或'''兴趣点检测'''（{{lang|en|interest point detection}}），是计算机视觉系统中用来提取特征以及推测图像内容的一种方法。角检测的应用很广，经常用在[[运动检测]]、[[跟踪]]、[[馬賽克 (影像處理)|馬賽克]]（image mosaicing）、[[全景图缝合]]（panorama stiching）、[[三维建模]]以及[[物体识别]]中。

== 问题定义==
两条边的交点形成一个角（点）。而图像的'''要点'''（也称为'''受关注点'''）是指图像中具有代表性以及稳健性（即指该点能够在有噪声干扰的情况下也能稳定的被定位，在大陆亦被称为：鲁棒性）的点。也就是说，要点可以是'''角'''（点），也可以不是，例如局部亮点或暗点，线段终点，或者曲线上的曲率最大值点。在实际应用中，很多所谓的（角）点检测算法其实是检测要点，而不仅仅是角（点）。所以，如果我们只想检测角的话，还需要对检测出的要点进一步分析。

例如也可以先經過邊檢測，之後在做一些後處理來檢測角，像是[[Kirsch operator]]和[[Frei-Chen masking set]]兩種方法。為了分辨區辨識時圖像含有一部分目標圖像的資訊是否正確，角檢測通常不是一個非常確定且同時需要很多額外的確認才可以確定，角檢測在圖像上最簡單的做法是利用[[相關 (概率論)|相關]]性，但這樣的作法需要耗費大量的運算資源以及得到的結果可能只是局部最大值，因此有另一個常見的作法是使用Harris和Stephens所提出的經由改善Moravec方法的結果。

== Moravec 角檢測演算法 ==
這是最早使用來做角檢測的做法，他首先定義所謂的「角」就是那些自我相似程度低的點。這個演算法檢查所有圖像中的像素，並考慮以該像素為中心點的一片範圍，該範圍與他周圍覆蓋最大的另一個範圍的相似度做為參考，而相似度通常是將兩個範圍的對應點計算誤差的平方和(SSD: Sum of Squared differences) ，越小代表相似度越高。

舉例來說，如果一個像素是位於一片均勻強度的區塊時，這時每個像素周圍與其附近的像素的周圍都是相當類似的，因此相似度也高，不會被認為是角。而在圖形的邊界處的像素，若是與邊垂直方向處附近的像素，兩者的周圍圖像相似度就會比較低，然而若是與邊平行附近的像素，兩者的周圍圖像相似度就會比較高(看到的都是一條在同樣位置的邊)，因此也不會被認為是角。只有在那些與附近像素的周圍圖像都很不相似的像素，才會被認為是「角」。

如果我們將這種與周圍的相似程度量化(使用誤差平方和)，並且找出整個圖像的局部最大值(局部最不相似的點)，這些局部最大值就很有可能是我們想要偵測到的「角」。

== Harris & Stephens / Plessey / Shi–Tomasi 角檢測演算法 ==
{{Main|哈里斯邊角偵測}}
Harris & Stephens改善了Moravec的方法，他們直接考慮每個像素沿著特定方向處的像素的SSD，而不是使用與周圍像素範圍的SSD。

不失一般性，我們假設現在是對一個灰階的2維圖像來做偵測。令這個圖為 <math>I</math> ，考慮 <math>(u, v)</math> 位置的像素與周圍的區塊，並選取一個固定向量 <math>(x, y)</math> 作為該像素的參考像素，因此固定的這個向量 <math>(x, y)</math> 所算出的所有差平方和的總和記做為 <math>S(x,y)</math> ，而對於每個 <math>(u,v)</math> 做不同加權，就可以得到
:<math>
S(x,y) = \sum_u \sum_v w(u,v) \, \left( I(u+x,v+y) - I(u,v)\right)^2
</math>
如果使用[[泰勒展開式]]將 <math>I(u+x,v+y)</math> 展開，假設<math> I_x</math> 和 <math> I_y</math>是 <math>I</math> 的偏微分，可以得到
:<math>
I(u+x,v+y) \approx I(u,v) + I_x(u,v)x+I_y(u,v)y
</math>
並將原式改寫成
:<math>
S(x,y) \approx \sum_u \sum_v w(u,v) \, \left( I_x(u,v)x + I_y(u,v)y \right)^2,
</math>
或是使用[[矩陣]]來簡化算式
:<math>
S(x,y) \approx \begin{pmatrix} x & y \end{pmatrix} A \begin{pmatrix} x \\ y \end{pmatrix},
</math>
其中矩陣 <math>A</math> 為
:<math>
A = \sum_u \sum_v w(u,v) 
\begin{bmatrix}
I_x^2 & I_x I_y \\
I_x I_y & I_y^2 
\end{bmatrix}
=
\begin{bmatrix}
\langle I_x^2 \rangle & \langle I_x I_y \rangle\\
\langle I_x I_y \rangle & \langle I_y^2 \rangle
\end{bmatrix}
</math>

式子中的矩陣是Harris矩陣，而括號代表對所有的 <math>(u,v)</math> 取加權平均，

一個角(或者說是要點)可以被刻劃成該點 <math>(u,v)</math> 使得 <math>S(u,v)</math> 在不同的方向 <math>(x,y)</math> 之間有很大的[[變異數]]的點。
根據分析 <math>A</math> 的[[特徵值]]，以上的特性可以用下面的方式闡述：在角的點上，<math>A</math>應該要有兩個"大"的[[特徵值]]。

根據[[特徵值]]的大小，我們會有以下的推論：
#如果 <math>\lambda_1 \approx 0</math> 和 <math>\lambda_2 \approx 0</math> 則這個像素 <math>(u,v)</math> 只是一個普通的點。
#如果 <math>\lambda_1 \approx 0</math> 但 <math>\lambda_2</math> 為一個大的正數，則這個像素 <math>(u,v)</math> 位在邊上面。
#如果 <math> \lambda_1</math> 和 <math> \lambda_2</math> 都是大的正數，則這個像素 <math>(u,v)</math> 就是一個角點。

Harris 和 Stephens 注意到計算[[特徵值]]在運算量上面相當大，計算中需要使用到取平方根的操作，因此給出了另一個近似值 <math>M_c</math> ，其中 <math>\kappa</math> 是需要調整的重要參數。
:<math>
M_c = \lambda_1 \lambda_2 - \kappa \, (\lambda_1 + \lambda_2)^2
= \operatorname{det}(A) - \kappa \, \operatorname{trace}^2(A)
</math>
因此該演算法不需要真正的去做 <math>A</math> 的[[特徵分解]]，而只需要去估計 <math>A</math> 的[[行列式]]和[[跡]]。
Shi–Tomasi<ref name="shitomasi"/> 角檢測在假設一般圖像每個像素所給出的函數值通常是光滑(smooth)且穩定的(stable)，他直接去計算 <math>\min(\lambda_1, \lambda_2)</math> ，有時又稱該方法為 Kanade-Tomasi 角檢測。

而 <math>\kappa</math> 的值通常是由經驗決定，而通常在 0.04–0.15 的範圍裡是可解的。
另一種方法可以避開選擇 <math>\kappa</math> 的困擾，這個方法是使用 Noble's<ref name="noble"/> 角測度 <math>M_c'</math> ，而角測度是計算所有[[特徵值]]
的[[調和平均數]]
:<math>
M_c' = 2 \frac{\operatorname{det}(A)}{\operatorname{trace}(A) + \epsilon},
</math>
其中 <math>\epsilon</math> 是一個小的正常數。

而角的位置的[[共變異數矩陣]]即為<math> A^{-1} </math>，可以寫成
:<math>
\frac{1}{\langle I_x^2 \rangle \langle I_y^2 \rangle - \langle I_x I_y \rangle^2}
\begin{bmatrix}
\langle I_y^2 \rangle & -\langle I_x I_y \rangle\\
-\langle I_x I_y \rangle & \langle I_x^2 \rangle
\end{bmatrix}.
</math>

== Förstner 角檢測 ==
[[File:Corner detection using Foerstner Algorithm.png|thumb|使用 Förstner 演算法的例子]]
在某些情況，會希望更精確地去計算角的位置，為了得到近似值，Förstner<ref>{{cite journal|last=Förstner|first=W|author2=Gülch|title=A Fast Operator for Detection and Precise Location of Distinct Points, Corners and Centres of Circular Features|journal=ISPRS|year=1987|url=http://www.ipb.uni-bonn.de/fileadmin/publication/papers/1987/foerstner87.fast.pdf}}{{dead link|date=2017年10月 |bot=InternetArchiveBot }}</ref> 演算法可以解出閉集上的角附近範圍中的所有切線與最接近這些切線的點，該演算法依賴於在一個理想的角附近。

一個像素 <math>\mathbf{x'}</math> 的切線 <math>T_{\mathbf{x'}}(\mathbf{x})</math> 可以由數學式給出
:<math>
T_\mathbf{x'}(\mathbf x)=\nabla I(\mathbf{x'})^{\top}(\mathbf{x}-\mathbf{x'})=0
</math>
其中 <math>\nabla I(\mathbf{x'})=[I_{\mathbf{x}},I_{\mathbf{y}}]^{\top}</math> 是圖像 <math>I</math> 在 <math>\mathbf{x'}</math> 點的[[梯度]]向量。
而最靠近長方形範圍 <math>N</math> 中所有切線的點 <math>\mathbf{x}_{0}</math> 為
:<math>\mathbf{x}_{0}=\underset{\mathbf{x}\in \mathbb{R}^{2\times 1}}{\operatorname{argmin}}\int_{\mathbf{x'}\in N}T_{\mathbf{x'}}(\mathbf{x})^{2}d\mathbf{x'}</math>
<math>\mathbf{x}_{0}</math> 到切線 <math>T_{\mathbf{x'}}</math> 的距離依照[[梯度]]向量的大小來加權，因此若經過該點的切線有較大的[[梯度]]的話，在加權上就會占較高的比重。

嘗試著解 <math>\mathbf{x}_{0}</math> ：
:<math>
\begin{align}
\mathbf{x}_{0}&=\underset{\mathbf{x}\in \mathbb{R}^{2\times 1}}{\operatorname{argmin}} \int_{\mathbf{x'}\in N}(\nabla I(\mathbf{x'})^{\top}(\mathbf{x}-\mathbf{x'}))^{2}d\mathbf{x'}\\
&=\underset{\mathbf{x}\in \mathbb{R}^{2\times 1}}{\operatorname{argmin}}\int_{\mathbf{x'}\in N}(\mathbf{x}-\mathbf{x'})^{\top}\nabla I(\mathbf{x'})\nabla I(\mathbf{x'})^{\top}(\mathbf{x}-\mathbf{x'})d\mathbf{x'}\\
&=\underset{\mathbf{x}\in \mathbb{R}^{2\times 1}}{\operatorname{argmin}}\, (\mathbf{x}^{\top}A\mathbf{x}-2\mathbf{x}^{\top}\mathbf{b}+c)
\end{align}
</math>

<math>A\in\mathbb{R}^{2\times 2},\textbf{b}\in\mathbb{R}^{2\times 1},c\in\mathbb{R}</math> 分別為
:<math>
\begin{align}
A&=\int \nabla I(\mathbf{x'})\nabla I(\mathbf{x'})^{\top}d\mathbf{x'}\\
\mathbf{b}&=\int \nabla I(\mathbf{x'})\nabla I(\mathbf{x'})^{\top}\mathbf{x'}d\mathbf{x'}\\
c&=\int \mathbf{x'}^{\top}\nabla I(\mathbf{x'})\nabla I(\mathbf{x'})^{\top}\mathbf{x'}d\mathbf{x'}\\
\end{align}
</math>

要找出最小值可以經由計算式子對 <math>x</math> 的微分，並讓微分後的式子等於0來解<math>x</math>
:<math>
2A\mathbf{x}-2\mathbf{b}=0 \Rightarrow A\mathbf{x}=\mathbf{b}
</math>
注意到如果要能夠解上述等式， <math>A\in\mathbb{R}^{2\times 2}</math> 必須要是可逆的，或是說 <math>A\in\mathbb{R}^{2\times 2}</math> 必須要是滿[[秩]]的，而解可以寫成
:<math>x_{0}=A^{-1}\mathbf{b}</math>
只有在範圍 <math>N</math> 之中有角時才存在。

此外 Lindeberg<ref name="lindeberg94icip"/><ref name="lindeberg98"/> 給出一個方法去評估角的確定性，經由最小化誤差
:<math>\tilde{d}_{min} = \frac{c - b^T A^{-1} b}{\mbox{trace} A}</math>
而這對所有尺度都適用，因此這方法可以自動去適應圖片中不同梯度大小所造成的影響與誤差。

此外
*<math>c</math> 可以被視為最小平方誤差計算中的誤差，因此當 <math>c</math> 為0時，將沒有誤差存在。
*這個演算法可以用來找出環狀特徵的中心，只需將上述演算法中的[[梯度]]向量改成[[法線]]向量即可。

== 多尺度 Harris 算子 ==
Harris 算子中的微分矩陣 <math>A</math> 會牽涉到要計算圖像中的偏微分([[Image derivatives]]) <math>I_x, I_y</math>，而這可以用附近點的線性組合來做逼近，而計算線性組合時通常也會需要根據附近圖像值的大小來做縮放，因此需要兩個額外的縮放參數：(i)一個局部縮放參數主要用來讓圖像平滑一點 (ii)一個積分參數用來累積在微分操作中的非線性算子，作為圖像的修正項。

若以 <math>I</math> 代表原本圖形中的亮度，<math>L</math> 為一個將圖像 <math>I</math> 通過一個[[高斯濾波器]]讓圖像變模糊的結果。
:<math>g(x, y, t) = \frac {1}{2{\pi} t}e^{-(x^2+y^2)/2t}</math>
而參數 <math>t</math> 用來控制[[高斯濾波器]]的變異數
:<math>L(x, y, t)\ = g(x, y, t) * I(x, y)</math>
令 <math>L_x = \partial_x L</math> 和 <math>L_y = \partial_y L</math> 為 <math>L</math> 的偏導數，此外用一個高斯濾波器作為縮放大小，參數 <math>s</math> 可供調整。
則[[Structure tensor#The multi-scale structure tensor|''multi-scale second-moment matrix'']] <ref name="lindeberg94book"/><ref name="lindeberg08enc"/>  可以被定義為
:<math>
\mu(x, y; t, s) =
\int_{\xi = -\infty}^{\infty} \int_{\eta = -\infty}^{\infty}
\begin{bmatrix}
 L_x^2(x-\xi, y-\eta; t)                               & L_x(x-\xi, y-\eta; t) \, L_y(x-\xi, y-\eta; t) \\
L_x(x-\xi, y-\eta; t) \, L_y(x-\xi, y-\eta; t) & L_y^2(x-\xi, y-\eta; t) 
\end{bmatrix}
g(\xi, \eta; s) \, d\xi \, d\eta.
</math>
則我們也可以用前面類似的方法來計算 <math>\mu</math> 的特徵值，並且定義多尺度 Harris corner 測度為
:<math>M_c(x, y; t, s) = \operatorname{det}(\mu(x, y; t, s)) - \kappa \, \operatorname{trace}^2(\mu(x, y; t, s))</math>
注意到局部尺度參數 t 和積分尺度參數 s ，這兩個參數通常會有相對關係 <math>s = \gamma^2 t</math>，其中 <math>\gamma</math> 為一個參數通常介於 <math>[1, 2]</math> 之間。
因此我們可以計算多尺度 Harris corner 測度 <math>M_c(x, y; t, \gamma^2 t)</math> ，在給定的任何局部尺度 t 去做到多尺度角偵測。
一般實際應用上，多尺度角偵測通常會先做尺度選擇的步驟，可以參考正規化尺度拉普拉斯算子 <ref name="lindeberg98"/><ref name="lindeberg94book"/>。
:<math>\nabla^2_{norm} L(x, y; t)\ = t \nabla^2 L(x, y, t) = t (L_{xx}(x, y, t) + L_{yy}(x, y, t))</math>
常常在尺度選擇的部分用到，並且用來同時調整尺度以適應該角點。<ref name="schmid"/>
* 空間範圍內多尺度角測度 <math>M_c(x, y; t, \gamma^2 t)</math> 的最大值：
:<math>(\hat{x}, \hat{y}; t) = \operatorname{argmaxlocal}_{(x, y)} M_c(x, y; t, \gamma^2 t)</math>
* 將圖像通過一個高斯濾波器 <math>\nabla^2_{norm}(x, y, t)</math> (拉普拉斯算子<ref name="lindeberg98"/>)所得到的 <math>L</math> 的局部最大值或最小值：
:<math>\hat{t} = \operatorname{argmaxminlocal}_{t} \nabla^2_{norm}L(\hat{x}, \hat{y}; t)</math>

== 參考文獻 ==
=== 引用 ===
{{Reflist|2|refs =
<ref name="shitomasi">{{cite conference
|author=J. Shi and C. Tomasi
|title=Good Features to Track,
|publisher=Springer
|date=June 1994
|booktitle=9th IEEE Conference on Computer Vision and Pattern Recognition
|url=http://citeseer.ist.psu.edu/shi94good.html
|access-date=2015-07-03
|archive-date=2008-05-14
|archive-url=https://web.archive.org/web/20080514231042/http://citeseer.ist.psu.edu/shi94good.html
|dead-url=no
}}
<br />
{{cite journal
|author=C. Tomasi and T. Kanade
|title=Detection and Tracking of Point Features
|year=2004
|journal=Pattern Recognition
|url=http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V14-49D6WH0-1_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_version=1&_urlVersion=0&_userid=10&md5=cecb6ab80d45107f1cedb17aa4b211fb
|doi=10.1016/S0031-3203(03)00234-6
|volume=37
|pages=165–168
}}</ref>

<ref name="noble">{{cite thesis
|type=Ph.D. 
|author=A. Noble
|title=Descriptions of Image Surfaces
|year=1989
|publisher=Department of Engineering Science, Oxford University
|page=45
}}</ref>

<ref name="lindeberg94icip">{{cite conference
|author=T. Lindeberg
|title=Junction detection with automatic selection of detection scales and localization scales
|booktitle=Proc. 1st International Conference on Image Processing
|location=Austin, Texas
|volume=I
|pages=924–928
|year=1994
|url=http://www.csc.kth.se/~tony/abstracts/Lin94-ICIP.html
|access-date=2015-07-03
|archive-date=2017-08-25
|archive-url=https://web.archive.org/web/20170825092750/http://www.csc.kth.se/~tony/abstracts/Lin94-ICIP.html
|dead-url=no
}}</ref>

<ref name="lindeberg98">{{cite journal
|url = http://www.csc.kth.se/cvap/abstracts/cvap198.html
|author = Tony  Lindeberg
|title = Feature detection with automatic scale selection
|journal = International Journal of Computer Vision
|volume = 30
|number = 2
|pages = 77–116
|year = 1998
|accessdate = 2015-07-03
|archive-date = 2021-03-02
|archive-url = https://web.archive.org/web/20210302225346/http://www.csc.kth.se/cvap/abstracts/cvap198.html
|dead-url = no
}}</ref>

<ref name="lindeberg94book">{{cite book
|author=T. Lindeberg
|title=Scale-Space Theory in Computer Vision
|url=http://www.nada.kth.se/~tony/book.html
|publisher=Springer
|year=1994
|ISBN=0-7923-9418-6
|access-date=2015-07-03
|archive-date=2021-04-17
|archive-url=https://web.archive.org/web/20210417111801/https://www.nada.kth.se/~tony/book.html
|dead-url=no
}}</ref>

<ref name="lindeberg08enc">{{cite journal
|author = T. Lindeberg
|title = Wiley Encyclopedia of Computer Science and Engineering
|journal = Encyclopedia of Computer Science and Engineering (Benjamin Wah, ed), John Wiley and Sons
|volume = IV
|pages = 2495–2504
|year = 2008–2009
|doi = 10.1002/9780470050118.ecse609
|url = http://www.nada.kth.se/~tony/abstracts/Lin08-EncCompSci.html
|chapter = Scale-Space
|ISBN = 0-470-05011-X
|access-date = 2015-07-03
|archive-date = 2019-09-07
|archive-url = https://web.archive.org/web/20190907121454/http://www.nada.kth.se/~tony/abstracts/Lin08-EncCompSci.html
|dead-url = no
}}</ref>

<ref name="schmid">{{cite journal
|author=K. Mikolajczyk, K. and C. Schmid
|title=Scale and affine invariant interest point detectors
|year=2004
|journal=International Journal of Computer Vision
|volume=60
|issue=1
|pages=63–86
|url=http://www.robots.ox.ac.uk/~vgg/research/affine/det_eval_files/mikolajczyk_ijcv2004.pdf
|format=PDF
|doi=10.1023/B:VISI.0000027790.02288.f2
|access-date=2015-07-03
|archive-date=2018-01-07
|archive-url=https://web.archive.org/web/20180107201853/http://www.robots.ox.ac.uk/~vgg/research/affine/det_eval_files/mikolajczyk_ijcv2004.pdf
|dead-url=no
}}</ref>
}}

=== 来源 ===
* {{cite conference
|author = C. Harris and M. Stephens
|title = A combined edge and corner detector
|booktitle = Proceedings of the 4th Alvey Vision Conference
|pages = 147–151
|year = 1988
}}
* {{cite book
|author = C. Harris.
|chapter = Geometry from visual motion
|editor = A. Blake and A. Yuille
|title = Active Vision
|publisher = MIT Press, Cambridge MA
|year = 1992
}}
* {{cite journal
|author = H. Moravec
|title = Obstacle Avoindance and Navigation in the Real World by a Seeing Robot Rover
|year = 1980
|journal = Tech Report CMU-RI-TR-3 Carnegie-Mellon University, Robotics Institute
}}

[[Category:特征检测 (计算机视觉)]]