простейший алгоритм сжатия ч/б изображения
Ivan Kuvshinov
AK> байтов, а ниблов. Получалось раза в 2-3 в среднем.
Что такое "нибл"?
AK> Потом мне идею подсказал хороший человек, что можно ту часть картинки,
AK> которая уже "разжата", использовать как "словарь". Тогда я сделал RLE
...
AK> ниблов надо копировать из буфера. Получилось намного лучше, сжатие в
AK> среднем 3-4 раза (в пределе сжатие примерно в 60 раз), стало хорошо
AK> жать не только "горизонтальные" элементы, но и "вертикальные". Кодовой
Как расжатие может влиять на сжатие? Можно алгоритм по подробней, а то я не
понимаю, что здесь написанно.
КИА
Alex Kouznetsov
AK>> Я сжимал "настоящие" ч/б обычным RLE без потерь, но брал поток не
AK>> байтов, а ниблов. Получалось раза в 2-3 в среднем.
IK> Что такое "нибл"?
nibble = 4 бита
AK>> Потом мне идею подсказал хороший человек, что можно ту часть картинки,
AK>> которая уже "разжата", использовать как "словарь". Тогда я сделал RLE
IK> ...
AK>> ниблов надо копировать из буфера. Получилось намного лучше, сжатие в
AK>> среднем 3-4 раза (в пределе сжатие примерно в 60 раз), стало хорошо
AK>> жать не только "горизонтальные" элементы, но и "вертикальные". Кодовой
IK> Как расжатие может влиять на сжатие?
Алгоритмы сжатия и разжатия - дуальны. Раз я сменил алгоритм разжатия (стал
использовать буфер), то соответственно изменился и алгоритм сжатия.
IK> Можно алгоритм по подробней, а то я не понимаю, что здесь написанно.
"Обычный RLE" просто указывает, сколько раз надо повторить кодовую комбинацию
из входного потока в выходном потоке. Мой "RLE с буфером" вместо этого
указывает, сколько ниблов надо скопировать из буфера в выходной поток.
Входной поток состоит из однобайтных токенов двух типов:
-- "копировать нибл Х в выходной поток и в буфер" (значение Х "зашито" в тело
токена)
-- "копировать N ниблов из буфера в выходной поток"
Буфер кольцевой, размер буфера соответствует ширине одной скан-линии экрана.
Т.е. буфер содержит предыдущую, уже раскодированную строку изображения.
Указатель буфера соответствует горизонтальной позиции экрана.
Токен второго типа в пределе позволяет скопировать весь буфер целиком в
выходной поток. Если, например, в этом месте на изображении есть только
вертикальные линии, то достаточно один раз заполнить буфер (при помощи токенов
первого типа), а дальше можно просто копировать строку, пока не прорисуются
все вертикальные линии.
Пока, Алексей
Ivan Kuvshinov
AK> -- "копировать нибл Х в выходной поток и в буфер" (значение Х "зашито"
AK> в тело токена) -- "копировать N ниблов из буфера в выходной
AK> поток" Буфер кольцевой, размер буфера соответствует ширине одной
AK> скан-линии экрана. Т.е. буфер содержит предыдущую, уже раскодированную
AK> строку изображения. Указатель буфера соответствует горизонтальной
AK> позиции экрана.
Интересная модификация. То есть фактически присутствует стековый cashe
естественных комбинаций, благодаря стековой модели не требуется адресация, так?
У меня была мысль усовершенствовать RLE, как баланс между количеством бит на
повторяемость значений и количеством бит на смещение - вроде
дельта-кодирования, и я даже рассматривал возможность взятия значения из уже
пожатого (там естественные растояния "поскипаны") - но ничего конкретного у
меня не оформилось.
КИА
Alex Kouznetsov
AK>> Входной поток состоит из однобайтных токенов двух типов:
AK>> -- "копировать нибл Х в выходной поток и в буфер" (значение Х "зашито"
AK>> в тело токена) -- "копировать N ниблов из буфера в выходной
AK>> поток" Буфер кольцевой, размер буфера соответствует ширине одной
AK>> скан-линии экрана. Т.е. буфер содержит предыдущую, уже раскодированную
AK>> строку изображения. Указатель буфера соответствует горизонтальной
AK>> позиции экрана.
IK> Интересная модификация. То есть фактически присутствует стековый cashe
IK> естественных комбинаций, благодаря стековой модели не требуется
IK> адресация, так?
Правильно, адресации не нужно, но модель не стековая. Это кольцевой буфер,
который "катится вдоль выходного потока" как "колесико". Он "привязан" к
выходному потоку в одной точке - в том ниббле, который надо сейчас выводить в
выходной поток. Адресация не требуется потому, что точка привязки сдвигается
автоматически вместе с вых. потоком (т.е. где "колесико касается потока"). То
что выводится в вых. поток - автоматически повторяется в этом буфере.
Например, на экран вывелась такая инфа (хекс, каждая цифра - нибл)
0123456789ABCDEF -- первая скан-линия
56789ABC -- вторая скан-линия
Соответственно, в буфере будет
89ABCDEF
56789ABC
Если придет токен "первого типа" (т.е. обычный RLE) со значением "скопировать
нибл '3' в выходной поток 5 раз", то на экран выведется
0123456789ABCDEF
56789ABC33333
а в буфере будет
DEF
56789ABC33333
Теперь, если придет токен "второго типа" (т.е. RLE с указанием на буфер) со
значением "скопировать 14 ниблов из буфера в выходной поток", то на экран
выведется
0123456789ABCDEF
56789ABC33333DEF
56789ABC333
А в буфере будет
33DEF
56789ABC333
Пока, Алексей