Главная Глоссарий Видеонаблюдение Сжатие данных: алгоритмы и форматы
Глоссарий
Алфавитный навигатор по статьям
1  3  4  7  8  9  
A  B  C  D  E  F  G  H  I  N  O  P  Q  R  S  T  V  W  X  
А  Б  В  Г  Д  З  И  К  Л  М  Н  О  П  Р  С  Т  У  Ф  Ц  Ч  Ш  Э  Я  

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

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

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

Алгоритмы сжатия делятся на
Сжатие без потерь
возможно восстановление исходных данных без искажений
используется при обработке компьютерных программ и данных, реже — для сокращения объёма звуковой, фото- и видеоинформации
Наиболее известные:
Преобразование Барроуза — Уилера; преобразование Шиндлера; алгоритм 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-кодирование)

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

Алгоритм Шеннона — Фано
Самый простой алгоритм кодирования

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

Арифметическое кодирование
Развитие энтропийного кодирования


Видеонаблюдение

Внешний вид AN5-21B3.6I Внешний вид AN5-21B3.6I
Уличная аналоговая видеокамера
- 1/3" Pixel plus 1099 - 800 ТВЛ - 3,6 мм - ИК- 20 м
1 764

Производитель Axycam
Внешний вид AD4-P37B3.6I-MG Внешний вид AD4-P37B3.6I-MG
  • - 1/4" 1Мр H42
  • - 720p ( 30 к/с)
  • - 3.6mm
  • - подсветка - 20м
1 829

Производитель Axycam
Внешний вид AN4-37B3.6I-MG Внешний вид AN4-37B3.6I-MG
  • - 1/4" 1Мр H42
  • - 720p ( 30 к/с)
  • - 3.6mm
  • - подсветка - 20м
2 025

Производитель Axycam
Внешний вид AD-P31B3.6I-AHD Внешний вид AD-P31B3.6I-AHD
  • - 1/4" 1Мр Omnivision
  • - 720p ( 30 к/с)
  • - 3.6mm
  • - подсветка - 20м
2 156

Производитель Axycam
Внешний вид AD-P31B2.8I-AHD Внешний вид AD-P31B2.8I-AHD
  • - 1/4" 1Мр Omnivision
  • - 720p ( 30 к/с)
  • - 2.8mm
  • - подсветка - 20м
2 286

Производитель Axycam
Внешний вид AN5-31B3.6I-AHD white/dark grey Внешний вид AN5-31B3.6I-AHD white/dark grey
  • - 1/4" 1Мр Omnivision
  • - 720p ( 30 к/с)
  • - 3.6mm
  • - подсветка - 20м
2 482

Производитель Axycam
Внешний вид AD-31B3.6I-AHD Внешний вид AD-31B3.6I-AHD
  • - 1/4" 1Мр Omnivision
  • - 720p ( 30 к/с)
  • - 3.6mm
  • - подсветка - 25м
2 548

Производитель Axycam
Внешний вид AD7-31V12I-AHD Внешний вид AD7-31V12I-AHD
  • - 1/4" 1Мр Omnivision
  • - 720p ( 30 к/с)
  • - 2.8-12mm
  • - подсветка - 25м
3 854

Производитель Axycam
Внешний вид AD-P33B3.6NIL Внешний вид AD-P33B3.6NIL
Купольная металлическая IP камера
4 050

Производитель Axycam
Внешний вид AN4-37V12I-MG Внешний вид AN4-37V12I-MG
  • - 1/4" 1Мр H42
  • - 720p ( 30 к/с)
  • - 2.8-12mm
  • - подсветка - 40м
4 246

Производитель Axycam
Найдено товаров: 2031
1 2 3 4 5

Возврат к списку

Создание проекта системы видеонаблюдения всего за несколько минут;
Все РЕАЛЬНО: в т.ч. сектора наблюдения, параметры кабельных трасс;
Загрузка готовых планов и их масштабирование;
Спецификация обрудования и смета создается автоматически;
Дружелюбный интерфейс;
Индивидуальные настройки программы и оборудования.
Техподдержка встроена непосредственно в программу.
Регистрация занимает одну минуту.

ОТ ЗАПРОСА ДО ОФОРМЛЕННОГО ПРЕДЛОЖЕНИЯ - 15 МИНУТ