Implementación del espacio de escala

Espacio de escala
Axiomas del espacio de escala
Implementación del espacio de escala
Detección de características
Detección de bordes
Detección de manchas
Detección de esquinas
Detección de crestas
Detección de puntos de interés
Selección de escala
Adaptación de formas afines
Segmentación del espacio de escala
v t mi

En las áreas de visión por computadora , análisis de imágenes y procesamiento de señales , la noción de representación del espacio de escala se utiliza para procesar datos de medición a múltiples escalas y, específicamente, mejorar o suprimir las características de la imagen en diferentes rangos de escala (consulte el artículo sobre el espacio de escala ). . El espacio de escala gaussiano proporciona un tipo especial de representación del espacio de escala, donde los datos de la imagen en N dimensiones se someten a suavizado por convolución gaussiana.. La mayor parte de la teoría del espacio de escala gaussiana se ocupa de imágenes continuas, mientras que, al implementar esta teoría, se tendrá que afrontar el hecho de que la mayoría de los datos de medición son discretos. Por lo tanto, surge el problema teórico con respecto a cómo discretizar la teoría continua mientras se preservan o aproximan bien las propiedades teóricas deseables que conducen a la elección del núcleo de Gauss (ver el artículo sobre axiomas del espacio de escala ). Este artículo describe enfoques básicos para esto que se han desarrollado en la literatura.

Planteamiento del problema

La representación en el espacio de escala gaussiana de una señal continua N -dimensional,

${\displaystyle f_{C}\left(x_{1},\cdots ,x_{N},t\right),}$

se obtiene convolucionando f _C con un núcleo gaussiano N -dimensional :

${\displaystyle g_{N}\left(x_{1},\cdots ,x_{N},t\right).}$

En otras palabras:

${\displaystyle L\left(x_{1},\cdots ,x_{N},t\right)=\int _{u_{1}=-\infty }^{\infty }\cdots \int _{u_{N}=-\infty }^{\infty }f_{C}\left(x_{1}-u_{1},\cdots ,x_{N}-u_{N},t\right)\cdot g_{N}\left(u_{1},\cdots ,u_{N},t\right)\,du_{1}\cdots du_{N}.}$

Sin embargo, para la implementación , esta definición no es práctica, ya que es continua. Al aplicar el concepto de espacio de escala a una señal discreta f _D , se pueden tomar diferentes enfoques. Este artículo es un breve resumen de algunos de los métodos más utilizados.

Posibilidad de separación

Usando la propiedad de separabilidad del kernel gaussiano

${\displaystyle g_{N}\left(x_{1},\dots ,x_{N},t\right)=G\left(x_{1},t\right)\cdots G\left(x_{N},t\right)}$

la operación de convolución N -dimensional se puede descomponer en un conjunto de pasos de suavizado separables con un núcleo gaussiano unidimensional G a lo largo de cada dimensión

${\displaystyle L(x_{1},\cdots ,x_{N},t)=\int _{u_{1}=-\infty }^{\infty }\cdots \int _{u_{N}=-\infty }^{\infty }f_{C}(x_{1}-u_{1},\cdots ,x_{N}-u_{N},t)G(u_{1},t)\,du_{1}\cdots G(u_{N},t)\,du_{N},}$

donde

${\displaystyle G(x,t)={\frac {1}{\sqrt {2\pi t}}}e^{-{\frac {x^{2}}{2t}}}}$

y la desviación estándar de la σ gaussiana está relacionada con el parámetro de escala t según t = σ ² .

Se asumirá la separabilidad en todo lo que sigue, incluso cuando el núcleo no sea exactamente gaussiano, ya que la separación de las dimensiones es la forma más práctica de implementar el suavizado multidimensional, especialmente a escalas más grandes. Por tanto, el resto del artículo se centra en el caso unidimensional.

El kernel gaussiano muestreado

Al implementar el paso de suavizado unidimensional en la práctica, el enfoque probablemente más simple es convertir la señal discreta f _D con un kernel gaussiano muestreado :

${\displaystyle L(x,t)=\sum _{n=-\infty }^{\infty }f(x-n)\,G(n,t)}$

donde

${\displaystyle G(n,t)={\frac {1}{\sqrt {2\pi t}}}e^{-{\frac {n^{2}}{2t}}}}$

(con t = σ ² ) que a su vez se trunca en los extremos para dar un filtro con respuesta de impulso finita

${\displaystyle L(x,t)=\sum _{n=-M}^{M}f(x-n)\,G(n,t)}$

