Міністерство транспорту України

Українська державна академія залізничного транспорту

Бохан Костянтин Олександрович

УДК 621.327: 681.5

СПОСОБИ ТА ЗАСОБИ ДВОВИМІРНОГО
ПЕРЕТВОРЕННЯ ЗОБРАЖЕНЬ В БАЗИСІ ХААРА

05.12.02 "Телекомунікаційні системи та мережі"

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня
кандидата технічних наук

Харків – 2003

Дисертацією є рукопис.

Робота виконана в Харківському військовому університеті

Науковий керівник: | кандидат технічних наук, професор
Корольов Анатолій Вікторович, професор кафедри "Системи управління та зв’язку" Харківського військового університету Міністерства оборони України, м. Харків.

Офіційні опоненти: - | доктор технічних наук, професор
Краснобаєв Віктор Анатолійович,
професор кафедри "Автоматизації та комп'ютерних технологій" Харківського державного технічного університету сільського господарства Міністерства аграрної політики України, м. Харків;

- | кандидат технічних наук,
Бараннік Володимир Вікторович,
старший науковий співробітник відділу ІОЦ, Харківського військового університету Міністерства оборони України, м. Харків.

Провідна установа | Харківський національний університет радіоелектроніки, кафедра “Безпеки інформаційних технологій”, Міністерство освіти і науки України,
м. Харків.

Захист відбудеться “ 24 ” 06 2003 р. о “ 13 ” годині на засіданні спеціалізованої вченої ради Д .820.01 при Український державній академії залізничного транспорту за адресою:

Україна, 61050, м. Харків, майдан Фейєрбаха, 7.

З дисертацією можна ознайомитись в бібліотеці академії.

Відгук на автореферат просимо надсилати за адресою:
Україна, 61050, м. Харків, майдан Фейєрбаха, 7.

Автореферат розісланий “ 22 ” 05 2003 р.

Вчений секретар

спеціалізованої вченої ради

к.т.н., доцент М.В. Книгавко

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. На етапах формування, передачі, аналізу та відображення відеоінформація піддається різним видам цифрової обробки: фільтрації, стиску, реставрації, розпізнаванню й ін. Наприклад, застосування методів стиску дозволяє зменшити час передачі відеоінформації по каналах зв'язку, знизити вимоги до їх пропускної здатності. В більшості процедур цифрової обробки відеоданих використовуються різні ортогональні перетворення (ОП) (Фур'є, Уолша, Хаара, ДКП і ін.). При цьому на їх виконання може знадобитися до 90 % часу, необхідного для виконання всієї процедури обробки зображення.

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

Значний внесок у рішення зазначених проблем внесли багато вчених. Серед них Александров В.В., Зубарєв Ю.Б., Котельников В.А., Красильников Н.Н., Онищенко Ю.О., Поляков П.Ф., Хараташвілі Н.Г., Кунт М., Претт У.К. Ахмед Н., Рао К.Р., Хуанг Т.С., Виноград С., Ендрюс Г., Кулі Дж.У., Садихов Р.Х., Соболєв Ю.В. і ін.

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

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

Зв'язок з науковими програмами, планами, темами. Дослідження в дисертаційній роботі проводилися у відповідності з наступними нормативними актами:

1. Концепцією розвитку Єдиної національної системи зв'язку України
до 2010 р.

2. Завданнями Національної програми інформатизації України на 2000 – 2005 р.

3. Законом про зв'язок.

4. Планами НДР МО України, ХВУ.

Основні результати дисертаційної роботи використані в 4-х науково-дослідних роботах: шифри “Око-2” (звіт №3759, інв. №12197), “Куб” (звіт №3816, інв. №13076), “Тор” (звіт №3822, інв. №13078), “Мрія” (звіт №3824, інв. №13077).

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

Відповідно до поставленої мети необхідно вирішити наступні задачі досліджень:

1. Розробити одноетапний спосіб двовимірного перетворення Хаара.

