Эффективные идеи RLE для битовых данных

Question

Один из моих основных проектов - это библиотека дисплеев для микроконтроллеров. Как часть этого, у меня есть коллекция шрифтов (растровых изображений) и значков (альфа-канал).

Поскольку ресурсы (флэш-память и оперативная память) ограничены в микроконтроллерах, я рассматриваю лучшие способы хранения данных для этих шрифтов и значков.

Я склоняюсь к использованию компоновки с разделительной плоскостью для данных (например, ILBM на используемой Амиге), то есть вместо хранения всех бит для каждого пикселя вы сохраняете все первые бит для всего изображения вместе , а затем второй бит и т. д. Это становится более эффективным для работы с глубинами изображений, которые не являются мощью двух (попробовали ли вы упаковать 3-битные данные в 8-битный поток данных?).

Я также хотел бы сжать каждый из этих битпланов. RLE кажется наиболее разумным. Однако, поскольку теперь я работаю с потоками битов, а не целыми числами, мне интересно, какой лучший способ реализации RLE.

Я мог бы придерживаться традиционного метода обработки битов в блоках по 8 и поиска повторяющихся байтов (2 или более одинаковых, заменить на 2 одинаковых, а затем подсчитать количество в пробеге), но я не может видеть, что это замечательно, когда дело доходит до побитовых данных, которые будут содержать один битплан. (Между прочим, ILBM использует множество этих байт-мудрых методов - обрабатывает данные исключительно как байты и повторяет их по мере необходимости с байтами заголовка, определяющими, как следует обрабатывать следующий байт (ы).

Альтернативой может быть использование метода чередования числа бит. То есть, начните считать бит равным 0 и запишите номер этого бита в прогоне. Затем переключитесь на 1 и запишите число 1 бит в прогоне. Затем снова переключитесь на 0 и запишите количество бит. И т. Д.

Опять же, отлично, если у вас длинный пробег одного и того же бита, но как только вы получите быстрое чередование бит, вы получите массивное увеличение занимаемого пространства (8 бит, скажем 01010101, могут закончиться до 8 байтов [1,1,1,1,1,1,1,1]).

Главное предостережение для чего-либо здесь заключается в том, что оно должно быть эффективным - как в процессоре для его распаковки, так и в памяти для хранения любых рабочих буферов при его распаковке. Вот почему я думаю о RLE, а не о других методах.

Так что, я думаю, я ищу идеи, которые я пропустил. Какая была бы лучшая реализация для сжатия потока одиночных битов и представления этих сжатых данных в байт-центричной системе?

---

Пример глиф (десятичный):

00 00 02 14 03 00 00 00 
00 00 09 13 10 00 00 00 
00 00 13 05 13 00 00 00 
00 05 12 00 12 06 00 00 
00 11 15 15 15 11 00 00 
00 14 02 00 01 14 00 00 
08 12 00 00 00 12 08 00 
11 07 00 00 00 07 12 00 
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 

битовые плоскости 0-3 будет, таким образом, быть

0   1   2   3 
00001000  00111000  00010000  00010000 
00111000  00001000  00010000  00111000 
00111000  00000000  00111000  00101000 
01000000  00000100  01101100  00101000 
01111100  01111100  00111000  01111100 
00001000  01100100  01000100  01000100 
00000000  00000000  01000100  11000110 
11000100  11000100  01000110  10000010 
00000000  00000000  00000000  00000000 
00000000  00000000  00000000  00000000 

Однако глиф этот размер я бы вряд ли даже пытаться компресс. Это достаточно мало, чтобы быть бессмысленным. Однако он иллюстрирует разбиение битовых плоскостей и то, как битовые потоки будут выглядеть относительно исходных данных.

Answer 1

Проблема сжатия растровых изображений была предметом исследования на протяжении десятилетий, поэтому вы можете просто использовать результат этого, который является JBIG2. Вы можете использовать Google для открытого кода JBIG2.