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

 

ДИПЛОМНА РОБОТА

СТИСНЕННЯ ЗОБРАЖЕНЬ

ВСТУП

Кожен день величезна кількість інформації запам'ятовується, перетворюється і передається в цифровому вигляді. Фірми постачають через Інтернет своїх ділових партнерів, інвесторів і потенційних покупців річними звітами, каталогами та інформацією про товари. Введення і спостереження розпоряджень - дві основні електронні банківські операції - можуть виконуватися в комфортних умовах прямо зламу. Як частина урядової програми інформатизації в США сформовано повний каталог (а також засоби для його підтримки і зберігання) Бібліотекі Конгресу - найбільшої в світі бібліотеки, доступної по мережі Інтернет. Ось-ось стане реальністю складання персональної програми кабельного телебачення за замовленням користувачів. Відповідно значна частина переданих даних при цьому є по суті графічній або відеоінформацією, вимоги до пристроїв зберігання і засобів зв'язку стають величезними. Таким чином, значний практичний і комерційний інтерес набувають засоби стиснення даних для їх передачі або зберігання.

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

Цікавість до проблеми стиснення зображень виник більше 35 років тому. З першу увагу дослідників було звернено до питань розробки аналогових методів скорочення смуги частот відеосигналу - підхід, названий стисненням смуги пропускання. Поява обчислювальної техніки і наступні розробки в області інтегральних мікросхем призвели до зсуву інтересу від аналогових методів до цифрових алгоритмам стиску. Прийняття відносно недавно декількох ключових міжнародних стандартів стиснення зображень наочно продемонструвало значне зростання даної області - від теоретичних розробок, розпочатих в 1940-х роках К. Шенноном та іншими вченими, які першими сформулювали імовірнісний підхід до інформації, її представленю, передачі і стиску, до практичного застосування цих теоретичних результатів.

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

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

Розділи 1.4-1.6 присвячені практичній стороні питання стиснення зображень, включаючи як найважливіші використовувані методи, так і прийняті стандарти, які стимулювали розширення меж і сприяли визнанню даної дисципліни. Методи поділяються на дві великі категорії: методи стиснення без втрат і методи стиснення з втратами. Розділ 1.4 присвячений методам першої групи, які, зокрема, корисні при архівації зображень. Ці методи гарантують стиск і відновлення зображень без якого б то не було спотворення інформації. У розділі 1.5 описуються методи другої групи, що дозволяють досягти більш високого рівня обєднання даних, але не забезпечують абсолютно точного відтворення вихідного зображення. Стиснення зображень з втратами знаходить застосування в таких областях як широкомовне телебачення, відеоконференції і факсимільні передачі, в яких деяка кількість помилок є прийнятним компромісом, що дозволяє підвищити ступінь стиснення. Нарешті, розділ 1.6 присячений розгляду існуючих і пропонованих стандартів стиснення зображень.

ГЛАВА 1 ОСНОВНА ЧАСТИНА

1.1 Основи

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

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

де величина зазвичай називається коефіцієнтом стиснення, є

У разі, коли , отримаємо: і , що говорить про те, що перший спосіб подання інформації не містить надлишкових даних у порівнянні з другим. Якщо , то і , що означає значне стискання та високу надмірність даних першого набору по відношенню до другого. Нарешті, якщо , то і , і означає, що другий набір містить багато надлишкових даних в порівнянні з першим. Як правило, таке збільшення кількості даних є небажаним. Взагалі, значення і знаходяться всередині відкритих інтервалів і , відповідно. На практиці, коефіцієнт стиснення, такий як 10 (або 10:1), означає, що перший набір даних (в середньому) містить 10 одиниць зберігання інформації (скажімо, біт) на кожну одну одиницю другого (тобто стисненого) набору даних. Відповідне цьому значення надмірності 0,9 і означає, що 90% даних першого набору є надлишковими.

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

1.1.1 Кодова надмірність

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

Припустимо, що дискретна випадкова змінна , розподілена в інтервалі [0, 1], являє значення яскравості зображення, і що кожне значення з'являється з імовірністю .

де - загальне число рівнів яскравості, - кількість пікселів, що має значення яскравості , а - загальне число елементів в зображенні. Якщо число бітів, використовуваних для представлення ожного із значень , дорівнює , то середнє число бітів, необхідних для представлення значення одного елемента, дорівнює

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

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

Приклад 8.1 Просте пояснення нерівномірного кодування.

Зображення має 8 рівнів яскравості, розподіл імовірностей яких представлено в Таблиці 1.1. Якщо для представлення можливих 8 рівнів використовується простий 3-бітовий двійковий код (див. колонки Код 1 і в Таблиці 1.1), то 3 бітам, оскільки 3 бітам для всіх . Якщо використовується Код 2 з Таблиці 1.1, то середнє число бітів, необхідних для кодування зображення, зменшиться до наступної величини

Таблиця 1.1 Приклад нерівномірного кодування

Відповідно до формули (1.1-2), результуючий коефіцієнт стиснення дорівнює 3/2, 7 або 1,11. Таким чином, при використанні Коду 1 біля 10% даних (у порівнянні з Кодом 2) є надлишковими. Точний рівень надмірності може бути обчислений згідно (1.1-1):

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

Рис. 1.1 Графічне представлення принципу, що лежить в основі стиснення даних за допомогою нерівномірного кодування

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

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

1.1.2 Міжелементна надмірність

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

Графіки на Рис. 1.2 (д) і (е) суть відповідні коефіцієнти автокореляції , обчислені уздовж одного рядка кожного зображення. Ці коефіцієнти були отримані за допомогою нормалізованого варіанта рівняння

де

Нормувальні коефіцієнт в (1.1-6) враховує зміну числа елементів підсумовування, яке залежить від значення . Звичайно, значення повинно бути строго менше числа елементів в рядку. Значення змінної є номер рядка, використовуваної для обчислень. Звернемо увагу на істотні відмінності між графіками на Рис. 1.2 (д) і (е), які можуть бути якісно повязані зі структурами зображень (а) і (б). Цей зв'язок особливо помітний на Рис. 1.2 (е), де висока кореляція між значеннями пікселів, віддалених на 45 і 90 відліків, може бути прямо повязана з відстанями між вертикально орієнтованими спічками на Рис. 1.2 (6). Крім того, сильно корельованими виявляються значення суміжних пікселів: при , для зображення (а) і для зображення (б). Ці значення є типовими для більшості правильно оцифрованих телевізійних зображень.

кодер стиснення декодер бітовий

Рис. 1.2 Два зображення, гістограми значень їх яскравості і нормалізовані коефіцієнти автокореляції уздовж однієї із рядків

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

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

Приклад 1.2 Просте пояснення до кодування довжин серій.

На Рисунку 1.3 показана проста процедура відображення. На Рис. 1.3 (а) зображений ділянку монтажної схеми електронного пристроя, оцифрований з дозволом приблизно 13 ліній / мм. (330 dpi). На Рис. 1.3 (6) дане зображення представлене в двох градаційному варіанті, а графік на Рис. 1.3 (в) показує профіль яскравості уздовж деякого рядка зображення і рівень порогу бінарності. Оскільки на двохградаційному зображенні міститься багато областей з постійними значеннями, то більш ефективним поданням може бути перетворення значень елементів уздовж рядка в набір наступних пар: тут означает значення яскравості на відрізку (серії) - довжину даної серії.

Координата по горизонталі

Рис. 1.3 Малюнок до кодування довжини серії

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

Для представлення 1024 біт вихідних двохградаційних даних виявилося достатньо всього 88 біт. В цілому ж, весь наведений фрагмент розмірами 1024x343 елемента може бути представлений у вигляді 12166 серій.

На запис однієї серії використовувалося 11 біт, таким чином результуючий коефіцієнт стиснення і відповідна відносна надмірність складають

1.1.3 Візуальна надмірність

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

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

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

Приклад 1.3. Стиснення допомогою квантування.

Я Розглянемо зображення на Рис. 1.4. На Рис. 1.4 (а) представлено чорно-біле зображення з 256 можливими градаціями яскравості. На Рис. 1.4 (6) показано те ж саме зображення після рівномірного квантування на 16 рівнів (4 біта). Отриманий в результаті коефіцієнт стиснення дорівнює 2:1. Зауважимо, що на гладких областях вихідного зображення з'явилися помилкові контури; це звичайний видимий ефект занадто грубого представлення рівнів яркостей зображення.

а) б) в)

Рис. 1.4 (а) Початкове зображення. (6) Рівномірне квантування на 16 рівнів. (в) Метод модифікованого квантування яскравості на 16 рівнів

Можна відзначити значне покращення зображення на Рис. 1.4 (в), що стало можливим при використанні квантування, базованих на особливостях зорової системи людини. Незважаючи на те, що коефіцієнт стиснення при другому способі квантування теж рівний 2:1, помилкові контури значно ослаблені; однак при цьому з'явилася деяка додаткова, хоча і мало помітна зернистість. Для отримання даного результату був використаний так названий метод модифікованого квантування яскравості (МКЯ). Він враховує властиву оці чутливість до контурів і руйнує помилкові контури шляхом додавання до значення кожного елементу перед його квантуванням невеликий квазівипадкової величини, генеруємої на підставі значень молодших бітів сусідніх елементів. Оскільки молодші біти, як правило, досить випадкові, це еквівалентно додаванням деякого рівня випадковості, залежного від локальних характеристик зображення, і тим самим призводить до руйнування чіткості виникають перепадів, що виглядають як помилкові контури. Даний метод пояснюється Таблицею 1.2. Значення суми - спочатку рівне нулю - формується шляхом складання поточного 8-бітового значення яскравості і чотирьох молодших розрядів раніше отриманої суми. Однак якщо старші чотири розряду значення елемента вже були рівні 1111, то перенесення одиниці з молодших розрядів в старші блокіруется. Чотири старших біта отриманої суми використовуються в якості результату квантування (кодування) значення елемента.

Таблиця 1.2 Ілюстрація методу модифікованого квантування яскравості(МКЯ)

Підхід, використаний в методі модифікованого квантування яскравості, широко використовується багатьма процедурами Квантування, що оперують безпосередньо зі значеннями яркостей елементів стисливих зображень. Найчастіше вони здійснюють одночасне зменшення як просторового, так і яскравого розширення зображення. Вплив ефекту квантування у вигляді з'являються помилкових контурів або інших схожих ефектів потребує застосування євристичних методів їх компенсації. Так, звичайні черезрядковий 2:1, застосовувана в системах широкомовного телебачення, є теж форма квантування, при якому чергуються сусідні кадри дозволяють зменшити швидкість сканування при порівняно невеликому зниженні сприйнятої якості зображення.

1.1.4 Критерії вірності відтворення

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

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

