10456

Алгоритмы сжатия изображений

Реферат

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

Алгоритмы сжатия изображений Введение В настоящее время в космических системах ДЗЗ отмечается быстрый рост производительности оптикоэлектронных систем съемки Земли в то время рост пропускной способности радиолиний передачи данных характеризуется более медленным...

Русский

2013-03-26

163 KB

91 чел.

Алгоритмы сжатия изображений

Введение

В настоящее время в космических системах ДЗЗ отмечается быстрый рост производительности оптико-электронных систем съемки Земли, в то время рост пропускной способности радиолиний передачи данных характеризуется более медленными темпами. Это обстоятельство приводит к возрастанию требований к аппаратуре сжатия видеоинформации. Так, за последние 10 лет характерная степень сжатия алгоритмов, аппаратно реализуемых на борту, КА возросла с 2-3 до 10 и более раз. Такую степень сжатия невозможно реализовать при использовании алгоритмов сжатия без потерь. Поэтому, несмотря на то, что алгоритмы сжатия без потерь используются в современных космических системах (там, где потери радиометрической точности являются недопустимыми), наиболее активно развиваются и являются востребованными алгоритмы сжатия изображений с потерями. В настоящее время для этих целей, как правило, применяются алгоритмы 4 семейств, отличающихся по эффективности и по сложности реализации: ДИКМ (дифференциально-импульсная кодовая модуляция), ИСИ (иерархическая сеточная интерполяция), JPEG и алгоритмы на основе вейвлет-преобразования.

Алгоритмы семейства ДИКМ отличаются простотой аппаратной реализации на ПЛИС и строгим постоянством выходного информационного потока, однако качество сжатого изображения сохраняется на высоком уровне только при степени сжатия 4 бита на пииксел. При степени сжатия до 2 бита на пиксел деградация изображения становится очень большой, но еще приемлемой для некоторых применений. Сжатие до 1 бита на пиксел искажает изображение до неприемлемого уровня.

Алгоритм JPEG и его аналоги получили широкое распространение в компьютерной технике. Они отличаются умеренной сложностью аппаратной реализации и позволяют регулировать степень сжатия в широких пределах – до 0,5-1 бита на пиксел, причем при степени сжатия 1 бит на пиксел качество изображения оказывается достаточно высоким. К их недостаткам следует отнести непостоянство выходного информационного потока, которое требует использования буферной памяти.

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

Алгоритмы на основе вейвлет – преобразования являются наиболее эффективными алгоритмами, однако и сложность их реализации максимальна. Правда, следует отметить, что они так же, как и ДИКМ, могут обеспечивать постоянство выходного информационного потока.

Критерии качества изображений.

При сравнении алгоритмов сжатия изображений с потерями существует проблема, заключающаяся в том, что отсутствует критерий оценки качества сжатого изображения. На практике используются 4 критерия:

  •  Метод экспертных оценок
  •  Среднеквадратичное отклонение
  •  Максимальное отклонение
  •  Отношение "сигнал/шум".

Пусть x(i, j) – исходное изображение,

y(i, j) -сжатое изображение,

n – число пикселов в изображении.

Тогда:

Среднеквадратичное отклонение .

Максимальное отклонение .

Отношение "сигнал/шум" .

ДИКМ

Алгоритм ДИКМ основан на предсказании сигнала в кодируемом пикселе и на использовании одной или нескольких неравномерных шкал квантования.

Пример неравномерной шкалы квантования.

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

Алгоритм JPEG

