Вычислительная оптимизация взаимных преобразований цветовых пространств на базе арифметики с фиксированной точкой

Размещено на http://www.allbest.ru/

Вычислительная оптимизация взаимных преобразований цветовых пространств на базе арифметики с фиксированной точкой

Гришенцев Алексей Юрьевич

доктор технических наук 

доцент, Санкт-Петербургский национальный

исследовательский университет

информационных технологий, механики и оптики 

Коробейников Анатолий Григорьевич

доктор технических наук 

профессор, Санкт-Петербургский филиал

Федерального государственного бюджетного

учреждения науки Института земного магнетизма,

ионосферы и распространения радиоволн им.

Н.В.Пушкова Российской академии наук. 

Югансон Андрей Николаевич

аспирант, ФГАОУ ВО "Санкт-Петербургский

национальный исследовательский университет

информационных технологий, механики и оптики" 



Аннотация

В данной работе представлены результаты по систематизации методов вычислительной оптимизации преобразования цветовых пространств на базе применения арифметики с фиксированной точкой. Сформулированы задачи и проанализированы основные проблемы возникающие в случае вычислительной оптимизации в процессе образования цветовых пространств с точки зрения повышения быстродействия. Изложены принципы перехода от формата с плавающей к формату с фиксированной точкой. Приведён пример и анализ вычислительной оптимизации при взаимном преобразовании RGB и Y709CbCr. В данной работе рассмотрен метод вычислительной оптимизации преобразования цветовых пространств на базе применения арифметики с фиксированной точкой При применении рассмотренного принципа практической реализации время вычислений для изображения 4134x2756 на процессоре Intel Core 2 Duo сократилось в 18-ть раз. Такое повышение производительности является очень значимым. Не составляет труда применить указанный подход к прочим подобным вычислениям, особенно на современных 64-х и 128-ми разрядных процессорах, когда необходимые значения умещаются в один процессорный регистр.

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



Abstract

арифметика точка фиксированный

In their article the authors provide their results on systematization of methods for computational optimization of the transformation of color spaces based upon the application of fixed-point arithmetic. The authors formulate the goals and analyze the key problems arising in the situation of computational optimization in the process of color space formation from the standpoint of the speed of operation increase. The principles of transition from a floating point format to a format with a fixed point are stated. The authors also provide an example for the analysis of computational optimization for the mutual transformation of RGB and Y709CbCr. In this article the authros consider the method of computational optimization of the transformation of color spaces based on the application of fixed-point arithmetic. When applying the considered principle of practical implementation, the computation time for an image of 4134x2756 on an Intel Core 2 Duo processor becomes 18 times less. This is a very significant increase in productivity. It is not too difficult to apply this approach to other similar calculations, especially on modern 64-bit and 128-bit processors, when the necessary values fit into a single processor register. 

Keywords: RGB, format with a floating point, the format with fixed point, computing optimization, mathematical coprocessor, serial processing of images, parallel processing of images, transformation, color space, image processing 



Введение

