將行排序數據最快轉換爲列順序數據

我有一個來自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 =寬度，所以公式是精確的

來源

2012-02-01 Marc

雙for循環將是對元素的數量O（N），你不能擊敗，因爲你有將它們全部複製，但是在你的for循環中，可能會有一些你不需要每次執行的乘法。幾乎不可能產生任何性能差異。如果圖像很大，你當然可以將進程分成多個線程。 – CashCow 2012-02-01 18:01:33

[緩存高效矩陣移調程序？]的可能重複（http://stackoverflow.com/questions/5200338/a-cache-efficient-matrix-transpose-program） – 2012-02-01 18:02:52

您是否絕對需要複製它？如果你必須的話，沒有更快的方法。你的複製算法是最優的，因爲每個元素確實需要被訪問。如果您不復制它，請考慮交換索引 - 也就是說，無論何時您需要索引索引，都用（i，j）而不是（i，j）索引它。你能做到嗎？你可以很容易地看到這需要O（1）時間（也許O（1）空間）。 – mrm 2012-02-01 18:03:00

它被稱爲「矩陣轉置」最佳方法儘量減少高速緩存未命中的數量，交換小青瓦一個的大小或幾個高速緩衝存儲器槽。對於多級緩存，這將變得困難。 start reading here

this one is a bit more advanced

BTW的URL處理「到位」換位。創建轉置副本將有所不同（它使用兩倍的緩存插槽，杜！）

來源

2012-02-01 18:05:56 wildplasser

假設你需要一個新的數組，所有的元素都移動了，你可以用算法速度管理的最快速度是元素個數（即寬度*高度）的O（N）。

對於實際需要的時間，可能會產生多個線程，其中每個線程都複製一些元素。這當然是值得的，如果你確實有很多。

如果已經創建了線程並且它們接受隊列中的任務或任何其他任務，那麼如果要處理大量這些圖像，這將是最有效的。

在您的個人「循環」中，您可以避免多次執行相同的乘法操作，當然，指針運算可能比隨機訪問快一點。

來源

2012-02-01 18:04:54 CashCow

我懷疑多個線程將在這裏幫助。矩陣轉置完全是內存綁定的，所以這一切都取決於您如何使用緩存。 – 2012-02-01 18:06:29

你有種回答自己，但沒有代碼。我認爲你需要某事像：

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)

來源

2012-02-01 18:53:18 Artur

感謝您的建議Artur。我在問如何在沒有double for循環的情況下這樣做，因爲根據體系結構的不同，複製連續的內存塊比一次創建副本要快得多。 – Marc 2012-02-01 22:25:12

將行排序數據最快轉換爲列順序數據

回答

相關問題