Сжатие с потерями

Для простоты изложения пусть изображение хранится в квадратной матрице X с элементами x_i,j N строк на N столбцов. Для некоторых методов применяют разбивку исходного изображения на блоки. Обрабатывая матрицу, мы будем иметь временную сложность алгоритма как минимум кратной N³. Для ее уменьшения поступают следующим образом: разбивают изображение на несколько малых размером n на n, n << N, каждое малое изображение будем обрабатывать отдельно. Тогда, вместо N³ будем иметь N²n сложность алгоритма.

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

Самый первый способ, который приходит в голову, следующий. Уменьшим количество бит для хранения одного пикселя (элемента исходной матрицы). Пусть пикселы исходного изображения имеют формат RGB Truecolor 8:8:8 (на каждую цветовую составляющую отводится по 8 бит). Перекодируем изображение в формат 5:5:5 (то есть каждая цветовая составляющая будет иметь 2⁵ =32 градации), отбрасывая младшие четыре бита изображения. Мы также можем использовать свойство глаза наиболее хорошо различать цвет в области зеленого и кодировать изображение в формат RGB 4:5:4 и каждый пиксел будет занимать два байта.

Можно пойти еще дальше: перевести исходное изображение в другую цветовую модель и отформатировать его. Например, в YIQ 6:3:3 - отводим на яркость 6 бит, на синфазный и интегрированный каналы по 3, используя то, что человеку более важна информация об интенсивности, нежели о цвете. При “жадном” кодировании, когда используем малое количество бит на пиксел, сразу после декодирования, перед выводом изображения можно провести так называемый anti-aliasing - сгладить резкие цветовые переходы, возникшие из-за малого числа градаций цветовых составляющих. Дальнейшее усовершенствование заключается в индексировании цветов. RGB Truecolor формат может поддерживать более 16 млн. цветов. Выберем n (обычно n - степень 2) индексных цветов c_K так, чтобы минимизировали сумму: .

Далее создаем выходной массив B N на N, элемент которого b_i,j равен k, где k= m - номер цвета такой, что выполняется . Выходная информация - массив B и собственно таблица индексных цветов c. Результаты данного подхода можно посмотреть в разделе “Форматирование и индексирование изображений”.

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

.

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

. Самый оптимальный метод - Карунена-Лоэва. Строки матрицы преобразования A - нормированные собственные вектора K_x, то есть являются решением уравнения вида K_xx = _ix, K_x = E{(x- Ex)(x-Ex)^T} - ковариация, E - мат. ожидание, T - знак транспонирования. Коэффициенты преобразования y=Ax имеют матрицу преобразования вида:

, где _.._- собственные значения K_x. Отбрасывая малые собственные значения получаем сжатие. Данный метод, хотя и дает наименьшую ошибку приближения среди аналогичных кодеров, используется редко, так как требует большого объема вычислений при своей работе. Преобразование Карунена-Лоэва называют также оптимальным кодированием. Рассмотрим другие кодеры данного семейства:

Фурье, , для данного преобразования существует алгоритм, с временной сложностью n²log₂n. Преобразование Фурье представляет собой разложение по спектру.

Дискретное косинусное преобразование (ДКП).

.Наиболее используемый

в настоящее время метод, так как он дает результат ошибку приближения чуть больше чем разложению Карунена-Лоэва. Существует алгоритм, реализующий данный метод со сложностью 2n²log₂n-1.5n+4.

Симметричное преобразование Адамара.

, где

i_l и j_l - состояние разрядов двоичного представление чисел i и j. Для n=2 матрица будет следующей: . Хотя метод Адамара не дает столь хороших результатов как предыдущие, зато все операции преобразование сводится к сложениям и вычитаниям.

При отборе коэффициентов пользуются следующими способами:

Пороговый отбор. Отбрасываются коэффициенты, которые по модулю, ниже установленного порога.

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

Обычно отбрасываемые коэффициенты обнуляют. Далее применяют последовательное и энтропийное сжатие. Так работает алгоритм JPEG кодирования. Все это дает снижение размера массива, при приемлемом качестве изображения, в 5-16 раз. На приведенном примере использовалось исходное изображение в разрешении 240 на 362 пикселя в RGB Truecolor и занимало 240*362*3=260640 байт. Левое сжатое изображение занимает 46000 байт и внешне не отличается от исходного. Левое нижнее изображение имеет размер 8004 байт и имеет заметные резкие цветовые переходы в области неба. Правое нижнее изображение имеет размер 5401 байт (!) и хотя изображение стало слишком мозаичным, мы вполне можем понять его содержание. При использовании разбивок на блоки иногда возникает побочный эффект: становятся заметными границы блоков. Для борьбы с ним разбивку проводят так, чтобы блоки “наезжали” на границы соседних с ним блоков.

Другой принцип лежит в основе пирамидального кодирования. Пусть x(k,l) - исходное изображение. Получим из него его низкочастотную, с частотой среза f₁, “версию” x₁(k,l) с помощью локального усреднения с одномодовым гауссоподобным двумерным импульсным откликом. x₁(k,l) можно рассматривать как предсказание для c. e₁(k,l) = x(k,l) - x₁(k,l) - ошибка предсказания, далее повторяем для частоты среза f₂: e₂(k,l) = x₁(k,l) - x₂(k,l) - ошибка предсказания меньше чем для e₁ в f₁/f₂ раз. Получаем в итоге последовательность e₁,e₂,.., e_t. На каждой итерации размерность изображения сокращается в f_i /f_i+1 раз. Данный метод уменьшает занимаемый размер в 10..20 раз при приемлемом качестве изображения. Но сложность алгоритма выше по сравнению с предыдущими методами.

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

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

Уменьшение числа областей. Обычно в изображении 70% созданных областей содержатся в 4% изображения. Соседние области объединяют, если они обладают близкими свойствами, также удаляют незначительные (по размеру), области. Алгоритмы создания и удаления областей - задача не простая и может быть оптимизирована по многим направлениям различными способами. Именно от нее зависит дальнейшая эффективность алгоритма.

Рассмотрим собственно кодирование. Оно состоит из двух этапов: 1 - кодирование контуров и 2 - текстур, лежащих в них. Контуры представляются в виде матрицы с битовыми элементами, который равен 1, если точка входит в границу области - контур и 0 - иначе. Данную матрицу можно энтропийно сжать с эффективностью ~1.2.. 1.3 бита на пиксел контура. Текстура (содержимое) каждой области приближается средним уровнем свойства ее области и двумерным полиномом (линейным, квадратным или кубическим - в зависимости от реализации и требований к качеству). При декодировании прибавим зернистость в текстуру с помощью гауссова псевдослучайного фильтра с уже известной среднеквадратичной ошибкой. Данный метод позволяет добиться сжатия изображения в 20..75 раз с приемлемым качеством изображения. Временные затраты при его реализации весьма велики. При работе данного метода мы также можем (с небольшими дополнительными вычислениями) параллельно перевести изображение в векторную форму.