脊检测

脊检测（Ridge detection）为试图寻找相片中的脊的位置之方法。在数学及电脑视觉等领域中，一个双变数光滑函数的脊（或是称作为脊集合）是所有至少在一个维度中是局部最大值的点所形成的曲线的集合，就如同地理上山脊的概念。而一个$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 = \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}$$

不难看出$L_{pp}, L_{qq}$即为海森矩阵的特征值，而旋转矩阵的旋转角度可以由海森矩阵的特征向量所决定。

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

有了恰当的旋转后，便可以正式的定义函数$f(x, y)$ 在单一尺度下的脊，脊包含所以符合以下条件的点。

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

相对应的谷，谷包含所有符合以下条件的点。

$$L_{q} = 0, L_{qq} \geq 0, |L_{qq}| \geq |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 \geq 0$$

其中

$$L_v^2 L_{uu} = L_x^2 L_{yy} - 2 L_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} + 2 L_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} \leq 0, \partial_t(R) = 0, \partial_{tt}(R) \leq 0,$$

其中 $t$ 为尺度空间表示中的尺度. 相似的，尺度空间谷包含所有符合以下条件的点。

$$L_{q} = 0, L_{qq} \geq 0, \partial_t(R) = 0, \partial_{tt}(R) \leq 0.$$

如此定义下，可以想像尺度空简脊为三维空间中一些一维曲线的集合（原本相片的二维加上尺度空间一维），而最后呈现的脊便是这些曲线在相片平面上的投影。

当初Lindeberg (1996, 1998) 提出了尺度空间脊时，他考虑了三个描述脊强度的函数。

- 主曲率

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

- 特征值差的平方经$\gamma$-标准化后的平方

$$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 + 4 L_{xy}^2 \right).$$

- 特征值差经$\gamma$-标准化后的平方

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

$L_{pp, \gamma-norm}$是一个通用性的描述函数，常被用在血管侦测及道路提取等应用中，而$A_{\gamma-norm}$则被用在指纹的增强，即时手部追踪及手势辨识，以及利用局部影像统计侦测追踪影像或影片中的人。

## 历史

脊与谷第一次被使用在数位影像的领域中是在由Haralick于1983及Crowley于1984对于高斯金字塔的想法，脊在医学影像中的应用则有Pizer及其同事的深入研究 及他们所提出的M-reps。脊检测因Lindeberg加入了$\gamma$-标准化导数及尺度空间脊等概念而有所提升。这些概念之后由Steger等人使用在道路提取，由Frangi等人使用在血管的分割 以及由Satos等人及Krissian等人使用在曲线及管状结构的侦测中。

## N维空间中脊与谷的定义

脊的概念，推广了实数函数的局部最大值。一个在 $f:\mathbb{R}^n \rightarrow \mathbb{R}$定义域中的点$\mathbf{x}_0$，若存在一个距离$\delta>0$使得所有在这个距离内的都符合$f(\mathbf{x}) < f(\mathbf{x}_0)$，则点$\mathbf{x}_0$是一个局部最大值。

稍微放宽一下这个条件，若所有在$\mathbf{x}_0$的附近的点$\mathbf{x}$中$n-1$维的子集合，皆符合$f(\mathbf{x}) < f(\mathbf{x}_0)$，则$\mathbf{x}_0$便是脊上的一个点。这样的放宽，给予了脊一个维度的自由，也就是说脊会是一个一维的曲线。同样的概念套用到局部最小值上，可以得到一维的谷曲线。

以下的定义是根据Eberly的著作，可以被当作是之前的脊的定义的推广。令$U \subset \mathbb{R}^n$为一个开放集合，且$f:U \rightarrow \mathbb{R}$是一个光滑函数。令$\mathbf{x}_0 \in U$。令$\nabla_{\mathbf{x}_0}f$为$f$在点$\mathbf{x}_0$的梯度。令$H_{\mathbf{x}_0}(f)$为函数$f$在点$\mathbf{x}_0$的$n \times n$海森矩阵。令$\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$为$n$个$H_{\mathbf{x}_0}(f)$的排序好的特征值，并令$\mathbf{e}_i$为对应到$\lambda_i$的单位特征向量。(在此，假设所有特征值是相异的)

点$\mathbf{x}_0$在一维的脊上若:

- $\lambda_{n-1}<0$且
- $\nabla_{\mathbf{x}_0} f \cdot \mathbf{e}_i=0$ for $i=1, 2, \ldots, n-1$.

这精确地限制了$f$在特定的$n-1$维中在点 $\mathbf{x}_0$有局部最大值。

这样的定义很自然的可以被推广到成k维的脊，一个点$\mathbf{x}_0$在k维脊上若

- $\lambda_{n-k}<0$且
- $\nabla_{\mathbf{x}_0} f \cdot \mathbf{e}_i=0$ for $i=1, 2, \ldots, n-k$.

## 最大尺度脊

以下的定义可以被追溯到Fritsch，当初他对如何从二维灰阶相片中提取几何资讯十分感兴趣，他使用了medialness滤镜处理相片，得到了一种类似各点到边缘距离在尺度空间的资料，而这种资料的脊若是再叠加回原本的相片上，与原本相片的形状骨骼（如Blum的中轴）十分相似。

最大尺度脊定义在一个三维的函数上，其中二维是相片平面，一维是尺度空间。其中我们想要以下的条件为真，若$(\mathbf{x},\sigma)$是一个在最大尺度脊上的点，则函数在这个点上的值在尺度轴上是极大值。令$f(\mathbf{x},\sigma)$为一个光滑可微分的函数于$U \subset \mathbb{R}^2 \times \mathbb{R}_{+}$。则$(\mathbf{x},\sigma)$是在最大尺度脊上的点当且仅当

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