Гарним прикладом тут є критерій середньоквадратичного відхилення (СКВ) різниці вихідного і вхідного зображень. Нехай означає вхідне зображення, а - його наближення, одержуване в результаті операцій стиснення і подальшого відновлення. Для будь-яких і помилка (нев'язка) для елементів зображень і визначається як

а величина повної нев'язки двох зображень дорівнює

де розміри зображення рівні . Величина середньоквадратичного відхилення еск0 різниці зображень і буде дорівнює

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

Відношення сигнал-шум, позначуване, виходить витягом квадратного кореня з правої частини виразу (1.1-9).

Хоча об'єктивні критерії вірності відтворення пропонують простий і зручний механізм оцінки інформаційних втрат, все-таки більшість відновлених зображень, врешті-решт, розглядаються людиною. Отже, визначення якості зображення за допомогою суб'єктивного оцінювання часто є кращим. Це може бути досягнуто шляхом показу «типового» відновленого зображення групі спостерігачів (експертів) і усереднення їх оцінок. Оцінювання може вироблятися як з використанням абсолютної шкали оцінок, так і шляхом попарного порівняння зображень і . У Таблиці 1.3 наведений один з можливих варіантів абсолютної шкали оцінювання. Попарні порівняння з використанням такої шкали можуть бути сформовані, наприклад, у вигляді набору наступних чисел: {-3, -2, -1,0,1,2.3}, що відображає, відповідно, суб'єктивні оцінки рейтингу: {значно гірше, гірше , злегка гірше, однаково, злегка краще, краще, значно краще}. У будь-якому випадку ці оцінки засновані на суб'єктивних критеріях вірності відтворення.

Приклад 8.4. Порівняння оцінок якості зображень.

Оцінки середньоквадратичних відхилень (1.1-8) зображень на Рис. 1.4 (6) і (в) від оригіналу (а) складають 6,93 і 6,78 градацій яскравості. Аналогічні оцінки відносин сигнал-шум () дорівнюють відповідно 10,25 і 10,39. Хоча ці значення досить близькі, суб'єктів незалежні оцінки візуальної якості двох вищевказаних зображення складають «погано» для зображення на Рис. 1.4 (6) і «приймемо» для зображення на Рис. 1.4 (в).

Таблиця 1.3 Шкала оцінок якості зображень. (Організація з дослідження класифікацій в телебаченні)

1.2 Моделі стиснення зображень

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

Як видно з Рис. 1.5, система стиснення містить два принципово різних структурних блоку: кодер і декодер. Початкове зображення подається на кодер, який перетворить вхідні дані в набір символів. Після передачі по каналу кодовані дані потрапляють на декодер, де створюється відновлене зображення . Взагалі, зображення може бути точною копією зображення , а може такий і не бути.

Рис. 1.5 Загальна модель системи стиснення

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

Як кодер, так і декодер, показані на Рис. 1.5, складаються з двох досить незалежних блоків. Кодер містить кодер джерела, кодування усуває надмірність джерела (вхідного сигналу), і кодер каналу, який збільшує перешкодостійкість сигналу на вихідні кодера каналу. Як легко припустити, декодер містить декодер каналу, за яким слідує декодер джерела. Якщо канал між кодером і декодером є каналом без перешкод (тобто в ньому не виникає помилок), то кодер каналу і декодер каналу можуть був відсутній ¬ вати, і тоді колер і декодер будуть містити, відповідно, тільки кодер джерела і декодер джерела.

.2.1 Кодер і декодер джерела

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

а) Кодер джерела

б) Декодер джерела

Рис. 1.6 (а) Модель кодера джерела, (б) Модель декодера джерела

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

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

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

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

Схема декодера джерела, представлена ??на Рис. 1.6 (6), має лише два блоки: блок декодера символів і блок зворотного перетворювача. Ці блоки здійснюють операції, зворотні тим операціям, які виконувалися в кодері джерела блоками кодера символів і перетворювача, причому в зворотному порядку. Оскільки операція квантування незворотна, то блок «зворотного квантователя» на Рис. 1.6 (6) відсутня.

.2.2 Кодер і декодер каналу

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

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

Розглянемо 7-бітовий код Хеммінга, що складається з кодових слів виду , асоційований з безліччю 4-бітових двійкових чисел :

де знак означає операцію виключає АБО. Зауважимо, що біти , і суть біти парності для наборів бітів і відповідно. (Нагадаємо, що двійкова рядок є парною, якщо містить парне число бітів зі значенням 1).

При декодуванні декодер каналу повинен перевірити на парність бітові позиції отриманого розширеного кодового слова. Це здійснюється наступними операціями:

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

Приклад 8.5. Кодування по Хеммінга.

Розглянемо передачу 4-бітових значень яскравості, наприклад, отриманих за допомогою алгоритму модифікованого квантування яскравості (МКЯ) - див. Таблицю 1.2, по каналу зв'язку з шумом. Помилка в єдиному біті може призвести до зміни правильного значення сигналу на 128 градацій яскравості. Для підвищення стійкості до шуму і щоб забезпечити виявлення і усунення одиночних помилок, кодер каналу може використовувати код Хеммінга, що потребує деякого збільшення надмірності. Згідно рівнянням (1.2-1), після кодування по Хеммінга перше значення МКЯ з Таблиці 1.2 буде однаково 1100110. Оскільки код Хеммінга збільшує число біт, необхідних для передачі значення МКЯ, з 4 до 7, то коефіцієнт стиснення 2:1, який був раніше досягнутий за рахунок використання методу МКЯ, зменшиться до 8/7 або 1,14:1 . Таке зменшення результуючого коефіцієнта стиснення є та ціна, яку доводиться платити за підвищення перешкодозахищеності.

1.3 Елементи теорії інформації

У Розділі 1.1 було представлено декілька шляхів зменшення обсягів обємних даних, необхідних для представлення зображення. Природно виникає наступне питання: наскільки багато даних в дійсності необхідно для представлення зображення? Іншими словами, чи існує мінімальна кількість даних, яких потрібно для повного опису зображення без втрат інформації? Теорія інформації дає математичну основу для відповіді на це та близькі йому запитання.

1.3.1 Вимірювання інформації

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

Значення Р(Е) часто називають кількістю інформації в подію Е. Взагалі кажучи, приписуване події Е кількості інформації тим більше, чим менше ймовірність Е. Якщо Р(Е) = 1 (тобто подія виникає завжди), то І(Е) = 0 і даним обставинам не приписують ніякої інформації. Це означає, що немає ніякої невизначеності, пов'язаної з подією, то повідомлення про те, що дана подія сталася, не несе ніякої інформації. Однак, якщо Р(Е)=0,99, то повідомлення про те, що Е сталося, вже передає якийсь невелика кількість інформації. Повідомлення ж, що Е не відбулося, передає істотно більше інформації, оскільки ця подія значно рідше.

Підстава логарифма в (1.3-1) задає одиницю виміру кількості інформації. Якщо використовується підставу m, то говорять про одиниці вимірювання по підставі m. Коли основа дорівнює 2, одиниця інформації називається біт. Зауважимо, що якщо Р (Е) = 1/2, то , або одному біту. Таким чином, біт є кількість інформації, що передається повідомленням про те, що сталося одне з двох можливих рівноймовірно подій. Простий приклад повідомлення такого роду - повідомлення про результат підкидання монети.

1.3.2 Канал передачі інформації

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

Рис. 1.7.Проста система передачі інформації

Припустимо, що джерело інформації на Рис. 1.7 генерує випадкову послідовність символів з кінцевого або рахункового набору можливих символів, тобто вихід джерела є дискретна випадкова величина. Набір вихідних символів називають алфавітом джерела А, а елементи набору - символами або літерами. Імовірність того, що джерело породжує символ дорівнює , причому

Для опису сукупності ймовірностей символів джерела зазвичай використовується J-мірний вектор ймовірностей . Тим самим джерело інформації повністю описується кінцевим ансамблем повідомлень (А, z).

У відповідностей зі зробленими припущеннями і формулою (1.3-1), кількість інформації, що передається джерелом при появі одного символу , буде . Якщо зявляються k символів джерела, то, згідно закону великих чисел, при достатньо великих k символ буде з'являтися на виході (в середовищ-ньому) раз. Тим самим середня кількість інформації, передається за допомогою k символів джерела, складе величину

Середня кількість інформації, що припадає на один символ джерела і позначуване , одно

Цю величину називають ентропією або невизначеністю джерела. Вона визначає середню кількість інформації (в системі одиниць з основою m), одержуваної при спостереженні одного символу джерела. Коли ця величина більше, то пов'язана з джерелом невизначеність, а значить, і кількість інформації, більше. Коли символи джерела рівноймовірно, що задається рівнянням (1.3-3) ентропія, або невизначеність, приймає максимальне значення, і тоді джерело передає максимально можливе середнє кількість інформації на один символ.

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

Імовірність виходу даного каналу і розподіл імовірності джерела z пов'язані наступним виразом

де є умовна ймовірність, тобто ймовірність отримати на виході символ , за тієї умови, що на вхід був поданий символ .

Якщо умовні ймовірності, що входять у вираз (1.3-4), записати в вигляді матриці Q розмірами , так що

тоді розподіл ймовірностей вихідних символів каналу може бути записано в матричній формі

Матрицю Q з елементами називають матрицею перехідних ймовірностей каналу, або, в скороченому вигляді, матрицею каналу.

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

де є ймовірність того, що джерелом був переданий символ за умови, що одержувач прийняв символ . Очікуване (середнє) значення для даного виразу по всьому буде рівне

яке, після підстановки рівняння (1.3-7) для і нескладних подібних перетворень може бути записано в наступному вигляді

Тут є спільна ймовірність і , тобто ймовірність того, що був переданий символ і був отриманий символ .

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

Підставляючи вирази (1.3-3) та (1.3-9) для і в (1.3-10), і згадуючи, що , отримуємо

після подальших перетворень цей вираз може бути переписано у вигляді

Таким чином, середня кількість інформації, що отримується при спостереженні одного символу на виході каналу, залежить від розподілення ймовірностей джерела (вектора z) і матриці каналу Q. Мінімальнt можливе значення дорівнює нулю і досягається тоді, коли вхідні і вихідні символи виявляються статистично незалежними, тобто у разі, коли : при цьому логарифмічні члени в правій частині (1.3-11) дорівнюють нулю для всіх значень j і k. Максимальне значення по всіх можливих виборам розподілу z джерела є пропускна здатність С каналу, описуваного матрицею каналу Q. Таким чином

,

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

Приклад 8.6. Двійковий випадок.

Розглянемо двійковий джерело інформації з вихідним алфавітом . Ймовірності породження символів джерелом дорівнюють і , відповідно. Згідно (1.3-3), ентропія джерела дорівнює

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

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

Для кожного вступника на вхід символу ДСК породжує один символ Ьу з алфавіту каналу Ймовірності отримання на виході символів і можуть бути визначені з (1.3-6):

Оскільки , отже, ймовірність того, що на виході буде символ 0, дорівнює , а ймовірність того, що на виході буде символ 1 , дорівнює .

Тепер з (1.3-12) може бути обчислена середня взаємна інформація для ДСК. Розкриваючи знак підсумовування в цьому рівнянні, і збираючи разом відповідні члени, отримаємо в результаті:

а)б)в)

Рис. 1.8. Три функції двійкової інформації: (а) Двійкова функція ентропії. (б) Середня взаємна інформація двійкового симетричного каналу (ДСК). (в) Пропускна здатність ДСК

,

де є двійкова функція ентропії, показана на Рис. 1.8 (а). Якщо значення помилки каналу фіксоване, то при і . Більш того, приймає максимальне значення, коли символи двійкового джерела рівноймовірні. На Рис. 1.8 (6) представлена залежність від при фіксованому значенні помилки каналу .

Згідно рівнянню (1.3-13), пропускна здатність ДСК визначається як максимум середньої взаємної інформації по всіх утворюючим розподілам джерела. На Рис. 1.8 (6) наведено графік для всіх можливих розподілів двійкового джерела (тобто для , або для всіх значень від до ). Можна побачити, що для будь-якого максимум досягається при = 1/2. Це значення відповідає вектору розподілів символів двійкового джерела . При цьому значення буде рівно . Таким чином, пропускна здатність ДСК, зображена на Рис. 1.8 (в) дорівнює

.

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

1.3.3 Основні теореми кодування

Загальні математичні принципи, викладені в Розділі 1.3.2, базуються на моделі системи передачі інформації, схема якої приведена на Рис. 1.7, і складається з джерела інформації, каналу та одержувача. У даному розділі в цю схему буде додана система зв'язку, і будуть розглянуті три основні теореми кодування, або подання, інформації. Як показано на Рис. 1.9, система зв'язку розміщена між джерелом і одержувачем, і складається з кодера і декодера, з'єднаних каналом зв'язку.

Терема кодування для каналу без шуму

Коли і інформаційний канал, і система зв'язку вільні від помилок, то основна роль останньої повинна зводитися до подання джерела в максимально компактній формі.

Рис. 1.9 Модель системи передачі інформації

При цих умовах теорема кодування для каналу без шуму, також називають першою теорема Шеннона, визначає мінімально досяжну середню довжину кодового слова на символ джерела.

Джерело інформації з кінцевим ансамблем повідомлень (А,z) і статистично незалежними символами джерела, називається джерелом без пам'яті. Якщо виходом джерела є не один символ, а послідовність з n символів алфавіту, то можна вважати, що вихід джерела приймає одне з можливих значень, позначуваних з повного набору можливих послідовностей в n елементів: . Іншими словами, кожен блок , називається блоковою випадковою змінною, складається з n символів алфавіту A. (Позначення дозволяє відрізняти набір блоків від набору символів алфавіту A.) Імовірність окремого блоку , дорівнює і пов'язана з імовірностями окремих символів наступним співвідношенням

де індекси використовуються для вказівки n символів алфавіту А, складових блок . Як і раніше, вектор (штрих означає, що використовується блокова випадкова змінна) позначає сукупне розподіл ймовірностей , і ентропія джерела дорівнює

Підставляючи (1.3-14) для і спрощуючи вираз, отримаємо

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

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

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

або

де означає середню довжину кодового слова, яке відповідає n-кратному розширенню нерозширення джерела, тобто

Розділивши (1.3-17) на n, і враховуючи, що , отримаємо нерівність:

, (1.3-19)

яке перетворюється в граничному випадку в рівність

(1.3-20)

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

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

Приклад 1.7. Кодування з розширенням.

Джерело інформації без пам'яті з алфавітом має ймовірності символів і . Згідно (1.3-3), ентропія цього джерела дорівнює 0,918 біт/символ. Якщо символи і представлені однобітових кодовими словами 0 і 1, то біт/символ і результуюча ефективність кодування дорівнює , або 0,918.

У Таблиці 1.4 містяться і тільки що розглянутий код, і альтернативний спосіб кодування, заснований на двократному розширення джерела. У нижній частині таблиці наведені чотири блокових символу (), відповідних другому варіанту. Як випливає з (1.3-14), їх ймовірності рівні 4/9, 2/9, 2/9 і 1/9. Відповідно (1.3-18), середня довжина кодового слова при цьому буде дорівнює 17/9 = 1,89 біт/символ. Ентропія при двократному розширенні джерела дорівнює подвоєною ентропії нерозширення джерела, тобто 1,83 біт/символ, так що ефективність при другому варіанті кодування складе = 1,83 / 1,89 = 0,97.

Таблиця 1.4 Приклад кодування з розширенням

Це дещо краще, ніж ефективність нерозширення джерела, яка дорівнює 0,92. Як легко бачити, кодування дворазового розширення джерела скорочує середнє число бітів кодової послідовності на один символ джерела з 1 біт/символ до 1,89 / 2 = 0,94 біт/символ.

Теорема кодування для каналу з шумом

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

Приклад 1.8. Двійковий канал з шумом.

Припустимо, що ДСК має ймовірність помилки = 0,01 (тобто 99% всіх символів джерела передаються через канал правильно). Простий спосіб збільшення надійності зв'язку полягає в повторенні кожного повідомлення або кожного двійкового символу кілька разів. Наприклад, припустимо, що замість передачі одного символу 0 або 1, використовується кодове повідомлення 000 або 111. Імовірність того, що під час передачі трьохсимвольного повідомлення не виникне помилки, дорівнює , або Імовірність однієї помилки буде , двох , а ймовірність трьох помилок складе . Оскільки імовірність помилки при передачі одного символу становить менше 50%, то одержуване повідомлення може бути декодовано методом голосування трьох отриманих символів. Вірогідність невірного декодування трьохсимвольного кодового слова дорівнює сумі імовірностей помилок в двох символах і в трьох символах, тобто . Якщо ж у слові немає помилок, або всього одна помилка, то воно буде декодовано вірно. Таким чином, для = 0,01 ймовірність помилки при передачі зменшилася до значення 0,0003.

Розширюючи тільки що описану схему повторення, можна досягти як завгодно малої результуючої помилки передачі. У загальному випадку, це здійснюється кодуванням n-кратного розширення джерела при використанні K-символьної кодової послідовності довжини r, де . Ключовим питанням при такому підході є вибір в якості допустимих кодових слів тільки деякого числа з можливих кодових послідовностей, а також формулювання вирішального правила, оптимізуючого ймовірність правильного декодування. У попередньому прикладі, повторення кожного символу джерела три рази еквівалентно кодуванню нерозширення двійкового джерела, використовуючого лише два з = 8 можливих кодових слів. Два допустимих коду - це 000 і 111. Якщо на декодер надходить якийсь інший (недопустимий) код, то вихід визначається голосуванням по більшості з трьох кодових бітів. Джерело інформації без пам'яті породжує інформацію зі швидкістю (в одиницях інформації на символ), рівної ентропії джерела . У разі n-кратного розширення, джерело створює інформацію зі швидкістю одиниць інформації на символ. Якщо інформація кодується так, як у попередньому прикладі, то максимальна швидкість кодованої інформації дорівнює , і вона досягається у випадку, коли всі допустимі кодові слова рівноймовірні. У такому випадку говорять, що код розміру і довжиною блоку має швидкість коду одиниць інформації на символ.

Друга теорема Шеннона [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 95 169 243 243 243

21 21 95 169 243 243 243

21 21 95 169 243 243 243

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. Застосування відображення для зменшення ентропії.

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

0 0 74 74 74 0 0

0 0 74 74 74 0 0

0 0 74 74 74 0 0

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

.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 126 126

39 126 126

39 126 126

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 встановлюється рівним сс'.

а)

б)

.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 біт/піксель.

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

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

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

Декодер на Рис. 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 (а) за допомогою простого лінійного провісника першого порядку

)б)в)

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

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

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

.5 Стиснення з втратами

На відміну від викладеного в попередньому розділі підходу до кодування без втрат, кодування з втратами засноване на виборі балансу між точністю відновлення зображення і ступенем його стиснення. Якщо допустити появу спотворень в кінцевому результаті кодування (які можуть бути, а можуть і не бути помітними), то можливо значне збільшення коефіцієнта стиснення. Фактино, багато методи стиснення з втратами можуть цілком пізнавано відновлювати одноколірні зображення виданих, стислих з кофіцієнтами більш ніж 100:1, а також відтворювати фактично відрізнити від оригіналу зображення при коефіцієнтах стиснення від 10:1 до 50:1. У той же час методи стиснення без втрат рідко добиваються коефіцієнтів кращих, ніж 3:1. Як показано в Розділі 1.2, принципова різниця між структурними схемами цих двох підходів полягає в наявності або відсутності блоку квантування на Рис. 1.6.

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

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

Для адаптації моделі до введення блоку квантувача, безпомилковий кодер на Рис. 1.19 (а) повинен бути змінений так, щоб передбачення, що генеруються кодером і декодером, були ідентичними.

а)

б)

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

Як видно на Рис. 1.21 (а), це досягається приміщенням кодера з втратами в ланцюг зворотного зв'язку провісника, де його вхід, позначений , формується як функція від попереднього передбачення і помилки квантування. Таким чином

де. та ж, що була визначена в формулі (1.4-7) в Розділі 1.4.4. Схема зі зворотним зв'язком запобігає накопиченню помилки на виході кодера. Як видно з Рис. 1.21 (б), вихід декодера також задається формулою (1.5-1).

Приклад 1.16. Дельта-модуляція.

Дельта-модуляція (ДМ) є простим, але добре відомим способом кодування з втратами, в якому провісник і квантувач визначаються таким чином

і

де - коефіцієнт передбачення (зазвичай менше 1), а - позитивна константа. Вихід квантувача , може бути представлений єдиним бітом (див. Рис. 1.22 (а)), так що кодер символів на Рис. 1.21 (а) може використовувати 1-бітовий рівномірний код. Результуюча швидкість ДМ-коду складе 1 біт/піксель.

На Рис. 1.22 (в) ілюструється механізм дельта-модуляції; в таблиці наведені значення сигналів при стисненні і відновленні наступної вхідної послідовності: {14, 15, 14, 15, 13, 15, 15, 14, 20, 26, 27, 28, 27, 27, 29, 37, 47, 62, 75, 77, 78, 79, 80, 81, 81, 82, 82} при = 1 = 6,5. Процес починається з передачі неспотвореного значення першого елемента декодеру. При початкових умовах встановлених як на стороні кодера, так і на стороні декодера, решту значення на виході можуть бути визначені повторними обчисленнями за формулами (1.5-2), (1.4-5) , (1.5-3) та (1.5-1). Так, при n = 1 отримаємо : (тому, що > 0), , і результуюча помилка відновлення складає (15 - 20,5), або -5,5 рівнів яскравості.

а) б)в)

Рис. 1.21 Приклад дельта-модуляції