2. Розробити двовимірний цілочисловий базис Хаара, метод його формування та спосіб цілочислового двовимірного перетворення Хаара.

3. Розробити швидкі алгоритми прямого та зворотного двовимірного перетворення Хаара.

4. Розробити програмну, апаратну і програмно-апаратну реалізацію розроблених способів і алгоритмів.

5. Розробити спосіб субоптимальної фільтрації на основі двовимірного цілочислового перетворення Хаара.

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

Об'єкт досліджень. Підсистеми обробки і передачі інформації телекомунікаційних систем.

Предмет досліджень. Обробка зображень в телекомунікаційних системах.

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

Наукова новизна отриманих результатів дисертаційної роботи полягає в наступному:

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

2. Вперше запропоновані цілочисловий двовимірний базис Хаара (ЦДБХ) і метод формування ЦДБХ на основі двовимірного базису Хаара. Цілочисловий двовимірний базис Хаара відрізняється від відомих тим, що складається з двовимірних базисних функцій, які приймають цілочислові значення на інтервалі визначення.

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

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

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

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

Практична значимість отриманих результатів. Практична значимість отриманих результатів полягає в наступному:

1) розроблені способи й алгоритми двовимірного перетворення Хаара дозволяють: зменшити час виконання ортогонального перетворення зображень в 2?5 рази; зменшити величину середньоквадратичного відхилення (СКВ) відновлених зображень у 1,5?2 рази; рівнобіжно виконувати більшість арифметичних операцій перетворення; одержувати необхідні коефіцієнти без обчислення всіх інших; зменшити витрати оперативної пам'яті при виконанні перетворень на 30%; спростити технічну і програмну реалізацію двовимірних ортогональних перетворень;

2) запропоновано спосіб субоптимальної вінеровської фільтрації, який дозволяє зменшити час виконання субоптимальної фільтрації зображень у 2?5 рази і значно спростити технічну реалізацію вінеровського фільтра;

3) розроблений спосіб зонального стиску зображень при допустимих значеннях СКВ забезпечує стиск реалістичних зображень в 2 ? 20 разів. Час, що необхідний для виконання процедур стиску і відновлення зображень, в 4 ? 5 рази менше, ніж при використанні зонального стиску на основі дискретно-косінусного перетворення.

Розроблені програмне забезпечення та пристрої, в яких реалізовані запропоновані способи й алгоритми двовимірного перетворення Хаара, спосіб субоптимальної фільтрації зображень та спосіб зонального стиску зображень. На способи і пристрої перетворення Хаара отримані патенти України.

Практична значимість отриманих результатів підтверджується їх застосуванням при розробці нових зразків техніки в НТ СКБ “Полісвіт” (акт реалізації від 15.11.2002 р.), в навчальному процесі ХВУ в дисципліні “Системи відображення інформації в АСУ”, при курсовому і дипломному проектуванні (акт реалізації від 19.10.2002 р.)

Особистий внесок здобувача. Всі положення і результати, що виносяться на захист, отримані автором самостійно. Внесок здобувача в публікації, виконані в співавторстві, полягає в наступному: в роботах 1, 2 автором запропоновані пристрої швидкого одномірного перетворення Хаара; в роботі 3 запропонований одномірний цілочисловий базис Хаара; в роботах 5, 13 запропонований двовимірний базис Хаара і розроблений спосіб виконання двовимірного перетворення Хаара на його основі; в роботі 7 автором запропонований двовимірний цілочисловий базис Хаара і способи виконання двовимірного перетворення Хаара на його основі; в роботі 6 запропоновані способи й алгоритми швидкого двовимірного перетворення Хаара на основі дійсного й цілочислового двовимірного базису Хаара; в роботі 8 запропонований спосіб підвищення ефективності швидкого двовимірного перетворення Хаара за рахунок рівнобіжного виконання операцій перетворення; в роботі 10 розроблений спосіб зональної стиску на основі двовимірного перетворення Хаара; в роботі 4 автор виконав розрахунок ентропії колірних компонентів для різних колірних моделей; в роботі 12 здобувачем розроблений пристрій для порівняння чисел.

