Image Processing Median Filter in C

Question

I am attempting to perform Median Filter with size 3 x 3 in C language. The function MedianFilter33 has been implemented as follows.

The experimental implementation

• The basic structures:

  typedef struct RGB
  {
   unsigned char R, G, B;
  } RGB;
  typedef struct BMPIMAGE
  {
   char FILENAME[MAX_PATH];
   unsigned int XSIZE;
   unsigned int YSIZE;
   unsigned char FILLINGBYTE;
   unsigned char *IMAGE_DATA;
  } BMPIMAGE;
  typedef struct RGBIMAGE
  {
   unsigned int XSIZE;
   unsigned int YSIZE;
   RGB *IMAGE_DATA;
  } RGBIMAGE;
  

• MedianFilter33 function implementation:

  RGB *MedianFilter33(const RGB *image,const int xsize,const int ysize)
  {
   RGB *output;
   output = (RGB*)malloc(xsize * ysize * sizeof(RGB));
   if (output == NULL)
   { 
   printf("Memory allocation error!");
   return NULL;
   }
   for(long long int i = 0; i <(xsize * ysize); i++)
   {
   if( (i < xsize) || ( (i % xsize) == 0) || ( ((i + 1) % xsize) == 0) || (i >= (xsize*(ysize-1))))
   {
   output[i].R = image[i].R;
   output[i].G = image[i].G;
   output[i].B = image[i].B;
   } 
   else
   {
   unsigned char *sort_array;
   sort_array = (unsigned char*)malloc(9 * sizeof(unsigned char));
   // R channel sorting
   sort_array[0] = image[i-xsize-1].R;
   sort_array[1] = image[i-xsize].R;
   sort_array[2] = image[i-xsize+1].R;
   sort_array[3] = image[i-1].R;
   sort_array[4] = image[i].R;
   sort_array[5] = image[i+1].R;
   sort_array[6] = image[i+xsize-1].R;
   sort_array[7] = image[i+xsize].R;
   sort_array[8] = image[i+xsize+1].R;
   sort_array = bubble_sort_uchar(sort_array,9,0);
   output[i].R = sort_array[4];
   // G channel sorting
   sort_array[0] = image[i-xsize-1].G;
   sort_array[1] = image[i-xsize].G; 
   sort_array[2] = image[i-xsize+1].G;
   sort_array[3] = image[i-1].G; 
   sort_array[4] = image[i].G; 
   sort_array[5] = image[i+1].G; 
   sort_array[6] = image[i+xsize-1].G;
   sort_array[7] = image[i+xsize].G; 
   sort_array[8] = image[i+xsize+1].G;
   bubble_sort_uchar(sort_array,9,0);
   output[i].G = sort_array[4];
   // B channel sorting
   sort_array[0] = image[i-xsize-1].B;
   sort_array[1] = image[i-xsize].B; 
   sort_array[2] = image[i-xsize+1].B;
   sort_array[3] = image[i-1].B; 
   sort_array[4] = image[i].B; 
   sort_array[5] = image[i+1].B; 
   sort_array[6] = image[i+xsize-1].B;
   sort_array[7] = image[i+xsize].B; 
   sort_array[8] = image[i+xsize+1].B;
   bubble_sort_uchar(sort_array,9,0);
   output[i].B = sort_array[4];
   }
   }
   return output;
  }
  

Full Testing Code

In order to test MedianFilter33 function implementation above, a tiny bmp image read / write framework has been performed.