JPEG - один из новых и достаточно мощных алгоритмов. Практически, он является стандартом де-факто для полноцветных изображений. Оперирует алгоритм областями 8x8, на которых яркость и цвет меняются сравнительно плавно. Вследствие этого при разложении матрицы такой в двойной ряд по косинусам (см. формулы ниже) значимыми оказываются только первые коэффициенты. Таким образом, сжатие в JPEG ocуществляется за счет плавности изменения цветов в изображении.
Алгоритм разработан группой экспертов в области фотографии специально для сжатия 24-битовых изображений. JPEG - Joint Photographic
Expert Group- подразделение в рамках ISO - Международной организации по стандартизации. Название алгоритма читается как [jei'peg]. В целом алгоритм основан на дискретном косинусном преобразовании (в дальнейшем - ДКП), применяемом к матрице изображения для получения некоторой новой матрицы коэффициентов. Для получения исходного изображения применяется обратное преобразование.

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

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

Как работает алгоритм JPEG
Итак, рассмотрим алгоритм подробнее (рис. 6). Пусть мы сжимаем 8 - битовое изображение.

Рисунок 6.

Шаг 1. Разбиваем исходное изображение на матрицы 8x8.

Шаг 2. В упрощенном виде ДКП при n=8 можно представить так:

,      (11)

где

,       (12)

        (13)

Рисунок 7. Базисные функции одномерного ДКП.

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

Шаг 4. Производим квантование. В принципе это просто деление рабочей матрицы на матрицу квантования поэлементно.

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

В стандарт JPEG включены рекомендованные матрицы квантования, построенные опытным путем. Матрицы для большей или меньшей степени сжатия получают путем умножения исходной матрицы на некоторое число A.

С квантованием связаны и специфические эффекты алгоритма. При больших значениях коэффициента А потери в низких частотах мс быть настолько велики, что изображение распадется на квадраты 8x8. Потери в высоких частотах могут проявиться в так называемом эффекте Гиббса, когда вокруг контуров с резким переходом цвета образуется своеобразный "нимб".

Шаг 5. Переводим матрицу 8x8 в 64-элементный вектор при помощи "зигзаг"-сканирования, т. е. берем элементы с индексами (0,0), (0,1), (1,0), (2,0)...

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

Таким образом, в начале вектора мы получаем коэффициенты матрицы, соответствующие низким частотам, а в конце - высоким.

Шаг 6. Свертываем вектор с помощью алгоритма группового кодирования. При этом получаем пары типа <пропустить, число>, где "пропустить" является счетчиком пропускаемых нулей, а "число" - значение, которое необходимо поставить в следующую ячейку. Так, вектор 42 3 0 0 0 2 0 0 0 0 1 ... будет свернут в пары (0,42) (0,3) (3,-2) (4,1)....

Шаг 7. Свертываем получившиеся пары кодированием по Хаффману с фиксированной таблицей.

Отрицательными сторонами алгоритма является то, что:

  •  При повышении степени сжатия изображение распадается на отдельные квадраты (8x8). Это связано с тем, что происходят большие потеря в низких частотах при квантовании и восстановить исходные данные становится невозможно.
  •  Проявляется эффект Гиббса - ореолы по границам резких переходов цветов.

Для обеспечения постоянства выходного информационного потока на выходе блока аппаратного устанавливается специальная буферная память небольшой емкости. Входящая информация разбивается на блоки (обычно по 8 строк), и каждый блок сжимается по отдельности. Объем сжатого блока сравнивается с заданным, и, если полученный объем больше заданного, происходит увеличение матрицы квантования, что приводит к увеличению степени сжатия в А раз. Подобный процесс, в сочетании с контролем степени заполненности буфера (при заполнении буфера на 50-75% степень сжатия увеличивается) приводит к тому, что на выходе буфера получается постоянный информационный поток.

Рисунок 9.

Алгоритм ИСИ

Метод иерархической сеточной интерполяции основан на идее сокращения избыточности входных данных за счет использования прореженного изображения для аппроксимации промежуточных отсчетов.

На рисунке показано расположение отсчетов для 4 иерархических уровней для на изображении размера 9х9.

Рисунок 10. Размещение отсчетов иерархических уровней на изображении

Анализируя схему, легко видеть, что r-й уровень представляет собой сетку с шагом 2r, из которой исключены отсчеты, лежащие в узлах сеток с шагами 2r+1, 2r+2 ... 2R-1 . Таким образом, данное представление не является избыточным и не увеличивает объем входных данных при сжатии. При этом иерархический уровень с большим шагом используется для аппроксимации уровня с меньшим шагом. Очевидно, что при таком подходе для сжатия каждого уровня представления изображения применяется один и тот же алгоритм, поэтому можно ограничиться описанием последовательности процедур обработки для уровня  произвольным фиксированным номером r. Общая схема процесса преобразования информации представлена на рис. 23.

Рисунок 11. Общая схема преобразования информации.

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


 

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

74202. Functional programming languages and tools 55 KB
  Functional programming languages (FPL) were originally developed specifically to handle symbolic computation and list-processing applications. In FPLs the programmer is concerned only with functionality, not with memory-related variable storage and assignment sequences.
74203. Сылақ және майлау жұмыстарына арналған машиналар 717.44 KB
  Сылақ станциялары мен агрегаттары және қол ысқылауыштарының атқаратын қызметі негізгі параметрлері және қолданылу облысы. Жылжымалы сылау агрегаттары. Еден асты негіздерін дайындауға және шатыр мен гидроизоляциялауға арналған машиналар құрылымы мен жұмысы Жоспар: Сылақ станциялары мен агрегаттары және қол ысқылауыштарының атқаратын қызметі.
74204. Жер жұмыстарына арналған машиналар туралы жалпы мағлұматтар 147.63 KB
  Жұмысшы органдары мен топырақпен өзара әсерлесуі. Топырақтардың физикамеханикалық сипаттамасы Жоспар: Жер жұмыстарына арналған машиналар туралы жалпы мағлұматтар. Жұмысшы органдары мен топырақпен өзара әсерлесуі. Топырақтардың физикамеханикалық сипаттамасы.
74205. Жер қазу-тасымалдау машиналары. Қызметі, қолданылу облысы. Негізгі техника-экономикалық көрсеткіштері 659.49 KB
  Жер қазутасымалдау машиналары ЖҚТМ деп топырақты массивтен тарту күші арқылы ажыратып оны түсіру орнына өз жүрісімен жеткізетін құрылыс машиналарын атайды. Негізгі атқаратын жұмысшы операциялары: топырақты қабаттап өңдеу оны тасымалдау құрылыс объектісі негізіне төсеу немесе төгу топырақ беттерін жоспарлау. Негізгі қызметі: топырақты жер бетімен сүргіш органы арқылы азғана арақашықтыққа 150м жылжыту арқылы қабаттап өңдеу. Мына жағдайларда қолданылады: құрылыс алаңын дайындау барысында топырақтың беткі құнарлы қабатын алу;...
74206. Экскаваторлар. Жіктелуі, қолданылу облысы. Жұмысшы органының негізгі түрлері, параметрлері және құрылыс экскаваторларының индексациясы 885.5 KB
  Біршөмішті экскаватордың жұмыс циклі рет-ретімен орындалатын топырақ қазу, оны шөмішпен төсеу орнына тасымалдау, топырақты үйме мен көлік құралына аудару арқылы шөмішті босату және келесі циклді бастау үшін шөміштің алғашқы позициясына қайтып оралу операцияларынан тұрады
74207. Бұрғылау машиналары және жабдықтары. Бұрғылау құралы. Шпурлар бұрғылауға арналған машиналар. Бұрғылау-кранды машиналар 1.45 MB
  Бұрғылау – бұл топырақ массивінде қирау заттарын сыртқа шығара отырып, цилиндрлік жазықтықтар түзу арқылы топырақты қирату процесі. Егер диаметрі 75 мм дейін және тереңдігі 9 м болса жазықтықтар шпурлар деп, ал өлшемдері үлкен болса бұрғы деп аталынады.
74208. Тиеп-түсіру машиналары. Тиегіштер түрлері. Жұмыс процесі 455.42 KB
  Жұмысшы жабдық нұсқаларының көптігі және жұмыс органдарының ауыспалылығы құрылыс тиегіштерінің жұмыс жасау облысын кеңейтіп оларды құрылыс тасымалының барлық этаптарында қолданылатын универсалды машинаға айналдырады. БФПТтердің жұмысшы жабдығы жебе коромысло тартқыш гидроцилиндрлер құратын рычагты механизмнен тұрады. Сонымен қатар түсіру биіктігін ондаған сантиметрге жоғарылатытын машинаның универсалдылығын арттыратын жақты шөміштер де қолданылады бірақ олар жұмысшы жабдықтың күрделенуіне қосымша гидравликалық контурлар орнату...
74209. Машиналардың ұсақтау типтері жәнеұсақталатын материал беріктігі мен ұсақталу дәрежесіне қарай оларды таңд. 1.43 MB
  Грохоттардың қолданылуы принциптік схемалары жұмыс процестері негізгі параметрлері мен жұмыс өнімділігі Жоспар: Машиналардың ұсақтау типтері және ұсақталатын материал беріктігі мен ұсақталу дәрежесіне қарай оларды таңдап алу. Тас жыныстарды бұзу мен уатудың механикалық процесі ұсақтау деп аталады және тас ұсақтағыш машиналар тас ұсақтағыштарды қолдана отырып ұсақтау жаншу сындыру және үйкеу көмегімен жүзеге асырылады. Ұсақтау машиналарында ұсақталатын жыныстың қасиеттеріне және ірілігіне қарай әртүрлі әдістер бірге қолданылады.
74210. Бетон қоспалары мен сылақтарын дайындауға арналған машиналар мен жабдықтар. Араластырғыш машиналардың қызметі мен құрамы. Араластырғыш машиналардың жіктелуі 1.46 MB
  Бетон араластырғыштар мен циклді және үздіксіз жұмыс жасайтын сылақ араластырғыштардың типтері негізгі параметрлері мен конструктивтік схемалары. Бетон қоспаларын тығыздау қажеттіліктері мен тәсілдері Жоспар: Араластырғыш машиналардың қызметі мен құрамы. Бетон араластырғыштар мен циклді және үздіксіз жұмыс жасайтын сылақ араластырғыштардың типтері негізгі параметрлері мен конструктивтік схемалары.