用於從RGB值數組中切片平面的算法

Question

我有一個平面數組的字節RGB值，其值爲R1 G1 B1 R2 G2 B2 R3 G3 B3 ... Rn Gn Bn。所以，我的數據是這樣的：

char imageData[WIDTH * HEIGHT * 3]; 

但我想通過一個寬*高陣列到現有的C庫，預計這一數據的一個平面上。那將只是R值的序列（或者只是G，或者只是B）。

很容易分配新陣列並複製數據（duh）。但圖像非常大。如果它不是一個C庫，但採取了某種迭代界面來細化「切片」遍歷，那就太好了。但是我無法編輯我正在調用的代碼......它需要一個普通的舊指針指向一個連續內存塊。

但是我有寫入權限這個數組。創建一個可以將它分類到顏色平面的例程是可行的。我還需要一個反轉轉換，將它放回去，但根據定義，將它分類爲多個平面的相同方法可用於將它退出。

我該如何有效地將這個陣列變成R1 R2 R3 ... Rn G1 G2 G3 ... Gn B1 B2 B3 ... Bn然後再回來？任何非天真的算法？

Answer 1

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

Answer 2

本文"A Simple In-Place Algorithm for In-Shuffle"介紹如何轉置矩陣的2 * N，並給出了一個提示如何做其他情況下，所以3 * N也可能。 This answer to other question表明這確實是可能的。

或者使用一種算法將每個值寫入其置換位置，然後對該位置的值執行相同操作，直到循環連接。在位矢量中標記處理的值。並繼續，直到這個向量都是1。

這兩種算法都不支持緩存。可能一些聰明的PREFETCH指令可以改善這一點。

編輯：

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

我的原意是使用尺寸寬度的位向量HEIGHT，這給WIDTH的開銷身高/ 8。但總是有可能犧牲空間速度。位向量的大小可以是WIDTH或HEIGHT，也可以是任何希望的值，甚至是0。技巧是保持一個指向單元的指針，在這之前所有的值都被轉置。位向量用於單元格，從此指針開始。全部1秒後，移動到下一個位置，然後除了實際數據移動外，執行所有算法步驟。位矢量已準備好繼續轉置。這個變體是O（N^2）而不是O（N）。

EDIT2：

PREFITCH優化並不難實現：只要計算指標，調用PREFETCH，並把指標給隊列（ringbuffer），然後從隊列索引和移動數據。

EDIT3：

其他算法的想法，這是O（1）尺寸，O（N *日誌（N））的時間，是高速緩存友好，並且可以比 「循環」 算法快（對於圖像尺寸< 1GB）：

• 分割N * 3矩陣炭的幾個3×3點矩陣和轉置他們
• 拆分結果到炭的3×3矩陣[3]和轉置他們
• 繼續矩陣大小小於數組的大小
• 現在我們已經有3 * 2 * log3（N）有序的部分。加入他們。
• 首先加入大小相等的部分。可以使用長度爲4的非常簡單的「循環」。
• 加入不等大小的塊與反向（反向（一），反向（B））

Answer 3

如果你只需要一個平面，這似乎很容易。如果你需要全部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]) 
} 

它應該不會太難運行循環從高到低反轉過程。