Стиснення зображень

Друга теорема Шеннона [Shаппоп, 1948], також називається теоремою кодування для каналу з шумом, підтверджує наступне. Для будь-якого , де C є пропускна здатність каналу без пам'яті, існує код довжини r, де r-ціле, має швидкість R, таку, що ймовірність помилки блокового декодування не перевищує будь-якого наперед заданого з інтервалом . Таким чином, імовірність помилки можна зробити як завгодно малою, за умови, що швидкість кодових повідомлень менше або дорівнює пропускної здатності каналу.

Теорема кодування джерела (про взаємозв'язок швидкості і спотворення)

Теореми, розглянуті до справжнього моменту, встановлюють фундаментальні межі безпомилкової зв'язку як по надійним, так і по ненадійним каналам. У даному розділі ми повернемося до випадку каналу без помилок, але в цілому процес передачі інформації може бути не точним. Головним завданням системи зв'язку в такий послідовності є «стиснення інформації», можливо, за рахунок деякого її спотворення. У більшості випадків середня помилка, яку вносить стисненням, обмежується деякими максимально допустимим рівнем D. Ми хочемо знайти найменшу допустиму швидкість як функцію заданого критерію точності, при якій інформація може бути передана від джерела до одержувача. Вирішенням цієї конкретної проблеми займається розділ теорії інформації, називається теорія взаємозв'язку швидкості та спотворення.

Нехай джерело інформації і вихід декодера на Рис. 1.9 визначені кінцевими ансамблями (А, z) і (В, z) відповідно. Припускається, що канал на Рис. 1.9 є каналом без помилок, так що матриця каналу Q, Яка пов'язує z з v згідно (1.3-6), може розглядатися як визначальна тільки сам процес кодування-декодування. Оскільки процес кодування-декодування є детермінованим, описує деякий ідеальний канал без пам'яті, що імітує ефект стиснення і відновлення інформації. Всякий раз, коли джерело породжує вихідний символ , останній представляється деяким кодовою символом, який в результаті декодується у вихідний символ з імовірністю (див. Розділ 1.3.2).

Постановка задачі кодування джерела, при якій середня величина спотворення не повинна перевищувати рівня D вимагає методу кількісної оцінки величини спотворення для будь-якого виходу джерела. Для простого випадку нерозширення джерела може бути використана ненегативна функція вартості, називається мірою спотворення, визначальна величину «штрафу», виникає у випадку, коли вихід джерела відтворюється на виході декодера . Вихід джерела є випадковою величиною, тому спотворення також є випадковою величиною, середнє значення якої дорівнює

Запис підкреслює, що середнє спотворення є функція процедури кодування-декодування, яка (як уже зазначалося раніше) моделюється матрицею каналу . Конкретна процедура кодування-декодування називається D-точною тоді і тільки тоді , коли середнє спотворення менше або дорівнює D. Таким чином, набір D-точних процедур кодування-декодування може бути записаний у вигляді

Оскільки кожна процедура кодування-декодування визначається матрицею каналу Q, то середня інформація, що отримується при спостереженні одиничного виходу декодера, може бути порахована відповідно (1.3-12). Отже, ми можемо визначити найменшу допустиму швидкість як функцію спотворення виразом

тобто як мінімальне значення (1.3-12) на множині всіх D-точних кодів. Зауважимо, що залежить від значень ймовірностей в векторі z і елементів матриці Q, а мінімум в правій частині (1.3-25) береться по Q. Якщо D = 0, то менше або дорівнює ентропії джерела, тобто .

Рівняння (1.3-25) визначає мінімально можливу швидкість як функцію спотворення, при якій інформація від джерела може бути доставлена ??одержувачу за умови, що середнє спотворення менше або дорівнює D. Щоб обчислити цю швидкість, тобто , ротрібно мінімізувати значення , що задається (1.3-12), шляхом вибору підходящої матриці Q (або ) за умови виконання наступних обмежень

,

і

Формули (1.3-26) і (1.3-27) виражають основні властивості матриці каналу : її елементи повинні бути невід'ємними і, оскільки будь-якому вхідному символу повинен відповідати якийсь вихід, сума елементів по будь-якому стовпцю матриці повинна бути рівна 1. Рівняння (1.3-28) показує, що мінімальна швидкість досягається при максимально допустимому спотворенні. Приклад 1.9. Обчислення швидкості як функції спотворення для двійкового джерела без пам'яті.

Розглянемо двійковий джерело без пам'яті з рівноімовірними символами джерела {0, 1} і простою мірою спотворення

де - одинична дельта-функція. Оскільки якщо і 0 в інших випадках, то кожна помилка кодування-декодування вважається за одну одиницю спотворення. Для знаходження може бути використано варіаційне числення, а саме метод Лагранжа знаходження умовного екстремуму. Розглянемо функцію Лагранжа

яка додатково залежить від множників Лагранжа , , ...,. Прирівняємо її похідні по змінним до нуля (тобто = 0), і вирішимо систему, що складається з отриманих рівнянь разом з рівняннями зв'язків (1.3-27) і (1.3-28), для невідомих і , , ...,. Якщо отримані значення не негативні, тобто задовольняють (1.3-26), це означає, що знайдено вірне рішення. Для певної вище пари джерела і спотворення, отримаємо наступні 7 рівнянь (з 7-ма невідомими)

Послідовність алгебраїчних перетворень приводить до наступних результатів:

так що

Оскільки було задано, що символи джерела рівноймовірно, то максимальне можливе спотворення дорівнює 1/2. Таким чином і елементи матриці Q відповідають (1.3-12) для всіх D.

Взаємна інформація, пов'язана з Q і раніше визначеним двійковим джерелом, обчислюється з використанням (1.3-12). Відповідно помітив схожість матриці Q і матриці двійкового симетричного каналу, можна відразу написати:

.

Це випливає з результату Прикладу 1.6 при підстановці = 1/2 і в вираз . Швидкість як функція спотворення може бути отримана прямо з (1.3-25)

.

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

Для простих джерел і заходів спотворення, швидкість як функція спотворення може бути обчислена аналітично, як і в попередньому прикладі. Більше того, коли аналітичні методи не працюють, то можуть використовуватися сходяться ітеративні алгоритми, зручні для чисельної реалізації на комп'ютерах.

Рис. 1.10 Швидкість як функція спотворення для двійкового симетричного джерела

Після того, як обчислили на , теорема кодування джерела стверджує, що для будь-якого існує такий код довжини r і швидкості , що середнє спотворення на символ задовольняє умові . Важливий практичний наслідок даної теореми і теореми кодування для каналу з шумом полягає в тому, що вихід джерела може бути відновлений декодером з довільно малою ймовірністю помилки , за умови, що канал має пропускну спроможність . Цей останній результат відомий як теорема про передачу інформації.

1.3.4 Застосування теорії інформації

Теорія інформації надає основні засоби, необхідні для прямого представлення та кількісної обробки інформації. У даному розділі розглядається застосування цих засобів у конкретних задачах стиснення зображень. Оскільки фундаментальна посилання теорії інформації полягає в тому, що формування інформації може бути представлено у вигляді імовірнісного процесу, в першу чергу буде розглянута статистична модель процесу формування зображення.

Приклад 1.10. Обчислення ентропії зображення.

Розглянемо питання оцінювання інформаційного змісту (тобто ентропії) простого 8-бітового зображення:

21 21 21 95 169 243 243 243

21 21 21 95 169 243 243 243

21 21 21 95 169 243 243 243

21 21 21 95 169 243 243 243

Один відносно простий підхід полягає в тому, що можна припустити деяку конкретну модель джерела і обчислити ентропію зображення, базуючись на цій моделі. Наприклад, можна припустити, що зображення було отримано уявним «8-бітовим напівтоновим джерелом», який послідовно породжує статистично незалежні пікселі згідно якомусь заздалегідь заданому імовірнісному законом. При цьому необхідно, щоб символи джерела були рівнями яскравості, а алфавіт джерела складався з 256 можливих символів. Якщо ймовірності символів відомі, то середній інформаційний зміст зображення (ентропія) кожного елемента зображення може бути обчислена безпосередньо за допомогою виразу (1.3-3). Наприклад, у випадку одномірної щільності ймовірностей, символи джерела рівноймовірно і джерело характеризується ентропією 8 біт/елемент. Тобто кількістю інформації на символ джерела (елемент зображення) складе 8 біт. Тоді повна ентропія наведеного вище зображення складе 256 бітів. Це конкретне зображення є тільки одне з можливих рівноймовірно зображень розмірами 48 пікселів, які можуть бути породжені обраним джерелом.

Альтернативним підходом до оцінювання інформаційного складу може бути створення моделі джерела, заснованої на відносній частоті появи рівнів яркостей розглянутого зображення. Тобто спостережуване зображення може бути використано як зразок послідовного процесу роботи джерела значень яскравостей, яким воно було створено. Оскільки спостережуване зображення є єдиним індикатором зміни джерела, то доцільним буде використання гістограми яскравостей отриманого зображення для моделювання розподілу джерела символів:

Оцінка ентропії джерела, названа оцінкою першого порядку, може бути обчислена за допомогою (1.3-3).

Для даного прикладу оцінка першого порядку складе 1,81 біт/елемент. Таким чином, Ентропія джерела складе приблизно 1,81 біт/елемент, а всього зображення - 58 бітів.

Більш точні оцінки ентропії джерела значень яскравостей, який породив дане зображення, можуть бути розраховані шляхом дослідження відносної частоти появи блоків пікселів на зображенні, де під блоком розуміється група сусідніх пікселів. При збільшенні розміру блоку до безкінечності, оцінка близька до істинної ентропії джерела. (Цей результат може бути отриманий за допомогою процедури, що застосовувалася для доказу теореми кодування без шуму в Розділі 1.3.3.). Таким чином, вважаючи, що у даного зображення рядки послідовно зв'язані один за одним, а кінець зв'язаний з початком, можна обчислити відносні частоти пар пікселів (тобто дворазове розширення джерела)

Отримана оцінка ентропії (знову-таки, за допомогою (1.3-3)) складає 2,5 / 2 = 1,25 біт/елемент, де поділ на 2 є наслідком розгляду двох пікселів одночасно. Ця оцінка називається оцінкою другого порядку ентропії джерела, оскільки вона отримана обчисленням відносних частот двохелементний блоків. Хоча оцінки третього, четвертого, і більш високих порядків забезпечили б ще краще наближення ентропії джерела, збіжність цих оцінок до істинної ентропії джерела повільна, а їх обчислення складно. Наприклад, звичайне 8-бітове зображення містить можливих пар значень, відносні частоти яких повинні бути визначені. Якщо розглядаються блоки з 5 елементів, то значення можливих груп з п'яти значень складе , або ~ .

Хоча знаходження істинної ентропії зображення достатньо важко, тим не менш, оцінки, подібні розглянутим у попередніх прикладах, допомагають у розумінні можливостей стиснення зображення. Наприклад, оцінка першого порядку ентропії дає нижню межу для стиснення, якого можна досягти застосуванням одного тільки коду змінної довжини. (Згадаймо з Розділу 1.1.1, що коди змінної довжини використовуються для скорочення кодової надлишковості.) Крім того, відмінності між оцінками ентропії першого і більш високих порядків вказують на наявність або відсутність міжелементної надмірності; тобто вони показують, чи є елементи зображення статистично незалежними. Якщо елементи виявляються стастатистично незалежні (що означає відсутність міжелементних надмірності), то тоді оцінки високих порядків ентропії еквівалентні оцінкам першого порядку, а значить, нерівномірне кодування забезпечує оптимальне стиснення. Для зображення, розглянутого в попередньому прикладі, чисельна різниця між оцінками ентропії першого і другого порядків показує, що може бути побудоване таке відображення, яке дозволить додатково скоротити представлення зображення на 1,81 - 1,25 = 0,56 біт/елемент.

Приклад 1.11. Застосування відображення для зменшення ентропії.

Розглянемо відображення елементів зображення, наведеного в попередньому прикладі, яке представляє зображення наступним чином:

21 0 0 74 74 74 0 0

21 0 0 74 74 74 0 0

21 0 0 74 74 74 0 0

21 0 0 74 74 74 0 0

Сформований тут різницевий масив отриманий за допомогою першого стовпця вихідного зображення і використанням значень різниць сусідніх стовпців для інших елементів. Наприклад, другий елемент у першому рядку отриманий як (21 - 21) = 0. Статистика різницевого зображення наступна:

Якщо тепер розглядати отриманий масив як породжений «різницевим джерелом», то для визначення оцінки першого порядку ентропії можна знову скористатися формулою (1.3-3). Результатом буде 1,41 біт/елемент.

Це означає, що якщо кодувати отримане різницеве зображення способом нерівномірного кодування, вихідне зображення може бути представлене з допомогою 1,41 біт/елемент, або близько 46 бітів.

Це значення більше, ніж оцінка другого порядку ентропії, отримана в попередньому прикладі і рівна 1,25 біт/елемент. Тим самим ясно, що може бути знайдений більш ефективний спосіб відображення.

Попередні приклади показують, що оцінка першого порядку ентропії зображення не обов'язково є мінімальною швидкістю коду зображення. Причина полягає в тому, що, як правило, значення елементів зображення не є статистично незалежними. Процедура мінімізації фактичної ентропії зображення (какотмечено в Розділі 1.2) називається кодуванням джерела. За умови відсутності помилок ця процедура поєднує дві операції - відображення і кодування символів. Якщо ж припустимо виникнення помилок, то в неї також включається ще й етап квантування.

Із застосуванням засобів теорії інформації може також вирішуватися і кілька більш складних завдань - стиснення зображення з втратами. У цьому випадку, однак, найважливішим результатом є теорема кодування джерела. Як показано в Розділі 1.3.3, ця теорема стверджує, що будь-яке джерело без пам'яті може бути закодований за допомогою коду, що має швидкість , такого, що середнє спотворення на символ не перевищує . Щоб правильно застосувати цей результат до стисненню зображень з втратами, потрібно розробити підходящу модель джерела, вибір адекватної міри спотворень, а також обчислення відповідної швидкості як функції спотворень . Перший крок цієї процедури вже був розглянутий. На другому кроці можливий підхід на основі використання об'єктивного критерія якості з Розділу 1.1.4. Заключний крок стосується відшукання матриці Q, елементи якої мінімізують висловлювання (1.3-12) при обмеженнях, що накладаються умовами (1.3-24) - (1.3-28). На жаль, дана задача особливо важка, і може бути вирішена лише в невеликому числі практичних випадків. Одним з таких є випадок, коли зображення являє собою гауссову випадкову величину, а міра спотворення є функція середньоквадратичної помилки. Тоді оптимальний кодер повинен перетворювати зображення за методом головних компонент і представити кожну компоненту з однаковою середньоквадратичною помилкою.

1.4 Стиснення без втрат

У багатьох додатках стиснення без втрат є єдино допустимим методом скорочення обсягу даних. Одним з таких додатків є архівація медичних або ділових документів, стиснення з втратами яких зазвичай заборонено за законом. Іншим є обробка супутникових зображень, де як застосування, так і вартість отримання вихідних даних роблять стиск небажаним. Ще одним напрямком є цифрова рентгенологія, в якій втрата інформації може погіршити точність діагностики. У цих та інших областях потреба в стисненні зображень без втрат пояснюється конкретним використанням розглянутих зображень.

У цьому розділі увагу буде сконцентровано на використовуваних в даний час методах стиснення без втрат. Такі методи звичайно забезпечують ступінь стиснення в 2-10 разів. Більш того, вони однаково застосовні і до напівтоновим і до двійковим зображенням. Як відзначалося в Розділі 1.2, алгоритми стиснення без втрат зазвичай складаються з двох досить незалежних операцій: (1) розробка альтернативного уявлення зображення, в якому зменшена міжелементна надмірність, і (2) кодування отриманих даних для усунення кодової надмірності. Ці кроки відповідають операціям відображення і символьного кодування моделі джерела, яка розглядалася при обговоренні Рис. 1.6.

1.4.1 Нерівномірне кодування

Найбільш простим підходом до стиснення зображень без втрат є скорочення тільки кодової надмірності. Як правило, кодова надмірність присутня при будь-якому звичайному двійковому кодуванні значень елементів зображення. Як вже зазначалося в Розділі 1.1.1, вона може бути усунута кодуванням рівнів яскравості за умови мінімізації середнього числа біт, необхідного для подання значення одного елемента (1.1 -4). Щоб досягти цього, потрібна розробка нерівномірного коду, який найбільш імовірно рівнем яскравості присвоює самі короткі кодові комбінації. Нижче досліджуються кілька оптимальних і майже оптимальних методів побудови таких кодів, які формулюються на теоретико-інформаційному рівні. Зауважимо, що на практиці символами джерела можуть бути як значення яскравості зображення, так і виходи операцій їх відображення (різниці значень елементів, довжини серій і т.д.).

Кодування Хаффмана

Найвідоміший метод скорочення кодової надмірності був запропонований Хаффманом. При незалежному кодуванні символів джерела інформації, коди Хаффмана забезпечують найменше число кодових символів (бітів) на символ джерела. У термінах теореми кодування без шуму (Розділ 1.3.3), результат є оптимальним для фіксованого значення n, при умові, що символи джерела кодуються окремо.

Першим кроком у підході Хаффмана є побудова серії (безлічі рівнів) зредукованих джерел шляхом послідовності ймовірностей розглянутих символів і «склеювання» символів з найменшими ймовірностями в один символ, який буде заміщати їх у редукованому джерелі наступного рівня.

Рис.1.11 Модифікації джерела по Хаффману

Цей процес ілюструється на Рис. 8.11 для двійкового кодування (аналогічно можуть бути побудовані К-символьні коди Хаффмана). У двох лівих колонках гіпотетичний набір символів джерела та їх ймовірності впорядковані зверху вниз у порядку знищення ймовірностей. Для формування першої редукції джерела, символи з найменшими ймовірностями - в даному випадку 0,06 і ??0,04 - об'єднуються в деякий «складовий символ» з сумарною ймовірністю 0,1. Цей складовий символ і пов'язана з ним ймовірність поміщаютьються в список символів редукованого джерела, який знову упорядковується в порядку знищення значень отриманих ймовірностей. Цей процес повторюється до тих пір, поки не утвориться модифіковане джерело всього лише з двома, що залишилися символами (сама права колонка на малюнку).

Другий крок в процедурі кодування по Хаффману полягає в кодуванні кожного з модифікованих джерел, починаючи з джерела з найменшим числом символів (тобто правого на Рис. 1.11), і повертаючись назад до вихідного джерела. Для джерела з двома символами найменшим двійковим кодом є, звичайно, символи 0 і 1. Як показано на Рис. 1.12, ці символи приписуються символам джерела праворуч (вибір символів довільний - змінні 0 на 1 і навпаки дасть абсолютно той же результат). Оскільки символ поточного модифікованого джерела, що має ймовірність 0,6, був отриманий об'єднанням двох символів попереднього модифікованого джерела, то кодовий біт 0, вибраний для даного варіанта, приписується кожному з двох відповідних символів попереднього джерела, потім ці коди довільним чином доповнюються символами 0 і 1, для відмінності їх один від одного. Ця операція потім повторюється для модифікованих джерел всіх інших рівнів, поки не буде досягнутий рівень вихідного джерела. Результуючий код приведений в самій лівій колонці (Код) на Рис. 1.12. Середня довжина цього коду складе

Рис. 1.12 Процедура побудови коду Хаффмана

біта/символ.

Оскільки ентропія джерела дорівнює 2,14 біта/символ, то, згідно (1.3-21), ефективність коду Хаффмана складе 0,973.

Процедура Хаффмана будує оптимальний код для набору символів і їх ймовірностей за умови, що символи кодуються по одному. Після того, як код побудований, процес кодування/декодування здійснюється простим табличним перетворенням. Код Хаффмана є миттєвим однозначно декодіруемий блоковою кодом. Він називається блоковим кодом, оскільки кожен символ джерела відображається в фіксовану послідовність кодових символів. Він є миттєвим, тому що кожне кодове слово в рядку кодових символів може бути декодовано незалежно від подальших символів. Він є відповідно декодованим, тому будь-який рядок з кодових символів може бути декодована єдиним чином. Таким чином, будь-який рядок кодованих по Хаффману символів може декодувати аналізом окремих символів в рядку зліва направо. Для двійкового коду, представленого на Рис. 1.12, аналіз зліва направо показує, що в закодованому рядку 010100111100 першим правильно кодовим словом є 01010, яке є код для символу . Наступним правильним кодовим словом є 011, що відповідає символу . Продовжуючи ці дії, отримаємо декодоване повідомлення у вигляді .

Майже оптимальні нерівномірні коди

Побудова двійкового оптимального коду Хаффмана є незвичайним завданням, коли потрібно кодувати велику кількість символів. Для загального випадку J вихідних символів необхідно побудувати J - 2 редукцій джерела (див. Рис. 1.11) і виконати J - 2 привласнення коду (див. Рис. 1.12). Так, побудова оптимального коду Хаффмана для зображення з 256 рівнями яркостей, вимагає 254 редукції джерела і 254 присвоєння коду. Зважаючи на обчислювальну складність цього завдання, іноді доводиться жертвувати кодовою ефективністю для спрощення кодової комбінації.

У Таблиці 1.5 наведено чотири нерівномірних коди, які забезпечують такий компроміс. Зауважимо, що середня довжина коду Хаффана (див. останній рядок таблиці) менше, ніж у інших приведених кодів. Простий двійковий код має максимальну середню довжину. До того ж, швидкість коду в 4,05 біта/символ, що досягається методом Хаффмана, наближається до межі ентропії, рівної 4,0 біта/символ, підрахованої за формулою (1.3-3) і наведеної внизу таблиці. Хоча жоден з решти кодів, наведених у таблиці 1.5, не досягає ефективності коду Хаффмана, всі вони являються більш простими для побудови. Подібно коду Хаффмана, вони привласнюють самі короткі кодові слова найбільш імовірним символам джерела.

Таблиця 1.5 Нерівномірні коди

Стовпчик 5 Таблиці 1.5 відповідає простій модифікації основного методу кодування Хаффмана, назвається урізане кодування Хаффмана. Урізаний код Хаффмана будується тільки для найбільш ймовірних символів джерела, де . Для представлення інших (щодо рідкісних) символів джерела використовується код префікса, супроводжуваний кодом постійної довжини. У таблиці 1.5 значення було вибрано рівним 12, а префіксом було тринадцятого кодове слово коду Хаффмана. Тим самим «символ префікс-коду» був включений як 13-й (і останній) символ модифікованого кодового джерела з імовірністю, яка дорівнює сумі ймовірностей, що залишилися символів з до . Ці 9 символів потім кодировались при користуванні коду префікса, який виявився рівним , і 4-бітового двійкового коду, рівного індексу символу мінус 13.

У стовпці 6 Таблиці 1.5 наведено друга близька до оптимального нерівномірного коду, відомий як В-код. Він близький до оптимального, коли ймовірності символів джерела підкоряються степеневому закону виду з деякою позитивною константою .

Наприклад, розподілення довжин серій в двійковому поданні типового машинописного текстового документа близько експоненціальним. Як видно з Таблиці 1.5, кодове слово складене з бітів продовження, позначених С, і інформаційних бітів, які є двійковими числами. Єдиним завданням бітів продовження є поділ окремих кодових слів; для цього значення бітів продовження змінюються з 0 на 1 і навпаки для кожного кодового слова в рядку. В-код, представлений в Таблиці 1.5, називається -кодом тому, що за кожним бітом продовження йдуть два інформаційних біта. Послідовність -кодів, відповідних вихідній рядку символів буде виглядати наступним чином: 001 010 101 000 010 або 101 110 001 100 110, залежно від того, вибране чи значення першого біта продовження дорівнює 0 або 1.

Два нерівномірних коди, що залишилися в Таблиці 1.5 відносяться до зсувних кодів. Зсувний код формується послідовністю наступних операцій: (1) упорядкуванням вихідних символів в порядку убування їх ймовірностей, (2) поділом загального числасимволів на блоки рівних розмірів, (3) кодуванням символів всередині одного блоку і повторенням набору отриманих кодів для всіх решту блоків, (4) додавання спеціальних символів зсуву вгору і/або зсуву вниз для ідентифікації кожного з блоків. Всякий раз, коли декодер розпізнає символи зсуву, він переміщається на відовідне число блоків вгору або вниз по відношенню до основного блоку.

Щоб сформувати 3-бітовий двійковий зсувне код, використаний в колонці 7 Таблиці 1.5, вихідні символи (в кількості 21) спочатку були розташовані в порядку спадання їх ймовірностей і розділені на три блоки по 7 символів. Потім символи верхнього блоку - він розглядається як опорний блок - кодуються двійковим кодом із значеннями від 000 до 110. Восьмий двійковий код (111), не входяшіе в опорний блок, використовується як один символ зсуву вгору і ідентифікує блоки, що залишилися (в даному випадку символ зсуву вниз не використовується). Символи в останніх двох блоках кодуються за допомогою одного або двох символів зсуву в комбінації з двійковим кодом, побудованим для опорного блоку і поширеним на інші блоки. Наприклад, символ джерела буде закодовано як 111 111 100.

Зсувний код Хаффмана в колонці 8 Таблиці 1.5 формується схожим чином. Принципова різниця полягає в присвоєнні ймовірності зсувного символу ще до кодування основного блоку по Хаффману. Як правило, значення ймовірності зсувного символу підраховується як сума ймовірностей всіх символів поза основним блоком, а код зсувного символу визначається на основі тих же концепцій, що і префікс-код в урізаному коді Хаффмана. В даному випадку сума підраховується по вихідним символам і становить 0,39. Таким чином символ зсуву виявляється найбільщ імовірним символом і йому приписується одна з найкоротших кодових слів коду Хаффмана (0).

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

На відміну від розглянутих раніше нерівномірних кодів, арифметичне кодування створює неблоковие коди. В арифметичному кодуванні, історія якого може бути простежена аж до робот Елайеса, не існує однозначної відповідності між символами джерела і кодовими словами. Замість цього, вся послідовність символів джерела (тобто всі повідомлення) співвіднесена з одним арифметичним кодовим словом. Саме по собі кодове слово задає інтервал дійсних чисел між 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). Стратегія округлення гарантує, що обмеження, пов'язані з кінцевою точністю обчислень, не перешкоджають точному поданню кодових підінтервалів.