/* Develop by Jimmy Hu */
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#define MAX_PATH 256
#define FILE_ROOT_PATH "./"
#define True true
#define False false
typedef struct RGB
{
 unsigned char R, G, B;
} RGB;
typedef struct BMPIMAGE
{
 char FILENAME[MAX_PATH];
 
 unsigned int XSIZE;
 unsigned int YSIZE;
 unsigned char FILLINGBYTE;
 unsigned char *IMAGE_DATA;
} BMPIMAGE;
typedef struct RGBIMAGE
{
 unsigned int XSIZE;
 unsigned int YSIZE;
 RGB *IMAGE_DATA;
} RGBIMAGE;
RGB *MedianFilter33(const RGB*, const int x, const int y);
RGB *raw_image_to_array(const unsigned char *image, const int xsize, const int ysize);
unsigned long bmp_read_x_size(const char *filename, const bool extension);
unsigned long bmp_read_y_size(const char *filename, const bool extension);
char bmp_read(unsigned char *image, const int xsize, const int ysize, const char *filename, const bool extension);
BMPIMAGE bmp_file_read(const char *filename, const bool extension);
int bmp_write(const unsigned char *image, const int xsize, const int ysize, const char *filename);
unsigned char *array_to_raw_image(const RGB* InputData, const int xsize, const int ysize);
unsigned char bmp_filling_byte_calc(const unsigned int xsize);
unsigned char *bubble_sort_uchar( const unsigned char *data_input,
 const unsigned long long int data_input_count,
 const bool mode);
