脊检测

脊检测（英語：Ridge detection）為試圖尋找相片中的脊的位置之方法。在數學及電腦視覺等領域中，一個雙變數光滑函數的脊（或是稱作為脊集合）是所有至少在一個維度中是局部最大值的點所形成的曲線的集合，就如同地理上山脊的概念。而一個${\displaystyle N}$變數函數的脊，是所有在${\displaystyle N-1}$個維度中是局部最大值的點所形成的曲線的集合。脊可以看作是局部最大值的延伸。相對的，一個函數的谷可以以類似的方式定義，只要以局部最小值取代脊定義中的局部最大值的部份。

脊集合與谷集合表現了一個函數直覺上的幾何資訊，因此可以提供一種對於函數特徵的簡潔呈現。圖像分析及電腦視覺為了獲得相片中物件延伸特性的資訊，利用了脊集合與谷集合的特性而有脊检测及谷检测。相關的應用像是在分水嶺演算法中被使用以進行圖像分割，或是利用相片中的脊與谷去計算物件可能的形狀等等。此種幾何資訊的表示方式，若只有進行單一尺度的計算，容易會受到雜訊的干擾。根據尺度空間理論，多重尺度的脊與谷可以透過相片經過高斯金字塔的預先處理獲得，藉此應該可以產生對於物件更穩定的描述。

二維相片中單一尺度的脊與谷的微分幾何定義

令 ${\displaystyle f(x,y)}$ 為一個二維函數，而${\displaystyle L}$ 為${\displaystyle f(x,y)}$ 的尺度空間表示，此種表示可以透過${\displaystyle f(x,y)}$ 與高斯函數的摺積獲得。

在單一尺度下，高斯函數中的${\displaystyle t}$ 為一定值。

${\displaystyle g(x,y,t)={\frac {1}{2\pi t}}e^{-(x^{2}+y^{2})/2t}}$ .

透過旋轉的方式，可以找到一組直角座標${\displaystyle (p,q)}$ 使得 ${\displaystyle L_{pq}=0}$ ，其中的方向導數運算子，

${\displaystyle \partial _{p}=\sin \beta \partial _{x}-\cos \beta \partial _{y},\partial _{q}=\cos \beta \partial _{x}+\sin \beta \partial _{y}}$ 

進一步帶入海森矩陣中。

${\displaystyle H={\begin{bmatrix}L_{xx}&L_{xy}\\L_{xy}&L_{yy}\end{bmatrix}}={\begin{bmatrix}\sin \beta &-\cos \beta \\\cos \beta &\sin \beta \end{bmatrix}}{\begin{bmatrix}L_{pp}&L_{pq}\\L_{pq}&L_{qq}\end{bmatrix}}{\begin{bmatrix}\sin \beta &\cos \beta \\-\cos \beta &\sin \beta \end{bmatrix}}}$ 

不難看出${\displaystyle L_{pp},L_{qq}}$ 即為海森矩陣的特徵值，而旋轉矩陣的旋轉角度可以由海森矩陣的特徵向量所決定。

${\displaystyle \cos \beta ={\sqrt {{\frac {1}{2}}\left(1+{\frac {L_{xx}-L_{yy}}{\sqrt {(L_{xx}-L_{yy})^{2}+4L_{xy}^{2}}}}\right)}}}$ ,${\displaystyle \sin \beta =\operatorname {sgn}(L_{xy}){\sqrt {{\frac {1}{2}}\left(1-{\frac {L_{xx}-L_{yy}}{\sqrt {(L_{xx}-L_{yy})^{2}+4L_{xy}^{2}}}}\right)}}}$ .

有了恰當的旋轉後，便可以正式的定義函數${\displaystyle f(x,y)}$  在單一尺度下的脊，脊包含所以符合以下條件的點。 ^[1]

${\displaystyle L_{p}=0,L_{pp}\leq 0,|L_{pp}|\geq |L_{qq}|.}$ 

相對應的谷，谷包含所有符合以下條件的點。

${\displaystyle L_{q}=0,L_{qq}\geq 0,|L_{qq}|\geq |L_{pp}|.}$ 