На Рис. 1.22 (6) графічно показані дані, представлені в таблиці на Рис. 1.22 (в). Тут показаний вхідний сигнал () і вихід декодера (). Зауважимо, що на ділянці швидкого зміни вхідного сигналу від n = 14 до 19, де виявляється занадто малим для відстеження великих змін на вході, виникає спотворення, що називається перевантаження по крутизні. Крім того, на ділянці від n = 0 до 7, де виявляється занадто велике для відображення малих змін на вході або щодо плавних ділянок, виникає шум гранулярності. На більшості зображень ці два явища призводять до розмивання контурів і появи областей з високою зернистістю або шумом (тобто до спотворення гладких об'єктів).

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

Оптимальні провісники

Оптимальні провісники, що використовуються в більшості використовуємих кодерів з пророкуванням, мінімізують середній квадрат помилки передбачення кодера

де Е {} - математичне сподівання, за умови, що

і

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

За таких умов проблема побудови оптимального провісника зводиться до відносно простої задачі вибору m коефіцієнтів провісника, які будуть мінімізувати наступний вираз

Диференціюючи рівняння (1.5-7) по кожному з коефіцієнтів, прирівнюючи значення похідних до нуля, і вирішуючи отримуємо систему рівнянь за умови, що має нульове середнє і дисперсію , отримаємо

де є зворотною матрицею наступної матриці автокорреляції розмірами

а і є -елементними векторами

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

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

і узагальненим лінійним провісником четвертого порядку

то результуючі оптимальні коефіцієнти будуть рівні

де - горизонтальний, а - вертикальний коефіцієнти корреляції розглянутого зображення.

Нарешті, звичайно потрібно, щоб сума коефіцієнтів передбачения в (1.5-6) була менше або дорівнює одиниці, тобто

Це обмеження накладається для того, щоб гарантувати, що значення на виході провісника буде залишатися всередині допустимого діапазону рівнів яскравостей, а також, щоб зменшити вплив шумів передачі, вплив яких зазвичай проявляється на відновленому зображенні у вигляді горизонтальних смуг. Важливо також зменшити чутливість ДІКМ декодера по відношенню до вхідного шуму, тому що єдина перешкода (при визначених умовах) може розповсюджуватися на весь подальший вихід. Це означає, що вихід декодера може виявитися нестійким. Запровадження додаткового обмеження в (1.5-15) що сума повинна бути строго менше одиниці - дозволяє зменшити протяжність впливу шуму на вході декодера до декількох вихідних значень.

Приклад 1.17. Порівняння методів передбачення.

Розглянемо помилки пророкування, що виникають при ДІКМ кодуванні напівтонового зображення на Рис. 1.23, в припущенні нульовою помилки квантування і при використанні кожного з наступних чотирьох провісників

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

У вигляді зображень показані помилки передбачень, що виникають при використанні формул (1.5-16) - (1.5-19). Як видно, помітність помилки зменшується зі збільшенням порядку передбачення. Стандартні відхилення помилок передбачення дають близькі результати: вони рівні, відповідно, 4,9, 3,7, 3,3 і 4,1 рівня яскравості.

Оптимальне квантування

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

Проблема побудови квантователя полягає у виборі найкращих значень і для конкретного критерію оптимізації та щільності розподілу ймовірностей . Якщо критерієм оптимізації

Рис. 1.22 Типова функція квантування

який може бути як статистичної, так і візуальною мірою, є мінімізація середнього квадрата помилки квантування (тобто ), а також, якщо є парною функцією, умовами мінімальної помилки [Мах, 1960] є:

і

Рівняння (1.5-20) показує, що оптимальні рівні квантування є точками центрів тягарів областей під по кожному з інтервалів квантування, розділених пороговими рівнями, а рівняння (1.5-21) - що порогові рівні повинні розташовуватися посередині між рівнями квантування. Умови (1.5-22) є наслідком того, що q- непарна функція. Таким чином, для будь-якого L і , такі пари і для яких виконуються рівняння (1.5-20) - (1.5-22), є оптимальними в сенсі среднеквадрі-тичної помилки. Відповідний квантователь називається L-рівневим квантувачем Ллойда-Макса.

Таблиця 1.10. Квантователь Ллойда-Макса для щільності розподілу ймовірностей Лапласа з одиничною дисперсією

У таблиці 1.10 наведені порогові рівні і рівні квантування 2-, 4-, і 8-рівневого квантувача Ллойда-Макса для функції щільності розподілу ймовірностей Лапласа з одиничною дисперсією (1.4.10). Ці значення були отримані чисельним методом [Paez, Glisson, 1972], оскільки отримання точного, або явного, рішення рівнянь (1.5-20) - (1.5-22) для більшості нетривіальних досить важко. Три представлених квантувача забезпечують фіксовані швидкості коду, рівні, відповідно, 1, 2 і 3 бітам/піксель. Оскільки Таблиця 1.10 була побудована для розподілення з одиничною дисперсією, то значення порогових рівнів і рівнів квантування для випадків виходять простим множенням табульованих значень на величину стандартного відхилення наявного розподілу щільності ймовірностей. В останньому ряду таблиці наведені розміри кроку оптимального рівномірного квантувача, який одночасно задовільняє рівняння (1.5-20) - (1.5-22), а також додатковим обмеженням.

Якщо в кодере з втратами з пророкуванням (Рис. 1.21 (а)) використовується кодер символів, що породжує нерівномірний код, то при одній і тій же вихідній точності оптимальний рівномірний квантувач з кроком розміру в забезпечить більш низьку швидкість коду (для щільность розподілу ймовірностей Лапласа), ніж рівномірно кодований вихід квантувача Ллойда-Макса.

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

Приклад 1.18. Ілюстрація процесів квантування і відновлення.

Параметри квантователя визначалися шляхом множення табличних значень порогових рівнів та рівнів квантування для квантователя Ллойда-Макса на на стандартне відхилення неквантованої помилки двовимірного передбачення, наведене в попередньому прикладі (тобто 3,3 рівня яскравості). Зверніть увагу, що контури на декодованих зображеннях розмиті через перевантаження по крутизні. Цей ефект сильно помітний на Рис. 1.26 (а), де використувався дворівневий квантувач, але вже проявляється менше на Рис. 1.26 (в) і (д), які отримані за допомогою 4- і 8-рівневий квантувач. На Рис. 1.27 (а), (в) і (д) показані посилені різниці між вихідним (на Рис. 1.23) і отриманими декодованими зображеннями.

Для отримання декодованого зображення на Рис. 1.26 (6), (г) і (е), помилки яких показані на Рис. 1.27 (6), (г) і (е), викоритовувався метод адаптивного квантування, в якому для кожного блоку з 16 елементів вибирався найкращий (в сенсі середнього квадрата помилки) з чотирьох можливих квантувачів. Ці чотири квантувача є варіантами масштабування раніше описаного оптимального квантувача Ллойда-Макса. Масштабні коефіцієнти були 0,5, 1,0, 1,75. і 2,5. Оскільки для зазначення номера вибраного квантувача до кожного блоку додавався 2-бітовий додатковий код, то накладні витрати склали 0,125 біта/піксель.

Зверніть увагу на значне зменшення видимих помилок, досягнуте завдяки незначному збільшенню швидкості коду. У Таблиці 1.11 наведені значення стандартних відхилень помилок (1.1-8) різницевих зображень на усіх чотирьох варіантів вищенаведених провісників (1.5-16) - (1.5-19) при різних комбінаціях провісника і квантувача. Зауважимо, що з точки зору середнього квадрата помилки, дворівневий адаптивний квантувач дає настільки ж добрі результати, що і чотирьохрівневий неадаптівний. Більш того, чотирьохрівневий адаптивний квантувач дає кращі результати, ніж восьмирівневий неадаптівний. Взагалі, чисельні результати показують, що тенденції зміни величини помилки для провісників (1.5-16), (1.5-17) і (1.5-19) збігаються з аналогічними характеристиками провісника (1.5-18). У нижньому рядку таблиці наведена величина стиснення, що досягається кожним з розглянутих методів. Зауважимо, що значні зменшення стандартного відхилення помилки, що досягається адаптивним квантувачем, не приводить до істотного поліпшення характеристик стиснення.

Таблиця 8.11 Значення стандартних відхилень помилок при ДІКМ кодированії з втратами

.5.2 Трансформаційне кодування

Методи кодування з пророкуванням, які обговорюються в Розділі 1.5.1, оперують безпосередньо зі значеннями елементів зображення, і тим самим є просторовими методами. У справжньому розділі будуть розглядатися методи стиску, засновані на модифікації і стисненні результатів перетворення зображення, так звані методи трансформаційного кодування. Відповідно до цього підходу, оборотне лінійне перетворення (наприклад, перетворення Фур'є) використовується для відображення зображення в набір коефіцієнтів перетворення, які потім квантуються і кодуються. Для більшості реальних зображень значне число коефіцієнтів мають малу величину, і можуть бути достатньо грубо квантованими (або повністю видалені) ціною невеликого спотворення зображення. Для перетворення даних зображень можут використовуватися різні перетворення, включаючи дискретне перетворення Фур'є (ДПФ).

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

а)

б)

Рис. 1.23 Система трансформаційного кодування: (а) кодер; (б) декодер

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

Вибір перетворення

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

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

для Аналогічним чином, зображений може бути отримано за заданим за допомогою зворотного перетворення

для . Функції і в даних рівняннях називаються, відповідно, ядром прямого і ядром зворотнього перетворення. З причин, які будуть ясні нижче, їх також називають базисними функціями або базисними зображеннями. Набір для в рівнянні (1.5-25) називають коефіцієнтами перетворення; вони можуть бути коефіцієнтами розкладання зображення за базисними функціями .

Ядро прямого перетворення в (1.5-24) називається розділеним, якщо

У разі, коли дорівнює , рівняння (1.5-26) може бути записано у вигляді

Аналогічні коментарі можуть бути зроблені по відношенню до отруту ¬ ру зворотного перетворення; для цього досить замінити на в (1.5-26) і (1.5-27 ). Неважко показати, що двовимірне розділене перетворення може бути обчислено за допомогою відповідних одновимірних перетворень, які виконуються послідовними проходами спочатку по рядках, потім по стовпцях, або ж у зворотному порядку.

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

і

де . Підставляючи ці ядра в (1.5-24) і (1.5-25), отримаємо спрощенний варіант (в якому М = N) прямого та зворотного дискретного перетворення Фур'є.

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

де . Підсумовування у показнику ступеня виконується по модулю 2, і означає -й біт (справа наліво) в двійковому представленні . Якщо, наприклад, і , то , , . Значення в (1.5-30) обчислюються наступним чином

де підсумовування, як зазначалося раніше, виробляються за модулем 2. Для обчислення використовуються аналогічні вирази.

На відміну від ядер ДПФ, які є сумами синусів і косинусів (див. (1.5-28) і (1.5-29)), ядра перетворення Уолша-Адамара складаються з +1 і - 1, що чергуються розташованих у шаховому порядку. На Рис. 1.24 показано ядро ??для N = 4. Кожен блок складається з 4x4 = 16 елементів; білий колір означає +1, а чорний означає -1. Щоб сформувати лівий верхній блок необхідно покласти і обчислити значення для . Всі значення в цьому випадку дорівнюють +1. Другий блок у верхньому ряду є набір значень для , і так далі. Як уже зазначалося, важливість перетворення Уолша Адамара полягає в простоті реалізації - значення всіх елементів в його ядрі дорівнюють або +1 або -1.

Рис. 1.24 Базисні функції Уолша-Адамара для N = 4. Початок координат кожного блоку знаходиться в його лівому верхньому куті

Одним з найбільш часто використовуваних перетворень для стиску зображень є дискретне косинусне перетворення (ДКП). Воно виходить шляхом підстановки в (1.5-24) і (1.5-25) наступних (однакових) ядер

де

і аналогічно для . На Рис. 1.30 показані базисні функції для випадку . Результати представлені в тому ж форматі, що і на Рис. 1.24, за винятком того, що значення не є цілими. Світліші рівні яскравостей на Рис. 1.25 відповідповідають великим значенням .

Рис. 1.25 Базисні функції дискретного косинусного перетворення для N = 4. Початок координат кожного блоку знаходиться в його лівому верхньому куті

Приклад 1.19. Трансформаційне кодування з використанням ДПФ, ПУА і ДКП, і усіканням коефіцієнтів.

Результати були отримані розбиттям вихідного зображення на блоки розмірами 8x8 елементів, представленням кожного блоку за допомогою одного з розглянутих перетворень (ДПФ, ПУА або ДКП), обнуленням (усіканням) 50% найменших за значеннями коефіцієнтів, і виконанням зворотних перетворень над отриманими масивами.

У всіх випадках 32 залишаються коефіцієнта вибиралися як найбільші за значенням. Якщо відволіктися від використання квантування і кодування, то цей процес призводить до двократнього стиску вихідного зображення. У всякому разі зауважимо, що 32 видалених коефіцієнта мали дуже малий вплив на якість відновленого зображення. Їх усунення, тим не менш, призвело до виникнення деяких відхилень, які у вигляді зображень представлені на Рис. 1.31 (6), (г) і (е). Значення стандартних відхилень помилок склали, відповідно, 1,28, 0,86, і 0,68 рівнів яскравості.

Невеликі відмінності в стандартних відхиленнях помилок, приведених в попередньому прикладі, прямо пов'язані з енергією, або характеристиками ущільнення інформації застосованих перетворень. Відповідно до (1.5-25), зображення розмірами може бути представлене як функція свого двовимірного перетворення

для . Зауважимо, що в порівнянні з (1.5-25) тут відбулася заміна N на , і тепер розглядається як блок стисливого зображення. Оскільки ядро ??зворотного перетворення в (1.5-34) залежить тільки від індексів а не від значень або , то воно може розглядатися як набір базисних функцій або базисних зображень для лінійної комбінації.

Ця інтерпретація стане ясніше, якщо записати (1.5-34) у вигляділі

де є матриця розмірами , що містить значення елементів блока , а

Тоді - матриця, що містить значення елементів вхідного блоку - явно задається як лінійна комбінація матриць розмірами , тобто матриць для в (1.5-36). Ці матриці фактично є базисними зображеннями (або функціями) розкладання (1.5-35); відповідні значення є коефіцієнтами розкладання. Базисні зображення ПУА і ДКП для випадку n = 4 ілюструються на Рис. 1.29 і 1.30.

Задамо маскуючу функцію для коефіцієнтів перетворення:

для . Наближення для виходить з усіченої послідовності

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

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

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

Завдяки цьому багато системи трансформаційного кодування грунтуються на ДКП, яке дає хороший компроміс між ступенем упаковки інформації та обчислювальною складністю. Доказом того, що характеристики ДКП мають велике практичне значення, є той факт, що ДКП увійшло в міжнародний стандарт систем трансформаційного кодування (див. Розділ 1.6). У порівнянні з іншими подібними перетвореннями, ДКП забезпечує упаковку найбільшої кількості інформації в найменше число коефіцієнтів (для більшості реальних зображень), а також мінімізує ефект появи блокової структури, що називається блоковими спотвореннями, що виявляється в тім, що на зображенні стає видно границю між сусідніми блоками. Остання особливість вигідно виділяє ДКП серед інших синусоїдальних перетворень. Оскільки ДПФ характеризується n-точковою періодічностью, то розриви на межах блоків, представлені на Рис. 1.26 (а), призводять до появи помітної високочастотної складової. При усіканні або квантуванні коефіцієнтів ДПФ, прикордонні елементи блоків через явища Гіббса приймають невірні значення, що призводить до виникнення блокових спотворень. Таким чином, межі між сусідніми блоками стають помітними через те, що прикордонні елементи блоків приймають спотворені значення. ДКП представлене на Рис. 1.26 (6), зменшує цей ефект, тому що його періодичність у 2n точок не призводить до розривам на кордонах блоку. Перевагою ДКП є також і те, що воно реалізоване в інтегральних мікросхемах.

Рис. 1.26 Періодичність, притаманна одномірним (а) ДПФ і (б) ДКП

Вибір розмірів блоку.

Іншим важливим чинником, від якого залежать помилки трансформаційного кодування і обчислювальна складність, є розмір блоку. У більшості додатків зображення розбиваються таким чином, що кореляція (надмірність) між сусідніми блоками зменшується до деякого допустимого рівня, причому розмір блока n вибирається як ціла ступінь двійки. Остання умова дозволяє спростити обчислення перетворень по блоках. Взагалі, зі збільшенням розміру блоку зростає як ступінь стиснення, так і обчислювальна складність. Найбільш часто використовуваними є розміри 8 х 8 і 16x16 елементів.

Приклад 1.20. Вплив розміру блока в трасформаційному кодуванні.

На Рис. 1.27 графічно показано вплив розміру блоку на точність відновлення при трансформаційному кодуванні. Дані, наведені на графіках, були отримані розкладанням на півтонового зображення на Рис.1.23 на блоки розмірами , де обчисленим перетворення по кожному блоку, усіканням 75% отриманих коефіцієнтів, і виконанням зворотного перетворення. Згодом, що криві ПУА і ДКП стають майже горизонтальні при розмірах блока великих 8 , тоді як помилки відновлення ДПФ в цій області зменшуються, ще більш швидше. Екстраполюючи ці криві на більші значення n можливо уявити, що крива помилок выдновлення ДПФ перейде криву ПУА і наблизиться до ДКП.

Рис. 1.27 Залежність помилки відновлення від розмірів блоку

При розмірах блоку 2x2 всі три криві збігаються. У цьому випадку залишається тільки один з чотирьох (25%) коефіцієнтів у кожному перетвореному масиві. Цей коефіцієнт у всіх перетвореннях є постійною складовою, так що зворотне перетворення попросту заміняє значення всіх чотирьох пікселів блоку їх середнім значенням. Цей ефект добре видно на Рис. 1.34 (г), де показаний збільшений фрагмент результату ДКП з блоками 2x2. Зауважимо, що блокові спотворення, які максимальні на даному зображенні, зменшуються при збільшенні розмірів блоку до 4x4 і 8x8 на Рис. 1.34 (д) і (е). Для порівняння, на Рис. 1.34 (в) показаний збільшений фрагмент вихідного зображення. Крім того, для зіставлення з результатами попереднього прикладу, на Рис. 1.34 (а) і (б) представлено відновлене зображення (після усікання 75% коефіцієнтів) а також зображення отриманих помилок.

Подання в двійковій формі

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

Приклад 1.21. Двійкове подання.

Перший результат був отриманий використанням порогового кодування, що залишає 8 найбільш великих коефіцієнтів кожного блоку, а другий - за допомогою зонального кодування. В останньому випадку кожен коефіцієнт ДКП розглядався, як випадкова величина, розподіл якої визначаєтьсяь по всьому ансамблю блоків на зображенні. Були знайдені 8 розподілів з максимальними дисперсіями (12,5% з 64 коефіціента блоку 8x8), і відповідно до їх розташуванням була сформована маска, аналогічна в (1.5-38), використовувана для всіх блоків. Зверніть увагу, що при пороговому кодуванні різницеве зображення містить значно менше помилок, ніж при зональному кодуванні.

Реалізація зонального кодування.

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

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

а) б)

в) г)

Рис. 1.28 Звичайні (а) зональні маски, (б) розподіл бітів по зонах, (в) гранична маска, (г) упорядкованість коефіцієнтів

Число рівнів квантування (а відповідно, число бітів), що відводяться кожному квантувачеві, вибирають пропорційно . Такий розподіл бітів узгоджується з теорією взаємозв'язку швидкості і спотворення (див. Розділ 1.3.3), яка свідчить, що гауссова випадкова змінна з дисперсією , при відтворенні з середнім квадратом помилки менше, ніж D, не може бути представлена ??менш ніж битами (див. Завдання 1.11). Інтуїтивний висновок такий, що інформаційний зміст гаусової випадкової змінної пропорційно . Таким чином, число бітів, що відводиться залишилися коефіцієнтам в (1.5-38) (які в даному випадку вибираються згідно з критерієм максимальної дисперсії) повинно бути пропорційно логарифму дисперсії коефіцієнтів.

Реалізація порогового кодування

При зональному кодуванні, для всіх блоків зазвичай використовується одна фіксована маска. Порогове кодування, навпаки, є по суті адаптивним, оскільки позиції зберігаються коефіціента перетворення залежать від конкретного блоку. Фактично, порогове кодування є адаптивним підходом до трансформаційного кодування, яке завдяки своїй обчислювальної простоті, найчастіше і використовується на практиці. В його основі лежит той принцип, що в будь-якому блоці коефіцієнти перетворення, які мають найбільшу амплітуду, дають найзначніший внесок у інформаційний зміст відновлюваного блоку, що і було продемонстровано на останньому прикладі. Оскільки положення найбільших коефіцієнтів від блоку до блоку міняються, елементи упорядковуються (попередньо заданим методом) в одномірну послідовність, згодом кодованих кодом довжин серій. На Рис. 1.36 (в) представлений приклад типової порогової маски для одного блоку деякого гіпотетичного зображення. Ця маска дозволяє проілюструвати процес порогового кодування, математично описуваного формулою (1.5-38). Після маскування, двовимірний масив з коефіцієнтів перебудовується за допомогою зигзаг упорядкування (названого також Z-упорядкуванням). Зигзаг упорядкування очевидно з Рис. 1.34 (г), де показана черговість, в якій вибираються коефіцієнти. Сформований одновимірний масив з коефіцієнтів містить довгі серії постійних кодів, у другій половині - нулів, які добре стискуються кодуванням довжин серій. Одержувана кодова послідовність піддається ще одному етапу кодування, вже із застосуванням одного з алгоритмів нерівномірного кодування, розглянутих в Розділі 1.4.

Існує три основних способи поділу коефіцієнтів перетворення в блоці по порогу, або, інакше кажучи, побудови порогової маскуючої функції у формі, заданої формулою (1.5-37): (1) використання єдиного глобального порога, однакового для всіх блоків; (2) використання індивідуальних порогів для кожного блока; (3) змінний поріг, який може змінюватися як функція розташування коефіцієнта в блоці. У першому випадку рівень стиснення може змінюватися від зображення до зображення в залежності від того, скільки коефіцієнтів виявляються вище або нижче порога. Другий варіант, названий кодуванням N-найбільших, залишає одинакову кількість коефіцієнтів у кожному блоці. Як результат, швидкість коду є постійною і заздалегідь відомою. Третій метод, як і перший, призводить до коду непостійною швидкості, але зате має ту перевагу, що дозволяє об'єднати етапи квантування і розділення по порогу, замінюючи в (1.5-38) на

де - результат квантування та поділу по порогу значення , а - елемент масиву коефіцієнтів нормалізації перетворення

Перед тим, як нормалізовані (квантовані і розділені по порогу) коефіцієнти перетворення можуть бути піддані зворотному перетворенню для відновлення блоку зображення , вони повинні бути помножені на . Одержуваний в результаті масив є наближенням

Тим самим, зворотне перетворення отриманих значень дасть в результаті наближення відновлюваного блоку зображення.

На Рис. 1.29 графічно зображена формула (1.5-40) для випадку . Зауважимо, що приймає ціле значення до при умові

Якщо , то і коефіцієнт перетворення виявляється усіченим або викресленим. Коли коефіцієнт видається нерівномірним кодом, довжина якого зростає із збільшенням , то число бітів, що відводяться на уявлення , управляється зміною значення с. Тобто елемент матриці Z може масштабуватись, забезпечуючи тим самим різноманіття рівнів стиску. На Рис. 1.29 (6) показані значення типового масиву коефіцієнта нормалізації. Цей масив значень, які є ваговими множниками для коефіцієнтів перетворення в блоці, складений на основі оцінок візуального сприйняття, широко використовується в стандарті JPEG.

а) б)

Рис. 1.29 (а) Крива квантування порогового кодування (див. формулу (1.5-40)). (б) Типова матриця коефіцієнтів нормалізації

Приклад 1.22. Ілюстрація граничного кодування.

Перший варіант, що забезпечує коефіцієнт стиснення 34:1, був отриманий прямим застосуванням коефіцієнтів нормалізації. Другий, на якому зображення стисло з коефіцієнтом 67:1, отриманий за допомогою масштабування (попереднього множення масиву коефіцієнтів нормалізації на 4). Для порівняння: середнє значення коефіцієнтів стиску по всім методам стиснення без втрат, розглянутих в Розділі 1.4, склало лише 2,62:1.

.5.3 Вейвлет-кодування

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

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

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

Принципова відмінність системи вейвлет-кодування на Рис. 1.39 від системи трансформаційного кодування на Рис. 1.28 полягає у відсутності етапу формування окремих блоків. Оскільки вейвлет-перетворення ефективно з точки зору обчислень, і одночасно з цим по суті локально (тобто його базисні функції є просторово обмежені), то не потрібно додаткового розбиття початкового зображення. Як буде видно на наступному прикладі, відсутність такого кроку дозволяє позбутися від блокових спотворень, характерних для методів, заснованих на ДКП, при високих коефіцієнтах стиснення.

Приклад 1.23. Порівняння способів кодування, заснованих на вейвлет-перетворенні та ДКП.

Крім зменшення помилок відновлення при використаних рівнях стиснення, вейвлет-кодування.

Зауважимо повну відсутність блокових спотворень, що домінують на аналогічному фрагментіна стисненим блоковим варіантом трансформаційного кодування.

При збільшенні ступеня стиснення більш ніж 67:1, максимального з використаних в попередніх прикладах, помітним стає пропажа фактури на плаття жінки і розмивання контурів очей. Обидва ефекти є результатами відновлення зображення, стисненого вейвлет-кодуванням з коефіцієнтами 108:1 і 167:1. Збільшення розмитості особливо помітно на фрагментах. Стандартні відхилення помилок склали 3,72 і 4,73 рівнів яскравості. Суб'єктивна оцінка обох зображень показує їх очевидну перевагу перед результатом стиснення 67, виконаного за допомогою ДКП, стандартне відхилення помилки якого 6,33 рівнів яскравості.

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

Вибір вейвлета.

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

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