Апробація результатів дисертації. Основні положення дисертації доповідалися й обговорювалися на:

- 14-й і 15-й міжнародних школах-семінарах “Перспективні системи управління на залізничному, промисловому та міському транспорті”, м. Алушта: 2001, 2002 р.;

- міжнародних НТК “Проблеми інформатики і моделювання”, м. Харків: 2001, 2002 р.;

- 63-й науково-технічної конференції ХарДАЗТ і фахівців залізничного транспорту, м. Харків: 2001 р.;

- міжнародних науково-практичних конференціях “Проблеми енергозабезпечення та енергозбереження в АПК України”, м. Харків: 2001, 2002 р.

- науково-технічних семінарах “Синтез, обработка и отображение информационных моделей” Наукової ради НАНУ по проблемі “Теоретическая электротехника и электронное моделирование”, м. Харків: 2000 – 2002 р.

- науково-технічної конференції “Проблеми розробки і удосконалення засобів телекомунікацій систем управління в ЗСУ”, м. Київ: 2002 р.;

- науково-технічних семінарах ХВУ, м. Харків: 2000 _2002 р.

Публікації. Основні положення дисертаційної роботи опубліковані в 26 наукових працях, які включають 11 наукових статей, 2 патенти України, 1 позитивне рішення на видачу патенту України, 8 тез і матеріалів на всеукраїнських й міжнародних конференціях та семінарах, 4 звіти по науково-дослідних роботах.

Структура роботи. Дисертаційна робота складається з вступу, чотирьох розділів, висновків, списку використаних літературних джерел і дев’яти додатків. Повний обсяг роботи складає 217 сторінок машинописного тексту, з яких обсяг основного тексту складає 143 сторінку; додатки, список використаних джерел, малюнки і таблиці – 75 сторінок. Робота ілюстрована 47 малюнками, приведено 12 таблиць. Список використаних джерел складається з 121 найменувань.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

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

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

В другому розділі дисертації отримані: двовимірний базис Хаара і спосіб двовимірного перетворення Хаара (ДПХ), двовимірний цілочисловий базис Хаара і спосіб двовимірного цілочислового перетворення Хаара (ДЦПХ). Для двовимірного базису Хаара сформовані двовимірні базисні функції, дискретні відліки яких організовані у вигляді матриць: _для прямого перетворення і _для зворотного перетворення.

Структура матриці є клітинною і складається з підматриць розмірності , ( ), які організовані в масив розмірності . Підматриці являють собою дискретні значення визначеної двовимірної функції базису Хаара.

Підматриці отримують відповідно до матричного виразу

, (1)

де - підматриці двовимірної матриці Хаара з координатами ; - вектор-стовпець, отриманий транспонуванням k-го рядка матриці дискретних значень одномірного базису Хаара; - вектор-рядок, що являє собою l-й рядок матриці дискретних значень одномірного базису Хаара; - символ кронекірівського добутку.

На рис. 1 приведений приклад однієї з підматриць .

Необхідні коефіцієнти двовимірного перетворення Хаара (елементи трансформанти ) обчислюються відповідно до виразу

, (2)

де - елемент трансформанти ; - елемент блоку зображення ; - елемент підматриці ; N – розмірність блоків ().

Вираз (2) являє собою пряме двовимірне перетворення Хаара.

Для зворотного двовимірного перетворення Хаара формується матриця . Структура матриці має вигляд аналогічний . Підматриці матриці визначаються виразом

, (3)

де _підматриця двовимірної матриці Хаара з координатами ; - вектор-стовпець, отриманий транспонуванням k-го рядка транспонованої матриці дискретних значень одномірного базису Хаара; - вектор-рядок, що являє собою l-й рядок транспонованої матриці дискретних значень одномірного базису Хаара; - символ кронекірівського добутку.

