Сжатие изображений с потерями

14.1. Необходимость сжатия с потерями

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

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

14.2. Оценка потерь

Напомним, что A называется алгоритмом сжатия c потерями (англ. lossy compression), если он не обеспечивает возможность точного восстановления исходного изображения. Т.е. подбирается пара A, A*, где A* приближенно восстанавливает изображение: для любого изображения I A(I) = I1, A*(I1) = I2 и при этом полученное восстановленное изображение I2 не обязательно точно совпадает с I (см. определение в первом параграфе предыдущей лекции). Возникает вопрос: как оценивать потери визуальной информации, т.е. меру отличия I от I2? Существует множество хороших мер для оценки таких потерь, однако для всех из них можно подобрать такие два изображения, что их мера отличия будет достаточно большой, но на глаз различия будут почти незаметными. И наоборот - можно подобрать изображения, сильно различающиеся на глаз, но имеющие небольшую меру отличия.

Введем сначала норму для значений атрибутов пикселей. Для полутоновых изображений, где на каждое значение атрибута пикселя отводится 8 бит:

Причем $$M^* = max \Vert \cdot \Vert$$, т.е. максимально возможное значение для такой нормы равно 255 x 255 = 65025. Для полноцветных изображений с тремя 8 -битными значениями атрибута пикселя (тремя 8 -битными каналами):

следовательно M* = 3 x 255 x 255 = 195075.

Стандартной мерой отличия является мера отношения сигнала к шуму ( PSNR - англ. Peak Signal-to-Noise Ratio), определяемая так:

где MSE(I1, I2) - другая мера - среднеквадратическая ошибка ( L2 -мера, MSE - англ. Mean Squared Error), определяемая так:

Тем не менее самой важной "мерой" оценки потерь является мнение наблюдателя. Чем меньше различий (а лучше - их отсутствие) обнаруживает наблюдатель, тем выше качество алгоритма сжатия.

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

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

Будем рассматривать изображение как функцию двух переменных, определенную в точках конечного растра (имеется в виду точечная модель растра, см. определение в разделе 1.1). I(x, y) - значение атрибута пикселя (например номер в палитре, интенсивность), зависящее от цветовой модели представления изображения (см. рис. 14.1 и рис. 14.2). Множество таких функций на точках фиксированного конечного растра образуют конечномерное евклидово пространство RX,Y размерности m x n (|X|=m,|Y|= n) со скалярным произведением

Будем отождествлять с таким пространством L2(X x Y ). В таком пространстве существует базис (см. [3]), т.е. такая система элементов $$\left\{e_k \right\}_{k=1}^{k=m \times n}$$ из RX,Y и такой набор не равных одновременно нулю коэффициентов $$\left\{C_k \right\}_{k=1}^{k=m \times n}$$, что для любой функции I из этого пространства выполнено

Если дополнительно предположить ортонормальность базиса, т.е.

то выполняется следующее соотношение:

Ck = (I, ek).

Дискретное Преобразование Фурье

Напомним определение двумерного дискретного преобразования Фурье функции I:

для всех k = 1 . . .m, l = 1 . . . n. Обратное преобразование определяется так:

Система функций $$\left\{e^{2\pi \left ( p\frac{k}{m} + q\frac{l}{n} \right )}\right\}_{k,l=0}^{m,n}$$ образует базис в пространстве функций-изображений (см. [3]).

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

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

Рассмотрим определение дискретного косинусного преобразования (ДКП) [43]. Пусть изображение имеет размеры N x N. Прямое преобразование записывается так:

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

Дискретное преобразование обладает свойствами.

Коэффициенты t(u, v) - это амплитуды пространственных частот изображения. В случае изображений с плавными переходами большая часть информации содержится в низкочастотном спектре (см. лекцию 7).

Отметим, что применение дискретного косинус-преобразования эквивалентно применению дискретного преобразования Фурье примерно двойной длины к действительным (некомплексным) и четно симметричным данным (эквивалентность вытекает из того, что преобразование Фурье четной действительной функции четно и действительно).

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

Алгоритм сжатия, используемый в формате хранения изображений JPEGJoint Photographic Experts Group организация, занимающаяся разработкой и стандартизацией алгоритмов и форматов сжатия изображений. см. лекцию 1).

Y00Cb00Cr00 Y01Cb01Cr01 Y02Cb02Cr02 Y03Cb03Cr03
Y10Cb10Cr10 Y11Cb11Cr11 Y12Cb12Cr12 Y13Cb13Cr13
Y20Cb20Cr20 Y21Cb21Cr21 Y22Cb22Cr22 Y23Cb23Cr23
Y30Cb30Cr30 Y31Cb31Cr31 Y32Cb32Cr32 Y33Cb33Cr33

