Факультет: Компьютерных наук и технологий
	Кафедра: Компьютерной инженерии
	Специальность: Системное программирование
	Тема выпускной работы: Исследование методов преобразования цветных графических изображений
	Научный руководитель: Самощенко Александр Викторович

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

«Исследование методов преобразования цветных графических изображений»

Введение, актуальность, цель и задачи

Что такое изображение? На этот вопрос можно ответить по‐разному. Самое простое и широкое определение этого понятия: изображение — это то, что мы видим. Другое определение: изображение — это информация, пригодная для визуального восприятия. В зависимости от происхождения условно можно выделить следующие типы изображений:

• Рисованное или печатное (художник, полиграфия, принтер).
• Оптическое (распределение интенсивности электромагнитного поля создаваемое оптическим прибором в некоторой области пространства, например, на сетчатке глаза, на экране при проецировании, в плоскости приемника объектива фотоаппарата).
• Фотографическое (оптическое изображение, зарегистрированное на фотоматериале в результате химического процесса).
• Электронное или цифровое (оптическое изображение, зарегистрированное с помощью электронного приемника, например, ПЗС‐матрицы, сканера). Электронным также называют изображение, отображаемое на экране монитора.

Как видим, деление условное. Изображение из одного типа сразу переходит в другой. Цепочка этих преобразований в большинстве случаев заканчивается изображением на сетчатке глаза и образом в мозге человека.

В настоящий момент существует достаточно много форматов хранения и алгоритмов сжатия графической информации: растровые форматы (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, предназначенный для ускорения операций умножения на логических ячейках

При реализации алгоритмов, использующих операцию умножения с накоплением для потока входных данных, часто один и тот же поток данных необходимо умножать одновременно на разные коэффициенты с накоплением суммы отдельно по каждому из каналов умножения. Для реализации подобных алгоритмов блоки умножения в микросхеме имеют дополнительный вход, который может каскадно соединяться с выходом предыдущего умножителя в колонке (рис.2).[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

Муха Евгений Михайлович
Тема выпускной работы:
«Исследование реализаций MPEG2 видеопроцессоров на FPGA и PRUS»
http://masters.donntu.ru/2005/fvti/mukha/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 г. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.