相似的，也可以將座標旋轉，使得新座標${\displaystyle (u,v)}$ 中，${\displaystyle v}$ 的方向平行相片的梯度，而${\displaystyle u}$ 的方向垂直相片的梯度。

${\displaystyle \partial _{u}=\sin \alpha \partial _{x}-\cos \alpha \partial _{y},\partial _{v}=\cos \alpha \partial _{x}+\sin \alpha \partial _{y}}$ 

此時的旋轉角度為，

${\displaystyle \cos \alpha ={\frac {L_{x}}{\sqrt {L_{x}^{2}+L_{y}^{2}}}},\sin \alpha ={\frac {L_{y}}{\sqrt {L_{x}^{2}+L_{y}^{2}}}}}$ 

以下的定義可以被證明與前述的是等價的^[2]

${\displaystyle L_{uv}=0,L_{uu}^{2}-L_{vv}^{2}\geq 0}$ 

其中

${\displaystyle L_{v}^{2}L_{uu}=L_{x}^{2}L_{yy}-2L_{x}L_{y}L_{xy}+L_{y}^{2}L_{xx},}$ 

${\displaystyle L_{v}^{2}L_{uv}=L_{x}L_{y}(L_{xx}-L_{yy})-(L_{x}^{2}-L_{y}^{2})L_{xy},}$ 

${\displaystyle L_{v}^{2}L_{vv}=L_{x}^{2}L_{xx}+2L_{x}L_{y}L_{xy}+L_{y}^{2}L_{yy}}$ 

由${\displaystyle L_{uu}}$ 的正負號決定一個點是脊或是谷，${\displaystyle L_{uu}<0}$ 是脊而${\displaystyle L_{uu}>0}$ 是谷.

計算二維相片在變化尺度下的脊

單一尺度脊的主要問題是對於雜訊非常敏感，實驗證實尺度的選擇需要特別的調整才能得到一組能夠反應相片中結構的脊。為了在缺乏過往經驗時處理這個問題，而有了尺度空間脊的概念，此時尺度大小這個變數被當作是脊定義的固有特性，尺度可以在尺度空間中變化。此種概念使得尺度可以被自動的調整到反應相片結構的大小，以下有多種方法皆是基於此。

令${\displaystyle R(x,y,t)}$ 為一個描述脊強度的函數（底下有詳細定義）。則對於一個二維相片，尺度空間脊包含所有符合以下條件的點，

${\displaystyle L_{p}=0,L_{pp}\leq 0,\partial _{t}(R)=0,\partial _{tt}(R)\leq 0,}$ 

其中 ${\displaystyle t}$  為尺度空間表示中的尺度. 相似的，尺度空間谷包含所有符合以下條件的點，

${\displaystyle L_{q}=0,L_{qq}\geq 0,\partial _{t}(R)=0,\partial _{tt}(R)\leq 0.}$ 

如此定義下，可以想像尺度空簡脊為三維空間中一些一維曲線的集合（原本相片的二維加上尺度空間一維），而最後呈現的脊便是這些曲線在相片平面上的投影。

當初Lindeberg (1996, 1998)^[3] 提出了尺度空間脊時，他考慮了三個描述脊強度的函數。

• 主曲率

${\displaystyle L_{pp,\gamma -norm}={\frac {t^{\gamma }}{2}}\left(L_{xx}+L_{yy}-{\sqrt {(L_{xx}-L_{yy})^{2}+4L_{xy}^{2}}}\right)}$ 

• 特徵值差的平方經${\displaystyle \gamma }$ -標準化後的平方

${\displaystyle N_{\gamma -norm}=\left(L_{pp,\gamma -norm}^{2}-L_{qq,\gamma -norm}^{2}\right)^{2}=t^{4\gamma }(L_{xx}+L_{yy})^{2}\left((L_{xx}-L_{yy})^{2}+4L_{xy}^{2}\right).}$ 

• 特徵值差經${\displaystyle \gamma }$ -標準化後的平方