para M elegido suficientemente grande (ver función de error ) de modo que

${\displaystyle 2\int _{M}^{\infty }G(u,t)\,du=2\int _{\frac {M}{\sqrt {t}}}^{\infty }G(v,1)\,dv<\varepsilon .}$

Una opción común es establecer M en una constante C multiplicada por la desviación estándar del kernel gaussiano.

${\displaystyle M=C\sigma +1=C{\sqrt {t}}+1}$

donde C a menudo se elige entre 3 y 6.

Sin embargo, el uso del núcleo gaussiano muestreado puede dar lugar a problemas de implementación, en particular cuando se calculan derivadas de orden superior a escalas más finas mediante la aplicación de derivadas muestreadas de núcleos gaussianos. Cuando la precisión y la solidez son criterios primarios de diseño, se deben considerar enfoques de implementación alternativos.

Para valores pequeños de ε (10 ⁻⁶ a 10 ⁻⁸ ), los errores introducidos al truncar el gaussiano suelen ser insignificantes. Sin embargo, para valores mayores de ε, existen muchas mejores alternativas a una función de ventana rectangular . Por ejemplo, para un número dado de puntos, una ventana de Hamming , ventana Blackman , o ventana Kaiser hará menos daño a las propiedades espectrales y otras de la Gaussiana que un simple truncamiento hará. A pesar de esto, dado que el kernel de Gauss disminuye rápidamente en las colas, la recomendación principal sigue siendo utilizar un valor suficientemente pequeño de ε para que los efectos de truncamiento ya no sean importantes.

El kernel discreto de Gauss

El núcleo gaussiano discreto ideal (sólido) comparado con el gaussiano ordinario muestreado (punteado), para escalas t = [0.5, 1, 2, 4]

Un enfoque más refinado es convertir la señal original con el kernel de Gauss discreto T ( n , t ) ^{[1] [2] [3]}

${\displaystyle L(x,t)=\sum _{n=-\infty }^{\infty }f(x-n)\,T(n,t)}$

donde

${\displaystyle T(n,t)=e^{-t}I_{n}(t)}$

y denota las funciones de Bessel modificadas de orden entero, n . Esta es la contraparte discreta del gaussiano continuo en el sentido de que es la solución a la ecuación de difusión discreta (espacio discreto, tiempo continuo), al igual que el gaussiano continuo es la solución a la ecuación de difusión continua. ^{[1] [2] [4]}${\displaystyle I_{n}(t)}$

Este filtro se puede truncar en el dominio espacial como para el gaussiano muestreado

${\displaystyle L(x,t)=\sum _{n=-M}^{M}f(x-n)\,T(n,t)}$

o se puede implementar en el dominio de Fourier usando una expresión de forma cerrada para su transformada de Fourier de tiempo discreto :

${\displaystyle {\widehat {T}}(\theta ,t)=\sum _{n=-\infty }^{\infty }T(n,t)\,e^{-i\theta n}=e^{t(\cos \theta -1)}.}$

Con este enfoque en el dominio de la frecuencia, las propiedades del espacio de escala se transfieren exactamente al dominio discreto, o con una excelente aproximación utilizando una extensión periódica y una transformada discreta de Fourier adecuadamente larga para aproximar la transformada de Fourier en tiempo discreto de la señal que se suaviza. Además, las aproximaciones derivadas de orden superior se pueden calcular de manera sencilla (y preservando las propiedades del espacio de escala) aplicando operadores de diferencia central de soporte pequeño a la representación del espacio de escala discreta . ^[5]

Al igual que con el gaussiano muestreado, un truncamiento simple de la respuesta al impulso infinito será en la mayoría de los casos una aproximación suficiente para valores pequeños de ε, mientras que para valores más grandes de ε es mejor usar una descomposición del gaussiano discreto en una cascada de filtros binomiales generalizados o, alternativamente, construir un kernel aproximado finito multiplicando por una función de ventana . Si ε se ha elegido demasiado grande para que los efectos del error de truncamiento comiencen a aparecer (por ejemplo, como extremos espurios o respuestas espúreas a operadores derivados de orden superior), entonces las opciones son disminuir el valor de ε de manera que un kernel finito más grande se utiliza, con corte donde el soporte es muy pequeño, o para utilizar una ventana ahusada.

Filtros recursivos

Núcleos de espacio de escala. Gaussiano discreto ideal basado en funciones de bessel (rojo) y filtros de suavizado recursivos hacia adelante / atrás de dos pares de polos (azul) con polos como se describe en el texto. La parte superior muestra los granos individuales y la parte inferior es su convolución acumulativa entre sí; t = [0,5, 1, 2, 4].

