Image Processing

In this unit we introduce specific data structures in C for representing and processing images.

Introduction

As you likely know from experiences with MediaScheme in CSC 151, images commonly consist of a large number of dots or pixels, arranged in a grid pattern, called a raster. Such images are often called raster graphics.

With this organization of image data into dots, the storage of images reduces to two basic issues:

The first part of this reading examines these two matters. The reading then discusses several technical details and provides an example.

Pixels

While several image formats exist, perhaps the most common specification for each pixel involves a red, green, and blue component. Each color component is typically stored as one byte, a char in C. In this context, negative values are not meaningful, so each component is considered an unsigned char, taking values from 0 to 255. Further, the red, green, and blue (R/G/B) components naturally form a coherent quantity— a struct in the context of C. With this in mind, MyroC defines a pixel as follows:

/**
 * @brief Struct for a pixel
 */
typedef struct
{
  unsigned char R; // The value of the red component 
  unsigned char G; // The value of the green component 
  unsigned char B; // The value of the blue component 
} Pixel;

Within this framework, R/G/B values of 0 correspond to no light of that color component and R/G/B values of 255 correspond to maximal light. This leads to the following natural definitions:

Pixel blackPixel = {0, 0, 0};
Pixel whitePixel = {255, 255, 255);

Pictures

Perhaps the most conceptually-simple structure for a picture involves a two-dimensional array of R/G/B pixels. Each picture has a height and a width, and an overall picture is just a two-dimensional array with those dimensions. When working with a Scribbler 2 robot, the camera on the original Fluke board takes a picture that is 192 pixels high and 256 pixels wide, while a picture from the newer Fluke 2 is 266 pixels high and 427 pixels wide. Of course, other cameras or images may have different dimensions.

A pragmatic detail: You may recall from working with one- and two-dimensional arrays that the declaration of a two-dimensional array allocates space, but the array name just gives the base address, not the height and width dimensions. We cannot infer the dimensions of the array given only the variable name. For this reason, it is convenient to store the dimensions of an image together with the two-dimensional array. Thus, in much processing, the height, width, and pixel array are naturally part of a single package, so a picture is defined as a struct:

/**
 * @brief Struct for a picture object
 * @note the picture size is always 427 in width and 266 in height
 */
typedef struct 
{
  int height; /* The actual height of the image -- no more than 266*/
  int width;  /* The actual width of the image  -- no more than 427*/
  Pixel pix_array[266][427]; /* The array of pixels comprising the image */
} Picture;

Technical Details

Although the organization of images into dots or pixels may seem reasonably straightforward at a conceptual level, numerous technical details arise when processing pictures within a computer. Five such considerations are:

Image Sizes

The storage of images presents an interesting challenge in the context of MyroC and the C programming language.

In principle, a rectangular image can have any positive height and width. For example, the size of an image taken by a Scribbler 2 depends upon version of the Fluke card that is plugged into the robot. Images for the original Fluke are 192 pixels high by 256 pixels wide. Low-resolution images for the Fluke 2 are 266 by 427. More generally, users might wish to create and transform their own images, and a user might naturally want to determine the size of their pictures. Note that high-resolution images from the Fluke 2 (e.g., 800 by 1280) are not practical due to memory constraints and thus are not available in MyroC.

As already noted, it seems particularly natural to store an image in MyroC as a 2-dimensional array, with the rows and columns corresponding to the picture's raster.

The C programming language requires the size of a 2-dimensional array to be specified when the array is declared, and access to pixels in a 2-dimensional array is possible only when the number of columns is known when a program is compiled.

Altogether, users may run their programs with either an original Fluke or with a Fluke 2 (or even both types of Flukes), and users may wish to create pictures of varying sizes. Yet, C requires 2-dimensional arrays to have a specified number of columns (determined at compile time).

MyroC resolves this problem by recording the height and width of an image as fields in the Picture struct and by declaring the struct's pix_array to be sufficiently large (266 pixels high by 427 pixels wide) to accommodate any Fluke version. Further, user-defined images may have any size, as long as height ≤ 266 and width ≤ 427.

