Охранная сигнализация

Пожарная сигнализация

Мини АТС и IP-телефония

 

Главная Термины: Видеонаблюдение Сжатие данных. Алгоритмы и форматы

Сжатие данных. Алгоритмы и форматы

Сжатие данных (графических изображений, видеоизображений и звука) — процедура их перекодирования, производимая с целью уменьшения их объёма. Применяется для более рационального использования устройств хранения и передачи данных.

 

Сжатие основано на устранении избыточности информации, содержащейся в исходных данных.

Примером избыточности является повторение в тексте фрагментов (например, слов естественного или машинного языка). Подобная избыточность обычно устраняется заменой повторяющейся последовательности более коротким значением (кодом). Другой вид избыточности связан с тем, что некоторые значения в сжимаемых данных встречаются чаще других, при этом возможно заменять часто встречающиеся данные более короткими кодами, а редкие — более длинными (вероятностное сжатие). Сжатие данных, не обладающих свойством избыточности (например, случайный сигнал или шум), невозможно без потерь. Также, обычно невозможно сжатие зашифрованной информации.

 

Алгоритмы сжатия делятся на

Сжатие без потерь

возможно восстановление исходных данных без искажений
используется при обработке компьютерных программ и данных, реже — для сокращения объёма звуковой, фото- и видеоинформации

Наиболее известные:

Преобразование Барроуза — Уилера; преобразование Шиндлера; алгоритм DEFLATE; Дельта-кодирование; Энтропийное кодирование; Инкрементное кодирование; Алгоритмы Лемпеля — Зива; LZ77; LZ77-PM; LZFG; LZFG-PM; LZP; LZBW; LZSS; LZB; LZH; LZRW1; LZ78; LZW; LZW-PM; LZMW; LZMA; LZO; PPM; RLE; SEQUITUR; Вейвлет; Алгоритм Шеннона — Фано; Алгоритм Хаффмана; Адаптивное кодирование Хаффмана; Усечённое двоичное кодирование; Арифметическое кодирование; Адаптивное арифметическое кодирование; Кодирование расстояний; Энтропийное кодирование; Унарное кодирование; Кодирование Фибоначчи; Кодирование Голомба; Кодирование Райса; Кодирование Элиаса

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

восстановление возможно с искажениями, несущественными с точки зрения дальнейшего использования восстановленных данных
применяется для сокращения объёма звуковой, фото- и видеоинформации, оно значительно эффективнее сжатия без потерь.

Наиболее известные:

JPEG; Линейное предсказывающее кодирование; А-закон; Мю-закон; Фрактальное сжатие; Трансформирующее кодирование; Векторная квантизация; Вейвлетное сжатие

 

Описание некоторых алгоритмов без потерь

Алгоритм RLE (вариант 1.)

Известен также как алгоритм PPM

Групповое кодирование — от английского Run Length Encoding (RLE) — один из самых старых и самых простых алгоритмов архивации графики.

Изображение в нем (как и в нескольких алгоритмах, описанных ниже) вытягивается в цепочку байт по строкам растра.

Само сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт.

Замена их на пары "счетчик повторений" - "значение" уменьшает избыточность данных.

Алгоритм рассчитан на деловую графику — изображения с большими областями повторяющегося цвета.

Ситуация, когда файл увеличивается, для этого простого алгоритма не так уж редка. Ее можно легко получить, применяя групповое кодирование к обработанным цветным фотографиям.

Данный алгоритм реализован в формате PCX.

 

Алгоритм RLE (вариант 2.)

Имеет больший максимальный коэффициент архивации и меньше увеличивает в размерах исходный файл.

Алгоритм декомпрессии для него выглядит так: Признаком повтора в данном алгоритме является единица в старшем разряде соответствующего байта. Похожие схемы компрессии использована в качестве одного из алгоритмов, поддерживаемых форматом TIFF, а также в формате TGA.

Характеристики алгоритма RLE:

Коэффициенты компрессии:

Первый вариант: 32, 2, 0,5.

Второй вариант: 64, 3, 128/129. (Лучший, средний, худший коэффициенты)

Класс изображений: Ориентирован алгоритм на изображения с небольшим количеством цветов: деловую и научную графику.

Симметричность: Примерно единица.

Характерные особенности: К положительным сторонам алгоритма, пожалуй, можно отнести только то, что он не требует дополнительной памяти при архивации и разархивации, а также быстро работает. Интересная особенность группового кодирования состоит в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения.

Особенности изображения, за счет которых происходит сжатие - Подряд идущие одинаковые цвета: 2 2 2 2 2 2 2 15 15 15

