Сжатие изображений или Как запихнуть большую картинку в маленький микроконтроллер

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

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

Для приведенного выше примера один символ - это 5х7 точек. 35 бит. 5 байт.
Для сохранения первой половины печатных символов ASCII - спец.символы, цифры, большие и маленькие английские буквы - это 96 символов - нужно 5 * 96 = 480 байт.
Если же к этому добавить еще и кириллический алфавит (+72 символа), то получим 840 байт.

Но шрифт 5х7 точек - он маленький, хорош для дисплеев с большим размером пикселей. А современные недорогие и доступные радиолюбителю дисплеи, особенно цветные, имеют достаточно высокую плотность пикселей. Например, TFT IPS дисплей с диагональю 1.51" имеет разрешение 240х240 пикселей. На этом дисплее вышеуказанный текст шрифтом 5х7 точек будет высотой порядка 1 мм.

Кому нужен текст размером в миллиметр?

Соответственно, нужен шрифт побольше. Символ шрифта 14х21 точку занимает 294 бита или 37 байт. 168 символов - это 6216 байт.

А если кроме шрифтов, нужно еще и картинки выводить ?

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

Посчитаем размер. Эта картинка имеет размер 84х72 пикселя - это 6048 бит. Или 756 байт.

Ну а теперь возьмем вот эту картинку:

Эта картинка - 120х120 пикселей. Недорогие цветные дисплеи оперируют 18-битным цветом, но позволяют загружать 16-битный цвет в формате RGB565. 16 бит - это 2 байта.
Считаем: 120х120х2 = 28800 байт. Или 28 килобайт.

А если попробовать уменьшить число цветов? Например, с 16 бит до 4... Было 65536 цветов. стало 16. Картинка станет хуже.

Она же, но увеличенная в 4 раза. 

Ощутимо хуже. Но и размер у нее теперь будет 7200 байт всего..

Платой за такое уменьшение размера является потеря качества картинки.

Но опять же, для графического интерфейса пользователя редко когда используются изображения с фотокачеством. Чаще это какие то иконки, пиктограммы, символы с не очень большим количеством цветов. И ограничение количества используемых цветов - а соответственно, и число бит на пиксель, может дать значительную экономию размера.

Но! Как бы мы не уменьшали число цветов, менее, чем 1 бит на пиксель, у нас не получится.

И картинка, к примеру, 128х64 пикселя будет минимум 1 килобайт. Всегда.

Но! Тут на помощь приходят различные алгоритмы сжатия.

Самый простой и нетребовательный к ресурсам алгоритм - это RLE. Run-length encoding. Кодирование длин серий. 

К примеру, на картинке выше - перебираем пиксели, слева направо, сверху вниз...

И видим, что у нас 40 пикселей белого цвета. А потом - 23 черных пикселя.
В обычном режиме эти 63 пикселя ужмутся в 8 байт.
А если сохранить код цвета и количество пикселей - то если в лоб, то 4 байта.
А если с некоторыми ограничениями - кодировать длину последовательности семью битами, а один бит оставить на задание цвета, например - то вообще в 2 байта можно уложиться.

Казалось бы, все супер. А если встретится вот такая картинка?

Тут уже выигрыша никакого не будет. наоборот, будет проигрыш. Поскольку длина последовательности одного цвета тут колеблется от одного до трех пикселей. А у нас для кодирования длины и цвета последовательности отведен какой то размер данных. 

Разберем верхнюю строчку картинки. Там 19 пикселей : 3 белых, 1 черный, 1 белый, 1 черный, 2 белых, 1 черный, 1 белый,1 черный, 1 белый,1 черный, 3 белых, 1 черный, 2 белых пикселя.

Попробуем их закодировать, как в примере выше - 7 бит на длину, 1 бит на цвет.
13 последовательностей длиной от 1 до 3 пикселей. И каждую мы кодируем 7+1=8 битами. Всего 13 байт.
Хотя 19 пикселей - это всего 3 байта, если просто сохранять пиксели как есть.

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

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

Для отрисовки простых графических примитивов редко когда нужно много цветов.
Соответственно, можно ограничиться 16, 8, 4 или вообще 2 цветами. 
И сохранить эти цвета в отдельный массив-палитру. А в кадрах хранить не значение цвета, а индекс этого массива. В зависимости от размера палитры это может быть 4,3, 2 или всего 1 бит. В отличие от значения самого цвета, который даже для недорогого цветного дисплея может быть 2 байта - 16 бит на цвет.

