Assignment 3: Bit-mapped Graphics and Matrices

CPS 100E, Fall 1995

due: October 23 at 8am, 20 points
This programming project involves writing a program for manipulating bitmap pictures. Your program will be able to read in and write out bitmaps, and perform several operations on bitmaps (invert, reflect, enhance, and expand a picture). The program will also be able to read and write compressed pictures. Finally, you'll be able to read all the files in a directory and allow the user to select one of these files for manipulation.

Getting Started

You should create a subdirectory named prog3 in your cps100e directory. This should copy the following file(s): Makefile, usepix.cc, pixmap.h, pixmap.cc.

Verify that these file(s) have been copied by typing ls to see all the files in the current directory. In particular, the Makefile for this assignment is different than makefiles from previous assignments so be sure you have copied the file from ~ola/cps100e/prog3 . You should create a link to a directory of images. To do this type

    ln -s ~ola/data/images images
You can then type ls images to see the names of the images stored there. When prompted for the name of a file to load, you can type images/mystery.cbm , for example.

Bit-maps

Many different forms of graphical images exist. Common forms include gif , tiff , and X-window dumps . In this assignment a form of image called a bitmap will be used. These bitmaps can be black-and-white, gray-scale, and color. This assignment uses only black-and-white and gray-scale images.

Pixels

An image can be represented as a 2-dimensional grid of pixels, each of which can be off (white) or on (black). Color and gray-scale images can be represented using multi-valued pixels. For example, numbers from 0 to 255 can represent different shades of gray. A bitmap is a 2-D grid of 0's and 1's, where a 0 corresponds to an off pixel and a 1 corresponds to an on pixel. For example, the following is a bitmap which represents a 9x8 picture of a `<' sign. The bitmap of 0's and 1's on the left is shown as it is displayed on the screen using the program xv on the right (enlarged eight times).

0 0 0 0 0 1 1 0
0 0 0 0 1 1 0 0
0 0 0 1 1 0 0 0
0 0 1 1 0 0 0 0
0 1 1 0 0 0 0 0
0 0 1 1 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 0 1 1 0 0
0 0 0 0 0 1 1 0

Representing images as bitmaps is very natural, and some reasonably nice tools for drawing and displaying bitmaps can be found in the UNIX environment ( xpaint and xv are described below). Although representing such images using the '0' and '1' characters (or the numbers 0 and 1) may be wasteful of space (a character is 8-bits and as a '0' or '1' represents only 1-bit of information), it is conceptually simple and methods for compressing such images exist.


Your program

You are to complete the implementation of the Pixmap class, as outlined in the files pixmap.h and pixmap.cc . The data fields of the Pixmap class include a struct Map that stores a 2-D array of pixels (the image field), the dimensions of the array (number of rows and columns); the number of gray-levels (1 for black-and-white and usually 255 for gray-scale) and two comment strings which store information about the file from which information about the bitmap is read. You will be implementing some of the member functions that are currently not implemented.

Required Member functions

You must complete the following member functions:
Read
A member function that takes an input stream and reads in a picture from that stream. Picture files can be formatted in either black-and-white, gray-scale, or (run-length) compressed form. Currently only black-and-white and gray-scale forms are implemented, you must add code so that compressed black-and-white images can be read (you should have started this in lab). Input files are formatted as described below. For example, the `<' picture can be read in from either of the files shown below
P1                                       
# CREATOR: XV Version 3.00 11/29/94
  8 9                                    
  0 0 0 0 0 1 1 0                        
  0 0 0 0 1 1 0 0                        
  0 0 0 1 1 0 0 0
  0 0 1 1 0 0 0 0
  0 1 1 0 0 0 0 0
  0 0 1 1 0 0 0 0
  0 0 0 1 1 0 0 0
  0 0 0 0 1 1 0 0
  0 0 0 0 0 1 1 0
C1                     
# CREATOR: CPS100E Pixmap 9/25/95
8 9                    
5 2 5 2 5 2 5 2 5 2    
7 2 7 2 7 2 7 2 1      

