Ю Мочульський, В Ісько - Вейвлет-компресія зображень - страница 1

Страницы:
1  2 

ВІСНИК ЛЬВІВ. УН-ТУ

Серія фізична. 2004. Вип. 37. С. 211-219

VISNYK LVIV UNIV. Ser.Physic. 2004. № 37. P. 211-219

УДК 621.391

PACS number(s): 42.30.Va

ВЕЙВЛЕТ-КОМПРЕС1Я ЗОБРАЖЕНЬ Ю. Мочульський, В. Ісько

Львівський національний університет імені Івана Франка, вул. Драгоманова, 19, 79005 Львів, Україна, e-mail: ivi@bizmir.net

Ключові слова: вейвлет, вейвлет-перетворення, компресія, стисне­ння зображень.

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

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

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

Отже, перед алгоритмом відеокомпресії постає завдання з виявлення і фільтрації надлишкової інформації. Як же його вирішити?

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

Наприкінці 80 - на початку 90-хроків розроблено новий стандарт, названий Wavelet-компресією.

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

структура.

© Мочульський Ю., Ісько В., 2004

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

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

Стиснення зображень. Загальний підхід до стиснення зображень за допомогою вейвлет-перетворення полягає внаступному :

1) виконати вейвлет-перетворення;

2) упорядкувати отримані коефіцієнти за спаданням;

3) відкинути "хвіст" упорядкованого масиву так, щоб енергія залишених коефіцієнтів масиву дорівнювала припустимому (за заданими умовами задачі компресії) значенню;

4) квантувати коефіцієнти (за заданими умовами задачі компресії);

5) виконати стиснення без втрат отриманих коефіцієнтів (наприклад, методом RLE або LZW);

6) запам'ятати збережені коефіцієнти іїхнє положення в масиві вихідних коефіцієнтів.

Уразівідновлення потрібно замінити відкинуті коефіцієнти нулями.

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

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

Для нас важливим є етап вейвлет-перетворення. У дискретному випадку вейвлет-перетворення можна виконувати методом Малла (так званий пірамідальний метод). Цей метод полягає у фільтруванні сигналу (для одновимірного випадку) двома фільтрами для розділення його на смуги низько- та високочастотної складової, відповідно, низько- (L) та високочастотним (Н) фільтром. На фільтри накладається умова ортогональності для неповторюваності (унікальності) вихідних даних у підсмугах. Отриманий сигнал усмугах можна децимувати на 2 за рахунок того, що частотна смуга кожної знихзменшена вдвічі. Тепер єдві підсмуги, довжина кожної з яких дорівнює половині довжини початкового сигналу. Сигнал, отриманий після низькочастотного фільтра, міститьповільнозмінні особливості вхідного сигналу (так звані апроксимуючі коефіцієнти), апісля високочастотного - локальні особливості сигналу високочастотного характеру (різкі зміни, сплески чи спади сигналу - деталізуючі коефіцієнти). У більшості випадків на низькочастотну смугу припадає більша частина енергії сигналу, ніж на високочастотну (може становити 99%). Тому знову можна виконати фільтрування низькочастотної компоненти сигналу двома фільтрами. Відповідно до цього знову єдві смуги, які децимують. Цей блок фільтрації та децимації можна повторювати на низькочастотній компоненті к разів так щоб не перевищувало довжини вхідного сигналу, де к - рівень розкладу. Отримана схема показана на рис.1, а. Також можливий варіант фільтрування і високочастотної компоненти (див. рис.1, б).

Вхідний сигнал

Фільтрування

Вхідний сигнал Фільтрування

Рівень 1

L

Н

L

Н

 

/ \

 

/ ч

/ V

Рівень 2

Рівень 3 l

L

Н

L

Н

\   і \       \ \

L Н

L Н

L Н

L Н

а б Рис. 1. Схема ортогонального (а) та пакетного (б) вейвлет-перетворення.

Першу схему (див. рис. 1, а) називають ортогональним вейвлет-перетворенням, другу (див. рис.1, б) - пакетним вейвлет-перетворенням (айого зображення - дерево перетворень).

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

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

