• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

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

Загальна характеристика функцій ШПФ.

Вхідні і вихідні дані - цілі 32р. комплексні числа, формат збереження наведений на рис.3

Діапазон вхідних даних зазначений у таблиці 3.

Розрядність коефіцієнтів перетворення - 8 біт (два варіанти представлення: 6 і 7 біт на одиницю)

Робота з даними - арифметика з фіксованою крапкою.

Вихідні дані розташовані в правильному порядку.

Таблиця 7.4. Продуктивність функцій прямого і зворотного ШПФ на процесорі NM6403

NM6403 cycle tіme=25 ns (40MHz)

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

Стиск даних у форматі JPEG-9 (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. Це ілюструється рис.8.1.

Рис.8.1.

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

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

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

P_ДКП=APA^T,

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

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

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

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

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

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

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

Спочатку виконується квантування значень ДКП. Для цього формується матриця 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) матриці дільників і заокруглються до найближчого цілого. Процес квантування описується наступним виразом: round(x(i,j)/ q(i,j)).

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

наведено далі:

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

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

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

34,45,7,0,-2,-4,-14,-15,-1,0,2,8,9,3,2,-1,-1,1,0,0,0,0,0,0,1,1,2,0,0,0,1,0,0,0,0,0,0,0,-3,-2,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

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

B(i):=А(i)-A(i-1), де i=2,3,4,…

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

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

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

Іншими словами при кодуванні серій нулів отримуємо пари типу (x,y), де x означає лічильник числа пройдених нулів, а y – чергове ненульове значення.

Так, послідовність

34,45,7,0,-2,-4,-14,-15,-1,0,2,8,9,3,2,-1,-1,1,0,0,0,0,0,0,1,1,2,0,0,0,1,0,0,0,0,0,0,0,-3,-2,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

буде згорнута в пари

(0,34)(0,45)(0,7)(1,-2)(0,-4)(0,-14)(0,-15)(0,-1)(1,2)(0,8)(0,9)(0,3)(0,2)(0,-1)

(0,-1)(0,1)(6,1)(0,1)(0,2)(3,1)(7,-3)(0,-2)

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис.8.2.

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

Степінь стиску в форматі JPEG - від 16:1 до 25:1 без помітної втрати якості.

Читайте також:

1. А. Розрахунки з використанням дистанційного банкінгу.
2. Алгоритм жорданових перетворень
3. Аудиторські ризики, пов’язані з використанням комп’ютерних інформаційних систем
4. Аутентифікація з використанням односторонніх функцій
5. Безпосереднє обчислення з використанням формули Ньютона-Лейбніца.
6. Бухгалтерській облік валютних операцій банку з використанням платіжних карток
7. Види і напрямки організаційних перетворень міжнародних корпорацій
8. Вплив всесторонннього стиску і температури на механічні властивості гірських порід
9. ГЕОМЕТРИЧНІ ПОБУДОВИ АКСОНОМЕТРИЧНИХ ЗОБРАЖЕНЬ
10. Демодуляція дискретних сигналів.
11. Джерело дискретних повідомлень і його ентропія
12. Діагностика в процесі метафоричної самопрезентації учасників АСПН з використанням «архетипу» тіста

Переглядів: 936