Ridge detection

In image processing, ridge detection is the attempt, via software, to locate ridges in an image, defined as curves whose points are local maxima of the function, akin to geographical ridges.

For a function of N variables, its ridges are a set of curves whose points are local maxima in N − 1 dimensions. In this respect, the notion of ridge points extends the concept of a local maximum. Correspondingly, the notion of valleys for a function can be defined by replacing the condition of a local maximum with the condition of a local minimum. The union of ridge sets and valley sets, together with a related set of points called the connector set, form a connected set of curves that partition, intersect, or meet at the critical points of the function. This union of sets together is called the function's relative critical set.^[1][2]

Ridge sets, valley sets, and relative critical sets represent important geometric information intrinsic to a function. In a way, they provide a compact representation of important features of the function, but the extent to which they can be used to determine global features of the function is an open question. The primary motivation for the creation of ridge detection and valley detection procedures has come from image analysis and computer vision and is to capture the interior of elongated objects in the image domain. Ridge-related representations in terms of watersheds have been used for image segmentation. There have also been attempts to capture the shapes of objects by graph-based representations that reflect ridges, valleys and critical points in the image domain. Such representations may, however, be highly noise sensitive if computed at a single scale only. Because scale-space theoretic computations involve convolution with the Gaussian (smoothing) kernel, it has been hoped that use of multi-scale ridges, valleys and critical points in the context of scale space theory should allow for more a robust representation of objects (or shapes) in the image.

In this respect, ridges and valleys can be seen as a complement to natural interest points or local extremal points. With appropriately defined concepts, ridges and valleys in the intensity landscape (or in some other representation derived from the intensity landscape) may form a scale invariantskeleton for organizing spatial constraints on local appearance, with a number of qualitative similarities to the way the Blum's medial axis transform provides a shape skeleton for binary images. In typical applications, ridge and valley descriptors are often used for detecting roads in aerial images and for detecting blood vessels in retinal images or three-dimensional magnetic resonance images.

Let ${\displaystyle f(x,y)}$ denote a two-dimensional function, and let ${\displaystyle L}$ be the scale-space representation of ${\displaystyle f(x,y)}$ obtained by convolving ${\displaystyle f(x,y)}$ with a Gaussian function

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

Furthermore, let ${\displaystyle L_{pp}}$ and ${\displaystyle L_{qq}}$ denote the eigenvalues of the Hessian matrix

${\displaystyle H={\begin{bmatrix}L_{xx}&L_{xy}\\L_{xy}&L_{yy}\end{bmatrix}}}$

of the scale-space representation${\displaystyle L}$ with a coordinate transformation (a rotation) applied to local directional derivative operators,

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

where p and q are coordinates of the rotated coordinate system.

It can be shown that the mixed derivative ${\displaystyle L_{pq}}$ in the transformed coordinate system is zero if we choose

${\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)}}}$.

Then, a formal differential geometric definition of the ridges of ${\displaystyle f(x,y)}$ at a fixed scale ${\displaystyle t}$ can be expressed as the set of points that satisfy ^[3]

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

Correspondingly, the valleys of ${\displaystyle f(x,y)}$ at scale ${\displaystyle t}$ are the set of points

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

In terms of a ${\displaystyle (u,v)}$ coordinate system with the ${\displaystyle v}$ direction parallel to the image gradient

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

where

${\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}}}}}$

it can be shown that this ridge and valley definition can instead be equivalently^[4] written as

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

where

${\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}}$

and the sign of ${\displaystyle L_{uu}}$ determines the polarity; ${\displaystyle L_{uu}<0}$ for ridges and ${\displaystyle L_{uu}>0}$ for valleys.

Un problema principal de la definición de cresta de escala fija presentada anteriormente es su alta sensibilidad a la elección del nivel de escala. Los experimentos demuestran que el parámetro de escala del núcleo de pre-suavizado gaussiano debe ajustarse cuidadosamente al ancho de la estructura de cresta en el dominio de la imagen, para que el detector de cresta produzca una curva conectada que refleje las estructuras subyacentes de la imagen. Para abordar este problema en ausencia de información previa, se ha introducido el concepto de crestas en el espacio de escalas , que trata el parámetro de escala como una propiedad inherente de la definición de cresta y permite que los niveles de escala varíen a lo largo de una cresta en dicho espacio. Además, el concepto de cresta en el espacio de escalas también permite ajustar automáticamente el parámetro de escala al ancho de las estructuras de cresta en el dominio de la imagen, como consecuencia de una definición bien establecida. En la literatura, se han propuesto diversos enfoques basados ​​en esta idea.