Существует значительное многообразие цветовых пространств позволяющих отображать цветовую палитру графического изображения. Поэтому при преобразованиях форматов графических данных часто приходится иметь дело с преобразованиями цветовых пространств. В большинстве случаев пользователю желательно иметь быстрый, приводящий к минимальным искажениям алгоритм преобразования. Исследованиями и стандартизацией, в том числе, в области цветоощущения, цветопередачи, занимаются ряд организаций по всему миру. Данные организации разработали ряд стандартов и рекомендаций по классификации и использованию цветовых пространств, например [1-3]. Анализ литературы и открытой документации к некоторым программным средствам показал, что уделено не достаточное внимание вопросам вычислительной оптимизации алгоритмов преобразования цветовых пространств [3-11]. В подавляющем большинстве случаев преобразования рассматриваются в форматах с плавающей точкой, что собственно вызывает ряд вопросов при практическом внедрении, например, с учётом значительных размеров современных цифровых графических изображений, преобразования цветовых пространств в форматах с плавающей точкой, даже с учётом использования математического сопроцессора (FPU от англ. floating point unit), требует существенных вычислительных затрат. При использовании арифметики с плавающей точкой существенное повышение скорости вычислений может предоставить применение графических сопроцессоров на базе библиотек OpenGL, DirectX или технологии неграфических вычислений на базе графических сопроцессоров GPGPU (от англ. General-purpose graphics processing units), но применение специальных средств обработки цифровой графической информации не всегда доступно и целесообразно. Но следует отметить, что многие современные приложения обработки изображений реализованы в системах, не имеющих GPU, примером таких систем могут быть системы на базе микроконтроллеров STM32 (http://www.st.com/) реализующие методы обработки динамических (в том числе видео) и статических изображений и другие подобные системы. Таким, образом, кроме параллельной, по-прежнему являются актуальными методы последовательной обработки изображений. Рассмотренные в статье методы могут быть использованы как в системах параллельной, так и в системах последовательной обработки изображений.

Фиксированная точка вместо плавающей

На рис. 1 приведено две схемы обработки сигналов в соответствии с последовательностью преобразований. Схема на (рис. 1, а) обеспечивает высокое быстродействие, но накладывает некоторые, порой недопустимые, ограничения на процедуру преобразования. Схема на (рис. 1, б), позволяет производить самые разнообразные цифровые преобразования сигнала, но существенно снижает быстродействие на этапах: обработки сигнала в формате с плавающей точкой (ПТ) и преобразования форматов.

Рис. 1. Возможные схемы обработки цифровых сигналов. Обозначения: ФТ - формат с фиксированной точкой; ПТ - формат с плавающей точкой; АЦП - аналогово-цифровой преобразователь; ЦАП - цифро-аналоговый преобразователь; ФТ > ПТ и ПТ > ФТ - соответствующие преобразования форматов

Возможным компромиссом и решением проблемы повышения быстродействия, является использование схемы, приведённой на (рис. 2). В данной схеме отсутствуют операции в формате ПТ. Все операции выполняются в целочисленных форматах, а требуемая точность достигается за счёт увеличения числа разрядов, фактически за счёт перехода к формату с фиксированной точкой (ФТ).

Рис. 2. Альтернативная схема цифровых преобразований сигналов. Обозначения: Ф1 - ФТ формат, совместимый с ЦАП и АЦП; Ф2 - ФТ формат, позволяющий произвести требуемые преобразования без переполнения

Например, в большинстве цветовых схем на каждый цветовой канал изображения выделяется восемь бит. Сложение двух или более восьмибитных элементов в формате типа unsigned char (или unsigned int8 - 8 бит без знака 0…255), может привести к переполнению и результату не соответствующему ожиданиям. Использование переменных большей разрядности позволяет гарантированно, не вызывая переполнения (до определённого значения суммы), производить сложение. Например, формат unsigned int16 (16 бит без знака 0…65535) позволяет произвести сложение, гарантированно не вызывая переполнения, до 256 элементов типа unsigned char.

Следующая операция - умножение. В целочисленной арифметике умножение на число, кратное степени двух, может быть выполнено с помощью поразрядного сдвига влево. Умножение может достаточно быстро приводить к переполнениям. Например, при операциях над сигналами, каждый дискретный элемент, которых представлен в формате unsigned char, действия в формате unsigned int16 могут, в наихудшем случае, вызвать переполнение уже при втором умножении в формате unsigned int32 - при четвёртом умножении. Можно заключить, что при использовании целочисленных форматов, для операции умножения, необходимо учитывать возможность переполнения, ограничивая результаты операции после выполнения соответствующего числа раз. Практическая реализация такого ограничения зависит от особенностей конкретной программно-аппаратной платформы и способа решения задачи.

Наиболее затратной с точки зрения потребления вычислительных ресурсов, является - деление. В целочисленной арифметике деление на число, кратное степени двух, может быть выполнено с помощью поразрядного сдвига вправо. Заметим, что деление на любое число (кроме нуля) можно с заданной степенью точности, реализовать с помощью операций сдвига и сложения. При делении в целочисленной арифметике может возникать существенная потеря точности за счёт отбрасывания дробной части.

Обобщим сказанное в формальной записи. Наиболее используемыми операциями цифровой обработки является умножение с последующим суммированием, например: свёртка, БПФ, фильтр скользящего среднего и др. реализуется на базе умножения с последующим суммированием [11-13]. Пусть по схеме (рис.2) в формате ФТ необходимо выполнить умножение (1) с последующим суммированием  некоторых значений  на коэффициенты :

(1)

где  - в формате ФТ;  - в формате ПТ;  - результат суммы в формате ПТ.

Для исключения переполнения, в худшем случае, когда все значения  имеют максимально возможную величину, необходимо:

- ограничить число элементов, т.е. N;

- ограничить значения коэффициентов .

Ограничение величины N при необходимости реализуется с помощью разделения всей суммы (1) на некоторые частичные суммы:

 , (2)

где .

Ограничить значения  коэффициентов возможно, например, при помощи нормирования:

, (3)

причём нормирование целесообразно производить заранее, перед обработкой.

Далее, с учётом формата ФТ в котором будет производиться умножение с суммированием, необходимо принять решение: сколько знаков после точки должны быть учтены. Пусть значимое число знаков будет k тогда коэффициент hвозможно вычислить как h=0x10k=1016k=16k, где 0x - префикс 16-ричной системы исчисления. Основание степени 16 обеспечивает некоторую избыточность, по сравнению с основанием десятичной системы счисления, что повышает точность вычислений. Если при основании 16 есть вероятность переполнения, то в качестве основания, возможно, взять число 8, но при этом произойдёт понижение точности. В общем случае при значении коэффициента h=2k (2 в степени k, где k - целое) операции умножения и деления на h легко выполнить с помощью сдвига, влево и вправо на log2h бит соответственно, для h=16k, логарифм имеет значение: log2h=log224k, например:

 - умножение: ;

- деление: ;

где  и  - операторы поразрядного сдвига влево и вправо соответственно. Ценность выбора основания два заключается в возможности замены в двоичных системах относительно медленных операций умножения и деления, быстрыми операциями поразрядного сдвига.

Результирующее выражение для операций умножения с последующим суммированием, возможно, осуществить в соответствии с выражением:

(4)

где  - целочисленный эквивалент коэффициента с плавающей точкой ,  - поправочный коэффициент для округления к ближайшему целому при делении с помощью сдвига.

Наиболее затратной, с точки зрения потребления вычислительных тактов, является операция деления, как видно из выражения (4) операция деления, при вычислении преобразования форматов по основанию кратному степени двойки, заменяется операцией сдвига.

Взаимные преобразования цветовых пространств

Рассмотрим выражения для взаимных преобразований широко используемых в практике цифровой обработки изображений цветовых пространств RGB и Y709CbCr. Цветовое пространство RGB ассоциировано со спецификой устройства зрительного анализатора человека, применяется для визуализации изображений и как цветовое пространство некоторых графических форматов, например BMP24. Цветовое пространство Y709CbCr [2] является вариацией цветоразностной модели YCbCr, применяется с системах цифрового телевиденья высокой чёткости, а так же в некоторых форматах компрессии изображений [11,12]. Взаимные преобразования RGB и Y709CbCr осуществляются при помощи уравнений:

(5)

и

(6)

Вычислительная оптимизация на примере взаимных преобразований цветовых пространств RGB и Y709CbCr

Для хранения изображений будем использовать массив структур, описание структуры приведено в листинге 1.

Листинг 1. Структура вектора цветового пространства RGB и Y709CbCr (C++)

typedef unsigned char uchar; // без знаковый байт

#pragma pack (push, 1) // отключаем выравнивание памяти

// цветовая палитра RGB

// покомпонентное представление, в скобках указаны компоненты

// палитр (RGB) и (YCbCr) соответственно

struct ColorSpace {

uchar byteLo; // компонента младший байт (Lower) (R) (Y)

uchar byteAv; // компонента средний байт (Average) (G) (Cb)

uchar byteHi; // компонента старший байт (Hight) (B) (Cr)

};

#pragma pack (pop) // выравнивание памяти исходное состояние

В листинге 2 приведён пример преобразования элемента изображения (пикселя) из цветового пространства RGB в Y709CbCr в формате ПТ.

Листинг 2. Преобразование значения из цветового пространства RGB в Y709CbCr, вычисления в формате ПТ (C++).

ColorSpace x; // пиксель типа ColorSpace (листинг 1)

float R, G, B; // временные переменные

R=(float)x.byteLo; // цветовые компоненты преобразуем в формат ПТ

G=(float)x.byteAv;

B=(float)x.byteHi;

// компонент Y

x.byteLo=(uchar)floor(0.183*R+0.614*G+0.062*B+16);

// компонент Cb

x.byteAv=(uchar)floor(-0.101*R-0.338*G+0.439*B+128);

// компонент Cr

x.byteHi=(uchar)floor(0.439*R-0.399*G-0.040*B+128);

Оптимизированный вариант преобразования данных из цветового пространства RGB в Y709CbCr в соответствии с выражением (5), (листинг 3), на базе принципов целочисленных вычислений в формате с ФТ рассмотренных ранее. Для перевода в формата ФТ использовался множитель h=220=2(4)•5=1048576 из расчёта максимального использования разрядной сетки, с целью повышения точности, без переполнения. Для округления к ближайшему целому, возможно, использовать добавление величины (0.5h)=(h>>1)=524288. В листинге 3 и 4 для наглядности производимых действий некоторые операции записаны излишне подробно. При включении оптимизации, большинство современных компиляторов автоматически рассчитает все возможные значения на этапе компиляции и избавит результирующий код от излишних действий.

Листинг 3. Преобразование значения из цветового пространства RGB в YCbCr, вычисления в формате ФТ (C++).

ColorSpace x; // пиксель типа ColorSpace

int R, G, B;

R=(int)x.byteLo;

G=(int)x.byteAv;

B=(int)x.byteHi;

const int h=((2<<20)>>1); // h=524288;

// компонент (Y)

x.byteLo=(uchar)(abs(191889*R+643826*G+65012*B+16777216+h))>>20);

