T-Th 9:05 or 11:15
in Kimball B11

CS 1110: Introduction to Computing Using Python

Spring 2013

Assignment 6:
Images

Due to CMS by Saturday, April 13th at 11:59 pm
These instructions last updated on April 08 2013 18:19.
Added authorship info and section numbers.

Authors: D. Gries, L. Lee, S. Marschner, W. White.

Digital imaging is a ubiquitous tool in modern life: we snap photos with our phones, share them with friends and family, crop them, edit them, post them to online galleries, and it's all done with two-dimensional arrays of triples of numbers, giving the red, green, and blue values for each pixel that makes up the image. Lots of photo editing applications provide tools to modify images to your liking, and they all work by modifying these arrays of pixel values.

You can represent an image as a 2-dimensional list of color pixels. To avoid the overhead created by lists of lists in Python, however, it is common to represent an image as a 1-dimensional list with the pixels all listed together, row by row—known as row-major order, as described below. Calculating indices into a row-major array can make code hard to read, so this assignment, like most code that deals with images, encapsulates the image's pixel list inside a class (in our case ImageArray) that provides an abstraction to let us treat the list of pixels as a two-dimensional array—or as a 1D array depending on our preference. So in addition to learning about images, you will also see encapsulation in action.

Reading the Instructions

These instructions are fairly long, and you should spend an evening simply reading these instructions while looking over the existing classes. Even though you don't need to understand every detail of the ImageArray class, or especially of the user interface, you should be able to see how the program fits together: what calls what, which data goes where. It's important to understand the overall plan before you start writing your code.

Learning Objectives

This assignment has several important objectives.

• It gives you practice with writing loops and using invariants.
• It gives you practice with writing loops to process one- and two-dimensional sequences.
• It gives you practice with using helper methods and constants to structure your code properly.
• It gives you practice with using encapsulation to make difficult programming concepts easier.
• It introduces you to the concept of a tuple, which is essentially an immutable list.
• It gives you practice with manipulating images at the pixel level.

Table of Contents

• Before You Get Started
• Academic Integrity
• Collaboration Policy
• Assignment Source Code
• Running the Application
• Getting Help
• Understanding the ImagerApp Application
• Code Organization
• Class ImageArray
• Pixels and Tuples
• Class ImagePanel
• The Module imager.kv
• Class Main
• Class ImageProcessor
• Assignment Instructions
• Testing Guidelines
• Task 1. vertReflect
• Task 2. jail
• Task 3. monochromify
• Task 4. vignette
• Task 5. Blurring, two flavors
• Finishing the Assignment

Before You Get Started

Read this entire document carefully. Budget your time wisely. In particular, you should get started on this assignment immediately. You have just over a week to work on this assignment, and there is no room to grant (further) extensions, with the second prelim coming on its heels. There are six methods in total. We recommend that you work on at least one method a day.

Academic Integrity

We have used various versions of this assignment in past versions of the class, both in Java and in Python. It is a good one, and students really like it. Do not share your code with others. Do not obtain or look at a copy of the earlier solution or a version being done by another student. Such cheating helps no one, especially you, and it makes more unnecessary work for us.

It is highly unlikely that your code for this assignment will look exactly like someone else's. Once again, we will be using Moss to check for instances of cheating and plagiarism. Anyone caught copying code will be prosecuted, with the end result perhaps being to fail the course.

Collaboration Policy

You may do this assignment with one other person. If you are going to work together, then form your group on CMS as soon as possible. If you do this assignment with another person, you must work together. It is against the rules for one person to do some programming on this assignment without the other person sitting nearby and helping.

With the exception of your CMS-registered partner, you may not look at anyone else's code or show your code to anyone else, in any form whatsoever.

Assignment Source Code

The first thing to do in this assignment is to download the zip file A6.zip from this link. You should unzip it and put the contents in a new directory. This zip file contains the following:

imager.py

This file contains the class Main, which is the primary class for the application. It initializes all of the objects in the application. It has methods that perform actions in response to the user clicking on buttons in the application.

The file also contains subsidiary classes that manage dialogs that appear in response to various user actions (loading a file, saving a file, etc.). It also has the main driver class ImagerApp that initializes the GUI and starts up the application.