Значення відліків блоку зображення X(n) обчислюють відповідно до виразів:

; (4)

, (5)

де ; _елемент (відлік) блоку зображення X(n); _коефіцієнт перетворення Хаара (елемент трансформанти Y(n)); _елемент підматриці матриці .

Вирази (4) і (5) являють собою зворотне двовимірне перетворення Хаара.

Двовимірний цілочисловий базис Хаара формується в результаті модифікації дійсного двовимірного базису (матриці і ) у відповідності з одним із наступних правил:

Правило 1. При виконанні прямого двовимірного перетворення Хаара дійсні значення базисних функцій виду ( ) необхідно розділити на . При виконанні зворотного двовимірного перетворення Хаара дійсні значення цих же базисних функцій помножуються на .

Правило 2. При виконанні прямого двовимірного перетворення Хаара дійсні значення базисних функцій виду ( ) необхідно помножити на . При виконанні зворотного двовимірного перетворення Хаара дійсні значення цих же базисних функцій діляться на .

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

В результаті модифікації отримаємо матриці і , елементи яких приймають цілочислові значення, рівні , r = 0, 1, 2, … Вираз для прямого цілочислового двовимірного перетворення Хаара має вид

, (6)

де ;  _елемент підматриці матриці .

Вираз для зворотного цілочислового двовимірного перетворення має вид

, (7)

де ; _елемент підматриці матриці .

Так як елементи цілочислових матриць і приймають значення 0 і , r = 0, 1, 2, … , то операції множення/ділення на замінені операціями побітового зсуву ліворуч/праворуч на r розрядів.

Визначено два способи нормування матриць перетворення: виконання нормування під час виконання прямого перетворення Хаара або під час виконання зворотного перетворення Хаара. В останньому випадку забезпечується значення СКВ рівне 0, але значно зростає динамічного діапазону трансформанти.

В третьому розділі розроблений спосіб швидкого двовимірного перетворення Хаара (ШДПХ), застосування якого дозволить зменшити кількість арифметичних операцій, час виконання перетворення і спростити технічну реалізацію процедури перетворення. Отримано аналітичні вирази, які описують процедури ШДПХ, а також вирази для розрахунку кількості арифметичних операцій, що виконуються під час перетворення зображень за допомогою запропонованого способу.

Кількість ітерацій, необхідних для виконання ШДПХ блоку зображення визначається виразом .

Кількість арифметичних операцій для ШДПХ визначається по формулах: ; ; .

Алгоритм складається з процедур трьох типів, які позначені наступним чином: А, B і C. На рис. 2 приведені графи зазначених процедур.

Для блоку зображення розмірності 8х8 алгоритм ШДПХ складається з трьох ітерацій:

1. На першій ітерації алгоритму ШДПХ виділяються чотирьохточечні блоки, над кожним з яких виконується процедур А. В результаті виконання процедур першої ітерації формується: 16 коефіцієнтів перетворення Хаара (); масив чотирьохточечних двовимірних перетворень Хаара (ДПХ) розмірності 4х4; масив чотирьохточечних ДПХ розмірності 4х4; масив чотирьохточечних ДПХ розмірності 4х4.

2. На другій ітерації обробці піддаються масиви , і , в результаті якої будуть сформовані восьмиточечні та шістнадцятиточечні ДПХ. Масив обробляється по стовпцям відповідно до процедури В, масив обробляється по рядкам відповідно до процедури В, для обробки масиву він розбивається на чотирьохточечні блоки, над якими виконується процедура А. В результаті виконання процедур другої ітерації отримаємо: 4 коефіцієнта перетворення Хаара ( ); 16 коефіцієнтів перетворення Хаара ( , ); 16 коефіцієнтів перетворення Хаара ( , ); масив шістнадцятиточечних ДПХ розмірності 2х2; масив шістнадцятиточечних ДПХ розмірності 2х2; масив шістнадцятиточечних ДПХ розмірності 2х2.

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

