ПРЯМОКУТНА АПРОКСИМАЦІЯ(НАБЛИЖЕННЯ) ДИСКРЕТНОГО
ПЕРЕТВОРЕННЯ КОСИНУСА
Резюме
Ефективне виконання перетворення дискретного косинуса здійснюється в цьому документі.В побудові це використовується, як систола масиву процесора, який складається з прямокутних обертань. Кути цих обертань позначають ? EMBED Equation.3 . З відношенням щодо простого виконання VLSI реалізовано наближення DСТ. Наближення одержується шляхом використання приблизних прямокутних обертань. Тобто, точні обертання ? EMBED Equation.3 замінюють наближеними ~? EMBED Equation.3 , за допомогою чого обертання над ~? можна легко здійснювати, використовуючи прості переміщення і дії додавання . Використання наближених обертань гарантує ефективне виконання кожного обертання, а отже, і для всіх перетворень. Прямокутне перетворення зберігається, отже, також, можливе досконале перетворення. Коефіцієнти матриці перетворень наближені до високої точності, такі, що різницею до точності DCT можна знехтувати з відношенням до практичних застосувань.
EMBED Equation.3 I.Вступ
Дискретний Косинус Перетворень (DCT) [5, 8] є суттю багатьох алгоритмів для обробки сигналу. Це зумовлено фактом, що перетворення здається майже оптимальним, щоб встановити співвідношення між певними сигналами. Тому (DCT) має стійке місце в обробці зображень. Зображення зазвичай ділять в підблоках розміру 8х8 або 16х16,які потім перетворюють за допомогою (DCT).Перетворені підблоки квантуються і закодовуються, перед відправкою приймачу, де зображення відновлюється, використанням зворотного Дискретного Косинуса Перетворень (IDCT).З появою Високо Чіткого ТБ (HDTV) і його великої кількості зображень даних, що є важливим ніж колись, стискати дані без втрати інформації. Крім того HDTV вимагає обробки зображень даних в реальному часі, роблячи ефективним виконання, використованого алгоритму.
В цьому документі побудова для DCT, введена з використання систоли массиву процессора [1].Цей масив може використовуватись також для будь-якого іншого прямокутного(ортогонального) сигнального перетворення. Масив систоли виконує перетворення близько:n(n..1)/2 прямокутних перетворень. Кожен процесор повинен виконувати ортогональне перетворення. Прилад швидкого DCT буде альтернативним, але менш гнучким. Представлений підхід не є не повним виконанням перетворення, що є головним завданням, але реалізація прямокутного (ортогонального) обертання проводиться в кожному процесорі.
Для того, щоб досягти простого виконання цих обертань, точні обертання представляються наближеним рядом (послідовністю) з ?-обертань [7].Таким чином, точний кут може бути наближеним до довільної високої точності, за допомогою чого, незалежно від прямокутника, зберігається точність. ?-обертання можуть бути виконані з операціями зміни та додавання і, тому, гарантують просте виконання цілого наближеного обертання. Є три класи простих ?-обертань: один клас включає CORDIC обертання [2.9.10], які знаходять застосування в багатьох галузях. З трьома классами обертання, гнучкість є забезпеченою, який повинен експлуатуватися в порядку пошуку найкращого наближення з незначним зусиллям для підрахунку. Не тільки можливість здійснення DCT, але і представлення підходу може бути застосованим для іншого наближення сигналу перетворень (наприклад, хвиля наближених перетворень [7] або матриця розкладу (наприклад власне значення розкладу[3,4])).
Цей документ організований в наступному порядку: Параграф 2 угода з масивами систол процесора, побудова, використана, відповідно до, наближеного перетворення. Параграф 3 включає три класи ?-обертань, що використовуються для наближення точного обертання кутів. Параграф 4 дає приклад наближення простого виконання DCT розміру 8х8, що використовується у обробці зображень. Після порівняння наближення DCT з точним в секції 5 результати підсумовуються.
II.Масив систоли процесора для здійснення DCT
Ми використовуємо масив систоли процесора (Рис 1.) для розв`язування систем лінійних рівнянь за Боянчуком вцілому. Цей масив QR-розкладу може бути з будь-якою наданою матрицею. Для матриці nxn EMBED Equation.3 процесори, які виконують прямокутні перетворення є необхідними. Звичайно, DCT перетворення матриці С також може бути розкладеним з масивом, внаслідок чого обертання кутів ?` EMBED Equation.3 (1<=j<=n-1, j<i<=n) є необхідним. Тому, що матриця С розкладається на матрицю Q та матрицю R,що є рівносильним: матриці:
C=QR=QI.
Обробка матриці С і з відомим обертаннями приводить до тотожньої матриці:
EMBED Equation.3 EMBED Equation.3 С=I>Q=C
Обробляючи сигнальний вектор s з масивом, основаним на відомих обертаннях ? EMBED Equation.3 можна інтерпретувати як матрицю вектора добутку або як зворотне дискретне перетворення косинуса IDCT, що приводить до перетворення вектора t.
EMBED Equation.3 EMBED Equation.3 s=t> EMBED Equation.3 s=t
Кожне (orthonormal) матричне векторне множення можна виконати за допомогою EMBED Equation.3 обертань. Кути ? EMBED Equation.3 і ?` EMBED Equation.3 -одинакові, тільки індекси різні.
III.Класи ортонормальних обертань
Нехай ортонормальне ?-обертання буде визначено матрицею W, яка є результатом прямокутних перетворень W` і вимірюючого фактора r.

