Вибір перетворення

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

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

для Аналогічним чином, зображений може бути отримано за заданим за допомогою зворотного перетворення

для . Функції і в даних рівняннях називаються, відповідно, ядром прямого і ядром зворотнього перетворення. З причин, які будуть ясні нижче, їх також називають базисними функціями або базисними зображеннями. Набір для в рівнянні (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.29 показано ядро ​​для N = 4. Кожен блок складається з 4x4 = 16 елементів; білий колір означає +1, а чорний означає -1. Щоб сформувати лівий верхній блок необхідно покласти і обчислити значення для . Всі значення в цьому випадку дорівнюють +1. Другий блок у верхньому ряду є набір значень для , і так далі. Як уже зазначалося, важливість перетворення Уолша Адамара полягає в простоті реалізації - значення всіх елементів в його ядрі дорівнюють або +1 або -1.

Рис. 1.29. Базисні функції Уолша-Адамара для N = 4. Початок координат кожного блоку знаходиться в його лівому верхньому куті.

Одним з найбільш часто використовуваних перетворень для стиску зображень є дискретне косинусне перетворення (ДКП). Воно виходить шляхом підстановки в (1.5-24) і (1.5-25) наступних (однакових) ядер:

де

і аналогічно для . На Рис. 1.30 показані базисні функції для випадку . Результати представлені в тому ж форматі, що і на Рис. 1.29, за винятком того, що значення не є цілими. Світліші рівні яскравостей на Рис. 1.30 відповідповідають великим значенням .

Рис. 1.30. Базисні функції дискретного косинусного перетворення для N = 4. Початок координат кожного блоку знаходиться в його лівому верхньому куті.

Приклад 1.19. Трансформаційне кодування з використанням ДПФ, ПУА і ДКП, і усіканням коефіцієнтів.

На Рис. 1.31 (а), (в) і (д) показані три наближення напівтонового зображення розмірами 512x512 елементів (Рис. 1.23). Ці результати були отримані розбиттям вихідного зображення на блоки розмірами 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.31. Наближення зображення на Рис. 1.23 за допомогою перетворення з усіканням коефіцієнтів: (а) Фур'є, (в) Уолша-Адамара, (д) ​​косинусного, а також зображення відповідних посилених помилок.

Ця інтерпретація стане ясніше, якщо записати (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.32 (а), призводять до появи помітної високочастотної складової. При усіканні або квантуванні коефіцієнтів ДПФ, прикордонні елементи блоків через явища Гіббса приймають невірні значення, що призводить до виникнення блокових спотворень. Таким чином, межі між сусідніми блоками стають помітними через те, що прикордонні елементи блоків приймають спотворені значення. ДКП представлене на Рис. 1.32 (6), зменшує цей ефект, тому що його періодичність у 2 n точок не призводить до розривам на кордонах блоку. Перевагою ДКП є також і те, що воно реалізоване в інтегральних мікросхемах.

а)

б)

Рис. 1.32. Періодичність, притаманна одномірним (а) ДПФ і (б) ДКП.

Поиск по сайту: