created 06/25/2005; revised 01/21/2007, 12/16/2007, 11/17/2010, 08/03/2012, 11/15/15


Image Puzzles — Images in Memory

This section discusses programs that keep an entire image in memory as it is worked on.


14. Images in Memory

Our programs so far have created image files by writing the pixels to disk one pixel at a time in raster order. Although this works well for creation of some simple images, in general it is more convenient to have all the pixels in memory at one time and to process them in whatever order arises naturally. To do this, it might seem sensible to use a two dimensional array of pixel data, like this:

unsigned char image[512][512];

However, this turns out to be awkward. It is more convenient to use a struct for an image:


typedef struct
{
  int nrows;               /* number of rows */
  int ncols;               /* number of columns */
  unsigned char *pixels;   /* pixel data stored in a 1D array */
} image;

The struct contains a field, pixels, which points to a one dimensional array of pixel data. This pixel data is allocated dynamically (more on this later). For our image, pixels are in the range 0..255, so one unsigned byte will hold the data for one pixel. An image struct with its pixel data looks like this:

image struct

Here the image has 4 rows and 6 columns. The struct member pixels points to a block of 24 contiguous bytes in memory that store the pixel data in raster order. The byte marked x is for the pixel at row 2 column 4. (Row and column indexes start at zero.)

We want our pixels to represent gray levels of zero to 255. With some compilers, the data type char represents values -128 to +127. This is allowed by the ANSI standard. The qualifier unsigned ensures that pixels have the desired range.

Image processing functions will be called with a struct parameter:

  
void processImage ( image img )
{
  int r, c; 
  
  for ( r=0; r < img.nrows; r++ )
    for ( c=0; c < img.ncols; c++ )
    . . . .
}	

15. Constructing an Image

We want the image struct to work for images of any size. This means that nrows*ncols number of bytes must be allocated for pixels. It is convenient to package this in a function:


unsigned char *newImage( image *img, int nrows, int ncols )
{
  img->nrows = nrows;
  img->ncols = ncols;
  img->pixels = (unsigned char *)malloc( nrows * ncols );
  return img->pixels;
}

newImage() takes a pointer to an image struct (it needs a pointer so it can modify the members of the struct), fills in nrows and ncols, then dynamically allocates memory for the pixel data. The address of the first of these bytes is placed in the field pixels of the struct.

Memory allocation might fail. If it does, malloc() returns NULL. The function returns the same value malloc() returns so the caller can check for errors. Here is a complete (and useless) program that constructs a 300 rows by 400 columns image struct:


int main ( int argc, char* argv[] )
{
  image x ;

  if ( newImage( &x, 300, 400 ) == NULL )
  {
    printf(">>error<< can't allocate memory\n");
    return;
  }
  system( "pause" );
  free( x.pixels );
}

The program constructs the image, pauses, then frees memory and exits.


16. Freeing an Image

Dynamically allocated memory should be returned to the system by calling free(). Here is a convenient function that does that:


void freeImage( image *img )
{
  img->nrows = 0;
  img->ncols = 0;
  free( img->pixels );
  img->pixels = NULL;
}

Although it is possible for free()to fail, it happens so rarely (and there is nothing we can do when it does fail) that this function ignores that possibility.


17. Accessing Pixels

Conceptually, an image is a 2D grid of pixels. For example, here is an image of 4 rows and 6 columns: Image of 4 rows and 6 columns

The pixel marked y is at row 0 column 2. The pixel marked x is at row 2 column 4. The pixel marked z is at row 3 column 2. Here is how this image is implemented:

Image Implementation

The pixel y (conceptually at row 0 column 2) is at location pixels[2]. Recall that array subscripting and address calculation are equivalent: pixels[2] is the same as *(pixels+2). Review C arrays and pointer arithmetic if this is unclear.

The pixel x is in row number 2, which means that all the pixels of row 0 and row 1 precede it. It is at location 4 in its row. So it is at location pixels[ncols*2 + 4] which is pixels[16]. (Remember that rows and columns are numbered starting at 0).

Pixel z (conceptually at row 3 column 2) is at location pixels[ncols*3 + 2] which is pixels[20].

Rule: Say that an image has ncols number of columns and that bytes are numbered starting at zero. Then a pixel that is conceptually at row r column c will be at byte number:

ncols*r + c

Notice that the number of rows is not used this calculation.

