Implementación del espacio de escala

En los campos de la visión por computadora , el análisis de imágenes y el procesamiento de señales , la noción de representación en el espacio de escalas se utiliza para procesar datos de medición en múltiples escalas, y específicamente para realzar o suprimir características de la imagen en diferentes rangos de escala (véase el artículo sobre el espacio de escalas ). Un tipo especial de representación en el espacio de escalas la proporciona el espacio de escalas gaussiano, donde los datos de la imagen en N dimensiones se someten a un suavizado mediante convolución gaussiana . La mayor parte de la teoría del espacio de escalas gaussiano se ocupa de imágenes continuas, mientras que al implementar esta teoría hay que tener en cuenta 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 adecuadamente las propiedades teóricas deseables que llevan a la elección del núcleo gaussiano (véase el artículo sobre los axiomas del espacio de escalas ). Este artículo describe los enfoques básicos para esto que se han desarrollado en la literatura, ver también ^{[ 1 ]} para un tratamiento en profundidad sobre el 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 escalas, y ^{[ 2 ]} para un tratamiento complementario sobre métodos de discretización híbridos.

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

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

se obtiene mediante la convolución de 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 su implementación , esta definición resulta poco práctica, ya que es continua. Al aplicar el concepto de espacio de escalas a una señal discreta f _D , se pueden adoptar diferentes enfoques. Este artículo ofrece un breve resumen de algunos de los métodos más utilizados.

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 lo que sigue, se asumirá la separabilidad, incluso cuando el núcleo no sea exactamente gaussiano, ya que la separación de 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.

Al implementar en la práctica el paso de suavizado unidimensional, 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 ) de tal manera 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 a 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 en algún punto entre 3 y 6.

Sin embargo, el uso del núcleo gaussiano muestreado puede generar problemas de implementación, en particular al calcular derivadas de orden superior a 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 primordiales, 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 afectarán menos a las propiedades espectrales y otras propiedades de la gaussiana que un simple truncamiento. No obstante, 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 del truncamiento dejen de ser importantes.

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

