takya.ru страница 1
скачать файл

Алгоритмические основы машинной графики

Лекция № 11



    Сжатие изображений 2.

Курс лекций «Алгоритмические основы машинной графики» читается в качестве специального курса на Механико-математическом факультете Московского Государственного Университета им. М.В. Ломоносова.
Содержание

1. Введение. 1

2. Изображение как функция. 2

2.1 Разложение в ряд Фурье. 2

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

2.3 Вейвлеты (Wavelets) 5

2.4 S – преобразование. 6

3. Фрактальное сжатие. 7

Литература 7




1.Введение.


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

2.Изображение как функция.


Рисунок 1.Функция Изображения.

Будем рассматривать изображение как целочисленную функцию 2-ух переменных , где значение цвета, либо его номер в палитре, либо, например, интенсивность – это зависит от цветовой модели представления изображения (см. Рисунок 1.Функция Изображения)

Эту функцию можно разложить в ряд:

Где мы формально заменили на , a , – базисные функции.

2.1Разложение в ряд Фурье.


Здесь: , соответственно получим разложение:

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

Для сжатия изображений практически не используется.

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


В формате JPEG используется дискретное косинусное преобразование (ДКП) (DCT - Discrete Cosine Transform)

Пусть наше изображение квадратное, т.е. размера .

Рассмотрим прямое преобразование (Forward):

, где ,

Существует и обратное преобразование (inverse):



,где ,

В чём же смысл, если коэффициентов столько же?

Рассмотрим некоторые:

- фактически среднее арифметическое изображения

- появляется первый косинус (см. Рисунок 2. График при i=1, j=0.)

Рисунок 2. График при i=1, j=0.



(см. Рисунок 3)

Рисунок 3. График при i=2, j=0.

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

В формате JPEG, перед тем как применить ДКП, изображение разбивается на блоки размером 8 на 8 пикселей (это становится если задать высокую степень компрессии). Затем к ним применяется ДКП.

Некоторые коэффициенты можно хранить приближённо, т.к. глаз не сможет заметить достаточно маленьких изменений. Операция округления коэффициентов называется квантованием и выполняется по формуле:

Здесь означает покомпонентное умножение плюс взятие целой части.

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

Рисунок 4. Зигзаг упорядочивание.

Затем используется сжатие без потерь сначала RLE, а затем метод Хаффмана с фиксированной таблицей.

Соответственно составим краткую схему алгоритма сжатия применяемого в JPEG:



  1. Разбиение изображения на блоки .

  2. Применение к ним преобразования(FDCT).

  3. Квантование.

  4. Зигзаг упорядочивание.

  5. RLE+Huffman.

Восстановление изображение - этот же алгоритм только в обратном порядке.

2.3Вейвлеты (Wavelets)


Идея в использовании локального всплеска (см. Рисунок 5. Пример локального всплеска.) вместо глобально-периодических функций, т.е.

таких функций , что:



Рисунок 5. Пример локального всплеска.



и , при .

Рассмотрим пример таких функций - систему Хаара. В общем виде она записывается так:







- общий вид обратного



Рисунок 6. Рисунок 7.

Если преобразование применяется к строке то так (здесь рассматриваем функцию , которая определена на отрезке от 0 до 1, который разбит на частей, см. Рисунок 8. Строка изображения):



Рисунок 8. Строка изображения



Получается, что мы берём на каждом шаге некоторое среднее значение функции в точке.


2.4S – преобразование.


Рассмотрим строчку изображения и применим к ней преобразование по таким формулам:

,

Т.к. делить на два плохо из-за проблем с точностью и скоростью, то обычно применяют другие формулы, а именно:



, [ ] - означает взятие целой части.

если нечётное, то если прибавляем к 1, иначе (если меньше) прибавляем к 1.

В силу того, что обычно соседние пиксели имеют одинаковые значения цвета(например), то разность будет близка к нулю. Такое преобразование можно применить несколько раз. Обычно такое преобразование применяется к некоторой квадратной матрице (нашему изображению) несколько раз. Далее полученные коэффициенты сжимают без потерь методами Хаффмана, арифметическим или SPIHT(Set Partitioning in Hierarchical Trees).



Рисунок 9. S - преобразование.

Метод описанный выше чаще всего используется для сжатия последовательностей изображений, например, в форматах серии MPEG и DivX.


3.Фрактальное сжатие.


Фрактальное сжатие основано на том, что мы представляем изображение в более компактной форме - с помощью коэффициентов системы итерируемых функций ( Iterated Function System(IFS)) Фактически, фрактальная компрессия - это поиск самоподобных областей в изображении и определение для них параметров аффинных преобразований. Получается, что даже для небольших изображений мы получим огромное число перебираемых вариантов. Соответственно современные алгоритмы направлены на уменьшение времени архивации изображения без ухудшения качества изображения. Декомпрессия заключается в необходимости проведения нескольких итераций аффинных преобразований, коэффициенты которых получаем при компрессии. Соответствующий математический аппарат гарантирует нам сходимость изображений, получаемых в ходе итераций, к исходному. Обычно достаточно 16 итераций.

Литература


© Группа Компьютерной Графики, 2002
Лаборатория Вычислительных Методов, Мех-мат МГУ

Стр. из



скачать файл



Смотрите также:
Лекция №11 Сжатие изображений 2
53.29kb.
План-конспект урока по теме «Линзы. Построение изображений, даваемых линзами»
55.17kb.
Топологические алгоритмы обработки цифровых изображений
46.76kb.
Вейвлет-фильтрация признаков описания формы изображений А. Л. Жизняков1, А. А. Фомин1
88.26kb.
Курс реализуется в рамках направления 552800 «Информатика и вычислительная техника», относится к циклу специальных дисциплин
317.76kb.
В. Б. Борщев и B. H. Partee. Казань, кгу, Апрель 2003 стр. Лекция
411.65kb.
Публичная лекция Е. Г. Дозорцевой Лекция: "Психология и право"
702.04kb.
Лекция. Периферийные средства мк-51 Лекция
71.5kb.
Лабораторная работа 9-10. Файловые системы. Управление дисками. Использование групповой политики
332.66kb.
Комбинированные алгоритмы поддержки принятия решений при автоматизированной идентификации зашумленных структурированных изображений
285.37kb.
Лекция «Принципы гнсс-зондирования ионосферы»
196.59kb.
Для заданных стержневых систем построить эпюры внутренних силовых факторов, предварительно изучив соответствующие разделы программы
25.82kb.