Приклад 1.24. Вейвлет-базис в вейвлет-кодуванні.

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

Як можна бачити з Таблиці 1.12, для перетворень, число необхідних операцій множення і склалося на коефіцієнт (для кожного рівня розкладання). Всі чотири перетворення виконувалися з використанням швидкого вейвлет-перетворення (тобто блоку фільтрів). Відмітим, що здатність до упаковки інформації зростає зі збільшенням обчислювальної складності (тобто числа ненульових коефіцієнтів фільтрів). При використанні вейвлетів Хаара і усіканням коефіцієнтів деталей на рівні значення 1,5, обнуляються 46% коефіцієнтів перетворення. При використанні більш складних біортогональних вейвлетів, число обнуляємих коефіцієнтів виростає до 55%, збільшуючи при цьому потенціал стиснення на 10%.

Таблиця 1.12 Довжини (кількість ненульових коефіцієнтів) фільтрів вейвлет-перетворення і частка обнуляємих коефіцієнтів при усіканні перетворений на рівні 1.5

Вибір рівня розкладання

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

Приклад 1.25. Рівні розкладання в вейвлет-кодуванні.

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

При збільшенні числа рівнів розкладання більше трьох, число обнуляємих коефіцієнтів змінюється мало.

Таблиця 1.13 Вплив рівня розкладання на вейвлет-кодування зображення розмірами 512x512

Розрахунок квантувача

Найважливішим фактором, що впливає на коефіцієнт стиснення і точність відновлення зображення у вейвлет-кодуванні, є квантування коефіцієнтів. Хоча найчастіше для різних рівнів застосовуються однакові квантувачі, ефективність квантування може бути помітно підвищена одним з наступних методів: (1) введенням збільшеного інтервалу квантування навколо нуля, названого «мертвою зоною», або (2) узгодження розмірів інтервалу квантування з масштабом. У будь-якому випадку обрані інтервали квантування повинні бути передані декодеру разом з кодованим потоком даних. Самі інтервали можуть визначатися як в ручну, так і автоматично на основі аналізу стислого зображення. Наприклад, глобальний поріг для коефіцієнтів може обчислюватися як медіана модулів детальних коефіцієнтів першого рівня, або ж, як функція числа відкинутих нулів і кількості енергії, яке залишається в відновлюваному зображенні.

Приклад 1.26. Вибір інтервалу «мертвої зони» в вейвлет-кодуванні.

Вплив розміру інтервалу «мертвої зони» на частку усікаються детальних коефіцієнтів для трьохрівневого вейвлет-кодування. З збільшення розміру «мертвої зони» число обнуляємих коефіцієнтів також зростає. Вище зламу кривої (тобто більше 4,5) приріст малий; це є наслідком того, що гістограма детальних коефіцієнтів має яскраво виражений пік поблизу нуля. Стандартні відхилення помилок відновлення, відповідні порогу «мертвої зони» зростають від 0 до 1,77 рівня яскравості при порозі 4,5, і до 2,79 при порозі 18, де число нулів досягає вже 96,43%. Якщо видалити всі детальні коефіцієнти, що збільшить частку нулів приблизно на 1,5%, то помилка відновлення зросте до 7,6 рівнів яскравості.

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

Багато з методів стиснення (як з втратами, так і без втрат), описані до справжнього моменту, грають найважливішу роль в найбільш розповсюджених стандартах стиснення зображень. У даному розділі розглядаються деякі з цих стандартів, і на їх основі демонструются представлені раніше методи. Більшість з стандартів були схвалені Міжнародною організацією зі стандартизації (International Standardization Organization - IOS) і Міжнародним Консультативним Комітетом з телефонії і телеграфії - МККТТ. Вони стосуються застосування методів стиснення як двійкових, так і напівтонових (монохромних або кольорових) зображень, а також і нерухомих, і рухомих зображень (тобто відеопослідовностей).

.6.1 Стандарти стиснення двійкових зображень

Двома з найбільш широко використовуваних стандартів стиснення двійкових (двохградаційнних) зображень є стандарти МККТТ Групи 3 та Групи 4. В даний час вони застосовуються в багатьох комп'ютерних додатках, хоча спочатку вони розроблялися як методи факсимільного (FАХ) кодування для передачі документів по телефонним мережам. Стандарт Групи 3 використовує неадаптивний метод одновимірного кодування довжин серій, згідно якого в кожній групі з K рядків (К = 2 або 4) всі рядки крім першої можуть кодуватися двовимірним чином. Стандарт Групи 4 є модернізованим і дещо спрощеним варіантом стандару Групи 3, допускає лише двовимірне кодування. Обидва стандарти використовують один і той же неадаптівний підхід до двовимірному кодуванню. Цей підхід дуже близький до методу кодування відносних адрес (КВА), описаного в Розділі 1.4.3.

При розробці стандартів МККТТ були відібрані вісім представлених тестових документів, що містять надруковані і рукописні тексти на декількох мовах, а також графічні малюнки. Зображення цих документів використовувалися як основа для оцінювання різних варіантів двійкового стиснення. Існуючі стандарти Групи 3 та Групи 4 дозволяють стискати їх з коефіцієнтом близько 15:1. Оскільки стандарти Групи 3 та Групи 4 є неадаптівними методами, то іноді вони приводять до збільшення обсягу даних (наприклад, у випадку напівтонових зображень). Щоб подолати цю та пов'язані з нею інші проблеми. Об'єднана група по двійковим зображенням, що є об'єднаним комітетом при МККТТ і ISO, адаптувала і запропонувала кілька інших стандартів стиснення двійкових зображень. Вони включають JBIG1 - метод адаптивного арифметичного кодування, що забезпечує найкращі результати стиснення, як в середньому, так і в найгіршому випадках, а також JBIG2 (на даний момент остаточний варіант, представлений комітетом), який дозволяє досягти стиснення в 2-4 раз кращого, ніж JBIG1. Ці стандарти можуть бути використані для стиснення як двійкових, так і напівтонових зображень з роздільною здатністю по яскравості до 6 бітів на піксель (методом кодування бітових площин).

Одновимірний стиск.

У одновимірному методі стиснення МККТТ Групи 3 кожен рядок зображення кодується послідовністю нерівномірних кодів, які відображають довжини переміжних серій білих і чорних елементів при порядковому скануванні зліва направо. При цьому бувають два типи кодових слів. Якщо довжина серії менше 63 елементів, то використовується код закінчення з Таблиці 1.14, що містить модифікований код Хаффмана. Якщо ж довжина серії перевищує 63 елемента, то спочатку ставиться максимально можливий код продовження (не перевищує довжини серії) з Таблиці 1.15, за яким йде код закінчення, відповідної різниці між дійсною довжиною серії і значенням коду продовження.

Таблиця 1.14 Коди закінчення МККТТ

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

Таблиця 1.15 Коди продовження МККТТ

Двовимірний стиск.

Спосіб двовимірного стиснення, прийнятий стандартами МККТТ Групи 3 і Групи 4, заснований на построчном скануванні, згідно якому позиція кожного елемента зміни (тобто елемента переходу з чорного на біле або з білого в чорне) поточного кодованого рядка кодується, або щодо позиції відповідного елемента зміни опорного рядка (тобто рядки, розташованої безпосередньо над кодованого рядком), або щодо позиції попереднього елемента зміни в кодованого рядку. Опорним рядком для першого рядка кожного зображення є уявний білий рядок.

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

Після визначення позиції поточного опорного елемента і пов'язаних з ним елементів зміни, виконуються дві прості перевірки, на підставі яких вибирається один з трьох можливих режимів кодування: перехідний режим, вертикальний режим або горизонтальний режим. Перша перевірка, відповідна першій точці розгалуження, порівнює позиції і . Інша перевірка, відповідна другої точки розгалуження в схемі на Рис. 1.44, визначає відстань між позиціями і і порівнює його зі значенням 3. Залежно від результатів цих перевірок здійснюється перехід на один із трьох обведених блоків на Рис. 1.44, після чого виконується відповідна процедура кодування. Потім для підготовки до наступного кроку ітерації визначається нова позиція опорного елемента згідно відповідному методу на блок-схемі.

У Таблиці 1.16 наведені особливі коди, що використовуються для кожного із трьох можливих режимів кодування. У перехідному режимі, в якому, зокрема, виключений випадок розташування безпосередньо під , потрібно тільки кодове слово перехідного режиму 0001. Як показано на Рис. 1.45 (а), даний режим відповідає випадку, коли білі або чорні серії опорної рядки не перекривають поточну білу або чорну серію на кодованого рядку. У горизонтальному режимі кодування відстані від до і від до повинні кодуватися відповідно до кодів закінчення і кодами продовження з Таблиць 1.14 і 1.15, які слідують за кодовим словом горизонтального режиму 001. Цей випадок позначений в Таблиці 1.16 як де і позначають відстані, відповідно, від до і від до . Нарешті, у вертикальному режимі кодування одне з семи кодових слів позначає відстань між і . Параметри, пов'язані з горизонтальним і вертикальними режимами кодування. Кодове слово моди розширення, наведене в нижньому рядку Таблиці 1.16, використовується для вказівки додаткового режиму факсимільного кодування. Так, наприклад, код 0000001111 використовується для початку режиму передачі без стискування.

Таблиця 1.16 Таблиця двовимірного коду МККТТ.

Приклад 1.27. Приклад вертикального режиму кодування МККТТ.

Друга перевірка, здійснює вибір між вертикальним і горизонтальним режимом, вказує на те, що повинен бути задіяний вертикальний режим, оскільки відстань між і менше 3. Згідно Таблиці 1.16, повинно бути вибрано кодове слово 000010, яке вказує, що знаходиться на дві позиції лівіше . В якості підготовки до наступної ітерації, переміщається в позицію .

8.6.2 Стандарти стиснення півтонових нерухомих зображень

МККТТ і ISO розробили декілька стандартів стиснення напівтонових (многоградаціонних) зображень. Ці стандарти, знаходяться на різних стадіях твердження, стосуються алгоритмів стиснення як монохромних (чорно-білих), так і кольорових зображень. У протилежний стандартам стиснення двійкових зображень, розглянутих в Розділі 1.6.1, стандарти стиснення напівтонових зображень принципово грунтуються тільки на методах стиснення з втратами (див. Розділи 1.5.2 та 1.5.3). При розробці стандартів, комітети МККТТ і ISO запитували рекомендації з приводу алгоритмів у великого числа дослідницьких лабораторій, компаній та університету. Кращі з числа алгоритмів, представлених на розляд, були відібрані на основі критеріїв якості зображення і характеристик стиснення. Підсумковими стандартами, що відображають сучасне положення технології стиснення напівтонових зображень, з'явилися наступні: первісний стандарт JPEG заснований на ДКП; нещодавно запропонований, заснований на вейвлет-перетворенні, стандарт JPEG 2000; а також стандарт JPEG-LS, що поєднує схему безпомилкового або майже безпомилкового адаптивного передбачення з механізмом виявлення плоских областей та кодуванням довжин серій [ISO/IЕС, 1999].

Одним з найбільш повних і популярних стандартів стиснення напівтонових нерухомих зображень є стандарт JPEG. Він визначає три різних режими кодування: (1) режим послідовного кодування з втратами, заснований на ДКП та відповідний для більшості застосувань; (2) розширений режим кодування, використовуємих для більшого стиснення, для більш високої точності, або для покрокового відтворення; та (3) режим кодування без втрат, гарантує точне відновлення інформації після стиснення. Щоб бути сумісним зі стандартом JPEG, продукт або система повинні забезпечувати підтримку режиму послідовного кодування. При цьому точно не визначаються ні формат файлу, не проторове розширення, ні модель колірного простору.

