PDF de programación - Desarrollo de predictor de píxel adaptativo para mapas de bits

Desarrollo de predictor de píxel
adaptativo para mapas de bits

Development of adaptive pixel predictor for bitmaps

Javier Garduño Cimental
[email protected]

Resumen:

Los mapas de bits, por naturaleza, consumen gran cantidad de espacio de almacenamiento. Si bien se

han desarrollado muy diversos y sofisticados métodos de compresión para los mismos, han quedado
relegados los métodos destinados a una compresión sin pérdida de información. El resultado de este
trabajo pretende paliar esta carencia.

Considerando que no es posible comprimir cualquier ráfaga de datos de un tamaño particular a
uno más pequeño, y que un mapa de bits puede ser cualquier arreglo arbitrario de valores, se analizan
algunos supuestos y principios asociados a las imágenes que pueden tener algún sentido para el obser-
vador, de manera que sea posible conseguir que dicho subconjunto, el de las imágenes con sentido, sea
el favorecido por algún algoritmo compresor.

El mecanismo ideado es un predictor de pixel, un algoritmo destinado a transformar los datos ori-
ginales de un mapa de bits, sin que esto conlleve a una pérdida de información en los mismos. El resul-
tado es un nuevo conjunto de datos con menor entropía que los datos originales, cualidad que favorece
su compresión.

sense to the observer, so that it is possible to make
this subset, the images with meaning, favored by
any compressor algorithm.

The mechanism developed is a predictor of
pixel, an algorithm designed to transform the ori-
ginal data of a bitmap, without this leading to a
loss of information therein. The result is a new set
of data with less entropy than the original data, a
quality that enhances their compression.

Keywords:

Algorithm, compression, image, mathematics,

predictor, bitmap, heuristic, pixel.

Palabras clave:

Algoritmo, compresión, imagen, matemáticas,

predictor, mapa de bits, heurística, pixel.

Abstract:

Bitmaps, by nature, consume lots of storage
space. While many have developed very sophis-
ticated compression methods for them, those
methods for lossless compression of information
have been left behind. The result of this paper aims
to fill this gap.

Whereas it is not possible to compress any
data burst of a particular size to a smaller, and that
a bitmap can be any arbitrary arrangement of va-
lues, we analyze some assumptions and principles
associated with the images that might make some

núm. 11, 2012, pp. 97-118

97

Introducción

motivo, es ideal la compresión de la información que constituye dicha imagen.

Los mapas de bits consumen gran cantidad de espacio de almacenamiento. Por tal

Si bien existen muchos métodos de compresión, la mayoría de ellos están
diseñados para realizar una reducción de tamaño con pérdida de información, quedando
relegados los métodos que realizan la misma tarea sin pérdida de la misma.

Normalmente, estos últimos incluyen un proceso encargado de transformar la infor-
mación a fin de facilitar el alcance de mejores tasas de compresión. Sin embargo, dichos
procesos son en extremo simples.

Con la creación de este algoritmo se pretende llenar el nicho creado por las técnicas
usadas tradicionalmente. El objetivo es encontrar una forma de transformar un mapa de
bits (imagen) de forma que coadyuve a mejorar su compresión utilizando un algoritmo
tradicional de compresión entrópica (Huffman)1, o similar.

Entendiendo la compresión

La compresión de datos hace referencia a la habilidad de reducir la cantidad de bits utiliza-
dos en el almacenamiento de tales datos. Por tasa de compresión se hace referencia a la razón
que existe entre el tamaño original de los datos y el tamaño de la versión comprimida de
los mismos. Es decir:

Donde C es la tasa de compresión, D es el tamaño original de los datos, y d es el tama-

ño de los datos comprimidos. Mayores valores de C son mejores.

En la teoría de la información, la información es tratada como una magnitud. Es cuantifi-
cable, y para caracterizar la información de una secuencia de símbolos, que es la manera en
que se almacena los datos de un mapa de bits, se utiliza la entropía.

La entropía y la no inyectividad de la compresión son conceptos de suma importancia en

el desarrollo de este trabajo.

Entropía

Se refiere al grado de incertidumbre que existe en la aparición de símbolos en una

secuencia de símbolos.

1 Huffman, D.A., A method for the construction of minimum-redundancy codes. En Resonance, vol 11 núm 2, pp 91–99, 2006.

98

Gabino Eduardo Castrejón GarcíaJavier Garduño Cimental Definición formal de entropía2

La entropía medida en bits se define formalmente como:

Donde:

p(xi) es la probabilidad de que la variable discreta x se encuentre en el estado xi. El
conjunto de todos los xi representa los n símbolos posibles que puede contener una cadena
de símbolos.

No inyectividad de la compresión

Para todos los casos una secuencia de símbolos, como la que podría estar almacenando
una imagen, se codifica como una secuencia de bits. Dicha secuencia ordenada se puede
considerar un número de base 2. Teniendo esto en cuenta, podemos establecer la siguiente
propiedad general:

Sea M el conjunto de todos los números de base n que se pueden escribir con m dígitos.

Sea K el conjunto de todos los números de base n que pueden ser escritos con k dígitos.

Donde:

Para cada M existen exactamente m - 1 subconjuntos K. Llámese Tm al conjunto que

contiene a dichos conjuntos K, quedando definido como:

Al ser disjuntos los conjuntos Ki, el conjunto Tm posee una cardinalidad:

2 Shannon, Claude E., A Mathematical Theory of Comunication, en The Bell System Technical Journal, vol 27, pp 379–423, 623–653, Julio -
Octubre 1948.

99

LA RESPONSABILIDAD PATRIMONIAL DEL ESTADODESARROLLO DE PREDICTOR DE PÍXEL ADAPTATIVO PARA MAPAS DE BITS Matemáticas e Ingeniería La cardinalidad de Tm no es otra cosa que la suma de la cardinalidad de cada uno de los

subconjuntos Ki que lo constituyen.

Llamemos regla de compresión a la función C que, recibiendo como entrada un elemento
de M, dé como resultado un elemento de Tm, tal que para cada elemento de Tm generado por
C, exista uno y sólo un elemento de M que lo haya generado.

Por tal motivo, la función C no puede generar un elemento de Tm para todos y cada
uno de los elementos de M. De lo que se concluye que no todo elemento de M puede ser
asociado a un elemento de cualquier conjunto K de forma inyectiva. Además, nos muestra
una relación inversa entre la razón de compresión y la fracción de datos que se pueden
comprimir. En otras palabras, podemos decir lo siguiente:

Lema 1. No es posible que todos los datos de tamaño m se compriman a un tamaño

menor k, siempre que sea utilizada la misma regla de compresión.

Lema 2. A mayor tasa de compresión, menor la cantidad de conjuntos de datos que

pueden alcanzarla.

Obtención del predictor de pixel

En muchos casos, la información que posee un flujo de datos ha sido generada por un
proceso no aleatorio. Esto convierte a dicho flujo de datos en algo potencialmente predecible.
La predictibilidad de la información abre la posibilidad de reducir su entropía.

Con todo lo anterior presente, se pretende crear un predictor de pixel que cumpla las

siguientes funciones:

•

•

Explotar el orden y características intrínsecas que poseen las imágenes, con el fin de
predecir su comportamiento, generando en el proceso un nuevo flujo de datos con
menor entropía, facilitando así su compresión.

Servir como método de discriminación, alentando la compresión del subconjunto de
imágenes que tengan sentido para el observador, sobre las imágenes carentes de él.

Propósito del predictor de pixel

Su objetivo es transformar el conjunto de datos que constituyen un mapa de bits, de
forma que la aplicación de un método de compresión resulte en un conjunto de datos más
pequeño. La forma de conseguirlo es prediciendo el valor de los pixeles, almacenando sola-
mente las diferencias que posea con respecto al valor real.

Se desea además que la compresión resultante sea “sin pérdida”. Para que todo ello

resulte posible deben cumplirse las siguientes condiciones:

100

Gabino Eduardo Castrejón GarcíaJavier Garduño Cimental Condición 1. El predictor debe realizar una transformación sin pérdida de información.
Condición 2. El predictor debe poseer inversa. Es decir, debe ser posible obtener los

datos de la imagen original a partir del nuevo flujo de datos generado por el predictor.

Supuestos

Al hablarse de imagen, se hará referencia a un gráfico constituido por un solo canal de
color. Para imágenes que contengan un número mayor de canales, como las imágenes en
color, se utilizará el término imagen multicanal.

Imagen ideal

Una imagen ideal puede ser concebida como un campo escalar, donde el valor asociado
donde su valor depende de

a cada punto es su brillo correspondiente. Es una función
la posición (x, y) considerada. Se puede expresar como:

Donde

es un vector de coordenadas cartesianas (x, y) que representa cada punto de
la imagen ideal. Un mapa de bits puede ser concebido como un muestreo de la función Φ
donde cada muestra corresponde a un pixel.

Imágenes posibles e imágenes con sentido

Un mapa de bits puede ser cualquier arreglo de valores, pero no resulta interesante ni
necesario tener la capacidad de comprimir todas las imágenes posibles. No todas las imágenes
posibles tienen sentido para el observador. El propósito será, por tanto, encontrar un método
que permita discriminar entre ambos tipos de imágenes: las que tienen “sentido” de las que
no. De forma que el pequeño conjunto de imágenes con sentido sea el subconjunto de imáge-
nes posibles que se compriman más.

La definición de imagen con sentido es vaga hasta ahora. La pregunta entonces es: ¿qué
significa exactamente imagen con sentido? Es necesario definir el concepto de manera formal.
Para definir a una imagen con sentido, n