де вимірюючий фактор r отримується з:

Кут ? EMBED Equation.3 EMBED Equation.3 цих ?-обертань обчислюються:

З поваги до кваліфікованого виконання ми повинні вибрати коефіцієнти c`та s` настільки прості, наскільки це можливо. Також, вимірюючий фактор r повинен бути виконаний з малою кількістю переміщень і дій додавання. Ціна, яку нам доведеться заплатити за простоту ?-обертань є те, що тільки обмежений набір ?-обертань кутів є доступним.Є декілька можливостей, які приводять до класів таких протсих ?-обертань.Вони були показані також у [3,7].
Класс I є одним ?-обертанням CORDIC [2,9,10]. ?-обертання цього классу дістаєтся з:

З цими ?-обертаннями кут може бути поданий:

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

Кути
можуть бути реалізовані з цими ?-обертаннями.
Клас III баується на , де для більш маленького і різниця до стандартних обертань (клас I) є більш значною ніж для більшого і.

Тільки спеціальні кути
можуть бути реалізовані.
Просте виконання ортогонального обертання гарантується для всіх трьох класів, як матричні входи, обчислені за допомогою переміщень і дій додавання.Щоб уникнути обчислення квадратного кореня у вимірюючомк чинникові, два ?-обертання з такими ж вимірюючими факторами повинні комбінуватися. З трьох класів один не обов`язково використовувати з однаковими ?-обертаннями двічі (як у [4]), якщо є можливість об`єднання обертань різних класів.Розкладання на множники вимірюю чого чинника цілого обертання може здійснюватись з малою кількістю переміщень і дій додавання.

Звичайно, k-залежить від класів ?-обертань
для класу I, k=i.
для класу II, k=2i+2
для класу III, k=3i+3
IV.Представлення дискретного перетворення косинуса з наближеними обертаннями.
DCT потребує EMBED Equation.3 обертань, за допомогою чого, кожен кут ? може бути необхідним.Тому, багато множень можуть бути необхідними для здійснення точних обертань.У параграфі 3 були представлені методи, як спеціальні обертання можуть виконуватись тільки з перестановками та діями додавання.. Необхідні обертання масиву систоли можуть бути наближені до продукту обговорених обертань і , наскільки це стосується DCT Точний кут ?, наближений до суми кутів
, що приводить до за допомогою чого, різниця повинна бути мінімізованою настільки, як необхідна кількість кутів .

Як приклад, ми показуємо наближення не для всіх 28 обертань Рис1., тільки для .З наступним наближенням, різниця кутів може бути зменшеною до , використанням представлення кутів з параграфа 3.Тут необхідні лише декілька простих ?-обертань.

Вимірюючи чинники та комбінуються до 1/(1+2 EMBED Equation.3 ).Якщо ми пропонуємо довжину слова з 32 бітів,то обертання не створюють вимірюючого чинника, тому що
.Вимірюючий фактор розкладений на множники відповідно до (1).Результуюча структура з Рис 2., яка реалізує обертання є хорошим наближенням до точного обертання з .Всі кути обертання наближені подібним чином, що призводить до хорошого наближення цілого DCT. Чим більше ?-обертань використано, тим краща точність наближення DCT. Але,звичайно зі збільшенням числа ?-обертань також збільшується обчислювальна складність.В залежності від складності нашого обчислювального прикладу, виконання наближення обертання потребує 18 переміщень та дій додавання, під час точного обертання необхідно 128 переміщень і дій додавання (вважаємо, що одне обертання складається з 4 множень і одне множення довжнини слова з 32 бітів складається з 32 переміщень і дій додавання ).Як обчислювані зусилля всіх обертань до представленого прикладу, так і відношення між точними і наближеними обертаннями косинуса є подібними.
V.Порівняння точного і наближеного DCT
Постає питання наскільки доюрим є результат наближення DCT.Причиною використання DCT в обробці зображень є те, що це перетворення є майже оптимальним для стиснення даних.Для наших тестів, зображення «Lena», розміру 224х224 поділене на 784 блоки, розміру 8х8.Блоки перетвореного косинуса з точним і наближеним і енергія стиснення обох перетворень є порівняними. Норми блоків 2х2 і 4х4, які містять більш значну прохідну інформацію є проаналізованими (верхня ліва сторона в перетвореній області, Рис.3). є нормою блоків 2х2 після точного DCT, є нормою блоків 2х2 після наближеного DCT, є нормою блоків 4х4, після точного DCT, є нормою блоків 4х4, після наближеного DCT.Як бачимо, значення обертань і
є близькими до 1, енергія стиснення апроксимованого DCT є такою ж доброю як і енергія наближеного DCT.На рис.3 бачимо, що для 784 блоків зображень відхилення є (відмінними) від 1.Для від`ємних значень і (Рис.3) , можемо бачити, що енергія стиснення для наближеного DCT є навіть кращою, ніж для точного DCT.В загальному, енергія стиснення наближеного DCT є такою ж як і енергія стиснення точного DCT, підтримуючи використання простого виконання наближеного DCT.
V.Висновок
У цьому документі було представлено метод для наближення DCT, щоб здійснити просте виконання, реалізоване тільки з допомого переміщень та дій додавання. Послідовність різниці класів ?-обертань використовується для наближення точних обертань, це показано у масиві систоли, що реалізовує дискретне перетворення косинуса. Ця різниця класів робить можливим точне наближення всіх кутів з малою кількістю ?-обертань.Чим більше ?-обертань необхідно, тим кращою буде точність. При (ortonormality) зберігається точність, але є незначні відхилення між коефіцієнтами оберненої матриці і матриці .Це може бути показане, але в практичному застосування цими різницями можна нехтувати. Представлений метод наближення може бути розширений до інших побудов, використовуючи DCT. Побудови для швидкого DCT також базуються на прямокутних (ортогональних) обертаннях блоків,що можуть бути виконанні, використанням наближених обертань. В цьому документі використовується обговорення масиву систоли, починаючи з цього шляху поширюється на всі прямокутні (ортогональні) перетворення сигналів.









Рис1.Масив систоли процесора виконання DCT

Рис2.Структура одного процесора, що здійснює одне обертання перетворення.

Рис3.Порівняння енергії стиснення точного і наближеного DCT.