1.4.2 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-бітове зображення розмірами 44, що має вертикальний контур:

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) подається на вихід в якості чергового коду; ця нерозпізнана серія поповнює словник, а стан розпізнаної серії ініціюється останнім надійшовшим символом. Останні дві колонки таблиці описують коди і серії яркостей, які послідовно додаються до словника при кодуванні всього зображення розмірами 44 елемента. Додається дев'ять додаткових кодових слів. По завершенні кодування словник має 265 кодових слів; при цьому LZW алгоритм успішно виявив кілька повторюваних серій яркостей, що дозволило йому зменшити вихідне 128-бітове зображення до 90-бітового зображення (тобто до 10 кодів з 9 бітів). Кодова послідовність на виході створює при читанні третьої колонки (Вихід кодера) зверху вниз. Результуючий коефіцієнт стиснення дорівнює 1,42:1.

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

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

1.4.3 Кодування бітових площин

Іншим ефективним підходом до скорочення міжелементної надлишковості є обробка бітових площин зображення окремо. Метод, названий кодування бітових площин, заснований на концепції попереднього розкладання багатоградаціного зображення (чорно-білого або кольорового) на серію двійкових зображень, і подальшого кодування кожного з них за допомогою одного або декількох добре відомих алгоритмів стиснення двійкових зображень. Нижче розглядаються найбільш відомі підходи до розкладання і аналізуються деякі з широко використовуємих методів стиснення.

