Паралельні і послідовні структури вейвлет-процесорів

Размещено на http://www.allbest.ru

Паралельні і послідовні структури вейвлет-процесорів

кандидат технічних наук, доцент, Ломоносов Ю. В.

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

Ключові слова: Вейвлет аналіз, паралельні і послідовні структури обробки даних, вейвлет-процесори.

вейвлет процесор дані

PhD, Associate Professor, Lomonosov Yu. V. Parallel and serial structures of wavelet processors/ Yaroslav Mudryi National Law University, Ukraine, Kharkiv

Possible variants of construction of wavelet transformer processor structures for realization of methods of image compression of different physical nature are considered. The problem of analysis and selection of a set of promising characteristics and criteria that must meet the structures and algorithms of digital processors wavelet signal processing, as well as the construction of these structures and algorithms in practice. The development of modern wavelet processor structures will be able to ensure the powerful development of multimedia data processing systems and provide a further level of research into new methods of high-quality data compression.

Keywords: Wavelet analysis, parallel and serial data processing structures, wavelet processors.

Вступ

Стрімкий розвиток систем мультимедійних даних в мережі Internet зумовили актуальність досліджень нових методів високоякісної компресії сигналів різної фізичної природи, а також створення апаратних платформ для них. Причому провідне місце серед цих методів належить алгоритмам з використанням вейвлет- перетворень. [1, c. 125-131; 2, с. 280-283; 3, с. 173-176]. Однак кількість публікацій, що стосуються апаратної реалізації вейвлет- перетворень вельми обмежена [4, с 27-36].

Постановка задачі. На сьогоднішній день досить актуальною бачиться завдання аналізу і вибору сукупності перспективних характеристик і критеріїв, яким повинні відповідати структури і алгоритми цифрових процесорів вейвлет-обробки сигналів, а також побудова цих структур і алгоритмів. [5, с. 845-849]

Данні дослідження. На практиці методи обробки даних з використанням вейвлет-аналізу спираються на швидкі алгоритми, запропоновані Малла [4, с 27-36]. В обчислювальному аспекті ці алгоритми зводяться до знаходження двох пар квадратурних дзеркальних фільтрів, вимоги до яких складаються в симетричності і максимальної гладкості.

При цьому фільтри що розкладають та відновлюють дані визначаються за формулами, наведеними нижче, а пара фільтрів при n = 1 та m = 2, на рис. 1.

Рис.1. Розкладаючий і поновлюючий фільтри

Вираз для отримання k - го вей влет-коефіцієнта W (k) з використанням поновлюючих і розкладаючих фільтрів (1) можна записати наступним чином

Таким чином, на основі аналітичного опису вейвлет- перетворення необхідно побудувати апаратні реалізації і провести їх кількісний і якісний аналіз. Використовуючи вирази для визначення (вейвлет) W- коефіцієнтів (2), схему, що реалізовує "гілку" обчислення, можна представити таким чином (рис. 2.). У даній схемі (N=8) видно, що результати обчислень першого ярусу процесорів послідовно і локально передаються ("проштовхуються") процесорам другого ярусу і так далі, поки не буде набуті значень всіх w- коєфіцієнтів, або процедура вейлет-перетворення вихідного сигналу не буде зупинена на якому-небудь рівні розкладання.

У даній схемі (N=8) видно, що результати обчислень першого ярусу процесорів послідовно і локально передаються ("проштовхуються") процесорам другого ярусу і так далі, поки не буде набуті значень всіх w-коєфіцієнтів, або процедура вейлет-перетворення вихідного сигналу не буде зупинена на якому-небудь рівні розкладання.

Рис. 2. Структурна схема обчислення вейлет-коєфіцієнтів

Для отримання H і G коефіцієнтів (рис. 2.) можна запропонувати наступні схеми процесорів (рис. 3.).

Рис. 3. Схеми H і G процесорів