imager.kv

This is a Kivy declaration file that describes the layout of the GUI with buttons, panels, and other features. It does not do anything with the buttons; it just describes their arrangement on the screen, while imager.py has the methods that perform actions when they are clicked.

image_panel.py

This module contains a single class ImagePanel. Objects of this class have a single method: display, which is used to draw an image on an ImagePanel.

image_processor.py

This file contains a single class ImageProcessor, which is the class that has methods for manipulating an image. This is the only class that you will need to modify.

image_array.py

This file contains a single class ImageArray. An object of this class maintains an array of pixels in an image in row-major order. It has methods for getting and setting a pixel in an image, and provides abstractions to treat the image as either a 1-dimensional or a 2-dimensional list.

samples/

This is a subdirectory containing a number of images in .jpg and .png format. You are welcome to add your own images if you like, though you'll want to shrink them down pretty small; this program would be slow on multi-megapixel images straight from a camera or phone.

The program is explained in more detail below. The only class that you will need to modify is ImageProcessor. However, be sure to look at the code for the entire project, as it is very illuminating, and it is hard to understand what your code needs to do without understanding the overall plan.

Running the Application

In order to run the application, navigate to the directory containing these files and type

  python imager.py

This will import all the files and run the application. A window will open with two versions of a default image, some buttons, and a text area, as shown below.

When you modify an image with this application, the left image will not change; it is showing the original image. The right image will change as you click buttons. The actions for the buttons Invert, Transpose, Horizontal Reflect, and Rotate Right are already implemented. Click on them to see what they do. The effects of the buttons are cumulative. After any series of clicks, the Restore button returns the right image to its original state.

Python is not a speedy language, and pixels are numerous. When you click on the buttons, you might notice that it takes a second or two for something to happen. (If you go on to do image processing or scientific computing in Python, you will learn about libraries that let you do these oprations efficiently, without having to explicitly loop over the pixels.) To give you some feedback on this process, the word Processing... appears in the upper right corner whenever the application is doing something. If this word does not go away after 5 seconds or so, then your program is likely stuck and has a bug in it (e.g. you might have a while-loop that runs forever).

The remaining buttons are not implemented (Rotate Left does something, but not the correct thing. Do you see why?). It is your task to write the code to make them work.

Getting Help

If you do not know where to start, or if you are completely lost, please see someone immediately. This is a more complex assignment than the previous ones. You may talk to the course instructors, a TA, or a consultant. See the staff page for more information. Do not wait until the last minute!

Understanding the ImagerApp Application

Code Organization

The diagram to the right shows how this application is organized. When we draw lines between two components, that means that we are emphasizing that the two components must communicate with each other. If the components are objects of a class, communication is typically done by one object calling a method or accessing the data of the other. If there are no lines between two classes, then we are not concerned about communication between objects of those two classes. Thinking about which classes have to interact (and ideally, minimizing the number of these interactions) is an important part of designing a program.

In this diagram, the first class that is instantiated and has its methods called is ImagerApp; this happens when you type

   python imager.py

This class builds the GUI specified in the file imager.kv, and then calls the config method of the Main class. This method initializes the application, creating instances of the ImageArray and ImageProcessor classes. The Main class also listens for button presses and calls the appropriate method, called a handler, to do something in response.

Most of the time, the handler methods call a method in ImageProcessor to modify the displayed image, and then redraw the result. Some functionality, such as loading and saving a file, is provided by pop-up windows that are supported by other, minor classes in the imager module.

The image itself is maintained internally as a one-dimensional list of pixels in the class ImageArray. As an image is conceptually a two-dimensional list (width x height), the one-dimensional list stores the pixels in row-major order. This means that it first stores the elements of row 0, then the elements of row 1, then the elements of row 2, and so on. ImageArray provides methods for manipulating the image, allowing access to the pixels of an image row by row, column by column, or without regard to the order.

The class ImageProcessor provides methods for transforming an image stored in an ImageArray object. It does not hold the image data, but only manipulates it. As the lines in the diagram show, the ImageProcessor knows nothing about the GUI; it simply calculates. However, it does use the methods of ImageArray to accomplish its work.