int main(int argc, char** argv)
{
 printf("BMP image file name:(ex:test): ");
 char *FilenameString;
 FilenameString = (char*)malloc( MAX_PATH * sizeof(char) );
 scanf("%s",FilenameString);
 BMPIMAGE BMPImage1;
 BMPImage1 = bmp_file_read(FilenameString,false);
 free(FilenameString);
 printf("%s\n",BMPImage1.FILENAME);
 
 if(BMPImage1.IMAGE_DATA == NULL)
 { 
 printf("Image contents error!");
 return -1;
 } 
 
 RGBIMAGE RGBImage1;
 RGBImage1.XSIZE = BMPImage1.XSIZE;
 RGBImage1.YSIZE = BMPImage1.YSIZE;
 RGBImage1.IMAGE_DATA = (RGB*)malloc(RGBImage1.XSIZE * RGBImage1.YSIZE * sizeof(RGB));
 if (RGBImage1.IMAGE_DATA == NULL)
 {
 printf("Memory allocation error!");
 return -1;
 }
 RGBImage1.IMAGE_DATA = raw_image_to_array(BMPImage1.IMAGE_DATA, BMPImage1.XSIZE, BMPImage1.YSIZE);
 
 bmp_write(array_to_raw_image(MedianFilter33(RGBImage1.IMAGE_DATA,RGBImage1.XSIZE, RGBImage1.YSIZE), RGBImage1.XSIZE, RGBImage1.YSIZE), BMPImage1.XSIZE, BMPImage1.YSIZE, "MedianFilterOutput");
 
 return 0;
}
RGB *MedianFilter33(const RGB *image,const int xsize,const int ysize)
{
 RGB *output;
 output = (RGB*)malloc(xsize * ysize * sizeof(RGB));
 if (output == NULL)
 { 
 printf("Memory allocation error!");
 return NULL;
 }
 for(long long int i = 0; i <(xsize * ysize); i++)
 {
 if( (i < xsize) || ( (i % xsize) == 0) || ( ((i + 1) % xsize) == 0) || (i >= (xsize*(ysize-1))))
 {
 output[i].R = image[i].R;
 output[i].G = image[i].G;
 output[i].B = image[i].B;
 } 
 else
 {
 unsigned char *sort_array;
 sort_array = (unsigned char*)malloc(9 * sizeof(unsigned char));
 // R channel sorting
 sort_array[0] = image[i-xsize-1].R;
 sort_array[1] = image[i-xsize].R;
 sort_array[2] = image[i-xsize+1].R;
 sort_array[3] = image[i-1].R;
 sort_array[4] = image[i].R;
 sort_array[5] = image[i+1].R;
 sort_array[6] = image[i+xsize-1].R;
 sort_array[7] = image[i+xsize].R;
 sort_array[8] = image[i+xsize+1].R;
 sort_array = bubble_sort_uchar(sort_array,9,0);
 output[i].R = sort_array[4];
 // G channel sorting
 sort_array[0] = image[i-xsize-1].G;
 sort_array[1] = image[i-xsize].G; 
 sort_array[2] = image[i-xsize+1].G;
 sort_array[3] = image[i-1].G; 
 sort_array[4] = image[i].G; 
 sort_array[5] = image[i+1].G; 
 sort_array[6] = image[i+xsize-1].G;
 sort_array[7] = image[i+xsize].G; 
 sort_array[8] = image[i+xsize+1].G;
 bubble_sort_uchar(sort_array,9,0);
 output[i].G = sort_array[4];
 // B channel sorting
 sort_array[0] = image[i-xsize-1].B;
 sort_array[1] = image[i-xsize].B; 
 sort_array[2] = image[i-xsize+1].B;
 sort_array[3] = image[i-1].B; 
 sort_array[4] = image[i].B; 
 sort_array[5] = image[i+1].B; 
 sort_array[6] = image[i+xsize-1].B;
 sort_array[7] = image[i+xsize].B; 
 sort_array[8] = image[i+xsize+1].B;
 bubble_sort_uchar(sort_array,9,0);
 output[i].B = sort_array[4];
 }
 }
 return output;
}
RGB *raw_image_to_array(const unsigned char *image, const int xsize, const int ysize)
{
 RGB *output;
 output = (RGB*)malloc(xsize * ysize * sizeof(RGB));
 if(output == NULL)
 { 
 printf("Memory allocation error!");
 return NULL;
 } 
 unsigned char FillingByte;
 FillingByte = bmp_filling_byte_calc(xsize);
 for(int y = 0;y<ysize;y++)
 {
 for(int x = 0;x<xsize;x++)
 {
 output[y*xsize + x].R =
 image[3*(y * xsize + x) + y * FillingByte + 2];
 output[y*xsize + x].G =
 image[3*(y * xsize + x) + y * FillingByte + 1];
 output[y*xsize + x].B =
 image[3*(y * xsize + x) + y * FillingByte + 0];
 }
 }
 return output;
}
//----bmp_read_x_size function----
unsigned long bmp_read_x_size(const char *filename, const bool extension)
{
 char fname_bmp[MAX_PATH];
 if(extension == false)
 { 
 sprintf(fname_bmp, "%s.bmp", filename);
 } 
 else
 { 
 strcpy(fname_bmp,filename);
 } 
 FILE *fp;
 fp = fopen(fname_bmp, "rb");
 if (fp == NULL) 
 { 
 printf("Fail to read file!\n");
 return -1;
 } 
 unsigned char header[54];
 fread(header, sizeof(unsigned char), 54, fp);
 unsigned long output;
 output = header[18] + (header[19] << 8) + ( header[20] << 16) + ( header[21] << 24);
 fclose(fp);
 return output;
}
//---- bmp_read_y_size function ----
unsigned long bmp_read_y_size(const char *filename, const bool extension)
{
 char fname_bmp[MAX_PATH];
 if(extension == false)
 { 
 sprintf(fname_bmp, "%s.bmp", filename);
 } 
 else
 { 
 strcpy(fname_bmp,filename);
 } 
 FILE *fp;
 fp = fopen(fname_bmp, "rb");
 if (fp == NULL)
 {
 printf("Fail to read file!\n");
 return -1;
 } 
 unsigned char header[54];
 fread(header, sizeof(unsigned char), 54, fp);
 unsigned long output; 
 output= header[22] + (header[23] << 8) + ( header[24] << 16) + ( header[25] << 24);
 fclose(fp);
 return output;
}
//---- bmp_file_read function ---- 
char bmp_read(unsigned char *image, const int xsize, const int ysize, const char *filename, const bool extension)
{
 char fname_bmp[MAX_PATH];
 if(extension == false)
 { 
 sprintf(fname_bmp, "%s.bmp", filename);
 } 
 else
 { 
 strcpy(fname_bmp,filename);
 } 
 unsigned char filling_bytes;
 filling_bytes = bmp_filling_byte_calc(xsize);
 FILE *fp;
 fp = fopen(fname_bmp, "rb");
 if (fp==NULL)
 { 
 printf("Fail to read file!\n");
 return -1;
 } 
 unsigned char header[54];
 fread(header, sizeof(unsigned char), 54, fp);
 fread(image, sizeof(unsigned char), (size_t)(long)(xsize * 3 + filling_bytes)*ysize, fp);
 fclose(fp); 
 return 0;
}
BMPIMAGE bmp_file_read(const char *filename, const bool extension)
{
 BMPIMAGE output;
 stpcpy(output.FILENAME, "");
 output.XSIZE = 0;
 output.YSIZE = 0;
 output.IMAGE_DATA = NULL;
 if(filename == NULL)
 { 
 printf("Path is null\n");
 return output;
 }
 char fname_bmp[MAX_PATH];
 if(extension == false)
 {
 sprintf(fname_bmp, "%s.bmp", filename);
 }
 else
 { 
 strcpy(fname_bmp,filename);
 } 
 FILE *fp;
 fp = fopen(fname_bmp, "rb");
 if (fp == NULL)
 { 
 printf("Fail to read file!\n");
 return output;
 } 
 stpcpy(output.FILENAME, fname_bmp);
 output.XSIZE = (unsigned int)bmp_read_x_size(output.FILENAME,true);
 output.YSIZE = (unsigned int)bmp_read_y_size(output.FILENAME,true);
 if( (output.XSIZE == -1) || (output.YSIZE == -1) )
 { 
 printf("Fail to fetch information of image!");
 return output;
 } 
 else
 { 
 printf("Width of the input image: %d\n",output.XSIZE);
 printf("Height of the input image: %d\n",output.YSIZE);
 printf("Size of the input image(Byte): %d\n",(size_t)output.XSIZE * output.YSIZE * 3);
 output.FILLINGBYTE = bmp_filling_byte_calc(output.XSIZE);
 output.IMAGE_DATA = (unsigned char*)malloc((output.XSIZE * 3 + output.FILLINGBYTE) * output.YSIZE * sizeof(unsigned char));
 if (output.IMAGE_DATA == NULL)
 { 
 printf("Memory allocation error!");
 return output;
 } 
 else
 {
 for(int i = 0; i < ((output.XSIZE * 3 + output.FILLINGBYTE) * output.YSIZE);i++)
 {
 output.IMAGE_DATA[i] = 255;
 }
 bmp_read(output.IMAGE_DATA, output.XSIZE, output.YSIZE, output.FILENAME, true);
 }
 } 
 return output;
}
//----bmp_write function---- 
int bmp_write(const unsigned char *image, const int xsize, const int ysize, const char *filename) 
{
 unsigned char FillingByte;
 FillingByte = bmp_filling_byte_calc(xsize);
 unsigned char header[54] =
 {
 0x42, 0x4d, 0, 0, 0, 0, 0, 0, 0, 0,
 54, 0, 0, 0, 40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 24, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0 
 }; 
 unsigned long file_size = (long)xsize * (long)ysize * 3 + 54;
 unsigned long width, height;
 char fname_bmp[MAX_PATH];
 header[2] = (unsigned char)(file_size &0x000000ff);
 header[3] = (file_size >> 8) & 0x000000ff; 
 header[4] = (file_size >> 16) & 0x000000ff; 
 header[5] = (file_size >> 24) & 0x000000ff; 
 
 width = xsize;
 header[18] = width & 0x000000ff;
 header[19] = (width >> 8) &0x000000ff;
 header[20] = (width >> 16) &0x000000ff;
 header[21] = (width >> 24) &0x000000ff;
 
 height = ysize;
 header[22] = height &0x000000ff;
 header[23] = (height >> 8) &0x000000ff;
 header[24] = (height >> 16) &0x000000ff;
 header[25] = (height >> 24) &0x000000ff;
 sprintf(fname_bmp, "%s.bmp", filename);
 FILE *fp; 
 if (!(fp = fopen(fname_bmp, "wb")))
 { 
 return -1;
 } 
 fwrite(header, sizeof(unsigned char), 54, fp);
 fwrite(image, sizeof(unsigned char), (size_t)(long)(xsize * 3 + FillingByte)*ysize, fp);
 fclose(fp);
 return 0;
}
unsigned char *array_to_raw_image(const RGB* InputData, const int xsize, const int ysize)
{
 unsigned char FillingByte;
 FillingByte = bmp_filling_byte_calc(xsize);
 unsigned char *output;
 output = (unsigned char*)malloc((xsize * 3 + FillingByte) * ysize * sizeof(unsigned char));
 if(output == NULL)
 { 
 printf("Memory allocation error!");
 return NULL;
 }
 for(int y = 0;y < ysize;y++)
 {
 for(int x = 0;x < (xsize * 3 + FillingByte);x++)
 {
 output[y * (xsize * 3 + FillingByte) + x] = 0;
 }
 }
 for(int y = 0;y<ysize;y++)
 {
 for(int x = 0;x<xsize;x++)
 {
 output[3*(y * xsize + x) + y * FillingByte + 2]
 = InputData[y*xsize + x].R;
 output[3*(y * xsize + x) + y * FillingByte + 1]
 = InputData[y*xsize + x].G;
 output[3*(y * xsize + x) + y * FillingByte + 0]
 = InputData[y*xsize + x].B;
 }
 }
 return output;
}
unsigned char bmp_filling_byte_calc(const unsigned int xsize)
{
 unsigned char filling_bytes;
 filling_bytes = ( xsize % 4);
 return filling_bytes;
}
unsigned char *bubble_sort_uchar( const unsigned char *data_input,
 const unsigned long long int data_input_count,
 const bool mode)
{
 unsigned char *output;
 output = (unsigned char*)malloc( data_input_count * sizeof(unsigned char) );
 for(unsigned long long int y=0;y < data_input_count;y++)
 {
 output[y] = data_input[y];
 }
 for(unsigned long long int x = 1; x < data_input_count; x++)
 {
 for(unsigned long long int y = 0; y < data_input_count - x; y++)
 {
 if( mode == 0 )
 {
 if(output[y] > output[y + 1])
 {
 unsigned char temp;
 temp = output[y];
 output[y] = output[y + 1];
 output[y + 1] = temp;
 }
 }
 else if( mode == 1 )
 {
 if(output[y] < output[y + 1])
 {
 unsigned char temp;
 temp = output[y];
 output[y] = output[y + 1];
 output[y + 1] = temp;
 }
 }
 }
 }
 return output;
}

