.

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

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

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

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

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

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

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

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

, где

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

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

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

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

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

Другой принцип лежит в основе пирамидального кодирования. Пусть x(k,l) - исходное изображение. Получим из него его низкочастотную, с частотой среза f1, «версию» x1(k,l) с помощью локального усреднения с одномодовым гауссоподобным

двумерным импульсным откликом. x1(k,l) можно рассматривать как предсказание для c. e1(k,l) = x(k,l) - x1(k,l) - ошибка предсказания, далее повторяем для частоты среза f2: e2(k,l) = x1(k,l) - x2(k,l) - ошибка предсказания меньше чем для e1 в f1/f2 раз. Получаем в итоге последовательность e1 ,e2 , , et. На каждой итерации размерность изображения сокращается в fi /fi+1 раз. Данный метод уменьшает занимаемый размер в 10 20 раз при приемлемом качестве изображения. Но сложность алгоритма выше по сравнению с предыдущими методами.

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

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

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

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

Литература

1. Эндрюс. Применение вычислительных машин для обработки изображений.

2. Харри. Обработка изображений при помощи ЦВМ.

3. Яншин. Анализ и обработка изображений. Принципы и алгоритмы.

4. Джад, Вышецки. Цвет в науке и технике.

5. Мартинес. Обработка изображений.