Implementación del espacio a escala

En las áreas de visión artificial , análisis de imágenes y procesamiento de señales , la noción de representación en el 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 ). Un tipo especial de representación en el espacio de escala es proporcionado por el espacio de escala gaussiano, donde los datos de la imagen en N dimensiones se someten a suavizado por convolución gaussiana . La mayor parte de la teoría para el espacio de escala gaussiano trata con imágenes continuas, mientras que al implementar esta teoría uno tendrá que enfrentar el hecho de que la mayoría de los datos de medición son discretos. Por lo tanto, surge el problema teórico sobre 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 gaussiano (consulte el artículo sobre los axiomas del espacio de escala ). Este artículo describe los enfoques básicos para esto que se han desarrollado en la literatura; consulte también ^[1] para un tratamiento en profundidad del tema de la aproximación de la operación de suavizado gaussiano y los cálculos de la derivada gaussiana en la teoría del espacio de escala.

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 adoptar diferentes enfoques. Este artículo es un breve resumen de algunos de los métodos más utilizados.

Posibilidad de separación

Utilizando 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 de la gaussiana σ está relacionada con el parámetro de escala t según t = σ ² .

En todo lo que sigue se supondrá que existe separabilidad, 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 lo 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 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 se elige a menudo en algún lugar 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 en escalas más finas mediante la aplicación de derivadas muestreadas de núcleos gaussianos. Por lo tanto, cuando la precisión y la robustez 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 la gaussiana suelen ser despreciables. 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 , una ventana de Blackman o una ventana de Kaiser causarán menos daño a las propiedades espectrales y de otro tipo de la gaussiana que un simple truncamiento. A pesar de esto, dado que el núcleo gaussiano disminuye rápidamente en las colas, la recomendación principal sigue siendo utilizar un valor suficientemente pequeño de ε de modo que los efectos del 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 ) ^{[2] [3] [4]}

