Сжатие монохромных картинок - изобретаем PCX

У меня образовался дисплейчик от нокии 3310. Монохромный. 84 х 48 пикселей.
Пока еще его не подключал. Только напаял проводочки.

Сегодня думал — в каком формате хранить картинки. Если записывать без сжатия по 1 биту на пиксель, то один кадр занимает 504 байта. Для отображения пары картинок оно конечно уместно, а вот если хочется записать в МК анимацию или еще что, то будет фейл.

Стал думать над тем, как-бы сжать картинку, чтобы при этом на распаковку тратилось минимум времени и сил. Первое, что пришло на ум — PCX. Это такой древний, как MS-DOS, формат изображений.

Суть в следующем: вместо того, чтобы писать подряд цвета для каждого пикселя, мы запишем сколько пикселей одного цвета идут друг за другом и цвет этой пачки.

Например, вот эта прекрасная картинка:
glider.PNG

Будет сжата, и записана как:
1 пиксель белого, 1 черного, 3 белого, 4 черного.

PCX умеет работать с восьмибитной палитрой, но для нас это слишком много — хватит и одного бита. Остальные 7 бит оставляем на запись длины цепочки одноцветных пикселей.

Еще понадобится записать разрешение картинки, без него восстановить её обратно будет невозможно. И общую длину данных, не считая заголовка. В итоге имеем вот такой формат:

format.PNG

Для преобразования из bmp в наш монохромный PCX написал (точнее, дописал) вот такую утилиту:

img_converter.PNG

Работает просто, как топор:
Нажимаем открыть, выбираем bmp (не больше 255х255 и монохромный). Он тут-же сжимается. Можно тыкнуть кнопку «Массив (pascal)» и получить готовый листинг для МикроПаскаля, типа такого:

const
 Black = $80;
 White = 0;

 Image: array[0..137] of byte = (
 $D1, //Сигнатура
 84, //Ширина
 48, //Высота
 138, //Размер данных (Low)
 0, //Размер данных (High)
//Дальше идет поток данных в формате [длина цепочки]+Цвет
 127+White,  127+White,  127+White,  127+White,  71+White,  2+Black,  11+White, 
 73+Black,  11+White,  72+Black,  42+White,  13+Black,  68+White,  20+Black, 
 62+White,  6+Black,  13+White,  5+Black,  58+White,  5+Black,  18+White, 
 5+Black,  54+White,  5+Black,  22+White,  5+Black,  52+White,  3+Black, 
 26+White,  3+Black,  51+White,  2+Black,  30+White,  2+Black,  49+White, 
 3+Black,  30+White,  3+Black,  47+White,  3+Black,  32+White,  3+Black, 
 45+White,  3+Black,  34+White,  3+Black,  44+White,  2+Black,  36+White, 
 2+Black,  44+White,  2+Black,  36+White,  2+Black,  43+White,  2+Black, 
 38+White,  2+Black,  42+White,  2+Black,  38+White,  2+Black,  42+White, 
 2+Black,  38+White,  2+Black,  41+White,  2+Black,  39+White,  2+Black, 
 42+White,  2+Black,  38+White,  2+Black,  42+White,  2+Black,  38+White, 
 2+Black,  42+White,  2+Black,  38+White,  2+Black,  43+White,  2+Black, 
 36+White,  2+Black,  44+White,  2+Black,  36+White,  2+Black,  44+White, 
 3+Black,  34+White,  3+Black,  45+White,  3+Black,  32+White,  3+Black, 
 47+White,  3+Black,  30+White,  3+Black,  49+White,  2+Black,  30+White, 
 2+Black,  51+White,  3+Black,  26+White,  3+Black,  52+White,  5+Black, 
 22+White,  5+Black,  54+White,  5+Black,  18+White,  5+Black,  58+White, 
 6+Black,  13+White,  5+Black,  62+White,  20+Black,  37+White,  72+Black, 
 12+White,  72+Black,  127+White,  127+White,  127+White,  127+White,  88+White);


