Мультимедийные технологии (стр. 3 из 7)
Недостатком этого метода является также его низкая помехоустойчивость. Даже редкие помехи приводят либо к появлению на изображениях протяженных штрихов, поскольку помеха изменяет значение яркости всей последовательности, либо, что еще хуже, к “раздергиванию” строк, если помеха искажает данные о числе повторения отсчета в последовательности. Достоинством же этого метода является простота его реализации. Отмеченные особенности определили и область его применения, а именно при записи графических изображений, в том числе цветных, содержащих большие однородные поля.
6 Кодирование методом LZW
В настоящее время метод LZW (Алгоритм сжатия, с адаптивностью и использованием кодов переменной длины с максимальной длиной 12 двоичных единиц.), используется в форматах записи как графической, так и гипертекстовой информации: GIF, TIFF, PDF.
6.1 ПРИНЦИПЫ МЕТОДА СЖАТИЯ LZW
Принципы метода сжатия LZW. Пусть сжатию подлежит черно-белое полутоновое изображение, проквантованное по яркости на 256 уровней. Сжатие начинается с того, что строится (инициализируется) первоначальная таблица кодов, в которой каждому уровню квантования сопоставляется код, представляющий собой двоичную запись номера уровня квантования. Так, например, нулевому уровню квантования приписывается значение кода - 0, первому уровню квантования значение - 1, и т.д., 255-му уровню квантования значение -255. Такая таблица содержит 256 значений кода. Далее в таблицу записываются еще два кода: код очистки, которому присваивается значение 256 и код конца записи -257. Код очистки используют для того, чтобы не произошло переполнение таблицы, которая по принятому соглашению может включать коды протяженностью не более 12 двоичных единиц (числа до 4096). Он необходим, так как по мере заполнения таблицы и соответствующего увеличения кода имеет место переход к кодам протяженностью в 10, 11 и 12 двоичных единиц, Код очистки инициализирует таблицу заново, стирая в ней все коды, начиная с 258 и выше и освобождая тем самым место для кодового представления встречающихся в изображении комбинаций символов. Код конца записи, как это видно из его названия, сигнализирует о том, что кодируемая последовательность окончилась. После завершения подготовительных операций алгоритм готов к началу сжатия данных (изображения).
Алгоритм сжатия данных:
· Инициализировать, т.е. ввести первоначальную таблицу кодов;
· Очистить таблицу кодов, начиная с кода 258 и до конца;
· Очиститьбуфер строки (String), буфер строки (Test) и буфер строки (Byte).
· Далее в цикле:
а) Прочитать очередной байт кодируемых данных в буфер (Byte).
б) Сцепить (конкатенировать) String + Byte и поместить результат в буфер Test.
в) Проверить, имеется ли в таблице кодов код, соответствующий комбинации, помещенной в буфер Test?
- если имеется, то содержимое буфера Test переписать в буфер String и перейти в начало цикла;
- если нет, то добавить в таблицу код, соответствующий содержимому буфера Test, присвоив ему значение, совпадающее со следующим свободным порядковым номером, вывести в выходной поток код, соответствующий содержимому буфера String, переписать содержимое буфера Byte в String и перейти в начало цикла.
· Работа программы заканчивается тем, что делаются записи в выходной поток кода содержимого String и кода конца записи.
В результате применения такого алгоритма получаем коды переменной длины, причем для сочетаний из двух-трех символов, каждый из которых в отдельности описывается в таблице 8-разрядным кодом, длина полученных кодов будет составлять не 16 и не 24 бита, а существенно меньшей.
Декодированию (декомпрессии) сжатых данных.
Декодирующий алгоритм, получая коды комбинаций исходных отсчетов, составляет по ним кодовую таблицу идентичную той, которую составляет кодирующий алгоритм.
Декодирующий алгоритм:
· Прочитать новый код сжатых данных (Newcode).
· Если Newcode представляет собой код конца записи, то завершить работу.
· Если Newcode представляет собой код очистки, то необходимо:
а) проинициализировать таблицу кодов;
б) прочитать следующий код сжатых данных (если это будет код конца записи, то завершить работу);
в) найти Newcode в кодовой таблице и вывести соответствующую ему декомпрессированную последовательность отсчетов;
г) скопировать Newcode в буфер, где был записан предыдущий код (Prevcode).
· Если же Newcode находится в таблице, но не является ни кодом очистки, ни кодом конца записи, то необходимо:
а) вывести соответствующую ему декомпрессированную последовательность отсчетов;
б) взять первый байт декомпрессированного кода Newcode и декомпрессированного кода Prevcode, конкатенировать их и добавить в кодовую таблицу;
г) скопировать Newcode в буфер, где хранится Prevcode.
Если Newcode в таблице отсутствует, а, кроме того, он не является кодом очистки и кодом конца записи, то необходимо:
а) конкатенировать и вывести значение декомпрессированного кода Prevcode+ первый байт того же значения;
б) добавить в таблицу элемент для вышеприведенного значения;
в) скопировать Newcode в буфер Prevcode.
Метод сжатия LZW может быть применен не только для сжатия данных, каждая единица которых имеет размер в один байт, например, отсчетов яркости черно-белого полутонового изображения, но также и для сжатия данных, имеющих произвольный размер. В этом случае кодовые последовательности этих данных объединяются в группы по 8 двоичных единиц. Так если каждый отсчет содержит 4 двоичных единицы, то объединение в группы происходит по два отсчета, а если один отсчет представлен 16 двоичными единицами кода, то такая кодовая последовательность делится пополам. Величина сжатия, обеспечиваемая при использовании этого метода, невелика и лежит обычно в пределах 2 – 3 раза.
7 Метод кодирования Хаффмена
Этот метод позволяет получить код с минимальной средней длиной при заданном распределении вероятностей значений некоррелированных отсчетов сигналов. Особенностью этого метода кодирования является использование кодов переменной длины, при этом наиболее вероятным символам присваиваются наиболее короткие кодовые слова, а менее вероятным – длинные.
На рис. 2.5 показано кодовое дерево применительно к случаю кодирования шести символов A1, A2,
Рис.2.5.
A3, A4, A5, A6 и приведены вероятности, с которыми они появляются. Построение кодовой таблицы начинается с того, что два символа с наименьшими вероятностями объединяются в узел кодового дерева, которому приписывается их суммарная вероятность. Речь идет о символах A5 и A6, суммарная вероятность которых равна 0,14. Далее объединяются следующие символы или узлы с наименьшей вероятностью, как это показано на рисунке. Этот процесс продолжается до тех пор, пока ветви кодового дерева не сойдутся к одному узлу, расположенному в вершине. После этого ветви дерева в зависимости от того, в какую сторону они расходятся от узла, обозначаются нулями или единицами (на рис. 2.5 правые ветви обозначены нулями, а левые единицами). Для того, чтобы найти значение кодового слова, которое следует приписать каждому символу, необходимо идти от вершины кодового дерева к данному символу, записывая нули или единицы, которыми обозначены пройденные ветви.
В случае применения кода Хаффмена для сжатия изображений необходимо вначале осуществить декорреляцию сигнала, которым представлено изображение, например, используя для этой цели метод кодирования длин серий, а уже затем применять кодирование по Хаффмену.
8 ПРИНЦИПЫ КОДИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ
ОРТОГОНАЛЬНЫХПРЕОБРАЗОВАНИЙ
Особенностью данного метода сжатия изображений является то, что при этом методе кодируется не само изображение, а значения спектральных коэффициентов, получающихся при ортогональном преобразовании изображения. В результате ортогональных преобразований изображения
, имеющего сильные корреляционные связи между смежными отсчетами (пикселами), имеет место декорреляция, в результате которой значения спектральных коэффициентов 
оказываются практически некоррелироваными. В отличие от исходного изображения, для которого характерно в среднем равномерное распределение энергии между его отсчетами (пикселами), распределение энергии между спектральными коэффициентами резко неравномерно. При этом основная доля энергии приходится на спектральные коэффициенты с малыми индексами 
, 
, представляющие амплитуды низких пространственных частот и лишь небольшая ее часть – на прочие. В целях сжатия изображений спектральные коэффициенты, имеющие малую амплитуду, либо квантуются на малое число уровней, либо вообще отбрасываются, что позволяет для их представления использовать коды с малым числом двоичных единиц. Так как средний квадрат шума квантования пропорционален среднему квадрату квантуемого сигнала, то возникающие при этом искажения изображения невелики. При декомпрессии (восстановлении) изображения вначале по имеющемуся коду восстанавливаются спектральные коэффициенты, а затем путем обратного ортогонального преобразования восстанавливается само изображение. Поскольку при записи или при передаче спектральных коэффициентов, в отличие от записи или передачи значений отсчетов исходного изображения, только небольшая их часть представлена кодом с большим количеством двоичных единиц, в то время как для представления остальных расходуется значительно меньше двоичных единиц, если они вообще не отбрасываются, достигается высокая степень сжатия. Поскольку, как это следует из приведенного описания метода, восстановленное изображение отличается от исходного вследствие квантования спектральных коэффициентов с большими индексами на малое число уровней, данный метод сжатия относится к группе методов сжатия с потерей информации.