${\displaystyle A_{\gamma -norm}=\left(L_{pp,\gamma -norm}-L_{qq,\gamma -norm}\right)^{2}=t^{2\gamma }\left((L_{xx}-L_{yy})^{2}+4L_{xy}^{2}\right).}$ 

${\displaystyle L_{pp,\gamma -norm}}$ 是一個通用性的描述函數，常被用在血管偵測及道路提取等應用中，而${\displaystyle A_{\gamma -norm}}$ 則被用在指紋的增強^[4]，即時手部追蹤及手勢辨識^[5]，以及利用局部影像統計偵測追蹤影像或影片中的人。^[6]

歷史

脊與谷第一次被使用在數位影像的領域中是在由Haralick於1983^[7]及Crowley於1984對於高斯金字塔的想法^[8][9] ，脊在醫學影像中的應用則有Pizer及其同事的深入研究^[10][11][12] 及他們所提出的M-reps。^[13] 脊检测因Lindeberg加入了${\displaystyle \gamma }$ -標準化導數及尺度空間脊等概念而有所提昇。這些概念之後由Steger等人使用在道路提取^[14][15] ，由Frangi等人使用在血管的分割^[16] 以及由Satos等人及Krissian等人使用在曲線及管狀結構的偵測中。^[17][18]

N維空間中脊與谷的定義