Так-же можно нажать кнопку «сохранить» и записать данные в .bin файл.
Алсо, утилта умеет отображать свои сжатые картинки — надо при открытии выбрать тип файла «Binary».

Алгоритм сжатия выглядит так:

Img_data[0] := $D0 or 1; //Сигнатура
Img_data[1] := Byte(Image1.Picture.Width); //Ширина
Img_data[2] := Byte(Image1.Picture.Height); //Высота

x := 0;
y := 0;
pos := 5; //Начинаем с 6го байта - в первых пяти служебная информация.
tmp_color := Image1.Picture.Bitmap.Canvas.Pixels[0,0]; //Устанавливаем цвет текущей цепочки
tmp_count := 0;

repeat

 stop := false;
//Цепочка может закончится по 3 причинам:
 if tmp_color <> Image1.Picture.Bitmap.Canvas.Pixels[x,y] then stop := true; //Изменился цвет
 if (x=Image1.Picture.Width-1) and (y=Image1.Picture.Height-1) then //Закончилась картинка
 begin
  stop := true;
  Inc(tmp_count); //Тогда надо инкрементировать счетчик лишний раз
 end;
 if tmp_count=127 then stop := true; //Закончился счетчик
 

 if stop then //Если цепочка закончилась, то
  begin
   //Записываем данные её днине и цвете пикселей
   Img_data[pos] := 0; 
   if tmp_color = clBlack then Img_data[pos] := $80;
   Img_data[pos] := Img_data[pos] + (tmp_count and $7F);
   Inc(pos);

   tmp_color:=Image1.Picture.Bitmap.Canvas.Pixels[x,y]; //Цвет новой цепочки
   tmp_count := 0; //Сбрасываем счетчик
  end;



 Inc(tmp_count); // + один пиксель в цепочке

//Смещаем указатель:
 Inc(x);
 if x=Image1.Picture.Width then
  begin
   x := 0;
   Inc(y);
  end;


until (y=Image1.Picture.Height); //Условие завершения - достигнут кнец изображения

//Сохраняем данные о размере записи:
Data_size := pos;
Img_data[4] := Hi(data_size);
Img_data[3] := Lo(data_size);


Для проверки качества сжатия взял 8 разных картинок. Все они имеют разрешение 84х48 пикселей, и несжатый размер 504 байта (без служебной информации).


Как и следовало ожидать, сжатие черного квадрата проходит лучше всего — 37 байт вместе с заголовком. Win!


Две линии и овал сжались до 138 байт. Кстати, листинг, который висит выше — от этой картинки.


Эмблема этой вашей игры про паркур ужалась до 186 байт.


Попытка уменьшить мою мою эмблемку до 48 пикселей по вертикали привела к тому, что надпись зафейлилась.
А после сжатия в PCX она стала весить 277 байт.


Корявая такая надпись. После сжатия весит 305 байт.


Матан после преобразования стал весить 329 байт.


А вот плакат «НЕ ТУПИТЬ» наоборот — вырос до 574 байт.


Сжатие сеточки с ячейкой в 1 пиксель приводит к фейлу.
После «сжатия» она стала весить 3989 байт. Тоже самое случится, если сжимать вертикальную штриховку.

Алгоритм сжатия можно сделать чуть более интеллектуальным. К примеру, если размер файла после сжатия > исходного, то записать, вместо сжатых, исходные данные, изменив сигнатуру (первый байт в массиве), или попробовать другой метод сжатия. Естественно, что на стороне МК алгоритм распоковщика должен быть готов к разным форматам данных.

А пока у меня есть довольно простой алгоритм, который сжимает bmp в полтора-два раза, без потерь. А главное, сжатая картинка шустро распаковывается. Вот так:

//Начальные значения
  x := 0;
  y := 0;
  count := 0;
//Читаем данные до конца файла
  while fs.Position < fs.Size do
    begin
      fs.Read(tmp_byte,1); //Читаем очередной байт
      Img_data[fs.Position-1] := tmp_byte; // Это к распаковке не относится (тут по ходу чтения заполняется массив)
      count := tmp_byte and $7F;// Выделяем длину цепочки
      color := clWhite; 
      if tmp_byte and $80 = $80 then color := clBlack; //Выделяем цвет
      //Заполняем цепочку
      for tmp_byte := 0 to count - 1 do
       begin
        Image1.Picture.Bitmap.Canvas.Pixels[x,y] := color; //Выводим очередной пиксель

        Inc(x); //Сдвигаем указатель вправо
        if x=Image1.Picture.Width then //Если дошли до края,
        begin
         x := 0;
         Inc(y); //То переходим на след строку.
        end;
       end;
    end;


Это кусок кода из той-же утилиты. Распаковщик для МК я пока не писал — как разберусь с дисплеем, возьмусь за него.

В приложении к статье — утилита и тестовые картинки.
  • +2
  • 26 мая 2011, 02:38
  • dcoder
  • 1
Файлы в топике: Converter.zip

Комментарии (30)

RSS свернуть / развернуть
RLE это называется. Еще как минимум в BMP и TGA юзается. Самый простой алгоритм, чем и радует. Можно еще попробовать препроцессинг строк аля PNG сделать. Не слишком накладно, но вполне можно сделать сжимабельной если не сетку, то хотя бы полосы — полноценно кодироваться будет только первая строка, остальные выродятся в нули.
0
  • avatar
  • Vga
  • 26 мая 2011, 02:52
А для анимаций еще кстати можно добавить межкадровый препроцессинг. Типа XProger'овского XLE.
0
  • avatar
  • Vga
  • 26 мая 2011, 02:56
это больше подходит не для анимаций, а для массива картинок. для анимации выгоднее записывать отличия от предыдущего кадра.
0
Отличия, как правило, тоже нужно чем-то сжимать. Учитывая, что они в основном состоят из нулей — RLE вполне неплохо справляется.
Алсо, 7 бит на длину наверное лишку для таких маленьких картинок. Правда, следущее удобное значение — 3, а этого уже маловато (картинка будет весить от 0.5 до 4 размеров исходной). Можно еще 5 попробовать.
Вертикальная штриховка кстати будет весить еще больше сеточки. 4032 байта плюс заголовок — 4037.
0
И еще мелкая оптимизация. Поскольку цепочка не может иметь нулевую длину — можно кодировать длины от 1 до 128, а не 0..127 (здесь малозаметно, а вот при меньшем размере поля длины — более актуально).
0
Комп у нас шустрый-шустрый. Вполне может попробовать разные алгоритмы сжатия — разное количество бит на длину, разное направление сканирования (горизонтальное/вертикальное). С каким получится компактнее — тот и оставить, не забыв поменять сигнатуру.

Вот только картинру с вертикальной разверткой будет писец как неудобно на дисплей выводить.
0
ну-ну… учитывая что обычная его настройка в горизонтальном направлении выводить столбцы по 8 пикселей. собственно отсюда по моему и пошло то, что для него шрифт делают 6х8 пикселей.
0
Кстати, о шустроте. Более 99% времени комп у тебя занимается вычислением вызова Pixels[i, j]. Подумай в сторону использования ScanLine.
0
Знаю. Но все равно размер картинки маленький и обработка выполняется почти моментально. Другое дело, если размер будет больше.
0
А как вы смотрите на такую бредовую идею:
<1 бит: 0> <7 бит: неупакованные данные>
<1 бит: 1> <цвет> <6 бит: количество — 8>
при мение мение 8-ми подряд идущих символов описанного вами метода вы всё равно получаете коэффициент сжатия меньше единицы, так и хранить данную последовательность неупакованной. Тут получим худшее сжатие 7/8, лучший 135/8. Но это теория, как на практике — надо смотреть конкретные примеры.

P.S.: Про сжатие есть полезный сайтик.
+3
Не такая уж бредовая идея. Скорее наоборот — вполне годная.
И распаковка опять-же не сильно усложняется.
Надо будет опробовать. Спасибо.
0
да этот сайтик с библиотекой машкова один из старейших сайтов в рунете и в мире, он по моему существовал с 1996 года.
0
Есть кстати еще алгоритмы сжатия графики для факсов. Они ориентированы на сжатие черно-белой картинки и (я так думаю) на работу в достаточно ограниченных аппаратных условиях. Стоит и на них взглянуть.
0
  • avatar
  • Vga
  • 26 мая 2011, 17:07
Факс использует таблицы…
0
По моей ссылке есть пример. 100к архив исходников.
0
Я бы сделал самое простое изменение — сделал бы изменяемой длину записи количества одинаковых пикселей. От 0 до 7 или 8 бит.
Программа на PC тупо сжимает всеми вариантами и узнает длину, при которой результат меньше всего.
0
Это требует добавления функций побитового чтения/записи. Варианты, где одна запись укладывается в 4 или 8 бит тем и хороши, что с ними проще работать. 6 бит — чуть хуже, но его тоже можно декодировать фиксированной процедурой 3-в-4.
Кстати, есть ведь и реализации LZ, у которых декодер весит порядка 200 байт (в варианте для х86) — LZO например. Правда, они обычно просят память под входной и вызодной буферы, но они могут и частично перекрываться.
0
Если использовать RLE для таких маленьких монохромных картинок, то мне кажется нет смысла записывать цвет пикселя отдельным битом. Просто чередовать белые-черные. Если максимальной длины последовательности не хватает для кодирования всех точек одного цвета, то вставляется последовательность нулевой длины другого цвета. На 8-битах разницы нет, а на 4 или 6 — думаю будет заметен выигрышь. Кроме разве что полностью монотонной картинки, но кому оно надо. Например для 4 бит. Последовательность от 1 до 8 одноцветных пикселей будут кодироваться равнозначно, от 9 до 15 будет выигрышь в 2 раза, на 16 мы проиграем (тут придется записать 15, 0, 1), 17-24 — равнозначно, 25-30 — снова выигрышь

Можно и еще оптимизировать. Например для 4-бит кода сделать значения 1-15 — соответствующее число точек одного цвета, далее цвет меняется на противоположный, а 0 означает 15 точек одного цвета, далее цвет продолжается. Выигрышь в сжатии гарантирован.
0
  • avatar
  • ACE
  • 27 мая 2011, 01:11
Стоит попробовать этот вариант, спасибо.
0
кстати, раз картинка у вас все время одинаковая и прямоугольная — может быть есть смысл попробовать поменять Х и У при сжатии (что на некоторых картинках позволит сэкономить)? а при распаковке посмотреть вертикальная или горизонтальная картинка, и произвести обратную замену.
0
То-есть просто поворачивать картинку на 90 градусов?
0
да, думаю на некоторых картинках это может дать прирост, в частности при вертикальных штрихах :)
Правда, код отображения чуть вырастет.
0
Лучше к каждой строке добавлять флаг препроцессинга — например, «эта строка содержит только отличия от предыдущей» или «эта строка содержит только отличия от инвертированной предыдущей», тогда все строки кроме первой у штриховки и сетки окажутся нулевыми. Правда, оно потребует наличие буфера предыдущей строки, но под этот экран и так придется распаковывать 8 строк, если я правильно понял как он заполняется.
0
ну горизонтальное заполнение в нем вроде тоже есть. надо даташит покурить. только его никто не юзал (точнее он не так популярен).
0
А что если одним байтом кодировать 8 пикселей? Все равно ведь либо пиксель белый, либо черный. Ну выделить в байте по биту на пиксель, и всего делов… И если я все правильно понял, весить будет почти в 8 раз меньше (не учитывая служебную инфу в начале файла)…
0
Ну смотри:
84 * 48 это 4032 пикселя. Разделить на 8 бит будет = 504 байта. Не так уж мало. Я об этом с самаго начала писал.
0
Извиняюсь, сначала недопонял =) Тогда конечно)
0
для сеточки надо заюзать векторную графику :)
0
Вот, может заинтересует, моя подобная утилита для конвертирования изображений в код :), поддерживает много вариантов выходного кода и сжатие используя кодировкой длин серий.

hobby-research.at.ua/load/utility/grafika/bitmap2code/9-1-0-22
0
взял на заметку, как раз может пригодится.
0
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.