Данный
Алгоритм сжатия используются и
предназначен для сжатия картинок
то есть растровых
изображений(растровое изображение
- это когда каждый пиксель на
картинке задаётся числом которое
представляет собой номер цвета в
текущей палитре). Растровое
изображение хранится в формате BMP.
Поэтому любая картинка
представляет собой массив пикселей
например в паскале это выглядит так
Pixels: Array [1..256,1..256] of Byte
Цвет каждого пикселя кодируется
Байтом(байт это восемь бит- а бит
это либо ноль либо один поэтому
один байт это 256 в десятичной
системе ) Так вот у нас есть массив
который содержит полную информацию
о картинке картинка размером 256*256*256
- третье измерение это цвет.
В алгоритме JPEG исходное изображение представляется двумерной матрицей размера N*N, элементами которой являются цвет или яркость пиксела. Упаковка значений матрицы выполняется за три этапа:
Высокая эффективность сжатия, которую дает этот алгоритм, основана на том факте, что в матрице частотных коэффициентов, образующейся из исходной матрицы после дискретного косинусного преобразования, низкочастотные компоненты расположены ближе к левому верхнему углу, а высокочастотные - внизу справа. Это важно потому, что большинство графических образов на экране компьютера состоит из низкочастотной информации, так что высокочастотные компоненты матрицы можно безболезненно выбросить.“Выбрасывание” выполняется путем округления частотных коэффициентов. После округления отличные от нуля значения низкочастотных компонент остаются, главным образом, в левом верхнем углу матрицы. Округленная матрица значений кодируется с учетом повторов нулей. В результате графический образ сжимается более чем на 90% , теряя очень немного в качестве изображения только на этапе округления.
Основным этапом работы алгоритма является дискретное косинусное преобразование (ДКП), представляющее собой разновидность преобразования Фурье. Оно позволяет переходить от пространственного представления изображения к его спектральному представлению и обратно. Что нужно сделать на первом этапе первом этапе? Следует создать ДКП матрицу, используя такую формулу :
DCT = 1/sqr(N), если i=0 ij DCT = sqr(2/N)*cos[(2j+1)*i*3.14/2N], если i > 0 ij N = 8, 0
На этом этапе мы посчитаем матрицу квантования, используя этот псевдокод: for i:=0 to 8 do for j:=0 to 8 do Q[i,j] = 1+((1+i+j)*q); где q - это коэффициент качества, от него зависит степень потери качества сжатого изображения для q = 2 имеем матрицу квантования:
| 3 5 7 9 11 13 15 17|
| 5 7 9 11 13 15 17 19|
| 7 9 11 13 15 17 19 21|
Q = | 9 11 13 15 17 19 21 23|
|11 13 15 17 19 21 23 25|
|13 15 17 19 21 23 25 27|
|15 17 19 21 23 25 27 29|
|17 19 21 23 25 27 29 31|
теперь нужно каждое число в матрице квантования разделить на число в соответствущей позиции в матрице RES, в результате получим:
| 30 0 0 0 0 0 0 0|
| -7 8 1 1 0 0 0 0|
|-11 6 0 1 0 0 0 0|
A = | -5 -3 0 0 0 0 0 0|
| -7 -3 2 0 0 0 0 0|
| -4 4 0 0 0 0 0 0|
| -1 0 1 0 0 0 0 0|
| -3 1 0 0 0 0 0 0|
как вы видите здесь имеется довольно много нулей, мы получим наиболее длинную последовательность нулей, если будем использовать следущий алгоритм:
+----+----+----+----+----+----+----+----+
| 1 | 2 | 6 | 7 | 15 | 16 | 28 | 29 |
+----+----+----+----+----+----+----+----+
| 3 | 5 | 8 | 14 | 17 | 27 | 30 | 43 |
+----+----+----+----+----+----+----+----+
| 4 | 9 | 13 | 18 | 26 | 31 | 42 | 44 |
+----+----+----+----+----+----+----+----+
| 10 | 12 | 19 | 25 | 32 | 41 | 45 | 54 |
+----+----+----+----+----+----+----+----+
| 11 | 20 | 24 | 33 | 40 | 46 | 53 | 55 |
+----+----+----+----+----+----+----+----+
| 21 | 23 | 34 | 39 | 47 | 52 | 56 | 61 |
+----+----+----+----+----+----+----+----+
| 22 | 35 | 38 | 48 | 51 | 57 | 60 | 62 |
+----+----+----+----+----+----+----+----+
| 36 | 37 | 49 | 50 | 58 | 59 | 63 | 64 |
+----+----+----+----+----+----+----+----+
итак у нас получилась последовательность: 30 0 -7 -11 8 0 0 1 6 -5 -7 -3 0 1 0 0 0 1 0 -3 -4 -1 4 2 0 0 0 0 0 0 0 0 0 0 0 -3 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3. Этап Вторичного Сжатия.
Самым распространенным методом вторичного сжатия является метод Хаффмана и его разновидности. Сжатие Хаффмана - статистический метод сжатия, который уменьшает среднюю длину кодового слова для символов алфавита. Код Хаффмана является примером кода, оптимального в случае, когда все вероятности появления символов в сообщении - целые отрицательные степени двойки. Код Хаффмана может быть построен по следующему алгоритму: 1.Выписываем в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте; 2.Последовательно объединяем два символа с наименьшими вероятностями появления в новый составной символ, вероятность появления которого полагается равной сумме вероятностей составляющих его символов. В конце концов, мы построим дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него; 3.Прослеживаем путь к каждому листу дерева помечая направление к каждому узлу (например, направо - 1, налево - 0). Поясним создание дерева с использованием иллюстраций :
A B C D E 10 5 8 13 10 B C A E D 5 8 10 10 13 A E BC D 10 10 13 13 BC D AE 13 13 20 AE BCD 20 26 AEBCD 46
Теперь, если в тексте встречается, например, символ "d" , то вместо того, чтобы выделять этому символу байт, после сжатия символ займет всего 2 бита (01).