Розроблений алгоритм допускає рівнобіжне виконання більшості операцій перетворення, що дозволяє додатково зменшити час виконання перетворення в 510 разів.

В четвертому розділі проведена оцінка параметрів ефективності способів ортогонального перетворення Хаара при обробці зображень. Виконано порівняння отриманих результатів з аналогічними параметрами дискретно-косінусного перетворення (ДКП) та перетворення Уолша.

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

Розроблено програмну і технічну реалізації запропонованих способів і алгоритмів. У випадку технічної реалізації запропоновані патентоспроможні пристрої на основі однокристальних ЕОМ та на дискретних елементах.

Розроблено спосіб субоптимальної вінеровської фільтрації, який складається з наступних процедур: розбивка зашумленого зображення на блоки розмірності NxN; виконання прямого швидкого двовимірного цілочислового перетворення Хаара (ШДЦПХ) над кожним блоком; обробка стовпців отриманих трансформат за допомогою матриці фільтра А; обробка рядків матриць, отриманих на попередньому етапі, за допомогою транспонованої матриці АТ; виконання зворотного швидкого двовимірного цілочислового перетворення Хаара над трансформантами, обробленими фільтром А. Один зі способів розрахунку матриці фільтра А визначається виразами:

; (8)

, (9)

де G() – оператор двомірного ортогонального перетворення; - коваріаційна матриця зображення; - коваріаційна матриця шуму.

Експерименти показали, що для виконання за допомогою запропонованого способу потрібно в 1.5?4 рази менше часу, ніж для відомих способів субоптимальної фільтрації.

Розроблено спосіб стиску зображень на основі ШДЦПХ і способу зональної селекції коефіцієнтів перетворення. Процедура стиску складається з наступних етапів: розбивка вихідного зображення на блоки розмірності NxN; виконання ШДЦПХ над кожним із блоків; формування зонових послідовностей; виключення зі сформованих послідовностей зон з нульовими коефіцієнтами і формування послідовності блокових дескрипторів; збереження у файлі послідовності дескрипторів і зонових послідовностей відповідно до заданої міри якості.

Відновлення стиснутого зображення складається з наступних процедур: зчитування з файлу послідовності блокових дескрипторів і зонових послідовностей; створення трансформанти відновлюваного зображення, яка заповнена нульовими значеннями; відновлення з зонових послідовностей зон трансформант блоків зображення відповідно до інформації про конфігурацію трансформант, яка записана в блокових дескрипторах; виконання зворотного ШДЦПХ над кожною з трансформант блоку зображення. Зони селекції визначаються наступним правилом.

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

На рис. 3 приведена конфігурація зон селекції для трансформанти перетворення Хаара розмірності 8х8.

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

, (10)

де N – розмірність зображення по вертикалі; M – розмірність зображення по горизонталі; – кількість колірних складових в зображенні; – розрядність елементів колірних складових; – кількість елементів в i-й зонової послідовності j-ї колірний складової; – розрядність елементів i-ї зонової послідовності; – кількість елементів у послідовності дескрипторів j-ї колірний складової.

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

ВИСНОВКИ

В даній роботі одержали подальший розвиток способи і засоби двовимірних ортогональних перетворень зображень у базисі Хаара. При цьому:

1. Найбільш важливими науковими і практичними результатами, отриманими в роботі, є:_

спосіб двовимірного перетворення Хаара, застосування якого дозволить: зменшити величину СКВ в порівнянні з іншими способами виконання двовимірного перетворення Хаара в 1,5 рази за рахунок одноетапної процедури перетворення; рівнобіжне обчислення коефіцієнтів перетворення, що зменшить час виконання перетворення; одержувати тільки необхідні для аналізу й обробки коефіцієнти без необхідності обчислення всіх коефіцієнтів перетворення Хаара; зменшити витрати оперативної пам'яті при виконанні перетворень на 30%, так як не потрібно зберігати проміжні результати;_

