脊检测

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

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

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

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

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

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

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

${\partial }_p=\sin \beta {\partial }_x-\cos \beta {\partial }_y,{\partial }_q=\cos \beta {\partial }_x+\sin \beta {\partial }_y$

進一步帶入海森矩陣中。

$H=\left[\begin{array}{cc}{L}_{xx}& L_{xy}\\ L_{xy}& L_{yy}\end{array}\right]=\left[\begin{array}{cc}\sin \beta & -\cos \beta \\ \cos \beta & \sin \beta \end{array}\right]\left[\begin{array}{cc}{L}_{pp}& L_{pq}\\ L_{pq}& L_{qq}\end{array}\right]\left[\begin{array}{cc}\sin \beta & \cos \beta \\ -\cos \beta & \sin \beta \end{array}\right]$

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

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

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

$L_p=0,L_{pp}\le 0,|L_{pp}|\ge |L_{qq}|.$

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

$L_q=0,L_{qq}\ge 0,|L_{qq}|\ge |L_{pp}|.$

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

${\partial }_u=\sin \alpha {\partial }_x-\cos \alpha {\partial }_y,{\partial }_v=\cos \alpha {\partial }_x+\sin \alpha {\partial }_y$

此時的旋轉角度為，

$\cos \alpha =\frac{L_x}{\sqrt{L_x^2+L_y^2}},\sin \alpha =\frac{L_y}{\sqrt{L_x^2+L_y^2}}$

以下的定義可以被證明與前述的是等價的

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

其中

$L_v^2{L}_{uu}=L_x^2{L}_{yy}-2L_x{L}_y{L}_{xy}+L_y^2{L}_{xx},$

$L_v^2{L}_{uv}=L_x{L}_y(L_{xx}-L_{yy})-(L_x^2-L_y^2)L_{xy},$

$L_v^2{L}_{vv}=L_x^2{L}_{xx}+2L_x{L}_y{L}_{xy}+L_y^2{L}_{yy}$

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

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

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

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

$L_p=0,L_{pp}\le 0,{\partial }_t(R)=0,{\partial }_{tt}(R)\le 0,$

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

$L_q=0,L_{qq}\ge 0,{\partial }_t(R)=0,{\partial }_{tt}(R)\le 0.$

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

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

• 主曲率

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

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

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

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

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

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

歷史

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

N維空間中脊與谷的定義

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

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

以下的定義是根據Eberly的著作，可以被當作是之前的脊的定義的推廣。令$U\subset {ℝ}^n$為一個開放集合，且$f:U\to ℝ$是一個光滑函數。令${𝐱}_0\in U$。令${\mathrm{\nabla }}_{{𝐱}_0}f$為$f$在點${𝐱}_0$的梯度。令$H_{{𝐱}_0}(f)$為函數$f$在點${𝐱}_0$的$n\times n$海森矩陣。令${\lambda }_1\le {\lambda }_2\le \cdots \le {\lambda }_n$為$n$個$H_{{𝐱}_0}(f)$的排序好的特徵值，並令${𝐞}_i$為對應到${\lambda }_i$的單位特徵向量。(在此，假設所有特徵值是相異的)

點${𝐱}_0$在一維的脊上若:

1. ${\lambda }_{n-1}<0$且
2. ${\mathrm{\nabla }}_{{𝐱}_0}f\cdot {𝐞}_i=0$ for $i=1,2,\dots ,n-1$.

這精確地限制了$f$在特定的$n-1$維中在點 ${𝐱}_0$有局部最大值。

這樣的定義很自然的可以被推廣到成k維的脊，一個點${𝐱}_0$在k維脊上若

1. ${\lambda }_{n-k}<0$且
2. ${\mathrm{\nabla }}_{{𝐱}_0}f\cdot {𝐞}_i=0$ for $i=1,2,\dots ,n-k$.

最大尺度脊

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

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

1. $\frac{\partial f}{\partial \sigma }=0$ and $\frac{{\partial }^{2}f}{\partial {\sigma }^2}<0$, and
2. $\mathrm{\nabla }f\cdot {𝐞}_1=0$ and ${𝐞}_1^{t}H(f){𝐞}_1<0$.

參見

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