3

I'm trying to make a function that shuffles an image as shown below: shuffle

Its argument takes three 600x400 RGB arrays to create the pixel colors. I have been trying to brainstorm this for so many hours but I'm so confused about methods to do it. Here's an idea I've tried working out, but I got overwhelmed and stumped with:

Copy each RGB array (R[][], G[][], and B[][] separately which combined makes a colored image) into their respective temporary arrays. Split the temporary arrays into a 4x4. Each element would contain its own 2D array with a block of the original image. Then using the random library I can assign the elements to new locations within the 4x4. I have no idea how to do this without making 42 arrays (16 arrays per color in the 4x4, but 42 arrays for R, G, and B). I would appreciate any advice or Here is the code I currently have, but I paused (or possibly abandoned) working on:

            void Shuffle(unsigned char R[WIDTH][HEIGHT], unsigned char G[WIDTH][HEIGHT], unsigned char B[WIDTH][HEIGHT]){

            // Initialize 150x100 inner shuffle arrays. These arrays are chunks of the original image
            int shuffArrR[150][100] = {0};
            int shuffArrG[150][100] = {0};
            int shuffArrB[150][100] = {0};

            int row = 0, col = 0;

        /*
                                BOUNDARY INFO FOR 4x4 ARRAY:

                                 C1: C2: C3: C4:    hBound# (row):
                                -------------------->   1
                           R1:  |   |   |   |   |
                                -------------------->   2
                           R2:  |   |   |   |   |
                                -------------------->   3                       
                           R3:  |   |   |   |   |
                                -------------------->   4
                           R4:  |   |   |   |   |
                                -------------------->   5
                                |   |   |   |   |
                                v   v   v   v   v

                vBound# (col):  1   2   3   4   5

                            vBound:         hBound:         
                            #:  col:        #:  row:
                            1    0          1    0
                            2   150         2   100
                            3   300         3   200
                            4   450         4   300
                            5   600         5   400
        */
            // Define boundaries
            int const vBound1 = 0, vBound2 = 150, vBound3 = 300, vBound4 = 450;
            int const hBound1 = 0, hBound2 = 100, hBound3 = 200, hBound4 = 300;

            for(row; row < HEIGHT; row++){
                for(col; col < WIDTH; col++){

                    // Copy RGB arrays to shuffle arrays
                    shuffArrR[col][row] = R[col][row];
                    shuffArrG[col][row] = G[col][row];
                    shuffArrB[col][row] = B[col][row];

                    // Define 16 blocks in 4x4 array ------------------

                    // If in R1
                    if(row >= hBound1 && row <= hBound2){

                        // And in C1
                        if(col >= vBound1 && col <= vBound2){
                            // ** I stopped here after I realized how many arrays I'd have to make to account for every element in the 4x4 **
                        }

                    }
                }
            }

        }