спосіб цілочислового двовимірного перетворення Хаара і два способи цілочислового нормування: нормування під час прямого перетворення або під час зворотного перетворення. Застосування запропонованих способів двовимірного цілочислового перетворення Хаара дозволить: додатково зменшити значення СКВ відновлених зображень на 2040 % при виконанні нормування під час прямого перетворення та забезпечити СКВ при виконанні нормування під час зворотного перетворення, зменшити час виконання перетворення Хаара над зображеннями в 3 4 рази за рахунок цілочислових операцій, значно спростити технічну реалізацію перетворення._

алгоритми прямого і зворотного швидкого двовимірного перетворення Хаара, які забезпечують зменшення значення середньоквадратичного відхилення на 20?40 %; зменшення часу виконання перетворення в 2?5 рази; більш просту технічну реалізацію, яка не вимагає додаткової пам'яті для збереження проміжних результатів; можливість рівнобіжного виконання процедур перетворення._

ефективний метод двовимірної субоптимальної фільтрації зображень, який дозволяє зменшити час фільтрації зображення в 1.5 ? 3 рази._

спосіб зонального стиску зображень на основі швидкого двовимірного цілочислового перетворення Хаара, який при допустимих значеннях СКВ забезпечує стиск реалістичних зображень у 2 ? 20 рази. Час, який необхідний для виконання процедур стиску і відновлення зображень, в 4 ? 5 разів менше, ніж при використанні зонального стиску на основі ДКП.

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

- зменшити середньоквадратичне відхилення оброблюваних зображень у 1,5?2 рази;

- зменшити час обробки в зображень 2?10 рази;

- знизити вимоги до обсягу оперативної пам'яті на 30%;

- спростити технічну реалізацію ортогонального перетворення Хаара.

3. Достовірність отриманих у роботі результатів підтверджується:

- високою збіжністю з результатами експериментальних досліджень;

- несуперечності відомим результатам;

- отриманими патентами України на винаходи;

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

4. Висунуті в роботі теоретичні і практичні положення відбиті в 4 звітах про НДР, використані в розробках НТ СКБ “Полісвіт” та в навчальному процесі ХВУ, що підтверджується відповідними актами про впровадження.

Отримані результати можуть бути використані: при проведенні науково-дослідних і дослідно-конструкторських робіт зі створення нових технічних засобів і програмних продуктів для обробки і передачі відеоінформації в телекомунікаційних системах; у навчальному процесі ВНЗ України.

СПИСОК ОСНОВНИХ ПРАЦЬ, ОПУБЛІКОВАНИХ
ПО ТЕМІ ДИСЕРТАЦІЇ

1. Королев А.В., Бохан К.А. Алгоритм быстрого преобразования Хаара // Системи обробки інформації. – Харків: НАНУ, ПАНМ, ХВУ. – 2001. – Вип. 3 (13). – С. 132 – 137.

2. Королев А.В., Бохан К.А. Применение быстрого преобразования Хаара в спутниковых автоматизированных системах зондирования сельскохозяйственных культур // Вісник Харківського державного технічного університету сільського господарства. – 2001. – Вып. 6. – С. 122 – 124.

3. Королев А.В., Бохан К.А., Кучук Г.А. Целочисленное преобразование Хаара при обработке изображений // Системи обробки інформації. – Харків: НАНУ, ПАНМ, ХВУ. – 2001. – Вип. 6 (16). – С. – 156.

4. Стрюк А.Ю., Бохан К.А. Цветовые модели в системах сжатия видеоданных // Радиоэлектроника и информатика. – 2002. _№ 1. – С. 23 – 25.

5. Бохан К.А. Королева Н.А. Способ двумерного преобразования Хаара // АСУ и приборы автоматики. – 2002. – Вып. 120. – С. 137 – 147.

