|
Харківський національний університет радіоелектроніки
Васильєв Микола Валерійович
УДК 004.383.5
Методи та апаратно-орієнтовані алгоритми синтезу процесорів швидких перспективних перетворень у системах візуалізації
05.13.13 – обчислювальні машини, системи та мережі
Автореферат
дисертації на здобуття наукового ступеня
кандидата технічних наук
Харків – 2003
Дисертацією є рукопис.
Робота виконана в Харківському національному університеті радіоелектроніки Міністерства освіти і науки України.
Науковий керівник – доктор технічних наук, професор Руденко Олег Григорійович, Харківський національний університет радіоелектроніки, завідувач кафедри електронних обчислювальних машин.
Офіційні опоненти:
– доктор технічних наук, професор Хажмурадов Манап Ахмадович, Національний науковий центр "Харківський фізико-технічний інститут", начальник відділу математичного забезпечення;
– кандидат технічних наук, Голубничий Дмитро Юрійович, Харківський військовий університет, ст. викладач кафедри обчислювальних систем та мереж.
Провідна установа – Національний технічний університет України “КПІ”, кафедра спеціалізованих комп’ютерних систем, Міністерство освіти і науки України, м. Київ.
Захист відбудеться 22.10.2003 р. о 14 годині на засіданні спеціалізованої вченої ради Д 64.052.01 у Харківському національному університеті радіоелектроніки (61166, м. Харків, пр. Леніна, 14).
З дисертацією можна ознайомитися у бібліотеці Харківського національного університету радіоелектроніки (61166, м. Харків, пр. Леніна, 14).
Автореферат розісланий 19.06.2003 р.
Вчений секретар
спеціалізованої вченої ради В.І. Саєнко
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. В імітаторах візуальних обстановок тренажерів транспортних засобів, а також при підготовці та в процесі трансляції телепередач на телецентрах та відеостудіях при виконанні складного перебивання кадрів, при монтажі та підготовці передач та фільмів, виникають проблеми, що пов’язані з обробкою “живих” зображень, гнучкістю процесу обробки, критерієм реального часу, якістю одержаного зображення та його відповідністю державним і міжнародним стандартам в області передачі й обробки телевізійних сигналів. Всі ці проблеми виникають при здійснюванні геометричних перетворень і відображенні реальних “живих” зображень за умов незалежності часу виконання перетворень від кількості елементів дискретизації зображення, а також при керуванні виконанням геометричних перетворень “живого” зображення в реальному часі.
Вимоги, яким повинні задовольняти вищевказані системи, що дозволяють реалізувати досить широкий комплекс перетворень, диктують необхідність використання в складі системи програмувальних засобів, а вимоги простоти обслуговування і низьких вартісних показників націлюють на використання найпростіших з них: мікропроцесорів і персональних ЕОМ.
Однак на цей час продуктивності найпростіших програмувальних засобів недостатньо для реалізації перетворення координат великих масивів елементів зображення в реальному часі. Тому в системі необхідна наявність апаратних засобів обробки інформації, що повинні бути досить універсальними і мати можливість перебудовуватися в залежності від виконання різних геометричних перетворень.
Існуючі на цей час системи провідних західних фірм, таких як Sony, Panasonic та інших, відрізняються вузькою спеціалізацією пристроїв за функціональним призначенням. Висока вартість необхідного користувачеві набору технічних засобів не дозволяє його придбати, а в Україні такі системи не випускаються. Декілька зразків пристроїв телевізійних відеоефектів "Естамп", які виготовлено в Росії (Санкт-Петербурзі) є громіздкими, ненадійними і не відповідають світовому рівню за функціональними можливостями. Тому гостро повстає питання створення на території України систем, які здійснюють перетворення зображень у реальному часі.
Для того, щоб здійснювати перетворення зображень у реальному часі, програмувальні засоби повинні встигати здійснювати необхідні обчислювальні операції за період розгорнення зображення на пристрої візуалізації. Це можуть бути незначні попередні обчислення, результат яких, впливаючи на апаратні засоби, буде основою для виконання перетворень координат усього масиву елементів розкладання зображення відповідно до заданого перетворення.
Для досягнення реального часу виконання перетворень незалежно від складності зображень використовуються принципи, що дозволяють виконувати обробку реальних зображень, які вводяться з телевізійної камери або з яких-небудь зовнішніх носіїв інформації, без їхнього попереднього аналітичного опису.
Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана в рамках держбюджетних і госпдоговірних тем, що виконувалися в Харківському національному університеті радіоелектроніки. Синтезовані і досліджені в дисертації алгоритми були використані під час виконання робіт №410 “Розробка теоретичних основ і нових архітектурних принципів створення тренажерних систем різного призначення” (№ДР0198U004440), №390 “Розробка політики і концепцій побудови захищених інформаційних технологій, розробка і дослідження методів і математичних моделей обробки і захисту інформації в системах і мережах” (№ДР0198U004445), у яких автор брав участь, як виконавець. Розроблені і досліджені в дисертації моделі, алгоритми і пристрої були використані при вирішенні задач обробки відеоінформації у Харківській обласній державній телерадіокомпанії (м. Харків, Україна), а також у ЗАТ Регіональної телекомпанії “Тоніс-Центр” (м. Харків, Україна).
Мета і задачі дослідження. Метою даного дослідження є розробка методів та апаратно-орієнтованих алгоритмів синтезу процесорів швидких перспективних перетворень у системах візуалізації, що здійснюють синтез геометрично змінюваних зображень у реальному часі.
Основні задачі наукового дослідження:
- дослідження можливих підходів до задачі побудови спецпроцесорів геометричних перетворень у реальному часі та обґрунтування вибору алгоритму синтезу;
- розробка апаратно-орієнтованих алгоритмів швидких геометричних перетворень, що задовольняють критеріям точності і швидкодії;
- розробка структури спецпроцесора швидких геометричних перетворень і визначення його місця в системах обробки відеоінформації реального часу;
- розробка і моделювання на ЕОМ алгоритмів, що реалізують афінні і проективні перетворення зображень, які генеруються;
- експериментальна перевірка результатів роботи і їхнє використання для вирішення конкретних прикладних задач.
Об'єкт дослідження – процес синтезу геометрично змінюваних зображень у системах візуалізації реального часу.
Предмет дослідження – алгоритми і структури спецпроцесорів швидких геометричних перетворень реального часу.
Методи дослідження – методи аналітичної геометрії і обчислювальної математики, що дозволили синтезувати різницево-ітераційні алгоритми обчислення складних геометричних функцій і математичних операцій; теорія імовірності; теорії матриць; методи математичного й імітаційного моделювання.
Наукова новизна отриманих результатів полягає в тому, що:
- вперше отримано апаратно-орієнтовані алгоритми швидких перспективних перетворень, які задовольняють критеріям точності і швидкодії, що дозволило спростити апаратурну реалізацію систем обробки відеоінформації за рахунок високої однорідності синтезованих структур;
- вперше одержано аналітичні співвідношення для часу виконання і похибок реалізації функції швидких перспективних перетворень, що дозволило за рахунок використання методу усунення похибки від відсутності збіжності ітераційного процесу, робити обчислення з підвищеною швидкодією і заданою точністю;
- вперше розроблено структуру спецпроцесора швидких геометричних перетворень зображень реального часу, яка за рахунок процесу одержання часткових результатів без очікування повного закінчення процесу обчислення дозволила розпаралелювати процедури реалізації функції перспективних перетворень.
Практичне значення отриманих результатів. Результати теоретичних досліджень реалізовані новими алгоритмами, що забезпечують одержання заданих перспективних перетворень зображень у реальному часі. Отримані алгоритми дозволяють розширити спектр перетворень зображень у реальному часі, які виконуються на сучасному устаткуванні, а також підвищити якість зображення, що перетворюється.
Розроблені в роботі апаратно-орієнтовані алгоритми швидких перспективних перетворень та розроблені структури спецпроцесорів швидких геометричних перетворень зображень реального часу були використані при розробці цифрових пристроїв телевізійних відеоефектів, які експлуатуються в складі апаратно-студійних блоків у штатно передбаченому місці включення блоків відеоефектів. Застосування розроблених алгоритмів дозволило спростити апаратурну реалізацію систем обробки інформації (за рахунок високої однорідності), а також робити обчислення з підвищеною швидкодією і заданою точністю. Застосування розроблених структур спецпроцесорів швидких геометричних перетворень зображень реального часу дозволило видавати часткові результати, не чекаючи повного закінчення процесу, що робить їх зручними в обчислювальних системах потокового типу.
Розроблені і досліджені в дисертації моделі, алгоритми та пристрої були використані при вирішенні задач обробки відеоінформації у Харківській обласній державній телерадіокомпанії (м. Харків, Україна) (акт від 05.02.2003), а також у ЗАТ Регіональної телекомпанії “Тоніс-Центр” (м. Харків, Україна) (акт від 12.02.2003) у вигляді блоку телевізійних відеоефектів, що дозволило підвищити якість відеопродукції, а також скоротити час її виробництва.
Основні положення, висновки і рекомендації, які викладені в дисертаційній роботі, використано при підготовці курсів “Системи цифрової обробки інформації”, “Моделювання систем” і “Цифрові системи керування” на кафедрі ЕОМ Харківського національного університету радіоелектроніки.
Особистий внесок здобувача. Основні результати отримані особисто автором. У роботах, написаних зі співавторами, здобувачу належить: у [1, 8] – опис апаратно-орієнтованих методів швидкої геометричної обробки зображень; [2] – розробка алгоритмів захисту відеоінформації, заснованих на методах обчислення складних геометричних функцій і математичних операцій; [4] – аналіз похибок методів проектування спецпроцесорів швидких геометричних перетворень; [6] – розробка структури апаратно-програмних засобів керування систем відображення інформації; [9] – розробка апаратно-орієнтованих алгоритмів перетворення зображень у реальному часі.
Апробація результатів дисертації. Основні результати дисертаційної роботи доповідалися й обговорювалися на 3-й, 4-й, 6-й і 7-й Міжнародних конференціях "Теорія і техніка передачі, прийому й обробки інформації" (Туапсе, 1997р., 1998р., 2000р., 2001р.), 1-му, 2-му Міжнародних молодіжних форумах "Електроніка і молодь у XXI столітті" (Харків, 1997 р., 1998 р.), на міській конференції "Актуальні проблеми сучасної науки в дослідженнях молодих учених м. Харкова" (Харків, 1998р.).
Публікації. За темою дисертації опубліковано 9 друкованих праць, 3 з яких – в наукових фахових виданнях, перелік яких затверджено ВАК України.
Структура та обсяг роботи. Дисертація складається зі вступу, чотирьох розділів, висновків, списку літератури з 110 найменувань, чотирьох додатків. Робота містить 34 ілюстрації, 3 таблиці. Загальний обсяг роботи складає 196 сторінок, у тому числі 135 сторінок основного тексту.
ОСНОВНИЙ ЗМІСТ РОБОТИ
У вступі обґрунтовується актуальність теми, якій присвячена дана дисертаційна робота. Сформульовано основну мету і задачі дослідження. Надано коротку анотацію отриманих у дисертації результатів, відзначена їхня наукова та практична цінність, наведені дані про впровадження результатів роботи.
Перший розділ присвячено огляду літератури та постановці задач дослідження. Розглянуто задачі виконання геометричних перетворень і апаратно-орієнтованих алгоритмів реалізації цих перетворень у системах візуалізації реального часу. Проаналізовано існуючі методи та алгоритми виконання геометричних перетворень. Розглянуто видові і перспективні перетворення, а також особливості сприйняття об'ємних зображень людським оком. Показано, що в деяких випадках “псевдоперспективні” зображення виглядають досить правдоподібно.
Надано рекомендації щодо вибору точки спостереження не дуже близької до об'єкта, особливо в тих випадках, коли кут  , показаний на рис. 1, приблизно дорівнює 90° ( – сферичні координати точки спостереження  ). При цьому практично виключений сильний ефект перспективи для вертикальних ліній.
Рис. 1. Сферичні координати точки спостереження
Показано, що для більш реалістичного вигляду зображення краще обмежувати не фактичне значення кута спостереження  , (рис. 2), а приблизно витримувати співвідношення
 , (1)
