10445

Реализация JPEG-подобного алгоритма сжатия изображений

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

Информатика, кибернетика и программирование

Реализация JPEGподобного алгоритма сжатия изображений. Алгоритмы на основе дискретного косинусного преобразования наиболее распространенным из которых является разработанный в начале 1990х годов алгоритм JPEG Joint Photographic Expert Group являются относительно простыми в реал

Русский

2013-03-26

109 KB

61 чел.

Реализация JPEG-подобного алгоритма сжатия изображений.

Алгоритмы на основе дискретного косинусного преобразования, наиболее распространенным из которых является разработанный в начале 1990-х годов алгоритм JPEG (Joint Photographic Expert Group) являются относительно простыми в реализации и достаточно эффективными.

К положительным сторонам алгоритма относятся:

  •  Хорошая передача периодических структур даже при высоких степенях сжатия.
  •  Гибкость алгоритма и возможность подстраивать алгоритм под то или иные задачи дистанционного зондирования.
  •  Хорошая изученность алгоритма и наличие эффективных алгоритмов вычисления дискретного косинусного преобразования.
  •  Наличие серийных микросхем аппаратного сжатия и проектов прошивок ПЛИС.

К недостаткам алгоритма JPEG следует отнести:

  •  Эффективность алгоритма находится на уровне алгоритма ИСИ и уступает алгоритмам на основе вейвлет – преобразования.
  •  При высоких степенях сжатия изображение распадается на блоки.
  •  Проявляется эффект Гиббса в виде ореолов вокруг перепадов яркости в изображении.

Далее будет описана модификация алгоритма JPEG, предназначенная для сжатия потоковой видеоинформации.

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

Исходя из требуемой степени сжатия, можно определить расчетный объем информации, приходящейся на один макроблок. Если объем сжатой информации для текущего макроблока получился более чем в 1,1 раза больше расчетного, то коэффициент при матрице квантования γ увеличивается в 1,3 раза, что повышает степень сжатия следующего макроблока. Если объем сжатой информации для текущего макроблока получился меньше чем в 0,9 от расчетного, то коэффициент при матрице квантования γ уменьшается в 1,3 раза. Кроме того, если заполненность выходного буфера превышает 50%, то коэффициент γ увеличивается еще в 1,3 раза. После (или в процессе) сжатия очередного макроблока происходит передача данных из буфера. Объем передаваемой информации равен расчетному размеру сжатого макроблока. Если при передаче информации происходит опустошение буфера, то формируемый информационный пакет дополняется специальным кодом "пробел", который определяется на этапе формирования кодовой таблицы Хаффмана. Объем буфера должен быть не менее чем в 4 раза больше расчетного объема сжатого макроблока.

Блок – схема алгоритма приведена на рисунке 7.


Рисунок 7.


Сначала опишем собственно алгоритм сжатия. Изображение разбивается на блоки размером 8 на 8 пикселов. Каждый блок представляется в виде матрицы 8 на 8 элементов. Над каждым блоком производится дискретное косинусное преобразование по формуле

B = D*A*DT,          (1)

A – исходная матрица,

B – матрица после дискретного косинусного преобразования

D – фиксированная матрица. Коэффициенты матрицы, умноженные на 65536, приведены в таблице 3.

Таблица 3

23170

23177

23171

23170

23171

23179

23177

23177

32138

27246

18205

6393

-6393

-18205

-27246

-32138

30274

12540

-12540

-30274

-30274

-12540

12540

30274

27246

-6393

-32138

-18205

18205

32138

6393

-27246

23170

-23170

-23170

23170

23170

-23170

-23170

23170

18205

-32138

6393

27246

-27246

-6393

32138

-18205

12540

-30274

30274

-12540

-12540

30274

-30274

12540

6393

-18205

27246

-32138

32138

-27246

18205

-6393

Полученная матрица коэффициентов дискретного косинусного преобразования поэлементно делится на фиксированную матрицу квантования, а полученные результаты округляются до ближайшего целого числа. Для изменения степени сжатия матрицу квантования можно умножить на некоторое число γ. Возможный вид матрицы квантования приведен в таблице 4. Конкретный вид матрицы квантования может изменяться.

Таблица 4

1

1

1

1

1

2

2

4

1

1

1

1

1

2

2

4

1

1

1

1

2

2

2

4

1

1

1

1

2

2

4

4

1

1

2

2

2

2

4

8

2

2

2

2

2

4

8

8

2

2

2

4

4

8

8

16

4

4

4

4

8

8

16

16