Коэффициенты сжатия - 32, 2, 0.5

 

Семейство алгоритмов LZ

LZW по первым буквам фамилий его разработчиков — Lempel, Ziv и Welch. Сжатие в нем, в отличие от PCX, осуществляется уже за счет одинаковых цепочек байт.

подобных алгоритмов, различающихся, например, методом поиска повторяющихся цепочек. Один из достаточно простых вариантов этого алгоритма, например, предполагает, что во входном потоке идет либо пара , либо просто “пропускаемых” байт и сами значения байтов (как во втором варианте алгоритма RLE). При разархивации для пары копируются байт из выходного массива, полученного в результате разархивации на байт раньше, а значений “пропускаемых” байт просто копируются в выходной массив из входного потока. Данный алгоритм является несимметричным по времени, поскольку требует полного перебора буфера при поиске одинаковых подстрок. В результате нам сложно задать большой буфер из-за резкого возрастания времени компрессии. Максимальный коэффициент сжатия составит в пределе 8192 раза. В пределе, поскольку максимальное сжатие мы получаем превращая 32Кб буфера в 4 байта, а буфер такого размера мы накопим не сразу. Однако, минимальная подстрока, для которой нам выгодно проводить сжатие должна состоять в общем случае минимум из 5 байт, что и определяет малую ценность данного алгоритма. К достоинствам LZ можно отнести чрезвычайную простоту алгоритма декомпрессии.

 

LZMA

Сокращение от англ. Lempel-Ziv-Markov chain-Algorithm

 

LZO

Алгоритм компрессии данных ориентированный на скорость

 

Алгоритм LZW

Рассматриваемый нами ниже вариант алгоритма будет использовать дерево для представления и хранения цепочек. Очевидно, что это достаточно сильное ограничение на вид цепочек, и далеко не все одинаковые подцепочки в нашем изображении будут использованы при сжатии. Однако в предлагаемом алгоритме выгодно сжимать даже цепочки, состоящие из 2 байт.

Процесс сжатия выглядит достаточно просто. Мы считываем последовательно символы входного потока и проверяем, есть ли в созданной нами таблице строк такая строка. Если строка есть, то мы считываем следующий символ, а если строки нет, то мы заносим в поток код для предыдущей найденной строки, заносим строку в таблицу и начинаем поиск снова.

В случае, если мы постоянно будем встречать новую подстроку, мы запишем в выходной поток 3810 кодов, которым будет соответствовать строка из 3808 символов. Без учета замечания 1 это составит увеличение файла почти в 1.5 раза.

LZW реализован в форматах GIF и TIFF.

Характеристики алгоритма LZW:

Коэффициенты компрессии: Примерно 1000, 4, 5/7 (Лучший, средний, худший коэффициенты) Сжатие в 1000 раз достигается только на одноцветных изображениях размером кратным примерно 7 Мб (6.918...).

Класс изображений: Ориентирован LZW на 8-битные изображения, построенные на компьютере. Сжимает за счет одинаковых подцепочек в потоке.

Симметричность: Почти симметричен, при условии оптимальной реализации операции поиска строки в таблице.

Характерные особенности: Ситуация, когда алгоритм увеличивает изображение, встречается крайне редко. LZW универсален — именно его варианты используются в обычных архиваторах.

Особенности изображения, за счет которых происходит сжатие - Одинаковые подцепочки: 2 3 15 40 2 3 15 40

Коэффициенты сжатия - 1000, 4, 5/7

 

Алгоритм Хаффмана

Один из классических алгоритмов, известных с 60-х годов. Использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины. И, напротив, встречающимся редко — цепочку большей длины. Для сбора статистики требует двух проходов по изображению.

На практике используются его разновидности. Так, в некоторых случаях резонно либо использовать постоянную таблицу, либо строить ее “адаптивно”, т.е. в процессе архивации/разархивации. Эти приемы избавляют нас от двух проходов по изображению и необходимости хранения таблицы вместе с файлом. Кодирование с фиксированной таблицей применяется в качестве последнего этапа архивации в JPEG и в рассмотренном ниже алгоритме CCITT Group 3.

Характеристики классического алгоритма Хаффмана:

Коэффициенты компрессии: 8, 1,5, 1 (Лучший, средний, худший коэффициенты)

Класс изображений: Практически не применяется к изображениям в чистом виде. Обычно используется как один из этапов компрессии в более сложных схемах.

Симметричность: 2 (за счет того, что требует двух проходов по массиву сжимаемых данных).

