Стиск нерухомих зображень з використанням хвилькових перетворень

Поняття хвилькового перетворення

Дискретне хвилькове перетворення (dyscrete wavelet transform (DWT)) принципово відрізняється від спектральних перетворень.

На рис.8.3 показано структуру для смугового аналізу, яка ґрунтується на використанні набору цифрових фільтрів, смуги пропускання яких примикають одна до одної, з частотними характеристиками Н_i(w), i=1,..,M.

 

 

 

Рис. 8.3.

y1 (n), y2 (n), y1 (n),…, yM (n) можна прорідити за теоремою Найквіста –Котельникова.

H(ω)

 

...

 

ω

 

Рис.8.4.

Кожний смуговий фільтр має вихід у_і(n), який отримується в результаті згортки вхідних даних x(n) з імпульсною характеристикою h_i(n) і-го ЦФ. Якщо смуги пропускання фільтрів вибрати так, що вони покривають увесь спектр вхідного сигналу, і якщо, крім того, фільтри побудовані дуже ретельно, то сума y(n) всіх вихідних сигналів фільтрів буде доброю апроксимацією вхідного сигналу (наведена пунктирним лініями на рис.)

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

Якщо до спектру X(w) дискретного сигналу x(n) застосувати зсув частоти на величину w_i , щоб отримати X (w-w_i), то одержаний спектр буде відповідати новому дискретному сигналу виду (Т- інтервал дискретизації).

x_i(n)= x(n) e ^{2 jnw iT}

де Т≤1/2f_c.

Якщо w_С- максимальна частота сигналу (наприклад, аналоговий сигнал x(t) має спектр, обмежений величиною w_С), потрібно виконати зсуви частоти сигналу :

де і = 1,…,М-1, щоб отримати аналіз М смуг, використовуючи один ФНЧ з частотою зрізу . Звідси випливає, що всі частотні смуги початкового спектру будуть зсунуті в смугу низьких частот [0,w_С/M].

Якщо використати в якості дискретних значень частоти величини:

де w =2p/T=2pf, то можна перевірити, що тепер співвідношення приймає дуже простий вид : x_i(n)=x(n)(-1)ⁿ, тобто просто використовується зміна знаку, що чергується.

НЧ–фільтрація початкового сигналу x(n) дає дискретний сигнал x1(n), який відповідає смузі [0,w_С/2] початкового спектру, тоді як фільтрація нижніх частот сигналу x(n)(-1)ⁿ дає дискретний сигнал x₂(n), що відповідає смузі [w_M/2, w_M] початкового спектру, зсунутий і переставлений у смугу частот [0,w_M/2].

Описаний крок можна застосувати знову до сигналів x1(n) i x2(n), розглядаючи тільки один з двох послідовних відліків ( тобто виконуючи децимацію - проріджування відліків), і попереднє співвідношення буде надалі вірним, якщо використовується зсув частоти, рівний . Тоді можна отримати 4 смуги. Таким чином, цей метод може розділити спектр сигналу на число смуг, що швидко зростає. На рис. нижче наведена деревоподібна структура цього методу, де f_m≤w_m/2p. Якщо виконується r послідовних кроків, отримується 2^r смуг.

дискретного сигналу і одного ЦФ нижніх частот.

Хвилькове перетворення одновимірного сигналу x(n) – це описаний вище розклад його на компоненти, кожна з яких відповідає за певну частотну смугу в спектрі початкового сигналу. Кожна з компонент, яка також є одновимірним сигналом, може розкладатися далі або ж розклад може бути припинено.

 

Рис.8.5.

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

Аналогічно хвилькове перетворення для двовимірного сигналу (зображення) x(n₁,n₂) –це розклад його на двовимірні компоненти, кожна з яких відповідає за певну частотну область в спектрі початкого зображення. У цьому разі для реалізації хвилькового перетворення слід використовувати двовимірні цифрові фільтри. Кожна з компонент, яка є двовимірним сигналом, може розкладатися далі або ж розклад можна зупинити.

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

На рис. показано так зване класичне (або логарифмічне) трирівневе хвилькове перетворення популярного тестового зображення Lena. При такому перетворенні на кожному рівні претворення, починаючи з другого, далі розкладаємо лише низькочастотну компоненту. Рівень 1 (розміру 512х512) – однорівневий хвильковий розклад початкового зображення Lena з рівня 0. Рівень 2 (розміру 256х256) показує однорівневе хвилькове перетворення низькочастотної компоненти з рівня 1. Рівень 3 (розміру 128х128) дає однорівневе хвилькове перетворення низькочастотної компоненти з рівня 2.

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

Як базовий інструмент для розкладу сигналів, хвилькові перетворення можуть розглядатися як дуальні до більш звичних методів аналізу Фур’є. Аналіз Фур’є пов’язаний з інтуїтивним інженерним поняттям „спектру” або „частотного змісту” сигналу. Аналіз на основі хвилькових перетворень, на противагу, пов’язаний з інтуїтивним поняттям „роздільної здатності” або „масштабування” сигналу. На функціональному рівні, Фур’є-аналіз співвідноситься з хвильковим аналізом як спектральні аналізатори у порівнянні з мікроскопами.

Хвилькові перетворення витісняють більш звичний Фур’є-базовий метод у формі дискретного косинусного перетворення, що використовується у форматі стиску зображень JPEG-9. Новий стандарт стиску JPEG-2000 базується на хвилькових перетвореннях. На них грунтується і формат стиску зображень відбитків пальців (fingerprint), прийнятий ФБР(Федеральне Бюро розслідувань).

Рис.8.7. Три рівні класичного (логарифмічного) хвилькового перетворення кольорового зображення розміру 512х512

Рис.8.8. Отримані 10 компонент трирівневого класичного (логарифмічного) хвилькового перетворення

Візьмемо низькочастотну компоненту з верхнього рівня (рівень 3) трирівневого хвилькового перетворення з рис.. Ця компонента – проріджена (з коефіцієнтом 8²=64) та згладжена версія початкового зображення. Дуже простий шлях стиску – залишити вказану компоненту і викинути решта 9 компонент. Отримаємо степінь стиску даних 64:1. Зауважимо, що коли потрібно наближення до початкового зображення повного розміру, слід виконати інтерполяцію низькочастотної компоненти з коефіцієнтом 64. Це можна ефективно зробити за допомогою триступеневого інтерполюючого цифрового фільтра.

Користуючись іншими з решта 9 компонент можна покращити якість відтвореного зображення, як показано на рис.8.9.

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

Така властивість ідеально підходить, наприклад, для передачі зображень у мережі Інтернет. Як відомо, Інтернет – це неоднорідна mess, стосовно числа користувачів та їх обчислювальних можливостей і фактичних пропускних здатностей. Хвилькові перетворення забезпечують природний шлях задовільнити усіх користувачів: користувачам з обмеженими ресурсами можна передати зображення нижчої якості, в той час як користувачі з потужнішими ресурсами можуть використати їх, щоб отримати зображення кращої якості.

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