Eric
  • 117
  • 1
  • 2
  • 12
  • 2
    Assign an index (0,15) to each block in the original array. Create an array with those indexes `array[16] = {0,1,2,...,14,15};` [Fisher-Yates shuffle](https://en.wikipedia.org/wiki/Fisher–Yates_shuffle) the array. For entry in the shuffled array, the index is the block in the output image, and the value is the index of the block in the original image. – user3386109 Oct 25 '18 at 23:02
  • How would I assign indices for each of the 16 2D chunks? – Eric Oct 25 '18 at 23:19
  • Are you sure you're not converting it to a format more difficult to handle? Usually pixels are packed RGB or GRB. – Neil Oct 25 '18 at 23:47
  • I've expanded my earlier comment to an answer. –  Oct 26 '18 at 00:03

2 Answers2

2

Use a better data structure

Right now, you are using multi-dimensional arrays, which has certain upsides and downsides lightly touched on elsewhere on SO. Because what you are doing is image processing, performance may be critical for you, and dereferencing multi-dimensional arrays is not exactly optimal for a variety of reasons (i.e. you're likelier to lose performance due to non-sequential reads).

There are a couple of ways to both improve performance, while also making your life easier:

Interleaved one-dimensional array

Meaning, you should use a single unsigned char img[WIDTH * HEIGHT * COLORS] array. This has the benefit of making your code also easier to maintain, as you can then handle RGB, B&W and RGBA images with a change to the constant COLORS. To access a given color of a single pixel, you could have img[y * width * COLORS + x * COLORS + color]. You could also write a macro to help with that, e.g. 

#define INDEX_XYZ(x,y,color) ((y) * WIDTH * COLORS + (x) * COLORS + (color))

To further improve on the usability of the function, considering passing it the size of each dimension, along with the number of colors. For example, you could change the signature to be...

void Shuffle(unsigned char image[], int height, int width, int colors);

Which would allow you to use the same function on images of any size (as long as both dimensions are divisible by four) and any color. You might also want to pass an argument indicating the number of subdivisions, so you could have a 3-by-3 segmentation or 8-by-8 segmentation if you wanted, and without having to change the function or repeat the code.

Split the image into segments

One way to do this would be to create the arrays for the segments...

unsigned char segments[SEG_HORI * SEG_VERT][WIDTH / SEG_HORI * HEIGHT / SEG_VERT * COLOR];

Note the multidimensionality - it is fine here, as it is desirable for us to have a number of separate segment to store the data in.

After which we copy data from the original:

// Calculate the height/width for the segments; you could do this as a macro too.
int seg_height = HEIGHT / SEG_VERT;
int seg_width = WIDTH / SEG_HORI;
// Iterate through the rows in the picture
for (int y = 0; y < HEIGHT; y++) 
{
    // Obtain the Y-coordinate of the segment.
    int segy = y / seg_height;

    // Iterate through the columns in the picture
    for (int x = 0; x < WIDTH; x++)
    {
        // Calculate the X-coordinate of the segment.
        int segx = x / seg_width,

        // Then calculate its index, using the X and Y coordinates.
            seg  = segy * SEG_HORI + segx,
        // Then, calculate the source index (from the image).
            src_idx = y * WIDTH * COLORS + x * COLORS,

        // Then, map the coordinates to the segment; notice that we take
        // modulos on the coordinates to get them to correctly map.
            dst_idx = y % seg_height * seg_width * COLORS + x % seg_width * COLORS;

        // Then copy the colors. You could also use memcpy(),
        // but the below should be more educational.
        for (int c = 0; c < COLORS; c++)
            segments[seg][dst_idx + c] = img[src_idx + c];
    }
}

Now, the image has been copied into the segments, and you can reorder them as you wish, as the "segments" are simply pointers. For example, the below would swap the top-left and the bottom-right segments.

unsigned char seg_temp[] = segments[0];
segments[0] = segments[15];
segments[15] = seg_temp;

Finally, to finalize the process and merge the segments back together, you need to redo the process above in reverse; it should be quite trivial to do, so I'll leave it for you as an exercise.

Final Notes

If you haven't already, you should familiarize yourself with the malloc() and free() functions, as well as memset() and memcpy(). They should prove very useful in the future, and would also improve the performance here as then you could copy everything into a destination array (along with the shuffle) in n operations, instead of modifying the original in 2n.

Disclaimer 1: I haven't ran any of the code through a compiler. No guarantees that it will work out of the box.

Disclaimer 2: I also do not claim the code to be well-optimized. Have to leave something for you to do.

1

  1. Label each block with an ID, 0, 1, 2, ...15 .

    -----------------
| 12| 13| 14| 15|
-----------------
| 8 | 9 | 10| 11|
-----------------                      
| 4 | 5 | 6 | 7 |
-----------------
| 0 | 1 | 2 | 3 |
-----------------

  2. Put all ID in an array, then shuffle the array. shuffle like this. Then traversal the array and swap content of each block. 

    int arr[16] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
arr_shuffle(arr, 16);
int i;
for (i = 0; i < 16; i++) {
    swap_block(i, arr[i]);
}

  3. Now the problem will be how to swap two block. Let's say we have block A and block B. Both size should be 100(height) * 150(width). Then think A is an array like A[100][150], and B is B[100][150]. swap this array will be like below.

    for (i = 0; i < 100; i++) {
    for (j = 0; j < 150; j++) {
        swap(A[i][j], B[i][j];
    }
}

  4. The final step should be convert A[i][j] and B[i][j] to the real element in array R/G/B. This can be done simply by math. 

    void get_real_id(int block_id, int x, int y, int *real_x, int *real_y)
{
    int row, col;

    row = block_id / 4;   // convert block id to row number
    col = block_id % 4;   // convert block id to col number

    // find BLOCK[y][x] in array R, which should be R[real_y][real_x]
    *real_x = (col * (WIDTH/4)) + x;  
    *real_y = (row * (HEIGHT/4)) + y;
}

  5. The sample code in below will work for array R. The define of R is R[HEIGHT][WEIGHT], not R[WEIGHT][HEIGHT] (This define should work too but I can't think with it).

    int R[HEIGHT][WIDTH];

int arr_shuffle(int *arr, int len)
{
    size_t i;
    for (i = 0; i < len - 1; i++)
    {
        size_t j = i + rand() / (RAND_MAX / (len - i) + 1);
        int t = arr[j];
        arr[j] = arr[i];
        arr[i] = t;
    }
}

void get_real_id(int block_id, int x, int y, int *real_x, int *real_y)
{
    int row, col;

    row = block_id / 4;
    col = block_id % 4;

    *real_x = (col * (WIDTH/4)) + x;
    *real_y = (row * (HEIGHT/4)) + y;
}

void swap_block(int src, int dst)
{
    int w_len = WIDTH / 4;  // should be 150
    int h_len = HEIGHT / 4; // should be 100

    int i, j;

    for (i = 0; i < h_len; i++) {
        for (j = 0; j < w_len; j++) {
            int real_src_x;
            int real_src_y;

            int real_dst_x;
            int real_dst_y;

            get_real_id(src, j, i, &real_src_x, &real_src_y);
            get_real_id(dst, j, i, &real_dst_x, &real_dst_y);

            // swap two point.
            int r = R[real_src_y][real_src_x];
            R[real_src_y][real_src_x] = R[real_dst_y][real_dst_x];
            R[real_dst_y][real_dst_x] = r;
        }
    }
}

int Shuffle()
{
    int i;
    int arr[16] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};

    arr_shuffle(arr, 16);

    for (i = 0; i < 16; i++) {
        int src_block_id = i;
        int dst_block_id = arr[i];

        swap_block(src_block_id, dst_block_id);
    }
}

  6. I should mention there is chance that after the Shuffle nothing changes.

randomeval
  • 599
  • 4
  • 13