Компьютерная Графика и Мультимедиа Сетевой журнал

О правильном и быстром доступе к изображениям написано во всех книжках по компьютерной графике. Тем не менее, в работе постоянно сталкиваюсь с тем, что даже достаточно опытные программисти (не говоря уж о студентах) то и дело выдают код типа 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(NULL), 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;
  }
}

Для пятимегапиксельной картинки закраска ее белым цветом обойдется в 45 000 000 умножений, 25 000 000 сложений и 15 000 000 индексаций... Не правда ли, лучше потратить все эти миллионы операций на что-то более полезное.

Как можно ускорить этот код? Пожалуйста:

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;  
   }
}

Для нашего пятимегапиксельного изображения этот код потребует в самом худшем случае (изображение 1x5000000) 5 000 000 умножений и 15 000 000 сложений. В типичном случае (при соотношении размеров изображение 4:3) ~2000 умножений и ~15 000 000 сложений (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 ; // ключевой момент: переход на следующей пиксель без индексации
}

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

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

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

Что же делать, если без прямого доступа к пикселям никуда, как оптимизировать SetPixel ? Об этом в другой раз.