If there is any possible improvement, please let me know.

Answer 1

• Thou shalt not cast malloc. It is redundant (if you #include <stdlib.h>), and may lead to hard-to-find bugs (if you don't).

• sort_array is allocated at each iteration, yet never freed.

  That said, I don't see why it needs malloc at all. Declare it statically

   unsigned char sort_array[9];
  

• DRY. The code for R, G, and B channels, thrice repeated, cries to become a function. Consider defining RGB as

   typedef struct {
   unsigned char channel[3];
   } RGB;
  

  and writing the else clause as

   for (int color = 0; color < 3; i++) {
   output[i].channel[color] = median_filter_channel(image, i, xsize, color);
   }
  

Answer 2

You’ve got some excellent answers commenting on the code itself. I am here to comment on the algorithm.

It is really hard to implement a color median filter. The median is defined for a set of scalar values (and thus it is straight-forward to define a median filter that works on a gray-scale image). But the median of a set of 3-vectors (such as RGB pixel values) is not well defined. You cannot meaningfully sort vectors.

You have implemented a marginal median—you compute the median for each of the components of the vector separately. The resulting value is typically not one of the input vectors. This means that your median filter is creating new colors that do not appear in the input image. For example, the marginal median of a equal combination of pure green, red and blue pixels is black! And the marginal median of an equal combination of pure magenta, cyan and yellow pixels is white!

There exists a vector median. It selects the input vector that has the minimal distance to all other inputs (using either the sum of distances or sum of square distances). This is a lot more expensive to compute than the marginal median, and there is no guarantee that the vector median is actually "in the middle" of the set. But at least you don’t introduce new colors.

You can define a consistent ordering of RGB colors, for example using dictionary sort, or sorting on brightness only and ignoring color, or some other system. No matter how you define the ordering, there is no guarantee that the result of your median computation is meaningful.

Finally, you can convert from RGB to another color space, and there use a dictionary sort. The same issues as above apply.

So, I have no good solution for you. It depends very much on the application which solution is most suitable. For "salt and pepper noise", the marginal median and the sorting on brightness alone are reasonable solutions.

Answer 3

int vs. size_t math

...,const int xsize,const int ysize) ...
output = (RGB*)malloc(xsize * ysize * sizeof(RGB));
// int * int 