Кількість устаткування таких процесорів визначається тривалістю розкладаючого і поновлюючого фільтрів (l і n). Це обумовлено процедурою згортання оброблюваного сигналу з відповідним фільтром при обчисленні к-го вейвлет-коєфіцієнта (2). Кількість відліків розкладаючого фільтру (рівне l) визначає кількість помножувачів процесора H, а кількість відліків поновлюючого фільтру G (рівне n) відповідно процесора G. Окрім цього кожен з процесів містить суматор накопичувального типа. Таким чином, кількість обладнаня процесора H рівна (l+1), а процесора G - (n+1) відповідно.

Введемо наступні основні характеристики і показники, яким повинні відповідати проектовані сучасні цифрові процесори обробки сигналів. Це: однорідність, регулярність, локальність і рекурсивність (архітектура систоли); продуктивність і об'єм устаткування, надмірність або ефективність процесорного поля; надійність і час проектування [2, с. 280-285].

Важливими характеристиками паралельних структур вейвлет- перетворень для цифрової обробки сигналів є продуктивність P і об'єм устаткування Q, які визначимо відповідно як

Pnap. = 2( N - 1)*(l + n + 2)/2 log N

Q = 2(N - 1)*(l + n + 2) (3)

Тут Рпар визначає умовний час, за який паралельна структура реалізує обчислення 2(N -1) * (l + n + 2) арифметичних операцій того або іншого вейвлет-алгорітму, 2*logN - кількість тактів виконання всіх операцій, Q - кількість процесорних елементів цієї структури.

Для порівняльної оцінки множини варіантів архітектур цифрових процесорів доцільно використовувати оцінку питомої продуктивності

де P і Q були визначені вище. Питому продуктивність "V" поряд з продуктивністю "Р" можна використовувати як важливий критерій порівняння структур вейвлет-перетворень з паралельною, послідовною і умовно-послідовною (послідовно-паралельною) архітектурою процесора.

Найбільш інформативною характеристикою паралельного алгоритму є прискорення (L), що показує у скільки разів використання паралельного алгоритму зменшує час виконання завдання в порівнянні з послідовним алгоритмом. В той же час слід ввести і характеристику (A), яка показує, у скільки разів устаткування паралельного процесора перевищує об'єм устаткування послідовного:

де Т - кількість тактів для здобуття вейвлет-коєфіцієнтів в послідовній і паралельній структурі процесора.

Для визначення апаратної надмірності вводиться коефіцієнт завантаження устаткування "R", який показує відношення сумарного числа працюючих процесорів (М) до непрацюючих (М*) при кожному такті рішення задачі і в цілому після її завершення:

Для N=32 значення коефіцієнтів R, M і M* приведені в таблиці 1.

Таблиця 1.

Значення коефіцієнта завантаження устаткування вейвлет- процесора (N=32, i=1, 2, 3, 4, 5)

R* - визначає відношення числа працюючих процесорів, на кожному етапі обчислення w-коєфіцієнтів, до їх загального числа, тобто - Q.

Аналіз таблиці 1 показує дуже низький коефіцієнт завантаження устаткування в паралельних вейвлет-структурах. Надмірність структур пов'язана з коефіцієнтом завантаження устаткування R зворотною залежністю, тобто, чим менше R, тим більше надмірність.

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

На рис. 4. представлена послідовна структура обчислення вейвлет коефіцієнтів. Приведена схема здійснює обчислення w- коєфіцієнтів з використанням фільтрів (h і g) згідно з виразами (2) з подальшим їх зберіганням у відповідних ОЗП. Регістри здвигу (RG) забезпечують зберігання і синхронну видачу оброблюваних відліків на вхід помножувача при дії сигналів, що управляють, з блоку управління (Блок Упр.). Самі фільтри зберігаються в банці фільтрів і їх відліки поступають на другий вхід помножувача, так само під впливом сигналів блоку управління (Блок Упр.). Суматор накопичувального типа акумулює результат роботи помножувача і передає отримані w-коєфіцієнти в ОЗП.

Таким чином, послідовно обчислюються дві групи w-коєфіцієнтів (Wh і Wg), див. рис.2. Далі група коефіцієнтів Wh через регістр здвигу поступає на вхід схеми для обчислення наступного ярусу (етапу) розкладання а група коефіцієнтів Wg запам'ятовується в ОЗП.

