Упаковка триколоров.

© Alone Coder

                Способ #1.

   Быстрый способ.
   Допустим,неупакованная картинка хранит-
ся в виде последовательности пикселов,по 2
пиксела в байте: %0aaa0bbb. (Как в 8 color
editor'е.)
   Отдельные  пикселы из этой последовате-
льности  легко извлекать командами RLD или
RRD. Поэтому начнём мыслить полубайтами.
   Вот  как  выглядит RLE-сжатие для таких
полубайтов:
   0aaa - просто пиксел с цветом "aaa";
   1aaa,NNNN - повторить цвет "aaa" NNNN+3
раза.
   Сжатие  и  распаковка  по такому методу
происходит очень быстро (сам проверял ;)).
Теоретически  метод должен хорошо справля-
ться  с  конверченными  картинками (в  них
очень  короткие  последовательности подряд
идущих одинаковых пикселов). Но на практи-
ке метод  жмёт очень и очень плохо, т.к. в
самой его конструкции предусмотрено увели-
чение длины непакующихся последовательнос-
тей на 25%.

   Обычный, однобайтный RLE типа:
   %0aaa0bbb - пикселы цветов "aaa","bbb";
   %1aaa0bbb,NNNNNNNN - повторить последо-
вательность цветов "aaa", "bbb" NNNNNNNN+3
раза;
   даст результаты не хуже,а на рисунках с
регулярной  штриховкой - даже лучше преды-
дущего.


                Способ #2.

   "Двухмерный RLE".
   В этом  методе одноцветная последовате-
льность N-й длины распространяется не сле-
ва  направо, а постепенно  увеличивающимся
квадратом:
   (при N=14)

   1 2 5 10
 ─4─3 6 11
 ─9─8─7 12
    ─14─13
   и т.д.

   Это позволяет использовать при упаковке
факт наличия в картинке некоторой вертика-
льной корреляции ;)
   Советую обратить внимание,как можно до-
биться более высокой плотности упаковки за
счёт наибольшего размера квадрата:

   Начинаем паковать с левого верхнего уг-
ла слева направо. Находим некоторый одноц-
ветный квадрат,растущий от первого пиксела
(или один пиксел в простейшем случае). По-
сле вычисления  размеров квадрата  и зане-
сения их  в упакованную последовательность
производим СТИРАНИЕ всех  пикселов  прове-
ренного  квадрата. При последующих поисках
квадратов СТЁРТЫЙ пиксел будет просто про-
пускаться (квадраты будут обходить его, не
увеличивая счётчик размера), причём от та-
кого пиксела, когда  наступит его очередь,
даже не будет строиться квадрат - т.е. пи-
ксел будет пропускаться и в главном цикле.
   Пикселы, заходящие  за экран, считаются
стёртыми.
   По-моему, очень оригинальный и перспек-
тивный метод! :)


                Способ #3.

   Разбиение по знакоместам.
   Разобьём картинку  на "знакоместа" раз-
мером  8x8 (всего  768  знакомест) и будем
рассматривать каждое из них отдельно.
   В знакоместе  может  встретиться  любое
количество цветов:от 1 до 8. Вот,например,
статистика по известным картинкам "eyore+"
(пьяные  в стельку Dj.Тигра и Dr.Винни-Пух
на именинах  у Mr.Иа-иа), "rockwell" (пиа-
нист) и "AUTOLOAD" (из редактора AGAv1.0):

 Цветов:   eyore+   rockwell  AUTOLOAD
    1        0        #f7       #93
    2       #38       #45       #33
    3       #2f       #38       #5c
    4       #31       #62       #95
    5       #68       #60       #7a
    6       #8a       #47       #6a
    7       #9f       #43       #4a
    8       #d7       #40       #1b

   Как видим, вероятности появления любого
количества  цветов  в  знакоместе примерно
равны, т. е. равны 1/8. В дальнейшем будем
учитывать этот факт.
   Подсчитаем, сколько бит потребуется для
хранения знакоместа:

   1 цвет: 3 бита;
   2 цвета: 64+6=70 бит;
   4 цвета: 128+12=140 бит;
   8 цветов: 192 бита.

   Конечно,можно свести трёхцветное знако-
место  к случаю 4-цветного и так далее, но
(см.выше) на этом мы потеряем примерно 350
байт на каждое "непредусмотренное" количе-
ство цветов - можете посчитать.Поэтому вы-
берем простые коды для 3,5,6,7 цветов:

   3 цвета: (66Ў106)+9 бит
(самый частый цвет кодируется битом 0, ос-
тальные два цвета - %10 и %11)
   5 цветов: (130Ў156)+15 бит
(3 двухбитных и 2 трёхбитных кода цвета)
   6 цветов: (132Ў170)+12 бит
(2 двухбитных и  4 трёхбитных  комбинации.
Вместо перечисления трёхбитных цветов мож-
но  просто указать, какие два цвета не ис-
пользуются)
   7 цветов: (134Ў182)+6 бит
(самый частый цвет=%00, остальные трёхбит-
ные. Указаны  только: самый  частый цвет и
неиспользуемый цвет)

   Ну, и прибавьте 3 бита,указывающие,ско-
лько всё-таки цветов в знакоместе. Получи-
тся весьма плотная упаковка.
   Выравнивать  блок  данных  упакованного
знакоместа по границе байта нежелательно -
средняя потеря = 384 байта.

   Может быть,это именно тот метод,который
бы хорошо смотрелся в 8 color editor'е?


                Способ #4.

   Теперь  попробуем  найти самый плотный,
пускай и медленный, метод сжатия для сред-
нестатистической диференой триколорной ка-
ртинки.
   Пусть построение (распаковка) идёт све-
рху вниз,слева направо.Требуется восстано-
вить цвет некоего пиксела. Входные данные:
текущая  позиция  упакованного файла и все
предшествующие пикселы.
   Пиксел  может принять один из 8 цветов,
причём с разными вероятностями.Вероятности
эти  будут зависеть от цветов предшествую-
щих пикселов.
   В  простейшем  случае  будем  учитывать
только последние 8 пикселов слева и сверху
(квадрат 8x8 без нижнего правого угла).Мо-
жно  придумать массу функций, возвращающих
вероятности появления цветов в зависимости
от окраски этого квадрата.
   Поскольку  картинка  диференая (Floyd -
Steinberg), то имеет смысл учитывать 2 ве-
личины, которые можно измерить в этом ква-
драте: предполагаемый средний цвет нужного
нам  пиксела (нужно как-то определить тен-
денцию изменения цвета в квадрате) и окра-
ску трёх ближайших к нему пикселов (от них
зависит,в какую сторону придётся округлять
полученный средний цвет).
   Допустим,нужная формула выведена.Массив
вероятностей появления каждого из 8 цветов
в этом  месте  построен. Это позволяет нам
при  упаковке: взять  действительный  цвет
этого пиксела и арифметическим кодировани-
ем по массиву вероятностей примешать его к
результирующей последовательности;при рас-
паковке: посмотреть,какому участку отрезка
[0;1),разделённого в соответствии с масси-
вом вероятностей,соответствует упакованная
последовательность - номер участка и будет
цветом.
   Короче, эта  идея пока совсем сырая, её
ещё думать и думать...
Сайт управляется системой uCoz