created: 02/02/2008


Puzzle 41 - Puzzle 50

Part I — Image Puzzles

These puzzles involve reading in an image, creating a smoothed image, then writing out the smoothed image to an image file.


Puzzle I41 — Image Smoothing

[M-25]Implement an image smoother as described in sections 22 and 23 of Image Smoothing. Here is what the command line looks like:

C:\PuzzleFolder>smooth inputImage.pgm smoothImage.pgm

The input image is not altered. The output image is a version of the input image that has been smoothed using a 3x3 neighborhood. For pixels along the edges of the images, copy the input image pixel unchanged to the output image. Here is a framework:

#include <stdlib.h>
#include <stdio.h>
#include "basicImage.c"

void smoothImage( image img, image smooth )
{
  int r, c, sum;
  unsigned char value ;

  /* Copy edge pixels from input image to output image */

  /* Fill in the center with neighborhood averages */
  for ( r=1; r<img.nrows-1; r++ )
    for ( c=1; c<img.ncols-1; c++ )
      . . .

}

int main ( int argc, char* argv[] )
{
  image img, smimg;
  
  if ( argc != 3 )
  {
    printf( "smooth oldImage smoothImage\n" );
    system( "pause" );
    exit( EXIT_FAILURE );
  }
  
  /* read in the image */
  readPGMimage( &img, argv[1] );

  /* create a blank image */
  newImage( &smimg, img.nrows, img.ncols );

  /* fill in values for the new image */
  smoothImage( img, smimg );
  
  /* write the image to disk and free memory */
  writePGMimage( smimg, argv[2] );
  freeImage( &img );
  freeImage( &smimg );
  
}

As always, you can develop this as a Dev-C++ project using a separate source file for each function used in the project. Otherwise, you can develop this as one big source file by including basicImage.c.

The answer will take about 25 moderatly easy lines of code in addition to those in the framework.


Puzzle I42 — Test image

[E-6]Write a program that creates an image where every N'th column is set to a particular value and the rest of the image is zero:

C:\PuzzleFolder>everyNth testImage.pgm rows cols N value

Images created with this program are useful for testing. Here is an image where every third row is set to 80x3 = 240, and the output of smoothing with a 3x3 mask:

Original Image
Smoothed Image

In general, each 3x3 neighborhood overlaps just one column with pixels of value 240. So the output value for each neighborhood is 80, and the smoothed image consists of pixels with a uniform value of 80 (except for the edges). Here is a framework:

#include <stdlib.h>
#include <stdio.h>
#include "basicImage.c"

int main ( int argc, char* argv[] )
{
  image img;
  int r, nrows, c, ncols, N, value ;
  
  if ( argc != 6 )
  {
    printf( "everyNth image rows cols N value\n" );
    system( "pause" );
    exit( EXIT_FAILURE );
  }

  nrows = atoi( argv[2] );
  ncols = atoi( argv[3] );
  N     = atoi( argv[4] );
  value = atoi( argv[5] );

  /* create a blank image */
  newImage( &img, nrows, ncols );

  /* fill in values for the new image */
  . . .

  /* write the image to disk and free memory */
  writePGMimage( img, argv[1] );
  freeImage( &img );
  
}


Puzzle I43 — Image Smoothing with Edges

Implement an image smoother as described in Image Smoothing, but now, unlike Puzzle I41, edge pixels in the smoothed image are averages. Here is what the command line looks like:

C:\PuzzleFolder>smoothB inputImage.pgm smoothImage.pgm

The input image is not altered. The output image is a version of the input image that has been smoothed using a 3x3 neighborhood.

Give edge pixels the average value of that portion of a 3x3 neighborhood that is included in the image. For example, the smoothed value for the location (0,0) is the average of the four pixels (0,0), (0,1), (1,0), and (1,1).

Use your answer to Puzzle 41 for this. Add some extra logic to the smooth function that deals with the edge pixels and corner pixels. There are two ways that this can be done.

[M-25]One way is to keep the code from Puzzle 41 that computes the value for each non-edge pixel, and to add lots of extra code to deal with the special cases (corners and edges). This will take about 25 lines of code in addition to the previous answer.

[H-12]Another way is to write a loop that visits every pixel (corners and edges included). The loop body includes logic that adds up only those pixels in a valid neighborhood. This will involve a rewrite of the previous soothing function, taking about 12 fairly trickly lines of code.


Puzzle I44 — Smoothing with a 5x5 Neighborhood

[E-2]Write an image smoother that uses a 5x5 neighborhood. In general, each pixel of the smoothed image will be the average of a 5x5 neighborhood centered on that pixel.

C:\PuzzleFolder>smooth5 inputImage.pgm smoothImage.pgm