Умовно-послідовна структура представлена на рис. 5. Ця структура відрізняється від послідовної схеми тим, що обчислення к- го w-коєфіцієнта відбувається паралельно по всьому набору відліків розкладаючого (H) або поновлюючого (G) фільтру. Але при цьому послідовно обчислюються спочатку одна група w-коєфіцієнтів (Wh або Wg) із застосуванням відповідного фільтру (H або G), а потім інша.

Рис.4. Послідовна структура вейвлет-перетворень

Далі аналогічно послідовній структурі виконується запис w- коєфіцієнтів у відповідні ОЗП і обчислення w-коєфіцієнтів наступного ярусу розкладання сигналу.

Рис. 5. Умовно-послідовна структура процесорів W-

перетворень

На рис. 6. представлена базова двопроцесорна структура побудови оптимальних обчислювачів w-коєфіцієнтів.

У даній схемі обчислення кожної групи w-коєфіцієнтів (Wh і Wg) здійснюється незалежно процесорами H і G відповідно, рис. 3. В разі нарощування даної схеми процесорами H і G можна перейти до чотирипроцесорної структури, далі до восьмипроцесорної і так далі.

Висновки

За результатами дослідження було встановлено, що питома продуктивність паралельної структури W-процесора із зростанням довжини оброблюваної вибірки падає. Це визначається високою надмірністю і низьким коефіцієнтом завантаження устаткування. Ця обставина може бути використана при виборі оптимальної тривалості N вибірок оброблюваного сигналу або визначення оптимального рівня "занурення" (вибір кількості ярусів розкладання сигналу) так, щоб забезпечити прийнятну міру завантаження процесорів паралельних структур.

Рис.6. Базова двопроцесорна структура обчислення W- коєфіцієнтів.

Питома продуктивність усіх квазіпослідовних структур із зростанням N зростає, окрім послідовної, питома продуктивність, якою є величина постійна внаслідок того, що відношення кількості операцій до кількості тактів від тривалості оброблюваної вибірки не залежить, а кількість устаткування також є постійною характеристикою і не залежить від N. Найкращій показник питомої продуктивності має двопроцесорна структура, це пояснюється високою мірою завантаження устаткування W-процесорів при зростанні вхідної вибірки (N), що забезпечує її ефективність.

Отримані в роботі результати і висновки дозволяють на практиці будувати різну архітектуру процесорів W-перетворень сигналів,

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

Література

Д. Ватолин, А. Ратушняк, М. Смирнов (2002). Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. Диалог-Мифи, 384.

Миано Дж. (2003). Форматы и алгоритмы сжатия изображений в действии. Триумф, 336.

Уэлстид С. (2003). Фракталы и вейвлеты для сжатия изображений в действии. Триумф, 320.

Ivanov, V.G., Lyubarskiy, M.G., Lomonosov, J.V. (2007). Cutting of content redundancy of images on the basis of classification of objects and background. Journal of Automation and Information Sciences. Begel House Inc., 39 (5), 27-36.

Гонсалес, Р., Вудс, Р. (2012). Цифровая обработка изображений. Техносфера, 1104.

References

D. Vatolin, A. Ratushnjak, M. Smirnov (2002). Metody szhatija dannyh. Ustrojstvo arhivatorov, szhatie izobrazhenij i video. Dialog-Mifi, 384. [in Russian].

Miano Dzh. (2003). Formaty i algoritmy szhatija izobrazhenij v dejstvii. Triumf, 336. [in Russian].

Ujelstid S. (2003). Fraktaly i vejvlety dlja szhatija izobrazhenij v dejstvii. Triumf, 320. [in Russian].

Ivanov, V.G., Lyubarskiy, M.G., Lomonosov, J.V. (2007). Cutting of content redundancy of images on the basis of classification of objects and background. Journal of Automation and Information Sciences. Begel House Inc., 39 (5), 27-36. [in English].

Gonsales, R., Vuds, R. (2012). Cifrovaja obrabotka izobrazhenij. Tehnosfera, 1104. [in Russian].

Размещено на Allbest.ru