6. Бохан К.А, Королева Н.А. Метод быстрого двумерного преобразования Хаара // АСУ и приборы автоматики. – 2002. – Вып. 121. – С. 74 – 79.

7. Бохан К.А, Королева Н.А. Двумерный целочисленный базис Хаара // Авіаційно-космічна техніка і технологія. – Харьков: НАУ “ХАИ”. – 2002. – Вып. . – С. 204 – 208.

8. Бохан К.А, Королева Н.А. Распараллеливание операций преобразования изображений по базису Хаара // Вісник Харківського державного технічного університету сільського господарства. – 2002. – Вып. 10. – С. 413 – 422

9. Бохан К.А. Динамический диапазон трансформант двумерных ортогональных преобразований // Інформаційно-керуючі системи на залізничному транспорті. – 2002. – №3. – С. 40-44.

10. Бохан К.А. Королева Н.А. Способ зонального сжатия изображений на основе быстрого двумерного целочисленного преобразования Хаара // Інформаційно-керуючі системи на залізничному транспорті. – 2002. – №6. – С. 40-46.

11. Бохан К.А. Метод субоптимальной винеровской фильтрации на основе двумерного преобразования Хаара // Системи обробки інформації. – Харків: НАНУ, ПАНМ, ХВУ. – 2002. – Вип. 6 (22). – С. 29 – 34.

12. Пат. № 43715А UA, МПК 7F07/04. Пристрій для порівняння чиселБохан К.О., Корольова Н.А., Кучук Г.А. (Україна). _№ 2001053572, Заявл. 28.05.2001, Опубл. 17.12.2001, Бюл. №11.

13. Пат. № 52264А UA, МПК 7F07/04. Спосіб виконання ортогональних перетворень зображень по базису Хаара / Бохан К.О., Корольова Н.А., Гіневський М.І. (Україна). _№ 2002042555, Заявл. 01.04.2002, Опубл. 16.12.2002, Бюл. №12.

АНОТАЦІЯ

Бохан К.О. Способи та засоби двовимірного перетворення зображень в базисі Хаара. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.12.02 – “Телекомунікаційні системи та мережі”. – Українська державна академія залізничного транспорту. Харків, 2003.

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

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

АННОТАЦИЯ

Бохан К.А. Способы и средства двумерного преобразования изображений в базисе Хаара. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.12.02 – Телекоммуникационные системы и сети. – Украинская государственная академия железнодорожного транспорта. Харьков, 2003.

Диссертация посвящена разработке способов и средств двумерного преобразования изображений в базисе Хаара с целью уменьшения времени обработки и передачи их в телекоммуникационных системах. В работе проведен анализ существующих способов и средств двумерных ортогональных преобразований, которые используются для обработки изображений, а так же обзор научно-технической и патентной литературы, который позволил классифицировать существующие способы, выявить их недостатки и определить способы повышения эффективности процедур двумерных ортогональных преобразований. Указанные способы реализованы, в предложенных в работе, способах двумерного преобразования Хаара. Способ двумерного преобразования Хаара (ДПХ) основан на двумерном базисе Хаара, который состоит из двумерных кусочно-постоянных базисных функций. Способ целочисленного двумерного преобразования Хаара (ЦДПХ) основан на целочисленном двумерном базисе Хаара, который состоит из двумерных базисных функций, принимающих только целочисленные значения на интервале определения. В работе предложен метод построения целочисленного базиса Хаара. Применение ЦДПХ позволит уменьшить величину СКО по сравнению с другими способами выполнения двумерного преобразования Хаара в 1,52 раза за счет одноэтапной процедуры преобразования и использования только целочисленных арифметических операций. С помощью ДПХ и ЦДПХ возможно рассчитывать только необходимые для анализа и обработки коэффициенты без необходимости вычисления всех коэффициентов преобразования Хаара; уменьшить затраты оперативной памяти при выполнении преобразований на 30%, так как не требуется хранить промежуточные результаты. В работе разработаны способы и устройства быстрого прямого и обратного двумерного преобразования Хаара, в которых используются процедуры трех типов: А, В и С. Разработанные способы обеспечивают: уменьшение значения среднеквадратического отклонения на 2040 %; уменьшение времени выполнения преобразования в 25 раз; более простую техническую реализацию, не требующую дополнительной памяти для хранения промежуточных результатов; возможность параллельного выполнения процедур преобразования. Это достигается за счет исключения из процедуры преобразования “избыточных” арифметических операций: операций умножения на “1” и “0”, операций сложения нулевых значений и дублирующихся арифметических операций. Разработан эффективный способ двумерной субоптимальной фильтрации изображений, который позволяет уменьшить время фильтрации изображения в 1.5 – 3 раза за счет применения быстрого двумерного целочисленного преобразования Хаара. Эксперименты показали, что субоптимальная фильтрация позволяет уменьшить среднеквадратическое отклонение зашумленных изображений в 2?3 раза.