Compress
A method that takes an output stream and writes the picture to that stream in compressed form . This method is similar to Write in that it should produce a file in a form that can be read back in to the program. The first line of output must be the identifier ``C1'', the second line is some creator string, the third line gives the number of columns and rows. The following lines are the run-length encoding of the image. Be sure that the encoding starts with a number of zeros (this number might be 0 indicating no zeros). When writing this function be very careful that the last number is written. Depending on how your compression code is written, you may need a statement after the loop you use. You don't need to implement compression of gray-scale images, but extra credit is awarded if you do.
Invert
A method that inverts the image as described below. You should have started this in lab. Note: In writing this method, an auxiliary array or another Pixmap CANNOT be created.
VertReflect
A method that reflects the image along the vertical axis as described below. You should have started this in lab. Note: In writing this method, an auxiliary array or another Pixmap CANNOT be created.
Expand
A method that expands the image in horizontal and/or vertical directions. If the expansion is begun in the lower right hand corner of the image an auxiliary array is not needed. Be sure to check that there is room for the expansion before doing it (you can always resize the matrix to ensure that there is room). The user should be prompted for the expansion factor of rows and columns (the prompting will be done in usepix.cc NOT in pixmap.cc . Expansion is described in more detail below.

Optional Member Functions

The member functions below are optional. Each one can earn 4 extra points These points can be applied to any non-test area of the course (e.g., labs, program, quizzes). Some are tough.
BlobCount
A method that counts ``blobs''. A blob is a contiguous black pixel region. In this case contiguous means adjacent either horizontally, vertically, or diagonally. Writing this routine will require some ingenuity and the use of an auxiliary recursive function. We'll discuss the details in class. For example, in the image shown below, there are 10 blobs. This function might be useful in processing slides in biology, for example.
Enhance
A method for changing the pixels to improve the quality of the picture. This method is described in some detail below. The user should be prompted for the size of the neighborhood to be used in the enhancement process.

Run-length encoding

Representing bit-mapped images as sequences of numbers is not (usually) efficient in terms of storage requirements. Usually, images contain much more white than black, and ``pockets'' of black (and white) tend to be localized. Bit-maps can be compressed via various methods to store pictures more efficiently. One compression method is called run-length encoding . Under this scheme, the bits in an image are scanned in row-major order, i.e., numbers are read across the first row from left to right, followed by the second row, and so on. When run-length encoding is used, the number of consecutive 0's is counted, then the number of consecutive 1's, then 0's, and so on. For example, the bitmap image above of the < symbol begins with five 0's, then two 1's, then five 0's, then two 1's, etc. The entire file is represented in compressed form by the following:
        5 2 5 2 5 2 5 2 5 2 7 2 7 2 7 2 7 2 1
Note that the sum of these numbers is 72, the number of bits in the original image. However, 19 numbers are used to represent what 72 numbers represented in the original image. In general, run-length encoding can offer considerable savings, and still be in ``human'' readable form.

By convention, the first number in a run-length encoding always corresponds to a sequence of 0's.

Thus, if a bitmap has a 1 as the first bit, then the first count in the run-length encoding will be 0 (since there are no zeros initially).


Manipulating bitmaps

Several operations can be applied to bitmaps that change them in some way. In the class Pixmap that you will work with for this assignment you will be implementing several of these operations (some are optional).

Inversion

Inverting a bitmap is a simple operation. To invert a bitmap, each bit must be inverted: 0's are changed to 1's and vice versa. For example, if the bitmap above is inverted the following image is obtained:
        1 1 1 1 1 0 0 1
        1 1 1 1 0 0 1 1
        1 1 1 0 0 1 1 1
        1 1 0 0 1 1 1 1
        1 0 0 1 1 1 1 1
        1 1 0 0 1 1 1 1
        1 1 1 0 0 1 1 1
        1 1 1 1 0 0 1 1
        1 1 1 1 1 0 0 1
Inverting a gray-scale image is possible too. If the gray-scale values range from 0-255. Then an image with value X is inverted by setting it to 255-X. In general, inversion of any pixel value X can be done by changing it to MAX - X where MAX is the largest value a pixel can have (1 in black-and-white, some other value in gray-scale --- but usually 255).

Vertical Reflection

An image can also be reflected along an axis (usually horizontal, vertical, or diagonal). Reflecting along a vertical axis through the middle of an image is the same as reversing the contents of each row (similarly, reflecting along the horizontal axis is the same as reversing each column). For example, when the original `<' bitmap above is reflected along the vertical axis the following image is obtained:
        0 1 1 0 0 0 0 0
        0 0 1 1 0 0 0 0
        0 0 0 1 1 0 0 0
        0 0 0 0 1 1 0 0
        0 0 0 0 0 1 1 0
        0 0 0 0 1 1 0 0
        0 0 0 1 1 0 0 0
        0 0 1 1 0 0 0 0
        0 1 1 0 0 0 0 0

Horizontal Reflection

The original image above (the < symbol) is unchanged if it is reflected in a horizontal line through the middle of the image. Reflecting a slash, however, is diagrammed below: the image on the left, when reflected in a horizontal line though the middle of the image, results in the image on the right. Note that each column of numbers is reversed.
     1 0 0 0 0            0 0 0 0 1
     0 1 0 0 0            0 0 0 1 0
     0 0 1 0 0            0 0 1 0 0
     0 0 0 1 0            0 1 0 0 0
     0 0 0 0 1            1 0 0 0 0

Enlargement

A bitmap image can be enlarged by expanding it horizontally, vertically, or in both directions. Expanding an image in place, i.e., without using an auxiliary array, requires some planning. In the figure below, an image is shown partially expanded by three vertically, and by two horizontally. By beginning the expansion in the lower right corner as shown, the image can be expanded in place --- that is without the use of an auxiliary array or bitmap. This will require careful planning in order to expand without using an extra array for storage.

Enhancement

Sometimes an image can be ``noisy'', e.g., it might be garbled when it is transmitted. Image enhancement is a method that takes out noise by changing pixel values according to the values of the neighboring pixels. The method used in this program is based on setting a pixel to the median value of those in its ``neighborhood''. The diagram below shows a 3-neighborhood and a 5-neighborhood of the middle pixel whose value is 28.
Using median-filtering, the 28 in the middle is replaced by the median of the values in its neighborhood. The nine values in the 3-neighborhood are (10 10 12 25 25 28 28 32 32). The median, or middle, value is 25 --- there are four values above 25 and four values below 25. The values in the 5-neighborhood are (10 10 10 10 10 10 12 12 12 18 18 18 25 25 25 25 25 25 32 32 32 32 32 32 32), and again the median value is 25 because there are 12 values above and 12 values below 25. The easiest way to find the median of a list of values is to sort them and take the middle element. Pixels near the border of an image don't have ``complete'' neighborhoods. These pixels are replaced by the median of the partial neighborhood that is completely on the grid of pixels. One way of thinking about this it to take, for example, a 3 x 3 grid and slide it over an image so that every pixel is centered in the grid. Each pixel is replaced by the median of the pixels of the image that are contained in the sliding grid. This requires using an extra array to store the median values which are then copied back to the original image when the median-filtering has finished. This is necessary so that the pixels are replaced by median values from the original image, not from the partially reconstructed and filtered image. Applying a 3 x 3 median-filter to the image on the left below results in the image on the right (these images look better on the screen than they do on paper).

Testing your program

You should test your program on mystery.cbm to see if you can read a compressed file. You should also read a normal file, compress it, read it as a compressed file, write it out, then use the Display option to see if it's the same.

Submission

To turn in this program use:
     submit100e prog3 pixmap.cc pixmap.h usepix.cc README image.pbm
The README file should indicate how long you worked on the assignment, with whom you collaborated, and any comments you have about the program. The file image.pbm should be a bitmap image you enjoy (and that you helped to create using some paint/draw program). Please send this as a compressed image if compressing saves space.

Grading

The functions that invert and reflect the image are worth a total of 4 points. Expansion is worth 5 points. The run-length encoding is worth 4 points. The README file and the image you create are worth a total of 3 points. Style will count for 4 points. If you implement BlobCount or Enhance, each can earn 4 extra points.

Viewing Images

Several images can be found in ~ola/data/images Since these images use some space, you may want to create links to them rather than copying them (see above). There are several ``interesting'' images stored there, you may find other images by asking your friends and acquaintances, or by surfing the internet. The Display option of the program usepix uses the shareware program xv . The program xv can be used by itself too. To invoke the program on the duke logo, for example, type xv duke.pbm . The xv program can read files in bitmap, gray-scale, giff, tiff, and a host of other formats (X-window dumps too). When the image is displayed, clicking the right mouse button when the cursor is on the image brings up the a menu of things to do with the image. It can be rotated, dithered, enlarged, etc. This program will allow you to view the images created by your Pixmap class and program. When a file is saved from within xv , it is possible to specify the kind of file. Specifying PBM ASCII files will permit the saved file to be processed by your program (as bitmap or P1 files). So a giff image can be scanned, examined using xv , then rewritten as a a portable bitmap (PBM) in ASCII. To quit xv type 'q' when the cursor is on the picture or click the quit button. The program xpaint will also process files in this ASCII portable bitmap format (as well as other formats). By scanning images into xpaint (type xpaint owen.pbm for example), the images can be altered, painted, etc.

Have fun.