// компонент (Cb)

x.byteAv=(uchar)(abs(-105906*R-354419*G+460325*B+134217728+h)>>20);

// компонент (Cr)

x.byteHi=(uchar)(abs(460325*R-418382*G-41943*B+134217728+h)>>20);

Сравнения преобразований для графических изображений размером 4134x2756 пикселей на базе вычислений в форматах ПТ и ФТ (рис. 3), показали, что, временя преобразования, на процессоре Intel Core 2 Duo было уменьшено более чем в 18-ть (восемнадцать!) раз. Подобное повышение скорости вычислений является очень значительным и хорошо иллюстрирует эффективность перехода (при возможности) к формату ФТ даже при наличии математического сопроцессора. Сопоставление и анализ конечных результатов преобразований с применением ФТ и ПТ показал их полную идентичность друг другу.

Рис. 3. Сравнение скорости вычислений преобразования

цветовых пространств для изображения размером 4134x2756

Для полноты рассмотрения вопроса приведём листинг обратного преобразования из цветового пространства Y709CbCr в RGB в соответствии с выражением (6) листинг 4.

Листинг 4. Преобразование значения из цветового пространства Y709CbCr в RGB, вычисления производятся в формате ФТ.

ColorSpace x; // пиксель типа ColorSpace 

int Y, Cb, Cr;

