Факультет: Ком'ютерних наук та технологiй
	Кафедра: Ком'ютерної інженерії
	Спеціальність: Системне програмування
	Тема випускної роботи: Дослідження засобів перетворення кольорових графічних зображень
	Керівник: Самощенко Олександр Вікторович

Реферат на тему выпускної роботи:

«Дослідження методів перетворення кольорових графічних зображень»

Введення, aктуальність, мета і завдання

Що таке зображення? На це питання можна відповісти по‐різному. Найпростіше і широке визначення цього поняття: зображення — це те, що ми бачимо. Інше визначення: зображення — це інформація, придатна для візуального сприйняття. Залежно від походження умовно можна виділити наступні типи зображень:

• Мальоване або друковане (художник, поліграфія, принтер).
• Оптичне (розподіл інтенсивності електромагнітного поля створюване оптичним приладом в деякій області простору, наприклад, на сітківці ока, на екрані при проектуванні, в площині приймача об'єктива фотоапарата).
• Фотографічне (оптичне зображення, зареєстроване на фотоматеріалів в результаті хімічного процесу).
• Електронне або цифрове (оптичне зображення, зареєстроване за допомогою електронного приймача, наприклад, ПЗЗ‐матриці, сканера). Електронним також називають зображення на екрані монітора.

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

На даний момент існує досить багато форматів зберігання і алгоритмів стиснення графічної інформації: растрові формати (BMP, ECW, GIF, ICO, ILBM, JPEG, JPEG 2000, MrSID, PCX, PNG, PSD, TGA, TIFF, HD, Photo), векторні формати (Scalable Vector Graphics (SVG і SVGZ), Encapsulated PostScript (EPS)), метафайли Windows: WMF, EMF, файли CorelDraw: → CDR, CMX, Adobe Illustrator (AI), XAR.

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

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

Рисунок 0 — Зразок використання ПЛІС FPGA
Анімація. Кількість кадрів — 4. Розмір — 115 Кб. Кількість повтореннь — 5

На цьому етапі роботи завдання полягає в дослідженні методів перетворення кольорового зображення з однієї моделі в іншу і реалізація його на FPGA з метою підвищення швидкодії роботи алгоритму. На даний момент розглядається модель перетворення зображення з формату RGB у кольорорізнісного формат YCbCr. Це перший етап в алгоритмі стиснення JPEG.

Наукова значимість і основні результати

Ресурси FPGA для виконання операцій множення і множення з накопиченням

Як відомо, продуктивність апаратної реалізації алгоритмів набагато вище програмною. Мікросхема з архітектурою FPGA, повна назва якої звучить як Field Programmable Gate Array (програмовані користувачем базові матричні мікросхеми), в даний час зосередила в собі останні технологічні досягнення мікроелектроніки та надає в розпорядження розробників найбільш розширені функціональні можливості. Розвиток архітектури FPGA пов'язано з постійним додаванням пристроїв, що полегшують виконання операцій цифрової обробки сигналів. У першу чергу це стосується множення. Основний програмований ресурс мікросхем з архітектурою FPGA — так звана логічна осередок. До її складу входять генератор логічних функцій, робота якого задається таблицею істинності (Look‐Up Table — LUT), тригер і деяке число спеціалізованих ресурсів, що спрощують реалізацію типових для цифрової схемотехніки вузлів. [1]

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

1. Ланцюги прискореного перенесення, призначені для швидкої передачі біта перенесення між логічними осередками, що спрощує організацію багаторозрядних вузлів.
2. Блочна пам'ять.
3. Виділені помножувачі: спеціалізовані блоки, які виконують множення незалежних 18‐біт операндів на частотах до сотень мегагерц (для сімейства Spartan‐3E — 266 МГц). На певному етапі розвитку ПЛІС з'ясувалося, що програмується логіка може розглядатися як ефективний співпроцесор цифрової обробки сигналів (DSP). Можливість реалізації паралельних обчислень на кристалі ПЛІС суттєво покращує їх позиції по відношенню до широко поширеним сигнальним процесорам. Ці умови реалізуються в основному в тих випадках, коли рішення задачі вимагає виконання великого числа операцій множення з накопиченням, зокрема в алгоритмах перетворення різних форматів представлення зображень. [2]

На рис. 4 показано одне з технічних рішень — вентиль MULT_AND. Його призначенням є зменшення обсягу логічних осередків, потрібних для реалізації множення «в стовпчик» — шляхом зсуву та складання. Коротенько нагадаємо, що множення двійкових чисел у стовпчик нічим не відрізняється від множення десяткових чисел, однак у силу того, що в двійковому поданні є тільки символи 0 і 1, виникають лише чотири варіанти: 0 × 0 = 0, 0 × 1 = 0, 1 × 0 = 0 і 1 × 1 = 1. Ці множення на кожен з розрядів по черзі утворюють проміжні суми, які потім піддаються підсумовування (з попередніми зрушенням, що легко простежити, виконавши множення в стовпчик на папері). Неважко бачити, що множення однобітних двійкових чисел реалізується вентилем 2И. Однак складність у тому, що при реалізації множення на логічних осередках перший їхній ряд виявляється задіяним саме для множення (хоча 4‐входовая LUT могла б зробити і більше). Вирішенням цієї часто зустрічається завдання і став спеціальний вентиль, що розташовується в кожній LUT. Його розміри невеликі, а функція зустрічається часто й істотно підвищує продуктивність ПЛІС, так що таке збільшення складності логічної осередку в цілому цілком виправдано. Наявність вентиля MULT_AND залишає вільної відповідну LUT. Важливо, що алгоритми САПР автоматично використовують ці ресурси при реалізації блоків множення. Також цікаво, що і в родинах з виділеними апаратними помножувача можна додавати в проект і помножувачі на осередках, які будуть мати меншу тактову частоту, але додатково збільшують максимальну продуктивність кристала. При цьому характеристики ПЛІС в задачах DSP зазвичай наводяться без урахування цього досить потужного резерву. [5]

Рисунок 1 — Вентиль MULT_AND, призначений для прискорення операцій множення на логічних осередках

При реалізації алгоритмів, що використовують операцію множення з накопиченням для потоку вхідних даних, часто один і той же потік даних необхідно множити одночасно на різні коефіцієнти з накопиченням суми окремо по кожному з каналів множення. Для реалізації подібних алгоритмів блоки множення в мікросхемі мають додатковий вхід, який може каскадно з'єднуватися з виходом попереднього помножувача в колонці (рис.1). [2]

Рисунок 2 — Каскадне з'єднання помножувачем

RGB to YCrCb Color‐Space Converter це — спрощений 3x3 матричний множник, що перетворює три вхідних каналу кольору в три вихідних каналу кольору за один CLK цикл.Оптимізована структура використовує тільки чотири множника або DSP48-Слайс, використовуючи залежності між коефіцієнтами в конвертованій матриці RGB до YCrCb або RGB до YUV стандартам. Ядро ефективно використовує 18x18‐бітові множники, суматори та регістри, побудовані на блоках DSP Virtex ™ ‐5, Virtex‐4 і Spartan ™‐3A DSP пристроїв, або інтегровані 18x18‐бітові множники в Virtex‐II, Virtex‐II Pro і Spartan 3 , що приводять до високоефективного і оптимального використання ресурсів. [3]

Колірний простір RGB

Червоний, зелений і синій (RGB) колірне простір, широко використовуються в комп'ютерній графіці. Червоний, зелений і синій три основних адитивних кольори: окремі компоненти додаються разом, щоб сформувати необхідний колір. [4]
YCbCr (або YCrCb) колірне простір
YCbCr або YCrCb колірний простір було розроблено в ході розвитку всесвітньої цифрового стандарту відео компонента. Y має діапазон від 16 до 235, Cb і Cr мають номінальний діапазон від 16 до 240. [4]

Висновок перетворення рівнянь

Ці рівняння можуть бути безпосередньо апаратно реалізовані, як показано на малюнку 2. Затемнені блоки на малюнку 2 представляють собою логічні блоки, які завжди реалізуються на DSP блоках, якщо блоки DSP доступні в цільовому пристрої. [3] Приклад тимчасової діаграми виконання перетворення представлений на рисунку 3.

Результати досліджень

У дослідженнях застосована мікросхема Spartan‐3 з частотою роботи 178 МГц (таблиця 1). У результаті отримана продуктивність 4,4 мс для обробки кадру розміром 1024х768 пікселів. Для порівняння, обробка такого ж зображення в системі Matlab займає 373 мс, що значно перевищує час виконання на апаратній платформі.

Рисунок 3 — Схема перетворення

Рисунок 4 — Часова діаграма виконання перетворення

Таблиця 1 — Таблиця продуктивності

Переваги використання даної апаратури очевидно: швидкодія, простота заміни апаратних блоків і удосконалення самого алгоритму.

Огляд алгоритму стиснення JPEG

При стисненні зображення перетворюється з колірного простору RGB у YCbCr (YUV). Слід зазначити, що стандарт JPEG (ISO / IEC 10918‐1) ніяк не регламентує вибір саме YCbCr, допускаючи та інші види перетворення (наприклад, з числом компонентів, відмінним від трьох), і стиснення без перетворення (безпосередньо в RGB), проте специфікація JFIF (JPEG File Interchange Format, запропонована в 1991 році фахівцями компанії C‐Cube Microsystems, і яка стала в даний час стандартом де‐факто) припускає використання перетворення RGB -> YCbCr.[2]

Після перетворення RGB -> YCbCr для каналів зображення Cb і Cr, що відповідають за колір, може виконуватися "проріджування" (subsampling [3]), яке полягає в тому, що кожному блоку з 4 пікселів (2х2) яскравості каналу Y ставляться у відповідність усереднені значення Cb і Cr (схема проріджування "4:2:0" [4]). При цьому для кожного блоку 2х2 замість 12 значень (4 Y, 4 Cb і 4 Cr) використовується всього 6 (4 Y і по одному усередненим Cb і Cr). Якщо до якості відновленого після стиснення зображення пред'являються підвищені вимоги, проріджування може виконуватися лише в якомусь одному напрямку — по вертикалі (схема "4:4:0") або по горизонталі ("4:2:2"), або не виконуватися зовсім ("4:4:4").

Стандарт допускає також проріджування з усередненням Cb і Cr не для блоку 2х2, а для чотирьох розташованих послідовно (по вертикалі або по горизонталі) пікселів, тобто для блоків 1х4 або 4х1 (схема "4:1:1"). Допускається також використання різних типів проріджування для Cb і Cr, але на практиці такі схеми зустрічаються виключно рідко.

Далі, яскравісної компонентів Y та відповідають за колір компоненти Cb і Cr розбиваються на блоки 8х8 пікселів. Кожен такий блок піддається дискретному косінусного перетворення (ДКП). Отримані коефіцієнти ДКП квантуються (для Y, Cb і Cr в загальному випадку використовуються різні матриці квантування) і пакуються з використанням кодів Хаффмана.Стандарт JPEG допускає також використання значно більш ефективного арифметичного кодування, однак, через патентних обмежень (патент на описаний в стандарті JPEG арифметичний QM‐кодер належить IBM) на практиці воно не використовується.

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

Практична цінність

Архітектура FPGA володіє великою гнучкістю, на її базі можна реалізовувати розпаралелювання операцій, що дозволяє істотно підвищити продуктивність всієї DSP‐системи. Найбільш типові приклади такого використання FPGA — реалізація КИХ‐фільтрів, швидкого перетворення Фур'є, цифрового перетворення з пониженням частоти, блоків прямого виправлення помилок [7].

Технології на базі FPGA дозволяють вирішувати в реальному часі задачі виявлення і розпізнавання образів, а також визначення їх характеристик (наприклад, лінійні розміри, швидкість, координати і т.д.). [8]

Напрямки робіт:

• формування зображень з ІК‐приймачів
• обробка зображень
• розпізнавання образів

Джерела зображень:

• ІЧ‐або відеокамера
• стерео зір
• багатозональної зображення

Класи розв'язуваних завдань:

• об'єкт на окремому зображенні (в тому числі багатозональної або стерео)
• рухливий об'єкт на послідовності зображень, отриманих нерухомим приймачем
• нерухомий об'єкт на послідовності зображень, отриманих нерухомим приймачем
• рухливий об'єкт на послідовності зображень, отриманих рухомим приймачем
• нерухомий об'єкт на послідовності зображень, отриманих рухомим приймачем

Огляд досліджень по темі в ДонНТУ

Муха Євген Михайлович
Тема випускної роботи:
«Дослідження реалізацій MPEG2 відеопроцесорів на FPGA та PRUS»
http://masters.donntu.ru/2005/fvti/mukha/diss/index.htm

Войтов Геннадій Володимирович
Тема випускної роботи:
«Аналіз аналогових сигналів на базі ЦГЗ в FPGA»
http://masters.donntu.ru/2009/fvti/voitovg/diss/index.htm

Дружинін Олексій Ігорович
Тема випускної роботи:
«Розробка багатопроцесорних систем рішення звичайних диференціальних рівнянь на базі FPGA‐технологій »

http://masters.donntu.ru/2006/fvti/druzhynin/diss/index.htm

Сімілєтов Олександр Сергійович
Тема випускної роботи:
«Дослідження структур тривимірних акселераторів, що використовують FPGA технології»
http://masters.donntu.ru/2004/fvti/similyetov/diss/index.htm

Cвістунов Сергій Миколайович
Тема випускної роботи:
«Дослідження та розробка на FPGA SPP‐архітектури поста контролю цифрових пристроїв»
http://masters.donntu.ru/2008/fvti/svistunov/diss/index.html

Кузьменко Володимир Олегович
Тема випускної роботи:
«Автоматизація проектування швидкодіючих цифрових пристроїв на FPGA»
http://masters.donntu.ru/2008/fvti/kuzmenko/diss/index.htm

Випріцкая Поліна Олександрівна
Тема випускної роботи:
«Автоматизація синтезу керуючих автоматів Милі на FPGA»
http://masters.donntu.ru/2008/fvti/vypritskaya/diss/index.htm

Гезь Михайло Валерійович
Тема випускної роботи:
«Моделювання HDL‐проектів на мультипроцесорної системі»
http://masters.donntu.ru/2003/fvti/gez/diss/index.htm

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

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

З 1984 року, коли вперше в світі Xilinx випустила програмовані логічні інтегральні схеми (ПЛІС) з архітектурою FPGA (Field Programmable Gate Array), і по теперішній час компанія є провідним світовим виробником мікросхем програмованої логіки. Технології Xilinx надають можливість виробникам електронного устаткування мінімізувати ризики за рахунок скорочення часу на розробку нової продукції і строків її виходу на ринок.Розробники можуть проектувати і займатися налагодженням своїх унікальних пристроїв на базі ПЛІС Xilinx набагато швидше, ніж при використанні традиційних методів, при яких мікросхеми отримують фіксовану структуру в момент їх виготовлення. Більше того, оскільки ПЛІС Xilinx представляють собою готові до програмування стандартні вироби, розробникам не потрібно чекати виготовлення прототипів або йти на істотні витрати для підготовки виробництва, як при використанні фіксованої логіки або ASIC (Applications Specific Integrated Circuit). В даний час продукція Xilinx знаходить саме широке застосування — від телекомунікацій і споживчої електроніки до автомобільного і промислового устаткування.

Сутність ринку ПЛІС

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

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

В Україні в інституті кібернетики ім. В. І. Глушкова у відділі мікропроцесорній техніці зібрано великий список публікацій на тему ПЛІС.
http://www.incyb.kiev.ua/s/284/ua/biblioteka_osnownyh_publikatsiy_/_otdel_mikroprotsessor.html

Висновок

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

Література

1. Кузелин М.О. , Кнышев Д.А., Зотов В.Ю. Современные семейства ПЛИС фирмы Xilinx: справочное пособие. — 440 с.
2. Тарасов И.Е. Разработка цифровых устройств на основе ПЛИС Xilinx с применением языка VHDL — 252 c.
3. RGB to YCrCb Color‐Space Converter v1.0 DS659 March 24, 2008 Product Specification — 6 с., 15 с., 17 с.
4. Гонсалес Р., Цифровая обработка изображений в среде MATLAB — 206 с., 216 с.
5. Тематический журнал «Компоненты и технологии». [Электронный ресурс]/ — Электронные данные — Режим доступа: http://www.kit-e.ru/index.php, свободный
6. Журнал «Электронные компоненты», 1999, №5. [Электронный ресурс]/ — Электронные данные — Режим доступа: http://www.elcp.ru/index.php?state=izd&i_izd=elcomp&i_num=1999_05&i_art=12, свободный
7. «ЭЛЕКТРОНИКА: Наука, Технология, Бизнес» российский научно‐технический журнал, освещающий проблемы электроники в её широком понимании. [Электронный ресурс]/ — Электронные данные — Режим доступа: http://www.electronics.ru/, свободный
8. Официальный сайт НТЦ "Модуль" — лидирующая российская hi‐tech‐компания, работающая в области электроники. [Электронный ресурс]/ — Электронные данные — Режим доступа: http://www.module.ru, свободный

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