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

На відміну від розглянутих раніше нерівномірних кодів, арифметичне кодування створює неблоковие коди. В арифметичному кодуванні, історія якого може бути простежена аж до робот Елайеса, не існує однозначної відповідності між символами джерела і кодовими словами. Замість цього, вся послідовність символів джерела (тобто всі повідомлення) співвіднесена з одним арифметичним кодовим словом. Саме по собі кодове слово задає інтервал дійсних чисел між 0 і 1. Зі збільшенням числа символів в повідомленні, інтервал, необхідний для їх подання, зменшується, а число одиниць інформації (скажімо, бітів), необхідних для представлення інтервалу, збільшується. Кожен символ в повідомленні зменшує розмір інтервалу в відності з ймовірністю своєї появи. Оскільки метод не вимагає, як, наприклад, підхід Хаффмана, щоб кожен вихідний символ відображався в ціле число кодових слів (тобто щоб символи кодировались по одному), він досягає (у теорії) кордону, поставлений теоремою кодування без шуму (див. Розділ 1.3.3).

На Рис. 8.13 проілюстрований основний процес арифметичного кодування. Тут кодується повідомлення з п'яти символів, утворене чотирьохсимвольним джерелом: . На початку процесу кодування передбачається, що повідомлення займає весь напіввідкритий інтервал [0, 1). Цей інтервал спочатку ділиться на чотири відрізка пропорційно ймовірностям символів джерела, які наведені в Таблиці 1.6. Символу , наприклад, відповідає подінтервал [0, 0,2). Оскільки це перший символ кодованого повідомлення, то значить, інтервал частини повідомлення () буде звужений до [0, 0,2). На Рис. 1.13 отриманий інтервал розтягнутий на повну висоту малюнка, і наведені значення на його кінцях відповідають значенням вузького діапазону. Потім вузький діапазон також ділиться на відрізки, пропорційно ймовірностям символів джерела, і процес повторюється з наступним символом повідомлення. Таким чином, символ звузить подінтервал до [0,04, 0,08), - до [0,056, 0,072) і т.д. Останній символ повідомлення, який повинен бути зарезервований для спеціального індикатора закінчення повідомлення, звужує діапазон до [0,06752, 0,0688). Звичайно, будь-яке число в цьому підінтервалі - наприклад, 0,068 - може бути використано для подання повідомлення.

Рис. 1.13. Процедура арифметичного кодування

Таблиця 1.6. Приклад арифметичного кодування.

Повідомлення з п'яти символів, наведене на Рис. 1.13, після арифметичного кодування вимагає для запису всього трьох десяткових цифр. Це відповідає 3/5 або 0,6 десяткових знаків на символ джерела і вельми близько ентропії джерела, яка, со гласно (8.3-3), становить 0,58 десяткових знаків (десяткових одиниць) на символ. При збільшенні довжини кодованого послідовності, результуючий арифметичний код наближається до межі, поставленою теоремою кодування без шуму. На практиці два фактора заважають кодовим характеристикам наблизитися до даної границі впритул: (1) необхідність включення деякого символу закінчення, що дозволяє відокремлювати одну кодову послідовнність від іншої, і (2) використання арифметики кінцевої точності. Для подолання останньої проблеми, при практичній реалізації арифметичного кодування застосовуються стратегії масштабування і округлення. Згідно стратегії масштабування, кожен подінтервал перед розбиттям його на відрізки, пропорційні ймовірностям символів, розтягується до діапазону [0, 1). Стратегія округлення гарантує, що обмеження, пов'язані з кінцевою точністю обчислень, не перешкоджають точному поданню кодових підінтервалів.

LZW кодування

Розглянувши основні методи скорочення кодової надмірності, перейдемо до розгляду одного з декількох методів стиснення без втрат, який також спрямований на скорочення міжелементних надлишковості зображення. Метод, званий методом кодування Лемпеля-Зіва-Уелша, відображає послідовність символів джерела різної довжини на рівномірний код, причому не вимагає апріорного знання ймовірностей появи кодуємих символів. Згадаймо з Розділу 1.3.3 твердженням першої теореми Шеннона про те, що n -кратне розширення джерела без памя’ті може бути кодоване з меншим середнім числом бітів на символ джерела, ніж сам нерозширення джерело. Незважаючи на той факт, що метод LZW -стиснення повинен бути ліцензований згідно патентом США № 4,558,302, він інтегрований в багато широко викорисвуємих файлових форматах зображень, включаючи GIF (graphic interchange format), TIFF (tagged image file format) а також PDF (portable document format).

