C применением кодов Хаффмана

Кафедра 308

 

Лабораторная работа №2

на тему: «Методы сжатия изображений»

по дисциплине

«Обработка аудио- и видеоинформации»

Вариант 5

 

 

 

Студент:

Группы № 03-518

Шпилевой С.Г.

 

Преподаватель:

Доцент, к.т.н.

Максимов А.Н.

 

 

Москва 2013

Задание

1) Провести «вручную» сжатие 2-ух фрагментов данных методом группового кодирования. Сравнить полученные коэффициенты сжатия.

2) Провести «вручную» сжатие 2-ух фрагментов данных методом LZW. Сравнить полученные коэффициенты сжатия.

3) Провести «вручную» сжатие 2-ух фрагментов данных с применением кодов Хаффмана. Сравнить полученные коэффициенты сжатия.

4) Провести «вручную» сжатие 2-ух фрагментов данных с применением алгоритмов RLE, LZW и кодов Хаффмана. Описать полученные результаты и сделать соответствующие выводы.

5) Реализоваь алгоритм JPEG в среде Mathcad и применить его для сжатия двух фрагментов изображения согласно варианту задания при q=2 для 1-ого фрагмента и при q=2 и 7 для 2-ого фрагмента. Сравнить полученные коэффициенты сжатия и объяснить результаты. Сделать вывод о влиянии пиксельных значений исходных фрагментов изображения на эффективность сжатия.

 

Исходные данные

 

	Номер задания
1 (RLE)	2 (LZW)	3 (Haffman)	4 (все три метода)	5 JPEG
Вариант 5	1,2	5,8	11,10		21,26

 

Практическая часть

 

Сжатие «вручную» 2-ух фрагментов данных

Методом группового кодирования

Алгоритм группового кодирования известный в англоязычной литературе как RLE – Run Length Encoding является самым простым и, как следствие, самым быстрым и нетребовательным к ресурсам ЭВМ. Его идея предельно проста: если во входном потоке данных встречаются повторяющиеся группы символов (байтов), то в выходной (сжатый) поток записываются лишь число символов в группе и сам повторяющийся символ.

1) Исходная строка символов:

bbbbbbbccccccbbcaaaaaaabbbccccaaaaaaabbbbbaaaaadddddddddaaaadd

 

Исходная строка символов после кодирования будет иметь вид:

7b6c2b1c7a3b4c7a5b5a9d4a2d

 

Так как исходная строка занимала 62 байта, а кодированная – 26 байт, то в результате достигается коэффициент сжатия K_сж = 62/26 = 2,385 > 1, следовательно,сжатие считается эффективным.

2) Исходная строка символов:

cbcbbbbcdccddaddabbddccaaaccddddccbbbaaadddddbbbbcacccddaabb

 

Исходная строка символов после кодирования будет иметь вид:

03cbc4b02cd2c2d1a2d1a2b2d2c3a2c4d2c3b3a5d4b02ca3c2d2a2b

 

Так как исходная строка занимала 60 байт, а кодированная – 55 байт, то в результате достигается коэффициент сжатия K_сж = 60/55 = 1,09 > 1, следовательно, сжатие считается эффективным.

 

Сжатие «вручную» 2-ух фрагментов

Данных методом LZW

LZW относится к группе словарных методов сжатия, которые разбивают входной поток данных на слова. Словом называется последовательность символов (байт). Совокупность всех слов называется словарем, в котором каждое слово содержится под своим номером (индексом, ссылкой). В выходной поток записываются только ссылки. Эффект сжатия возникает за счет того, что длина ссылок, как правило, меньше длины слов. Словарь формируется итеративно, по ходу работы алгоритма сжатия/распаковки.

 

5) b | a | a | c | c | b | cc | bc | a | ba | cc | ab | ba | ab | aa | ab |cc

1 0 0 2 2 1 6 8 0 3 6 11 3 11 4 11 6

 

Номер слова	Слово	Номер слова	Слово
	a		bca
	b		ab
	c		bac
	ba		cca
	aa		abb
	ac		baa
	cc		aba
	cb		aaa
	bc		abc
	ccb

 

Сжатый поток состоит из ссылок:

1 0 0 2 2 1 6 8 0 3 6 11 3 11 4 11 6

 

Входной поток был байтовым, на каждую ссылку отводится тоже один байт, получаем коэффициент сжатия К_сж = 27/17 = 1.588 > 1. Сжатие считается эффективным.

 

8) aïaaïcïbïcbïbïbbïcïccïbbïbcïaïcc

0 3 2 1 5 1 8 2 10 8 6 0 10

 

Номер слова	Слово	Номер слова	Слово
	a		bb
	b		bbc
	c		cc
	aa		ccb
	aac		bbb
	cb		bca
	bc		ac
	cbb

 

Сжатый выходной поток состоит из ссылок: 0 3 2 1 5 1 8 2 10 8 6 0 10.

 

Входной поток был байтовым, на каждую ссылку отводится тоже один байт, получаем коэффициент сжатия К_сж = 20/13 = 1.538 > 1, следовательно, сжатие считается эффективным.

Сжатие «вручную» 2-х фрагментов данных

c применением кодов Хаффмана

11) gdadafghggfghababahbagggabcdcdcahhggaghhhgacagca

 

Рассчитаем частоты появления символов алфавита:

 

g = 13/48 = 0,271

d = 4/48 = 0,083

a = 12/48 = 0,25

f = 2/48 = 0,042

h = 8/48 = 0,167

b = 4/48 = 0,083

c = 5/48 = 0,104

 

Сформируем дерево:

 

Код Хаффмана символов алфавита:

 

X	Code
g
a
h
c
b
d
f

 

Предположим, что входной поток был байт ориентированным, тогда

 

K_сж = 8/ (0,271∙1 + 0,250∙2 + 0,167∙3 + 0,104∙4 + 0,083∙5 + 0,083∙6 + 0,042∙6) = 8/ 2,853 = 2,804.

 

Сжатие считается эффективным.

10) faaadddddbbbccbaffbbbaabbabbbabbfcadcbfababadddab

 

Рассчитаем частоты появления символов алфавита:

 

a = 13/49 = 0,265

b = 18/49 = 0,367

c = 4/49 = 0,082

d = 9/49 = 0,184

f = 5/49 = 0,102

 

Сформируем дерево:

 

Код Хаффмана символов алфавита:

 

X	Code
b
a
d
f
c

 

Предположим, что входной поток был байт ориентированным, тогда

K_сж = 8/ (0,367∙1 + 0,265∙2 + 0,184∙3 + 0,102∙4 + 0,082∙4) = 8/ 2,185 = 3,661.

 

Сжатие считается эффективным.