Разработан способ и устройство зонального сжатия изображений, в которых зоны селекции коэффициентов преобразования определяются их чувствительностью, в качестве ортогонального преобразования используется быстрое двумерное целочисленное преобразование Хаара. Процедура сжатия состоит из следующих этапов: выполнение прямого двумерного целочисленного преобразования Хаара, выделение зон селекции коэффициентов, подлежащих сохранению, в зависимости от заданного параметра качества, формирование зоновых последовательностей (ЗП), сохранение ЗП в файл. Восстановление состоит из следующих этапов: чтение зоновых последовательностей из файла, формирование трансформант блоков изображение из ЗП, отсутствующие в ЗП элементы трансформант приравниваются к 0, выполнение быстрого обратного целочисленного преобразования Хаара. За счет применения быстрого двумерного целочисленного преобразования Хаара, при приемлемых значениях СКО обеспечивает сжатие реалистических изображений в 2 – 20 раз. Время, необходимое для выполнения процедур сжатия и восстановления изображений, в 4 – 5 раз меньше, чем при использовании зонального сжатия на основе ДКП.

На разработанные способы и средства получены патенты Украины на изобретения.

Ключевые слова: ортогональное преобразование, видеоинформация, изображения, быстрый алгоритм, субоптимальная фильтрация, зональное сжатие.

ABSTRACT

Bohan K.A. Ways and means of two-dimensional image transformation
the Haar. _Manuscript.

Thesis on reception scientific degrees of candidate of technical sciences on professions 05.12.02 “Telecommunications systems and network”, Ukrainian State Academy of Railway Transport, Kharkov, 2003.

In dissertational operation it is shown, that existing telecommunication both computing systems do not ensure machining and transmission of images real-time. For boosting efficiency of orthogonal images transformations ways and a means of two-dimensional transformation of images in basis of Haar designed. They ensure one step an image processing and a possibility of a deep parallelizing of procedures of transformation. From procedures of transformation, "redundant" and real arithmetic operations are eliminated. Operations multiplication and division substituted by operations of bit-by-bit shift. It determines efficiency of offered ways. Based on designed ways of two-dimensional transformation of Haar high-performance modes of a suboptimal filtering and zone compression of images are offered.

Key words: orthogonal transformation, videodata, images, sweeping algorithm, a suboptimal filtering, zone compression.

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня
кандидата технічних наук

СПОСОБИ ТА ЗАСОБИ ДВОВИМІРНОГО
ПЕРЕТВОРЕННЯ ЗОБРАЖЕНЬ В БАЗИСІ ХААРА

05.12.02 "Телекомунікаційні системи та мережі"

Бохан Костянтин Олександрович

Підписано до друку 20.05.2003. Формат 60х90 1/16 | Обсяг: обл.вид.арк. 1,25. умов.друк.арк. 1,0. Наклад 100 прим. | Надруковано в друкарні „Штрих” ПП. Шуст Ю.М.

Харків-23, вул. Бакуліна, 33.