CPS 6: Assignment 7
Summer 1999
Bit-mapped Graphics and Matrices
Due Friday, June 25, 11:59pm
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
Change into your cps6 directory
and create a directory called "assign7".
Change into the "assign7" directory.
In order to do this assignment, you need to copy files using the
following "cp" command (don't forget the trailing period, or dot). Type:
cp ~dr/cps6/assign7/* .
You'll need to link to a datafile of images by typing:
ln -s ~dr/cps6/images images
If you type "ls" you should see "Makefile", "images",
"usepix.cc", "pixmap.h",
and "pixmap.cc".
For the programming problem that follows, you should use the
style rules discussed in class, which includes meaningful variable names,
indentation, and comments at the top of the file and for each function.
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.
Go ahead and compile the program, type: make usepix
The program already reads in and displays black-and-white and grayscale
images, so lets run it to see these.
Run the program by typing: usepix
Select (l)oad image by typing the letter: l
For the name of the directory, type: images
(assuming you linked this directory correctly above)
Then type the number of a black-and-white image (or .pbm file),
try the number for rodgertiny.pbm
Once loaded, to display the image, type: d
The tool xv will pop up with a picture. To remove the picture, type
the letter q with the mouse cursor on the picture.
You can also load and display gray-scale images (or .pgm files)
Load another file by selecting (l)oad, type: l
followed by the directory: images
Select a .pgm file by typing the number associated with the file,
try rodger.pgm
Then display the file, by typing: d
The tool xv will pop up with a picture. To remove the picture, type
the letter q with the mouse cursor on the picture.
You cannot display compressed images yet (files in .cbm format), as you
will have to implement this. Don't do it yet, easier modifications
are suggested first below.
You can save black and white and gray-scale images in uncompressed form
as this has been implemented for you. To save an image, just select
(s)ave, give the image an appropriate name (.pbm or .pgm extension)
and the image will be written to your directory. To view the image, load
it from your directory (type . for your directory) and then display it.
This will be useful when you make changes to an image and then want to save
it.
NOTE: If you save an image, then it will be in your directory. To see
the image, load the directory '.' (the current directory).
WARNING: Many of the images are LARGE files. If you save a lot of images,
you may run out of disk space. Delete images you are no longer using.
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 matrix
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.
When you compile the program you MUST type
make usepix (do not type make pixmap). Also, be sure to
use getline for user-input and not >>. Finally, you MUST
run this program on a machine that uses X-windows if you use the display
option.
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.
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: CPS06 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. If you decide to do
this, you'll need to invent a scheme for gray-scale compression, there
is no "standard" method for doing this.
-
Invert
-
A method that inverts the image as described below.
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.
Note:
In writing this method, an auxiliary array or another Pixmap
CANNOT be created.
-
HorizReflect
-
A method that reflects the image along the horizontal axis as described
below.
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.
You can use an auxiliary matrix for this, but you will receive up to 4
points extra credit if you do the expansion in place, i.e., you do NOT
use an auxiliary matrix. Be sure to resize the matrix if necessary, or
abort the expansion if you decide not to resize (either approach is ok).
Here is a suggest ordering to help you get started.
After each modification, recompile usepix and make sure it works
correctly before moving on to the next modification.
Note that there is more info on each of these operations further down
on the handout.
-
Implement the function Pixmap::HorizReflect in pixmap.cc.
Try it first on black and white images, then grayscale images.
You can save the image and then compare it to the original image if you want.
-
Implement the function Pixmap::VertReflect in pixmap.cc.
-
Implement the function Pixmap::Invert in pixmap.cc
-
Modify Pixmap::Read in pixmap.cc to read in a black-and-white compressed
image. Try this out with one of the .cbm data files that is in C1 format,
for example, mystery.cbm
If it doesn't work, since all the .cbm files are very large,
you might want to write a small sample .cbm file
with just a few lines to test out.
After reading it in, write it to a file (uncompressed) and compare the two.
-
Modify PixMap::Compress in pixmap.cc to compress a black-and-white image.
You will also have to make some modifications in usepix.cc.
Again, use the small test file above to check this out first, before trying
a large file.
- There are still more modifications to make. Hopefully that was enough
to get you started.
Optional Member Functions
The member functions
below are optional. Each one can earn 4 extra points.
-
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, perhaps, 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
When your programs
compile and produce the correct output, create a "README" file
(please use all capital letters). Include your name, section number,
the date, and an
estimate of how long you worked on the assignment in the "README"
file. You must also include a list of names of all those people with
whom you collaborated on the assignment.
To submit your programs electronically type:
submit6 assign7 pixmap.cc pixmap.h usepix.cc README image.pbm
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, Enhance, or in-place expansion,
each can earn 4 extra points.
Viewing Images
Several images can be found in the directory images
that you have already linked to.
Since these images
use some space, you may not want to copy all of
them.
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 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 lenore.pbm for example), the images can be
altered, painted, etc.
Have fun.