The file imager.kv is a Kivy file that specifies the placement of buttons, labels with text, message area, and images on the screen. It also specifies the handlers to be called in response to button clicks. This file is not written in Python, but instead has an alternate format that is intended to make GUI layout simple. If you are interested, we describe a bit of it below.

Finally, there is the class ImagePanel. This is just the view to display the image. It has a single method called display which scales the image to fit on screen and displays it. In this application, there are two instances of ImagePanel, one for the original image on the left and one for the modified image on the right. Calling the display method of either one of them will cause its image to be updated, so that Python will redraw it.

The Class ImageArray

Abstractly, an image consists of a rectangular list of pixels (picture elements), where each pixel entry is a tuple that describes the color pixel. We show a 3x4 list below, with 3 rows and 4 columns, where each Eij is a pixel.

      E00  E01  E02  E03
      E10  E11  E12  E13
      E20  E21  E22  E23

Compared to nested lists, simple one-dimensional lists are easier to hand off to the graphics system in a single chunk, and to read from or write to files. And, sometimes it is more convenient to think of an image as just a list of pixels, without worrying about the 2D structure. Therefore, in practice, images are stored as one-dimensional lists.

The class ImageArray maintains the pixels in a list of length r*c, where r is the number of rows, and c is the number of columns. For the 3-by-4 image shown above, the list would contain the elements in row-major order:

      E00, E01, E02, E03, E10, E11, E12, E13, E20, E21, E22, E23

An object im of the class ImageArray maintains this list in its hidden field _data. You should never access this field directly. Instead, we have provided methods for accessing this field indirectly. You can get an individual pixel of im with im.get_pixel(row,col). You can also use im.get_flat_pixel(n). The former treats the image as a two-dimensional list, while the latter treats it as a one-dimensional list. The one that you wish to use depends upon your application. As you switch back and forth between these two methods, you will see the benefit of encapsulation (i.e. hiding the list itself and working with it through getters and setters).

In addition to the getters, you can change the image using im.set_pixel(row,col,pixel) and im.set_flat_pixel(n,pixel) in the same way. Thus, to set the pixel in row row and column col to a new value val, you would write im.set_pixel(row,col,val). There is also im.swap_pixels(r1,c1,r2,c2) which can swap the pixels at two different locations. That is all you need to know to manipulate images in this assignment. You never need to access the hidden field, and never need to be concerned about how the list is laid out.

If you look at the class ImageArray, you will notice that it does not enforce all preconditions, especially in the methods for getting and setting pixels. There are assert statements there, but they have been commented out. This is because of an unfortunate trade-off in programming; assert statements make your program safer, but they also slow it down. This is particularly true in image processing, where the methods containing these asserts are called thousands of times. Uncomment the assert statements in set_flat_pixel and then try the Invert button in the Imager application. See how much slower it is?

This is one reason we do not always enforce our preconditions. We put the preconditions in comments, but rely on "the honor system", as asserts would slow down the program. But asserts are really, really helpful with debugging, particularly when we have invariants, such as the restriction that each component of a color value is an int in 0..255. This is why we put the commented-out assert statements in ImageArray. If you are having trouble with one of the functions, uncomment these assert statements. Then, when you believe that everything is working fine, comment them out again so that the program runs faster.

Pixels and Tuples

As we discussed in a previous assignment, your monitor uses the RGB (red-green-blue) color system for images. Each RGB component is given by a number in the range 0 to 255. Black is represented by (0, 0, 0), red by (255, 0, 0), green by (0, 255, 0), blue by (0, 0, 255), and white by (255, 255, 255). In previous assignments, we stored these values in an RGB object defined in the colormodel module. These were mutable objects where you could change each of the color values.

In the ImageArray class we made a different design choice: the RGB colors are represented via tuples, not RGB objects. A tuple looks like a list, except that is defined without square brackets, and is usually written with parentheses. For example,

  x = (1, 3, 4, 5)

>>> x = (1, 3, 4, 5)
>>> x[0]
1
>>> x[1:3]
(3,4)

The only difference between a tuple and a list or object is that tuples are immutable. You cannot change the contents of a tuple, so an assignment like x[0] = 10) will produce an error. This means that in an ImageArray, the pixel values are immutable. You do not change an image by modifying the contents of a pixel object; instead you replace the pixel with a new one, using the setter methods in ImageArray). Speed is one of the reasons why we chose to use tuples to represent pixels. We could have converted these tuples to RGB objects to make them more familiar. However, like assert statements, this conversion would slow down image processing. So we want you to deal with tuples directly.

The Class ImagePanel

An ImagePanel object maintains two data items: a kivy.uix.widget.Widget object to display the image, and a reference to an ImageArray object. These items are supplied to the constructor when the ImagePanel object is created.

The display method is called to display an image on the Widget. If given an argument, it uses the new ImageArray object; otherwise it uses the one provided to the constructor. It constructs a "texture" from the image, calculates its proper size and placement, and applies the texture to the Widget. This is why we refer to ImagePanel as a view class; it does nothing but draw the image.

How does one learn to write all this code properly? When faced with doing something like this, most people will read the API specifications (located at kivy.org) and then start with other programs that do something similar and modify them to fit their needs.

The Module imager.kv

All of the other UI related components are defined in the file imager.kv. This is a Kivy file. It is a simple way to lay out buttons, sliders and text boxes that cuts down on the amount of Python code that you have to write. If you have ever done any work with web pages, this file is a lot like a CSS file. It defines the look of your application, so that you only need to write Python for the parts that do things.

We are not going to teach the Kivy language in this course, but it is not too difficult if you simply want to understand what is going on. You start with the name of a Kivy class in angle brackets (all of these classes are a subclass of kivy.uix.widget.Widget, which is used to draw something). Underneath you indent pairs of the form

  attribute_name: attribute_value

In addition, you will notice that sometimes a class is indented inside another class in imager.kv. This means that it will draw that object inside of the other. This how you align objects on the screen. For example, consider the following lines from imager.kv:

  BoxLayout:
      orientation: 'vertical'
      size_hint_x: .5

      Button:
          text: 'Restore'
          on_release: root.do(root.image_processor.restore)

      Button:
          text: 'Invert'
          on_release: root.do(root.image_processor.invert)

This means that we create a BoxLayout object which has attribute orientation (we ignore attribute size_hint_x for now). Since the value of this attribute is 'vertical', everything drawn inside this object is arranged vertically. The Button objects are all indented underneath, so they are drawn inside (and hence arranged vertically).

You will also notice in the example above that each Button object has an attribute on_release with a method call following it. This is how we hook up the imager.kv file with our Python code. These are the handlers that specify what happens when you press a button.

The Class Main

The class Main creates all of the other objects, including the ImageProcessor object. It also implements some functionality that is not strictly image manipulation, such as file I/O and calling display to redraw the screen.

You will notice several other classes in both imager.py and imager.kv. These minor classes define things like pop-up windows to load and save files. In each case, the view is specified in imager.kv while the controller is specified in imager.py. A few of these controller classes are essentially empty; that is because we are inheriting the controller functionality from some base class, and we just needed to subclass it to make sure that the controller and view had the same name.

The Class ImageProcessor

This class provides all the methods for manipulating the image given to it as an ImageArray in the constructor. The constructor stores the image in the (immutable) property original and stores a copy of it in the (mutable) property current.

As the image is manipulated, the object in current changes. It can be restored to its original state by copying the property original to current. That is what the procedure restore does. Note that restore actually creates a new object; it is not sufficient to just assign original to current. If we did that, both would point to the same object, so that whenever current changes, original would change also. It is necessary to make a "deep" copy.

Other methods in this class implement the various handlers for the buttons. When a button is clicked, the application calls the appropriate handler. The procedures invert, horizReflect, transpose, and restore are provided for you. The procedure invert retrieves each pixel, computes its color complement, and places the new pixel back into current.

Your goal in this assignment is to implement the procedures corresponding to the other buttons.

Assignment Instructions

The hardest part of this assignment is simply understanding how all of the classes fit together. However, the only class that you need to modify is ImageProcessor. Looking at this class, you will see that several methods are already complete, while others are just stubs. For this assignment, you need to implement the following six methods:

• vertReflect
• jail
• monochromify
• vignette
• blur
• bilateral

While working on these methods, you may find that you occasionally want to introduce new helper methods. This is fine, and is actually expected for some of the tasks below. However, you must write a complete and thorough specification of any helper method you introduce. It is best to write the specification before you write the method body, because it helps you as you write the program. This is standard practice in this course. It is a severe error not to do so, and points will be deducted for missing or inappropriate specifications.

You need not write loop invariants, and if you do, we will not grade them. But we encourage you to write them for each loop so that you get used to thinking in terms of the invariant. Look at the implemented methods in ImageProcessor to see what a loop invariant might look like.

Testing Guidelines

Before you write any code, you should be aware of our guidelines for testing. Using Python unit tests is difficult because it is not easy to access a picture. You do not have to use one. But this means you will need other creative ways of testing and debugging your code, such as print statements. If you add print statements to your code, please remember to remove them before submitting. We will deduct points if you do not remove them.

Task 1. vertReflect

This method should reflect the image about a horizontal line through the middle of the image. Look at the method horizReflect for inspiration, since it does something similar. This should be relatively straightforward. Remember that loop invariants are not required, and will not be graded. However, we will give you some feedback on them if you provide them.

Once you have implemented this method, you will notice that both the Vertical Reflect and Rotate Left buttons now work. That is because the method rotateLeft uses vertReflect as a helper. This demonstrates an a clever way to rotate an image.

Task 2. jail

This method is called when the user clicks the "Put in Jail" button. You can see the effect in the picture to the right. This method draws a red boundary and vertical bars. This will happen when you implement the method according to its specification, given as a comment in the method. Be sure to follow that specification carefully.

We have given you helper method _drawHBar to draw a horizontal bar (note that we have hidden it by naming it with a leading underscore; helper functions do not need to be visible to other modules or classes). In the same way, implement a helper method _drawVBar to draw a vertical bar. Do not forget to include its specification in your code.

This is a problem where you have to be very careful with rounding, to make sure that the bars are evenly spaced. You need to be aware of your types at all times. The number of bars should be an integer, not a float (you cannot have part of a bar). However, the distance between bars should be a float. That means your column position of each bar will be a float. Wait to turn this column position into an int (by rounding and casting) until you are ready to draw the bar.

When finished, open a picture, click the buttons Put in Jail, Transpose, Put in Jail, and Transpose again for a nice effect.

Task 3. monochromify

In this method, you will change the image from color to either grayscale or sepia. The choice depends on the value of the integer parameter color, which is either 0 to indicate grayscale or 1 to indicate sepia. However, do not use integer constants 0 and 1. Instead use the names GRAY and SEPIA, which are already defined in image_processor.py to be 0 and 1, respectively. There are a couple of good reasons for this. First, using mnemonic names rather than the actual values makes the program more readable, because the names indicate the intended meaning. Second, if you ever decide to change the representation in the future (say to 3 and 4), you can do so in one place without having to go through the whole program searching for (the right) occurrences of 0 and 1.

To implement this method, you should first calculate the overall brightness of each pixel using a combination of the original red, green, and blue values. The brightness is defined by:

brightness = 0.3 * red + 0.6 * green + 0.1 * blue

Sepia toning was a process used to increase the longevity of photographic prints. To simulate a sepia-toned photograph, darken the green channel to int(0.6 * brightness) and blue channel to int(0.4 * brightness), producing a reddish-brown tone. As a handy quick test, white pixels stay white for grayscale, and black pixels stay black for both grayscale and sepia tone.

To implement this method, get the color value for each pixel, recompute a new color value, and set the pixel to that color. Look at procedure invert as well as the discussion on tuples to see how this is done.

Task 4. vignette

Camera lenses from the early days of photography often blocked some of the light focused at the edges of a photograph, producing a darkening toward the corners. This effect is known as vignetting, a distinctive feature of old photographs. You can simulate this effect using a simple formula. Pixel values in red, green, and blue are separately multiplied by the value

1 - d2/h2

Like monochromification, this requires unpacking each pixel, modifying the RGB values, and repacking them (making sure that the values are ints when you do so). However, for this operation you will also need to know the row and column of the pixel you are processing, so that you can compute its distance from the center of the image.