В системі з послідовною обробкою (кодуванням), часто називається системою послідовної розгортки, точність вхідних і вихідних даних обмежена 8 бітами, а точність квантованих коефіцієнтів ДКП обмежена 11 бітами. Сам процес стиснення складається з трьох послідовних кроків: обчислення ДКП, квантування і кодування нерівномірним кодом. Спочатку зображення розбивається на окремі блоки розмірами 8x8 елементів, які обробляються послідовно зліва направо і зверху вниз. Обробка кожного блоку починається зі зсуву по яскравості значень всіх його 64 елементів, що отримується відніманням величини , де - максимальне число рівнів яскравості. Потім обчислюється двовимірне дискретне косинусное перетворення елементів блоку. Отримані значення коефіцієнтів квантуються відповідно до формули (1.5-40), перебудовується зигзаг перетворенням згідно формується одномірна послідовність квантованих коефіцієнтів.

Одновимірний масив, отриманий після зигзаг перетворення відповідно до Рис. 1.36 (д), впорядковується за зростанням просторової частоти; при цьому, як правило, виникають довгі послідовності нулів, що ефективно використовується процедурою JPEG кодування. Зокрема, ненульові АС коефіцієнти кодуються нерівномірним кодом, що визначає одночасно і значення коефіцієнта і число попередніх нулів.

Таблиця 1.17. Категорії кодування JPEG коефіцієнтів

Таблиця 1.18 Стандартні JPEG коди для DС коефіцієнтів (яскравість)

Таблиця 1.19 Стандартні JPEG коди для АС коефіцієнтів (яскравість)

Таблиця 1.19 (продовження). Стандартні JPEG коди для АС коефіцієнтів (яскравість)

Поточний DС коефіцієнт кодується диференціальним кодом як різниця з DС коефіцієнтом попереднього блоку. Таблиці 1.17, 1.18 і 1.19 передставляють складені JPEG і задаються за умовчанням стандартні коди Хаффмана для яскравості. Рекомендований JPEG масив квантування яркостей представлений на Рис. 1.37 (6) і може бути масштабованим для отримання безлічі рівнів стиснення. Хоча як для яскравості, так і для кольору передбачені стандартні таблиці кодування, а також перевірені шкали квантування, тим не менш, допускається побудова користувальницьких таблиць і шкал, адаптованих до характеристик стисливого зображення.

Приклад 1.28. Послідовне кодування і декодування JPEG.

Розглянемо стиснення і відновлення наступного блоку з 8x8 елементів відповідно до стандарту послідовного кодування JPEG:

55 61 66 70 61 64 73

59 66 90 109 85 69 72

59 68 113 144 104 66 73

58 71122 154 106 70 69

61 68 104 126 88 68 70

65 60 70 77 68 58 75

71 64 59 55 61 65 83

79 69 68 65 76 78 94

Вихідні значення пікселів можуть мати 256 або можливих рівнів яскравості, так що процес кодування починається зі зсуву діапазону значень - вибору з значень пікселів величини 27 або 128. В результаті вийде масив:

-73 -67 -62 -58 -67 -64 -55

-69 -62 -38 -19 -43 -59 -56

-69 -60 -15 16 -24 -62 -55

-70 -57 -6 26 -22 -58 -59

-67 -60 -24 -2 -40 -60 -58

-63 -68 -58 -51 -65 -70 -53

-57 -64-69 -73 -67 -63 -45

-49 -59 -60-63 -52-50-34

який, після прямого ДКП згідно (1.5-24) і (1.5-32) для N= 8, буде мати вигляд:

-29 -62 25 55 -20 -1 3

-21 -62 9 11 -7 -6 6

8 77 -25 -30 10 7 -5

13 35 -15 -9 6 0 3

-8 -13 -2 -1 1 -4 1

1 3 -3 -1 0 2 -1

-1 2 -1 2 -3 1 -2

-1 -1 -2 -1 -1 0 -1

Якщо для квантування отриманих даних використовується рекомендований JPEG масив нормалізації, наведений на Рис. 1.37 (6), то після масштабування і усікання (тобто нормалізації в відповідності до (1.5-40)), коефіцієнти візьмуть наступні значення:

-3 -6 2 2 0 0 0

-2 -4 0 00 0 0

1 5 -1 -1 0 0 0

1 2 -1 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

де, наприклад, DС коефіцієнт обчислений наступним чином

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

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

Побудова JPEG коду для переупорядоченной послідовності коефіцієнтів починається з обчислення різниці між значеннями DС коефіцієнтів в поточному і попередньому (вже закодованому) блоках. Оскільки блок був узятий нами з зображення на Рис. 1.23, і відомо, що DС коефіцієнт соседнеголевого, вже перетвореного і закодованого, блоку дорівнює - 17, одержувана ДІКМ різниця буде (-26 - (-17)) = -9, яка потрапляє в категорію 4 різниць DС в Таблиці 1.17. Згідно стандартним кодами Хаффмана для різниць з Таблиці 1.18, правильний основний код буде 101 (3-бітовий код). Однак сумарна довжина повністю закодованого коефіцієнта категорії 4 складе 7 біт - залишається 4 біти повинні бути взяті з молодших розрядів (МР) значення різниці. У загальному випадку, для конкретної категорії DС різниць (скажімо, категорії К), додатково вимагається К бітів, які обчислюються або як К молодших розрядів позитивної різниці, чи як К молодших розрядів негативної різниці мінус 1. Для роз ¬ ниці -9 відповідні значення МР складуть (0111-1), або 0110, і, таким чином, повне кодоване ДІКМ кодове слово буде 1010110.

Ненульові АС коефіцієнти переупорядоченного масиву кодуются аналогічним чином по Таблицям 1.17 і 1.19. Різниця складає лише в тому, що вибір кодового слова коду Хаффмана для АС коефіцієнта залежить як від категорії амплітуди коефіцієнта, так і від числа попередніх нулів (див. колонку «Довжина серії/категорія» в Таблиці 1.19). Остаточний код першого ненульового АС коефіцієнта переупорядкованого масиву (-3) буде 0100. Перші 2 біти даного коду вказують, що коефіцієнт був з категорії 2, і що в нього немає попередніх нульових коефіцієнтів (див. Таблицю 1.17); останні 2 біти були отримані процедурою додавання МР, аналогічної викладеної вище для коду DС різниць. Продовжуючи подібним чином, повна кодова послідовність переупорядкованого масиву буде виглядати

0100 001 0100 0101 100001 0110 100011 001 100011 001 001 100101 11100110 110110 0110 11110100 000 1010.

Прогалини між кодовими словами поставлені тут виключно для зручності читання. Хоча це і не потрібно в даному прикладі, таблиця стандартних кодів Хаффмана містить спеціальне кодове слово для серії довжиною в 15 нулів, за якою знову йде 0 (див. довжину серії F і категорію 0 в таблиці 1.19). Загальне число бітів, необхідних для кодування переупорядоченного масиву (а значить, необхідних для кодування всіх 8x8 елементів вибраного блоку), становить 92. Вихідний коефіцієнт стиснення дорівнює 512/92, або близько 5,6 / 1.

При відновленні стисненого JPEG блоку декодер в першу чергу повинен з безперервного потоку бітів відтворити нормалізовані коефіцієнти перетворення.

Оскільки послідовність двійкових кодів Хаффмана є миттєвою і однозначно декодованою (див. Розділ 1.4.1), цей крок легко реалізується за допомогою табличного перетворення.

Нижче наведений масив квантованих коефіцієнтів, відновлений з потоку бітів:

-26 -3 -6 2 2 0 0 0

-2 -4 0 0 0 0 0

1 5 -1 -1 0 0 0

1 2-1 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 00 0

Після множення на коефіцієнти нормалізації згідно (1.5-42), отримаємо массив

-33 -60 32 48 0 0 0

-24 -56 0 0 0 0 0

42 13 80 -24 -40 0 0 0

17 44 -29 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

де, наприклад, DС коефіцієнт отриманий таким чином

Повністю відновлений блок виходить після виконання зворотнього ДКП отриманого масиву відповідно до рівнянь (1.5-25) і (1.5-32), що дає

-64 -61 -64 -69 -66 -58 -50

-73 -61 -39 -30 -40 -54 -59

-78 -58 -9 13 -12 -48 -64

-77 -57 0 22 -13 -51 -60

-75 -64 -23 -13 -44 -63 -56

-71 -72 -54 -54 -71 -71 -54

-59 -70 -68 -67 -67 -61 -50

-47 -61 -66 -60 -48 -44 -44

і зворотного зсуву діапазону значень на + (тобто + 128). У результаті отримуємо:

64 67 64 59 62 70 78

55 67 89 98 88 74 69

50 70 119 141 116 80 64

51 71128149 115 77 68

53 64105115 84 65 72

57 56 74 75 57 57 74

69 59 60 61 61 67 78

81 67 62 69 80 84 84

Всі відмінності значень елементів вихідного і відновленого бло ¬ ків виникають внаслідок самої природи стиснення з втратами, явля ¬ ющегося суттю 1РЕС процедур стиснення і відновлення. У даному прикладі, помилки відновлення знаходяться в діапазоні від -14 до +11 і розподілені наступним чином:

-9 -6 2 11 -1 -6 -5

4 -1 1 11 -3 -5 3

9 -2 -6 -3 -12 -14 9

7 0 -4 -5 -9 -7 1

8 4 -1 11 4 3 -2

8 4 -4 2 11 1 1

2 5 -1 -6 0 -2 5

-2 2 6 -4 -4 -6 10

Середньоквадратична помилка відхилення, що з'явилася в результаті всього процесу стиснення і відновлення, становить приблизно 5,9 рівнів яскравості.

Блок пікселів, відновлюваний в попередньому прикладі, розміщений майже в центрі правого ока знімка жінки на Рис. 1.38 (а). Зауважимо, що як у вихідному, так і у відновленому блоках є пік значень яскравості у п'ятому елементі четвертого ряду, що відповідає відблиску на зіниці. Наявність такого локального піку і призвело до помітному збільшенню середньоквадратичної помилки відхилення відновленого блоку в порівнянні з середньою помилкою по всьому відбудовн-ленному зображенню. Фактично вона виявилася вдвічі вищою, ніж у відновленого зображення на Рис. 1.38 (а), яке також було стисло тим же JPEG алгоритмом послідовного кодування. Причина в тому, що багато блоки на вихідному зображенні потрапляють на ділянці з майже постійним значенням, і можуть бути представлені з малими помилками. На Рис. 1.38 (6) представлений ще один результат стиску зображення JPEG алгоритмом послідовного кодування.2000.

Стандарт JPEG 2000, хоча він ще остаточно формально не прийнятий, розширює вихідний стандарт JPEG, надаючи велику гнучкість, як при стисненні напівтонових зображень, так і при доступі до самим стислим даними. Так, наприклад, окремі частини зображення, стиснутого за стандартом JPEG 2000, можуть бути виділені для передачі, зберігання, відтворення або редагування. Стиснення за стандартом JPEG 2000 засновано на методах вейвлет-кодування, розглянутих в Розділі 1.5.3. Квантування коефіцієнтів здійснюється по-різному в різних масштабах і діапазонах (смугах), а самі квантовані коефіцієнти кодуються арифметичним кодом як бітові площини (див. Розділ 1.4). Згідно з визначеннями стандарту [ISO/IEC, 2000], процедура кодування зображення полягає в наступному.

Першим кроком процедури кодування є зрушення значення середнього рівня яскравості, здійснюваний вирахуванням з позитивних значень відліків кодованого зображення величини , де n - число бітів в елементах зображення. Якщо зображення має більше однієї компоненти - як, наприклад, червона, зелена і синя компоненти в разі кольорового зображення - кожна компонента зрушується незалежно. Якщо компонент в точності три, то вони додатково можуть бути декорельовані за допомогою лінійного перетворення компонент. Згідно стандарту, перетворення компонент може бути оборотним (перетворення цілих значень в цілі, використовуване в оборотньому вейвлет-перетворенні 5-3 без втрат), або незворотних (перетворення дійсних значення в дійсності, використовуючи у необоротному вейвлет-перетворенні 9-1 з втратами). Так, необоротне перетворення компонент складається в наступному

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

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