With this arrangement, sufficient space is available for a wide range of image sizes; not all alllocated space may be used for each picture, but the 2-dimensional array size within the Picture struct is adequate for many applications.

Rows and Columns

As a separate potential complication, a pixel labeled [i][j] might be considered in either of two ways:

Unfortunately, these two interpretations are exactly opposite regarding which index represents a row and which a column. In addressing this possible confusion, MyroC consistently follows the first interpretation:

Following standard mathematical convention for a 2D matrix, all MyroC references to a pixel are given within an array as [row][col].

Image Formats

Since image processing is used in a wide variety of applications, several common formats are used to store image data. The approach here, with an array of R/G/B pixels, is conceptually simple. However, other formats are possible as well.

The camera in a Scribbler 2 robot actually uses a different color designation (YUV format). Behind the scenes, the Scribbler transmits YUV values to your workstation, where the rTakePicture function transforms the YUV color coding to the more common RGB format.

Since images can consume much space, various formats are used to compress file sizes to speed the transmission of images and to reduce storage requirements. Each format has specific advantages for certain purposes. The .jpg or JPEG format was created by the Joint Photographic Experts Group (hence the acronym) and is largely based on what people actually see. Since this format is particularly common, MyroC provides functions to convert between a raw RGB format and JPEG format:

See the MyroC header file for details on each of these functions.

Pictures as Parameters

Since MyroC's Picture is a struct containing a 266 by 427 array of 3-byte Pixels, one Picture requires about 340,746 bytes of data. This size has at least two consequences.

Further, in a normal function call, C copies a struct in the same way that C copies the value of a int, float, or double. That is, suppose a function has the header

void munge (Picture pic)

Then the call munge(pix) (perhaps in main) copies all Pixel values in the pix_array field of pix to the corresponding array for parameter pic within munge. As a result, function calls with Picture parameters are generally time consuming.

For this reason, many Picture functions within MyroC utilize a pointer to a Picture, rather than the Picture itself. For example, the function to display a Picture on the terminal has the header

void rDisplayPicture (Picture *pic, double duration, const char * windowTitle)

and a typical call (from a main procedure) might be

rDisplayPicture (&pic, 5.0, "original pic");

In this call, the address of a Picture, &pic is the first parameter. With this call, the designated image will be displayed for a 5.0 seconds duration, and the image will appear in a window with the title "original pic".

Run-time Limitations

As a struct containing a 2-dimensional arrays of pixels, a Picture requires a moderate amount of space. In particular, an individual Pixel requires 3 bytes of main memory, so a 266 by 427 array of Pixels requires 340,746 bytes of memory. A typical int often requires 4 bytes, so an entire Picture in MyroC requires about 340,754 bytes of memory. Such space is readily available in modern computers.

However, operating systems often limit the amount of memory allocated when running an individual program, and this can impact applications—particularly if a MyroC program has arrays of images. Here are some observations on recent Linux and Mac OS X systems.

Examples

A Small Picture Example

This demonstrates a small picture example and the effect of copying the values from one variable of type struct to another variable of the same type.

structcopy.c

Splicing Pictures

The following program demonstrates how to capture images with the robot then iterate over the pixels in the image, assigning color values.

picture-splice.c
/* Example program taking two pictures using the Scribbler 2 and shows a
 *  picture composed of pieces of the two pictures */

#include <stdio.h>
#include <MyroC.h>

