Файл: Создание программного обеспечения для сжатия изображений.pdf

JPEG использует разложение изображения по косинусоидальным функциям, поэтому потери в нем (даже при заданных минимальных потерях) проявляются в волнах и ореолах на границе резких переходов цветов. Именно за этот эффект его не любят использовать при сжатии изображений, которые готовят для качественной печати: там этот эффект может стать очень заметен.

Вытеснение JPEG фрактальным алгоритмом в повсеместном использовании произойдет еще, не скоро (хотя бы в силу низкой скорости архивации последнего), однако в области приложений мультимедиа, в компьютерных играх его использование вполне оправдано. 

2.2Алгоритм архивации графики JPEG

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

Подготовка:

Нужно преобразовать изображение в вид яркость/цветность, можно использовать цветовую схему YCbCr (YUV), вот формулы перевода:

Y = 0.299*R + 0.578*G + 0.114*B 

Cb = 0.1678*R - 0.3313*G + 0.5*B 

Cr = 0.5*R - 0.4187*G + 0.0813*B 

Y нужно сохранить без изменений, его можно сжать любым алгоритмом без потери данных. 

2.2.1 Дискретное косинус преобразование

Основным этапом работы алгоритма является дискретное косинусное преобразование (ДКП), представляющее собой разновидность преобразования Фурье. Оно позволяет переходить от пространственного представления изображения к его спектральному представлению и обратно. Что нужно сделать на первом этапе? Следует создать ДКП матрицу, используя такую формулу:

DCT = 1/sqr(N), если i=0

DCT = sqr(2/N)*cos[(2j+1)*i*3.14/2N], если i > 0

N = 8, 0 < i < 7 , 0 < j < 7

в результате имеем (матрица ДКП):

|.353553 .353553 .353553 .353553 .353553 .353553 .353553 .353553|

|.490393 .415818 .277992 .097887 -.097106 -.277329 -.415375 -.490246|

|.461978 .191618 -.190882 -.461673 -.462282 -.192353 .190145 .461366|

|.414818 -.097106 -.490246 -.278653 .276667 .490710 .099448 -.414486|

|.353694 -.353131 -.354256 .352567 .354819 -.352001 -.355378 .351435|

|.277992 -.490246 .096324 .416700 -.414486 -.100228 .491013 -.274673|

|.191618 -.462282 .461366 -.189409 -.193822 .463187 -.460440 .187195|

|.097887 -.278653 .416700 -.490862 .489771 -.413593 .274008 -.092414|

например, нам нужно сжать следующий фрагмент изображения:

| 95 88 88 87 95 88 95 95|

|143 144 151 151 153 170 183 181|

|153 151 162 166 162 151 126 117|

IMG = |143 144 133 130 143 153 159 175|

|123 112 116 130 143 147 162 189|

|133 151 162 166 170 188 166 128|

|160 168 166 159 135 101 93 98|

|154 155 153 144 126 106 118 133|

|-33 -40 -40 -41 -33 -40 -33 -33|

| 15 16 23 23 25 42 55 53|

| 25 23 34 38 34 23 -2 -11|

IMG = | 15 16 5 2 15 25 31 47|

| -5 -16 -12 2 15 19 34 61|

| 5 23 34 38 42 60 38 0|

| 32 40 38 31 7 -27 -35 -30|

| 26 27 25 16 -2 -22 -10 5|

вот формула, по которой производится ДКП: RES*IMG*DCT

Для начала нужно посчитать промежуточную матрицу: TMP= IMG*DCT

|-103 -3 1 2 4 0 -1 5|

| 89 -40 12 -2 -7 5 1 0|

| 57 31 -30 6 2 0 5 0|

TMP = | 55 -28 24 1 0 -8 0 0|

| 32 -60 18 -1 14 0 -8 1|

| 84 -11 -37 17 -24 4 0 -4|

| 19 81 -16 -20 8 -3 4 0|

| 22 40 11 -22 8 0 -3 2|

затем умножаем ее на ДКП матрицу: RES = TMP*DCT

| 91 3 -5 -6 2 0 1|

|-38 -57 9 17 -2 2 2|

|-80 58 0 -18 4 3 4|

RES = |-52 -36 -11 13 -9 3 0|

|-86 -40 44 -7 17 -6 4|

|-62 64 -13 -1 3 -8 0|

|-16 14 -35 17 -11 2 -1|

|-53 32 -9 -8 22 0 2|

2.2.2 Этап Квантования

На этом этапе мы посчитаем матрицу квантования, используя этот псевдокод:

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

2.2.3 Этап Вторичного Сжатия

Самым распространенным методом вторичного сжатия является метод Хаффмана и его разновидности.

Сжатие Хаффмана - статистический метод сжатия, который уменьшает среднюю длину кодового слова для символов алфавита. Код Хаффмана является примером кода, оптимального в случае, когда все вероятности появления символов в сообщении - целые отрицательные степени двойки. Код Хаффмана может быть построен по следующему алгоритму:

1.Выписываем в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте;

2.Последовательно объединяем два символа с наименьшими вероятностями появления в новый составной символ, вероятность появления которого полагается равной сумме вероятностей составляющих его символов. В конце концов, мы построим дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него;

3.Прослеживаем путь к каждому листу дерева помечая направление к каждому узлу (например, направо - 1, налево - 0).

Подведя итог над вышесказанным, покажем обобщенную структуру компрессора и декомпрессора по стандарту JPEG:

Рисунок 2.2.1 - Компрессор и декомпрессор JPEG

3. РАЗРАБОТКА ПРОГРАММНО-АППАРАТНЫХ МОДУЛЕЙ

3.1 Разработка программного модуля на языке JPHP

Прежде, чем приступить к разработке программного обеспечения для сжатия изображений, необходимо выбрать алгоритм обработки и язык программирования. Выбор пал на проект Devel Next, среда разработки которого довольно проста в использовании и построена на языке JPHP.

JPHP – это альтернативная реализация языка php, от автора DevelNext. Проект jphp был начат еще в октябре 2013 года, целью проекта было написать компилятор в байткод (аля машинный код) Java, который затем бы выполнялся на виртуальной машине Java (да это и язык, и виртуальная машина, название одинаковое). Виртуальная машина (JVM если коротко), способна выполнять этот “машинный код” очень быстро, применять технику JIT там, где необходимо и даже оптимизировать полученный код, все для того, чтобы код выполнялся быстрее.