Here is another image. Pixel x is at row 4 column 8. At what offset into the byte data does it lie?

Pixel x in an image

Now ncols is 12, so the offset is ncols*r + c = 12*4 + 8 = 56.


18. Example Program

Here is a program (again, useless) that creates an image of 4 rows and 6 columns and sets the pixel at row 0 column 2 to value y, the pixel at row 2 column 4 to value x, and the pixel at row 3 column 2 to value z.



int main ( int argc, char* argv[] )
{
  image img ;
  const unsigned char x = 44, y = 77, z = 99;
  int r, c;

  if ( newImage( &img, 4, 6 ) == NULL )
  {
    printf(">>error<< can't allocate memory\n");
    return;
  }

  img.pixels[ img.ncols*0 + 2 ] = y; /* row 0 column 2 */
  img.pixels[ img.ncols*2 + 4 ] = x; /* row 2 column 4 */
  img.pixels[ img.ncols*3 + 2 ] = z; /* row 3 column 2 */

  system( "pause" );

  freeImage( &img );
}

19. setPixel() and getPixel()

It is convenient to encapsulate the calculations that access the pixel data of an image. Here are two functions that do that:


void setPixel( image img, int row, int col, unsigned char val )
{
  img.pixels[ img.ncols*row + col ] = val;
}


unsigned char getPixel( image img, int row, int col )
{
  return img.pixels[ img.ncols*row + col ] ;
}

setPixel() takes an image structure and sets a pixel at the specified row and column to a value. Notice that the first parameter is not the address of the structure since no field of the structure is changed. However, the structure contains a pointer to the pixel data, so changes can be made to the pixel data.

getPixel() takes an image structure and looks up the pixel value at the specified row and column and then returns that value. Note that the qualifier unsigned is used in these functions to ensure the correct range of pixel values.