Розкладання на бітові площини

Рівні яскравості m-бітового чорно-білого зображення можуть бути представлені у формі полінома з основою 2

Заснований на цій властивості простий метод розкладання багатоградаційного зображення на безліч двійкових зображень полягає у поділі m коефіцієнтів полінома на m однобітових бітових площин. Площина нульового порядку утворюється виділенням бітів (або коефіцієнтів) кожного елемента, а бітова площину порядку () - виділенням бітів . Взагалі, кожна бітова площина нумерується від 0 до і формується установкою значень її елементів рівним значенням відповідних бітів або поліноміальних коефіцієнтів елементів вихідного зображення. Недолік, властивий даному підходу, полягає в тому, що малі зміни яркостей можуть істотно впливати на складність бітових площин. Так, якщо піксель зі значенням 127 (01111111) змінить значення на 128 (10000000), то у всіх бітових площинах відбудеться перехід з 1 на 0 (або з 0 на 1). Наприклад, оскільки старші біти двох двійкових кодів для 127 і 128 розрізняються, то піксель сьомий бітової площині, що мав первинне значення 0, змінить значення на 1.

Альтернативним підходом до розкладання, який зменшує ефект перенесення бітів при малих змінах яркостей, є представлення зображення у вигляді m-бітового коду Грея. Відповідний код Грея, записується у вигляді , може бути визначений за коефіцієнтами полінома (1.4-2) наступним чином:

Тут знак означає операцію виключного АБО. Цей код має ту унікальну властивість, що йдуть один за одним кодові слова розрізняються тільки в одній бітової позиції. Таким чином, малі зміни яскравості з меншою ймовірністю будуть впливати на всі m-бітових площин. Наприклад, якщо відбувається перехід з рівня 127 на рівень 128, то перехід з 0 на 1 виникне тільки в 7-й бітової площині, оскільки коди Грея для 127 і 128 дорівнюють 11000000 і 01000000 відповідно.

Приклад 1.13. Кодування бітових площин.

На Рис. 1.14 (а) і (б) представлені зображення розмірами 10241024, використовувані для ілюстрації методів стиснення, описується в частині, що залишилася в даному розділі. Напівтонове зображення дитини було отримано ПЗС камерою високого розширення.



а) б)

Рис. 1.14 Зображення розмірами 1024x1024 елемента: (а) напівтонове 8-бітове зображення, (б) двійкове зображення

Рис. 1.15 Чотири старших бітових площині зображені на Рис. 1.14 (а): лівий стовбець - двійковий код, правий стовбець - код Грея

Двійкове (двохградаційне) зображення тексту документа на право володіння, підготовленого президентом США Ендрю Джексоном в 1796 р., було оцифровано на планшетному сканері. На Рис. 1.15 і 1.16 зображення дитини представлено у вигляді восьми двійкових бітових площин, а також у вигляді восьми бітових площин коду Грея. Зауважимо, що бітові площини високих порядків є значно менш складними, ніж їх доповнення низьких порядків; тобто вони містять протяжні області з меншим кіль ¬ кість деталей або випадкових змін. Крім того, бітові площини коду Грея, є менш складними, ніж відповідні двійкові бітові площини.

Кодування областей сталості

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

При стисненні текстових документів, які переважно є білими, може використовуватися кілька більш простий підхід, який полягає в тому, що білі блоки кодуються кодом 0, а всі інші (включаючи цілком чорні) блоки - кодом 1, за яким слідує набір бітів в блоці. Перевага такого підходу, що називається пропуском білих блоків (ПББ), виникає за рахунок запропонованих структурних властивостей стисненого зображення. Якщо ж і зустрічаються невелика кількість цілком чорних блоків, то вони будуть віднесені до групи блоків змішаної яскравості; тим самим 1-бітове кодове слово буде використовуватися тільки для найбільш ймовірних білих блоків. Дуже ефективною модифікацією даного способу є вибір розмірів блоку рівним . При цьому повністю білі рядки кодуються кодом 0, а всі інші рядки - кодом префікса 1, за яким слідує звичайна ПББ кодова послідовність. Інший підхід полягає в застосуванні ітеративного підходу, відповідно з яким двійкове зображення або бітова площина розбивається на послідовність зменшуваних двовимірних підблоків. Цілком білі блоки отримують код 0, а всі інші діляться на підблоки з префіксом 1 і кодуються аналогічним чином. Таким чином, якщо подблоков є цілком білим, то він є префіксом 1, що вказує, що це підблоки першого рівня, за яким, котрим слід 0, що вказує, що подблоков білий. Якщо ж подблоков не є цілком білим, то процес розбиття продовжується до тих пір, поки не буде досягнутий заданий поріг, після чого подблоков кодується або кодом 0, якщо він цілком білий, або кодом 1, за яким йде зображення підблока.