Y00Cb00Cr00 Y01Cb00Cr00 Y02Cb02Cr02 Y03Cb02Cr02
Y10Cb10Cr10 Y11Cb10Cr10 Y12Cb12Cr12 Y13Cb12Cr12
Y20Cb20Cr20 Y21Cb20Cr20 Y22Cb22Cr22 Y23Cb22Cr22
Y30Cb30Cr30 Y31Cb30Cr30 Y32Cb32Cr32 Y33Cb32Cr32

Y00Cb00Cr00 Y01Cb00Cr00 Y02Cb02Cr02 Y03Cb02Cr02
Y10Cb00Cr00 Y11Cb00Cr00 Y12Cb02Cr02 Y13Cb02Cr02
Y20Cb20Cr20 Y21Cb20Cr20 Y22Cb22Cr22 Y23Cb22Cr22
Y30Cb20Cr20 Y31Cb20Cr20 Y32Cb22Cr22 Y33Cb22Cr22

122 0 125 0 0 44 0 0 0 0 -1.

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

Данный алгоритм и формат являются самыми распространенными для передачи и хранения полноцветных изображений. Столь широкое распространение объясняется несколькими причинами: относительно невысокой вычислительной сложностью (что было очень актуально до 1996 года), достаточной степенью стандартизованности формата и алгоритма, а также отсутствием необходимости платить какие-либо лицензионные отчисления (т.к. отсутствуют патентованные алгоритмы). К недостаткам алгоритма относят возникновение упоминавшихся выше артефактов, которые слишком заметны для человеческого глаза.

Описанная выше схема сжатия является типичной для алгоритмов сжатия изображений с потерями (за исключением фрактального). Отличие в основном состоит в типе преобразования на шаге 3. Далее мы рассмотрим другой вид преобразования.

14.5. Вейвлет-преобразование

Идея вейвлет-преобразования состоит в разложении сигнала (функции-изображения) по системе функций, имеющих локальный всплеск и быстро убывающих на бесконечности [20]. В этом и последующих параграфах предполагается знакомство читателя с базовыми понятиями функционального анализа (см., например, [3]). Обычно такие функции вейвлет-преобразованияот англ. wavelet transform выводятся из так называемого материнского вейвлета. Материнский вейвлет - это функция $$\psi :$$

т.е. $$\psi \in L_2(\mathbb{R}) \cap L_1(\mathbb{R})$$ ; также предполагается, что

Материнский вейвлет преобразовывается следующим образом:

где $$(a, b) \in \mathbb{R} \backslash \{0\} \times \mathbb{R}$$. Примеры материнских вейвлетов см. на рис. 14.5. В общем случае вейвлет-преобразование записывается так:

При практическом применении вейвлет-преобразования анализ такого мощного (а именно континуум) множества коэффициентов невозможен. Поэтому (a, b) выбираются из счетного подмножества плоскости $$\mathbb{R} \backslash \{0\} \times \mathbb{R}$$. Обычно материнский вейвлет и множество значений (a, b) выбирают так, чтобы система $$\{\psi_{ab}\}$$ образовывала ортонормированный базис в пространстве $$L_2(\mathbb{R})$$. Тогда любую функцию f(x) из этого пространства можно разложить по этому базису $$f(x) = \sum_{j,k} c_{jk} \psi_{jk}(x)$$.

Поясним как применять вейвлет-преобразование к дискретному сигналу (например, изображению). Для простоты будем рассматривать одномерный случай - последовательность конечной длины $${\left\{s_j \right\}}_{j=0}^{N-1}$$. Тогда, при условии что материнский вейвлет $$\psi \in L_2(\mathbb{R})$$, преобразование можно записать так:

Рассмотрим простейшей вейвлет - вейвлет Хаара (англ. Haar wavelet). Рассмотрим пространство $$L_2(\mathbb{R})$$. В этом пространстве ортонормированна следующая система:

Данная система называется системой Хаара. Для такого вейвлета материнским является $$\chi_{00}$$ (см. рис. 14.6). В данном случае (a, b) выбраны из $$\mathbb{R} \setminus \{0\} \times \mathbb{R}$$ по такому закону:

Действие вейвлета Хаара на последовательность, состоящую из 2N элементов, можно рассматривать так: элементы группируются по два, вычисляется сумма и разность каждой пары, разности сохраняются, а из сумм формируется последовательность длины 2N-1 ; далее преобразование выполняется до тех пор, пока не останется одна сумма и соответственно 2N - 1 разность. Такое преобразование задается так называемой матрицей Хаара:

Последовательность (a0, . . . , a2N+1) представим так:

((a0, a1), . . . , (a2N, a2N+1)).

Теперь умножим справа векторы (ai, ai+1) на матрицу H2. Получим последовательность сумм и разностей ((s0, d0), . . . , (sN, dN)). Если последовательность имеет длину, кратную 4, то можно применить следующую матрицу Хаара:

Очевидно, что данные преобразования легко обратимы. С таким вейвлет-преобразованием тесно связано так называемое S-преобразование. Если мы не хотим, чтобы при преобразовании Хаара границы значений последовательности удваивались (из-за суммирования), надо брать полусумму. Однако при целом делении на 2 мы теряем точность. Решение данной проблемы выглядит так: пусть a и b - пара значений из исходной последовательности. Тогда

при этом восстановление выглядит так:

при этом, если d - нечетное, то при d > 0 к a добавляется 1, а если d < 0, то к b добавляется 1.

// s - сумма, d - разность
// Round(x) - взятие целой части
// IsOdd(x) - является ли нечетным
a = s + Round( d / 2 ); b = s - Round( d / 2 )
if( IsOdd( d ) )
{
    if ( d > 0 )
        a++;
    else
        b++;
}

В алгоритме JPEG2000 [10] используются так называемые вейвлеты Добеши (англ. Daubechies wavelet). В матричном виде для действия на вектор A длины 8 данное преобразование задается так:

где

Как видно, матрица имеет размеры 8 x 10 из-за необходимости участия в суммировании четырех компонент. Т.е. на самом деле, такая матрица умножается на следующий вектор:

A = (a1a2a3a4a5a6a7a8a9a10)T .

Обычно полагают либо a9 = a1, a10 = a2, либо a9 = a8, a10 = a7. Использование вейвлет-преобразований при сжатии изображений аналогично использованию дискретного косинус-преобразования в алгоритме JPEG, т.е. само преобразование - лишь ступень конвейера сжатия.

Вейвлет-преобразования имеют очень хорошую частотно-пространственную локализацию и по этому показателю превосходят традиционные косинус-преобразования и другие преобразования Фурье. Таким образом, становится возможно применять более сильное квантование, улучшая свойства последовательности для последующего сжатия без потерь. Алгоритмы сжатия изображений, основанные на этом преобразовании, при той же степени сжатия показывают лучшие результаты по сохранению качества изображения. К тому же вычислительная сложность очень низка и составляет O(N) (здесь N - длина последовательности, к которой применяется преобразование). Однако распространенность форматов, использующих сжатие на основе вейвлет-преобразования, невелика из-за наличия патентов, а также из-за большой распространенности обычного JPEG, дающего вполне приемлемые результаты.

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

Фрактальное сжатие основывается на поиске и кодировании самоподобных областей в изображении. При этом используются системы итерируемых функций (англ. IFS - Iterated Function System) [31], [12].

Определение 14.6.1. Отображение $$f \colon R \to R$$ в полном метрическом пространстве $$(R, \rho)$$ называется сжимающим, если $$\exists \alpha < 1 : \forall x, y \in R \rho(f(x), f(y)) < \alpha \rho(x, y)$$.

Cистеме из $$n$$ сжимающих отображений $$F = {f_1, . . . , f_n}$$, действующих в полном метрическом пространстве $$(R, \rho)$$, ставится в соответствие оператор системы итерируемых функций

где $$X \subseteq R, f(X) = \{f(x)|x \in X\}$$. Такое отображение является сжимающим с коэффициентом

По теореме о сжимающих отображениях [3] существует неподвижное множество $$S\colon F^*(S) = S$$.

Рассмотрим пример действия системы итерируемых функций. Пусть

действуют в пространстве R = [0; 1]2 с евклидовой метрикой. Данные отображения являются сжимающими $$(\alpha_i = \frac{1}{2})$$, и их неподвижные точки есть вершины равностороннего треугольника (их координаты $$(0, 0), (1, 0), (\frac{1}{2},\frac{\sqrt{3}}{2})$$ соответственно). Сначала будем последовательно применять оператор F* данных преобразований к множеству, ограниченному равносторонним треугольником (например, с координатами вершин, указанными выше). Неподвижное множество S, получаемое при действии оператора данной системы итерируемых функций, - это так называемый треугольник Серпинского (см. рис. 14.7). Процесс построения треугольника Серпинского см. на рис. 14.8. Можно начать применять оператор данных преобразований не к треугольнику, а к квадрату. Неподвижное множество будет таким же (см. рис. 14.9). Неважно, с какой области начинать (требуется только компактность), - получим треугольник Серпинского.

Другим примером неподвижного множества S для оператора F* для некоторой системы F из четырех аффинных преобразований является папоротник Барнсли (см. рис. 14.10).

Изображение папоротника может занимать десятки мегабайт (в хорошем разрешении), а его описание с помощью параметров аффинных преобразования - несколько сотен байт! Соответственно, идея сжатия состоит в поиске таких систем преобразований, которые бы в процессе итерирования приближали желаемое изображение. Задача ставится так:

Сложность такой задачи в общем случае очень высока. Однако, если рассматривать изображение как функцию (см. введение раздела 14.3) и ограничивать вид преобразований следующим образом:

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

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