Есть такое дело...
(«Телесистемы»: Конференция «Микроконтроллеры и их применение»)
миниатюрный аудио-видеорекордер mAVR

Отправлено =AK= 17 января 2005 г. 13:41
В ответ на: архивы, архиваторы... :( отправлено Aleksey_N 17 января 2005 г. 12:37 


От:Alex Volgin (piks_sw@yahoo.se)
Тема:простейший алгоритм сжатия ч/б изображения
Группы новостей:fido7.ru.compress
Дата:2003-10-02 13:42:10 PST
Hi All,
Помогите - есть массив 320х240, 8 бит на точку (картинка). Надо зажать с потерей качества раза в 4, но чтобы памяти алгоритм расходовал не более 2..3 кб.
Размер картинки, понятно, больше, поэтому я думаю сначала разбивать на блоки, например 32х16 точек и сжимать их последовательно.
Подскажите, где рыть...
------------------------------------------------------------------
От:Alex Kouznetsov (akouz@senet.com.au)
Тема:простейший алгоритм сжатия ч/б изображения
Группы новостей:fido7.ru.compress
Дата:2003-10-24 20:35:54 PST 
Я сжимал "настоящие" ч/б обычным RLE без потерь, но брал поток не байтов, а ниблов. Получалось раза в 2-3 в среднем. 
Потом мне идею подсказал хороший человек, что можно ту часть картинки, которая уже "разжата", использовать как "словарь". Тогда я сделал RLE с буфером в одну или две строки изображения, в этом буфере хранится то, что уже "разжато" (вначале буфер обнулен). RLE указывает, сколько ниблов надо копировать из буфера. Получилось намного лучше, сжатие в среднем 3-4 раза (в пределе сжатие примерно в 60 раз), стало хорошо жать не только "горизонтальные" элементы, но и "вертикальные". Кодовой памяти на алгоритм надо всего пару сотен байт.
------------------------------------------------------------------
От:Alex Kouznetsov (akouz@senet.com.au)
Тема:простейший алгоритм сжатия ч/б изображения
Группы новостей:fido7.ru.compress
Дата:2003-11-01 14:26:13 PST 
 IK>  Что такое "нибл"?
nibble = 4 бита
 IK>  Как расжатие может влиять на сжатие? 
Алгоритмы сжатия и разжатия - дуальны. Раз я сменил алгоритм разжатия (стал использовать буфер), то соответственно изменился и алгоритм сжатия.
 IK> Можно алгоритм по подробней, а то я не понимаю, что здесь написанно.
"Обычный RLE" просто указывает, сколько раз надо повторить кодовую комбинацию из входного потока в выходном потоке. Мой "RLE с буфером" вместо этого указывает, сколько ниблов надо скопировать из буфера в выходной поток.
Входной поток состоит из однобайтных токенов двух типов:
-- "копировать нибл Х в выходной поток и в буфер" (значение Х "зашито" в тело токена)
-- "копировать N ниблов из буфера в выходной поток"
Буфер кольцевой, размер буфера соответствует ширине одной скан-линии экрана. Т.е. буфер содержит предыдущую, уже раскодированную строку изображения. Указатель буфера соответствует горизонтальной позиции экрана.
Токен второго типа в пределе позволяет скопировать весь буфер целиком в выходной поток. Если, например, в этом месте на изображении есть только вертикальные линии, то достаточно один раз заполнить буфер (при помощи токенов первого типа), а дальше можно просто копировать строку, пока не прорисуются все вертикальные линии.
------------------------------------------------------------------
От:Alex Kouznetsov (akouz@senet.com.au)
Тема:простейший алгоритм сжатия ч/б изображения
Группы новостей:fido7.ru.compress
Дата:2003-11-01 21:06:57 PST
 IK>  Интересная модификация. То есть фактически присутствует стековый
 IK>  cashe естественных комбинаций, благодаря стековой модели не 
 IK>  требуется адресация, так?
Правильно, адресации не нужно, но модель не стековая. Это кольцевой буфер, который "катится вдоль выходного потока" как "колесико". Он "привязан" к выходному потоку в одной точке - в том ниббле, который надо сейчас выводить в выходной поток. Адресация не требуется потому, что точка привязки сдвигается автоматически вместе с вых. потоком (т.е. где "колесико касается потока"). То что выводится в вых. поток - автоматически повторяется в этом буфере. 
Например, на экран вывелась такая инфа (хекс, каждая цифра - нибл)
  0123456789ABCDEF   -- первая скан-линия
  56789ABC           -- вторая скан-линия
Соответственно, в буфере будет
          89ABCDEF
  56789ABC
Если придет токен "первого типа" (т.е. обычный RLE) со значением "скопировать нибл '3' в выходной поток 5 раз", то на экран выведется
  0123456789ABCDEF
  56789ABC33333
а в буфере будет
               DEF
  56789ABC33333
  
Теперь, если придет токен "второго типа" (т.е. RLE с указанием на буфер) со значением "скопировать 14 ниблов из буфера в выходной поток", то на экран выведется
  0123456789ABCDEF
  56789ABC33333DEF
  56789ABC333
А в буфере будет
             33DEF
  56789ABC333


Составить ответ  |||  Конференция  |||  Архив

Ответы
Перейти к списку ответов  |||  Конференция  |||  Архив  |||  Главная страница  |||  Содержание  |||  Без кадра

E-mail: info@telesys.ru