Адаптивные модификации кода Голомба и их использование для сжатия изображений в космических экспериментах И.М.Книжный, 2009 г. Институт космических исследований РАН

Статический код Голомба (1) Бернуллиевский источник: p(0) = q p(1) =(1-q) Энтропия: H B = –(1–q)log 2 (1–q) – q log 2 q ___________________________ Геометрический источник с бесконечным алфавитом: p(i)=(1-q)q i. Средняя длина символа: 1=> a0a0a0a0 01=> a1a1a1a1 001=> a2a2a2a2 0001=> a3a3a3a => a4a4a4a => a5a5a5a Энтропия:

Критерий оптимальности Голомба: q l =1/2 Критерий Галлагера-Ван Вурхиса: q l + q l+1 1 < q l + q l-1 [ i/l ] – унарный код i \ l – кодируется по Хаффмену: пусть Тогда если r = i\l < m, то r кодируется [ log 2 l ] - битовым кодовым словом, иначе - [log 2 l]+1 -битовым. Средняя длина кодового слова при этом составляет 1=> a0a0a0a0 01=> a1a1a1a1 001=> a2a2a2a2 0001=> a3a3a3a => a4a4a4a => a5a5a5a5 ……….=>… 0000…1=> a l …0=> alalalal Статический код Голомба (2) Конечный набор «укрупнённых» символов: Более простой подход: если r < m, то в качестве кодового слова используются [log 2 l] младших бит r, иначе - [log 2 l]+1 младших бит числа (r+m).

Статический код Голомба (3) i [i/l] rКодовоесловоi rКодовое слово словоi [i/l] rКодовое слово слово Пример: q = 0.93 (H g = ) => l = 10. m = m =

Статический код Голомба (4) Избыточность статического кода Голомба как функция известной вероятности q: Пример (продолжение):

Статический код Голомба (5) Избыточность статического кода Голомба:

Адаптивный код Голомба (1) lql q ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ l –1/log 2 q q l + q l+1 1 < q l + q l-1 ln x x – 1 (] z [ - ближайшее целое к z), где δ

Адаптивный код Голомба (2) lqqlqq Граничные значения частоты q для l = 1÷17, соответствующие критерию Галлагера - Ван Вурхиса ( q ) и вычисленные по приближённой формуле с поправкой δ ( q ):

