Как работает алгоритм
Шаг 1. Переводим изображение из цветового пространства RGB, с компонентами, отвечающими за красную (Red), зеленую (Green) и синюю (Blue) составляющие цвета точки, в цветовое пространство YCrCb (иногда называют YUV). В нем Y — яркостная составляющая, а Cr, Cb — компоненты, отвечающие за цвет (хроматический красный и хроматический синий). За счет того, что человеческий глаз менее чувствителен к цвету, чем к яркости, появляется возможность архивировать массивы для Cr и Cb компонент с большими потерями и, соответственно, большими коэффициентами сжатия. Подобное преобразование уже давно используется в телевидении. На сигналы, отвечающие за цвет, там выделяется более узкая полоса частот. Шаг 2. Разбиваем исходное изображение на матрицы 8х8. Формируем из каждой три рабочие матрицы ДКП — по 8 бит отдельно для каждой компоненты. При больших коэффициентах сжатия этот шаг может выполняться чуть сложнее. Изображение делится по компоненте Y — как и в первом случае, а для компонент Cr и Cb матрицы набираются через строчку и через столбец. Т.е. из исходной матрицы размером 16x16 получается только одна рабочая матрица ДКП. При этом, как нетрудно заметить, мы теряем 3/4 полезной информации о цветовых составляющих изображения и получаем сразу сжатие в два раза. Мы можем поступать так благодаря работе в пространстве YCrCb. На результирующем RGB изображении, как показала практика, это сказывается несильно. Шаг 3. Применяем ДКП к каждой рабочей матрице. При этом мы получаем матрицу, в которой коэффициенты в левом верхнем углу соответствуют низкочастотной составляющей изображения, а в правом нижнем — высокочастотной. Шаг 4. Производим квантование. В принципе, это просто деление рабочей матрицы на матрицу квантования поэлементно. Для каждой компоненты (Y, U и V), в общем случае, задается своя матрица квантования q[u,v] (далее МК). На этом шаге осуществляется управление степенью сжатия, и происходят самые большие потери. Понятно, что, задавая МК с большими коэффициентами, мы получим больше нулей и, следовательно, большую степень сжатия. В стандарт JPEG включены рекомендованные МК, построенные опытным путем. Матрицы для большего или меньшего коэффициентов сжатия получают путем умножения исходной матрицы на некоторое число gamma. С квантованием связаны и специфические эффекты алгоритма. При больших значениях коэффициента gamma потери в низких частотах могут быть настолько велики, что изображение распадется на квадраты 8х8. Потери в высоких частотах могут проявиться в так называемом “эффекте Гиббса”, когда вокруг контуров с резким переходом цвета образуется своеобразный “нимб”. Шаг 5. Переводим матрицу 8x8 в 64-элементный вектор при помощи “зигзаг”-сканирования, т.е. берем элементы с индексами (0,0), (0,1), (1,0), (2,0)... Таким образом, в начале вектора мы получаем коэффициенты матрицы, соответствующие низким частотам, а в конце — высоким. Шаг 6. Свертываем вектор с помощью алгоритма группового кодирования. При этом получаем пары типа (пропустить, число), где “пропустить” является счетчиком пропускаемых нулей, а “число” — значение, которое необходимо поставить в следующую ячейку. Так, вектор 42 3 0 0 0 -2 0 0 0 0 1... будет свернут в пары (0,42) (0,3) (3,-2) (4,1).... Шаг 7. Свертываем получившиеся пары кодированием по Хаффману с фиксированной таблицей. Процесс восстановления изображения в этом алгоритме полностью симметричен. Метод позволяет сжимать некоторые изображения в 10-15 раз без серьезных потерь.
В 1977 году израильские ученые А.Лемпел и Я.Зив опубликовали работу [], в которой привели разработанный ими алгоритм сжатия данных, названный позже LZ. На основе этого алгоритма в дальнейшем было разработано множество алгоритмов, учитывающих технические возможности компьютеров. В алгоритмах LZ учитываются корреляционные связи между символами, что позволяет значительно увеличить коэффициент сжатия. Сущность алгоритма сжатия данных LZ состоит в том, что повторяющиеся последовательности символов заменяются указателями на позиции, где они в тексте уже ранее появлялись. Одной из форм такого указателя может быть пара (n,m), которая ссылается на последовательность символов длиной m символов, начинающуюся с позиции n. В большинстве реализаций алгоритма Лепеля-Зива позиция в паре кодируется как смещение (разность) между позициями кодируемой строки и строки, на которую произведена ссылка. Из-за ограниченного объема оперативной памяти компьютера обычно используется вариант алгоритма Лемпеля-Зива со скользящим окном, когда максимальное значение смещения ограничено некоторым значением. Сжатие данных происходит следующим образом. В сжатые данные выдаются либо символы сжимаемых данных, либо ссылки на уже просмотренную часть сообщения. Эти ссылки указывают, что текущие символы некоторым количеством m совпадают с теми, что уже были прочитаны, начиная с позиции n. Распаковка начинается сначала сообщения.
Наиболее распространенные методы 1. Увеличение мощности сигнала Увеличение мощности сигнала приводит к превышению полезного сигнала над помехой и позволяет надежнее отделять полезный сигнал от помехи. Этот метод широко используется в вычислительной технике.
|
