Implementación de espacio a escala

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 en múltiples escalas y, específicamente, mejorar o suprimir 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 están sujetos a suavizado mediante convolución gaussiana . La mayor parte de la teoría del espacio de escala gaussiana trata con imágenes continuas, mientras que al implementar esta teoría habrá 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 de cómo discretizar la teoría continua preservando o aproximando bien las propiedades teóricas deseables que conducen a la elección del núcleo gaussiano (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 gaussiana en el espacio de escala 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 adoptar 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 núcleo 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},}$

dónde

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

y la desviación estándar del σ gaussiano 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 mayores. Por tanto, el resto del artículo se centra en el caso unidimensional.

El núcleo gaussiano muestreado

Al implementar el paso de suavizado unidimensional en la práctica, el enfoque presumiblemente más simple es convolucionar la señal discreta f _D con un núcleo gaussiano muestreado :

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

dónde

${\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 lo suficientemente grande (ver función de error ) tal 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 núcleo gaussiano.

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

donde C suele elegirse entre 3 y 6.

Sin embargo, el uso del núcleo gaussiano muestreado puede generar 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 de diseño primarios, 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 alternativas mejores a una función de ventana rectangular . Por ejemplo, para un número determinado de puntos, una ventana de Hamming , una ventana de Blackman o una ventana de Kaiser causarán menos daño a las propiedades espectrales y de otro tipo del gaussiano que un simple truncamiento. A pesar de esto, dado que el núcleo gaussiano disminuye rápidamente en las colas, la principal recomendación sigue siendo utilizar un valor de ε suficientemente pequeño para que los efectos de truncamiento ya no sean importantes.

El núcleo gaussiano discreto

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

Un enfoque más refinado es convolucionar la señal original con el núcleo gaussiano discreto T ( n , t ) ^{[1] [2] [3]}

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

dónde

${\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 de la gaussiana continua en el sentido de que es la solución de la ecuación de difusión discreta (espacio discreto, tiempo continuo), al igual que la gaussiana continua es la solución de 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 filtro 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 en 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 aproximación excelente utilizando extensión periódica y una transformada de Fourier discreta adecuadamente larga para aproximar la transformada de Fourier de tiempo discreto de la señal que se está suavizando. Además, las aproximaciones de derivadas de orden superior se pueden calcular de manera sencilla (y preservando las propiedades del espacio de escala) aplicando pequeños operadores de diferencia central de soporte a la representación del espacio de escala discreta . ^[5]

Al igual que con la gaussiana muestreada, un simple truncamiento 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 de la gaussiana discreta en una cascada de filtros binomiales generalizados o, alternativamente, construir un núcleo aproximado finito multiplicando por una función de ventana . Si ε se ha elegido demasiado grande de modo que los efectos del error de truncamiento comiencen a aparecer (por ejemplo, como extremos espurios o respuestas espurias a operadores de derivadas de orden superior), entonces las opciones son disminuir el valor de ε de modo que un núcleo finito más grande Se utiliza, con corte donde el soporte es muy pequeño, o utilizar una ventana cónica.

Filtros recursivos

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

Dado que la eficiencia computacional suele ser importante, a menudo se utilizan filtros recursivos de bajo orden para el suavizado del espacio de escala. Por ejemplo, Young y van Vliet ^[6] utilizan un filtro recursivo de tercer orden con un polo real y un par de polos complejos, aplicado hacia adelante y hacia atrás para realizar 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 igualar la curvatura de la función de transferencia a frecuencia cero del gaussiano discreto, lo que garantiza una propiedad de semigrupo aproximada del 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 frecuencias de Pólya normalizada que funciona para cualquier escala de suavizado, pero no es una aproximación tan excelente al gaussiano como el filtro de Young y van Vliet, que no es una secuencia de frecuencias de Pólya normalizada, debido a su complejidad. polos.

La función de transferencia, H ₁ , de un filtro recursivo de par de polos simétrico está estrechamente relacionada con la transformada de Fourier en tiempo discreto del núcleo gaussiano discreto mediante una 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 mediante:

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

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

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

donde las posiciones polares estables se ajustan resolviendo:

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

Las respuestas al 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 sólo uno o dos pares de polos por escala, una señal suavizada sucesivamente en escalas crecientes estará muy cerca de una señal suavizada gaussianamente. La propiedad del semigrupo se aproxima mal cuando se utilizan muy pocos pares de polos.

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

• linealidad
• invariancia de desplazamiento (desplazamientos de números 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 sólo se cumple aproximadamente, siendo la aproximación mejor para un mayor número de pares de polos:

• existencia de un generador infinitesimal A (el generador infinitesimal del gaussiano discreto, o un filtro que se aproxima a él, asigna aproximadamente una respuesta de filtro recursivo a una de t infinitamente 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

Varios autores han descrito este método de filtro recursivo y sus variaciones para calcular tanto el suavizado gaussiano como las derivadas gaussianas. ^{[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, brinden la mejor aproximación posible a la simetría rotacional, por lo que se pueden considerar implementaciones no separables para imágenes 2D como una alternativa.

Al calcular varias derivadas en el chorro N simultáneamente, el suavizado discreto del espacio de escala con el análogo discreto del núcleo gaussiano, o con una aproximación de filtro recursivo, seguida 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 de derivados.

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 simétrico de 3 núcleos [ 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 aproxima al gaussiano discreto en el límite de pequeños t . De hecho, con t infinitesimal , ya sea este filtro de dos ceros o el filtro bipolar con polos en Z  = t /2 y Z  = 2/ t se puede 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 crear un filtro de suavizado general de alta calidad. Por ejemplo, si el proceso de suavizado consiste en aplicar siempre un filtro bicuadrático (dos polos, dos ceros) hacia adelante y hacia atrás en cada fila de datos (y en cada columna en el caso 2D), los polos y los ceros pueden hacer cada uno un parte del alisado. Los ceros se limitan a 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 constituye una excelente aproximación al gaussiano discreto si los polos y los ceros hacen cada uno aproximadamente la mitad del suavizado. Los valores t para cada porción del suavizado (polos, ceros, aplicaciones múltiples hacia adelante y hacia atrás, etc.) son aditivos, de acuerdo con la propiedad aproximada del semigrupo.

Ubicaciones en el plano Z de cuatro polos (X) y cuatro ceros (círculos) para un filtro de suavizado que utiliza biquad hacia adelante/hacia atrás para suavizar a una escala t = 2, con la mitad del suavizado desde los polos y la mitad desde los ceros. Todos los ceros están 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 del gaussiano discreto, 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 mediante:

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

y requerimos t  ≤ 0,5 para mantener la función de transferencia no negativa.

Además, estos filtros con N pares de ceros son una aproximación aún mejor al 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 y 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 de escala

En cuanto al tema de selección automática de escala basada en derivadas normalizadas, con frecuencia se utilizan aproximaciones piramidales para obtener rendimiento en tiempo real. ^{[11] [12] [13]} La idoneidad de aproximar operaciones de espacio de escala dentro de una pirámide se origina en el hecho de que el suavizado en cascada repetido 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 escala creciente (consulte el artículo sobre múltiples núcleos ). -enfoques de escala para más detalles). Sin embargo, es posible que sea necesario tener especial cuidado para evitar artefactos de discretización.

Otros enfoques multiescala

Para los núcleos unidimensionales, existe una teoría bien desarrollada de enfoques de múltiples escalas , relativa a 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 continua, la gaussiana continua y la gaussiana discreta constituyen la opción única para señales continuas y discretas.

Existen muchas otras técnicas de procesamiento de señales, procesamiento de imágenes y compresión de datos a múltiples escalas, que utilizan wavelets y una variedad de otros núcleos, que no explotan ni requieren los mismos requisitos que las descripciones de espacios de escala ; es decir, no dependen de que una escala más gruesa no genere un nuevo extremo que no estaba presente en una escala más fina (en 1D) o de que no se mejoren 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 multiescala
• filtro gaussiano

enlaces externos

• pyscsp: caja de herramientas de espacio de escala para Python en GitHub (incluidas implementaciones de diferentes métodos para aproximar el suavizado gaussiano para datos discretos)

Referencias

1. Lindeberg, T., "Espacio de escala para señales discretas", PAMI(12), núm. 3, marzo de 1990, págs.
2. Lindeberg, T., Teoría del espacio-escala en 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 el procesamiento de imágenes y voz", IEEE Transactions on Acoustics, Speech and Signal Processing, vol. 39, págs. 723-727, marzo de 1991.
4. Campbell, J, 2007, El modelo SMM como 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 de 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 la señal . 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, INRIA Research Report 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 del 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 el filtrado gaussiano rápido de variantes espaciales". Imágenes en tiempo real . vol. 9, núm. 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". Métodos de escala espacial en visión por computadora. Apuntes de conferencias sobre informática. vol. 2695. Procedimiento. Scale-Space'03, Apuntes de conferencias de Springer sobre informática. 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 distintivas de la imagen a partir de puntos clave invariantes de escala", International Journal of Computer Vision, 60, 2, págs. 91-110, 2004.