Сжатие – представление информации в более эффективном виде, влекущее за собой уменьшение объема данных (как правило). В основном алгоритмы сжатия используют свойства графических данных:
- избыточность – группы одинаковых символов;
- предсказуемость – часто повторяющиеся одинаковые комбинации символов;
- необязательность – данные, мало влияющие на человеческое восприятие.
Оценки методов сжатия:
- степень сжатия – отношение объема сжатого файла к объему исходного файла;
- точность восстановления – среднеквадратичное отклонение значений пикселей сжатого изображения от оригинала;
- скорость компрессии и декомпрессии – суммарное время сжатия и восстановления;
- симметричность – отношение времени сжатия ко времени восстановления.
Все существующие алгоритмы можно разделить на два больших класса:
Алгоритмы сжатия без потерь
Сжатие без потерь – кодирование информации меньшим числом битов без ее искажения. Когда мы говорим о сжатии изображения без потерь, то имеем в виду, что существует алгоритм, обратный алгоритму сжатия, позволяющий точно восстановить исходное изображение.
Алгоритмы на основе статистических характеристик ставят наиболее частым элементам последовательностей наиболее короткий сжатый код
Алгоритмы серии RLE (англ. run-length encoding или кодирование повторов) основаны на очень простой идее: повторяющиеся группы элементов заменяются на числа повторов. Пример: последовательности из 21 бит (11111 000000 11111111 00) соответствует набор чисел 5 6 8 2. Этот набор при 3-х битном кодировании каждого числа (от 0 до 7) может быть представлен последовательностью из 18 бит 5 6 7 0 1 2 (101 110 111 000 001 010).
Алгоритм Шенона-Фано:
- Символы первичного алфавита m1 выписывают по убыванию вероятностей.
- Символы полученного алфавита делят на две части, суммарные вероятности символов которых максимально близки друг другу.
- В префиксном коде для первой части алфавита присваивается двоичная цифра «0», второй части — «1».
- Полученные части рекурсивно делятся и их частям назначаются соответствующие двоичные цифры в префиксном коде.
Алгоритм Хаффмана:
- Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который равен частоте появления символа.
- Выбираются два свободных узла дерева с наименьшими весами.
- Создается их родитель с весом, равным их суммарному весу.
- Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.
- Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.
- Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.
Алгоритм арифметического кодирования:
Рассмотрим в качестве примера строку abacaba:
Поставим каждому символу текста в соответствие отрезок на координатной прямой, длина которого равна частоте его появления.
- Считываем символ из входного потока и рассмотрим отрезок, соответствующий этому символу. Разделим этот отрезок на части, пропорциональные частотам встречаемости символов.
- Повторим пункт (1) до конца входного потока.
- Выберем любое число в пределах получившегося отрезка, которое и будет результатом арифметического кодирования
При декодировании уменьшаем пропорционально рабочий отрезок (аналогично кодированию), не изменяя значение кода. Символ определяется при попадании кода в соответствующие границы.
В словарных алгоритмах используется словарь из группы символьных сочетаний, который формируется на основе исходной последовательности. При сжатии происходит поиск наиболее длинной цепочки символов, уже записанной в словарь. Каждый раз, когда встречается цепочка, ещё не записанная в словарь, она добавляется туда.
Здесь под символом подразумевается некий повторяющийся элемент исходной строки — это может быть как печатный знак (character), так и любая битовая последовательность. Под кодом подразумевается не ASCII или UTF-8 код символа, а кодирующая последовательность битов.
Рассмотрим пример сжатия этим алгоритмом. Будем сжимать строку кукушкакукушонкукупилакапюшон. Исходный словарь заполнен следующим образом:
Процесс сжатия отражен в следующей таблице:
Процесс декодирования сводится к прямой расшифровке кодов. При этом используется только исходный словарь кодирования. В процессе декодирования он расширяется аналогичным образом.
Алгоритмы сжатия с потерями
Сжатие с потерями – кодирование информации с потерей той ее части, которая несущественна для представления данных. Методы сжатия с потерями качества изображений используют особенности человеческого зрения.
Идея, лежащая в основе всех алгоритмов сжатия с потерями, довольно проста: сначала удалить несущественную информацию, а затем к оставшимся данным применить наиболее подходящий алгоритм сжатия без потерь.
Метод JPEG включает три последовательных этапа:
- Предварительная обработка изображения.
- Спектральное преобразование данных.
- Квантование спектра и сжатие данных.
На 1-м этапе выполняются:
- переход к цветоразностной модели;
- разделение изображения на блоки;
- «прореживание» блоков цветовых составляющих.
Переход к цветоразностной модели означает преобразование значений базовых цветовых составляющих R G B к тройке составляющих Y U V, где Y — яркость, U — хроматические красный, V — хроматические синий.
Формируются блоки размером 8×8 пикселов, которые обрабатываются при сжатии независимо друг от друга.
Четверки соседних блоков объединяются в макроблоки 16х16. Для цветовых составляющих U и V выполняется «прореживание», когда четверки соседних пикселей усредняются. В результате 4 блока составляющих U и V преобразуются в 1. При этом яркостная составляющая Y, как наиболее важная, остается без изменений, а каждому блоку из 4 пикселей (2х2) яркостного канала Y ставятся в соответствие усреднённые значения U и V.
На втором этапе реализуется спектральное преобразование данных для всех блоков изображения.
Формально при этом коэффициенты Pxy исходной матрицы P преобразуется в коэффициенты dij матрицы D согласно приведенной на рисунке формуле.
Смысл преобразования заключается в том, что коэффициенты dij отражают «амплитуду колебаний» яркости пикселей. Например, если все пиксели блока имеют одинаковую яркость, то максимальными будет коэффициент d11 , а остальные dij = 0.
Чем больше деталей в изображении, тем большими окажутся значения “удаленных” коэффициентов. При этом, огрубляя коэффициенты матрицы, находящиеся ближе к ее правому нижнему углу, мы будем воздействовать именно на мелкие детали изображения. Визуально это проявится в «размывании» внутри блоков.
Порядок следования коэффициентов dij в соответствии с увеличением частоты («змейкой» от левого верхнего к нижнему правому углу) показан на рисунке.
На третьем этапе выполняется собственно огрубление коэффициентов с потерями информации и сжатие данных блоков.
Первоначально все коэффициенты матрицы D делятся с отбрасыванием дробной части на некоторые установленные делители. В примере такой делитель принят равным 8. В реальном алгоритме JPEG делители увеличиваются с возрастанием частот (на рисунке приведен фрагмент реальной матрицы делителей, в котором отображены первые 16 значений из 63).
Восстановление исходного вида матрицы выполняется обратным умножением на те же коэффициенты. Однако, поскольку при делении дробные части результатов отбрасывались, происходит необратимая потеря информации.
В результате процедуры огрубления набор коэффициентов может содержать много нулей. Кроме того маленькие цифры встречаются чаще, а набор используемых значений многократно уменьшается. Хотя каждый коэффициент по-прежнему кодируется одним байтом (то-есть, никакого сжатия еще не произошло), значительно улучшились условия для сжатия на следующем шаге преобразования.
Нетрудно видеть, что увеличивая значения делителей, мы дополнительно улучшим предпосылки сжатия (возрастет количество нулей и сократится объем алфавита). При этом за рост степени сжатия придется заплатить ухудшением качества изображения.
Чем больше степень сжатия, тем большими задаются делители. В практическом алгоритме они увеличиваются в направлении правого нижнего угла матрицы D. В результате этой операции строка из 64 коэффициентов матрицы содержит длинные последовательности «0» и удобна для окончательного сжатия. Такое сжатие выполняется с использованием метода RLE для цепочек нулей и кодирования по Хаффмену остальных коэффициентов. В результате, как правило, объем исходного графического файла сокращается в 10-20 раз. Возможно задавать и большую степень сжатия, учитывая требования к качеству восстановленного изображения.
Более детально особенности обработки уже знакомого нам блока изображения отражены на рисунке.
Полезные ссылки:
- Стандарт сжатия JPEG-2000 и фрактальное сжатие изображений
- Обзор методов супер-разрешения изображений для начинающих
- Как работает вариационный автоэнкодер (VAE)
Автор: Николай Свирневский