После этого полученная матрица 8 на 8 элементов переводится в 64-элементный вектор при помощи "зигзаг-сканирования". Порядок обхода элементов приведен на рисунке 6.

Рисунок 6 – Зигзаг-сканиорвание.

Элементы полученного 64-элементного вектора разделяется на 2 массива. Первый массив (DC-коэффициенты), состоит их 1-х элементов всех 64 элементных векторов в макроблоке и сжимается отдельно. Оставшиеся коэффициенты образуют 63-элементный вектор.

Каждому ненулевому элементу в этом векторе ставится в соответствие пара вида <количество нулей перед числом, число>. При этом количество нулей перед числом не должно превышать 15. В противном случае в качестве числа берется нуль. Например, пусть 63-элементный вектор имеет вид:

7, 0, 0, 0, 10, 0, -19, 7, 0, 0, 0, 0, 7, 0, 0, …только нули…, 0.

Он будет закодирован следующим образом:

<0 7>, <3 10>, <1 -19>, <0 7>, <4 7>, <КОНЕЦ БЛОКА>.

Здесь <КОНЕЦ БЛОКА> обозначает специально зарезервированное значение пары.

Если же имеется 63-элементный вектор такого вида:

10, 0, 0, 5, …33 нуля…, 1, 0, -2, … только нули…, 0,

то он кодируется следующим образом:

<0 10>, <2 5>, <15 0>, <15 0>, <1 1>, <1 -2>, <КОНЕЦ БЛОКА>.

Здесь вторая, третья и четвертая пары кодируют последовательность из 33 нулей.

Затем полученный массив пар кодируется в виде двух потоков. Первый из них является байтовым и содержит т. н. байты-ключи, которые в 4 младших битах содержат информацию о числе пропускаемых нулей, а в 4 старших битах – информацию о количестве бит, необходимом для представления числа.

Таблица 5.

Число

Старшие биты байта-ключа

Информативные биты

0

0000

-

±1

0001

1 0

±2, 3

0010

11 10 00 01

±4…7

0011

111 110 101 100 000 001 010 011

±8…15

0100

±16…31

0101

±32…63

0110

±64…127

0111

±128…255

1000

±256…511

1001

±512…1023

1010

±1024…2047

1011

±2048…4095

1100

±4096…8191

1101

±8195…16383

1110

±16384…32767

1111

Информативные биты представляют собой все биты числа, включая знаковый, но исключая старший значащий бит, так как он при заданном числе бит всегда равен 1.

Символу <КОНЕЦ БЛОКА > соответствует байт-ключ 0xFF, причем такому ключу не ставятся в соответствие биты в потоке информативных бит.

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

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

Таблица 6.

Число

Количество бит

Информативные биты

0

0

-

-1 1

1

1 0

-3, -2, 2, 3

2

11 10 00 01

-7 -6 -5 -4 4 5 6 7

3

111 110 101 100 000 001 010 011

-15 -14 -13 -12 -11 -10 -9 -8 8 9 10 11 12 13 14 15

4

1111 1110 1101 1100 1011 1010 1001 1000

0000 0001 0010 0011 0100 0101 0110 0111

±16…31

5

±32…63

6

±64…127

7

±128…255

8

±256…511

9

±512…1023

10

±1024…2047

11

±2048…4095

12

±4096…8191

13

±8195…16383

14

±16384…32767

15

Информативные биты представляют собой все биты числа, включая знаковый, но исключая старший значащий бит, так как он при заданном числе бит всегда равен 1.

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

Алгоритм декодирования является обратным к алгоритму сжатия. Единственным отличием является использование вместо формулы (1) формулы

B = DT*A*D,          (2)

где А – матрица коэффициентов дискретного косинусного преобразования,

В – матрица фрагмента изображения.

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

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

Возможные варианты упрощенного алгоритма:

  •  Передача фиксированных коэффициентов из левого верхнего угла коэффициентов ДКП
  •  Передача N наибольших коэффициентов ДКП (с указанием их координат)
  •  Модификация предыдущих способов, включая сжатие по Хаффману (используя таблицу из 16-32 кодовых слов). Представляет интерес при больших степенях сжатия
  •  Передача коэффициентов (кроме, быть может, верхнего левого) по битовым плоскостям, ограничиваясь передачей заданного количества бит или битовых плоскостей


Формирование макроблока из 8 строк

Сжатие блока при заданном γ

азмер сжатого макроблока <0,9 от номинального

Размер сжатого макроблока >0,9, но <1,1 от номинального

Размер сжатого макроблока >1,1 от номинального

