RLE-схема пиксельного уровня

Пиксельного уровня – применяются тогда, когда для хранения одного пиксельного значения. используется 2 или более смежных байтов данного изображения. На пиксельном уровне биты игнорируются, а байты используются для идентификации пиксельного значения. Размер закодированного пакета зависит от размера пиксельных значений, подлежащих кодир-ю. Сведения о кол-ве битов или байтов пикселя записано в заголовке файла изображения.

1-ый байт – счетчик(0-255)

2-ой байт – пиксель1 го канала(0-255) РИС

3-ий байт – пиксель 2го канала(0-255)

4-ый байт – пиксель 3 го канала(0-255)

Сущ-ют литеральные гр пиксельного уровня: для этого также как и в схемах байтового уровня используется старший бит 1 го байта. В RLE схемах пиксельного уровня счетчик содержит данные о количестве пикселей .

RLE-схемы с использованием флага

При таком способе кодир-ия для представления группы используется не 2 ,а 3 байта.

1-ый байт – флаг, значение которого указывает на то , что следующие 2 байта явл частью закодиров-ого пакета.

2-ой байт – счетчик группы

3-ий байт – значение группы

Если в процессе кодирования встреч. гр.,состоящая из 1,2 или 3х зн-ий,то это зн-я записываются на прямую в поток сжатых данных РИС

Флаговое знач. м.б. любое от 0 до 255,заранее оговоренное в заголовке файла или специф. RLE

# 100 гер. pix 213 20 20 222-флаг

222 99 213 20 20

При декодир. анализируется прочитанное значение ,если это флаговое зн-е, то читается и обрабатывается флаг. знач. и рез-ты. Если в 1 байте не содержится флаговое значение, то все прочитан значения запис. в выход. поток напрямую. В RLE пакете с использованием флага, минимальный размер групп, пригодных для кодирования увеличиться до 4 значений. Если поток незакодир. данных сдержит значение = флагу, то это значение д.б. закодировано в 3х байтовый пакет, т.о. можно избавится от ошибочных флаговых значений.

Пакет вертикального повторения для RLE схем

Эти пакеты исп-ся для повышения эффективности сжатия и повторяют строки развертки .Пакет не хранит реальных данных в каждой строке развертки, он просто указывает на необходимость повтор. пред. строку или строки еще раз. Самый простой пакет верт. повт. занимает 1 байт. Значение этого байта заранее оговор в специф и оно указ. не на то что предыдущую строку необх. повторить.

В формате WPG значение пакета вектик. повтор.- пустое мн-во.(обозначение).

# Изображение содержит строки шириной 1280 пикселей, пиксельная глубина 1 байт, все пиксели одного цвета. Необходимо закодировать первые сто строк изображения.

РИС

Сжатие методом LZW

Это метод сжатия без потерь,примен в разл форматах файла изобр. Включен в стандарт сжатия модемов и исп. в языке Post Script.

В 1977 был разработан и был назван LZ-77. Использ алгоритм для сжатия текстов,стал основой таких програм как PKZIP,PKUNZIP,ARJ. В1978 алгоритм был модифицир и стал применяться для сжатия двоичных данных. В 1984 был модиф компрессор и алгоритм получил наз-е LZW. Алгоритм LZW позволяет работать с любым типом данных, обеспечивает быстрое сжатие и распаковку. Этот алгоритм основан на поиске шаблонов в изображении и сохранении их. Программа считывает значения пикселей и строит таблицы кодов, которые представляют повторяющиеся пиксельные узоры, найденные этой программой. Степень сжатия достигается 3:1 или 4:1. Хорошо сжимаются насыщенные узорами изображения, содержащие большие блоки однотонной окраски или повторяющиеся одинаковые значения цветовых элементов. Этот алгоритм, как и RLE, не является форматом – он лишь включен в различные другие форматы файлов. LZW является полуадаптивным, т.к. строит словарь данных из входного потока, образцы данных идентифицируются в потоке данных и сопоставляются с записями из словаря. Если данные не представлены в словаре, то создается кодовая фраза, которая записывается как в словарь, так и в выходной поток сжатых данных. Если эта подстрока встречается повторно во входном потоке, то кодовая фраза соответствующая ей читается из словаря и записывается в выходной поток. Т.к. фразы имеют меньший физический размер, чем исходные данные, то LZW считается сжатием. Декомпрессор работает в порядке, обратном кодированию. Преимущество LZW в том, что для него необязательно сохранять словарь для последующего декодирования. При сжатии текстовых файлов LZW инициализирует первые 256 записей символами ASCII как фразами, а затем ищет их повторения.

Алгоритм LZW кодирования

С начала LZW проверяет является ли фраза(подстрока) уже известной. Если подстрока уже встречалась, то кодировщик выводит из словаря ее код, а в словарь записывает код для подстроки +след. символ

#Предположим встретилась строка:

/WED/WE/WEE/WEB/WET/

Словарь Выходной поток

/W-256 /

WE-257 W

ED-258 E

D/-259 D

/WE-260 256

E/-261 E

/WEE-262 260

E/W-263 261

WEB-264 257

B/-265 B

WET/-266 260

T

На первом шаге алгоритм выполняет проверку на наличие подстроки, состоящих из 2-х первых символов послед-ти в словаре (/W).Когда алгоритм не находит эту подстроку, то в выходн. поток он записывает ASCII код для одинакового символа ‘/’ и добаыляет в словарь ‘/W’ Т.к. 256 символов уже определены для ASCII одинак. символов(0-255) то 1-й подстр. м.б. поставлен в соответствии код 256. После того кодировщик читает след. символ, добавляет 2-ю подстроку WE в словарь, а выход. поток выводит ASCII символ ‘W’. Этот процесс повторяется до тех пор пока прочитанная подстрока не сопоставится со зн-ем из словаря. В этом случае система выведет в выход. поток код из словаря, а в словарь добавит уже 3х символьную подстроку Этот процесс продолжается до тех пор пока не исчерпается вход поток. Словарь очень быстро заполняется, т.к. нов. строка добавляется в таблицу каждый раз ,как генерируется код. Если использовать токлько 9-ти битные коды, то в предложенном примере то 19-ти байтная символьная стр-ра будет преобразована в 13.5 битную. Это демонстративный пример ,в действительности сжатие не начинается до тех пор, пока не будет построен примитивные словарь на 100 вых-х байт.

Алгоритм LZW декодирования

Алгоритму сжатия соответствует свойствам распаковки. Он получает выходной поток кодов от алгоритма сжатия и использует его для восстановления выходного потока. Одна из причин эф-ти явл-ся то ,что он не хранит словарь кодов, он его воссоздает в точности при распаковке. Это возможно из-за того, что словарь строится раньше, чем зап-ся выходной поток.

#Выход поток

/WED256E266261257B260T/

Словаря нет .По выходному потоку строи словарь.

вых. поток словарь вых. поток

/ /W-256 /

W WE-257 W

E ED-258 E

256 /WE-260 /W

E E/-261 E

260 /WEE-262 /WE

261 E/W-263 E/

257 WEB-26 WE

B B/-265 B

260 /WET-260 /WE

T

Алгоритм распаковки работает только на основе алгоритма сжатия и заканчивает свою работу и формирует словарь за столько же шагов как и алгоритм сжатия. Выходной поток алгоритма сжатия является исходным для работы алгоритма распаковки и в алг. распаковки 1-е 256 кодов также исп-ся для односимвольных данных.