${\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${\displaystyle I_{n}(t)}$denota las funciones de Bessel modificadas de orden entero, n . Esta es la contraparte discreta de la gaussiana continua, ya 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. ^{[ 3 ] [ 4 ] [ 6 ]}

Este filtro puede truncarse en el dominio espacial como en el caso de la gaussiana muestreada.

${\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 escalas se transfieren exactamente al dominio discreto, o con una excelente aproximación utilizando una extensión periódica y una transformada de Fourier discreta suficientemente 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 directa (y preservando las propiedades del espacio de escalas) aplicando operadores de diferencias centrales de soporte pequeño a la representación del espacio de escalas discretas . ^{[ 7 ]}

Al igual que con la gaussiana muestreada, una simple truncación de la respuesta de impulso infinita 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 comienzan a aparecer efectos del error de truncamiento (por ejemplo, como extremos espurios o respuestas espurias a operadores de derivada 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 es muy pequeño, o utilizar una ventana cónica.

Dado que la eficiencia computacional suele ser importante, a menudo se utilizan filtros recursivos de bajo orden para el suavizado en el espacio de escalas. Por ejemplo, Young y van Vliet ^{[ 8 ]} 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 obtener 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 ^{[ 3 ]} 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 en 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 frecuencia de Pólya normalizado que funciona para cualquier escala de suavizado, pero no es una aproximación tan excelente a la gaussiana como el filtro de Young y van Vliet, que no es una secuencia de frecuencia de Pólya normalizada, debido a sus polos complejos.

La función de transferencia, H ₁ , de un filtro recursivo de pares de polos simétrico está estrechamente relacionada con la transformada de Fourier de tiempo discreto del núcleo gaussiano discreto a través de 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 del polo estable Z = p mediante:

${\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 impulsionales de estos filtros no se aproximan mucho a una distribución gaussiana 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 se aproximará mucho a una señal suavizada mediante una distribución gaussiana. La propiedad de semigrupo se aproxima de forma deficiente cuando se utilizan muy pocos pares de polos.

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

• linealidad
• Invariancia de desplazamiento (desplazamientos 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

Las siguientes condiciones se cumplen solo 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 la aproxima, mapea aproximadamente una respuesta de filtro recursivo a una 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 exactamente iguales).
• simetría rotacional
• invariancia de escala

Este método de filtro recursivo y sus variaciones para calcular tanto el suavizado gaussiano como las derivadas gaussianas han sido descritos por varios autores. ^{[ 8 ] [ 9 ] [ 10 ] [ 11 ]} 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. ^{[ 12 ]}

A escalas finas, ni el método de filtrado recursivo ni otros métodos separables garantizan la mejor aproximación posible a la simetría rotacional, por lo que se pueden considerar implementaciones no separables para imágenes 2D como alternativa.

Al calcular simultáneamente varias derivadas en el N-jet , el suavizado discreto del espacio de escalas con el análogo discreto del núcleo gaussiano, o con una aproximación de filtro recursivo, seguido de operadores de diferencia de soporte pequeño, puede ser más rápido y más preciso que el cálculo de aproximaciones recursivas de cada operador de derivada.

Para escalas pequeñas, un filtro FIR de orden bajo puede ser un mejor filtro de suavizado que un filtro recursivo. El núcleo simétrico de 3 núcleos [ t /2, 1- t , t /2] , para t ≤ 0,5 suaviza a una escala de t usando un par de ceros reales en Z < 0, y se aproxima a la gaussiana discreta 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 pueden usarse 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 biquad (dos polos, dos ceros) hacia adelante y luego hacia atrás en cada fila de datos (y en cada columna en el caso 2D), tanto los polos como los ceros pueden realizar una parte del suavizado. Los ceros tienen un límite de t = 0,5 por par (ceros en Z = –1), por lo que, a grandes escalas, los polos realizan la mayor parte del trabajo. A escalas más finas, la combinación proporciona una excelente aproximación a la gaussiana discreta si tanto los polos como los ceros realizan aproximadamente la mitad del suavizado. Los valores de t para cada parte del suavizado (polos, ceros, aplicaciones múltiples hacia adelante y hacia atrás, etc.) son aditivos, de acuerdo con la propiedad de semigrupo aproximado.

La función de transferencia del filtro FIR está estrechamente relacionada con la DTFT del filtro gaussiano discreto, 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 mediante:

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

y requerimos que t ≤ 0,5 para que la función de transferencia siga siendo 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 polos y ceros son núcleos de espacio de escalas válidos, que satisfacen los mismos axiomas que los filtros recursivos de polos.

En cuanto al tema de la selección automática de escala basada en derivadas normalizadas, las aproximaciones piramidales se utilizan frecuentemente para obtener un rendimiento en tiempo real. ^{[ 13 ] [ 14 ] [ 15 ]} La idoneidad de aproximar las operaciones del espacio de escalas 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, bajo condiciones razonables, se aproximan a la gaussiana. Además, se puede demostrar que los núcleos binomiales (o, más generalmente, la clase de núcleos binomiales generalizados) constituyen la única clase de núcleos de soporte finito que garantizan la no creación de extremos locales o cruces por cero con el aumento de la escala (véase el artículo sobre enfoques multiescala para más detalles). Sin embargo, puede ser necesario tener especial cuidado para evitar artefactos de discretización.

Para núcleos unidimensionales, existe una teoría bien desarrollada de enfoques multiescala , que abarca filtros que no generan nuevos extremos locales ni nuevos cruces por cero al aumentar la escala. Para señales continuas, los filtros con polos reales en el plano s pertenecen a esta clase, mientras que para señales discretas, los filtros recursivos y FIR descritos anteriormente satisfacen estos criterios. Junto con el requisito estricto de una estructura de semigrupo continua, la gaussiana continua y la gaussiana discreta constituyen la única opción para señales continuas y discretas, respectivamente.

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 ondículas y diversos núcleos, que no aprovechan ni requieren los mismos requisitos que las descripciones del espacio de escalas ; es decir, no dependen de que una escala más gruesa no genere un nuevo extremo que no estuviera presente en una escala más fina (en 1D) o de que no se produzca una mejora de los extremos locales entre niveles de escala adyacentes (en cualquier número de dimensiones).

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

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