29 noviembre 2010

DPCM (Differential Pulse Code Modulation), Método diferencial para compresión de señales, Parte I, puro rollo

La teoría del siguiente choro mareador y las figuras pirateadas fueron tomad@s de:
Data Compression: The Complete Reference. David Salomon. Fourth Edition. Springer. 2007. Section 4.26: DPCM
Digital Signal Processing: Fundamentals and Applications. Li Tan. Academic Press. 2008. Section 11.3: Examples of Differential Pulse Code Modulation, and Adaptive DPCM G.721

La compresión por DPCM es parte de la familia de métodos compresión por codificación diferencial. La idea general es usar valores pasados recuperados como base para predecir el dato actual de entrada. Esto se basa en el hecho, por ejemplo, que los pixeles en una imagen o muestras adyacentes en el audio digitalizado se encuentran correlacionadas. Los valores correlacionados son generalmente similares, así que sus diferencias son pequeñas, esto resultando en una compresión.
A continuación se muestra el esquema simple de compresión diferencial para poder entender el principio del DPCM.

image

                           Codificador                                 Decodificador
Figura 1. CoDec Diferencial

La imagen anterior muestra un ejemplo de un codificador diferencial, se observa como el dato actual image se almacena en una unidad de almacenamiento, llámese “Delay” (o retardo pues si no les gusta agringarse), para ser usado para codificar el siguiente dato, o sea, image. Claro, la explicación anterior esta sumamente simplificada, en este ejemplo se muestra el uso de un cuantizador, eso significa que se tiene una compresión con perdidas o “lossy” y esto significa que nuestro dato codificado es realmente image el cual ya contiene un error de cuantización. Esto significa que la codificación por diferencias (o diferencial, como ustedes gusten y manden) nos mete en un nuevo problema: La acumulación de errores.
Entonces hay que tomar ventaja de lo que se menciona anteriormente, los datos que se van a comprimir están correlacionados. Esto significa que en general un dato depende de varios de sus vecinos, no solamente del anterior. Una mejor predicción puede ser lograda usando N de los datos previos para codificar el valor actual image, entonces tendremos una función image image, para predecir el dato actual image.
Ora si, en seguida pueden observar (jeje, como visita al museo) el diagrama del DPCM. (oooooohhhh!)

image
                          Codificador                                   Decodificador
Figura 2. DPCM
Oquey, oquey, haber encuentren la(s) diferencia(s) entre la Figura 1 y la Figura 2. ¿Está fácil? ¿que no? …
Pues si, cambiamos “Delay” por “Pred.” y se acabo el asunto.
Si.
Como se explicaba antes, el predictor viene siendo la funcioncica esta:
imageimage
En donde tenemos que es una función que nos afecta un conjunto de N pixeles y en base a esto obtenemos una mejor predicción de nuestro valor actual, es decir tratamos de minimizar el error introducido por la cuantificación.
Esta es la primera parte de dos, en esta ocasión fue el rollo previo a un ejemplo peque para poder explicar la DPCM.

This is I

Blog dedicado a escribir sobre Sistemas Embebidos y el Internet de las Cosas o IoT que le llaman.