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

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



a) б) в)

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

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

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

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 Значення стандартних відхилень помилок при ДІКМ кодированії з втратами

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

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