Y=(int)x.byteLo;

Cb=(int)x.byteAv;

Cr=(int)x.byteHi;

const int h=((2<<20)>>1); // h=524288;

// компонент (R)

x.byteLo=(uchar)(abs(1220689*Y-1152*Cb+1879436*Cr-259951428+h))>>20;

// компонент (G)

x.byteAv=(uchar)(abs(1220689*Y-223447*Cb-560263*Cr+80783763+h))>>20;

// компонент (B)

x.byteHi=(uchar)(abs(1220689*Y+2216249*Cb+1035*Cr-303343600+h))>>20;

Теперь рассмотрим программу выделения памяти для поля цифрового сигнала (листинг 5). В качестве примера возьмём статическое изображение с количеством оттенков 16777215 (0xFFFFFF), для сохранения элементов изображения будем использовать ранее созданную структуру ColorSpace (листинг 1).

Листинг 5. Выделение памяти для полноцветного изображения (C++)

// выделяем память

#pragma pack (push, 1)

// объявляем указатель на двумерный массив изображения

ColorSpace** data=0;

// iHeight - высота изображения (число строк)

// iWidth - ширина изображения (длина строк (столбцы))

data=new ColorSpace*[iHeight];

for (int i=0; i<iHeight; i++) {

data[i]=new ColorSpace[iWidth];

memset(data[i], 0, iWidth* sizeof(ColorSpace)); // инициализация нулём

}