де  – значення відстані об’єкта від точки спостереження.
З (1) випливає, що вибір надто малого значення відстані  , може бути джерелом утруднень.
Проаналізовано основні математичні методи та алгоритми побудови спеціалізованих процесорів обробки інформації. Більш детально розглянуті матричні методи, таблично-алгоритмічні методи, методи, які базуються на перерахункових схемах, метод псевдоповоротів вектора та різницево-ітераційні методи обчислення складних функцій і математичних операцій. Такий вибір методів для детального розгляду обумовлений областю кращого застосування того чи іншого методу побудови спеціалізованого процесора, що визначається видом функціональної залежності, яка підлягає реалізації, та конкретними обмеженнями, що накладаються практикою. Зроблено висновки щодо доцільності використання різницево-ітераційних методів для реалізації складних геометричних функцій перспективних перетворень. Це пов'язано з тим, що вони є дуже зручними при апаратній реалізації в двійковій системі з фіксованою комою. Ці методи дозволяють при простій апаратурній реалізації робити обчислення з підвищеною швидкодією і потрібною точністю для більшості задач керування промислово-технологічними процесами і фізичними об'єктами. Робота таких спецпроцесорів може бути описана різницевими і диференційними рівняннями. Як показують дослідження та експериментальна перевірка, кількість ітерацій, як правило, не перевищує розрядності аргументу реалізованої функції. Основним принципом обчислень є одночасне вирішення системи двох і більш рекурентних різницевих рівнянь шляхом ітераційного циклу простих операцій додавання і зсуву.
Рис. 2. Конус спостереження
Спецпроцесори зазначеного класу дозволяють видавати часткові результати, не чекаючи повного закінчення процесу. Ця обставина робить їх зручними в обчислювальних системах потокового типу.
На підставі проведеного аналізу існуючих методів і алгоритмів виконання геометричних перетворень зображень сформульовано мету, яка полягає в розробці методів та апаратно-орієнтованих алгоритмів і структури спецпроцесора перспективної обробки зображень у системах реального часу і задачі дослідження. Для опису геометричних перетворень запропоновано використовувати різницево-ітераційні методи обчислення складних функцій.
У другому розділі розглянуто один з апаратно-орієнтованих методів цифрового перетворення зображень – метод псевдоповоротів вектора, що складається з перетворення координат, визначення положення нових елементів на площині вихідного зображення – інтерполяції елементів-сусідів для одержання рівня яскравості елемента в знайденій позиції, та вивчено питання апаратурної реалізації функцій геометричних перетворень.
Показано, що алгоритми цифрового перетворення значно розрізняються за продуктивністю. Основними оцінюваними параметрами системи є її продуктивність і використання ресурсів. Дано рекомендації щодо використання однопрохідного та двохпрохідного варіантів алгоритму перетворення. Однопрохідна система добре працює, якщо кут повороту зображення не перевищує 5°. При повороті на великі кути продуктивність системи різко падає. Двохпрохідна система, навпаки, добре працює з будь-якими величинами кута повороту і її продуктивність зберігається приблизно постійною.
При розгляді реалізації синусно-косинусних функцій і операцій множення і ділення методом псевдоповоротів вектора, геометрична інтерпретація якого наведена на рис. 3, зроблено висновки щодо того, що значення кутів  , на які треба повертати вектор на і-му кроці, зручно вибирати такими, щоб їхні тангенси були рівні цілому степеню двійки. Така вимога диктується міркуваннями структурного спрощення пристрою – заміни операції множення операцією зсуву. Загальний член послідовності кутів у цьому випадку буде мати вигляд
 .