Адаптивный код Голомба (3) a i-1 a i-2 a i-3... a i-k+1 a i-k aiai k с(j) = ] 2 j (δ + ln ) [.kj c(j) то с учётом того, что если выбрать k таким образом, чтобы, где

Адаптивный код Голомба (4) Избыточность адаптивного кода Голомба для различных значений k (в предположении, что q – неизвестно, но остаётся постоянным): белая линия на графике – граница Галлагера-Ван Вурхиса (случай, соответствующий известному значению вероятности q).

Использование АКГ в предиктивных схемах сжатия изображений (1) Типичное изображение земной поверхности (КА аппарат Landsat 5, Большой Каньон, США) вместе с гистограммой яркости:

Использование АКГ в предиктивных схемах сжатия изображений (2) Распределение ошибки предсказания до (слева) и после (справа) ремаппинга

Использование АКГ в предиктивных схемах сжатия изображений (3) β (–1

Использование АКГ в предиктивных схемах сжатия изображений (4) k = 22 k = 11 k = 6 k = 3 хх х х Оценка параметра l по двумерному окружению из уже закодированных ошибок предсказания. На графиках - среднее число бит на пиксел сжатого изображения в зависимости от способа оценки l.

Использование АКГ в предиктивных схемах сжатия изображений (5) Размеры CALIC Huff. CALIC arithm. GAP- -Glm RAR 3.50 DaRT Размерность: пикселbpp LSTM16000x58803,80053,72093,76164,31903,7384 LSTM26000x58803,97103,90343,93084,57613,9033 LSTM46000x58803,73793,66623,68884,35783,6586 ADS13960х199203,49373,38043,44274,18703,4028 ADS23960х199203,21433,06683,12423,83273,0666 ADS33960х199203,60143,58893,54574,31163,5182 [MБ/с]:–3,611,513,813,203,59 Сравнение эффективности схем сжатия изображений ДЗЗ с использованием предиктора GAP и различных методов статистического кодирования. Кодек кодирования. Кодек GAP-Glm построен на основе CALIC заменой арифметического кодера адаптивным кодом Голомба (АКГ). Кодек DaRT использует модифицированный GAP и АКГ. Для сравнения приведены результаты сжатия с использованием архиватора WinRAR Лучшие результаты выделены жёлтым цветом.

Использование АКГ в предиктивных схемах сжатия изображений (6) Размеры изображения CALIC Huff. CALIC arithm. GAP- -Glm RAR 3.50DaRT Размерность:пикселbpp AIRFIELD 512x5125,58555,47485,54116,11544,9652 BRIDGE 512x5125,48235,37505,46264,47893,4734 COUPLE 512x5124,66544,59574,62525,40024,2082 HARBOUR 512x5124,52794,45834,48055,19764,4259 LENA 512x5124,17224,12074,12675,20884,0709 MAN 512x5124,41174,38514,39645,33964,3386 MANDRILL 512x5125,98045,89875,91326,55335,8906 PEPPERS 512x5124,27854,20914,28875,23914,1638 SAILBOAT 512x5124,74694,69454,73475,51674,6599 WOMAN1 512x5124,62184,55464,59855,46593,9605 WOMAN2512x5123,30953,20213,17404,04533,1389 [MБ/с]:–3,611,513,813,203,59 Сравнение эффективности схем сжатия на примере изображений из набора Old JPEG test set, не подвергавшихся искажающему сжатию:

Использование АКГ в схемах сжатия изображений на основе DCT (1) Распределение коэффициента DCT F 1,0 (белая линия) вместе с графиком аппроксимирующего экспоненциального распределения (красная линия):

Использование АКГ в схемах сжатия изображений на основе DCT (2) i \ j –0,03010,05160,08130,11720,17140,25510, ,03410,04590,06380,09060,12660,18030,26510, ,05510,06570,08070,10440,13890,19100,27540, ,08610,09530,10800,12860,15970,21080,29530, ,12500,13410,14630,16520,19470,24450,33280, ,18160,18970,20260,22110,25100,30460,39880, ,26440,27220,28800,30900,34180,40280,51320, ,39200,40440,42870,45640,49700,57420,71840,9694 Оценка для каждого коэффициента DCT 8x8 Fi,j изображения LSTM1:

Использование АКГ в схемах сжатия изображений на основе DCT (3) Гистограмма коэффициента DCT 8x8 F 2,3 (AC(3,2)) до и после квантования:

Использование АКГ в схемах сжатия изображений на основе DCT (4) Распределение длин серий нулевых коэффициентов DCT 8x8 в плоскостях AC(4,6) и AC(3,2) после операции квантования (изображение LSTM1):

Использование АКГ в схемах сжатия изображений на основе DCT (5) Quality:70 JPEG, Huff. static JPEG, Huff. opt JPEG arithmetic XGP-11pXGP-11XGP-11w Размерность: байт LSTM LSTM LSTM ADS ADS ADS Всего: % % % % % % % Сравнение результатов использования АКГ (кодек XGP) с различными способами оценки параметра l и JPEG (кодек Independent JPEG Group): JPEG Huff. static – неадаптивный код Хаффмена, JPEG Huff. opt – однопроходный динамический код Хаффмена, JPEG arithmetic – адаптивный арифметический кодер. XGP-11p, XGP-11 и XGP-11w – кодек XGP с оценкой параметра l соответственно по 11 точкам скользящего окна, двумерной области из 11 точек и с использованием набора весовых коэффициентов. Наилучшие результаты выделены жёлтым цветом.

Использование АКГ в схемах сжатия изображений на основе DCT (6) Quality:85 JPEG Huff. static JPEG Huff.opt. JPEG arithmetic XGP-11pXGP-11XGP-11w Размерность: байт LSTM LSTM LSTM ADS ADS ADS Всего: % % % % % % % МБайт/с: Сравнение результатов использования АКГ (кодек XGP) с различными способами оценки параметра l и JPEG (кодек Independent JPEG Group). Кодеки те же, что и на предыдущем слайде, но сжатие производилось с более высоким качеством (параметр качества = 85): В нижней строке таблицы – скорость кодирования при использовании соответствующего кодека.

Заключение и выводы Предлагаемый однопроходный адаптивный метод статистического сжатия на основе кода Голомба (АКГ) и его модификации отличаются малой вычислительной сложностью, эффективностью и высокой скоростью работы. В докладе показано, что их использование в предиктивных схемах сжатия изображений и в схемах с частотным преобразованием (на примере DCT) вместо арифметического кодирования обеспечивает в 2.5 раза более высокую скорость работы кодера при той же или большей степени сжатия изображений. Указанные качества позволяют сделать вывод о практической целесообразности применения АКГ при сжатии видеоданных с использованием бортовых вычислительных комплексов ограниченной технической оснащённости.

Использованные тестовые изображения (1) ADS1: ADS2: ADS3: Размер кадра 19920х3960 пикселов, 8 бит/пиксел, изображения получены при съемке авиационной цифровой камерой ADS-40 в окрестностях Берлина в августе 1999 г.

Использованные тестовые изображения (2) LSTM1: LSTM2 : LSTM4 : Изображения LSTM1, LSTM2, LSTM4 - спектральные каналы снимка Большого Каньона (США), полученного съемочной аппаратурой Thematic Mapper КА Landsat-5. Размер кадра 5880х6000 пикселов, 8 бит/пиксел.

Адаптивные модификации кода Голомба и их использование для сжатия изображений в космических экспериментах И.М.Книжный, 2009 г. Институт космических исследований РАН