γ = γ / 1,3

γ = γ * 1,3

Буфер заполнен больше, чем на 50%

Буфер заполнен меньше, чем на 50%

γ = γ * 1,3

Передача макроблока

  •  

 

А также другие работы, которые могут Вас заинтересовать

83481. Міжнародні річки 38.03 KB
  Міжнародні річки річки що протікають по території декількох держав або розділяють території декількох держав. Розрізняють власне міжнародні річки судноплавні річки що мають вихід до моря і використовуються для цілей інтенсивного торгового судноплавства; трансграничні багатонаціональні річки ті що протікають по території декількох держав і що не мають виходу до моря вони або несудноплавні або судноплавство по них носить місцевий характер; та прикордонні річки що розділяють території держав. Більш того прибережні держави спільно...
83482. Правовий режим Антарктики. Система договору про Антарктику 37.85 KB
  З метою визначення міжнародноправового режиму Антарктики 1 грудня 1959 р. Для сприяння реалізації цілей і принципів Договору створен; Консультативна рада що надає свої рекомендації національним урядам та готує проекти конвенцій щодо ресурсів Антарктики. Конвенція про збереження морських живих ресурсів Антарктики 1980 р.
83483. Режим Антарктики. Секторальний принцип розподілу арктичних просторів 38.21 KB
  Природні ресурси військовостратегічна безпека міжнародні сполучення ось причини уваги яка приділяється режиму Арктики. Правовий режим Арктики встановлюється міжнародним правом а також законами приарктичних держав. Простори Арктики історично поділені між Росією Канадою США Данією та Норвегією на п\'ять секторів.
83484. Концепція загальної спадщини людства 38.35 KB
  З часом вона стала концепцією загальної спадщини людства поширивши захист на інтереси не тільки нинішнього але і майбутніх поколінь. У позитивне міжнародне право концепція загальної спадщини була введена Договором про принципи діяльності держав по дослідженню і Використанню космічного простору включаючи Місяць і інші небесні тіла 1967 р. Вони отримали право на участь у встановленні режиму загальної спадщини і в його використанні за ними закріплене праві виходу до моря через територію прибережних держав.
83485. Населення та громадянство в міжнародному праві 38.91 KB
  Населення будьякої держави складається з наступних категорій: громадян даної держави іноземних громадян осіб без громадянства. Виділяють наступні способи набуття громадянства: філіація; натуралізація укорінення; поновлення в громадянстві реінтеграція; дарування громадянства; оптація; трансферт. Філіація або набуття громадянства за народженням базується на двох принципах: права крові jus snguinis та права ґрунту jus soli. Різновидом натуралізації є спрощений порядок набуття громадянства певними категоріями осіб.
83486. Громадянство і підданство 33.42 KB
  У доктрині міжнародного права і національного законодавства деяких держав замість терміна громадянство використовується термін підданство причому в якості цілком рівнозначних. Підданство відрізняється від громадянства насамперед тим що воно: поперше є інститутом монархічної держави і означає політикоправовий зв\'язок підданого з монархом; подруге такий правовий зв\'язок характеризується не взаємним і рівнообов\'язковим як при громадянстві а одностороннім характером: підданий виконує перед монархом тільки обов\'язки а монарх щодо...
83487. Придбання і втрата громадянства 37.17 KB
  Виділяють наступні способи набуття громадянства: філіація; натуралізація укорінення; поновлення в громадянстві реінтеграція; дарування громадянства; оптація; трансферт. Філіація або набуття громадянства за народженням базується на двох принципах: права крові jus snguinis та права ґрунту jus soli. Різновидом натуралізації є спрощений порядок набуття громадянства певними категоріями осіб.
83488. Режим іноземців. Особи без громадянства 35.93 KB
  До іноземців окрім іноземних громадян також відносять осіб без громадянства. Режим правове положення іноземців визначають як сукупність прав та обовязків іноземців на території даної держави. Режим іноземців встановлюється внутрішнім законодавством держав з врахуванням їх міжнародних зобовязань.
83489. Біженці, вимушені переселенці. Право притулку 39.38 KB
  В якості біженців не розглядаються особи що винні у скоєнні: злочину проти миру воєнного злочину або злочину проти людяності; важкого злочину аполітичного характеру поза країною що надала притулок; дій що суперечать цілям та принципам ООН. Право притулку право кожної людини шукати притулок від переслідування в інших державах та користатися цим притулком а також право держави дозволяти вїзд та проживання на її території особі яка переслідується в іншій державі за політичними мотивами. Територіальний притулок означає що держави...