Dado que la eficiencia computacional es a menudo importante, los filtros recursivos de bajo orden se utilizan a menudo para suavizar el espacio de escala. Por ejemplo, Young y van Vliet ^[6] usan un filtro recursivo de tercer orden con un polo real y un par de polos complejos, aplicados hacia adelante y hacia atrás para hacer una aproximación simétrica de sexto orden al gaussiano con baja complejidad computacional para cualquier suavizado. escala.

Al relajar algunos de los axiomas, Lindeberg ^[1] concluyó que los buenos filtros de suavizado serían " secuencias de frecuencia de Pólya normalizadas ", una familia de núcleos discretos que incluye todos los filtros con polos reales en 0 < Z <1 y / o Z > 1. , así como con ceros reales en Z <0. Para la simetría, que conduce a una homogeneidad direccional aproximada, estos filtros deben restringirse aún más a pares de polos y ceros que conducen a filtros de fase cero.

Para que coincida con la curvatura función de transferencia en cero frecuencia de la discreta de Gauss, lo que asegura un aproximado semi-grupo propiedad de aditivo t , dos polos en

${\displaystyle Z=1+{\frac {2}{t}}-{\sqrt {\left(1+{\frac {2}{t}}\right)^{2}-1}}}$

se puede aplicar hacia adelante y hacia atrás, para lograr simetría y estabilidad. Este filtro es la implementación más simple de un núcleo de secuencia de frecuencia de Pólya normalizado que funciona para cualquier escala de suavizado, pero no es una aproximación tan excelente al filtro gaussiano como el de Young y van Vliet, que no es la secuencia de frecuencia de Pólya normalizada, debido a su complejidad. polos.

La función de transferencia, H ₁ , de un filtro recursivo simétrico de pares de polos está estrechamente relacionada con la transformada de Fourier en tiempo discreto del kernel discreto de Gauss a través de la aproximación de primer orden de la exponencial:

${\displaystyle {\widehat {T}}(\theta ,t)={\frac {1}{e^{t(1-\cos \theta )}}}\approx {\frac {1}{1+t(1-\cos \theta )}}=H_{1}(\theta ,t),}$

donde el parámetro t aquí está relacionado con la posición polar estable Z = p a través de:

${\displaystyle t={\frac {2p}{(1-p)^{2}}}.}$

Además, dichos filtros con N pares de polos, como los dos pares de polos ilustrados en esta sección, son una aproximación aún mejor a la exponencial:

${\displaystyle {\frac {1}{\left(1+{\frac {t}{N}}(1-\cos \theta )\right)^{N}}}=H_{N}(\theta ,t),}$

donde las posiciones de los polos estables se ajustan resolviendo:

${\displaystyle {\frac {t}{N}}={\frac {2p}{(1-p)^{2}}}.}$

Las respuestas de impulso de estos filtros no son muy cercanas a las gaussianas a menos que se utilicen más de dos pares de polos. Sin embargo, incluso con solo uno o dos pares de polos por escala, una señal suavizada sucesivamente a escalas crecientes estará muy cerca de una señal suavizada por gauss. La propiedad del semigrupo se aproxima mal cuando se utilizan muy pocos pares de polos.

Los axiomas del espacio de escala que aún se satisfacen con estos filtros son:

• linealidad
• invariancia de cambio (cambios enteros)
• no creación de extremos locales (cruces por cero) en una dimensión
• no mejora de los extremos locales en cualquier número de dimensiones
• positividad
• normalización

Lo siguiente solo se satisface aproximadamente, la aproximación es mejor para un mayor número de pares de polos:

• existencia de un generador infinitesimal A (el generador infinitesimal del discreto gaussiano, o un filtro que se aproxima, mapea aproximadamente una respuesta de filtro recursiva a uno de t infinitesimalmente mayor )
• la estructura de semigrupo con la propiedad de suavizado en cascada asociada (esta propiedad se aproxima considerando que los núcleos son equivalentes cuando tienen el mismo valor t , incluso si no son del todo iguales)
• simetría rotacional
• invariancia de escala

Este método de filtro recursivo y las variaciones para calcular tanto el suavizado gaussiano como las derivadas gaussianas han sido descritos por varios autores. ^{[6] [7] [8] [9]} Tan et al. han analizado y comparado algunos de estos enfoques, y han señalado que los filtros de Young y van Vliet son una cascada (multiplicación) de filtros hacia adelante y hacia atrás, mientras que Deriche y Jin et al. Los filtros son sumas de filtros hacia adelante y hacia atrás. ^[10]

