El problema fundamental que Nibnib aborda es la descompresión de imágenes en tiempo real en entornos computacionalmente restringidos, donde el presupuesto de ciclos por píxel es extremadamente limitado (aproximadamente 6 ciclos). En estos contextos, los formatos de imagen tradicionales son inviables debido a su complejidad algorítmica y requisitos de memoria. Nibnib resuelve esto mediante un enfoque de descompresión simplificado y determinista que procesa múltiples píxeles por operación de lectura, aprovechando la naturaleza del hardware de baja potencia.
La relevancia actual de este problema radica en la proliferación de dispositivos embebidos y IoT que requieren interfaces gráficas de usuario (GUI) eficientes y de bajo consumo. Aunque la potencia de procesamiento ha aumentado, la demanda de eficiencia energética y la necesidad de mantener bajos los costos de hardware impulsan la búsqueda de algoritmos de procesamiento de medios que minimicen la carga de la CPU y la memoria. Nibnib se posiciona como una solución para estos casos de uso, donde la latencia de descompresión es crítica para una experiencia de usuario fluida.
Arquitectura del Sistema
La arquitectura de Nibnib se centra en un proceso de descompresión de imágenes basado en una paleta de deltas y un procesamiento de píxeles en pares. El formato de archivo es minimalista: 2 bytes para el ancho, 2 bytes para la altura, seguidos de 256 entradas de paleta de 32 bits, y luego los datos de las filas. Cada fila comienza con dos píxeles iniciales (RGB 565), seguidos por bytes que indexan la paleta, con un relleno para alinear la fila a múltiplos de 4 bytes.
El algoritmo de descompresión opera leyendo un byte del flujo de entrada, que se utiliza como índice para una paleta de 256 entradas. Cada entrada de la paleta contiene un valor delta de 32 bits. Este delta se suma al último píxel decodificado (duplicado), produciendo dos nuevos píxeles de 16bpp (RGB 565). El bit menos significativo del resultado es el píxel izquierdo, y el bit más significativo es el píxel derecho. Este enfoque de 'delta coding' en la paleta, en lugar de colores absolutos, permite una mayor fidelidad de color en regiones suaves con un tamaño de paleta fijo. La clave de la velocidad es la decodificación de dos píxeles por cada byte de entrada, logrando una compresión efectiva de 4 bits por píxel (4bpp).
El proceso de codificación es asimétrico y significativamente más lento que la descompresión. Implica una búsqueda exhaustiva para seleccionar la paleta óptima y los 'codewords' (índices de paleta) que minimicen el error de reconstrucción. Utiliza una técnica similar a la difusión de error (como Floyd-Steinberg) pero adaptada para operar en pares de píxeles, priorizando la reducción del error total sobre la diferencia individual de píxeles, lo que se alinea con la sensibilidad del sistema visual humano a las bajas frecuencias espaciales.
Flujo de Descompresión de Píxeles Nibnib
- 1 Inicializar Cargar los primeros dos píxeles de la imagen de entrada y establecer el 'píxe...
- 2 Leer Byte de Entrada Obtener un byte del flujo de datos comprimidos.
- 3 Lookup de Paleta Usar el byte como índice para obtener un valor delta de 32 bits de la paleta.
- 4 Duplicar Píxel Anterior El último píxel decodificado se duplica (ej. `pix >> 16 * 0x10001`).
- 5 Sumar Delta Sumar el valor delta de la paleta al píxel anterior duplicado.
- 6 Extraer Píxeles Los 16 bits bajos son el píxel izquierdo, los 16 bits altos son el píxel dere...
- 7 Almacenar Píxeles Guardar los dos píxeles decodificados en el búfer de salida.
- 8 Actualizar Píxel Anterior El píxel derecho decodificado se convierte en el 'píxel anterior' para la sig...
| Capa | Tecnología | Justificación |
|---|---|---|
| compute | RP2350 microcontroller | Plataforma objetivo de hardware con restricciones de ciclos por píxel (aprox. 6 ciclos). |
| data-processing | Nibnib format | Formato de imagen optimizado para descompresión de ultra baja latencia y 4bpp. vs JPEG (demasiado complejo para el presupuesto de ciclos), Formatos de paleta tradicionales (menor calidad en regiones suaves) Paleta de 256 entradas de 32 bits, cada entrada es un delta de color. |
Trade-offs
Ganancias
- ▲▲ Velocidad de descompresión
- ▲ Eficiencia de memoria
- ▲ Calidad de imagen en regiones suaves (comparado con paletas fijas)
Costes
- ▲▲ Velocidad de codificación
- ▲ Complejidad del codificador
- △ Artefactos de difusión de error en bordes afilados
// first two pixels copied from src[0..4], initializing pix
for x in 1..(width / 2) {
let inp = src[x + 3];
pix = ((pix >> 16) * 0x10001).wrapping_add(pal[inp as usize]);
out[x * 2] = pix & 0xffff;
out[x * 2 + 1] = pix >> 16;
}Fundamentos Teóricos
El concepto de Nibnib se conecta directamente con los fundamentos de la compresión de imágenes basados en paletas y la difusión de error, técnicas que tienen una larga historia en la computación gráfica. La idea de usar una paleta de deltas para mejorar la calidad de imagen en sistemas de baja profundidad de color es una evolución de las técnicas de cuantificación de color, como el algoritmo de cuantificación de color de median-cut de Paul Heckbert (1982) o el algoritmo de octree de Gervautz y Purgathofer (1988), que buscan optimizar la selección de colores en una paleta limitada.
La difusión de error, popularizada por el algoritmo de Floyd-Steinberg (1976), es un principio clave en la codificación de Nibnib. Este algoritmo distribuye el error de cuantificación de un píxel a sus vecinos, mejorando la percepción de detalle en imágenes con paletas limitadas. Nibnib adapta este principio al operar en pares de píxeles, lo que es una optimización para el rendimiento en hardware de baja potencia, reconociendo las limitaciones de procesamiento y la necesidad de maximizar la salida por ciclo. La asimetría entre codificación y decodificación es también un concepto bien establecido en la teoría de la información y la compresión, donde a menudo se sacrifica la complejidad del codificador para lograr un decodificador simple y rápido (ej. formatos de video como H.264/HEVC).