脊的概念，推廣了實數函數的局部最大值。一個在 ${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ 定義域中的點${\displaystyle \mathbf {x} _{0}}$ ，若存在一個距離${\displaystyle \delta >0}$ 使得所有在這個距離內的都符合${\displaystyle f(\mathbf {x} )<f(\mathbf {x} _{0})}$ ，則點${\displaystyle \mathbf {x} _{0}}$ 是一個局部最大值。

稍微放寬一下這個條件，若所有在${\displaystyle \mathbf {x} _{0}}$ 的附近的點${\displaystyle \mathbf {x} }$ 中${\displaystyle n-1}$ 維的子集合，皆符合${\displaystyle f(\mathbf {x} )<f(\mathbf {x} _{0})}$ ，則${\displaystyle \mathbf {x} _{0}}$ 便是脊上的一個點。這樣的放寬，給予了脊一個維度的自由，也就是說脊會是一個一維的曲線。同樣的概念套用到局部最小值上，可以得到一維的谷曲線。

以下的定義是根據Eberly的著作^[19]，可以被當作是之前的脊的定義的推廣。令${\displaystyle U\subset \mathbb {R} ^{n}}$ 為一個開放集合，且${\displaystyle f:U\rightarrow \mathbb {R} }$ 是一個光滑函數。令${\displaystyle \mathbf {x} _{0}\in U}$ 。令${\displaystyle \nabla _{\mathbf {x} _{0}}f}$ 為${\displaystyle f}$ 在點${\displaystyle \mathbf {x} _{0}}$ 的梯度。令${\displaystyle H_{\mathbf {x} _{0}}(f)}$ 為函數${\displaystyle f}$ 在點${\displaystyle \mathbf {x} _{0}}$ 的${\displaystyle n\times n}$ 海森矩陣。令${\displaystyle \lambda _{1}\leq \lambda _{2}\leq \cdots \leq \lambda _{n}}$ 為${\displaystyle n}$ 個${\displaystyle H_{\mathbf {x} _{0}}(f)}$ 的排序好的特徵值，並令${\displaystyle \mathbf {e} _{i}}$ 為對應到${\displaystyle \lambda _{i}}$ 的單位特徵向量。(在此，假設所有特徵值是相異的)

點${\displaystyle \mathbf {x} _{0}}$ 在一維的脊上若:

1. ${\displaystyle \lambda _{n-1}<0}$ 且
2. ${\displaystyle \nabla _{\mathbf {x} _{0}}f\cdot \mathbf {e} _{i}=0}$  for ${\displaystyle i=1,2,\ldots ,n-1}$ .

這精確地限制了${\displaystyle f}$ 在特定的${\displaystyle n-1}$ 維中在點 ${\displaystyle \mathbf {x} _{0}}$ 有局部最大值。

這樣的定義很自然的可以被推廣到成k維的脊，一個點${\displaystyle \mathbf {x} _{0}}$ 在k維脊上若

1. ${\displaystyle \lambda _{n-k}<0}$ 且
2. ${\displaystyle \nabla _{\mathbf {x} _{0}}f\cdot \mathbf {e} _{i}=0}$  for ${\displaystyle i=1,2,\ldots ,n-k}$ .

最大尺度脊

以下的定義可以被追溯到Fritsch^[20]，當初他對如何從二維灰階相片中提取幾何資訊十分感興趣，他使用了medialness濾鏡處理相片，得到了一種類似各點到邊緣距離在尺度空間的資料，而這種資料的脊若是再疊加回原本的相片上，與原本相片的形狀骨骼（如Blum的中軸）十分相似。

最大尺度脊定義在一個三維的函數上，其中二維是相片平面，一維是尺度空間。其中我們想要以下的條件為真，若${\displaystyle (\mathbf {x} ,\sigma )}$ 是一個在最大尺度脊上的點，則函數在這個點上的值在尺度軸上是極大值。令${\displaystyle f(\mathbf {x} ,\sigma )}$ 為一個光滑可微分的函數於${\displaystyle U\subset \mathbb {R} ^{2}\times \mathbb {R} _{+}}$ 。則${\displaystyle (\mathbf {x} ,\sigma )}$ 是在最大尺度脊上的點若且唯若

1. ${\displaystyle {\frac {\partial f}{\partial \sigma }}=0}$  and ${\displaystyle {\frac {\partial ^{2}f}{\partial \sigma ^{2}}}<0}$ , and
2. ${\displaystyle \nabla f\cdot \mathbf {e} _{1}=0}$  and ${\displaystyle \mathbf {e} _{1}^{t}H(f)\mathbf {e} _{1}<0}$ .

參見

• 尺度空間
• 特征检测
• 边缘检测
• 興趣點检测
• 斑點检测
• 電腦視覺

參考資料

1. T. Lindeberg. Scale-space. Encyclopedia of Computer Science and Engineering (Benjamin Wah, ed), John Wiley and Sons. 2008/2009, IV: 2495–2504 [2015-07-01]. doi:10.1002/9780470050118.ecse609. （原始内容于2019-09-07）.  请检查|date=中的日期值 (帮助)
2. Lindeberg, T. Scale-space theory: A basic tool for analysing structures at different scales. J. of Applied Statistics. 1994, 21 (2): 224–270 [2015-07-01]. doi:10.1080/757582976. （原始内容于2019-09-07）. 
3. Lindeberg, T. Edge detection and ridge detection with automatic scale selection. International Journal of Computer Vision. 1998, 30 (2): 117–154 [2015-07-01]. doi:10.1023/A:1008097225773. （原始内容于2006-07-09）.  Earlier version presented at IEEE Conference on Pattern Recognition and Computer Vision, CVPR'96, San Francisco, California, pages 465–470, june 1996
4. Almansa, A., Lindeberg, T. Fingerprint Enhancement by Shape Adaptation of Scale-Space Operators with Automatic Scale-Selection. IEEE Transactions on Image Processing. 2000, 9 (12): 2027–42 [2015-07-01]. PMID 18262941. doi:10.1109/83.887971. （原始内容于2019-09-07）. 
5. L. Bretzner, I. Laptev and T. Lindeberg: Hand Gesture Recognition using Multi-Scale Colour Features, Hierarchical Models and Particle Filtering, Proc. IEEE Conference on Face and Gesture 2002, Washington DC, 423–428.. [2015-07-01]. （原始内容于2019-07-22）. 
6. Sidenbladh, H., Black, M. Learning the statistics of people in images and video (PDF). International Journal of Computer Vision. 2003, 54 (1–2): 183–209 [2015-07-01]. （原始内容 (PDF)于2017-07-05）. 
7. Haralick, R. Ridges and Valleys on Digital Images. Computer Vision, Graphics, and Image Processing. April 1983, 22 (10): 28–38. doi:10.1016/0734-189X(83)90094-4. 
8. Crowley, J.L., Parker, A.C. A Representation for Shape Based on Peaks and Ridges in the Difference of Low Pass Transform (PDF). IEEE Trans Pattern Anal Mach Intell. March 1984, 6 (2): 156–170 [2015-07-01]. PMID 21869180. doi:10.1109/TPAMI.1984.4767500. （原始内容 (PDF)于2016-03-03）. 
9. Crowley, J.L., Sanderson, A. Multiple Resolution Representation and Probabilistic Matching of 2-D Gray-Scale Shape (PDF). IEEE Trans Pattern Anal Mach Intell. January 1987, 9 (1): 113–121 [2015-07-01]. doi:10.1109/TPAMI.1987.4767876. （原始内容 (PDF)于2017-08-30）. 
10. Gauch, J.M., Pizer, S.M. Multiresolution Analysis of Ridges and Valleys in Grey-Scale Images. IEEE Trans Pattern Anal Mach Intell. June 1993, 15 (6): 635–646. doi:10.1109/34.216734. 
11. Eberly D., Gardner R., Morse B., Pizer S., Scharlach C. Ridges for image analysis. Journal of Mathematical Imaging and Vision. December 1994, 4 (4): 353–373. doi:10.1007/BF01262402. 
12. Pizer, Stephen M., Eberly, David, Fritsch, Daniel S. Zoom-invariant vision of figural shape: the mathematics of cores. Computer Vision and Image Understanding. January 1998, 69 (1): 55–71. doi:10.1006/cviu.1997.0563. 
13. S. Pizer, S. Joshi, T. Fletcher, M. Styner, G. Tracton, J. Chen (2001) "Segmentation of Single-Figure Objects by Deformable M-reps", Proceedings of the 4th International Conference on Medical Image Computing and Computer-Assisted Intervention, Springer Lecture Notes In Computer Science; Vol. 2208, pp. 862–871. [2015-07-01]. （原始内容于2007-03-10）. 
14. Steger C. An unbiased detector of curvilinear structures. IEEE Trans Pattern Anal Mach Intell. 1998, 20 (2): 113–125 [2022-03-26]. doi:10.1109/34.659930. （原始内容于2012-02-05）. 
15. Laptev I., Mayer H., Lindeberg T., Eckstein W., Steger C., Baumgartner A. Automatic extraction of roads from aerial images based on scale-space and snakes (PDF). Machine Vision and Applications. 2000, 12 (1): 23 [2015-07-01]. doi:10.1007/s001380050121. （原始内容 (PDF)于2021-04-15）. 
16. Frangi AF, Niessen WJ, Hoogeveen RM, van Walsum T, Viergever MA. Model-based quantitation of 3-D magnetic resonance angiographic images. IEEE Trans Med Imaging. October 1999, 18 (10): 946–56. PMID 10628954. doi:10.1109/42.811279. 
17. Sato Y, Nakajima S, Shiraga N, Atsumi H, Yoshida S; et al. Three-dimensional multi-scale line filter for segmentation and visualization of curvilinear structures in medical images (PDF). Medical Image Analysis. 1998, 2 (2): 143–168 [2015-07-01]. doi:10.1016/s1361-8415(98)80009-1. （原始内容 (PDF)于2018-03-24）.  引文格式1维护：显式使用等标签 (link)
18. Krissian K., Malandain G., Ayache N., Vaillan R., Trousset Y. Model-based detection of tubular structures in 3D images. Computer Vision and Image Understanding. 2000, 80 (2): 130–171. doi:10.1006/cviu.2000.0866. 
19. Eberly, D. Ridges in Image and Data Analysis. Kluwer. 1996. ISBN 0-7923-4268-2. 
20. Fritsch, DS, Eberly,D., Pizer, SM, and McAuliffe, MJ. "Stimulated cores and their applications in medical imaging." Information Processing in Medical Imaging, Y. Bizais, C Barillot, R DiPaola, eds., Kluwer Series in Computational Imaging and Vision, pp. 365–368.