Одномірне кодування довжин серій

Ефективною альтернативою кодуванню областей сталості, є уявлення кожного рядка зображення або бітової площини послідовністі довжин, яка описує протяг сусідніх чорних або білих пікселів. Цей метод, що відноситься до кодування довжин серій (КДС), був розроблений в 1950-х роках і разом зі своїм двовимірних розширенням став стандартним методом стиснення у факсимільному (ФАКС) кодуванні. Основна ідея полягає в тому, що при скануванні рядки зліва направо виявляються неперервні серії з нулів або одиниць, які потім кодуються кодом їх довжини; крім того, встановлюються домовленість про визначення значення кожної серії. Найбільш частими методами завдання значення серії є наступні: (1) задавати значення першої серії кожного рядка, або (2) постановити, що кожен рядок починається з білої серії, однак допустити, що її довжина може бути нульовою.

Хоча кодування довжин серій саме по собі є досить ефективним методом стиснення зображень (див. приклад у Розділі 1.1.2), зазвичай можна додатково підвищити ступінь стиснення шляхом нерівномірного кодування самих значень довжин серій. До того ж, довжини чорних і білих серій можуть кодуватися окремо, використовуючи різні нерівномірні коди, кожен їх яких оптимізований по своїй статистиці. Наприклад, допускаючи, що символ представляе чорну серію довжини , можна оцінити ймовірність того, що символ може бути породжений гіпотетичним джерелом довжин чорних серій, шляхом ділення числа чорних серій дліни зображення на загальне число чорних серій. Оцінка ентропії цього джерела довжин чорних серій, що позначається , виходить підстановкою цих ймовірностей в (1.3-3). Аналогічним чином можна підрахувати ентропію джерела довжин білих серій, що позначається . Наближене значення загальної ентропії зображення, кодованого довжинами серій, складе

де означають середні значення довжин чорних і білих серій. Формула (1.4-4) дає оцінку середнього числа бітів на піксель, що потрібні для стиснення двійкового зображення кодом довжин серій.

Двовимірне кодування довжин серій

Концепції одновимірного кодування довжин серій легко розширюються на побудову різних варіантів двовимірного кодування. Одним з найбільш відомих способів є кодування відносних адрес (КВА), засноване на відстеженні двійкових переходів, які починають і закінчують кожну серію із чорних або білих елементів. Рис. 1.17 (а) ілюструє одну з реалізацій такого підходу. Нехай ес є відстань від поточного переходу с до попереднього переходу е (протилежного знака) на тому ж рядку, а сс' є відстань від с до першого аналогічного (тобто того ж знака) пе ¬ рехода на попередньому рядку після е , який позначається с'. Якщо ес<сс', то кодуються КОА відстань d буде дорівнює ес, якщо сс'<ес, то d встановлюється рівним сс'.



а)

б)

1.16 Ілюстрація кодування відносних адрес (КВА)

Подібно кодуванню довжин серій, кодування відносних адрес також вимагає ухвалення угоди про визначення значень серій. Крім того, для коректної роботи на кордонах зображення, передбачається наявність фіктивних переходів на початку і наприкінці кожного рядка, так само як і фіктивної передує початкового рядка (скажімо, цілком білою). Нарешті, оскільки для більшості реальних зображень розподіл ймовірностей КВА відстаней є нерівномірним (див. Розділ 1.1.1), заключним кроком процесу КВА буде кодування вибраного (тобто найкоротшого) КВА відстані d за допомогою підходящого нерівномірного кода. Як показано на Рис. 1.17 (6), може бути використаний код, подібний -коду. Найменшим відстаням присвоюються найкоротші кодові слова, а всі інші відстані кодуються з використанням префіксів. Код префікса встановлює діапазон для значення d, а наступне за ним значення (позначене ххх ... х на Рис. 1.17 (6)) - зсув d щодо початкової межі діапазону. Якщо ес і сс'дорівнюють +8 і +4, як показано на 1.17 (а), то правильний КВА код буде 1100011. Нарешті, якщо d = 0, то з знаходиться безпосередньо під с', тоді як якщо d = 1, то декодер має можливість вибрати найблищу точку переходу, оскільки код 100 не розрізняє, вказується чи зсув щодо поточної або попереднього рядка.