Dejar${\displaystyle R(x,y,t)}$denota una medida de la fuerza de la cresta (que se especificará más adelante). Entonces, para una imagen bidimensional, una cresta en el espacio de escalas es el conjunto de puntos que satisfacen

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

dónde${\displaystyle t}$es el parámetro de escala en la representación del espacio de escalas . De manera similar, un valle del espacio de escalas es el conjunto de puntos que satisfacen

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

Una consecuencia inmediata de esta definición es que, para una imagen bidimensional, el concepto de crestas en el espacio de escalas define un conjunto de curvas unidimensionales en el espacio de escalas tridimensional, donde el parámetro de escala puede variar a lo largo de la cresta (o el valle) del espacio de escalas. El descriptor de cresta en el dominio de la imagen será entonces una proyección de esta curva tridimensional en el plano bidimensional de la imagen, donde la información de escala del atributo en cada punto de la cresta puede utilizarse como una estimación natural del ancho de la estructura de la cresta en el dominio de la imagen en una vecindad de ese punto.

En la literatura se han propuesto diversas medidas de resistencia de la cresta. Cuando Lindeberg (1996, 1998) ^{[ 5 ]} acuñó el término cresta de espacio de escala, consideró tres medidas de resistencia de la cresta:

• La curvatura principal principal

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

expresado en términos de${\displaystyle \gamma }$-derivadas normalizadas con

${\displaystyle \partial _{\xi }=t^{\gamma /2}\partial _{x},\partial _{\eta }=t^{\gamma /2}\partial _{y}}$.

• El cuadrado de la${\displaystyle \gamma }$-diferencia de valor propio al cuadrado normalizada

${\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).}$

• El cuadrado de la${\displaystyle \gamma }$-diferencia de valores propios normalizada

${\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).}$

La noción de${\displaystyle \gamma }$Las derivadas normalizadas son esenciales aquí, ya que permiten calibrar correctamente los algoritmos de detección de crestas y valles. Al requerir que para una cresta gaussiana unidimensional incrustada en dos (o tres) dimensiones la escala de detección sea igual al ancho de la estructura de la cresta cuando se mide en unidades de longitud (un requisito de coincidencia entre el tamaño del filtro de detección y la estructura de la imagen a la que responde), se deduce que se debe elegir${\displaystyle \gamma =3/4}$De estas tres medidas de resistencia de la cresta, la primera entidad${\displaystyle L_{pp,\gamma -norm}}$es una medida de resistencia de cresta de propósito general con muchas aplicaciones, como la detección de vasos sanguíneos y la extracción de carreteras. Sin embargo, la entidad${\displaystyle A_{\gamma -norm}}$Se ha utilizado en aplicaciones como mejora de huellas dactilares, ^{[ 6 ]} seguimiento de manos en tiempo real y reconocimiento de gestos ^{[ 7 ]} así como para modelar estadísticas de imágenes locales para detectar y rastrear personas en imágenes y video. ^{[ 8 ]}

También existen otras definiciones de cresta estrechamente relacionadas que utilizan derivadas normalizadas con la suposición implícita de${\displaystyle \gamma =1}$. ^{[ 9 ]} Desarrolle estos enfoques con mayor detalle. Al detectar crestas con${\displaystyle \gamma =1}$Sin embargo, la escala de detección será el doble de grande que para${\displaystyle \gamma =3/4}$, lo que resulta en mayores distorsiones de la forma y una menor capacidad para capturar crestas y valles con estructuras de imagen cercanas que interfieren en el dominio de la imagen.

