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

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

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

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

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

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

Направления работ:

• формирование изображений с ИК‐приемников
• обработка изображений
• распознавание образов