Простежування і кодування контурів

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

У диференціальному кодуванні з пророкуванням передній і задній контури кожного об'єкта зображення (див. Рис. 1.18) простежуються одночасно, щоб сформувати послідовність пар (,). Величина означає різницю між координатами переднього контуру сусідніх рядків, а - різниця між довжиною об'єкта на сусідніх рядках. Ці різниці, а також спеціальні повідомлення, що вказують на початок нового контуру (повідомлення початок нового контуру) і закінчення старого контуру (повідомлення замикання контуру), описують кожний об'єкт.

Рис. 1.17 Параметри алгоритму диференціального кодування з пророкуванням (ДКП)

Якщо замінюється різницею між координатами задніх контурів об'єкта на сусідніх рядках, позначеної , то метод називається двойним дельта кодуванням (ДЦК).

Повідомлення про початок і замиканні контуру дозволяють парам (,) або (,), породженим на якійсь одній рядку зображення, бути правильно пов'язаними з відповідними парами на попередній і подальших рядках. Без цих повідомлень декодер не зміг би зв'язати одну пару різниць з іншого, або правильно розмістити контур на зображенні. Щоб уникнути кодування координат стовпця і рядка в кожному повідомленні про початок і замиканні контура, часто використовують окремий код, що дозволяє ідентифікувати рядки, взагалі не містять точок об'єктів. Фінальним кроком як ДКП-, так і ДДК-кодування є кодування значень , або , а також координат початку і замикання контурів підходящим нерівномірним кодом.

Приклад 1.14. Порівняння методів стиснення двійкових зображень.

Закінчуючи цей розділ, порівняємо вищеописані методи стиснення двійкових зображень. Методи порівнюються шляхом стиснення зображень на Рис. 1.14. Підсумкові швидкості кодів і коеффіціентів стиснення представлені в Таблицях 1.8 та 1.9. Відзначимо, що результати для довжин серій в методі КДС, а також для відстаней в методах ДКП та ДДК, наведені з урахуванням стиснення, досяжного при послідовному нерівномірному кодуванні (див. Розділі 1.4.1). Для цього визначались і використовувалися оцінки першого порядку ентропії (див. Розділ 1.3.4).

Результати, представлені в Таблицях 1.8 та 1.9, демонструють, що всі методи здатні скорочувати деяку кількість межелемент-ної надмірності. Тобто, результуючі кодові швидкості є нижче, ніж оцінка першого порядку ентропії кожного зображення.



Таблиця 1.8. Результати стиснення без втрат зображення на Рис. 1.14 (а) методом кодування бітових площин (прочерк у графі таблиці означає відсутність стиснення, швидкість коду дорівнює 1,00): Н = 6,82 біта/піксель.

Таблиця 1.9. Результати стиснення без втрат двійкового зображення на Рис. 1.14 (б): Н = 0,55 біта/піксель

Метод кодування довжин серій виявляється найкращим при кодування многоградаціонного зображення за допомогою бітових площин, в той час як двовимірні методи, такі як ДКП, ДДК та КОА, забезпечують більш гарне стиснення двухградаціонного зображення. Більш того, відносно проста процедура використання коду Грея при стисненні зображення на Рис. 1.14 (а), дозволяє поліпшити отриману ефективність кодування приблизно на 1 біт/піксель. Накінець, зауважимо, що всі п'ять методів стиснення змогли стиснути напівтонове зображення тільки з коефіцієнтами стиснення від 1 до 2, у той час як при стисненні двійкового зображення на Рис. 1.14 (6) їм вдалося досягти коефіцієнти стиску від 2 до 5. Як видно з Таблиці 1.8, причина різниці в ефективності полягає в тому, що всі алгоритми виявилися нездатними стиснути зображення молодших порядків при кодуванні зображення по бітових площинах. Прочерком у графах таблиці позначені ті випадки, коли застосування алгоритму стиснення приводь до збільшення обсягу даних. У таких випадках для подання бітової площині використовувалися незжаті дані, і отже, до швидкості коду додавалася величина 1 біт/піксель.

1.4.4 Кодування без втрат з передбаченням

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