Реалізація операції множення і ділення виконується за єдиним для них алгоритмом методом синхронного обертання двох векторів:
 ;
 ; (2)
 ,  .
Початкові умови й оператор повороту  для кожної операції мають вигляд:
для множення 
 (3)
для ділення 
 (4)
де  і  – операнди.
Рис. 3. Геометрична інтерпретація методу псевдоповоротів вектора
Обґрунтовано доцільність використання даних методів для вирішення перерахованих вище задач.
Позначено джерела похибок методу псевдоповоротів вектора. Зроблений аналіз можливих похибок обчислювача переслідував дві мети: визначення можливої точності реалізації алгоритмів та вибір доцільної розрядності обчислювача.
Точність рішення задачі визначається рядом похибок. Це: похибки методу; похибки вихідної інформації; похибки обчислень за рахунок округлення проміжних результатів.
Сутність першої похибки полягає в тому, що обчислення заданих функцій замінюється апроксимуючою задачею. Внаслідок цього можна одержати деяке наближення до точного рішення вихідної задачі.
Похибки вихідної інформації визначаються наближеним завданням величин коефіцієнта деформації вектора  і поточним кутом повороту вектора  . Похибка у завданні  найбільш істотно виявляється в процесі операцій зсуву, тому вона буде врахована при аналізі залежності третьої похибки.
Третя похибка визначається сумою числового ряду, що являє собою геометричну прогресію, перший член якої є  , а знаменник –  , де  – основна розрядність регістрів;  – додаткова розрядність координатних регістрів.
Повна похибка визначається як
 .
