Image Dividing in C for DCT

Question

Can anyone please tell us how to divide the image into 8X8 blocks?

I can read the image, but not divide it into an 8x8 submatrix for DCT.

int main()
{
    FILE *image_raw;
    unsigned char **matriz_image;
    int i, j;
    int rows=1080, colums=1920;

    matriz_image = (unsigned char  **) malloc (rows*sizeof(unsigned char *));

    //i create dinamic colums
    for(i=0; i<rows; i++)
    {
        matriz_image[i] = (unsigned char *) malloc (colums*sizeof(unsigned char ));
    }

    //i open image raw
    image_raw =  fopen("imag.dat", "r+b");
    //i copy values to matriz_image


    for (i = 0; i < rows; ++i)
    {
        fread(matriz_image[i], sizeof(unsigned char ), colums, image_raw);
    }


    for(i=0; i<rows; i++)
    {
        for(j=0; j<colums; j++)
        {
            // printf("%i ",*(*(matriz_image+i)+j));
            printf("%i ",matriz_image[i][j]);
        }
        printf("\n");
    }

Answer 1

You could do something like this:

void dct(unsigned char **m, int baserow, int basecol)
{
  for (int row = baserow, endrow = baserow + 8; row < endrow; ++row)
    for (int col = basecol, endcol = basecol + 8; col < endcol; ++col)
      ; // operate on m[row][col]
}

int do_dcts(unsigned char **m, int num_rows, int num_cols)
{
  if (num_rows <= 0 || num_rows % 8 || num_cols <= 0 || num_cols % 8)
    return -1;

  for (int row = 0; row < num_rows; row += 8)
    for (int col = 0; col < num_cols; col += 8)
      dct(m, row, col);    

  return 0;
}

You are wasting space and worsening your memory locality by implementing your 2D array using two levels of pointers. It's better to do one allocation and then offset into the array appropriately like so:

int main()
{
    FILE *image_raw;
    unsigned char *matriz_image;
    int i, j;
    int rows=1080, colums=1920;

    matriz_image = malloc(rows*colums*sizeof(unsigned char));

    ...

If you can make rows and colums constants or have VLAs, then you can do:

unsigned char (*m)[colums] = (unsigned char (*)[colums]) matriz_image;

m[5][2] = 2; // double indexed access without extra pointers + allocs

Similarly you can pass m's kind of pointer to your matrix to your functions to operate on it.

If you can't make rows and colums be compile-time constants and you don't have VLAs, then you can write helper fcns to do pointer arithmetic for you:

inline unsigned char *get_row(unsigned char *m, int numcols, int row)
{
  return &m[row * num_cols];
}

inline unsigned char *get_elem(unsigned char *m, int numcols, int row, int col)
{
  return &m[row * num_cols + col];
}

...

*get_elem(m, colums, 5, 2) = 2;  // double indexing not as nice but good memory usage

If you really need to get fast for these operations, then as you read your image in, you could reorganize it to lay the 8x8 bytes blocks contiguously in memory to have the best possible cache performance:

// organize m like m[rows * colums / 64][8][8]; so first index is an 8x8 block #

for (int k = 0; k < rows / 8; ++k)        // read all rows in chunks of 8
  for (int i = 0; i < 8; ++i)             // read 8 rows
    for (int j = 0; j < colums / 8; ++j)  // read 1 row in 8 byte chunks
      fread(&m[k * 8 * colums + i * 8 + j * 64], 1, 8, image_raw);

...

typedef unsigned char (*block_ptr)[8];

inline block_ptr get_block(unsigned char *m, int num_cols, int block_num)
{
  return (block_ptr) &m[block_num * 64];
}

inline block_ptr get_block2(unsigned char *m, int num_cols, int row, int col)
{
  if (row % 8 || col % 8)
    return NULL;

  return (block_ptr) &m[row * num_cols + col * 8];
}

...

for (int k = 0; k < rows * colums / 64; ++k)
{
  block_ptr block = get_block(m, num_colums, k);

  for (int i = 0; i < 8; ++i)
    for (int j = 0; j < 8; ++j)
      ;  // operate on block[i][j];
}