Упаковка триколоров. © 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),разделённого в соответствии с масси- вом вероятностей,соответствует упакованная последовательность - номер участка и будет цветом. Короче, эта идея пока совсем сырая, её ещё думать и думать...