(You might be thinking that the image struct and these two functions are an awful lot like an object-oriented program's image class and its "setter" and "getter" methods. This is correct thinking. As is often said, you can do object oriented programming in any language, and this is an example of just that.)

Here is an example program that shows how these methods work:


int main ( int argc, char* argv[] )
{
  image img ;
   
  if ( newImage( &img, 4, 6 ) == NULL )
  {
    printf(">>error<< can't allocate memory\n");
    return;
  }

  /* Set some pixels in the image (the remaining pixels will have unknown values) */
  setPixel( img, 0, 2, 44 ); /* row 0, col 2, value 44 */
  setPixel( img, 2, 4, 77 ); /* row 2, col 4, value 77 */
  setPixel( img, 3, 2, 99 ); /* row 3, col 2, value 99 */

  /* Verify that the pixels have been set to the intended values */
  printf("row 0, col 2: %d\n", getPixel( img, 0, 2 ) );
  printf("row 2, col 4: %d\n", getPixel( img, 2, 4 ) );
  printf("row 3, col 2: %d\n", getPixel( img, 3, 2 ) );

  system( "pause" ); /* Delete this if desired */

  freeImage( &img );
}

20. Writing an Image to a Disk File

In main memory, gray level images are held in structures of type image. On disk, images are held in files that follow the PGM format. We need a function that takes an image in main memory and writes it to a disk file. The following function takes an image structure (already filled in with values) and a file name. It creates a disk file with the requested name and writes the data from the structure to the file using the PGM format. It then closes the file.


void writePGMimage( image img, char *filename )
{
  FILE *file;

  /* open the image file for writing binary */
  if ( (file = fopen( filename, "wb") ) == NULL )
  {
    printf("file %s could not be created\n", filename );
    exit( EXIT_FAILURE );
  }

  /* write out the PGM Header information */
  fprintf( file, "P5\n");
  fprintf( file, "# Created by writeImage\n");
  fprintf( file,  "%d %d %d\n", img.ncols, img.nrows, 255 );

  /* write the pixel data */
  fwrite(img.pixels, 1, img.nrows*img.ncols, file );

  /* close the file */
  fclose( file );
}

The statement

 fwrite(img.pixels, 1, img.nrows*img.ncols, file ) 

writes all the bytes in the buffer img.pixels to the open file indicated by file. The parameter 1 is the size in bytes of each item (in this case, one byte) and the parameter img.nrows*img.ncols is how many of those items to write. Look at binary I/O in your C book if this is unclear.


21. Reading an Image from a Disk File

We also need a function that reads an image in PGM format from a disk file into an image struct. The following function creates an image struct, opens an image file, reads in the image header and initializes the struct, and then reads in the pixel data. It then closes the file. The data in the image struct can now be manipulated by other parts of the program.

 
void readPGMimage( image *img, char *filename )
{
  FILE *file;
  char  buffer[1024];
  int   nrows, ncols, ngray ;
  
  /* open the image file for reading binary */
  if ( (file = fopen( filename, "rb") ) == NULL )
  {
    printf("readImage(): file %s could not be opened\n", filename );
    exit( EXIT_FAILURE );
  }

  /* read signature on first line */
  if ( fscanf( file, "%s", buffer ) != 1 )
  {
    printf("error in image header: no signature\n" );
    exit( EXIT_FAILURE );
  }

  if ( strncmp( buffer, "P5", 2 ) != 0 )
  {
    printf("readPGMimage(): file %s is not a PGM file\n", filename );
    printf("Signature: %s\n", buffer );
    exit( EXIT_FAILURE );
  }

  /* skip over comment lines */
  int moreComments = 1, ch;
  while ( moreComments )
  {
    /* skip over possible white space */
    while ( (ch=fgetc(file)) && isspace(ch) );
    if ( ch=='#' )
    {
      /* comments are required to end with line-feed, so fgets will work */
      fgets( buffer, 1024, file );
    }
    else
    {
      moreComments = 0;
      ungetc( ch, file );
    }
  }

  /* get ncols, nrows, ngray and eat the required single white space that follows */
  int count = fscanf( file, "%d %d %d", &ncols, &nrows, &ngray );
  if ( count != 3 )
  {
    printf("error in image header\n" );
    exit( EXIT_FAILURE );
  }
  fgetc(file);

  if ( ngray != 255 )
  {
    printf("readPGMimage(): file %s is %d, not 8 bits per pixel\n",
      filename, ngray );
    exit( EXIT_FAILURE );
  }

  /* construct an image structure of the appropriate size */
  if ( !newImage( img, nrows, ncols ) )
  {
    printf("readPGMimage(): newImage failed\n" );
    exit( EXIT_FAILURE );
  }

  /* read the pixel data */
  fread( img->pixels, 1, img->nrows*img->ncols, file );

  /* close the file */
  fclose( file );
}

Here (again) is the PGM image format:

ASCII characters: 'P' followed by '5' followed by one or more whitespace characters (often ending with a newline character).
Zero or more comment lines. Each line starts with a # and ends with a newline character.
Width of image in pixels. ASCII characters indicating a decimal value, followed by one or more whitespace characters (often ending with a newline character).
Height of image in pixels. ASCII characters indicating a decimal value, followed by one or more whitespace characters (often ending with a newline character).
Maximum value of a pixel. ASCII characters indicating a decimal value, followed by a single whitespace character, often a newline. For us the maximum value will always be 255.
The pixel data, one byte per pixel, using unsigned binary (not ASCII).

Here is a program that exercises both readPGMimage and writePGMimage. It opens an existing PGM image file, and then writes the data in that file to a new PGM image file. Of course, an ordinary byte-by-byte file copy program would do this will a lot less fuss, but this program shows how the two functions work.


int main ( int argc, char* argv[] )
{
  image img ;
  
  if ( argc != 3 )
  {
    printf("copyImage oldImage newImage\n");
    system( "pause" );
    exit( EXIT_FAILURE );
  }
  
  /* read in the old image */
  readPGMimage( &img, argv[1]);
  
  /* here you might do something to the pixels of the old image */

  /* write the image to a different disk file and free memory */
  writePGMimage( img, argv[2]);
  freeImage( &img );
  system( "pause" );
}

22. Include Files and Projects

The C puzzles of the next sections use these functions:

The answers to the puzzles are written as source files that #include a file basicImage.c which contains the above functions and the definition of the image struct. This is done so that the puzzles are independent of environment.

To get the file basicImage.c click here: Basic Functions

In Dev-C++ and other program development environments it is more convenient to create a project, which is a bundle of all the source files and other resources needed to create an application. If you wish to create a project, create a header file (a "dot h" file) that contains the image struct definition and prototypes for the above functions. Create a second file that contains the source code for the above functions. Add these two files to your project along with your source code.

The puzzles have you create several useful functions, such as

You can add these one by one to your project as you write them.


Go to Contents — Return to the main contents page