// компонент 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 с.: ил.