A escalas finas, no se garantiza que el enfoque de filtrado recursivo, así como otros enfoques separables, proporcionen la mejor aproximación posible a la simetría rotacional, por lo que las implementaciones no separables para imágenes 2D pueden considerarse como una alternativa.

Cuando se calculan varias derivadas en el chorro N simultáneamente, el suavizado discreto del espacio de escala con el análogo discreto del kernel gaussiano, o con una aproximación de filtro recursivo, seguido de pequeños operadores de diferencia de soporte, puede ser más rápido y más preciso que calcular aproximaciones recursivas. de cada operador derivado.

Suavizadores de respuesta de impulso finito (FIR)

Para escalas pequeñas, un filtro FIR de orden bajo puede ser un mejor filtro de suavizado que un filtro recursivo. El 3-kernel simétrico [ t / 2, 1- t , t / 2] , para t  ≤ 0.5 se suaviza a una escala de t usando un par de ceros reales en Z  <0, y se acerca al discreto gaussiano en el límite de pequeños t . De hecho, con t infinitesimal , este filtro de dos ceros o el filtro de dos polos con polos en Z  = t / 2 y Z  = 2 / t se pueden utilizar como generador infinitesimal para los núcleos gaussianos discretos descritos anteriormente.

Los ceros del filtro FIR se pueden combinar con los polos del filtro recursivo para hacer un filtro de suavizado general de alta calidad. Por ejemplo, si el proceso de suavizado es aplicar siempre un filtro bicuadrático (dos polos, dos ceros) hacia adelante y luego hacia atrás en cada fila de datos (y en cada columna en el caso 2D), los polos y ceros pueden hacer cada uno una parte del suavizado. Los ceros se limitan en t = 0.5 por par (ceros en Z = –1), por lo que para escalas grandes los polos hacen la mayor parte del trabajo. En escalas más finas, la combinación hace una excelente aproximación al discreto gaussiano si los polos y ceros hacen cada uno aproximadamente la mitad del suavizado. La t los valores para cada porción del suavizado (polos, ceros, múltiples aplicaciones hacia adelante y hacia atrás, etc.) son aditivos, de acuerdo con la propiedad aproximada del semigrupo.

Ubicaciones del plano Z de cuatro polos (X) y cuatro ceros (círculos) para un filtro de suavizado usando biquad adelante / atrás para suavizar a una escala t = 2, con la mitad del suavizado de los polos y la mitad de los ceros. Los ceros están todos en Z = –1; los polos están en Z = 0.172 y Z = 5.83. Los polos fuera del círculo unitario se implementan filtrando hacia atrás con los polos estables.

La función de transferencia del filtro FIR está estrechamente relacionada con la DTFT discreta de Gauss, al igual que la del filtro recursivo. Para un solo par de ceros, la función de transferencia es

${\displaystyle {\widehat {T}}(\theta ,t)=e^{-t(1-\cos \theta )}\approx {1-t(1-\cos \theta )}=F_{1}(\theta ,t),}$

donde el parámetro t aquí está relacionado con las posiciones cero Z = z a través de:

${\displaystyle t=-{\frac {2z}{(1-z)^{2}}},}$

y requerimos t  ≤ 0.5 para mantener la función de transferencia no negativa.

Además, dichos filtros con N pares de ceros son una aproximación aún mejor a la exponencial y se extienden a valores más altos de t  :

${\displaystyle \left(1-{\frac {t}{N}}(1-\cos \theta )\right)^{N}=F_{N}(\theta ,t),}$

donde las posiciones cero estables se ajustan resolviendo:

${\displaystyle {\frac {t}{N}}=-{\frac {2z}{(1-z)^{2}}}.}$

Estos filtros FIR y de polo cero son núcleos de espacio de escala válidos, que satisfacen los mismos axiomas que los filtros recursivos de todos los polos.

Implementación en tiempo real dentro de pirámides y aproximación discreta de derivadas normalizadas a escala

En cuanto al tema de la selección automática de escala basada en derivadas normalizadas, las aproximaciones piramidales se utilizan con frecuencia para obtener un rendimiento en tiempo real. ^{[11] [12] [13]} La conveniencia de aproximar las operaciones de espacio de escala dentro de una pirámide se origina en el hecho de que el suavizado repetido en cascada con núcleos binomiales generalizados conduce a núcleos de suavizado equivalentes que, en condiciones razonables, se acercan al gaussiano. Además, se puede demostrar que los núcleos binomiales (o más generalmente la clase de núcleos binomiales generalizados) constituyen la clase única de núcleos de soporte finito que garantizan la no creación de extremos locales o cruces por cero con una escala creciente (ver el artículo sobre múltiples -enfoques a escalapara detalles). Sin embargo, puede ser necesario tener especial cuidado para evitar artefactos de discretización.

Otros enfoques de múltiples escalas

Para los núcleos unidimensionales, existe una teoría bien desarrollada de enfoques de múltiples escalas , con respecto a los filtros que no crean nuevos extremos locales o nuevos cruces por cero con escalas crecientes. Para señales continuas, los filtros con polos reales en el plano s están dentro de esta clase, mientras que para señales discretas, los filtros recursivos y FIR descritos anteriormente satisfacen estos criterios. Combinado con el estricto requisito de una estructura de semigrupo continuo, el gaussiano continuo y el gaussiano discreto constituyen la opción única para señales continuas y discretas.

Hay muchas otras técnicas de procesamiento de señales de múltiples escalas, procesamiento de imágenes y compresión de datos, que utilizan wavelets y una variedad de otros núcleos, que no explotan ni requieren los mismos requisitos que las descripciones de espacio de escala ; es decir, no dependen de una escala más gruesa que no genera un nuevo extremo que no estaba presente en una escala más fina (en 1D) o que no mejora los extremos locales entre niveles de escala adyacentes (en cualquier número de dimensiones).

Ver también

• Espacio de escala
• Pirámide (procesamiento de imágenes)
• Enfoques de múltiples escalas
• Filtro gaussiano

Referencias

1. Lindeberg, T., "Espacio de escala para señales discretas", PAMI (12), No. 3, marzo de 1990, págs. 234-254.
2. Lindeberg, T., Teoría del espacio de escala en la visión por computadora, Kluwer Academic Publishers, 1994 , ISBN  0-7923-9418-6
3. RA Haddad y AN Akansu, " Una clase de filtros binomiales gaussianos rápidos para procesamiento de imágenes y voz ", Transacciones IEEE sobre procesamiento de señales, voz y acústica, vol. 39, págs. 723-727, marzo de 1991.
4. Campbell, J, 2007, El modelo SMM como un problema de valor límite utilizando la ecuación de difusión discreta , Theor Popul Biol. Diciembre de 2007; 72 (4): 539-46.
5. Lindeberg, T. Aproximaciones derivadas discretas con propiedades de espacio de escala: una base para la extracción de características de bajo nivel, J. of Mathematical Imaging and Vision, 3 (4), págs. 349-376, 1993.
6. Ian T. Young y Lucas J. van Vliet (1995). "Implementación recursiva del filtro gaussiano" . Procesamiento de señales . 44 (2): 139-151. CiteSeerX 10.1.1.12.2826 . doi : 10.1016 / 0165-1684 (95) 00020-E . 
7. Deriche, R: Implementación recursiva del gaussiano y sus derivados, Informe de investigación de INRIA 1893, 1993.
8. Richard F. Lyon. "Reconocimiento de voz en el espacio de escala", Proc. de 1987 ICASSP. San Diego, marzo, págs. 29.3.14, 1987.
9. Jin, JS, Gao Y. "Implementación recursiva de filtrado LoG". Imágenes en tiempo real 1997; 3: 59–65.
10. . Sovira Tan; Jason L. Dale y Alan Johnston (2003). "Rendimiento de tres algoritmos recursivos para filtrado gaussiano de variante espacial rápida". Imágenes en tiempo real . Vol. 9 no. 3. págs. 215-228. doi : 10.1016 / S1077-2014 (03) 00040-8 .
11. Lindeberg, Tony y Bretzner, Lars (2003). Selección de escala en tiempo real en representaciones híbridas multiescala . Proc. Scale-Space'03, Springer Lecture Notes in Computer Science . Apuntes de conferencias en Ciencias de la Computación. 2695 . págs. 148-163. doi : 10.1007 / 3-540-44935-3_11 . ISBN 978-3-540-40368-5.
12. Crowley, J, Riff O: Cálculo rápido de campos receptivos gaussianos normalizados a escala, Proc. Scale-Space'03, Isla de Skye, Escocia, Springer Lecture Notes in Computer Science, volumen 2695, 2003.
13. Lowe, DG, "Características de imagen distintivas de puntos clave invariantes en escala", International Journal of Computer Vision, 60, 2, págs. 91-110, 2004.