В роботі показано, що ця похибка задовольняє нерівності
 .
Ця нерівність є аналітичним співвідношенням повних похибок реалізації функції швидких перспективних перетворень, а формула основної похибці наведена у третьому розділі.
Отримані аналітичні залежності значень похибок є максимальними, що іноді приводить до апаратурної надмірності. Уникнути можливої апаратурної надмірності без твердих вимог до максимально припустимої похибки можливо при використанні статистичного аналізу похибок. Запропоновано метод усунення похибок від незбіжності ітераційного процесу в пристроях, що реалізують принцип псевдоповоротів вектора. Використання даних методів принципово нічим не відрізняється від алгоритмів, заснованих на принципі псевдоповоротів вектора, за винятком більш складних схем керування.
У третьому розділі обґрунтована доцільність реалізації функції перспективних перетворень методами псевдоповоротів вектора, а також одержані необхідні аналітичні вирази, які використовуються при реалізації перспективних перетворень.
Виведено співвідношення для координат екрана перетвореного перспективного зображення, які є адаптованими для програмно-апаратної реалізації:
 ; (5)
 , (6)
де  ,  ,  ,  ,  ,  ,  ,  ,  – елементи матриці перетворень точки  у точку  (рис. 1);
 ,  – координати екрану перетвореного зображення.
Проведено дослідження апаратно-орієнтованих алгоритмів реалізації типових геометричних перетворень. Запропоновано варіанти розпаралелювання процедури реалізації функції перспективних перетворень між спеціалізованим процесором і керуючою ЕОМ.
Розглянуто реалізації елементарних математичних функцій, що складають основу функції перспективних перетворень.
На основі методів реалізації типових геометричних перетворень були отримані алгоритми для обчислення  і  за формулами (5) і (6).
Якщо ввести позначення
| 
