2012-02-01 78 views
2

我有一个来自openCV的IplImage,它以行排序格式存储其数据;将行排序数据最快转换为列顺序数据

图像数据存储在一维数组char * data;在位置x处的元素,Y是由

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

我想这个图像尽可能快地转换为与从存储在它的列排序的格式数据的第二图像格式;那就是

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

显然,做这种转换的一种方法是通过一个double for循环来逐个元素。

有没有更快的方法?


音符为OpenCV的afficionados,ELEM的实际位置(X,Y)由data + y*widthstep + x*sizeof(element)给出但是这给的总体思路,以及用于char数据的sizeof(元件)= 1,我们可以使widthstep =宽度,所以公式是精确的

+0

双for循环将是对元素的数量O(N),你不能击败,因为你有将它们全部复制,但是在你的for循环中,可能会有一些你不需要每次执行的乘法。几乎不可能产生任何性能差异。如果图像很大,你当然可以将进程分成多个线程。 – CashCow 2012-02-01 18:01:33

+0

[缓存高效矩阵移调程序?]的可能重复(http://stackoverflow.com/questions/5200338/a-cache-efficient-matrix-transpose-program) – 2012-02-01 18:02:52

+0

您是否绝对需要复制它?如果你必须的话,没有更快的方法。你的复制算法是最优的,因为每个元素确实需要被访问。如果您不复制它,请考虑交换索引 - 也就是说,无论何时您需要索引索引,都用(i,j)而不是(i,j)索引它。你能做到吗?你可以很容易地看到这需要O(1)时间(也许O(1)空间)。 – mrm 2012-02-01 18:03:00

回答

4

它被称为“矩阵转置” 最佳方法尽量减少高速缓存未命中的数量,交换小青瓦 一个的大小或几个高速缓冲存储器槽。对于多级缓存,这将变得困难。 start reading here

this one is a bit more advanced

BTW的URL处理 “到位” 换位。创建转置副本将有所不同(它使用两倍的缓存插槽,杜!)

0

假设你需要一个新的数组,所有的元素都移动了,你可以用算法速度管理的最快速度是元素个数(即宽度*高度)的O(N)。

对于实际需要的时间,可能会产生多个线程,其中每个线程都复制一些元素。这当然是值得的,如果你确实有很多。

如果已经创建了线程并且它们接受队列中的任务或任何其他任务,那么如果要处理大量这些图像,这将是最有效的。

在您的个人“循环”中,您可以避免多次执行相同的乘法操作,当然,指针运算可能比随机访问快一点。

+2

我怀疑多个线程将在这里帮助。矩阵转置完全是内存绑定的,所以这一切都取决于您如何使用缓存。 – 2012-02-01 18:06:29

0

你有种回答自己,但没有代码。我认为你需要某事像:

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) 
+0

感谢您的建议Artur。我在问如何在没有double for循环的情况下这样做,因为根据体系结构的不同,复制连续的内存块比一次创建副本要快得多。 – Marc 2012-02-01 22:25:12