int
main (void)
{
  Picture  pic1,  pic2,  spliced;
  int width, height, midcol, midrow;
  
  rConnect ("/dev/rfcomm0");

  /* Take a picture from current position, turn slightly, and take another */
  pic1 = rTakePicture();
  rTurnLeft (1, 1);
  pic2 = rTakePicture();

  /* Display both pictures */
  rDisplayPicture (&pic1, 5, "Picture 1");
  rDisplayPicture (&pic2, 5, "Picture 2");

  /* Picture size depends on the camera -- extract and calculate the middle */
  height = pic1.height;
  width = pic1.width;
  midrow = height / 2;
  midcol = width / 2;

  spliced.height = height;
  spliced.width = width;

  /* Iterate over the pixel locations, taking the top-left and bottom-right
     quadrant's pixels from pic1, and the others from pic2 */
  for (int row = 0; row < height; row++)
  {
    for (int col = 0; col < width ; col++)
    {
      if ( ((col < midcol) && (row < midrow)) || /* top-left quadrant */
           ((col > midcol) && (row > midrow)) )  /* bottom-right quadrant */
        spliced.pix_array[row][col]=pic1.pix_array[row][col];           
      else
        spliced.pix_array[row][col]=pic2.pix_array[row][col]; 
    } // col
  } // row

  /* Display the result as a non-blocking command before exiting */
  rDisplayPicture (&spliced, -3, "Spliced Picture");
  rDisconnect();
  return 0;
} // main

Passing Pictures

The following example highlights additional issues in Picture creation, display, and saving as well as passing them as parameters.

picture-example.c
/* Program to illustrate the creation and development of a Picture
   with MyroC.

   For this example, a Picture is developed, displayed, and saved with
   these properties:

   * the Picture will be 200 pixels high by 300 pixels wide
   * the outside border of the picture is black
   * the inside picture (a square of 150 pixels by 150 pixels)
        has diagonal rows of colored stripes
   
   Written by Henry Walker with modifications by Jerod Weinman
*/

#include <stdio.h>
#include <MyroC.h>

/* Create and return an image that is all black */
Picture
create_black_image (int height, int width);

/* Add a diagonal rainbow of stripes to a Picture */
void
add_stripes (Picture * p_pic);

int
main (void)
{
  printf ("program to create, display, and save an image\n");

  printf ("creating and displayng a black image\n");
  Picture pic = create_black_image (200, 300);
  /* Display image for 5 seconds in window called "original pic" */
  rDisplayPicture (&pic, -5.0, "original pic");
  
  printf ("adding stripes to image and displaying the result\n");
  add_stripes (&pic);
  rDisplayPicture (&pic, 5.0, "stripped pic");

  printf ("saving picture to file called 'stripped-picture.jpg'\n");
  rSavePicture (&pic, "stripped-picture.jpg");
  
  return 0;
} // main

/* Create and return an image that is all black */
Picture
create_black_image (int height, int width)
{
  Picture newPic;
  Pixel blackPixel = {0, 0, 0};

  /* set dimensions of new picture */
  newPic.width = width;
  newPic.height = height;

  /* iterate through all pixels in the picture, setting each to black */
  for (int row = 0; row < height; row++)
    for (int col = 0; col < width; col++)
      newPic.pix_array[row][col] = blackPixel;

  return newPic;
} // create_black_image

/* Add a diagonal rainbow of stripes to a Picture */
void
add_stripes (Picture * p_pic)
{
  const int TOP_BOT_BORDER = 25;
  const int LEFT_RIGHT_BORDER = 75;

  /* Calculate loop bounds (only once) */
  const int end_row = (*p_pic).height - TOP_BOT_BORDER;
  const int end_col = (*p_pic).width - LEFT_RIGHT_BORDER;
  
  /* Define an array of pixel colors */
  Pixel colorPalette [6] = {   {255, 0, 0},      /* red */
                               {0, 0, 255},      /* blue  */
                               {255, 255, 0},    /* redGreen */
                               {0, 255, 0},      /* green */
                               {255, 0, 255},    /* redBlue*/
                               {0, 255, 255}  }; /* blueGreen*/
                             
  /* in adding stripes to the image, leave a border unchanged at top and
     bottom, left and right */
  for (int row = TOP_BOT_BORDER ; row < end_row ; row++)
    for (int col = LEFT_RIGHT_BORDER ; col < end_col ; col++)
    {
      /* stripes will be 10 pixels wide,
         and will repeat every 6 colors */
      int colorIndex = ((row + col) / 10) % 6;
      
      (*p_pic).pix_array[row][col] = colorPalette [colorIndex];
    }
} // add_stripes