Кодирование Голомба - это метод сжатия данных без потерь с использованием семейства кодов сжатия данных, изобретенных Соломоном В. Голомбом в 1960-х годах. Алфавиты следующие за геометрическое распределение будут иметь код Голомбы в качестве оптимального префикса кода , [1] делает Голомбу кодирования очень хорошо подходит для ситуаций , в которых возникновение малых значений во входном потоке значительно чаще , чем большие значения.
Кодирование риса
Кодирование Райса (изобретенное Робертом Ф. Райсом ) означает использование подмножества семейства кодов Голомба для создания более простого (но, возможно, неоптимального) префиксного кода. Райс использовал этот набор кодов в адаптивной схеме кодирования ; «Кодирование Райса» может относиться либо к этой адаптивной схеме, либо к использованию этого подмножества кодов Голомба. В то время как код Голомба имеет настраиваемый параметр, который может быть любым положительным целым числом, коды Райса - это те, в которых настраиваемый параметр является степенью двойки. Это делает коды Райса удобными для использования на компьютере, поскольку умножение и деление на 2 можно более эффективно реализовать в двоичной арифметике .
Райс был мотивирован предложить это более простое подмножество из-за того факта, что геометрические распределения часто меняются со временем, точно не известны или и того, и другого, поэтому выбор кажущегося оптимальным кода может быть не очень выгодным.
Кодирование Райса используется в качестве этапа энтропийного кодирования в ряде методов сжатия изображений без потерь и аудиоданных .
Обзор
Построение кодов
Кодирование Голомба использует настраиваемый параметр разделить входное значение на две части: , результат деления на , а также , остаток. Частное передается в унарном кодировании , а остаток - в усеченном двоичном кодировании . Когда Кодирование Голомба эквивалентно унарному кодированию.
Коды Голомба – Райса можно рассматривать как коды, которые указывают число по положению ячейки ( q ) и смещению внутри ячейки ( r ). На рисунке выше показано положение Q и смещение г для кодирования целого числа N , используя Голомбу-Райс параметр M .
Формально две части задаются следующим выражением, где кодируемое число:
а также
- .
Окончательный результат выглядит так: .
Обратите внимание, что может иметь различное количество бит. Конкретно,составляет только b битов для кода Райса и переключается между b -1 и b битами для кода Голомба (т. е. M не является степенью 2). Позволять. Если, затем используйте биты b -1 для кодирования r . Если, затем используйте биты b для кодирования r . Четко,если M является степенью 2, и мы можем закодировать все значения r с помощью b битов.
Параметр M является функцией соответствующего процесса Бернулли , который параметризуетсявероятность успеха в данном судебном процессе Бернулли . является либо медианой распределения, либо медианой +/− 1. Его можно определить с помощью следующих неравенств:
которые решаются
- .
Код Голомба для этого распределения эквивалентен коду Хаффмана для тех же вероятностей, если бы можно было вычислить код Хаффмана.
Использовать с целыми числами со знаком
Схема Голомба была разработана для кодирования последовательностей неотрицательных чисел. Однако его легко расширить, чтобы принимать последовательности, содержащие отрицательные числа, используя схему перекрытия и чередования , в которой все значения переназначаются на некоторое положительное число уникальным и обратимым способом. Последовательность начинается: 0, -1, 1, -2, 2, -3, 3, -4, 4 ... n- е отрицательное значение (т.е. -n) отображается на n- е нечетное число (2n- 1), а m- е положительное значение отображается на m- е четное число (2m). Математически это можно выразить следующим образом: положительное значение отображается на () и отрицательное значение отображается на (). Такой код можно использовать для простоты, даже если он неоптимален. Истинно оптимальные коды для двусторонних геометрических распределений включают несколько вариантов кода Голомба, в зависимости от параметров распределения, включая этот. [2]
Простой алгоритм
Обратите внимание, что это кодирование Райса – Голомба, где в остаточном коде используется простое усеченное двоичное кодирование, также называемое «кодирование Райса» (другие двоичные кодирования переменной длины, такие как арифметические или кодирование Хаффмана, возможны для остальных кодов, если статистическое распределение кодов остатка не является плоским, особенно когда используются не все возможные остатки после деления). В этом алгоритме, если параметр M является степенью 2, он становится эквивалентным более простому кодированию Райса.
- Установите для параметра M целочисленное значение.
- Для N , числа, которое нужно закодировать, найти
- частное = q = int [ N / M ]
- остаток = r = N по модулю M
- Создать кодовое слово
- Формат кода:
, где - Факторный код (в унарном кодировании )
- Запишите строку длиной q из 1 бит (альтернативно из 0 бит)
- Запишите 0 бит (соответственно 1 бит)
- Остаточный код (в усеченной двоичной кодировке )
- ПОЗВОЛЯТЬ
- Если код r в двоичном представлении с использованием b битов.
- Если кодировать номер в двоичном представлении с использованием битов b + 1.
- ПОЗВОЛЯТЬ
- Формат кода:
Пример
Установите M = 10. Таким образом,. Обрезка
|
|
Например, при кодировании Райса – Голомба параметра M = 10 десятичное число 42 сначала будет разделено на q = 4, r = 2 и будет закодировано как qcode ( q ), rcode ( r ) = qcode (4 ), rcode (2) = 11110,010 (вам не нужно кодировать разделяющую запятую в выходном потоке, потому что 0 в конце кода q достаточно, чтобы сказать, когда q заканчивается, а r начинается; оба qcode и rcode имеют самостоятельное разделение).
Используйте для кодирования длин серий
Учитывая алфавит из двух символов или набор из двух событий, P и Q , с вероятностями p и (1 - p ) соответственно, где p ≥ 1/2, кодирование Голомба может использоваться для кодирования серий из нуля или более P ' ы разделены одиночными Q «с. В этом приложении наилучшей настройкой параметра M является ближайшее целое число к. Когда p = 1/2, M = 1 и код Голомба соответствует унарному ( n ≥ 0 P, за которым следует Q , кодируется как n единиц, за которыми следует ноль). Если желателен более простой код, можно присвоить параметр Голомба-Райса (т.е. параметр Голомба ) до ближайшего к ; хотя это не всегда лучший параметр, обычно это лучший параметр Райса, и его эффективность сжатия довольно близка к оптимальному коду Голомба. (Сам Райс предложил использовать различные коды для одних и тех же данных, чтобы выяснить, какой из них лучше. Более поздний исследователь JPL предложил различные методы оптимизации или оценки параметра кода. [3] )
Рассмотрите возможность использования кода Райса с двоичной частью, имеющей битов для последовательностей кодирования длин серий, где P имеет вероятность. Если вероятность того, что бит будет частью -битовый запуск ( P s и один Q ) и - степень сжатия этого прогона, то ожидаемая степень сжатия будет
Сжатие часто выражается в терминах , пропорция сжата. Для, подход кодирования длин серий приводит к степеням сжатия, близким к энтропийным . Например, используя код Райса для дает сжатие, а предел энтропии .
Адаптивное кодирование длин серий Голомба-Райса
Когда распределение вероятностей для целых чисел неизвестно, оптимальный параметр для кодировщика Голомба-Райса не может быть определен. Таким образом, во многих приложениях используется двухпроходный подход: сначала блок данных сканируется для оценки функции плотности вероятности (PDF) для данных. Затем из этой оцененной PDF определяется параметр Голомба-Райса. Более простой вариант этого подхода - предположить, что PDF принадлежит параметризованному семейству, оценить параметры PDF на основе данных, а затем определить расчет оптимального параметра Голомба-Райса. Это подход, используемый в большинстве приложений, обсуждаемых ниже.
Альтернативный подход к эффективному кодированию целочисленных данных, PDF которых неизвестен или изменяется, заключается в использовании обратно-адаптивного кодировщика. Метод Голомба-Райса (RLGR) достигает этого с помощью очень простого алгоритма, который регулирует параметр Голомба-Райса вверх или вниз, в зависимости от последнего закодированного символа. Декодер может следовать тому же правилу для отслеживания изменения параметров кодирования, поэтому не требуется передавать дополнительную информацию, а только закодированные данные. Предполагая, что обобщенный гауссовский PDF, который охватывает широкий диапазон статистических данных, наблюдаемых в данных, таких как ошибки предсказания или коэффициенты преобразования в мультимедийных кодеках, алгоритм кодирования RLGR может очень хорошо работать в таких приложениях.
Приложения
Многочисленные кодеки сигналов используют код Райса для остатков предсказания . В алгоритмах прогнозирования такие остатки имеют тенденцию попадать в двухстороннее геометрическое распределение , при этом небольшие остатки встречаются чаще, чем большие остатки, а код Райса близко приближается к коду Хаффмана для такого распределения без накладных расходов, связанных с необходимостью передачи таблицы Хаффмана. . Один сигнал, который не соответствует геометрическому распределению, представляет собой синусоидальную волну , потому что дифференциальные остатки создают синусоидальный сигнал, значения которого не создают геометрического распределения (наибольшее и наименьшее значения остатка имеют одинаковую высокую частоту появления, только медиана положительного и отрицательного реже встречаются остатки).
Некоторые аудиокодеки без потерь , такие как Shorten , [4] FLAC , [5] Apple Lossless и MPEG-4 ALS , используют код Райса после шага линейного предсказания (называемого «адаптивным FIR-фильтром» в Apple Lossless). Кодирование Райса также используется в кодеке изображений без потерь FELICS .
Кодер Голомба – Райса используется на этапе энтропийного кодирования кодеков изображений без потерь, основанных на алгоритме Райса . Один из таких экспериментов дает график степени сжатия, приведенный ниже. Смотрите другие записи в этой категории внизу этой страницы. При таком сжатии данные прогрессивной пространственной разницы дают чередующийся набор положительных и отрицательных значений около 0, которые преобразуются в только положительные целые числа (путем удвоения абсолютного значения и добавления единицы, если входной сигнал отрицательный), а затем Райса – Голомба кодирование применяется путем изменения делителя, который остается малым. [ необходима цитата ]
В этих результатах кодирование Райса может создавать очень длинные последовательности однобитов для частного; по практическим соображениям часто необходимо ограничить общую длину серии однобитовых, поэтому модифицированная версия кодирования Райса-Голомба состоит из замены длинной строки однобитовых кодировок путем кодирования ее длины рекурсивным кодом Райса-Голомба. кодирование; это требует резервирования некоторых значений в дополнение к начальному делителю k, чтобы обеспечить необходимое различие.
Схема JPEG-LS использует Райса – Голомба для кодирования остатков предсказания.
Упомянутая выше адаптивная версия кодирования Голомба-Райса (RLGR) длиной прогона используется для кодирования содержимого экрана в виртуальных машинах в компоненте RemoteFX протокола удаленного рабочего стола Microsoft.
Смотрите также
Рекомендации
- ^ Галлагер, RG; ван Вурхис, округ Колумбия (1975). «Оптимальные исходные коды для геометрически распределенных целочисленных алфавитов». IEEE Transactions по теории информации . 21 (2): 228–230. DOI : 10,1109 / tit.1975.1055357 .
- ^ Merhav, N .; Seroussi, G .; Вайнбергер, MJ (2000). «Кодирование источников с двусторонними геометрическими распределениями и неизвестными параметрами». IEEE Transactions по теории информации . 46 (1): 229–236. DOI : 10.1109 / 18.817520 .
- ^ Кили, А. (2004). Выбор параметра Голомба в кодировании риса (Технический отчет). Лаборатория реактивного движения . 42-159.
- ^ "человек укоротить" . Архивировано из оригинала на 2014-01-30 . Проверено 7 декабря 2008 .
- ^ Документация FLAC: обзор формата
дальнейшее чтение
- Голомб, Соломон В. (1966). Кодировки длин серий. IEEE Transactions по теории информации, IT - 12 (3): 399-401
- Райс, Роберт Ф .; Plaunt, R. (1971). «Адаптивное кодирование переменной длины для эффективного сжатия телевизионных данных космических аппаратов». Транзакции IEEE по коммуникациям . 16 (9): 889–897. DOI : 10.1109 / TCOM.1971.1090789 .
- Роберт Ф. Райс (1979), «Некоторые практические универсальные методы бесшумного кодирования», Лаборатория реактивного движения, Пасадена, Калифорния, JPL Publication 79-22, март 1979.
- Виттен, Ян Моффат, Алистер Белл, Тимоти. «Управление гигабайтами: сжатие и индексирование документов и изображений». Второе издание. Издательство Морган Кауфманн, Сан-Франциско, Калифорния. 1999 г. ISBN 1-55860-570-3
- Дэвид Саломон. "Сжатие данных", ISBN 0-387-95045-1 .
- HS Malvar, Адаптивное кодирование длин серий / Голомба-Райса квантованных обобщенных гауссовских источников с неизвестной статистикой , Proc. Конференция по сжатию данных, 2006 г.
- Энтропийное кодирование RLGR, открытая спецификация Microsoft MS-RDPRFX, кодек RemoteFX для протокола удаленного рабочего стола.
- С. Бюттчер, Кларк Кларк и Г.В. Кормак. Поиск информации: внедрение и оценка поисковых систем . MIT Press, Кембридж, Массачусетс, 2010.
Внешние ссылки
- веб-страница с коротко проработанным примером кодирования и декодирования Голомба.