Box Filters

I’ve been needing to get a tech blog for a while, so here it is finally. For my first entry I’m going to explain box filters (convolution matrices). It’s a pretty simple topic, but it has come up lately a few times, so I’m going to give a brief explanation and a possible implementation in C.

Box filters as mathematical objects take the form of square matrices.

Let (where k is and odd integer greater than 0) be a vector space of matrices over representing the set of all square convolution matrices (box filters) with kernel action size k and dimension n. Normally, box filters are 2-dimensional, since their (current) primary use is image processing. Blurs, edge-detection, etc can be implemented using these filters. To keep this short, I’m going to cover a simple box filter that operates on a 1-dimensional data set.

Let be a 1-dimensional box filter with kernel action size 3. A box filter of this type takes the form . Each element resulting from the box filter will be combination of the old element in the same position and its adjacent elements:

Say I’m given a 1-dimensional scalar array:

Which, when graphed, looks like this:

If I wanted to smooth this uniformly, I could use the box filter: In the cases where the kernel action area overlaps the edge, there are a few ways of applying the filter. One is to extend the edge value past the edge, another is to wrap the action area around to the other edge. Here are both results when the smoothing filter is applied:

Extended:

Wrapped:

For a less computational, more mathematical definition (for example, how these relate to general signal processing), google “convolution matrix”.

References:

http://docs.gimp.org/en/plug-in-convmatrix.html

#include <stdio.h> /* fprintf, printf */

enum Mode
{
  WRAP = 0,
  EXTEND = 1
};

/* filter assumed to be of kernel action area 3 */
void ApplyFilter(double *target, const double *source,
                 const double *filter, unsigned len, int mode)
{
  unsigned i;
  for(i = 1; i < (len - 1); i++)
  {
    target[i] = (filter[0] * source[i-1]) +
                (filter[1] * source[i])   +
                (filter[2] * source[i+1]);
  }

  switch(mode)
  {
    case WRAP:
      target[0]       = (filter[0] * source[len - 1]) +
                        (filter[1] * source[0])       +
                        (filter[2] * source[1]);
      target[len - 1] = (filter[0] * source[len - 2]) +
                        (filter[1] * source[len - 1]) +
                        (filter[2] * source[0]);
      break;

    case EXTEND:
      target[0]       = (filter[0] * source[0])       +
                        (filter[1] * source[0])       +
                        (filter[2] * source[1]);
      target[len - 1] = (filter[0] * source[len - 2]) +
                        (filter[1] * source[len - 1]) +
                        (filter[2] * source[len - 1]);
      break;

    default:
      fprintf(stderr, "Invalid mode specified!");
  }
}

void PrintSvgPath(const double *arr, unsigned len)
{
  unsigned i;

  printf("M %f, %f  ", 10.0, 100.0);

  for(i = 0; i < len; i++)
  {
    printf("L %f, %f  ", 10.0 + (i * 10.0), 10.0*(10.0 - arr[i]));
    printf("L %f, %f  ", 10.0 + ((i + 1) * 10.0), 10.0*(10.0 - arr[i]));
  }

  printf("L %f, %f", 10.0 + (len * 10.0), 100.0);
}

void PrintDoubleArr(const double *arr, unsigned len)
{
  unsigned i;

  printf("{ ");

  for(i = 0; i < len; i++)
  {
    printf("%.2f ", arr[i]);
  }

  printf("}\n");
}

int main()
{
  double source[]   = {3, 2, 0, 4, 1, 5, 2, 3, 1, 4};
  double filter[]   = {(1.0/3.0), (1.0/3.0), (1.0/3.0)};
  double wrap[10]   = {0};
  double extend[10] = {0};

  ApplyFilter(wrap,   source, filter, 10, WRAP);
  ApplyFilter(extend, source, filter, 10, EXTEND);

  PrintDoubleArr(source, 10);
  PrintDoubleArr(wrap, 10);
  PrintDoubleArr(extend, 10);

  puts("\n");
  PrintSvgPath(source, 10);
  puts("\n");
  PrintSvgPath(wrap, 10);
  puts("\n");
  PrintSvgPath(extend, 10);

  return 0;
}

Tags: box filter, graphics