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.
- Verify that you're in the cps100e directory by typing
pwd (print working directory).
Then type mkdir prog3 to create the subdirectory
prog3 .
- Change into the prog3 subdirectory
and type
cp ~ola/cps100e/prog3/* .
which will copy all the files
from the directory ~ola/cps100e/prog3
into your prog3
directory. Don't
forget the trailing period, or dot. If you do, you might get an error
message something like Permission denied .
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.
- The first line in a picture file will contain a string specifying
the file type. The identifier ``P1'' specifies a black-and-white
image, ``C1'' specifies a compressed image, ``P2'' specifies a
gray-scale image. You can, for extra credit, implement ``C2'' to
be used for compressed gray-scale images. Any other identifier
represents an unknown file type that should be ignored. This string
should be stored in the myKind field of a Pixmap object.
Be careful when writing out a compressed or uncompressed file:
the proper string MUST be written first or when it is subsequently
read in the program will not interpret the image correctly.
- The second line in a picture file is a comment identifying
the program that created the image.
This info should be stored in the myCreator field of
a Pixmap object. If you modify the image, you should change the string
that is written out to register that your program created the image.
All comments in a datafile MUST begin with a sharp-sign #
or the program xv won't process the file correctly.
- The third line of a file contains the dimensions
of the picture:
first the number of columns and then the number of rows.
These numbers should be stored in the appropriate fields of the
myMap field of a
Pixmap object. Be careful! The first number is the number of
columns .
For gray-scale images there is a third number that represents
the maximum value of the numbers used in the gray-scale image.
- Subsequent lines contain the actual bits/counts that describe
the picture.
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.