Algorithm for cut planes (in place) from an array of RGB values

Question

I have a flat RGB byte array that goes R1 G1 B1 R2 G2 B2 R3 G3 B3 ... Rn Gn Bn . Therefore, my data looks like this:

 char imageData[WIDTH * HEIGHT * 3]; 

But I want to pass the WIDTH * HEIGHT array to an existing C library that expects one plane of this data. This will be a sequence of only R values ​​(or just G, or just B).

It is easy enough to select a new array and copy the data (duh). But the images are very large. If it wasn’t C library, but some kind of iterative interface to improve the “trim” of the bypass, that would be great. But I can’t edit the code I call ... it wants a simple old pointer to a block of serial memory.

HOWEVER, I have write access to this array. You can create a routine that will sort it in color planes. I will also need an inverse transform that will return it, but by definition the same method that sorted it in planes could be used to undo it.

How much can I (in place) turn this array into R1 R2 R3 ... Rn G1 G2 G3 ... Gn B1 B2 B3 ... Bn , and then again? Any non-naive algorithms?

Answer 1

This article, “A Simple In-Place In-Shuffle Algorithm,” describes how to transpose a 2 * N matrix and gives a hint on how to do this for other cases, so 3 * N is possible. This answer to another question shows that this is really possible.

Or use an algorithm that writes each value to its transposed location, then does the same for the value from that location, and so on, until the loop is connected. The flag processes values ​​in a bit vector. And continue until this vector is 1s.

Both algorithms are not caching. Perhaps some clever use of the PREFETCH statement can improve this.

Edit:

C ++, RGB for single planes, not optimized:

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

My initial intention is to use a WIDTHHEIGHT-sized bit vector that gives the WIDTHHEIGHT / 8 overhead. But you can always sacrifice speed for space. The bit vector can be either WIDTH or HEIGHT, or any desired value of 0. The trick is to maintain a pointer to the cell in front of which all values ​​are transposed. The bit vector for cells starting at this pointer. After this is all 1s, it moves to the next position, then all the steps of the algorithm are performed, except for the actual data movement. And bit-bit is ready to continue transposing. This option is O (N ^ 2) instead of O (N).

Edit2:

PREFITCH optimization is not difficult to implement: just calculate the indexes, call PREFETCH and put the indexes in the queue (ringbuffer), then get the indexes from the queue and move the data.

Edit3:

The idea of ​​another algorithm that has size O (1), time O (N * log (N)), is cached and can be faster than the loop algorithm (for image sizes <1Gb):

• Divide the N * 3 matrix into several 3 * 3 char matrices and transfer them
• Divide the result into 3 * 3 char [3] matrices and transfer them
• Continue while matrix size is smaller than array size
• Now we have up to 3 * 2 * log3 (N) ordered parts. Join them.
• Connect pieces of the same size first. Very simple “cycles” of length 4 can be used.
• Combine fragments of unequal size with reverse (reverse (a), reverse (b))

Answer 2

If you only need one plane, this seems pretty simple. If you need all 3, you are probably lucky with a more complex algorithm.

 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]) } 

It should not be too difficult to start the cycle back from high to low to cancel the process.

Answer 3

 char *imageData = malloc (WIDTH * HEIGHT * 3 * sizeof(char)); 

this function does it 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; }