size_t math typically exceeds int (and maybe unsigned) math and may handle int overflow of xsize * ysize.

Consider dropping the unneeded cast, re-order and size to the referenced data, rather than type.

output = malloc(sizeof *output * xsize * ysize); // Uses size_t multiplication
// RGBImage1.IMAGE_DATA = (RGB*)malloc(RGBImage1.XSIZE * RGBImage1.YSIZE * sizeof(RGB));
RGBImage1.IMAGE_DATA = malloc(sizeof *RGBImage1.IMAGE_DATA * RGBImage1.XSIZE * RGBImage1.YSIZE);
// size_t * int(converted to size_t) 

const parameters

This is not about the const in const RGB *.

Curious code uses const int xsize, but not const RGB * const image as neither xsize nor RGB changes.

If one is using const to help prevent changes to unchanging parameters, be consistent.

// RGB *MedianFilter33(const RGB *image,const int xsize,const int ysize)
RGB *MedianFilter33(const RGB * const image, const int xsize, const int ysize)

IMO: these const tend to be more error prone/obfuscation than worth it as they are noise in a .h function declaration.

// Suggested:
RGB *MedianFilter33(const RGB *image, int xsize, int ysize)

int vs. long long

Code curiously uses long long i below versus int i.

... const int xsize,const int ysize ...
for(long long int i = 0; i <(xsize * ysize); i++) // Why long long int?

