Упаковка триколоров.
© 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