Алгоритм нарезки плоскостей (на месте) из массива значений RGB - PullRequest
Новая
       11

Алгоритм нарезки плоскостей (на месте) из массива значений RGB

7 голосов
/ 11 декабря 2011

У меня есть плоский массив байтовых значений RGB, который идет R1 G1 B1 R2 G2 B2 R3 G3 B3 ... Rn Gn Bn.Таким образом, мои данные выглядят так: 

char imageData[WIDTH * HEIGHT * 3];

Но я хочу передать массив WIDTH * HEIGHT в существующую библиотеку C, которая ожидает одну плоскость этих данных.Это будет последовательность только значений R (или просто G, или просто B).

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

ОДНАКО у меня есть доступ на запись в этот массив.Целесообразно создать процедуру, которая бы сортировала ее по цветовым плоскостям.Мне также понадобится обратное преобразование, которое вернет его обратно, но по определению тот же метод, который отсортировал его по плоскостям, мог бы быть применен для его сортировки.

Насколько эффективно я (на месте) могу превратить этот массив вR1 R2 R3 ... Rn G1 G2 G3 ... Gn B1 B2 B3 ... Bn а потом снова?Какие-нибудь не наивные алгоритмы?

Ответы [ 3 ]

1 голос
/ 11 декабря 2011

В этой статье «Простой алгоритм замены на месте» описывает, как транспонировать матрицу из 2 * N, и дает подсказку, как это сделать для других случаев, поэтому 3 * N может быть также возможно. Этот ответ на другой вопрос показывает, что это действительно возможно.

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

Оба алгоритма не подходят для кэширования. Возможно, какое-нибудь умное использование инструкции PREFETCH может улучшить это.

Edit:

C ++, RGB для отдельных плоскостей, не оптимизирован: 

#include <iostream>
#include <bitset>
#include <vector>

enum {N = 8};

void transpose(std::vector<char>& a)
{
  std::bitset<3*N> b;

  for (int i = 1; i < 3*N; ++i)
  {
    if (b[i])
      continue;

    int ptr = i;
    int next;
    char nextVal = a[i];

    do {
      next = ptr/3 + N*(ptr%3);
      char prevVal = nextVal;
      nextVal = a[next];
      a[next] = prevVal;
      ptr = next;
      b[ptr] = true;
    }
    while (ptr != i);
  }
}

int main()
{
  std::vector<char> a(3*N);

  for (int i = 0; i != 3*N; ++i)
    a[i] = i;

  transpose(a);

  for (int i = 0; i != 3*N; ++i)
    std::cout << (int)a[i] << std::endl;

  return 0;
}

Мое первоначальное намерение - использовать битовый вектор размером WIDTH HEIGHT, который дает служебную информацию WIDTH HEIGHT / 8. Но всегда можно пожертвовать скоростью ради космоса. Битовый вектор может иметь размер WIDTH или HEIGHT или любое желаемое значение, даже 0. Хитрость заключается в том, чтобы поддерживать указатель на ячейку, перед которой все значения транспонируются. Битовый вектор предназначен для ячеек, начиная с этого указателя. После того, как все это 1 с, он перемещается в следующую позицию, затем выполняются все шаги алгоритма, кроме фактического перемещения данных. И битовый вектор готов продолжить транспонирование. Этот вариант O (N ^ 2) вместо O (N).

Edit2:

Оптимизация PREFITCH не сложна для реализации: просто вычислите индексы, вызовите PREFETCH и поместите индексы в очередь (кольцевой буфер), затем получите индексы из очереди и переместите данные.

Edit3:

Идея другого алгоритма, который имеет размер O (1), время O (N * log (N)), является кеш-памятью и может быть быстрее, чем алгоритм "цикла" (для размеров изображения <1 Гб): </p>

  • Разделить матрицу N * 3 на несколько 3 * 3 матриц char и транспонировать их
  • Разделите результат на 3 * 3 матрицы char [3] и транспонируйте их
  • Продолжить, пока размер матрицы меньше размера массива
  • Теперь у нас есть до 3 * 2 * log3 (N) заказанных частей. Присоединяйтесь к ним.
  • Первые соединительные фигуры одинакового размера. Можно использовать очень простые «циклы» длины 4.
  • Соединение деталей неравного размера с реверсом (реверс (а), реверс (б))
1 голос
/ 12 декабря 2011

Если вам нужен только один самолет, это кажется довольно простым. Если вам нужны все 3, вам, вероятно, повезет больше с более сложным алгоритмом. 

void PlanarizeR(char * imageData, int width, int height)
{
    char *in = imageData;
    int pixelCount = width * height;
    for (int i = 0;  i < pixelCount;  ++i, in+=3)
        std::swap(*in, imageData[i])
}

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

0 голосов
/ 11 декабря 2011 
char *imageData = malloc (WIDTH * HEIGHT * 3 * sizeof(char));

эта функция делает это R1 R2 R3 ... Rn G1 G2 G3 ... Gn B1 B2 B3 ... Bn ,, 

char *toRGB(char *imageData, int WIDTH, int HEIGHT){
    int len = WIDTH * HEIGHT;
    char *RGB = malloc (len * sizeof(char));
    int i, j = 0,flag = 0;

    for(i=0 ; i<=len ; i++, j+=3){
        if(j<len)
            RGB[i] = imageData[j];
        else{
            switch(flag){
                case 0: j=-2; flag=1; break;   // j=-2 the next iteration will start at j=1
                case 1: j=-1; break;   // j=-1 the next iteration will start at j=2
            }
        }
    }
    return RGB;
}
...