Для двовимірного випадку євже чотири компоненти після фільтрування двома фільтрами, бо тепер наявні дві просторові координати [ та \. Відповідно, отримують такі компоненти: низькочастотна НН (після фільтрування двома низькочастотними фільтрами), високочастотна LL (після фільтрування двома високочастотними фільтрами) та комбіновані компоненти LH і HL.

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

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

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

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

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

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

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

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

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

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

Отже, необхідний критерій, що враховує всілякі просторові регулярні ефекти, виявляється, не так просто побудувати.

Найліпше втрати якості зображень оцінюють наші очі. Відмінним вважають архівування, за якого неможливо на око розрізнити первісне і розкодоване зображення; гарним - коли сказати, яке з зображень було архівоване, можна тільки в разі порівняння двох картинок, що є поряд; поганим - коли помітні великі спотворення зображення після компресії. У загальному випадку можна використовувати п'яти рівневу візуальну оцінку результату компресії зображень, хоча кількість рівнів оцінювання може бути різною. Нехай рівень якості 5 відповідає відмінному архівуванню, арівень якості 1 - найгіршій візуальній якості, за якої ледве можна впізнати початкове зображення. Відповідно, рівні якості 2, 3 і 4 є проміжними етапами візуального оцінювання (рис. 2).

Для кількісного порівняння різних методів компресії зображень використовують дві головні величини: ступінь стиснення та пікове відношення сигнал/шум (peak signal-to-noise ratio PSNR) [1]. Ступінь стиснення можна визначити як відношення кількості бітів у первинному оригінальному зображенні до кількості бітів у скомпресованому зображенні, або можна використовувати відношення біт/піксель (bit per pixel BPP). Пікове відношення сигнал/шум для скомпресованого зображення в градаціях сірого (при 8 біт/піксель) визначають так:

255

PSNR = 20log10 —, о

де 0 - середньоквадратична помилка,

о

і     0 N

—XX [ / (L, І ) - / U і')]2

N і 0 - значення ширини та висоти зображення, піксель; / і / - сигнали початкового та скомпресованого зображень, відповідно.

Якість 5 - Найліпша Якість 3 - середня Якість 1 - найгірша

Рис. 2. Приклад візуальної оцінки результату компресії.

Для досліджень ефективності вейвлет-перетворення у компресії зображень використовували засоби математичного пакета Matlab. Вейвлет-алгоритм компресії порівнювали з поширеним алгоритмом JPEG. Досліджували компресію для зображень різної складності, тобто зображень з різним розміром деталей (елементів). Для цього вибрано зображення "чайка" як низькодеталізоване; зображення "ведмідь" як середньодеталізоване; та "зимовий ліс" як зображення з найвищим рівнем вмісту дрібних деталей (рис. 3). Оцінювали рівень компресії за двома критеріями: візуальна оцінка та PSNR. Результати наведені утабл. 1, 2 та показані на рис. 4.

Рис. 3. Тестові зображення.

Коефіцієнт стиснення. Таблиця 1

Метод стиснення

Візуальна оцінка зображення

 

5

4

3

2

1

Низькодеталізоване зображення

Компресія зображення методом JPEG

6,64

15,50

28,30

46,50

54,25

Ортогональне вейвлет-перетворення

8,97

15,48

38,46

90,91

166,67

Пакетне вейвлет-перетворення

7,32

9,93

32,15

66,67

153,85

Середньодеталізоване зображення

Компресія зображення методом JPEG

3,03

6,03

13,02

32,55

46,50

Ортогональне вейвлет-перетворення

3,48

6,48

14,14

33,00

66,67

Пакетне вейвлет-перетворення

3,58

6,67

16,95

37,04

100,00

Високодеталізоване зображення

Компресія зображення методом JPEG

1,64

2,77

6,58

19,15

26,04

Ортогональне вейвлет-перетворення

2,58

3,65

10,00

23,58

50,00

Пакетне вейвлет-перетворення

2,56

3,65

10,52

23,64

65,79

Коефіцієнт PSNR, дБ. Таблиця 2

Метод стиснення

Візуальна оцінка зображення

 

5

4

3

2

1

Низькодеталізоване зображення

Компресія зображення методом JPEG

44,58

40,65

30,95

26,37

22,84

Ортогональне вейвлет-перетворення

45,21

41,25

34,08

28,37

25,10

Пакетне вейвлет-перетворення

42,22

39,27

31,45

28,31

25,10

Середньодеталізоване зображення

Компресія зображення методом JPEG

35,92

31,05

26,28

22,31

19,83

Ортогональне вейвлет-перетворення

35,71

30,96

27,27

24,62

22,92

Пакетне вейвлет-перетворення

34,92

30,31

26,31

24,12

21,97

Високодеталізоване зображення

Компресія зображення методом JPEG

27,12

23,90

19,15

16,01

12,89

Ортогональне вейвлет-перетворення

26,88

23,88

19,25

17,35

16,36

Пакетне вейвлет-перетворення

25,47

22,86

18,54

17,03

15,98

ВЕЙВЛЕТ-КОМПРЕСІЯ ЗОБРАЖЕНЬ

70 60 50 40 30 20 10

0

432

Візуальна оцінка

432

Візуальна оцінка б

-Компресія зображення методом JPEG| ■ Ортогональне вейвлет-перетворення - Пакетне вейвлет-перетворення

Рис. 4. Графіки залежностей коефіцієнта стиснення для трьох типів зображень: а - високодеталізованого; б - середньодеталізованого; в - низькодеталізованого.

Рис. 5. Порівняння ефективності стиснення зображень:

а - використання стандартного методу стиснення зображень JPEG. Коефіцієнт стиснення 1:26, візуальна оцінка 3; б - використання пакетного вейвлет-перетво­рення для стиснення зображень. Коефіцієнт стиснення 1:32, візуальна оцінка 3.

5

а

5

1

5

б

а

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

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

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

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

Приклад порівняння JPEG та вейвлет-компресії - зображення чайки (див. рис. 5). Зрис. 5 видно, що за однакового візуального сприйняття рівень компресії на основі вейвлет-аналізу є вищим, коефіцієнт стиснення 26 та 32 відповідно.

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

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

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

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

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

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

1. Дьяконов В. П. Вейвлеты. От теории к практике. М.: Солон-Р, 2002. 448 с.

2. Robert W. Buccigrossi, Eero P. Simoncelli. Image Compression via Joint Statistical Characterization in the Wavelet Domain // IEEE Transactions On Image Processing. 1999. Vol. 8. N 12. P. 1688-1701.

Страницы:
1  2 


Похожие статьи

Ю Мочульський, В Ісько - Вейвлет-компресія зображень