магистрант
2 года Жусипбекова Ж., к.т.н.,
доцент Балабеков Б.Ч.
Южно-Казахстанский Государственный Университет имени М. Ауезова, г. Шымкент, Казахстан
Анализ методов сжатия полутоновых
изображений
В
последние годы исследования в компьютерной графике в значительной мере
сосредоточены вокруг использования вейвлетов /1/.
Среди графических приложений компьютерной графики, где были применены вейвлеты, можно выделить следующие: сжатие и редактирование
изображения, автоматический контроль над уровнем детализации при редактировании
и рисовании кривых и поверхностей, восстановление поверхности через ее
контурные линии, быстрые методы решения проблем моделирования глобального
освещения, анимация. В данной работе рассмотрены методы сжатия изображений,
основанных на использовании вейвлет преобразований.
Любое цифровое изображение
представляет собой матрицу чисел, элементы которой часто называют пикселами. Бывают изображения с палитрой и без нее. Палитра
является упорядоченным набором чисел, соответствующих цветам радуги. Для
изображения с палитрой в каждом пикселе сохраняется номер используемого цвета
из палитры при закраске этого пиксела. Палитры бывают
из 16 или 256 цветов. Для изображения без палитры используются системы
цветопередачи или градации серого. Одной из распространенных систем цветопредставления является система RGB, в которой
любой цвет получают как смесь трех основных цветов: красного, зеленого и синего. В этом случае пиксел
содержит информацию о трех компонентах цвета. Для изображения в градациях
серого цвета значение каждого пиксела соответствует
его яркости от черного цвета до белого с несколькими уровнями, обычно применяют
2, 16 и 256 уровней. При разработке алгоритмов и методов сжатия изображения
следуют принципу сжатия изображений: для любого пиксела
изображения его ближайшие соседи – пикселы будут
иметь тот же или близкий цвет. Это означает, что значения соседних пикселов сильно зависят друг от друга, присутствует корреляция
между ними, которую еще называют пространственной избыточностью. Один простейших
способов применения данной корреляции для сжатия изображения заключается в
следующем. Для простоты рассмотрим одну строчку из матрицы изображения в
градациях серого цвета длиной в восемь пикселов,
которые представим как значения некоторой функции:
f = {176 186
196 204 201
198 204 214} (1)
В этом ряду
только два пиксела равны по значению. Среднее
арифметическое значение этих чисел равно 197.37. Теперь отнимая от каждого пиксела значение предыдущего пиксела,
получим следующий ряд чисел:
g = {176 10 10 8
-3 -3 6
10 } (2)
Ряды (1) и (2) графически показаны на рисунке 1. Из последовательности (2) видно, что разности соседних пикселов меньше чем их абсолютные значения, среднее арифметическое значение ряда (2) равно 26.75, разности повторяются, среди них только пять разных значений. Следующее существенное замечание касается отсутствия корреляции между числами ряда (2), что прослеживается из вторых разностей:
h = {176
-166 0 -2
-11 0 9
4} (3)
Принцип
сжатия изображений приводит также к следующим методам сжатия изображений. Можно
из целого изображения выбрать его подмножество по определенному правилу,
например, не учитывать каждую i-ю строку и i-й столбец
изображения, а остальные записать в сжатый файл. Если i=2, то исходное изображение сожмется в четыре раза. При
реконструкции каждая строка и столбец берутся дважды для восстановления исходного
размера изображения.
Следующие три способа сжатия
изображения связаны с преобразованием изображения: дискретное косинус
преобразование (DCT), вейвлет преобразование (DWT), поворот изображения. Последнее преобразование выполняют
таким образом. Так как соседние пикселы коррелированы то, сгруппировав их попарно получим множество
пар, которые можно рассматривать как точки плоскости. Ясно, что если эти точки
откладывать на графике, то получится «облако» точек сгущенных около прямой y=x. Теперь
используя операцию вращения на 45о по часовой стрелке, совместим эту
прямую с осью “х”, очевидно, что большинство точек преобразованного “облака” будут
иметь координату “у” близкую к нулю, а координата “x” при этом изменится незначительно. Далее выполняется операция
квантования пикселов, что приведет к появлению серии
нулей, наличие которых улучшает сжатие. Для обратного преобразования выполняют
вращение на 45о против часовой стрелки. Эти операции делаются с
помощью соответствующих матриц:
(4)
Для вейвлет
преобразования изображения рассматривается преобразование Хаара, которое можно
записать в матричном виде
|
|
0.35 |
0.35 |
0.5 |
0 |
0.7 |
0 |
0 |
0 |
|
|
0.35 |
0.35 |
0.5 |
0 |
-0.7 |
0 |
0 |
0 |
|
|
0.35 |
0.35 |
-0.5 |
0 |
0 |
0.7 |
0 |
0 |
|
W = |
0.35 |
0.35 |
-0.5 |
0 |
0 |
-0.7 |
0 |
0 |
|
|
0.35 |
-0.35 |
0 |
0.5 |
0 |
0 |
0.7 |
0 |
|
|
0.35 |
-0.35 |
0 |
0.5 |
0 |
0 |
-0.7 |
0 |
|
|
0.35 |
-0.35 |
0 |
-0.5 |
0 |
0 |
0 |
0.7 |
|
|
0.35 |
-0.35 |
0 |
-0.5 |
0 |
0 |
0 |
-0.7 |
На рисунке
2 приведены результаты работы компьютерной программы, которая сжимает исходное
изображение, применяя рассмотренные выше методы. Оригинал изображения
представлен на рисунке 2а. При этом были использованы следующие значения коэффициента
сжатия: 1) для метода нахождения разности соседних пикселов
- 3 (рисунок 2d), 2) для
метода выбора подмножества изображения - 16 (рисунок 2e), 3) для дискретного косинус преобразования - 30
(рисунок 2c), 4) для вейвлет преобразования коэффициент
сжатия равен 31 (рисунок 2b), 5) для
поворота изображения - 1.7
(рисунок 2f). Из визуального сопоставления данных рисунков можно сделать
следующие выводы. Для приложений, в которых необходим незначительный
коэффициент сжатия, подходят методы выбора подмножества и поворота изображения.
Там, где требуются большие коэффициент сжатия лучше подходят вейвлет преобразование и дискретное косинус преобразование.
Литература
1. Малла С. Вэйвлеты в обработке сигналов. Пер. с англ. – М.: Мир, 2005. – 671 с., ил.