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

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

Рис. 1.19. Модель кодування без втрат з пророкуванням: (а) кодер; (б) декодер.

Декодер на Рис. 1.19 (6) відновлює значення з отриманої кодової послідовності і виконує зворотну операцію:

Для формування пророкує значення можуть використуватися різні локальні, глобальні або адаптивні методи (див. Розділ 1.5.1). Однак у більшості випадків пророкування формується як лінійна комбінація m попередніх елементів:

де m - порядок лінійного передбачення, - коефіцієнти пророкування ( = 1,2,…, m) а операція означає округлення до ближчого цілого. При скануванні індекс п нумерує виходи провісника у відповідності з моментами їхньої появи. Тобто, , і в рівняннях (1.4-5) - (1.4-7) можуть бути замінені на позначення, , і де означає дискретний час. В принципі, п може бути індексом як в просторі координат, так і в часі (номер кадру в разі тимчасової послідовності зображения). Для одновимірного лінійного кодування з пророкуванням вираз (1.4-7) може бути переписано у вигляді

де кожна залежна змінна тепер виражає виключно як функція просторових координат . Відповідно (1.4-8) одномірне лінійне пророкування є функція значень попередніх елементів одного опрацьованого рядка. В випадку двовимірного кодування з пророкуванням буде, взагалі кажучи, функцією всіх попередніх елементів, отриманих в даний час за допомогою послідовним скануванням з ліва на право і зверху вниз. В тривимірному випадку будуть також додаватися значення пік селів із попередніх кадрів. Для перших елементів кожного рядка вираз (1.4-8) не визначено, тому ці елементи повинні кодуватися якимось іншим способом (наприклад, кодом Хаффмана), і розглядатися як затримки процесу кодування з пророкуванням. Ці коментарі мають відношення також і до випадків двовимірного або трьохвимірного кодування.

Приклад 1.15. Кодування з передбаченням.

Розглянемо кодування напівтонового зображення на Рис. 1.14 (а) за допомогою простого лінійного провісника першого порядку:

a)

б) в)

Рис.1.20 (а) Зображення помилки передбачення, отриманої з (1.4-9). (б) Гистограма рівнів яскравості початкового зображення. (в) Гистограма помилок передбачення.

Провісник такого загального вигляду називається провісником по попередньому елементі, і відповідна процедура кодування називається диференціальним кодуванням, або кодуванням по попередньому елементу. На Рис. 1.20 (а) показано у вигляді зображення значення (сигнал) помилки пророкування, що отримується з (1.4-9) при . На цьому зображенні значення яскравості 128 відповідає нульовій помилці передбачення, а відмінні від нуля позитивні і негативні помилки передбачення посилені в 8 разів і зображуються, відповідно, більш яскравими або більш темними відтінками. Середнє значення даного зображення становить 128,02, що відповідає середній помилці передбачення в 0,02 рівня яркостей.

На Рис. 1.20 (6) і (в) представлені гістограма рівнів яркостей вихідного зображення (приведеного на Рис. 1.14 (а)), а також гістограмма помилок передбачення, отриманих за формулою (1.4-9). Зауважимо, що дисперсія помилок передбачення на Рис. 1.20 (в) багато менше дисперсії рівнів яркостей вихідного зображення. Більш того, оцінка першого порядку ентропії сигналу помилки передбачення також значно менше, ніж відповідна оцінка ентропії перехідного зображення (3,96 біт/піксель проти 6,81 біт/піксель). Це зменшення ентропії відображає скорочення значної степені надмірності за допомогою процесу кодування, незважаючи на те, що згідно (1.4-5) для точного уявлення послідовності помилок передбачення m- бітового зображення потрібні (m + 1) - бітові числа. Хоча для кодування даної послідовності помилок передбачення може бути використана будь-яка з розглянутих в Розділі 1.4.1 процедур нерівномірного кодування, результуючий коефіцієнт стиснення буде обмежений величиною приблизно 8/3,96, або близько 2:1. Взагалі, оцінка максимально стиснення будь-якого варіанту кодування без втрат з передбаченням може бути отримана діленням середнього числа бітів, використовуємих для представлення значення одного пікселя, на оцінку першого порядку ентропії сигналу помилки передбачення.

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

де - величина стандартного відхилення .

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