Потім обчислюється одномірне дискретне вейвлет-перетворення по рядках і по стовпцях кожної компоненти тайла. Стиснення без втрат (оборотне вейвлет-перетворення 5-3) засноване на використанні коефіцієнтів уточнюючих послідовностей для масштабованої функції та вейвлет-функції системи біортогонапьних вейвлетів. Для нецілих значень коефіцієнтів перетворення задається процедура округлення. У системах стиснення з втратами (необоротне вейвлет-перетворення 9-7) застосовують коефіцієнти уточнюючих послідовностей для масштабується функції та вейвлет-функції системи вейвлетів, описаної в. У кожному з випадків перетворення обчислюється з допомогою швидкого вейвлет-перетворення, або за допомогою так званої ліфтинг-схеми. Коефіцієнти, необхідні для побудови блоку фільтрів аналізу незворотного швидкого вейвлет-перетворення (БВП).Реалізація альтернативної ліфтинг-схеми вимагає шести послідовних операцій:

Тут X є перетворюються тайл-компонента, Y - результат перетворення, а і задають положення тайл-компоненти всередині компоненти повного зображення. Тобто, вони є індекс першого відліку перетвореного рядка або стовпця тайл-компоненти (), і того відліку, який слідує безпосередньо за послідовним відліком (). Змінна n приймає значення у залежності від значень і , а також від того, яка з шести операцій виконується. Для або , X(n) виходить симетричним продовженням Х; наприклад

По закінченні операцій ліфтінга значення Y з парними індексами будуть збігатися з результатами на виході низькочастотного БВП фільтра аналізу, а значення Y з непарнимі індексами - з результатами на виході високочастотного БВП фільтра аналізу. Параметри ліфтингу складають: = -1,586134342, = -0,052980118, = 0,882911075, = 0,433506852, а коефіцієнт К = 1,230174105.

Таблиця 1.20 Імпульсні характеристики низькочастотного і високочастотного фільтрів аналізу для незворотного вейвлет-перетворення 9-7, застосовуваного в разі стиснення з втратами

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

Стандарт не визначає число масштабів, які повинні бути обчислені.

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

де - знак числа, [] - ціла частина числа, а крок квантування становить

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

Так, для складової потрібно 2 додаткових біти розкладання.

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

де позначає число рівнів розкладання складової від вихідної тайл-компоненти зображення до складової b.

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

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

де означає відновлене значення коефіцієнта, а - число декодованих бітових площин для . Отримані значення коефіцієнтів потім піддаються зворотним перетворенням по стовпцях і рядках, використовуючи блок фільтрів зворотнього БВП, коефіцієнти якого беруться з Таблиці 1.20, або за допомогою наступної ліфтинг-операції

Параметри , , , і тут ті ж, що використовувалися для рівнянь (1.6-2). Якщо необхідно, здійснюється симетричне продовження значень коефіцієнтів по рядках і стовпцях. Фінальними операціями декодування є збір тайл-компонент, зворотне перетворення компонент (якщо потрібно) і зворотний зсув значення середнього рівня яскравості. У разі незворотного вейвлет-перетворення 9-7, зворотне перетворення компонент обчислюєтся за формулами

після чого до отриманим значенням додається величина , де n - число бітів в елементах зображення. Зображення на Рис. 1.40 і 1.41 Розділу 1.5.3, що ілюструють стиснення з коефіцієнтами від 34:1 до 167:1, були отримані за допомогою алгоритму JPEG 2000 стиску з втратами.

1.6.3 Телевізійні стандарти стиснення

Стандарти стиснення відеоданих (телевізійні стандарти) розширюють трансформаційні методи стиснення нерухомих зображень, розглянуті в попередньому розділі, в сенсі скорочення часової або міжкадрової надлишковості. Хоча в даний час існує цілий ряд різних стандартів кодування, тим не менше, більшість з них засноване на використанні схожих методів стиснення відеоданих. В залежності від призначення, стандарти групуються в дві великі категорії: (1) стандарти для відеоконфепенцій, і (2) мультимедійні стандарти.

Багато зі стандартів для відеоконференцій, включаючи Н.261 (називаються також РХ64), Н.262, Н.263, і Н.320, визначені Міжнародним союзом з телекомунікацій (ITU), що є наступником Міжнародного консультативного комітету з телеграфії і телефонії (МККТТ). Стандарт Н.261 призначений для застосування при швидкостях, відповідних звичайними телефонними лініями, і забезпечує передачу відеоданих по лініях Т1 із затримками не більше 150 мс. (При затримках більше 150 мс. у спостерігача частково втрачається відчуття візуальної зворотнього зв'язку). Стандарт Н.263, навпаки, призначений для передачі відеоданих з дуже низькими швидкостями від 10 до 30 Кбіт/сек., а стандарт Н.320, який є розширенням Н.261, розроблений з урахуванням смуги пропускання Цифрових мереж з інтегрованими послугами (ISDN). У кожному з стандартів використовується схема кодування на основі дискретного косинусного перетворення (ДКП) з компенсацією руху. Здійснити оцінку руху по перетвореним данних складно, тому дана операція здійснюється в просторовій області. Блоки пікселів, називаються макроблоками, порівнюються з блоками попереднього кадру, знаходиться величина зсуву блоку, що забезпечує найменшу помилку пророкування, яка і є параметром компенсації руху. Помилка передбачення потім трансформується ДКП по блокам 8x8 пікслів, квантуєтся і кодується для передачі або зберігання.

Мультимедійні стандарти стиснення відеоданих для персоналізваного телебачення, цифрове широкомовне телебачення високої чіткості (ТВЧ), а також обслуговування баз даних зображень / відео використовують близькі методи оцінки руху і кодування. Три основні стандарти - MPEG-1, МРЕG-2 і МРЕG-4 були розроблені Групою Експертів по рухомих зображеннях (МРЕG), що діє під егідою ISO і МККТТ. МРЕG-1 є стандартом кодування «розважаючої якості», призначеного для запису та відтворення відеоданих на цифрові носії типу компакт-дисків (СD-RОМ); він забезпечує швидкість потоку даних близько 1,5 Мбіт/с. МРЕG-2 орієнтований на додатки, що вимагають телевізійного якості з рівнем між NTSC/PAL і CCIR 601 при швидкості передачі від 2 до 10 Мбіт/с. - даний параметр відповідає диапазону кабельного телебачення і вузькосмугових систем супутникової сигналізації. Метою як МРЕG-1, так і МРЕG-2 є забезпечення ефективності передачі та зберігання аудіо-і відеоданих (АВ). МРЕG-4, з іншого боку, забезпечує підвищення ефективності стиснення відеоданих; інтерактивність, засновану на зберіганні, наприклад, об'єктно-орієнтований доступ до АВ-об'єктам, або ефективну інтеграцію натурних і синтезованих даних, універсальний доступ, що допускає нестійко працююче обладнання, можливість додавати або видаляти АВ-об'єкти або міняти масштаби розширення об'єктів. Хоча подібні функціональні можливості і призводять до необхідності сегментації відеоданих на об'єкти довільного виду, тим не менш, сегментація як така не є частиною стандарту. Значна частина відеоданих (наприклад, комп'ютерні ігри) виготовляється і легкодоступна у формі відео об'єктів. МРЕВ-4 націлений на швидкості передачі від 5 до 64 Кбіт / с. для мобільних і Комутованих телефонних мереж загального доступу (PSTN), а також на швидкості до 4 Мбіт / с. для передачі ТВ і фільмів. Крім того, він підтримує передачу як з постійною, так і зі змінною швидкостями кодування.

Також як і стандарти відеоконференцій ITU, стандарти МРЕG побудовані на основі гібридної блокової схеми ДІКМ/ДКП кодування. Він використовує надлишковості як всередині кадру, так і між сусідніми кадрами, одноманітність руху між кадрами, а також психофізичні властивості зорової системи людини. Входом кодера є масиви 8x8 пікселів, названі блоками зображення. Стандартами визначені також макроблоки розмірами 2x2 блоку зображення (тобто масиви з 16x16 пікселів) і так звані слайси - набори з послідовних неперекриваючих макроблоків. Для кольорового відео макроблок складається з чотирьох блоків яскравості, що позначаються від до , і двох блоків цветоразностей і

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

Блоки основного потоку даних, відзначені сірим кольором, аналогічні операціям перетворення, квантування і нерівномірного кодування JPEG-кодера. Принципова різниця полягає у вхідних даних, які можуть бути або звичайним блоком даних зображення, або різницею між звичайним блоком і його пророкуванням, зробленим на основі попереднього та / або подальшого кадрів відеопослідовності. Це призводить до трьох основних типів кодованих кадрів відеопослідовності:

. Основний або незалежний кадр (І-кадр). І-кадр кодується незалежно від всіх як попередніх, так і наступних кадрів відео послідовності. Із всіх трьох можливих типів кадрів він найбільш схожий на JPEG-кодоване зображення. Більш того , він є точкою відліку для побудові послідовності із Р- і В - кадрів. Наявність І - кадрів забезпечує вільний доступ до відео послідовності, легкість її змін, а також захист від поширення помилок передачі. Як результат, всі стандарти вимагають періодичного вставляння подібних кадрів в стислий кодовий потік.

. Передбачений кадр (Р-кадр). Р-кадр є стисла різниця між поточним кадром і його пророкуванням, зробленим на основі попереднього I-або Р- кадру. Різниця формується у блоці обчислення різниці. Передбачення включає компенсацію руху, здійснювану зміщенням декодувати макроблоки в околиці своєї центральної точки, і обчисленням заходи кореляції (наприклад, суми квадратів різниць значень пікселів в пророкує зображенні і зрушеному макроблоків); ці операції показані в нижній частині схеми на Рис. 1.47. У дійсності процес пошуку оптимального передбачення часто проходить на більш точному рівні, ніж розмір одного елемента (наприклад, можливе зміщення макроблоку на 1/4 елемента), що вимагає здійснення інтерполяції значень елементів до обчислення заходів кореляції. Знайдений вектор руху потім кодується нерівномірним кодом і передається як частина загального кодованого потоку даних.

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

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

Висновок

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

Посилання та література для подальшого вивчення

1.С.М. Клименко, О.С. Дуброва Стандарти стиснення зображень: Навч. пос. К.: КНЕУ, 2005

2.С.Ф. Покропивний, С.М. Соболь, Г.О. Швиданенко Бізнес-план: технологія розробки та обґрунтування: Навч. пос. - К.: КНЕУ, 1999. - 208 с.

.С.Ф. Покропивний, С.М. Соболь, Г.О. Швиданенко, Л.М. Шапринська Моделі стиснення зображень : Навч. метод. Посібник для самост. вивч. диск. К.: КНЕУ, 2001. - 160 с.

.Л.Г. Агафонова, О.В. Рога Підготовка плану: Практикум. - 3-тє вид., стер. К.: Т-во „Знання, КОО, 2001. - 158 с.

.Тєлєтов О. С. Елементи теорії інформації: Підручник. - : К.: Центр навчальної літератури, 2004. - 248 с.

.Покропивний С.Ф. Графіка. - 2-ге, переробл. та доп. - К.: КНЕУ, 2001. - 528 с., іл.

.Т.О. Примак «СТИСНЕННЯ ЗОБРАЖЕНЬ» : Навч.посібник.

ДИПЛОМНА РОБОТА СТИСНЕННЯ ЗОБРАЖЕНЬ ВСТУП Кожен день величезна кількість інформації зап

Больше работ по теме: