Лекция №11 Сжатие изображений Курс лекций «Алгоритмические основы машинной графики» icon

Лекция №11 Сжатие изображений Курс лекций «Алгоритмические основы машинной графики»



Смотрите также:
Курс лекций «Алгоритмические основы машинной графики» читается в качестве специального курса на...
Курс лекций «Алгоритмические основы машинной графики» читается в качестве специального курса на...
Программа дисциплины алгоритмические основы распознавания изображений...
Курс лекций Лекция Введение в земледелие. Лекция Научные основы земледелия...
Конспект Лекций Лекция 1 Введение в компьютерную геометрию и графику Основные направления...
Анализ и сжатие изображений с использованием математической 3d морфологии...
Курс лекций по дисциплине «основы менеджмента» Для самостоятельного изучения тем дисциплины на...
Структура курса лекций (34 часа) Лекция Введение (2 ч.). Лекция Проблема сущности религии (2 ч.)...
Реферат по дисциплине Основы программирования и алгоритмические языки на тему : ”Архитектурные...
Лекция 01. Преобразования в двухмерном пространстве 23...
Курс лекций Москва -2004 Вишневский В. В. Правоведение. Курс лекций. М.: Мосу,2004. 80 с...
Что такое видеосистема компьютера?...



скачать

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

Лекция № 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
Лаборатория Вычислительных Методов, Мех-мат МГУ


Стр. из






Скачать 53,45 Kb.
оставить комментарий
Дата25.04.2012
Размер53,45 Kb.
ТипЛекция, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Документы

наверх