El esquema de elevación es una técnica tanto para diseñar ondículas como para realizar la transformada de ondículas discretas (DWT). En una implementación, a menudo vale la pena fusionar estos pasos y diseñar los filtros de ondículas mientras se realiza la transformación de ondículas. A esto se le llama entonces la transformada wavelet de segunda generación . La técnica fue introducida por Wim Sweldens . [1]
El esquema de elevación factoriza cualquier transformada de ondícula discreta con filtros finitos en una serie de operadores de convolución elementales, los llamados pasos de elevación, que reducen el número de operaciones aritméticas en casi un factor dos. El tratamiento de los límites de la señal también se simplifica. [2]
La transformada de ondículas discretas aplica varios filtros por separado a la misma señal. En contraste con eso, para el esquema de elevación, la señal se divide como una cremallera. Luego, se aplica una serie de operaciones de acumulación de convolución a través de las señales divididas.
Lo esencial
La versión más simple de una transformada de ondícula directa expresada en el esquema de elevación se muestra en la figura anterior. significa predecir paso, que se considerará de forma aislada. El paso de predicción calcula la función de ondícula en la transformada de ondícula. Este es un filtro de paso alto. El paso de actualización calcula la función de escalado, lo que da como resultado una versión más suave de los datos.
Como se mencionó anteriormente, el esquema de elevación es una técnica alternativa para realizar el DWT utilizando ondas biortogonales. Para realizar el DWT utilizando el esquema de elevación, los pasos de elevación y escala correspondientes deben derivarse de las ondas biortogonales. Los filtros de análisis () de la ondícula particular se escriben primero en una matriz polifásica
dónde .
La matriz polifásica es una matriz de 2 × 2 que contiene los filtros de paso bajo y paso alto de análisis, cada uno dividido en sus coeficientes polinomiales pares e impares y normalizados. A partir de aquí, la matriz se factoriza en una serie de matrices triangulares superior e inferior de 2 × 2, cada una con entradas diagonales iguales a 1. Las matrices triangulares superiores contienen los coeficientes para los pasos de predicción, y las matrices triangulares inferiores contienen los coeficientes para los pasos de actualización. Se puede extraer una matriz que consta de todos ceros con la excepción de los valores diagonales para derivar los coeficientes del paso de escala. La matriz polifásica se factoriza en la forma
dónde es el coeficiente del paso de predicción, y es el coeficiente del paso de actualización.
A continuación se muestra un ejemplo de una extracción más complicada que tiene múltiples pasos de predicción y actualización, así como pasos de escala; es el coeficiente del primer paso de predicción, es el coeficiente del primer paso de actualización, es el coeficiente para el segundo paso de predicción, es el coeficiente del segundo paso de actualización, es el coeficiente de escala de muestra impar, y es el coeficiente de escala de muestras pares:
De acuerdo con la teoría de matrices, cualquier matriz que tenga entradas polinómicas y un determinante de 1 se puede factorizar como se describió anteriormente. Por lo tanto, cada transformada de ondículas con filtros finitos se puede descomponer en una serie de pasos de elevación y escalado. Daubechies y Sweldens discuten la extracción con escalón de elevación con más detalle. [3]
Filtro CDF 9/7
Para realizar la transformación CDF 9/7, se requieren un total de cuatro pasos de elevación: dos de predicción y dos de actualización. La factorización de elevación conduce a la siguiente secuencia de pasos de filtrado. [3]
Propiedades
Reconstrucción perfecta
Cada transformación del esquema de elevación se puede invertir. Cada banco de filtros de reconstrucción perfecta se puede descomponer en pasos de elevación mediante el algoritmo euclidiano . Es decir, "banco de filtros descomponible por elevación" y "banco de filtros de reconstrucción perfecta" denotan lo mismo. Cada dos bancos de filtros de reconstrucción perfecta se pueden transformar entre sí mediante una secuencia de pasos de elevación. Para una mejor comprensión, si y son matrices polifásicas con el mismo determinante, entonces la secuencia de elevación de a es el mismo que el de la matriz polifásica perezosa a .
Acelerar
La aceleración se multiplica por dos. Esto solo es posible porque la elevación se limita a los bancos de filtros de reconstrucción perfecta. Es decir, el levantamiento elimina de alguna manera las redundancias causadas por una reconstrucción perfecta.
La transformación se puede realizar inmediatamente en la memoria de los datos de entrada (en el lugar, in situ) con solo una sobrecarga de memoria constante.
No linealidades
Las operaciones de convolución pueden ser reemplazadas por cualquier otra operación. Para una reconstrucción perfecta, solo es relevante la invertibilidad de la operación de adición. De esta manera se pueden tolerar los errores de redondeo en la convolución y es posible la reconstrucción con bits exactos. Sin embargo, la estabilidad numérica puede verse reducida por las no linealidades. Esto debe respetarse si la señal transformada se procesa como en una compresión con pérdida . Aunque cada banco de filtros reconstruible puede expresarse en términos de pasos de elevación, una descripción general de los pasos de elevación no es obvia a partir de una descripción de una familia de ondículas. Sin embargo, por ejemplo, para casos simples de la ondícula de Cohen-Daubechies-Feauveau , existe una fórmula explícita para sus pasos de elevación.
Aumento de los momentos de desaparición, la estabilidad y la regularidad.
Un levantamiento modifica los filtros biortogonales para aumentar el número de momentos de desaparición de las ondas biortogonales resultantes y, con suerte, su estabilidad y regularidad. Aumentar el número de momentos de fuga disminuye la amplitud de los coeficientes de ondas en las regiones donde la señal es regular, lo que produce una representación más escasa. Sin embargo, aumentar el número de momentos de fuga con un levantamiento también aumenta el soporte de la ondícula, lo cual es un efecto adverso que aumenta el número de coeficientes grandes producidos por singularidades aisladas. Cada paso de elevación mantiene la biortogonalidad del filtro pero no proporciona control sobre los límites de Riesz y, por lo tanto, sobre la estabilidad de la base biortogonal de ondículas resultante. Cuando una base es ortogonal, la base dual es igual a la base original. Tener una base dual que sea similar a la base original es, por tanto, una indicación de estabilidad. Como resultado, la estabilidad generalmente mejora cuando las ondas duales tienen tantos momentos de fuga como las ondas originales y un soporte de tamaño similar. Esta es la razón por la que un procedimiento de elevación también aumenta el número de momentos de fuga de ondas duales. También puede mejorar la regularidad de la onda dual. Un diseño de elevación se calcula ajustando el número de momentos de fuga. La estabilidad y regularidad de las ondas biortogonales resultantes se miden a posteriori, esperando lo mejor. Ésta es la principal debilidad de este procedimiento de diseño de ondículas.
Levantamiento generalizado
El esquema de levantamiento generalizado fue desarrollado por Joel Solé y Philippe Salembier y publicado en la tesis doctoral de Solé. [4] Se basa en el esquema de elevación clásico y lo generaliza rompiendo una restricción oculta en la estructura del esquema. El esquema de elevación clásico tiene tres tipos de operaciones:
- Una transformada de ondas perezosas divide la señal en dos nuevas señales: la señal de muestras impares denotada por y la señal de muestras pares denotada por .
- Un paso de predicción calcula una predicción para las muestras impares, basándose en las muestras pares (o viceversa). Esta predicción se resta de las muestras impares, creando una señal de error..
- Un paso de actualización recalibra la rama de baja frecuencia con parte de la energía eliminada durante el submuestreo. En el caso del levantamiento clásico, esto se usa para "preparar" la señal para el siguiente paso de predicción. Utiliza las muestras impares predichas para preparar los pares (o viceversa). Esta actualización se resta de las muestras pares, produciendo la señal denotada por.
El esquema es invertible debido a su estructura. En el receptor , el paso de actualización se calcula primero con su resultado agregado nuevamente a las muestras pares, y luego es posible calcular exactamente la misma predicción para agregar a las muestras impares. Para recuperar la señal original, la transformada de ondícula perezosa debe invertirse. El esquema de elevación generalizado tiene los mismos tres tipos de operaciones. Sin embargo, este esquema evita la restricción de suma-resta que ofrecía el lifting clásico, lo que tiene algunas consecuencias. Por ejemplo, el diseño de todos los pasos debe garantizar la invertibilidad del esquema (no garantizado si se evita la restricción de suma-resta).
Definición
El esquema de elevación generalizado es una transformación diádica que sigue estas reglas:
- Desintercala la entrada en un flujo de muestras pares y otro flujo de muestras impares. A esto a veces se le denomina Transformada Lazy Wavelet .
- Calcula una asignación de predicción . Este paso intenta predecir muestras impares teniendo en cuenta las pares (o viceversa). Hay un mapeo del espacio de las muestras en al espacio de las muestras en . En este caso las muestras (de) elegido para ser la referencia para se llaman el contexto . Podría expresarse como:
- Calcula una asignación de actualización . Este paso intenta actualizar las muestras pares teniendo en cuenta las muestras predichas impares. Sería una especie de preparación para el siguiente paso de predicción, si lo hubiera. Podría expresarse como:
Obviamente, estas asignaciones no pueden ser funciones. Para garantizar la invertibilidad del esquema en sí, todas las asignaciones involucradas en la transformación deben ser invertibles. En caso de que surjan mapeos y lleguen a conjuntos finitos (señales de valores acotados discretos), esta condición equivale a decir que los mapeos son inyectivos (uno a uno). Además, si un mapeo va de un conjunto a un conjunto de la misma cardinalidad, debería ser biyectivo .
En el Esquema de levantamiento generalizado, la restricción de suma / resta se evita al incluir este paso en el mapeo. De esta forma se generaliza el Esquema de Levantamiento Clásico.
Diseño
Se han desarrollado algunos diseños para el mapeo de pasos de predicción. El diseño del paso de actualización no se ha considerado tan a fondo, porque queda por responder en qué medida es útil exactamente el paso de actualización. La principal aplicación de esta técnica es la compresión de imágenes. Hay algunas referencias interesantes como, [5] [6] [7] y. [8]
Aplicaciones
- Wavelet transforma ese mapeo de enteros a enteros
- Transformada de Fourier con reconstrucción de bits exactos [9]
- Construcción de ondas con un número requerido de factores de suavidad y momentos de fuga.
- Construcción de ondículas adaptadas a un patrón dado [10]
- Implementación de la transformada de ondículas discretas en JPEG 2000
- Transformaciones impulsadas por datos, p. Ej., Wavelets que evitan los bordes [11]
- Transformaciones de ondículas en celosías no separables , por ejemplo, ondículas rojo-negras en la celosía de quincunx [12]
Ver también
- El esquema de Feistel en criptología utiliza la misma idea de dividir datos y alternar la aplicación de funciones con la suma. Tanto en el esquema de Feistel como en el esquema de elevación, se utiliza para la codificación y decodificación simétricas.
Referencias
- ^ Sweldens, Wim (1997). "El esquema de elevación: una construcción de wavelets de segunda generación" (PDF) . Revista de análisis matemático . 29 (2): 511–546. doi : 10.1137 / S0036141095289051 .
- ^ Mallat, Stéphane (2009). Un recorrido Wavelet por el procesamiento de señales . Prensa académica. ISBN 978-0-12-374370-1.
- ^ a b Daubechies, Ingrid ; Sweldens, Wim (1998). "Factorizar las transformaciones de Wavelet en pasos de elevación" (PDF) . Revista de análisis y aplicaciones de Fourier . 4 (3): 247–269. doi : 10.1007 / BF02476026 .
- ^ Doctorado. disertación: Optimización y generalización de esquemas de elevación: aplicación a la compresión de imágenes sin pérdida .
- ^ Rolon, JC; Salembier, P. (7-9 de noviembre de 2007). "Lifting generalizado para codificación y representación de imágenes dispersas" . Simposio de codificación de imágenes, PCS 2007 .
- ^ Rolon, JC; Salembier, P .; Alameda, X. (12 al 15 de octubre de 2008). "Compresión de imagen con Lifting Generalizado y conocimiento parcial de la señal pdf" (PDF) . Congreso Internacional de Procesamiento de Imágenes, ICIP'08 .
- ^ Rolon, JC; Ortega, A .; Salembier, P. "Modelado de contornos en el dominio Wavelet para compresión de imagen de elevación generalizada" (PDF) . ICASSP 2009 (presentado) .
- ^ Rolon, JC; Mendonça, E .; Salembier, P. Levantamiento generalizado con estimación de pdf local adaptable para codificación de imágenes (PDF) .
- ^ Oraintara, Soontorn; Chen, Ying-Jui; Nguyen, Truong Q. (2002). "Transformada de Fourier rápida entera" (PDF) . Transacciones sobre procesamiento de señales . 50 (3): 607–618. doi : 10.1109 / 78.984749 .
- ^ Thielemann, Henning (2004). "Wavelets óptimamente emparejados" . Procedimientos en Matemática Aplicada y Mecánica . 4 : 586–587. doi : 10.1002 / pamm.200410274 .
- ^ Fattal, Raanan (2009). "Wavelets para evitar bordes y sus aplicaciones" . Transacciones ACM en gráficos . 28 (3): 1. CiteSeerX 10.1.1.205.8462 . doi : 10.1145 / 1531326.1531328 .
- ^ Uytterhoeven, Geert; Bultheel, Adhemar (1998). La Transformada Wavelet Rojo-Negro . Simposio de procesamiento de señales (IEEE Benelux). págs. 191-194.
enlaces externos
- Lifting Scheme : breve descripción del algoritmo de factorización
- Introducción al esquema de elevación