用于从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]) 
} 

它应该不会太难运行循环从高到低反转过程。