1.1 Filas
a. Secuencias
Cada fila de una imagen consiste en una sucesión de secuencias maximales de puntos tales que los puntos en cada secuencia tienen todos el mismo valor. Así la fila está completamente determinada mediante la especificación de las longitudes y los valores de estas secuencias. Si hay sólo unas pocas secuencias, esta representación es muy económica; por esta razón, la codificación de la longitud de la secuencia se usa algunas veces para compresión de imágenes. Por ejemplo, supongamos que la fila tiene una longitud n, y que hay r secuencias. Puesto que son necesarios log2 n bits para especificar la longitud de una secuencia (puede tener cualquier longitud entre 1 y n), el número de bits necesarios para especificar todas las longitudes de secuencias es r log2 n. Así si hay m posibles valores, esta representación de la fila requiere r (log2 n + log2 m) bits, en contraposición con los n log2 m bits que son necesarios cuando la fila es tratada como una cadena de longitud n.
Cuando m = 2, necesitamos sólo especificar el valor de la primera secuencia en la fila, puesto que los valores deben alternarse. Así la especificación de la longitud de la secuencia de una fila en una imagen binaria requiere 1 + r log2 n bits, frente a los n bits necesarios para representar la fila como una cadena de bits. Nótese que estos ahorros son solamente uni-dimensionales; para una imagen de n ´ n, si el número medio de secuencias en cada fila es r, el número total de bits necesarios por la representación de la longitud de la secuencia es n(1 + r log2 n) frente a los n2 necesarios en el caso binario o nr(log2 m + log2 n) frente a n2 log2 m en el caso general.
b. Árboles
binarios
Supongamos, para simplificar, que la longitud de la fila es una potencia de 2, digamos n = 2k. Describiremos ahora un método para representar la fila mediante un árbol binario, cada una de cuyas hojas corresponde a una secuencia (no necesariamente maximal) de valor constante cuya longitud es una potencia de 2, digamos 2i, y cuya coordenada de posición es un múltiplo de 2i.
El nodo raíz del árbol representa la fila entera. Si toda la fila tiene un valor, etiquetamos el nodo raíz con ese valor y paramos; en este caso, el árbol consiste sólo en el nodo raíz. En otro caso, añadimos dos descendientes al nodo raíz, representando las dos mitades de la fila. El proceso se repite entonces para cada uno de esos nuevos nodos: si su mitad de la fila tiene valor constante, lo marcamos con ese valor y no le damos ningún descendiente; si no, le damos dos descendientes correspondientes a las dos mitades de su mitad. En general, en el nivel h del árbol (donde la raíz está al nivel 0), los nodos (si hay alguno) representan partes de la fila de longitud 2k-h, en posiciones que son múltiplos de 2k-h . Si una parte tiene valor constante, su nodo es un nodo hoja (i.e., no tiene descendientes), marcados con ese valor; en otro caso, ese nodo tiene dos descendientes correspondientes a las dos mitades de la parte. A nivel k, los nodos (si hay alguno) corresponden a píxeles únicos, y son todos nodos hoja, marcados con los valores de sus píxeles.
Un ejemplo simple de una cadena y el correspondiente árbol binario se muestra en la figura 1. Nótese que los bloques de valor constante correspondientes a los nodos hoja del árbol no son necesariamente secuencias maximales; si la longitud de una secuencia no es una potencia de 2, o si la posición de comienzo no es un múltiplo de la apropiada potencia de 2, se representa por más de un nodo de hoja.
Fig. 1
Representación binaria de una cadena. (a) Cadena binaria de longitud 32.
(b) Árbol; los círculos rellenos y huecos son nodos hoja correspondientes a
bloques de 1’s y 0’s respectivamente. Hay 39 nodos, 20 de los cuales son nodos
hoja. (c) Representación en paréntesis del árbol. La representación de la
longitud de secuencia de esta cadena es 1:1,2,1,1,2,1,8,1,1,2,1,1,6,1,2,1, donde
el 1 inicial representa el hecho de que la cadena empieza con una secuencia de
1s; hay 16 secuencias.
El espacio necesario para almacenar el árbol es proporcional al número de nodos. (Por ejemplo, el árbol puede ser representado por una cadena de paréntesis en la que cada nodo se mapea en un par de paréntesis encerrando la subcadena que representa el subárbol enraizado en ese nodo, como se ilustra en la Figura 1c. Los nodos hoja pueden ser representados mediante sus valores asociados). Si la fila consta sólo de unas pocas secuencias, el árbol tendrá relativamente pocos nodos, pero el número exacto depende de las posiciones y longitudes de las secuencias.
La representación en árbol binario de las filas de una imagen no parece haber sido utilizada en la práctica. Se ha presentado aquí como un preliminar a la representación bi-dimensional del árbol de cuadrados en la sección 1.2b.