Методы сжатия изображений

Методы сжатия изображений Напоминание Матрица интенсивности(яркости) Обычно 0 – черный, 255 - белый Основы Сжатие данных - уменьшение объема данных, используемого для представления определенного количества информации. Относительная избыточность: R = 1-(1/C), где С= b/b’ С- коэффициент сжатия b- число единиц информации до сжатия b’ – число единиц информации после сжатия Модель сжатия изображений Степень статистической избыточности Энтропия, которая определяет минимальное число бит, необходимое для представления заданной последовательности чисел с последующей возможностью полного восстановления информации Вычисление энтропии изображения 21 21 21 95 169 243 243 243 21 21 21 95 169 243 243 243 21 21 21 95 169 243 243 243 21 21 21 95 169 243 243 243 Уровень яркости Число Вероятность 21 12 3/8 95 4 1/8 169 4 1/8 243 12 3/8 (21,21) (21,95) (95, 169) (169, 243) (243, 243) (243, 21) 8 4 4 4 8 4 1/4 1/8 1/8 1/8 1/4 1/8 Можно предположить, что изображение было получено воображаемым «8-битовым полутоновым источником», который последовательно порождает статистически независимые пиксели согласно какому-то заранее заданному вероятностному закону. Если вероятности символов известны, то среднее информационное содержание изображения (энтропия) каждого элемента изображения может быть вычислена напрямую с помощью выражения пред. слайда Альтернативный подход – использование гистограммы яркостей для расчета частоты(формула используется та же) оценка первого порядка составит 1,81 бит/элемент. оценка второго порядка составляет 1, 25 бит/элемент Те можно построить такое отображение которое позволит сократить представление Классы методов сжатия Алгоритмы сжатия без потерь (lossless) позволяют при декомпрессии бит в бит восстановить исходное сообщение. Алгоритмы сжатия с потерями широко используются при сжатии музыки, видеоданных и изображений. Основы Принципиально невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Образуем полную группу данных длиной n бит Их число = 2n Число различных сообщений с длиной меньшей или равной n (при наличии хотя бы одного сообщения меньшей длины) будет не больше 2n. Это значит, что невозможно однозначно сопоставить все исходные сообщения сжатым: либо некоторые исходные сообщения не будут иметь сжатого представления, либо нескольким исходным сообщениям будет соответствовать одно и то же сжатое, а значит их нельзя отличить. Классы изображений • Изображения с небольшим количеством цветов (4-16) и большими областями, заполненными одним цветом. Примеры: деловая графика - гистограммы, диаграммы, графики и т.п. • Изображения, с использованием плавных переходов, построенные на компьютере. Примеры: графика презентаций, эскизные модели в САПР, изображения построенные по методу закраски Гуро. • Фотореалистичные изображения. Пример: отсканированные фотографии. • Фотореалистичные изображения с наложением деловой графики. Критерии оценки алгоритмов • Худший, средний и лучший коэффициенты сжатия. • Класс изображений, на который ориентирован алгоритм. • Потеря качества • Симметричность. Характеризует ресурсоемкость процессов кодирования и декодирования. Методы сжатия без потерь • Поточные и словарные алгоритмы при кодировании используется не информация о частотах символов в сообщении, а информация о последовательностях, встречавшихся ранее. • Алгоритмы статистического (энтропийного) сжатия. Сжатие информации на основе неравномерности частот, с которыми различные символы встречаются в сообщении. Кодирование длин серий (RLE - Run-Length Encoding) Последовательность повторяющихся символов заменяется символом и количеством его повторов. Применяется в форматах РСХ, TIFF, ВМР Не требует дополнительной памяти при работе, и быстро выполняется. Крайне низкая эффективность на последовательностях неповторяющихся символов Пример Длина 66 символов W- белый B - черный WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWW WWWWWWWWWWWWWWBWWWWWWWWWWWWWW • • • • • • • 12 символов «W»; 1 символ «B»; 12 символов «W»; 3 символа «B»; 24 символа «W»; 1 символ «B»; 13 символов «W» 12W1B12W3B24W1B13W -------------------------------------«АБАБАБ» (6 байт) «1А1Б1А1Б1А1Б» (12 байт) Модификации RLE • Второй вариант имеет больший максимальный коэффициент архивации и меньше увеличивает в размерах исходный файл. Признаком повтора в данном алгоритме является единица в старшем разряде соответствующего байта: Использование RLE Канонический алгоритм Хаффмана Использует только частоту появления одинаковых байт во входном блоке данных. Сопоставляет символам входного потока, которые встречаются чаще, цепочку битов меньшей длины. И, напротив, встречающимся редко - цепочку большей длины. Метод кодирования состоит из двух основных этапов: • Построение оптимального кодового дерева. • Построение отображения код-символ на основе построенного дерева. ----Используется в формате JPEG Алгоритм https://habrahabr.ru/post/144200/ Имеется последовательность «beep boop beer!» 1. считаем частоты символов: Символ Частота 'b' 3 'e' 4 'p' 2 '' 2 'o' 2 'r' 1 '!' 1 Продолжение 2. Создаем узлы бинарного дерева для каждого знака и добавим их в очередь, используя частоту в качестве приоритета: Символ Частота 'b' 3 'e' 4 'p' 2 '' 2 'o' 2 'r' 1 '!' 1 Продолжение 3. Объединяем два первых элемента из очереди и создаем новый узел дерева, в котором они оба будут потомками, а приоритет нового узла будет равен сумме их приоритетов. После этого мы добавим получившийся новый узел обратно в очередь Продолжение 4. Получим последовательно: Продолжение 5. Дерево построено: Построение отображения код-символ Символ Код 'b' 00 'e' 11 'p' 101 '' 011 'o' 010 'r' 1000 '!' 1001 Декодирование Поскольку ни один из полученных кодов не является префиксом другого, они могут быть однозначно декодированы при чтении их из потока. Символ Код 'b' 00 'e' 11 'p' 101 '' 011 'o' 010 'r' 1000 '!' 1001 Результат На практике, при реализации данного алгоритма сразу после построения дерева строится таблица Хаффмана. Таблица — это по сути связный список или массив, который содержит каждый символ и его код, потому что это делает кодирование более эффективным. Как правило, для кодирования используется таблица Хаффмана, а для декодирования — дерево Хаффмана. Входная строка: «beep boop beer!» Входная строка в бинарном виде: «0110 0010 0110 0101 0110 0101 0111 0000 0010 0000 0110 0010 0110 1111 0110 1111 0111 0000 0010 0000 0110 0010 0110 0101 0110 0101 0111 0010 0010 000» Закодированная строка: «0011 1110 1011 0001 0010 1010 1100 1111 1000 1001» Степень статистической избыточности Энтропия, которая определяет минимальное число бит, необходимое для представления заданной последовательности чисел с последующей возможностью полного восстановления информации Недостатки Для восстановления содержимого сжатого сообщения декодер должен знать таблицу частот, которой пользовался кодер. Следовательно, длина сжатого сообщения увеличивается на длину таблицы частот, которая должна посылаться впереди данных. Необходимость наличия полной частотной статистики перед началом собственно кодирования требует двух проходов по сообщению: одного для построения модели сообщения (таблицы частот и Ндерева), другого для собственно кодирования. Избыточность кодирования обращается в ноль лишь в тех случаях, когда вероятности кодируемых символов являются обратными степенями числа 2. Для источника с энтропией, не превышающей 1 (например, для двоичного источника), непосредственное применение кода Хаффмана бессмысленно. Адаптивный алгоритм Хаффмана Позволяет строить кодовую схему в поточном режиме (без предварительного сканирования данных), не имея никаких начальных знаний из исходного распределения, что позволяет за один проход сжать данные. Преимуществом этого способа является возможность кодировать на лету. Арифметическое кодирование Пpи аpифметическом кодиpовании текст пpедставляется вещественными числами в интеpвале от 0 до 1. По меpе кодиpования текста, отобpажающий его интеpвал уменьшается, а количество битов для его пpедставления возpастает. Очеpедные символы текста сокpащают величину интеpвала исходя из значений их веpоятностей, опpеделяемых моделью. Более веpоятные символы делают это в меньшей степени, чем менее веpоятные, и, следовательно, добавляют меньше битов к pезультату. -----Используется в JPEG-2000, MPEG-4, H.264 Пример Текст “eaii!”. Aлфавит { a,e,i,o,u,! } Символ Веpоятность Интеpвал a .2 [0.0; 0.2) e .3 [0.2; 0.5) i .1 [0.5; 0.6) o .2 [0.6; 0.8) u .1 [0.8; 0.9) ! .1 [0.9; 1.0) И кодиpовщику, и декодиpовщику известно, что в самом начале интеpвал есть [0; 1) Кодировка Текст “eaii!”. После пpосмотpа пеpвого символа "e", кодиpовщик сужает интеpвал до [0.2; 0.5), котоpый модель выделяет этому символу. Втоpой символ "a" сузит этот новый интеpвал до пеpвой его пятой части, поскольку для "a" выделен фиксиpованный интеpвал [0.0; 0.2). В pезультате получим pабочий интеpвал [0.2; 0.26) Символ Веpоятность Интеpвал a .2 [0.0; 0.2) e .3 [0.2; 0.5) i .1 [0.5; 0.6) o .2 [0.6; 0.8) u .1 [0.8; 0.9) ! .1 [0.9; 1.0) В начале [0.0; 1.0 ) После пpосмотpа "e" [0.2; 0.5 ) ‐"‐"‐"‐ "a" [0.2; 0.26 ) ‐"‐"‐"‐ "i" [0.23; 0.236 ) ‐"‐"‐"‐ "i" [0.233; 0.2336) ‐"‐"‐"‐ "!" [0.23354; 0.2336) Конечный интервал [0.23354; 0.2336) Вычисление границ NewHigh = OldLow + (OldHighOldLow)*HighRange(X) NewLow = OldLow + (OldHighOldLow)*LowRange(X) OldLow – нижняя граница интервала, в котором представляется текущий символ; OldHigh – верхняя граница интервала; HighRange(X) – исходная верхняя граница кодируемого символа; LowRange(X) – исходная нижняя граница кодируемого символа. Символ Веpоятность Интеpвал a .2 [0.0; 0.2) e .3 [0.2; 0.5) i .1 [0.5; 0.6) o .2 [0.6; 0.8) u .1 [0.8; 0.9) ! .1 [0.9; 1.0) В начале [0.0; 1.0 ) После пpосмотpа "e" [0.2; 0.5 ) ‐"‐"‐"‐ "a" [0.2; 0.26 ) ‐"‐"‐"‐ "i" [0.23; 0.236 ) ‐"‐"‐"‐ "i" [0.233; 0.2336) ‐"‐"‐"‐ "!" [0.23354; 0.2336) Конечный интервал [0.23354; 0.2336) Декодировка Текст “eaii!”. Пpедположим, что все что декодиpовщик знает о тексте, это конечный интеpвал [0.23354; 0.2336). Он сpазу же понимает, что пеpвый закодиpованный символ есть "e" Чтобы декодировать второй символ (который кодировался в полуинтервале [0,2;0.5)) полуинтервал нужно нормализовать, т.е. Символ Веpоятность Интеpвал привести к виду [0;1). Это делается с a .2 [0.0; 0.2) помощью следующей формулы: e .3 [0.2; 0.5) codeN=(code-RangeL(x))/(RangeH(x)-RangeL(x)), i .1 [0.5; 0.6) где code – текущее значение кода. codeN = (0.23354-0.2)/(0.5-0.2) =0.118 o .2 [0.6; 0.8) Тогда это “a” u .1 [0.8; 0.9) И тд ! .1 [0.9; 1.0) Словарные методы сжатия данных Входную последовательность символов можно рассматривать как последовательность строк, содержащих произвольное количество символов. Идея словарных методов состоит в замене строк символов на такие коды, что их можно трактовать как индексы строк некоторого словаря. Образующие словарь строки будем далее называть фразами. При декодировании осуществляется обратная замена индекса на соответствующую ему фразу словаря. Словарь - это набор таких фраз, которые будут встречаться в обрабатываемой последовательности. Индексы фраз должны быть построены таким образом, чтобы в среднем их представление занимало меньше места, чем требуют замещаемые строки. За счет этого и происходит сжатие. Роман Ф.М. Достоевского “Бесы” www.intuit.ru Методы сжатия изображений Длина строки Количество различны х строк Использовано комбинаций, % от всех возможны х 5 196969 0.0004 4 72882 0.0213 3 17481 0.6949 2 2536 13.7111 1 136 100.0000 Уменьшение размера возможно в первую очередь за счет того, что обычно в сжимаемых данных встречается лишь малая толика всех возможных строк длины n, поэтому для представления индекса фразы требуется, как правило, меньшее число битов, чем для представления исходной строки. Метод кодирования Лемпеля-Зива-Уэлша (Lempel-Ziv-Welch, LZW) Метод отображает последовательности символов источника различной длины на равномерный код, причем не требует априорного знания вероятностей появления кодируемых символов. LZW реализован в форматах GIF и TIFF Алгоритм является однопроходным Описание метода При запуске процесса кодирования строится «словарь», содержащий лишь кодируемые символы источника. Для 8-битового монохромного изображения словарь имеет размеры в 256. Кодер последовательно анализирует символы источника (т.е. значения пикселей), и при появлении отсутствующей в словаре серии, она помещается в определяемую алгоритмом (следующую свободную) позицию словаря. Если первые два пикселя изображения, например, были белыми (255-255), эта серия может быть приписана позиции 256, являющейся следующей свободной после зарезервированных для уровней яркостей позиций с 0 по 255. В следующий раз, когда встретится серия из двух белых пикселей, для их представления будет использовано кодовое слово 256, как адрес позиции, содержащей серию 255-255. В случае 9-битового словаря, содержащего 512 кодовых слов, исходные 8+8 = 16 битов, требуемые для представления двух пикселей, будут заменены одним 9-битовым кодовым словом. Ясно, что допустимый размер словаря является важнейшим параметром. Если он слишком мал, то обнаружение совпадающих серий яркостей будет маловероятна; если слишком велик, то размер кодового слова будет ухудшать характеристики сжатия Алгоритм Кодирование Начало. Шаг 1. Все возможные символы заносятся в словарь. Во входную фразу X заносится первый символ сообщения. Шаг 2. Считать очередной символ Y из сообщения. Шаг 3. Если Y -это символ конца сообщения, то выдать код для X, иначе: – Если фраза XY уже имеется в словаре, то присвоить входной фразе значение XY и перейти к Шагу 2 , – Иначе выдать код для входной фразы X, добавить XY в словарь и присвоить входной фразе значение Y. Перейти к Шагу 2. Конец. Декодирование Начало. Шаг 1. Все возможные символы заносятся в словарь. Во входную фразу X заносится первый код декодируемого сообщения. Шаг 2. Считать очередной код Y из сообщения. Шаг 3. Если Y- это конец сообщения, то выдать символ, соответствующий коду X, иначе: – Если фразы под кодом нет в словаре, вывести фразу, соответствующую коду , а фразу с кодом занести в словарь. – Иначе присвоить входной фразе код и перейти к Шагу 2 . Конец. Пример LZW-кодирования # = 00000 A = 00001 B = 00010 C = 00011 ... Z = 11010 ---------------------------------------------------Исходная длина 125 бит: TOBEORNOTTOBEORTOBEORNOT# ---------------------------------------------------Если сообщение будет длиннее, то элементы словаря будут представлять всё более и более длинные части текста, благодаря чему повторяющиеся слова будут представлены очень компактно. Результат 96 бит LZW-декодирование Нам нужно знать начальный словарь, а последующие записи словаря мы можем реконструировать уже на ходу, LZW и GIF Особенности реализации в формате сжатия изображений gif. - Переменный размер кода таблицы цепочек, который не может превышать 12 бит, т.е. не превышать числа 4095. - Использование двух специальных кодов – это код обновления (реинициализации) таблицы цепочек , и код завершения потока символов Определение количества цветов: 2-256 Кодирование пикселей изображения начинается кодами размером бит. По мере накопления таблицы будут увеличиваться значения кодов и как только очередной код достигает значения , то это значит, что значение необходимо увеличить на 1, иначе значение кода превысит прежний размер в бит. Ограничение размера таблицы приводит к необходимости переинициализации таблицы. А для того, чтобы декодировщик знал, что в определенный момент произошло перегенерирование таблицы, кодировщик в выходной поток записывает код управляющего символа . Сжатие данных с потерями Одна из серьезных проблем машинной графики заключается в том, что до сих пор не найден адекватный критерий оценки потерь качества изображения. А теряется оно постоянно — при оцифровке, при переводе в ограниченную палитру цветов, при переводе в другую систему цветопредставления для печати, и, при архивации с потерями. Тем не менее… Критерии качества сжатого изображения Среднеквадратичное отклонение значений пикселов: Максимальное отклонение: Мера, которую сейчас используют на практике, мера отношения сигнала к шуму (peak-to-peak signal-tonoise ratio — PSNR). Сжатие посредством квантования и дискретизации Человек способен замечать незначительные перепады яркости, но гораздо менее чувствителен к цветности. Также, начиная с определённого момента, повышение точности дискретизации не влияет на визуальное восприятие изображения. Таким образом, некоторая часть информации может быть удалена без ухудшения визуального качества. Такую информацию называют визуально избыточной. Дискретизация Самы м просты м способом удаления визуальной избы точности является уменьшение точности дискретизации, но на практике этот способ можно применять только для изображений с простой структурой, т.к. искажения, возникающие на сложны х изображениях, слишком заметны Дискретизация (от лат. discretio — «различать», «распознавать») — преобразование непрерывной функции в дискретную. Квантование Для удаления избыточной информации чаще уменьшают точность квантования, но нельзя уменьшать её бездумно, т.к. это приводит к резкому ухудшению качества изображения. Модификация Использовать равномерное квантование, но значением закодированной яркости выбирать не середину отрезка, а математическое ожидание яркости на этом отрезке, либо использовать неравномерное разбиение всего диапазона яркостей. Квантование (англ. quantization) — в информатике — разбиение диапазона значений непрерывной или дискретной величины на конечное число интервалов. Поканальная обработка Изменение уровней в цветоразностной модели. JPEG преобразование 1.Изображение преобразуется из цветового пространства RGB в YCbCr. 2.каналы Cb и Cr прореживают, то есть блоку пикселей присваивается усредненное значение. Например, после прореживания в 2 раза по вертикали и горизонтали, пиксели будут иметь такое соответствие: 3. Затем значения каналов разбиваются на блоки 8x8 (все видели эти квадратики на слишком сжатом изображении). 4.Каждый блок подвергается дискретно-косинусному-преобразованию (ДКП), являющемся разновидностью дискретного преобразования Фурье. Получим матрицу коэффициетов 8x8. Причем левый верхний коэффициент называется DC-коффициентом (он самый важный и является усредненным значением всех значений), а оставшиеся 63 — AC-коэффициентами. 5. Получившиеся коэффициенты квантуются, т.е. каждый умножается на коэффициент матрицы квантования (каждый кодировщик обычно использует свою матрицу квантования). 6. Затем они кодируются кодами Хаффмана. Дискретное косинусное преобразование Дискретное преобразование обладает свойствами: Некоррелированность коэффициентов . Коэффициенты независимы друг от друга, т.е. точность представления одного коэффициента не зависит от любого другого. " Уплотнение" энергии (англ. energy compaction). Преобразование сохраняет основную информацию в малом количестве коэффициентов. Данное свойство сильнее всего проявляется на фотореалистичных изображениях. Пирамиды изображений Пирамида изображений представляет собой набор изображений в уменьшающемся масштабе, организованный в форме пирамиды. Основу пирамиды составляет подлежащее обработке изображение высокого разрешения; вершина пирамиды состоит из приближения низкого разрешения. По мере движения вверх по пирамиде масштаб (размеры и разрешение) уменьшаются. Если нижний уровень J имеет размеры 2Jx2J или NxN, где J = log2N, то промежуточный уровень j имеет размеры 2kх2k, где 0