Обработка графической информации.
 |
Для простоты изложения пусть изображение хранится в квадратной матрице X с элементами xi,j N строк на N столбцов. Для некоторых методов применяют разбивку исходного изображения на блоки. Обрабатывая матрицу, мы будем иметь временную сложность алгоритма как минимум кратной N3
. Для ее уменьшения поступают следующим образом: разбивают изображение на несколько малых размером n на n, n << N, каждое малое изображение будем обрабатывать отдельно.
Тогда, вместо N3 будем иметь N2n сложность алгоритма.
В данном разделе будем рассматривать сжатие графической информации с потерями. То есть из сжатого выходного массива невозможно при декодировании получить исходный. Но будем сжимать таким образом, чтобы потери как можно меньше воспринимались глазом при демонстрации данной графической информации.
Самый первый способ, который приходит в голову, следующий. Уменьшим количество бит для хранения одного пикселя (элемента исходной матрицы). Пусть пикселы исходного изображения имеют формат RGB Truecolor
8:8:8 (на каждую цветовую составляющую отводится по 8 бит). Перекодируем изображение в формат 5:5:5 (то есть каждая цветовая составляющая будет иметь 25 =32 градации), отбрасывая младшие четыре бита изображения. Мы также можем использовать свойство глаза наиболее хорошо различать цвет в области зеленого и кодировать изображение в формат RGB 4:5:4 и каждый пиксел будет занимать два байта.
Можно пойти еще дальше: перевести исходное изображение в другую цветовую модель и отформатировать его. Например, в YIQ 6:3:3 - отводим на яркость 6 бит, на синфазный и интегрированный каналы по 3, используя то, что человеку более важна информация об интенсивности, нежели о цвете. При «жадном»
кодировании, когда используем малое количество бит на пиксел, сразу после декодирования, перед выводом изображения можно провести так называемый anti-aliasing - сгладить резкие
цветовые переходы, возникшие из-за малого числа градаций цветовых составляющих. Дальнейшее усовершенствование заключается в индексировании цветов.
RGB Truecolor формат может поддерживать более 16 млн. цветов. Выберем n (обычно n - степень 2 )
индексных цветов cK так, чтобы минимизировали сумму:
Далее создаем выходной массив B N на N, элемент которого bi,j равен k, где k=
m - номер цвета такой, что выполняется
Рассмотрим семейство кодеров изображения, основанных на отбросе коэффициентов преобразования. Все они используют разбивку на блоки. Пусть Y - получаемое изображение, A - матрица преобразования.
После преобразования, сохраняем только часть коэффициентов, за счет чего и осуществляется сжатие. Наиболее эффективным будет метод, минимизирующий оценку:
где l1.. lg - собственные значения Kx. Отбрасывая малые собственные значения получаем сжатие. Данный метод, хотя и дает наименьшую ошибку приближения среди аналогичных кодеров, используется редко, так как требует большого объема вычислений при своей работе. Преобразование Карунена-Лоэва называют также оптимальным кодированием. Рассмотрим другие кодеры данного семейства:
Фурье,
Преобразование Фурье представляет собой разложение по спектру.
Дискретное косинусное преобразование (ДКП).
в настоящее время метод, так как он дает результат ошибку приближения чуть больше чем разложению Карунена-Лоэва. Существует алгоритм, реализующий данный метод со сложностью 2n2log2n-1.5n+4.
Симметричное преобразование Адамара.
il и jl - состояние разрядов двоичного представление чисел i и j.
Для n=2 матрица будет следующей:
При отборе коэффициентов пользуются следующими способами:
Пороговый отбор. Отбрасываются коэффициенты, которые по модулю,
ниже установленного порога.
Зональный отбор. Отбрасываются коэффициенты, принадлежащие к малокритичному спектру. Например, при ДКП или преобразовании Фурье можем отбросить часть коэффициентов, принадлежащих к высокочастотному спектру, так как чувствительность глаза выше в низкочастотной области.
 |
 |
 |
на границы соседних с ним блоков.