${\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 cuanto a que es la solución de la ecuación de difusión discreta (espacio discreto, tiempo continuo), así como la gaussiana continua es la solución de la ecuación de difusión continua. ^{[2] [3] [5]} ${\displaystyle I_{n}(t)}$

Este filtro se puede truncar en el dominio espacial como en el caso del filtro gaussiano muestreado.

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

o puede implementarse en el dominio de Fourier utilizando 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 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 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 discreto . ^[6]

Al igual que con la gaussiana muestreada, 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 mayores de ε es mejor utilizar 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 comiencen a aparecer los efectos del error de truncamiento (por ejemplo, como extremos espurios o respuestas espurias a operadores derivados de orden superior), entonces las opciones son disminuir el valor de ε de modo que se utilice un núcleo finito más grande, con un corte donde el soporte sea muy pequeño, o utilizar una ventana cónica.

Filtros recursivos

Núcleos en el espacio de escala. Gaussiana discreta ideal basada 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. En la parte superior se muestran los núcleos individuales y en la parte inferior su convolución acumulada entre sí; t = [0,5, 1, 2, 4].

Dado que la eficiencia computacional suele ser importante, los filtros recursivos de orden bajo se utilizan a menudo para suavizar el espacio de escala. Por ejemplo, Young y van Vliet ^[7] utilizan 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 a la gaussiana con baja complejidad computacional para cualquier escala de suavizado.

Al relajar algunos de los axiomas, Lindeberg ^[2] concluyó que los buenos filtros de suavizado serían " secuencias de frecuencia 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 de la función de transferencia en la frecuencia cero de la gaussiana discreta, lo que garantiza una propiedad de semigrupo aproximada de t aditivo , 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 Pólya normalizado 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 Pólya normalizada, debido a sus polos complejos.

La función de transferencia, H ₁ , de un filtro recursivo de pares de polos simétricos está estrechamente relacionada con la transformada de Fourier de tiempo discreto del núcleo gaussiano discreto 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 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 solo uno o dos pares de polos por escala, una señal suavizada sucesivamente a escalas crecientes será muy cercana a una señal suavizada gaussianamente. La propiedad de semigrupo se aproxima mal cuando se utilizan muy pocos pares de polos.

Los axiomas del espacio de escala que todavía se satisfacen con 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

Los siguientes solo se cumplen de forma aproximada, siendo la aproximación mejor para un mayor número de pares de polos:

• existencia de un generador infinitesimal A (el generador infinitesimal de la gaussiana discreta, o un filtro que lo aproxima, asigna aproximadamente una respuesta de filtro recursivo a una 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

Varios autores han descrito este método de filtro recursivo y sus variaciones para calcular tanto el suavizado gaussiano como las derivadas gaussianas. ^{[7] [8] [9] [10]} 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 los filtros de Deriche y Jin et al. son sumas de filtros hacia adelante y hacia atrás. ^[11]

En escalas finas, no se garantiza que el enfoque de filtrado recursivo ni otros enfoques separables brinden 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.

Al calcular varias derivadas en el N-jet 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 recursiva, 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 de derivada.

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 suaviza a una escala de t utilizando un par de ceros reales en Z  < 0, y se aproxima al gaussiano discreto en el límite de t pequeño. De hecho, con t infinitesimal , tanto este filtro de dos ceros como el filtro de dos polos con polos en Z  = t /2 y Z  = 2/ t se pueden utilizar como el generador infinitesimal para los kernels 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 delante y luego hacia atrás en cada fila de datos (y en cada columna en el caso 2D), los polos y los ceros pueden realizar cada uno una parte del suavizado. Los ceros tienen un límite 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 constituye una excelente aproximación a la gaussiana discreta si los polos y los ceros realizan cada uno aproximadamente la mitad del suavizado. Los valores t para cada parte del suavizado (polos, ceros, aplicaciones múltiples hacia delante y hacia atrás, etc.) son aditivos, de acuerdo con la propiedad de semigrupo aproximado.

Ubicaciones en el plano Z de cuatro polos (X) y cuatro ceros (círculos) para un filtro de suavizado que utiliza un bicuadrado hacia adelante/atrás para suavizar a una escala t = 2, con la mitad del suavizado desde los polos y la otra mitad desde 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 de Gauss discreta, al igual que la del filtro recursivo. Para un único 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 que 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 relación con el 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. ^{[12] [13] [14]} La idoneidad de aproximar operaciones de escala-espacio 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 aproximan al gaussiano. Además, se puede demostrar que los núcleos binomiales (o, de manera más general, 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 (consulte el artículo sobre enfoques multiescala para obtener más detalles). Sin embargo, puede ser 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 multiescala , 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. Combinados con el requisito estricto 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, procesamiento de imágenes y compresión de datos en múltiples escalas que utilizan wavelets y una variedad de otros núcleos, que no explotan ni requieren los mismos requisitos que las descripciones del espacio 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 haya una mejora de los extremos locales entre niveles de escala adyacentes (en cualquier número de dimensiones).

Véase también

• Espacio de escala
• Pirámide (procesamiento de imágenes)
• Enfoques multiescala
• Filtro gaussiano

Enlaces externos

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

Referencias

1. Lindeberg, T., "Aproximaciones discretas de suavizado gaussiano y derivadas gaussianas", Journal of Mathematical Imaging and Vision, 66(5): 759–800, 2024.
2. Lindeberg, T., "Espacio de escala para señales discretas", PAMI(12), No. 3, marzo de 1990, págs. 234-254.
3. Lindeberg, T., Teoría del espacio de escala en visión por computadora, Kluwer Academic Publishers, 1994, ISBN  0-7923-9418-6
4. RA Haddad y AN Akansu, "Una clase de filtros binomiales gaussianos rápidos para procesamiento de voz e imágenes", IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 39, págs. 723-727, marzo de 1991.
5. Campbell, J, 2007, El modelo SMM como un problema de valor límite utilizando la ecuación de difusión discreta , Theor Popul Biol. 2007 diciembre;72(4):539-46.
6. 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.
7. Ian T. Young y Lucas J. van Vliet (1995). "Implementación recursiva del filtro gaussiano". Procesamiento de señales . 44 (2): 139–151. Código Bibliográfico :1995SigPr..44..139Y. CiteSeerX 10.1.1.12.2826 . doi :10.1016/0165-1684(95)00020-E. 
8. Deriche, R: Implementación recursiva de la gaussiana y sus derivadas, Informe de investigación INRIA 1893, 1993.
9. Richard F. Lyon. "Reconocimiento de voz en el espacio de escala", Proc. de 1987 ICASSP. San Diego, marzo, págs. 29.3.14, 1987.
10. Jin, JS, Gao Y. "Implementación recursiva del filtrado LoG". Imágenes en tiempo real 1997;3:59–65.
11. . Sovira Tan; Jason L. Dale y Alan Johnston (2003). "Rendimiento de tres algoritmos recursivos para filtrado gaussiano rápido con variantes espaciales". Imágenes en tiempo real . Vol. 9, núm. 3. págs. 215–228. doi :10.1016/S1077-2014(03)00040-8.
12. Lindeberg, Tony y Bretzner, Lars (2003). "Selección de escala en tiempo real en representaciones híbridas multiescala". Métodos de espacio de escala en visión artificial. Apuntes de clase en informática. Vol. 2695. Proc. Scale-Space'03, Springer Lecture Notes in Computer Science. págs. 148–163. doi :10.1007/3-540-44935-3_11. ISBN 978-3-540-40368-5.
13. 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.
14. Lowe, DG, “Características distintivas de la imagen a partir de puntos clave invariantes en escala”, International Journal of Computer Vision, 60, 2, págs. 91-110, 2004.