For this reason, we highly recommend that you use the methods get_pixel and set_pixel in the class ImageArray, which treat the array as a 2-dimensional list, rather than get_flat_pixel and set_flat_pixel, which treat it like a 1-dimensional list. A flat list was fine for invert and monochromify, but that was because the row and column did not matter in those methods.

Task 5. Blurring, two flavors

The last part of the assignment is the most involved. A very common operation on images is blurring: to reduce noise, to simulate an out-of-focus background, or to reduce distracting detail in an unimportant part of an image. In this assignment you implement two kinds of blur: a simple blur that removes detail everywhere and a fancier (though still simple) blur known as bilateral filtering that is designed to remove fine details without blurring important features.

Simple blur

This method works like the blur tool in Photoshop. This method replaces each pixel of the current image by the average of itself and its eight neighbors (see figure at right). The averages must be taken separately for each color component. Thus an interior pixel's red component will be replaced by the average of the red components of that pixel and its eight neighbors, and similarly for the blue and green components. To simplify things, for this assignment do not worry about the pixels in the first and last column and row, which don't have a full complement of eight neighboring pixels; just leave them alone.

As in transpose, the method will have two nested loops, and each iteration of the inner loop will process one pixel. Do not write all the code to process a pixel in the inner loop. Instead, write a helper method that processes one pixel, and call this from the body of the inner loop. This is done to keep each method simple and short. Also, you can initially stub in the helper method (e.g. have it set the pixel to carnelian, (179, 27, 27)) to facilitate constructing and testing one part of your code at a time.

Even if you do it correctly, this method is slow. Our solution takes 3-4 seconds on each of the sample images. Keep this in mind if you choose to implement when you run this method.

Bilateral filter

Once you have the basic blur working, the bilateral filter is a small tweak to the same code. The goal is to smooth out detail without blurring strong edges, and the idea is simple: avoid averaging together pixels with very different values. The blur proceeds exactly as a basic blur, except that a neighboring pixel is excluded from the average if the difference between its pixel value and the center pixel's value exceeds some threshold. (The name bilateral comes from the idea of selecting pixels to average according to two criteria: they have to be close in position, and they have to be close in value.)

In order to decide which pixels to include, we need to have a way to measure difference between two RGB pixels using a single number. In this assignment we use the maximum difference across all three channels: that is, the largest of the difference in red value, difference in green value, and difference in blue value. The differences are measured in absolute value; for instance the red difference is abs[(red of center pixel) − (red of neighbor pixel)].

Don't forget to count how many pixels you add up in your average, so that you can divide by that number when you compute the average pixel value.

Bilateral filtering is used for many things in digital photography; for one, it is used to remove noise from grainy images without making them look blurry. Too much of this makes images look odd—or artistic, depending on your view. Play with your implementation a little, seeing what effect the threshold has (you change the threshold using the text box next to the Bilateral button in the Imager window) and what happens when you apply the filter repeatedly. Note that very low thresholds (for instance, 0) exclude all pixels that are at all different from the center pixel, resulting in an unchanged image, and very high thresholds (e.g. 255) don't exclude any pixels, which reduces to computing the basic blur. A moderate threshold with repeated application produces an almost painted look.

Finishing the Assignment

Once you have everything working you should go back and make sure that your program meets the class coding conventions. In particular, you should check that the following are all true:

1. There are no tabs in the file, only spaces
2. Classes are separated from each other by two blank lines.
3. Methods are separated from each other by a single blank line.
4. Lines are short enough that horizontal scrolling is not necessary (about 80 chars is long enough).
5. The specifications for all of the methods and properties are complete.
6. Specifications are immediately after the method header and indented.

Finally, at the top of image_processor.py you should have three single line comments with (1) the module name, (2) your name(s) and netid(s), and (3) the date you finished the assignment. We have been taking off points for people that keep forgetting to do this.

Turning it In

Upload the file image_processor.py to CMS by the due date: Saturday, April 13th at 11:59 pm. Do not submit any files with the extension/suffix .pyc . It will help to set the preferences in your operating system so that extensions always appear.