asyan.org
добавить свой файл
1 2 3
Проектування комп’ютерних засобів цифрової обробки сигналів та зображень”

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

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

Стиск даних у форматі JPEG (Joint Photographic Experts Group), який дозволяє стискати окремі (незмінні, still picture) зображення, можна умовно розбити на три етапи:

1-й етап - перетворення та субдискретизація кольорової інформації;

2-й етап – поблокові дискретні косинусні перетворення;

3-й етап – квантування та кодування значень дискретного косинусного перетворення.

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

Кожна точка зображення, представлена 3 байтами в системі RGB, переводиться в систему YUV (яскравість, кольорова насиченість, кольоровий тон) згідно виразів:
Y=77/256*R+150/256*G+29/256*B

U=131/256*R-110/256*G-21/256*B+128

V= -44/256*R-87/256*G+131/256*B+128

або в матричному вигляді



Перетворення з системи YUV в систему RGB виконується за формулами:

R=Y+1.37*(U-128)

G=Y-0.698*(U-128)-0.336*(V-128)

B=Y+1.73*(V-128)

або в матричному вигляді



Далі значення компоненти Y залишаються без зміни, а число значень компонент U і V зменшується (так звана субдискретизація; компоненти U і V можна загрубити без суттєвої втрати якості зображення). Можливі різні варіанти субдискретизації: просте викидання частини з сусідніх точок чи заміна значень сусідніх точок зображення на їх середні. При цьому можливі кілька варіантів об'єднання точок: дві по горизонталі, дві по вертикалі, квадрат з чотирьох сусідніх точок. Найчастіше використовується наступний варіант: число точок зменшується вдвоє, причому значення точок обчислюються згідно з виразом

y(n)=1/4*x(n-2)+1/2*x(n-1)+1/4*x(n).

При цьому блок 8Х16 значень компоненти U або V перетворюється в блок 8Х8 значень.

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

x(n)=[y(2n)+y(2n-1)]/2.

Якщо використовується описаний варіант субдискретизації, то досягається стиск зображення в 1,5 рази. Дійсно 1 байт компоненти яскравості залишається без змін, а кожні 2 байти компонент U і V заміняються на 1 байт. Отже, замість 6 байт на кожних 2 точки зображення тепер припадає 4 байта. Якщо використовується варіант об'єднання чотирьох сусідніх точок, то досягається стиск зображення в 2 рази. Адже 1 байт компоненти яскравості залишається без змін, а кожні 4 байти компонент U і V заміняються на 1 байт. Тобто, замість 12 байт на кожних 4 точки зображення тепер припадає 6 байт.

Мінімальний фрагмент інформації для обробки – це блок початкового RGB зображення розміру 8Х16 елементів. У результаті обробки такого фрагменту на першому етапі отримуємо чотири блоки розміру 8Х8: два блоки розміру 8Х8 для компоненти яскравості Y та по одному блоку розміру 8Х8 для компонент U і V. Це ілюструється наступним рисунком.

Другий етап має в своїй основі дискретне косинусне перетворення (ДКП).

Кожна з компонент Y,U,V зображення на цьому етапі розглядається як окреме монохромне (однокольорове) зображення і її стиск проводиться окремо.

Зображення розбивається на блоки 8Х8 елементів. До кожного блоку P застосовується двовимірне ДКП

PДКП=APAT,

де А - матриця двовимірного ДКП,

PДКП - матриця значень ДКП фрагменту зображення.

П
ряме ДКП задається наступним виразом

а обернене ДКП задається формулою





де для i=0 та c(i)=1 для i=1,2,…,7.

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


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

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

Спочатку виконується квантування значень ДКП. Для цього формується матриця Q дільників з елементами q(i,j)=1+(1+i+j)r,i,j=0,1,…,7; r- параметр, який впливає на якість зображення, що отримуємо при відтворенні. Для компонент Y рекомендується брати r=2, а для компонент U,V значення r може бути більшим. q(i,j) це не що інше як крок квантування, який залежно від позиції змінюється. При русі від верхнього лівого кута до правого нижнього кута крок квантування збільшується, тобто виконується грубіше квантування.

При r=2 матриця дільників має вигляд


Значення x(i,j) матриці PДКП діляться на відповідні значення q(i,j) матриці дільників і заокруглються до найближчого цілого. Процес квантування описується наступним виразом:

Q(x(i,j),i,j)=round(x(i,j)/q(i,j)).

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


Кодування матриці квантованих елементів ДКП проводиться по шляху, показаному послідовними номерами (так званий зигзаг або змійка; у напрямку збільшення значень елементів матриці дільників).


Інакше кажучи, переводимо матрицю 8х8 в 64-елементний вектор за допомогою ’’зігзаг’’- сканування, тобто беремо елементи з індексами (0,0), (0,1), (1,0), (2,0), ...


Таким чином, на початку вектора ми дістаємо коефіцієнти матриці, які відповідають низьким частотам, а в кінці – високим частотам.

До коефіцієнтів ДКП, які знаходяться на першому місці (DC коефіцієнти) в послідовних матрицях розміру 8Х8 для кожної з компонент Y,U,V, застосовується дельта імпульсно-кодова модуляція:

DC(1):=DC(1); DC(i):=DC(i)-DC(i-1), де i = 2,3,4,…

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

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

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

Іншими словами при кодуванні серій нулів отримуємо пари типу (x,y), де x означає лічильник пропущених нулів, а y – значення, яке потрібно поставити в наступну комірку. Так, вектор 42 3 0 0 0 -2 0 0 0 0 1 ... буде згорнутий в пари (0,42)(0,3)(3,-2)(4,1) ... .

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

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


елемент

кодове слово

0

1

+1

0100

-1

0101

+2

0110

-2

0111

+3

00100

-3

00101

+4

00110

-4

00111

+5

0001000

-5

0001001

+6

0001010

-6

0001011

+7

0001100

-7

0001101

+8

0001110

-8

0001111

|D|>8

00001+8розрядів значення D


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

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

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

При відтворенні зображення виконуються наступні дії, зворотні до дій при стиску:

- декодування Хафмена та декодування серій нулів;

- деквантування (множення на відповідні значення елементів матриці дільників);

- обернені двовимірні ДКП блоків 8Х8 елементів;

- обернена кольорова субдискретизація (відтворення проміжних точок для компонент U,V шляхом інтерполяції між сусідніми точками);

-перехід від системи YUV до системи RGB.

Етапи стиску та відтворення даних при використанні формату JPEG показані на рис.


Рис.

«+» - втрат немає «–» - втрати є

Степінь стиску в форматі JPEG - від 16:1 до 25:1 без помітної втрати якості.
Стиск нерухомих зображень з використанням хвилькових перетворень
Поняття хвилькового перетворення
Дискретне хвилькове перетворення (dyscrete wavelet transform (DWT)) принципово відрізняється від спектральних перетворень.

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


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


...
ω

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

Метод, що пропонується, відповідає використанню одного єдиного цифрового фільтру низьких частот і зсуву в частотній області спектру дискретного сигналу шляхом множення вхідних даних на експоненціальний множник. Якщо до спектру X(w) дискретного сигналу застосувати зсув частоти на величину wi , щоб отримати X (w-wi), то одержаний спектр буде відповідати новому дискретному сигналу виду (Т- інтервал дискретизації).
xi(n)= x(n) e 2 jnw iT (1)

де Т ≤ .

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

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

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

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

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

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

рис.





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

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

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

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

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

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

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

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

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

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

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

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

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

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



следующая страница >>