Характерные особенности: Единственный алгоритм, который не увеличивает размера исходных данных в худшем случае (если не считать необходимости хранить таблицу перекодировки вместе с файлом).

Особенности изображения, за счет которых происходит сжатие - Разная частота появления цвета: 2 2 3 2 2 4 3 2 2 2 4

Коэффициенты сжатия - 8, 1.5, 1

 

Алгоритм Хаффмана с фиксированной таблицей CCITT Group 3

Близкая модификация алгоритма используется при сжатии черно-белых изображений (один бит на пиксел). Полное название данного алгоритма CCITT Group 3. Это означает, что данный алгоритм был предложен третьей группой по стандартизации Международного Консультационного Комитета по Телеграфии и Телефону (Consultative Committee International Telegraph and Telephone). Последовательности подряд идущих черных и белых точек в нем заменяются числом, равным их количеству. А этот ряд уже, в свою очередь, сжимается по Хаффману с фиксированной таблицей.

Определение: Набор идущих подряд точек изображения одного цвета называется серией. Длина этого набора точек называется длиной серии.

Этот алгоритм реализован в формате TIFF.

Характеристики алгоритма CCITT Group 3

Коэффициенты компрессии: лучший коэффициент стремится в пределе к 213.(3), средний 2, в худшем случае увеличивает файл в 5 раз.

Класс изображений: Двуцветные черно-белые изображения, в которых преобладают большие пространства, заполненные белым цветом.

Симметричность: Близка к 1.

Характерные особенности: Данный алгоритм чрезвычайно прост в реализации, быстр и может быть легко реализован аппаратно.

Особенности изображения, за счет которых происходит сжатие - Преобладание белого цвета в изображении, большие области, заполненные одним цветом

Коэффициенты сжатия - 213(3), 5, 0.25

 

JBIG

Алгоритм разработан группой экспертов ISO (Joint Bi-level Experts Group) специально для сжатия однобитных черно-белых изображений. Например, факсов или отсканированных документов. В принципе может применяться и к 2-х, и к 4-х битовым картинкам. При этом алгоритм разбивает их на отдельные битовые плоскости. JBIG позволяет управлять такими параметрами, как порядок разбиения изображения на битовые плоскости, ширина полос в изображении, уровни масштабирования. Последняя возможность позволяет легко ориентироваться в базе больших по размерам изображений, просматривая сначала их уменьшенные копии. Настраивая эти параметры, можно использовать описанный выше эффект “огрубленного изображения” при получении изображения по сети или по любому другому каналу, пропускная способность которого мала по сравнению с возможностями процессора. Распаковываться изображение на экране будет постепенно, как бы медленно “проявляясь”. При этом человек начинает анализировать картинку задолго до конца процесса разархивации.

Алгоритм построен на базе Q-кодировщика, патентом на который владеет IBM. Q-кодер так же, как и алгоритм Хаффмана, использует для чаще появляющихся символов короткие цепочки, а для реже появляющихся — длинные. Однако, в отличие от него, в алгоритме используются и последовательности символов.

Коэффициенты сжатия - 2-30 раз

 

Lossless JPEG

Этот алгоритм, разработан группой экспертов в области фотографии (Joint Photographic Expert Group). В отличие от JBIG, Lossless JPEG ориентирован на полноцветные 24-битные или 8-битные в градациях серого изображения без палитры. Он представляет собой специальную реализацию JPEG без потерь. Коэффициенты сжатия: 20, 2, 1. Lossless JPEG рекомендуется применять в тех приложениях, где необходимо побитовое соответствие исходного и декомпрессированного изображений. Подробнее об алгоритме сжатия JPEG см. следующий раздел.

Коэффициенты сжатия - 2 раза

 

Преобразование Барроуза — Уилера

Также известен как англ. BWT — предварительная обработка данных для улучшения сжатия без потерь

 

Преобразование Шиндлера

Английское название ST — модификация преобразования Барроуза — Уилера

 

Дельта-кодирование

Эффективно для сжатия данных, в которых последовательности часто повторяются

 

Инкрементное кодирование

Дельта-кодирование применяемое к последовательности строк

 

Алгоритм SEQUITUR

Сжатие без потерь, автоматическое адаптивное построение контекстно-свободной грамматики для обрабатываемых данных

 

Вейвлет

Кодирование на основе вложенных нуль-деревьев (англ.) (EZW-кодирование)

 

Энтропийное кодирование

Схема кодирования, которая присваивает коды символам таким образом, чтобы соотнести длину кодов с вероятностью появления символов

 

Алгоритм Шеннона — Фано

Самый простой алгоритм кодирования

 

Усечённое двоичное кодирование

Используется для однородного вероятностного распределения с конечным алфавитом

 

Арифметическое кодирование

Развитие энтропийного кодирования

 

Адаптивное арифметическое кодирование

Техника адаптивного кодирования, основывающаяся на арифметическом кодировании

 

Кодирование расстояний

Метод сжатия данных, который близок по эффективности к арифметическому кодированию

 

Унарное кодирование

Код, который представляет число n в виде n единиц с замыкающим нулём

 

Дельта (гамма) омега-кодирование Элиаса

Английское название Elias coding — универсальный код, кодирующий положительные целые числа

 

Кодирование Фибоначчи

Универсальный код, который кодирует положительные целые числа в двоичные кодовые слова

 

Кодирование Голомба

Форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением

 

Кодирование Райса

Форма энтропийного кодирования, которая оптимальна для алфавитов с геометрическим распределением

 

Описание некоторых алгоритмов с потерями

 

Алгоритм JPEG

JPEG — (читается джейпег) один из самых новых и достаточно мощных алгоритмов. Практически он является стандартом де-факто для полноцветных изображений. Оперирует алгоритм областями 8х8, на которых яркость и цвет меняются сравнительно плавно. Вследствие этого, при разложении матрицы такой области в двойной ряд по косинусам (см. формулы ниже) значимыми оказываются только первые коэффициенты. Таким образом, сжатие в JPEG осуществляется за счет плавности изменения цветов в изображении.

Алгоритм разработан группой экспертов в области фотографии специально для сжатия 24-битных изображений. JPEG — Joint Photographic Expert Group — подразделение в рамках ISO — Международной организации по стандартизации. В целом алгоритм основан на дискретном косинусоидальном преобразовании (в дальнейшем ДКП), применяемом к матрице изображения для получения некоторой новой матрицы коэффициентов. Для получения исходного изображения применяется обратное преобразование.

Процесс восстановления изображения в этом алгоритме полностью симметричен. Метод позволяет сжимать некоторые изображения в 10-15 раз без серьезных потерь.

?Существенными положительными сторонами алгоритма является то, что: Задается степень сжатия. Выходное цветное изображение может иметь 24 бита на точку.

Отрицательными сторонами алгоритма является то, что: При повышении степени сжатия изображение распадается на отдельные квадраты (8x8). Это связано с тем, что происходят большие потери в низких частотах при квантовании, и восстановить исходные данные становится невозможно. Проявляется эффект Гиббса — ореолы по границам резких переходов цветов.

Стандартизован JPEG относительно недавно — в 1991 году. Но уже тогда существовали алгоритмы, сжимающие сильнее при меньших потерях качества. Дело в том, что действия разработчиков стандарта были ограничены мощностью существовавшей на тот момент техники. То есть даже на персональном компьютере алгоритм должен был работать меньше минуты на среднем изображении, а его аппаратная реализация должна быть относительно простой и дешевой. Алгоритм должен был быть симметричным (время разархивации примерно равно времени архивации).

Последнее требование сделало возможным появление таких игрушек, как цифровые фотоаппараты — устройства, размером с небольшую видеокамеру, снимающие 24-битовые фотографии на 10-20 Мб флэш карту с интерфейсом PCMCIA. Потом эта карта вставляется в разъем на вашем лэптопе и соответствующая программа позволяет считать изображения. Не правда ли, если бы алгоритм был несимметричен, было бы неприятно долго ждать, пока аппарат “перезарядится” — сожмет изображение.

Не очень приятным свойством JPEG является также то, что нередко горизонтальные и вертикальные полосы на дисплее абсолютно не видны, и могут проявиться только при печати в виде муарового узора. Он возникает при наложении наклонного растра печати на горизонтальные и вертикальные полосы изображения. Из-за этих сюрпризов JPEG не рекомендуется активно использовать в полиграфии, задавая высокие коэффициенты. Однако при архивации изображений, предназначенных для просмотра человеком, он на данный момент незаменим.

Широкое применение JPEG долгое время сдерживалось, пожалуй, лишь тем, что он оперирует 24-битными изображениями. Поэтому для того, чтобы с приемлемым качеством посмотреть картинку на обычном мониторе в 256-цветной палитре, требовалось применение соответствующих алгоритмов и, следовательно, определенное время. В приложениях, ориентированных на придирчивого пользователя, таких, например, как игры, подобные задержки неприемлемы. Кроме того, если имеющиеся у вас изображения, допустим, в 8-битном формате GIF перевести в 24-битный JPEG, а потом обратно в GIF для просмотра, то потеря качества произойдет дважды при обоих преобразованиях. Тем не менее, выигрыш в размерах архивов зачастую настолько велик (в 3-20 раз!), а потери качества настолько малы, что хранение изображений в JPEG оказывается очень эффективным.

Несколько слов необходимо сказать о модификациях этого алгоритма. Хотя JPEG и является стандартом ISO, формат его файлов не был зафиксирован. Пользуясь этим, производители используют свои, несовместимые между собой форматы, и, следовательно, могут изменить алгоритм. Так, внутренние таблицы алгоритма, рекомендованные ISO, заменяются ими на свои собственные. Кроме того, легкая неразбериха присутствует при задании степени потерь. Например, при тестировании выясняется, что “отличное” качество, “100%” и “10 баллов” дают существенно различающиеся картинки. При этом, кстати, “100%” качества не означает сжатие без потерь. Встречаются также варианты JPEG для специфических приложений.

Как стандарт ISO JPEG начинает все шире использоваться при обмене изображениями в компьютерных сетях. Поддерживается алгоритм JPEG в форматах Quick Time, PostScript Level 2, Tiff 6.0 и, на данный момент занимает видное место в системах мультимедиа.

Характеристики алгоритма JPEG:

  • Коэффициенты компрессии: 2-200 (Задается пользователем).
  • Класс изображений: Полноцветные 24 битные изображения, или изображения в градациях серого без резких переходов цветов (фотографии).
  • Симметричность: 1
  • Характерные особенности: В некоторых случаях, алгоритм создает “ореол” вокруг резких горизонтальных и вертикальных границ в изображении (эффект Гиббса). Кроме того, при высокой степени сжатия изображение распадается на блоки 8х8 пикселов.
  • Особенности изображения, за счет которых происходит сжатие - Отсутствие резких границ

Фрактальный алгоритм

Фрактальная архивация основана на том, что мы представляем изображение в более компактной форме — с помощью коэффициентов системы итерируемых функций (Iterated Function System — далее по тексту как IFS). Прежде чем рассматривать сам процесс архивации, разберем, как IFS строит изображение, т.е. процесс декомпрессии .

Строго говоря, IFS представляет собой набор трехмерных аффинных преобразований, в нашем случае переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (х_координата, у_координата, яркость).

При кратком изложении упрощенного варианта алгоритма были пропущены многие важные вопросы. Например, что делать, если алгоритм не может подобрать для какого-либо фрагмента изображения подобный ему? Достаточно очевидное решение — разбить этот фрагмент на более мелкие и попытаться поискать для них. В то же время понятно, что эту процедуру нельзя повторять до бесконечности, иначе количество необходимых преобразований станет так велико, что алгоритм перестанет быть алгоритмом компрессии. Следовательно, мы допускаем потери в какой-то части изображения.

Для фрактального алгоритма компрессии, как и для других алгоритмов сжатия с потерями, очень важны механизмы, с помощью которых можно будет регулировать степень сжатия и степень потерь. К настоящему времени разработан достаточно большой набор таких методов. Во-первых, можно ограничить количество аффинных преобразований, заведомо обеспечив степень сжатия не ниже фиксированной величины. Во-вторых, можно потребовать, чтобы в ситуации, когда разница между обрабатываемым фрагментом и наилучшим его приближением будет выше определенного порогового значения, этот фрагмент дробился обязательно (для него обязательно заводится несколько “линз”). В-третьих, можно запретить дробить фрагменты размером меньше, допустим, четырех точек. Изменяя пороговые значения и приоритет этих условий, мы будем очень гибко управлять коэффициентом компрессии изображения, в диапазоне от побитового соответствия, до любой степени сжатия. Причем, эта гибкость будет гораздо выше, чем у ближайшего “конкурента” — алгоритма JPEG.

 


О компании

Объединив команду профессионалов различных специальностей, способных реализовать различные проекты, компания ПРОКСИМА предлагает комплекс услуг, включающий проектирование, подбор, поставку, монтаж, гарантийное и сервисное обслуживание систем видеонаблюдения, охранной и пожарной сигнализаций, систем контроля доступа, оповещения, мини АТС, антикражных систем, учета посетителей, ВОЛС, СКС, ЛВС, домофонных систем, электромонтажных работ, автоматических ворот. Наша задача предоставить вам решение, максимально удовлетворяющее вашим потребностям.