#pragma pack (pop)

// используем выделенную память

// ...

// чистим память

for (int i=0; i<iHeight; i++)

delete[]data[i];

delete[]data;

data=0;

Отметим, что дефрагментация, возникающая при многократном выделении памяти, может препятствовать её эффективному использованию и снижению быстродействия. Существуют так называемые механизмы сборки мусора, позволяющие своевременно освобождать память.

Способ организации использования выделенного адресного пространства может существенно повлиять на эффективность вычислений [5, 13-15]. В (листинге 6) приведён пример различных способов перебора двумерного массива. Результаты работы программы для массива data размером  приведены на диаграмме (рис. 4). Очевидно, что перебор по столбцам, вложенный в перебор по строкам, работает примерно в два раза быстрее, чем другая пара вложенных циклов. Здесь надо отметить, что понятия строка и столбец достаточно условны, ведь память ЭВМ линейна. В соответствии с принятыми названиями (строк и столбцов) и последовательностью выделения памяти (листинг 5) соседние элементы строки, расположены по соседним адресам в физической памяти, а элементы столбцов - удалены друг от друга. Следовательно, при проходе по строке, возможно, более эффективно использовать преимущества внутрипроцессорной быстродействующей кэш-памяти, логику предсказания и меньше обращается к более медленной оперативной памяти [16].

Заметим, что при инициализации возможно многократно быстрее заполнять фрагменты памяти некоторым константным значением с помощью функций стандартной библиотеки C таких как memcpy, memset; при использовании C++, например, инициализацией вектора (std::vector) при объявлении. В некоторых случаях целесообразно использовать команды ассемблера для копирования блоков памяти.

Листинг 6. Сравнение способов перебора элементов двумерного массива (C++).

// заполнение двумерного массива изображения data

// значением содержащимся в temp

UColorSpace temp;

...

// проход по столбцам

for (uint j=0; j<iWidth; j++) {

// проход по строкам

for (uint i=0; i<iHeight; i++) {

temp.numb=(i+j);

data[i][j]=temp.rgb;

}

}

...

// проход по строкам

for (uint i=0; i<iHeight; i++) {

// проход по столбцам

for (uint j=0; j<iWidth; j++) {

temp.numb=(i+j);

data[i][j]=temp.rgb;

}

}

Рис. 4. Время выполнения теста:

способ перебора элементов двумерного массива

Оптимизация программы с точки зрения использования памяти и с учётом архитектуры конкретной ЭВМ, может существенно повысить скорость обработки данных.

Заключение

В статье сделан анализ принципов вычислительной оптимизации с применением арифметики с фиксированной точкой. Рассмотрен принцип практической реализации на примере взаимного преобразования цветовых пространств RGB в Y709CbCr. При применении фиксированной точки время вычислений для изображения 4134x2756 на процессоре Intel Core 2 Duo время вычислений сократилось в 18-ть раз. Такое повышение производительности является очень значимым. Не составляет труда применить указанный подход к прочим подобным вычислениям, особенно на современных 64-х и 128-ми разрядных процессорах, когда необходимые значения умещаются в один процессорный регистр. Сделан анализ способов перебора массива изображения, показано, что оптимальным является перебор по столбцам, вложенный в перебор по строкам.