Now the two rows and two columns next to the edges will have incomplete neighborhoods centered on them.

There are too many special cases to handle each one individually. Start with the second version of the answer to Puzzle I43 where every pixel is visited in a loop, and the loop body determines which pixles to include in the neighborhood. Edit the code so that it implements a 5x5 neighborhood. This involves a fairly easy modification to two lines of code from the previous "hard" answer.


Puzzle I45 — Smoothing with a RxC Neighborhood

[E-8] Modify the previous program so that it implements an R rows by C columns neighborhood, where N and M are specified on the command line:

C:\PuzzleFolder>smoothNxM inputImage.pgm smoothImage.pgm R C

Various neighborhood shapes have various effects on the image. For example, here is the Kernighan image smoothed with a 1 by 7 neighborhood. The image looks as if the camera vertically when the picture was taken.

Smoothing with a 1 by 7 neighborhood

This is an easy modification of the previous program. Note that it is OK to have neighborhoods with an even number of rows or columns.


Puzzle I46 — Brightest Pixel in a 3x3 Neighborhood

[E-14] Modify the answer to I41 so that it examines each complete 3x3 neighborhood and (in the output image) replaces the central pixel with the brightest pixel in the neighborhood. Keep the edge and corner pixels the same.

C:\PuzzleFolder>pickBrightest inputImage.pgm resultImage.pgm

This does not produce a very pleasing effect. However, if you create a series of images, where each image is the result of using the program on the previos image, you get some interesting effects. If you keep doing this, eventually the entire image will be one brightness level— the level of the brightest pixel in the original image.

Each Pixel Replaced with the Brightest Pixel in its 3x3 Neighborhood
Each Pixel Replaced with the
Brightest Pixel in its 3x3 Neighborhood

Test your program with the test image from Puzzle I42.


Puzzle I47 — Repeated Smoothing

[E-5] Modify the answer to I43 so that it inputs an image, and outputs an image that has been smoothed with a 3x3 neighborhood N times. Do this by using a loop in the main() function. This has a similar effect to smoothing with a large neighborhood. The larger N is, the larger the effective neighborhood is. However, the effect is not identical to smoothing by computing the average of a large neighborhood. The value of a pixel in the output image is a weighted average of the pixels in its neighborhood, where closer pixels a weighted more heavily than distant pixels.

C:\PuzzleFolder>smoothRepeat inputImage.pgm resultImage.pgm N

Here is the original image, the image smoothed by averaging 7x7 neighborhoods, and the image smoothed with three times using 3x3 neighborhoods.

Original Image
7x7 Smoothing
Three Applications of
3x3 Smoothing
One Application of
3x3 Smoothing


Puzzle I48 — Closest to Average

[M-14] Modify the answer to I41 so that it examines each complete 3x3 neighborhood and (in the output image) replaces the central pixel with the pixel in the neighborhood that is closest to the average of all the pixels in the neighborhood. Keep the edge and corner pixels of the image the same.

C:\PuzzleFolder>pickAverage inputImage.pgm resultImage.pgm

This function removes "salt-and-pepper" noise, were isolated pixels in an image have a value much higher or lower than is correct.


Puzzle I49 — Test Image

[M-14]Add salt-and-pepper noise to an image by setting P percent of its pixels to black or white. Pick black or white with a simulated coin toss.

C:\PuzzleFolder>saltAndPepper oldImage noisyImage percent

Look in Puzzle Section B for information on random numbers, if you need to. Here is an image with 5% noise added:

Salt and Pepper Noise

Smooth the noisy image with any of the previous image smoothers and observe the effect.


Puzzle I50 — Median Filter

[H-20] Modify the answer to I47 so that it examines each complete 3x3 neighborhood and (in the output image) replaces the central pixel with the pixel in the neighborhood that is the median value of the pixels in the neighborhood. Keep the edge and corner pixels the same.

C:\PuzzleFolder>medianFilter inputImage.pgm resultImage.pgm

The median value of a list of integers is the value that is greater than half the other values and less than half the remaining values. For example, in the list

20, 24, 25, 25, 38, 41, 54, 67, 90

the median value is 38 because four values are below it and four values are above it. It does not matter that some values are repeated. Note that the median is always one of the values in the list. Depending on the numbers, it might be far from the average value. If there are nine values in a sorted list, the median is in the center of the list.

Of course, the values in the neighborhood will not usually appear in sorted order, so your function must somehow sort these values, either by using a sort function, or by doing the sort itself. Notice that a full sort is not needed; all you need to do is find the value that should be the fifth one on the list. However, if you want, use selection sort from Puzzle C49.

As with the closest to average filter, a median filter removes"salt-and-pepper" noise.

Salt and Pepper Noise Removed

 


― Return to the main puzzle page