La noción de crestas y valles en imágenes digitales fue introducida por Haralick en 1983 ^{[ 10 ]} y por Crowley en relación con las pirámides de diferencia de gaussianas en 1984. ^{[ 11 ] [ 12 ]} La aplicación de descriptores de crestas al análisis de imágenes médicas ha sido estudiada extensamente por Pizer y sus colaboradores ^{[ 13 ] [ 14 ] [ 15 ]} dando como resultado su noción de M-reps. ^{[ 16 ]} La detección de crestas también ha sido impulsada por Lindeberg con la introducción de${\displaystyle \gamma }$-derivadas normalizadas y crestas de espacio de escala definidas a partir de la maximización local de la curvatura principal principal apropiadamente normalizada de la matriz hessiana (u otras medidas de fuerza de cresta) sobre el espacio y sobre la escala. Estas nociones se han desarrollado posteriormente con aplicación a la extracción de carreteras por Steger et al. ^{[ 17 ] [ 18 ]} y a la segmentación de vasos sanguíneos por Frangi et al. ^{[ 19 ]} así como a la detección de estructuras curvilíneas y tubulares por Sato et al. ^{[ 20 ]} y Krissian et al. ^{[ 21 ]} Koenderink y van Doorn han presentado una revisión de varias de las definiciones clásicas de cresta a una escala fija, incluyendo relaciones entre ellas. ^{[ 22 ]} Kirbas y Quek han presentado una revisión de técnicas de extracción de vasos. ^{[ 23 ]}