Библиография

1. ITU-R Recommendation BT.601-7 от 03/2011, Studio encoding parameters of digital television for standard 4:3 and wide-screen 16:9 aspect ratios. ITU, Geneva, Switzerland, 2011.

2. ITU-R Recommendation BT.709, Basic Parameter Values for the HDTV Standard for the Studio and International Programme Exchange [formerly CCIR Rec.709] ITU, Geneva, Switzerland, 2002.

3. Malvar H. S., Sullivan G. J. Transform, Scaling & Color Space Impact of Professional Extensions, ISO/IEC JTC/SC29/WG11 and ITU-T SG16 Q.6 Document JVT-H031, Geneva, May 2003.

4. Гербер Р., Бик А., Смит К., Тиан К. Оптимизация ПО. Сборник рецептов. - СПб.: Питер, 2010. - 325 с.: ил

5. Касперский К. Техника оптимизации программ (+CD). С-Пб. Из-во: БХВ-Петербург, 2003 г. - 464 с.:ил.

6. Коробейников А.Г., Кудрин П.А., Сидоркина И.Г. Алгоритм распознавания трехмерных изображений с высокой детализацией//Вестник Поволжского государственного технологического университета. Серия: Радиотехнические и инфокоммуникационные системы. 2010. № 2. С. 91-98.

7. Гришенцев А.Ю., Коробейников А.Г. Методы и модели цифровой обработки изображений. - СПб. : Изд.-во Политехн. ун-та, 2014. - 190 с.

8. Гришенцев А.Ю., Коробейников А.Г. Понижение размерности пространства при корреляции и свертке цифровых сигналов//Известия высших учебных заведений. Приборостроение. 2016. Т. 59. № 3. С. 211-218.

9. Коробейников А.Г., Алексанин С.А. Методы автоматизированной обработки изображений при решении задачи магнитной дефектоскопии//Кибернетика и программирование. 2015. № 4. С. 49-61.

10. Коробейников А.Г., Федосовский М.Е., Алексанин С.А. Разработка автоматизированной процедуры для решения задачи восстановления смазанных цифровых изображений//Кибернетика и программирование. 2016. № 1. С. 270-291.

11. Гришенцев А. Ю., Коробейников А. Г. Декомпозиция n-мерных цифровых сигналов по базису прямоугольных всплесков. Научно-технический вестник информационных технологий, механики и оптики, 2012, № 4 (80).-С. 75-79

12. Гришенцев А. Ю. Эффективное сжатие изображений на базе дифференциального анализа. Российская академия наук «Журнал радиоэлектроники» http://jre.cplire.ru/jre/nov12/index.html, [электронный ресурс]// электронный журнал, ISSN 1684-1719, №11-ноябрь 2012 г.

13. Гришенцев А. Ю. Способ сжатия изображения. // Патент № 2500067, заявка № 2012107969/08, приоритет изобретения 01.03.2012, зарегистрировано в Государственном реестре изобретений РФ 27.11.2013.

14. Гришенцев А. Ю., Коробейников А. Г. Постановка задачи оптимизации распределённых вычислительных систем // Программные системы и вычислительные методы. - 2013.-№ 4.-С.370-375.

15. Гришенцев А.Ю. Моделирование распределения плотности тока в сложном неоднородном проводнике. Часть 1 // Научно-технический вестник информационных технологий, механики и оптики. 2006. № 29. С. 87-94.

16. Брей Б. Микропроцессоры Intel: 8086/8088, 80186/80188, 80286, 80386, 80486, Pentium, Pentium Pro, Pentium II, Pentium III, Pentium IV. Архитектура, программирование, интерфейсы. Шестое издание: Пер. с англ. - СПб.: БХВ-Петербург, 2005. - 1328 с.: ил.

Размещено на Allbest.ru