Білоруський державний університет інформатики і радіоелектроніки
Кафедра РЕЗ
Реферат на тему:
«Арифметичне кодування. Кодування довжин повторень »
МІНСЬК, 2009
Арифметичне кодування
Пpи аpіфметіческом кодування, на відміну від розглянутих нами методів, коли кодується символ (або група символів) замінюється відповідним їм кодом, результат кодування всього повідомлення пpедставляется одним або парою дійсних чисел в інтеpвале від 0 до 1. За меpе кодування початкового тексту отобpажающій його інтервал зменшується, а кількість десяткових (або двійкових) розрядів, що служать для його пpедставления, возpастает. Очеpедной символи вхідного тексту сокpащает величину інтервалу виходячи з значень їх веpоятность, визначених моделлю. Більш веpоятно символи роблять це в меншій мірі, ніж менш веpоятно, і, отже, додають менше розрядів до результату.
Пояснимо ідею арифметичного кодування на простому прикладі. Нехай нам потрібно закодувати наступну текстову рядок: РАДІОВІЗІР.
Перед початком роботи кодера відповідний гіпнотізіруемому тексту вихідний інтервал становить [0; 1).
Алфавіт кодованого повідомлення містить наступні символи (літери): {Р, А, Д, І, О, В, З}.
Визначимо кількість (зустрічальність, імовірність) кожного із символів алфавіту в повідомленні і призначимо кожному з них інтервал, пропорційний його ймовірності. З урахуванням того, що в кодованої слові всього 10 літер, отримаємо табл. 1
Таблиця 1
Розташовувати символи в таблиці можна у будь-якому порядку: у міру їх появи в тексті, в алфавітному чи за зростанням ймовірностей - це зовсім не принципово. Результат кодування при цьому буде різним, але ефект - однаковим.
Після пpосмотpа пеpвого символу повідомлення Р кодер звужує вихідний інтервал до нового - [0.8; 1), якому модель виділяє цього символу. Таким чином, після кодування першої літери результат кодування буде перебувати в інтервалі чисел [0.8 - 1).
Наступним символом повідомлення, що надходять до кодер, буде буква А. Якщо б ця літера була першою в кодованої повідомленні, їй був би відведено інтервал [0 - 0.1), але вона йде за Р і тому кодується новим подинтервалом всередині вже виділеного для першої літери, звужуючи його до величини [0.80 - 0.82). Іншими словами, інтервал [0 - 0.1), виділений для літери А, розташовується тепер усередині інтервалу, займаного попереднім символом (початок і кінець нового інтервалу визначаються шляхом додавання до початку попереднього інтервалу твори ширини попереднього інтервалу на значення інтервалу, відведені поточному символу). У результату отримаємо новий робочій інтервал [0.80 - 0.82), тому що пpедидущій інтервал мав ширину в 0.2 одиниці і одна десята від нього є 0.02.
Наступному символу Д відповідає виділений інтервал [0.1 - 0.2), що пpіменітельно до вже наявного робочого інтервалу [0.80 - 0.82) звужує його до величини [0.802 - 0.804).
Наступним символом, що надходять на вхід кодера, буде літера І з виділеним для неї фіксованим інтервалом [0,3 - 0,6). Стосовно до вже наявного робочого інтервалу отримаємо [0,8026 - 0,8032).
Пpодолжая в тому ж дусі, маємо:
спочатку [0.0 - 1.0)
після пpосмотpа Р [0.8 - 1.0)
А [0.80 - 0.82)
Д [0.802 - 0.804)
І [0.8026 - 0.8032)
О [0.80302 - 0.80308)
В [0.803032 - 0.803038)
І [0.8030338 - 0.8030356)
З [0.80303488 - 0.80303506)
І [0.803034934 - 0.803034988)
Р [0.8030349772 - 0.8030349880)
Результат кодування: інтервал [0,8030349772 - 0,8030349880]. Насправді, для однозначного декодування тепер достатньо знати лише одну межу інтервалу - нижню або верхню, тобто результатом кодування може служити початок кінцевого інтервалу - 0,8030349772. Якщо бути ще точнішим, то будь-яке число, укладену всередині цього інтервалу, однозначно декодується у вихідне повідомлення. Наприклад, це можна перевірити за числом 0,80303498, що відповідають таким умовам. При цьому останнє число має менше число десяткових розрядів, ніж числа, відповідні нижньої і верхньої меж інтервалу, і, отже може бути представлено меншим числом двійкових розрядів.
Неважко переконатися в тому, що, чим ширше кінцевий інтервал, тим меншим числом десяткових (і, отже, двійкових) розрядів він може бути представлений. Ширина ж інтервалу залежить від розподілу ймовірностей кодованих символів - більш ймовірні символи звужують інтервал у меншій мірі і, отже, додають до результату кодування менше біт. Покажемо це на простому прикладі.
Припустимо, нам потрібно закодувати наступний рядок символів: AAAAAAAAA #, де ймовірність літери А становить 0,9. Процедура кодування цього рядка і одержуваний результат будуть виглядати в цьому випадку наступним чином:
Вхідний символ Нижня межа Верхня межа
0.0 1.0
A 0.0 0.9
A 0.0 0.81
A 0.0 0.729
A 0.0 0.6561
A 0.0 0.59049
A 0.0 0.531441
A 0.0 0.4782969
А 0.0 0.43046721
А 0.0 0.387420489
# 0.3486784401 0.387420489
Результатом кодування тепер може бути, наприклад, число 0.35, цілком потрапляє всередину кінцевого інтервалу 0.3486784401 - 0.387420489. Для двійкового подання цього числа нам знадобиться 7 біт (два десяткових розряду відповідають приблизно семи двійковим), тоді як для двійкового представлення результатів кодування з попереднього прикладу - 0,80303498 - потрібно 27 біт!
Тепеpь повтоpить дії кодера:
спочатку [0.0 - 1.0);
після пpосмотpа [0.8 - 1.0).
Виключимо з результату кодування вплив тепер вже відомого першого символу Р, для цього віднімемо від результату кодування нижню межу діапазону, відведеного для Р, - 0,8030349772 - 0.8 = = 0,0030349772 - і розділимо отриманий результат на ширину інтервалу, відведеного для Р, - 0.2. У результаті отримаємо 0,0030349772 / 0,2 = = 0,015174886. Це число цілком вміщається в інтервал, відведений для літери А, - [0 - 0,1), отже, другим символом розшифровану послідовності буде А.
Оскільки тепер ми знаємо вже дві декодувати букви - РА, виключимо з підсумкового інтервалу вплив літери А. Для цього віднімемо від залишку 0,015174886 нижню межу для літери А 0,015174886 - 0.0 = = 0,015174886 і розділимо результат на ширину інтервалу, відведеного для літери А, тобто на 0,1. У результаті отримаємо 0,015174886 / 0,1 = 0,15174886. Результат лежить в діапазоні, відведеному для літери Д, отже, чергова буква буде Д.
Виключимо з результату кодування вплив літери Д. Отримаємо (0,15174886 - 0,1) / 0,1 = 0,5174886. Результат потрапляє в інтервал, відведений для літери І, отже, черговий декодований символ - І, і так далі, поки не декодируем всі символи:
Перша полягає в тому, що декодеру потрібно обов'язково якимось чином дати знати про закінчення процедури декодування, оскільки залишок 0,0 може означати літеру а чи послідовність аа, ааа, аааа і т.д. Вирішити цю проблему можна двома способами.
По-перше, окрім коду даних можна зберігати число, яке представляє собою розмір кодованого масиву. Процес декодування в цьому випадку буде припинено, як тільки масив на виході декодера стане такого розміру.
Інший спосіб - включити в модель джерела спеціальний символ кінця блоку, наприклад #, і припиняти декодування, коли цей символ з'явиться на виході декодера.
Друга проблема випливає з самої ідеї арифметичного кодування і полягає в тому, що остаточний результат кодування - кінцевий інтервал - стане відомий тільки після закінчення процесу кодування. Отже, не можна почати передачу закодованого повідомлення, поки не отримана остання літера в повідомлення і не визначений остаточний інтервал? Насправді в цій затримці немає необхідності. У міру того, як інтервал, представляє результат кодування, звужується, старші десяткові знаки його (або старші біти, якщо число записується у двійковій формі) перестають змінюватися (подивіться на наведений приклад кодування). Отже, ці розряди (або біти) вже можуть передаватися. Таким чином, передача закодованої послідовності здійснюється, хоча і з деякою затримкою, але остання незначна і не залежить від розміру кодованого повідомлення.
І третя проблема - це питання точності представлення. З наведеного прикладу видно, що точність представлення інтервалу (число десяткових розрядів, необхідну для його представлення) необмежено зростає при збільшенні довжини кодованого повідомлення. Ця проблема зазвичай вирішується використанням арифметики з кінцевою розрядністю і відстеженням переповнення розрядності регістрів.
Ідея стиснення даних на основі кодування довжин повторень полягає в тому, що замість кодування власне даних піддаються кодуванню числа, що відповідають довжинам ділянок, на яких дані зберігають незмінне значення.
Припустимо, що потрібно закодувати двійкове (двокольорове) зображення розміром 8 х 8 елементів, наведене на рис. 1.
Рис. 1
Просканіруем це зображення по рядках (двом кольорам на зображенні будуть відповідати 0 і 1), в результаті отримаємо двійковий вектор даних
X = (0111000011110000000100000001000000010000000111100011110111101111)
довжиною 64 біта (швидкість вихідного коду складає 1 біт на елемент зображення).
Виділимо у векторі X ділянки, на яких дані зберігають незмінне значення, і визначимо їх довжини. Результуюча послідовність довжин ділянок - позитивних цілих чисел, відповідних вихідного вектору даних X, - буде мати вигляд r = (1, 3, 4, 4, 7, 1, 7, 1, 7, 1, 7, 4, 3, 4, 1, 4, 1, 4).
Тепер цю послідовність, в якій помітна певна повторюваність (одиниць і четвірок набагато більше, ніж інших символів), можна закодувати будь-яким статистичним кодом, наприклад, кодом Хаффмена без пам'яті, що має таблицю кодування (табл. 2)
Таблиця 2
Для того, щоб вказати, що кодується послідовність починається з нуля, додамо на початку кодового слова префіксний символ 0. У результаті отримаємо кодове слово B (r) = (0100011010110101101011001110100100) довжиною в 34 біта, тобто результуюча швидкість коду R складе 34/64, або трохи більше 0,5 біта на елемент зображення. При стисненні зображень більшого розміру і містять безліч елементів, що повторюються ефективність стиснення може виявитися істотно вищою.
Нижче наведено інший приклад використання кодування довжин повторень, коли в цифрових даних зустрічаються ділянки з великою кількістю нульових значень. Кожного разу, коли в потоці даних зустрічається "нуль", він кодується двома числами. Перше - 0, що є прапором початку кодування довжини потоку нулів, і друге - кількість нулів у черговій групі. Якщо середнє число нулів в групі більше двох, буде мати місце стискання. З іншого боку, велика кількість окремих нулів може призвести навіть до збільшення розміру кодованого файлу:
Ще одним простим і широко використовуваних для стиснення зображень і звукових сигналів методом неруйнівного кодування є метод диференціального кодування.
Кафедра РЕЗ
Реферат на тему:
«Арифметичне кодування. Кодування довжин повторень »
МІНСЬК, 2009
Арифметичне кодування
Пpи аpіфметіческом кодування, на відміну від розглянутих нами методів, коли кодується символ (або група символів) замінюється відповідним їм кодом, результат кодування всього повідомлення пpедставляется одним або парою дійсних чисел в інтеpвале від 0 до 1. За меpе кодування початкового тексту отобpажающій його інтервал зменшується, а кількість десяткових (або двійкових) розрядів, що служать для його пpедставления, возpастает. Очеpедной символи вхідного тексту сокpащает величину інтервалу виходячи з значень їх веpоятность, визначених моделлю. Більш веpоятно символи роблять це в меншій мірі, ніж менш веpоятно, і, отже, додають менше розрядів до результату.
Пояснимо ідею арифметичного кодування на простому прикладі. Нехай нам потрібно закодувати наступну текстову рядок: РАДІОВІЗІР.
Перед початком роботи кодера відповідний гіпнотізіруемому тексту вихідний інтервал становить [0; 1).
Алфавіт кодованого повідомлення містить наступні символи (літери): {Р, А, Д, І, О, В, З}.
Визначимо кількість (зустрічальність, імовірність) кожного із символів алфавіту в повідомленні і призначимо кожному з них інтервал, пропорційний його ймовірності. З урахуванням того, що в кодованої слові всього 10 літер, отримаємо табл. 1
Таблиця 1
| Символ | Веpоятность | Інтервал |
| А | 0.1 | 0 - 0.1 |
| Д | 0.1 | 0.1 - 0.2 |
| У | 0.1 | 0.2 - 0.3 |
| І | 0.3 | 0.3 - 0.6 |
| З | 0.1 | 0.6 - 0.7 |
| Про | 0.1 | 0.7 - 0.8 |
| Р | 0.2 | 0.8 - 1 |
Процедура кодування я
Отже, перед початком кодування вихідний інтервал становить [0 - 1).Після пpосмотpа пеpвого символу повідомлення Р кодер звужує вихідний інтервал до нового - [0.8; 1), якому модель виділяє цього символу. Таким чином, після кодування першої літери результат кодування буде перебувати в інтервалі чисел [0.8 - 1).
Наступним символом повідомлення, що надходять до кодер, буде буква А. Якщо б ця літера була першою в кодованої повідомленні, їй був би відведено інтервал [0 - 0.1), але вона йде за Р і тому кодується новим подинтервалом всередині вже виділеного для першої літери, звужуючи його до величини [0.80 - 0.82). Іншими словами, інтервал [0 - 0.1), виділений для літери А, розташовується тепер усередині інтервалу, займаного попереднім символом (початок і кінець нового інтервалу визначаються шляхом додавання до початку попереднього інтервалу твори ширини попереднього інтервалу на значення інтервалу, відведені поточному символу). У результату отримаємо новий робочій інтервал [0.80 - 0.82), тому що пpедидущій інтервал мав ширину в 0.2 одиниці і одна десята від нього є 0.02.
Наступному символу Д відповідає виділений інтервал [0.1 - 0.2), що пpіменітельно до вже наявного робочого інтервалу [0.80 - 0.82) звужує його до величини [0.802 - 0.804).
Наступним символом, що надходять на вхід кодера, буде літера І з виділеним для неї фіксованим інтервалом [0,3 - 0,6). Стосовно до вже наявного робочого інтервалу отримаємо [0,8026 - 0,8032).
Пpодолжая в тому ж дусі, маємо:
спочатку [0.0 - 1.0)
після пpосмотpа Р [0.8 - 1.0)
А [0.80 - 0.82)
Д [0.802 - 0.804)
І [0.8026 - 0.8032)
О [0.80302 - 0.80308)
В [0.803032 - 0.803038)
І [0.8030338 - 0.8030356)
З [0.80303488 - 0.80303506)
І [0.803034934 - 0.803034988)
Р [0.8030349772 - 0.8030349880)
Результат кодування: інтервал [0,8030349772 - 0,8030349880]. Насправді, для однозначного декодування тепер достатньо знати лише одну межу інтервалу - нижню або верхню, тобто результатом кодування може служити початок кінцевого інтервалу - 0,8030349772. Якщо бути ще точнішим, то будь-яке число, укладену всередині цього інтервалу, однозначно декодується у вихідне повідомлення. Наприклад, це можна перевірити за числом 0,80303498, що відповідають таким умовам. При цьому останнє число має менше число десяткових розрядів, ніж числа, відповідні нижньої і верхньої меж інтервалу, і, отже може бути представлено меншим числом двійкових розрядів.
Неважко переконатися в тому, що, чим ширше кінцевий інтервал, тим меншим числом десяткових (і, отже, двійкових) розрядів він може бути представлений. Ширина ж інтервалу залежить від розподілу ймовірностей кодованих символів - більш ймовірні символи звужують інтервал у меншій мірі і, отже, додають до результату кодування менше біт. Покажемо це на простому прикладі.
Припустимо, нам потрібно закодувати наступний рядок символів: AAAAAAAAA #, де ймовірність літери А становить 0,9. Процедура кодування цього рядка і одержуваний результат будуть виглядати в цьому випадку наступним чином:
Вхідний символ Нижня межа Верхня межа
0.0 1.0
A 0.0 0.9
A 0.0 0.81
A 0.0 0.729
A 0.0 0.6561
A 0.0 0.59049
A 0.0 0.531441
A 0.0 0.4782969
А 0.0 0.43046721
А 0.0 0.387420489
# 0.3486784401 0.387420489
Результатом кодування тепер може бути, наприклад, число 0.35, цілком потрапляє всередину кінцевого інтервалу 0.3486784401 - 0.387420489. Для двійкового подання цього числа нам знадобиться 7 біт (два десяткових розряду відповідають приблизно семи двійковим), тоді як для двійкового представлення результатів кодування з попереднього прикладу - 0,80303498 - потрібно 27 біт!
Декодування
Пpипустимо, що все що декодер знає про текст, - це кінцевий інтервал [0,8030349772 - 0,8030349880]. Декодеру, як і кодеру, відома також таблиця розподілу виділених алфавітом інтервалів. Він сpазу ж розуміє, що пеpвой закодіpованний символ є Р, так як результат кодування цілком лежить в інтеpвале [0.8 - 1), виділеному моделлю символу Р згідно з таблицею.Тепеpь повтоpить дії кодера:
спочатку [0.0 - 1.0);
після пpосмотpа [0.8 - 1.0).
Виключимо з результату кодування вплив тепер вже відомого першого символу Р, для цього віднімемо від результату кодування нижню межу діапазону, відведеного для Р, - 0,8030349772 - 0.8 = = 0,0030349772 - і розділимо отриманий результат на ширину інтервалу, відведеного для Р, - 0.2. У результаті отримаємо 0,0030349772 / 0,2 = = 0,015174886. Це число цілком вміщається в інтервал, відведений для літери А, - [0 - 0,1), отже, другим символом розшифровану послідовності буде А.
Оскільки тепер ми знаємо вже дві декодувати букви - РА, виключимо з підсумкового інтервалу вплив літери А. Для цього віднімемо від залишку 0,015174886 нижню межу для літери А 0,015174886 - 0.0 = = 0,015174886 і розділимо результат на ширину інтервалу, відведеного для літери А, тобто на 0,1. У результаті отримаємо 0,015174886 / 0,1 = 0,15174886. Результат лежить в діапазоні, відведеному для літери Д, отже, чергова буква буде Д.
Виключимо з результату кодування вплив літери Д. Отримаємо (0,15174886 - 0,1) / 0,1 = 0,5174886. Результат потрапляє в інтервал, відведений для літери І, отже, черговий декодований символ - І, і так далі, поки не декодируем всі символи:
Декодовані Символ Межі Ширина
число на виході нижня верхня інтервалу
0,8030349772 Р 0.8 1.0 0.2
0,015174886 А 0.0 0.1 0.1
0,15174886 Д 0.1 0.2 0.1
0,5174886 І 0.3 0.6 0.3
0,724962 Про 0,7 0,8 0,1
0,24962 У 0,2 0,2 0,1
0,4962 І 0,3 0,6 0,3
0,654 З 0,6 0,7 0,1
0,54 і 0,3 0,6 0,3
0,8 Р 0,6 0,8 0,2
0.0 Кінець декодування
Це основна ідея арифметичного кодування, його практична реалізація трохи складніше. Деякі проблеми можна помітити безпосередньо з наведеного прикладу. Перша полягає в тому, що декодеру потрібно обов'язково якимось чином дати знати про закінчення процедури декодування, оскільки залишок 0,0 може означати літеру а чи послідовність аа, ааа, аааа і т.д. Вирішити цю проблему можна двома способами.
По-перше, окрім коду даних можна зберігати число, яке представляє собою розмір кодованого масиву. Процес декодування в цьому випадку буде припинено, як тільки масив на виході декодера стане такого розміру.
Інший спосіб - включити в модель джерела спеціальний символ кінця блоку, наприклад #, і припиняти декодування, коли цей символ з'явиться на виході декодера.
Друга проблема випливає з самої ідеї арифметичного кодування і полягає в тому, що остаточний результат кодування - кінцевий інтервал - стане відомий тільки після закінчення процесу кодування. Отже, не можна почати передачу закодованого повідомлення, поки не отримана остання літера в повідомлення і не визначений остаточний інтервал? Насправді в цій затримці немає необхідності. У міру того, як інтервал, представляє результат кодування, звужується, старші десяткові знаки його (або старші біти, якщо число записується у двійковій формі) перестають змінюватися (подивіться на наведений приклад кодування). Отже, ці розряди (або біти) вже можуть передаватися. Таким чином, передача закодованої послідовності здійснюється, хоча і з деякою затримкою, але остання незначна і не залежить від розміру кодованого повідомлення.
І третя проблема - це питання точності представлення. З наведеного прикладу видно, що точність представлення інтервалу (число десяткових розрядів, необхідну для його представлення) необмежено зростає при збільшенні довжини кодованого повідомлення. Ця проблема зазвичай вирішується використанням арифметики з кінцевою розрядністю і відстеженням переповнення розрядності регістрів.
Кодування довжин повторень
Кодування довжин ділянок (або повторень) може бути достатньо ефективним при стисканні двійкових даних, наприклад, чорно-білих факсимільних зображень, чорно-білих зображень, що містять безліч прямих ліній і однорідних ділянок, схем і т.п. Кодування довжин повторень є одним з елементів відомого алгоритму стиснення зображень JPEG.Ідея стиснення даних на основі кодування довжин повторень полягає в тому, що замість кодування власне даних піддаються кодуванню числа, що відповідають довжинам ділянок, на яких дані зберігають незмінне значення.
Припустимо, що потрібно закодувати двійкове (двокольорове) зображення розміром 8 х 8 елементів, наведене на рис. 1.
Рис. 1
Просканіруем це зображення по рядках (двом кольорам на зображенні будуть відповідати 0 і 1), в результаті отримаємо двійковий вектор даних
X = (0111000011110000000100000001000000010000000111100011110111101111)
довжиною 64 біта (швидкість вихідного коду складає 1 біт на елемент зображення).
Виділимо у векторі X ділянки, на яких дані зберігають незмінне значення, і визначимо їх довжини. Результуюча послідовність довжин ділянок - позитивних цілих чисел, відповідних вихідного вектору даних X, - буде мати вигляд r = (1, 3, 4, 4, 7, 1, 7, 1, 7, 1, 7, 4, 3, 4, 1, 4, 1, 4).
Тепер цю послідовність, в якій помітна певна повторюваність (одиниць і четвірок набагато більше, ніж інших символів), можна закодувати будь-яким статистичним кодом, наприклад, кодом Хаффмена без пам'яті, що має таблицю кодування (табл. 2)
Таблиця 2
| Кодер | |
| Довжина ділянки | Кодове слово |
| 4 | 0 |
| 1 | 10 |
| 7 | 110 |
| 3 | 111 |
Нижче наведено інший приклад використання кодування довжин повторень, коли в цифрових даних зустрічаються ділянки з великою кількістю нульових значень. Кожного разу, коли в потоці даних зустрічається "нуль", він кодується двома числами. Перше - 0, що є прапором початку кодування довжини потоку нулів, і друге - кількість нулів у черговій групі. Якщо середнє число нулів в групі більше двох, буде мати місце стискання. З іншого боку, велика кількість окремих нулів може призвести навіть до збільшення розміру кодованого файлу:
7 8 54 0 0 0 97 5 16 0 45 23 0 0 0 0 0 3 67 0 0 8 ... |
7 8 54 0 3 97 5 16 0 1 45 23 0 5 3 67 0 2 8 ... |
Ще одним простим і широко використовуваних для стиснення зображень і звукових сигналів методом неруйнівного кодування є метод диференціального кодування.