Вообще, для вот такого процесса кодирования картинки следует забыть, что есть байт, который 8 бит. И оперировать битовыми последовательностями. Которые потом уже , в конце, будут сгруппированы в байты.

Итак, кадр.

Первый бит - тип кадра - последовательность одинаковых пикселей или поток индексов цветов.

Далее несколько бит - количество пикселей в кадре.
Тут тоже интересная штука получается. последовательность одинаковых пикселей меньше двух не бывает. А поток разных пикселей - ну тоже как минимум из одного пикселя.
Соответственно, если мы отведем для хранения длины такой последовательности 5 бит, которыми можно закодировать число от 0 до 31, то для последовательности одинаковых пикселей мы можем закодировать их количество от 0+2 до 31+2 - от 2 до 33 пикселей. Аналогично и для потока разных пикселей - 0+1 .. 31+1 - от 1 до 32 пикселей.
Обобщая - при кодировании длины n битами можно закодировать последовательность одинаковых пикселей количеством от 2 до 2ⁿ+1 и поток разных пикселей - количеством от 1 до 2ⁿ.

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

А вот далее, после количества, идут собственно сами данные - индексы цветов пикселей. 
Для последовательности одинаковых пикселей это будет один индекс и на этом кадр закончится, а для потока разных пикселей это будет то количество индексов, которое было закодировано в начале кадра.

Есть еще маленькая оптимизация. Когда после потока разных пикселей начинается последовательность одинаковых. т.е. закончился кадр с потоком и нужно сохранять кадр с последовательностью одинаковых пикселей. А кадр последовательности - это один бит типа кадра, несколько бит длины последовательности да индекс цвета - тоже от 1 до 4 пикселей.
А если эта последовательность короткая, то иногда выгоднее эти несколько одинаковых пикселей закодировать в существующий поток (если его емкость это позволяет), нежели кодировать новый кадр.

Например, на длину данных отведено 6 бит, на индекс цвета - 2 бита.
Тогда кадр с последовательностью данных будет выглядеть так: TXXXXXXYY - 9 бит: T - один бит типа кадра, X - 6 бит длины последовательности, Y - 2 бита цвета последовательности.
А пиксель кодируется всего двумя битами. Четыре пикселя - 8 бит. А размер кадра - 9 бит. И если предыдущий кадр был потоком индексов цветов, то до четырех пикселей выгоднее включить в этот кадр, нежели создавать новый кадр последовательности. 

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

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

Вот это изображение из 16 цветов, 120 х 120 пикселей. 

В несжатом виде 4-битные индексы цветов занимают 7200 байт.
При сжатии вышеописанным алгоритмом, если на длину последовательности одинаковых пикселей отводить 5 бит, а на длину потока из разных - всего 2 бита, 4 бита на индекс цвета, то поток кадров займет 3680 байт. Сжали почти вдвое.

Динозаврик тоже в два раза ужался. Из 1024 байт в 520. Режим сжатия - 1 бит на индекс цвета, 5 бит на длины обоих типов кадров.

Дальнейшим развитием алгоритма сжатия можно попробовать анализировать пары или тройки  пикселей. Если отводить на тип кадра 2 бита - то у нас может быть 4 типа кадров:

• Кодирование последовательности пикселей одного цвета
• Кодирование последовательности повторяющейся пары пикселей
• Кодирование последовательности повторяющихся троек пикселей
• Кодирование последовательностей пикселей разных цветов.

Для сжатия изображений можно применить и другие алгоритмы сжатия без потерь. Например, LZ77 - алгоритм Абрахама Лемпеля (Abraham Lempel) и Якоба Зива (Jacob Ziv), разработанный ими в далеком 1977 году. Ну да, алгоритм почти мой ровесник. Алгоритм для сжатия данных использует метод поиска повторяющихся последовательностей и замены повторов этих последовательностей на ссылки на исходную последовательность. Но при распаковке данных по этому алгоритму нужно или держать в ОЗУ определенный объем ранее загруженных данных, или гонять по блоку данных назад-вперед, что бы прочитать последовательности, на которые встречены ссылки. Так же можно добавить в этот алгоритм некие элементы RLE - тогда повторы, идущие подряд, можно сжать еще сильнее.

Ну или проще взять микроконтроллер посовременнее, у которого много памяти, и не париться с этими детскими методами сжатия.

Следующая статья - Растровые шрифты и оптимизация занимаемого места