Самое быстрое преобразование упорядоченных по строкам данных в упорядоченные по столбцам данные

Question

У меня есть IplImage от openCV, который хранит свои данные в упорядоченном формате;

данные изображения хранятся в одномерном массиве char * data; элемент в положении x, y задается как

elem(x,y) = data[y*width + x] // see note at end

Я бы хотел как можно быстрее преобразовать это изображение во второй формат изображения, в котором его данные хранятся в упорядоченном по столбцам формате; то есть

elem(x,y) = data[x*height + y]

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

Есть ли более быстрый путь?

---

обратите внимание, что для openCV afficionados фактическое расположение элемента elem (x, y) задается как data + y*widthstep + x*sizeof(element), но это дает общее представление, а для данных char sizeof (element) = 1, и мы можем сделать widthstep = width, поэтому формула точная

Answer 1

Это называется «матричным транспонированием». Оптимальные методы пытаются минимизировать количество пропусков кеша, меняя местами маленькие тайлы размером один или несколько слотов кеша.Для многоуровневого кэша это будет сложно. начните читать здесь

этот немного более продвинутый

Кстати, URL имеют дело с транспозицией "на месте".Создание транспонированной копии будет другим (она использует вдвое больше слотов для кеша, да!)

Answer 2

Вы вроде ответили сами, но без кода. Я думаю, что вам нужно что-то вроде:

typedef struct
{
    unsigned char r;
    unsigned char g;
    unsigned char b;
}somePixelFormat;

#define HEIGHT 2
#define WIDTH  4

// let's say this is original image width=4 height=2 expresed as one dimentional
// array of structs that adhere to your pixel format
somePixelFormat src[ WIDTH * HEIGHT ] = 
{
    {0,0,0}, {1,1,1}, {2,2,2}, {3,3,3},
    {4,4,4}, {5,5,5}, {6,6,6}, {7,7,7}
};

somePixelFormat dst[ WIDTH * HEIGHT ];

void printImage( void *img, int width, int height, int pixelByteCount )
{
    for ( int row = 0; row < height; row++ )
    {
        for ( int col = 0; col < width; col++ )
        {
            printf( "(%02d,%02d,%02d) ", ((somePixelFormat*)img + width * row + col)->r,
                                         ((somePixelFormat*)img + width * row + col)->g,
                                         ((somePixelFormat*)img + width * row + col)->b );
        }

        printf ( "\n" );
    }
    printf("\n\n");
}

void flip( void *dstImg, void *srcImg, int srcWidth, int srcHeight, int pixelByteCount )
{
    for ( int row = 0; row < srcHeight; row++ )
    {
        for ( int col = 0; col < srcWidth; col++ )
        {
            *((somePixelFormat*)dstImg + srcHeight * col + row) = *((somePixelFormat*)srcImg + srcWidth * row + col);
        }
    }
}

int main()
{
    printImage( src, 4, 2, sizeof(somePixelFormat) );
    flip( dst, src, 4, 2, sizeof(somePixelFormat) );
    printImage( dst, 2, 4, sizeof(somePixelFormat) );

    getchar();
    return 0;
}

А вот пример вывода:

(00,00,00) (01,01,01) (02,02,02) (03,03,03) 
(04,04,04) (05,05,05) (06,06,06) (07,07,07) 


(00,00,00) (04,04,04) 
(01,01,01) (05,05,05) 
(02,02,02) (06,06,06) 
(03,03,03) (07,07,07) 

Answer 3

Предполагая, что вам нужен новый массив, в котором все элементы перемещены, самая быстрая с алгоритмической скоростью, которой вы можете управлять, - это O (N) по числу элементов (то есть ширина * высота).

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

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

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