En su sentido más amplio, la noción de cresta generaliza la idea de un máximo local de una función de valor real. Un punto${\displaystyle \mathbf {x} _{0}}$en el dominio de una función${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$es un máximo local de la función si hay una distancia${\displaystyle \delta >0}$con la propiedad que si${\displaystyle \mathbf {x} }$está dentro${\displaystyle \delta }$unidades de${\displaystyle \mathbf {x} _{0}}$, entonces${\displaystyle f(\mathbf {x} )<f(\mathbf {x} _{0})}$Es bien sabido que los puntos críticos, de los cuales los máximos locales son solo un tipo, son puntos aislados en el dominio de una función, salvo en las situaciones más inusuales ( es decir , los casos no genéricos).

Considere relajar la condición que${\displaystyle f(\mathbf {x} )<f(\mathbf {x} _{0})}$para${\displaystyle \mathbf {x} }$en todo un vecindario de${\displaystyle \mathbf {x} _{0}}$ligeramente para requerir solo que esta retención en un${\displaystyle n-1}$subconjunto dimensional. Presumiblemente, esta relajación permite que el conjunto de puntos que satisfacen los criterios, al que llamaremos cresta, tenga un solo grado de libertad, al menos en el caso genérico. Esto significa que el conjunto de puntos de la cresta formará un lugar geométrico unidimensional, o una curva de cresta. Nótese que lo anterior puede modificarse para generalizar la idea a mínimos locales y dar como resultado lo que podríamos llamar curvas de valle unidimensionales.

La siguiente definición de cresta sigue el libro de Eberly ^{[ 24 ]} y puede considerarse una generalización de algunas de las definiciones de cresta mencionadas anteriormente. Sea${\displaystyle U\subset \mathbb {R} ^{n}}$ser un conjunto abierto, y${\displaystyle f:U\rightarrow \mathbb {R} }$que sea suave. Deja${\displaystyle \mathbf {x} _{0}\in U}$. Dejar${\displaystyle \nabla _{\mathbf {x} _{0}}f}$ser el gradiente de${\displaystyle f}$en${\displaystyle \mathbf {x} _{0}}$y dejar${\displaystyle H_{\mathbf {x} _{0}}(f)}$ser el${\displaystyle n\times n}$Matriz hessiana de${\displaystyle f}$en${\displaystyle \mathbf {x} _{0}}$. Dejar ${\displaystyle \lambda _{1}\leq \lambda _{2}\leq \cdots \leq \lambda _{n}}$ser el${\displaystyle n}$valores propios ordenados de${\displaystyle H_{\mathbf {x} _{0}}(f)}$y dejar${\displaystyle \mathbf {e} _{i}}$sea ​​un vector propio unitario en el espacio propio para${\displaystyle \lambda _{i}}$(Para ello, conviene suponer que todos los valores propios son distintos).

El punto${\displaystyle \mathbf {x} _{0}}$es un punto en la cresta unidimensional de${\displaystyle f}$si se cumplen las siguientes condiciones:

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

Esto hace preciso el concepto de que${\displaystyle f}$restringido a este particular${\displaystyle n-1}$El subespacio de dimensión tiene un máximo local en${\displaystyle \mathbf {x} _{0}}$.

Esta definición se generaliza naturalmente a la cresta k -dimensional de la siguiente manera: el punto${\displaystyle \mathbf {x} _{0}}$es un punto en la cresta k -dimensional de${\displaystyle f}$si se cumplen las siguientes condiciones:

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

En muchos sentidos, estas definiciones generalizan naturalmente la de un máximo local de una función. Las propiedades de las crestas de convexidad máxima fueron fundamentadas matemáticamente por Damon ^{[ 1 ]} y Miller ^{[ 2 ] . Sus propiedades en familias de un parámetro fueron establecidas por Keller [ 25 ]} .

La siguiente definición se remonta a Fritsch ^{[ 26 ]} , quien estaba interesado en extraer información geométrica sobre figuras en imágenes bidimensionales en escala de grises. Fritsch filtró su imagen con un filtro de "medialidad" que le proporcionó información análoga a los datos de "distancia al límite" en el espacio de escalas. Las crestas de esta imagen, una vez proyectadas sobre la imagen original, debían ser análogas a un esqueleto de forma ( por ejemplo , el eje medial de Blum ) de la imagen original.

A continuación se presenta una definición para la cresta de escala máxima de una función de tres variables, una de las cuales es un parámetro de "escala". Una condición que queremos que se cumpla en esta definición es que, si${\displaystyle (\mathbf {x} ,\sigma )}$es un punto en esta cresta, entonces el valor de la función en el punto es máximo en la dimensión de escala. Sea${\displaystyle f(\mathbf {x} ,\sigma )}$ser una función suave y diferenciable en${\displaystyle U\subset \mathbb {R} ^{2}\times \mathbb {R} _{+}}$. El${\displaystyle (\mathbf {x} ,\sigma )}$es un punto en la cresta de escala máxima si y solo si

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

La detección de crestas suele tener como objetivo capturar el eje principal de simetría de un objeto alargado, mientras que la detección de bordes suele tener como objetivo capturar el contorno del objeto. Sin embargo, algunos textos sobre detección de bordes incluyen erróneamente la noción de crestas dentro del concepto de bordes, lo que genera confusión.

En términos de definiciones, existe una estrecha conexión entre los detectores de bordes y los detectores de crestas. Con la formulación de no máximo dada por Canny, ^{[ 27 ]} se cumple que los bordes se definen como los puntos donde la magnitud del gradiente asume un máximo local en la dirección del gradiente. Siguiendo una forma geométrica diferencial de expresar esta definición, ^{[ 28 ]} podemos en el mencionado anteriormente${\displaystyle (u,v)}$-sistema de coordenadas establece que la magnitud del gradiente de la representación del espacio de escalas, que es igual a la derivada direccional de primer orden en el${\displaystyle v}$-dirección${\displaystyle L_{v}}$, debería tener su derivada direccional de primer orden en el${\displaystyle v}$-dirección igual a cero

${\displaystyle \partial _{v}(L_{v})=0}$

mientras que la derivada direccional de segundo orden en el${\displaystyle v}$-dirección de${\displaystyle L_{v}}$debe ser negativo, es decir,

${\displaystyle \partial _{vv}(L_{v})\leq 0}$.

Escrito como una expresión explícita en términos de derivadas parciales locales.${\displaystyle L_{x}}$,${\displaystyle L_{y}}$...${\displaystyle L_{yyy}}$, esta definición de borde se puede expresar como las curvas de cruce por cero del invariante diferencial

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

que satisfacen una condición de signo en el siguiente invariante diferencial

${\displaystyle L_{v}^{3}L_{vvv}=L_{x}^{3}\,L_{xxx}+3\,L_{x}^{2}\,L_{y}\,L_{xxy}+3\,L_{x}\,L_{y}^{2}\,L_{xyy}+L_{y}^{3}\,L_{yyy}\leq 0}$

(Para más información, consulte el artículo sobre detección de bordes ). Cabe destacar que los bordes obtenidos de esta manera son las crestas de la magnitud del gradiente.

• detección de blobs
• visión por computadora
• Detección de bordes
• Detección de características (visión por computadora)
• detección de puntos de interés
• Espacio de escala