Концептуально LZW-кодування є дуже простим. При запуску процесу кодування будується початок кодової книги або «словник», що містить лише кодовані символи джерела. Для 8-бітового монохромного зображення словник має розміри в 256 слів і відображає значення яркостей 0, 1,2,..., 255. Кодер послідовно аналізує символи джерела (тобто значення пікселів), і при появі відсутньої в словнику серії, вона поміщається у визначувану алгоритмом (наступну вільну) місце словника. Якщо перші два пікселя зображення, наприклад, були білими (255-255), ця серія може бути приписана позиції 256, яка є наступною вільною після зарезервованих для рівнів яркостей позицій з 0 по 255. Наступного разу, коли зустрінеться серія з двох білих пікселів, для їх подання буде використовуватися кодове слово 256, як адресу позиції, що містить серію 255-255. У разі 9-бітового словника, що містить 512 кодових слів, вихідні 8+8 = 16 бітів, необхідні для подання двох пікселів, будуть замінені одним 9-бітовим кодовим словом. Ясно, що допустимі розмір словника є найважливішим параметром. Якщо він занадто малий, то виявлення співпадаючих серій яркостей буде малоймовірна; якщо занадто великий, то розмір кодового слова буде погіршувати характеристики стиснення.

Приклад 1.12. Приклад LZW-кодування.

Розглянемо наступне 8-бітове зображення розмірами 4 4, що має вертикальний контур:

39 39 126 126

39 39 126 126

39 39 126 126

39 39 126 126

У Таблиці 1.12 описуються кроки, використовувані при кодуванні його 16 пікселів. Підготовляється словник на 512 кодових слів:

У початковий момент позиції з 256 по 511 ще не використовуються.

При кодуванні пікселі зображення обробляються зліва направо і зверху вниз. Здійснюється катенація (приєднання) кожго наступного значення яскравості з наявною на даний момент серії, названої «розпізнана серія», яка наведена в позиції 1 Таблиці 1.7. Як можна побачити, спочатку ця змінна обнулена або порожня. Словник проглядається на виявлення збігу з кожною черговою серією, і якщо така виявляється, що і вімічено в першому рядку таблиці, то серія заміниться кодом (номером позиції) збігається і розпізнаної (тобто наявною в словнику) серії, що відзначено в першій колонці другого рядка. При цьому, ще не створює ніякого коду і не відбувається поновлення словника. Якщо ж співпадання серії і словника не виявляється (що зазначено у другому рядку таблиці), то номер позиції розпізнаної до теперішнього моменту серії (39) подається на вихід в якості чергового коду; ця нерозпізнана серія поповнює словник, а стан розпізнаної серії ініціюється останнім надійшовшим символом. Останні дві колонки таблиці описують коди і серії яркостей, які послідовно додаються до словника при кодуванні всього зображення розмірами 4 4 елемента. Додається дев'ять додаткових кодових слів. По завершенні кодування словник має 265 кодових слів; при цьому LZW алгоритм успішно виявив кілька повторюваних серій яркостей, що дозволило йому зменшити вихідне 128-бітове зображення до 90-бітового зображення (тобто до 10 кодів з 9 бітів). Кодова послідовність на виході створює при читанні третьої колонки (Вихід кодера) зверху вниз. Результуючий коефіцієнт стиснення дорівнює 1,42:1.

Таблиця 1.7. Приклад LZW-кодування.

Унікальним якістю тільки що продемонстрованого LZW кодування є те, що кодова книга (словник) створюється в процесі кодування даних. Примітно, що LZW-декодер будує ідентичний словник відновлення, якщо він декодує потік даних синхронно з кодером. Користувачеві пропонується в якості вправи (див. Завдання 1.16) декодувати вихід, отриманий в попередньому прикладі, і відновити кодову книгу. Хоча в даному прикладі це і не потрібно, тим не менше, більшість практичних додатків передбачають стратегію дій при переповнення словника. Простим рішенням є очищення, або ініціалізація, словника при його заповненні, і потім продовження кодування з чистим словником. Більш складним варіантом може бути стеження за характеристиками стиснення та очищення словника, якщо він стає недоступний або робота сповільнюється. В якості альтернативи можна простежувати і тимчасово видаляти найменш часто використовуємі входи словника, і відновлювати їх, якщо буде потрібно.

Поиск по сайту: