Два правила доступа к пикселям

О правильном и быстром доступе к изображениям написано во всех книжках по компьютерной графике. Тем не менее, в работе постоянно сталкиваюсь с тем, что даже опытные программисты (не говоря уж о студентах) то и дело выдают код типа SetPixel(x,y) или m_image[y * width * 4 + x], что приводит к плачевным результатам. Обработка изображений такого не прощает. В этой заметке мы попробуем разработать простой класс для хранение изображения и рассмотрим, как с ним можно (и нужно) быстро работать. Поможет новичкам.

Пустая “оболочка” класса выглядит следующим образом:

class Image
{
};

Вопрос первый. Как хранить изображение?

Будем хранить изображение в виде матрицы, развернутой по строкам слева-направо (это не единственно возможное представление, но одно из наиболее популярных). Будем считать, что ширина изображения W, высота — H, цвет представлен — 24бит RGB.

Записать это можно так:

class Image
{
 private:
 unsigned char m_image[ W * H * 3];
};

Но изображения фиксированного размера встречаются редко, поэтому нужно использовать динамическое выделение памяти. Заодно добавим конструктор/деструктор и метод для создания изображения нужного размера.

class Image
{
 public:

 Image()
 : m_image(0), m_width(0), m_height(0)
 { }

~Image()
 {
 DeleteImage();
 }

 void Create(int in_width, int in_height)
 {
   DeleteImage();
   m_image = new unsigned char[in_width * in_height * 3];
 }

 int Width() const { return m_width; }
 int Height() const { return m_height ;}

private:

 void DeleteImage()
 {
   delete[] m_image;
   m_image = NULL;
   m_width = 0;
   m_height = 0;
 }

private:

 unsigned char* m_image;
 int m_width;
 int m_height;
};

Теперь у нас есть простое изображение (не рассматриваем вопросы копирования и т.п.). Можно переходить к его изменению.

Формулы для получения индекса начала пикселя с координатами x,y (и обратные к ним) известны:

i = elementSize * (y * width + x);

x = (i / elementSize) % width;
y = (i / elementSize) / width;

(в нашем случае elementSize = 3)

Поэтому первое, что пишет студент, которому нужно поставить красную точку в положение (x,y), это следующее:

void SetPixel(int x, int y, unsigned char r, unsigned char g, unsigned char b)
{
 m_image[y * width * 3 + x * 3] = r;
 m_image[y * width * 3 + x * 3 + 1] = g;
 m_image[y * width * 3 + x * 3 + 2] = b;
}

...

Image img;
img.SetPixel(x, y, 255, 0, 0);

Если не надеяться на оптимизирующий компилятор, получаем 9 умножений, 5 сложений и 3 индексации на пиксель. Ну хорошо…

А теперь нужно закрасить красным цветом все изображение (тем более, что в нашем классе не предусмотрена первичная закраска картинки).

Получаем:

for(int x = 0; x < width; ++x)
{
 for(int y = 0; y < height; ++y)
 {
 m_image[y * width * 3 + x * 3] = 255;
 m_image[y * width * 3 + x * 3 + 1] = 0;
 m_image[y * width * 3 + x * 3 + 2] = 0;
 }
}

Для пятимегапиксельной картинки закраска ее белым цветом обойдется в 45000000 умножений, 25000000 сложений и 15000000 индексаций… Не правда ли, лучше потратить все эти миллионы операций на что-то более полезное?

Как можно ускорить этот код? Например, так:

int bytesPerLine = width * 3;
for(int y = 0; y < height; ++y)
{
 unsigned char* line = m_image + y * bytesPerLine;
 for(int x = 0; x < width; ++x)
 {
 *line = 255; ++line;
 *line = 0; ++line;
 *line = 0; ++line;
 }
}

Для нашего пятимегапиксельного изображения этот код потребует в самом худшем случае (изображение 1×5000000) 5000000 умножений и 15000000 сложений. В типичном случае (при соотношении размеров изображение 4:3) ~2000 умножений и ~15000000 сложений (0,0004 умножения и 3 сложения на пиксель). Есть разница, не правда ли? И на практике этот код в десятки раз быстрее “SetPixel-style” варианта.

Этого удалось добиться за счет замены прямых индексаций на арифметику указателей. Отсюда правило первое:

Правило 1. При массовой обработке пикселей изображения никогда не используйте прямые индексации по координатам пикселя. Вместо этого используйте арифметику указателей.

Это может быть оправдано только при рисовании отдельных точек (что на практике встречается довольно редко).

Поэтому добавим в определение нашего класса функции GetImage() и GetBytesPerLine():

unsigned char* GetImage() { return m_image; }
int BytesPerLine() const {return m_width * 3; }

Рассмотренный подход также отлично работает при копировании изображений с какими-либо преобразованиями:

Image srcImage;
Image dstImage;

... (пропускаем создание изображений, считаем, что размер одинаковый) ...

// внутри умножение, поэтому сохраняем
int bytesPerLineSrc = srcImage.BytesPerLine();
int bytesPerLineDst = dstImage.BytesPerLine();

for(int y = 0; y < srcImage.Height(); ++y)
{
 unsigned char* lineSrc =
   srcImage.GetImage() + y * bytesPerLineSrc;
 unsigned char* lineDst =
   dstImage.GetImag() + y * bytesPerLineDst;
 for(int x = 0; x < srcImage.Width(); ++x)
 {
 lineDst[0] = SomeFunc(lineSrc[0]);
 lineDst[1] = SomeFunc(lineSrc[1]);
 lineDst[2] = SomeFunc(lineSrc[2]);
 }
}

Внимание, не пытайтесь заменить строчки

lineDst[x] = SomeFunc(lineSrc[x]);

циклом:

for(int i = 0; i < 3; ++i)
 lineDst[i] = SomeFunc(lineSrc[i]);

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

Хорошо, а что если нам нужно нарисовать вертикальную линию? Не будет ли проще воспользоваться вариантом с явной индексацией? Проще может и будет, но не быстрее.

Вот как реализуется рисование вертикальной линии цвета (r,g,b) и точки (x1, y1) в точку (x1, y2):

int bytesPerLine = m_image.GetBytesPerLine();
unsigned char* line = m_image.GetImage()[y1 * bytesPerLine + x1 * 3];

for(int y = y1; y <= y2; ++y)
{
 line[0] = r;
 line[1] = g;
 line[2] = b;
 line += bytesPerLine ; // ключевой момент: переход на следующей пиксель без индексации
}

Здесь мы воспользовались тем, что в нашем “вытянутом” в одномерный массив изображении расстояние по вертикали между соседними пикселями равно ширине изображения. Фактически, это частный случай инкрементного вычисления координат по известным (предыдущим). Этот же подход работает при рисовании наклонных линий (алгоритм Брезенхема).

Отсюда второе правило:

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

Статья впервые опубликована в авторской колонке сетевого журнала «Компьютерная графика и мультимедиа» ).

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход /  Изменить )

Google photo

Для комментария используется ваша учётная запись Google. Выход /  Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход /  Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход /  Изменить )

Connecting to %s

На платформе WordPress.com. Тема: Baskerville 2, автор: Anders Noren.

Вверх ↑

%d такие блоггеры, как: