Pixels

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.

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 for example). 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.

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.

Here is an outline of how the program is setup.

• usepix.cpp - the main function is here.

  This function creates a PixChoices object and then repeatedly asks the user what they would like to do.

• PixChoices class - (pixchoices.h, pixchoices.cpp)

  This class prints a menu of options and then based on the option selected, starts the option.

• PixMap class - (pixmap.h, pixmap.cpp)

  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.

  class Pixmap { public: Pixmap(); // constructor (0-sized bitmap) // mutator functions void read(istream& input); // read pixmap from file void setPixel(int r, int c, int val); // set pixel (r,c) to val void setSize(int r, int c); // set size of image // accessor functions void write(ostream& output) const; // write image to file void compress(ostream& output) const; // run-length output int getPixel(int r, int c) const; // get pixel value int getRows() const; // number of rows in image int getCols() const; // number of columns in image int getLevel() const; // get (gray) level private: string myKind; // P1, C1, P2, etc. string myCreator; // program name that created pixmap int myLevel; // # different grays/colors tmatrix<int> myMap; // values that make up the image int myRows, myCols; // number of rows and columns in image };

• PixInvert class - (pixinvert.h, pixinvert.cpp)

  This class is used to invert the matrix.

• PixReflect class - (pixreflect.h, pixreflect.cpp)

  This class is used to reflect the matrix, either horizontally or vertically.

• PixExpand class - (pixExand.h, pixExpand.cpp)

  This class is used to expand the bitmap.

DO NOT add any more .cpp or .h files and DO NOT CHANGE THE MAKEFILE for any of these.

1. Write the invert function in the PixInvert class.

   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).

2. Write the vertReflect in the PixReflect class.

   An image can 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
   

3. Write the horizReflect function in the PixReflect class.

   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
   

4. Write the expand function in the PixExpand class

   4 points EXTRA if the expand is done without an extra matrix. Make sure you put a note of this in your README file.

   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.

   

5. Modify the read function in the PixMap class to read in compressed files.

   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 can be read in, you must add code so that compressed black-and-white images can be read.

   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.

   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

   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).

   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.

   • 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

   After writing the compress part of the read function, you should test the compression on mystery.cbm or any .cbm file to see if you can read it in correctly.

6. Write the compress function in the PixMap class to write compressed files.

   Compress is 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.

   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.

   You should 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.

EXTRA CREDIT

DO NOT add any more .cpp or .h files and DO NOT CHANGE THE MAKEFILE for any of these.

1. (4 pts) See the extra credit above on Expand, doing the expansion in place.

2. (1 pt) Create an interesting image to submit. You can use bitmap, xpaint, or some other tool to create it. It should be called image.pbm or some other appropriate . extension.

3. (2 pts) Gray Scale Compression

   You'll need to invent a scheme for gray-scale compression, there is no "standard" method for doing this.

   (4 pts) Enhance is 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.

   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).

   NOTE: you cannot modify the Makefile. For this part, consider creating a new class. Put its .h and .cpp in existing files. Do not create any new files! Ideally, it would be best to create new files for this part, but it complicates the grading.

Submit

When all your programs compile and produce the correct output, create a file named README (please use all capital letters in naming the file). In the file include your name, section number, the date, and an estimate of how long you worked on the assignment . You must also include a list of names of all those people with whom you consulted on the assignment. See the CPS 6 web page for the meaning of consult.

Please note .h files must also be submitted!

To submit your programs electronically you must be in your assign6 directory and type (REPLACE instructor with rodger or ramm depending on who your professor is, for example Prof. Rodger's students would type assign6rodger):

submit_cps006 assign6instructor *.cpp *.h README

You should receive a message telling you that the programs were submitted correctly. If the submit_cps006 command does not work, then try

  ~rodger/bin/submit6 assign6instructor *.cpp *.h README

To see that the programs were submitted correctly, type (REPLACE instructor with rodger or ramm depending on who your professor is, for example Prof. Rodger's students would type assign6rodger):

    submit_cps006 assign6instructor

with no arguments and a list of the files submitted will be shown. PLEASE RUN THIS COMMAND to make sure your programs were submitted correctly.

The submit command with *.cpp submits all of your .cpp programs in your current directory at the same time. You can resubmit again if you realize you made a mistake and want to change something. If you submit more than once, we grade the last submission. If the first submission is on time and the last one is late, then the programs are late. All programs must be turned in together. You cannot submit one program early and the rest late.