Сжатие информации с потерями

Технологии обработки информации. Лекция 6. Сжатие информации с потерями к.т.н., доцент Буряченко В.В. Красноярск, 2019 Содержание Сжатие данных с потерями. Методы сжатия изображений с потерями. Принципы сжатия. Формат сжатия JPEG. Сжатие посредством квантования и дискретизации. Дискретно-косинусное преобразование. Вейвлет-сжатие. Вейвлеты Хаара. Фрактальное сжатие. Методы оценки качества алгоритмов сжатия изображений.           2 Типы сжатия с потерями Существуют две основных схемы сжатия с потерями:  В трансформирующих методах кадры изображений или звука обычно трансформируются в новое базисное пространство и производится квантование. Трансформация может осуществляться либо для всего фрейма целиком, либо поблочно.  В предсказывающих методах предыдущие и/или последующие отсчеты данных используются для того, чтобы предсказать текущий отсчет изображения или звука. Ошибка между предсказанными данными и реальными вместе с добавочной информацией, необходимой для производства предсказания, затем квантуется и кодируется. В некоторых системах эти две техники комбинируются путём использования трансформирующих кодеков для сжатия ошибочных сигналов, сгенерированных на стадии предсказания. 3 Сжатие с потерями против сжатия без потерь Преимущество методов сжатия с потерями над методами сжатия без потерь состоит в том, что первые делают возможной большую степень сжатия, продолжая удовлетворять поставленным требованиям, а именно — искажения должны быть в допустимых пределах чувствительности человеческих органов физических чувств.  Методы сжатия с потерями часто используются для сжатия аналоговых данных — чаще всего звука или изображений.  В таких случаях распакованный файл может очень сильно отличаться от оригинала на уровне сравнения «бит в бит», но практически неотличим для человека «на слух» и «на глаз» в большинстве применений. 4 Методы сжатия изображений с потерями Снижение глубины цвета Метод главных компонент Фрактальное сжатие Сжатие на основе предсказания  JPEG-LS  ДИКМ (Дифференциальная импульсно-кодовая модуляция)  Иерархическая сеточная интерполяция  CALIC JPEG      Вэйвлетная компрессия (wavelet)  JPEG 2000  DjVu Дифференциальное сжатие   5 https://ru.wikipedia.org/wiki/Сжатие_данных_с_потерями Принципы сжатия данных с потерями Идея, лежащая в основе всех алгоритмов сжатия с потерями, довольно проста:  на первом этапе удалить несущественную информацию, а на втором этапе к оставшимся данным применить наиболее подходящий алгоритм сжатия без потерь.  Основные сложности заключаются в выделении этой несущественной информации.  Подходы здесь существенно различаются в зависимости от типа сжимаемых данных. Для звука чаще всего удаляют частоты, которые человек просто не способен воспринять, уменьшают частоту дискретизации, а также некоторые алгоритмы удаляют тихие звуки, следующие сразу за громкими, для видеоданных кодируют только движущиеся объекты, а незначительные изменения на неподвижных объектах просто отбрасывают. 6 Сжатие с использованием стандарта JPEG При сжатии изображение преобразуется из цветового пространства RGB в YCbCr. После преобразования RGB->YCbCr для каналов изображения Cb и Cr, отвечающих за цвет, может выполняться «прореживание» (subsampling), которое заключается в том, что каждому блоку из 4 пикселей (2х2) яркостного канала Y ставятся в соответствие усреднённые значения Cb и Cr (схема прореживания «4:2:0»). 1. 2. 7 Квантование при сжатии JPEG Далее яркостный компонент Y и отвечающие за цвет компоненты Cb и Cr разбиваются на блоки 8х8 пикселей. Каждый такой блок подвергается дискретному косинусному преобразованию (ДКП). Полученные коэффициенты ДКП квантуются (для Y, Cb и Cr в общем случае используются разные матрицы квантования) и пакуются с использованием кодирования серий и кодов Хаффмана. 3. 4. 8 Фотография в формате JPEG с уменьшением степени сжатия слева направо Дискретно-косинусное преобразование ДКП преобразует матрицу пикселей размера N x N в матрицу частотных коэффициентов соответствующего размера.  В получаемой матрице низкочастотные компоненты расположены ближе к левому верхнему углу, а более высокочастотные смещаются вправо вниз.  В связи с тем, что основная часть графических образов на экране состоит из низкочастотной информации, используя полученную матрицу можно дифференцированно отбрасывать наименее важную информацию с минимальными визуальными потерями.  Таким образом ДКП позволяет выбрать информацию, которую можно безболезненно отбросить, не внося серьезных искажений в картинку. 9 Квантование   Матрицы, используемые для квантования коэффициентов ДКП, хранятся в заголовочной части JPEG-файла. Обычно они строятся так, что высокочастотные коэффициенты подвергаются более сильному квантованию, чем низкочастотные. Это приводит к огрублению мелких деталей на изображении. Чем выше степень сжатия, тем более сильному квантованию подвергаются все коэффициенты. При сохранении изображения в JPEG-файле указывается параметр качества, задаваемый в некоторых условных единицах. Большее число обычно соответствует лучшему качеству (и большему размеру сжатого файла). 10 3 5 7 9 11 13 15 17 5 7 9 11 13 15 17 19 7 9 11 13 15 17 19 21 9 11 13 15 17 19 21 23 11 13 15 17 19 21 23 25 13 15 17 19 21 23 25 27 15 17 19 21 23 25 27 29 17 19 21 23 25 27 29 31 Пример матрицы округления с фактором качества равным 2 Сжатие  Последний этап работы алгоритма кодирования JPEG — это сжатие. После обработки матрицы ДКП с помощью МО, в результирующей матрице появляется большое количество нулей, особенно в высокочастотной области (правый нижний угол).  Первым шагом значение в левом верхнем углу результирующей матрицы заменяется на относительное. Так как соседние блоки изображения похожи друг на друга, то кодирование очередного элемента (0,0) через разницу с предыдущим будет более эффективным. Вторым шагом является непосредственно применение алгоритма кодирования повторов (LZW), для обработки большого количества подряд идущих нулей. Экспериментальные тестирования показали, что наилучших результатов можно добиться, если обходить матрицу зигзагом, как показано на рисунке ниже. 11 Порядок обхода матрицы зигзагом Декодирование  Так как ДКП является преобразованием Фурье, к нему существует обратное дискретное косинусное преобразование (ОДКП). Алгоритм декодирования повторяет алгоритм кодирования в обратном порядке. 12 http://rain.ifmo.ru/cat/view.php/theory/data-compression/jpeg-2006 Вейвлет сжатие   Вейвлеты – математические функции, предназначенные для анализа частотных компонент данных. В задачах сжатия информации вейвлеты используются сравнительно недавно, тем не менее исследователям удалось достичь впечатляющих результатов. В отличие от рассмотренных выше преобразований, вейвлеты не требуют предварительного разбиения исходного изображения на блоки, а могут применяться к изображению в целом.  Стандарт кодирования JPEG200 использует вейвлет-преобразование вместо ДКП.  Принцип работы вейвлет-кодирования будет рассмотрен на примере вейвлетов Хаара. 13 Преобразование Хаара для одномерного сигнала При преобразовании Хаара каждой паре элементов ставится в соответствие два числа: полусумма элементов и их полуразность.  Важно отметить, что это преобразование обратимо: т.е. из пары чисел можно легко восстановить исходную пару.  В результате преобразования сигнал распадается на две составляющее: приближенное значение исходного (с уменьшенным в два раза разрешением) и уточняющую информацию. 14 Двумерное преобразование Хаара  Если исходные данные представлены в виде матрицы, то сначала выполняется преобразование для каждой строки, а затем для полученных матриц выполняется преобразование для каждого столбца. 15 Вейвлет сжатие   Сжатие достигается путём удаления некоторых коэффициентов из уточняющих матриц. На рисунке показан процесс восстановления и само восстановленное изображение после удаления из уточняющих матриц малых по модулю коэффициентов: 16 Вейвлет сжатие   Представление изображения с помощью вейвлетов позволяет добиваться эффективного сжатия, сохраняя при этом визуальное качество изображения. Несмотря на простоту, преобразование Хаара сравнительно редко используется на практике, т.к. существуют другие вейвлеты, обладающие рядом преимуществ (например, вейвлеты Добеши или биортогональные вейвлеты). 17 https://habr.com/ru/post/251417/ Фрактальное сжатие изображений    Фрактальное сжатие изображений — алгоритм сжатия изображений c потерями, основанный на применении систем итерируемых функций (как правило являющимися аффинными преобразованиями) к изображениям. Данный алгоритм известен тем, что в некоторых случаях позволяет получить очень высокие коэффициенты сжатия при приемлемом визуальном качестве для реальных фотографий природных объектов. Основа метода фрактального кодирования — это обнаружение самоподобных участков в изображении. 18 Треугольник Серпинского — изображение, задаваемое тремя аффинными преобразованиями Оценка качества алгоритмов сжатия  Используется доступное изображение, обладающее желаемыми характеристиками, для которого проверяется визуальное и объективное качество различных алгоритмов сжатия. https://ru.wikipedia.org/wiki/Лена_(изображение) 19 Стандартное тестовое изображение «4.1.05.bmp». Размер исходного файла изображения 196662 байт, размеры 256× 256 пикселей, глубина цвета 24 бита, размер цифрового сигнала изображения 256× 256× 3 = 196608 байт Оценка качества алгоритмов сжатия  Коэффициент сжатия: где Dout – объём сжатых (выходных) данных (бит); Din – объём исходных (входных) данных (бит);  среднеквадратичная ошибка (MSE – mean square error): для двух монохромных изображений I и K размера m×n, одно из которых считается зашумленным приближением другого.  пиковое отношение сигнал/шум (PSNR – peak signal to noise ratio): где MAXI — это максимальное значение, принимаемое пикселем изображения. 20 Оценка качества алгоритмов сжатия  Можно оценивать качество как одного алгоритма сжатия с разными параметрами, так и сравнивать характеристики различных алгоритмов 21 Изображения, полученные различными способами сжатия (таблица 1): a) – сжатие на основе анализа дифференциальной структуры (∆ = 39); b) – сжатие на основе анализа дифференциальной структуры с предварительной свёрткой; c) – JPEG-сжатие (качество 0); d) – PNG-сжатие (разрядность 8, число цветов 32 таблица 4); e) – GIF-сжатие http://jre.cplire.ru/jre/nov12/1/text.pdf Выводы   Сжатие с потерями позволяет достичь очень высокой степени сжатия (10-500 раз в зависимости от типа данных). Представляет собой кодирование информации с потерей несущественной её части.    Основным подходом является перевод данных в частотную область и отбрасывание высоких частот. Применимо не для любых данных. Иногда оказывает негативное влияние на визуальное качество информации и понижает эффективность других алгоритмов. 22