Should xsize * ysize exceed INT_MAX, result is undefined behavior and so nothing is gained by making i an long long. Code could compute the product using long long math`:

// A little better
for(long long int i = 0; i <(1LL * xsize * ysize); i++)

For array sizing consider size_t and a C2x principle: put dimensions first.

// RGB *MedianFilter33(const RGB *image,const int xsize,const int ysize)
RGB *MedianFilter33(size_t xsize, size_t ysize, const RGB *image)

Likewise problem with

unsigned char header[54];
...
unsigned long output;
output = header[18] + (header[19] << 8) + ( header[20] << 16) + ( header[21] << 24);

header[18] + (header[19] << 8) + ( header[20] << 16) + ( header[21] << 24) is computed using int math.

Alternative:

unsigned long output = header[18] + 
 ((unsigned long)header[19] << 8) + 
 ((unsigned long)header[20] << 16) + 
 ((unsigned long)header[21] << 24);

Here also, I'd consider size_t rather than unsigned long.

• Toby Speight: A common, and useful, practice is to use const where possible and useful in the definition, but only the type (without top-level const) in other declarations (e.g. in a header file).
• chux: @TobySpeight I respectively disagree that "use const where possible". IMO not worthy the noise/clarity ratio. Perhaps there is a better forum than comments here to hash that out?
• Toby Speight: "where possible" is too strong. "Where you would declare a similar local variable const" is probably more apt. Main point was don't write it in non-defining declarations. (BTW, ITYM "respectfully"?)
• chux: @JimmyHu "error: assigning to 'RGB *' from incompatible type 'void *'" --> You are likely compiling in another language like C++. Try compiling in C instead.
• JimmyHu: @chux-ReinstateMonica Thank you for letting me know the difference. It can be compiled successfully in clang, not clang++.

Answer 4

buble_sort_uchar allocates memory, and returns a pointer to it, but the pointer is never freed. And in two cases (G and B channels), the returned pointer isn't saved so the sort effectively does nothing except leak memory.

Similarly, the memory allocated in MedianFilter33 for sort_array is never freed.

• Toby Speight: And neither of those actually require allocation - local variables should be fine in both cases.