Instagram claims that it is a site for sharing photos online with friends. But it became popular for its easy to use photo editing tools and image filters. In this assignment, you will learn how to make your own image filters. While they may not be as fancy as the ones provided by Instagram, this assignment will still teach the basic principles involved.
As we have seen in class, an image is just a 2-dimensional list of pixels (which are themselves RGB objects). So most of the functions/methods that you write in this assignment will involve nested for-loops that read a pixel at a certain position and modify it. You will need to use what you have learned about multi-dimensional lists to help you with this assignment.
One major complication is that graphics cards prefer to represent images as a 1-dimensional list in a flattened presentation instead. It is much easier for hardware to process an 1-dimensional list than a 2-dimensional one. However, flattened presentation (which we explain below) can be really confusing to beginners. Therefore, another part of this assignment is learning to use classes to abstract a list of pixels, and present it in an easy-to-use package.
Finally, this assignment will introduce you to a Python package. This application is a much more complex GUI than the one that you used in Assignment 3. While you are still working on a relatively small section of the code, there are a lot of files that go into making this application work. Packages are how Python groups together a large number of modules into a single application.
Important: This is longer than previous assignments. To reduce stress, we highly recommend that you follow the recommended micro-deadlines.
Authors: W. White, D. Gries, and D. Kozen
Learning Objectives
This assignment is designed to give you practice with the following skills:
- How to implement a class from its interface.
- How to enforce class invariants.
- How to use a classes to provide abstractions.
- How to write code for both 1-dimensional and 2-dimensional lists.
- How to manipulate images at the pixel level.
- How to write code for an underspecified function or method.
- How to program for unicode strings with foreign characters and emojis.
Table of Contents
Academic Integrity and Collaboration
This assignment is similar to one that we have given occasionally in the past, though it is heavily modified from previous years. Once again we still ask that you do not consult or seek out earlier versions of this assignment. Refering to a previous solution of this assignment without citing it is a violation of CS1110’s academic integrity policy.
We also ask that you do not enable violations of academic policy. Do not post your code to Pastebin, GitHub, or any other publicly accessible site.
Collaboration Policy
You may do this assignment with one other person. If you are going to work together, 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, we ask that you do not look at anyone else’s code or show your code to anyone else (except a CS1110 staff member) in any form whatsoever. This includes posting your code on Ed Discussions to ask for help. It is okay to post error messages online, but not code. If we need to see your code, we will ask for it.
Assignment Help
This assignment is a significant jump in difficulty from the previous programming assignment. Waiting to do this assignment until the last minute (or even the last week) is guaranteed to fail. We suggest that you start this assignment early, and that you go to office hours on the first sign of difficulty.
Assignment Overview
This assignment requires you to implement several parts before you have the whole application working. The key to finishing is to pace yourself, and make use of both the unit tests and the visualizer that we provide.
Assignment Source Code
To work on this assignment, you will need to download three files.
- imager.zip: The application package, with all the source code
- samples.zip: Several sample images to test in the application
- outputs.zip: The result of applying the filters to the sample images
You should download the zip archive imager.zip from the link above. Unzip it
and put the contents in a new directory. This time, you will see that this
folder contains a lot of files. You do not not need to understand most of these
files. The are similar to a3app.py in that they provide the GUI interface
for the application.
You only need to pay attention to the files that start with a6. There are
four of these. Two are completed and two are only stubs, waiting for you to
complete them.
- a6image.py: The
Imageclass, to be completed in Task 1 - a6canvas.py: The
Canvasclass, which is completed already - a6filter.py: The
Filterclass, to be completed in Task 2 - a6encode.py: The
Encodeclass, to be completed in Task 3 - a6test.py: The test script for the assignment, which is mostly complete
You should skim all of these files before continuing with the assignment instructions.
Suggested Micro-Deadlines
The material covered in this assignment is a major part of the second prelim. Therefore, it is important that you complete this assignment well before the second prelim, in order to give you time to study for that exam. That is why, at the end of each part of the assignment, we have a suggested completion date. Following these dates will guarantee you have enough time to study for the exam.
While these deadlines are not enforced, we recommend that you try to hit them. If you cannot make these deadlines, it might be a sign that you are having difficulty and need some extra help. In that case, you should go to office hours page as soon as possible.
Looking at the dates, this may seem like a lot of work. But the deadlines are chosen so that days work should end up being an hour-or-so of work on average. This is much like the expectation of a single lab. By spreading it out this way, it makes the assignment a lot less daunting, especially as you get to the final tasks which are a lot more work. Our expectation is that this assignment will take up to 15 hours on average.
The Imager Application
Because there are so many files involved, this application is handled a little
differently from previous assignments. To use this application, keep all of the
files inside of the folder imager. Do not rename this folder. To run the
program, change the directory in your command shell to just outside of the
folder imager and type
python imagerIn this case, Python will run the entire folder. What this really means is
that it runs the script in __main__.py. This script imports each of the other
modules in this folder to create a complex application.
Right now, this application will not do anything. However, once you
complete the Image class, it will display two
images of your instructor, like this:

As you work with this application, the left image will not change; it is the original image. The right image will change as you click buttons. The actions for the buttons Invert and Rotate.., are already implemented. Click on them to see what they do.
You will notice that this takes a bit of time (your instructor’s computer takes 2-3 seconds for most operations). The default image is 512x512. This is over 250 thousand pixels. The larger the image, the slower it will be. With that said, if you ever find this taking more than 30 seconds, your program is likely stuck and has a bug in it.
The effects of the buttons are cumulative. You can undo the last effect applied
with Image.. Undo. To remove all of the effects, choose
Image.. Clear. This will revert the right image to its original state.
You can load a new image at any time using the Image.. Load button. Alternatively, you can start up with a new image by typing
python imager myimage.pngwhere myimage.png is your image file. The program can handle PNG, JPEG, and
GIF (not animated) files. You also can save the image on the right at any time
by choosing Image.. Save. You can only save as a PNG file.
The remaining buttons of the application are not implemented. Reflect.. Horizontal works but the vertical choice does not. In Part 2 of the assignment, you will write the code to make them work.
If you are curious about how this application works, most of the code is in
interface.py and interface.kv. The file interface.kv arranges the
buttons and colors them. The module interface.py contains Python code that
tells what the buttons do. However, the code in this module is quite advanced
and we do not expect you to understand any of it.
The Encoder Features
Next to the Image.. button, you will see a button for Text... This button is used by the last part of the assignment, to store secret messages in text. To access these features, choose Text.. Show.
When you do this for the first time, you will see an error message that says “No hidden message found”. This is perfectly normal. You have not encoded anything yet, so there is nothing to decode. As a rule, the application will always decode the message hidden in the file at start-up, and you will see that error if there is no message.

To encode a message (once you have completed Part 3), type text in the box on the right. The box will change color to blue if you have unsaved changes. Once you press the Encode button, it will write the message inside the image and change color back. At this point, you will probably want to save the image to a PNG file to decode later. Applying any of the image filters (invert, reflect, etc.) will corrupt the hidden message and cause it to be lost.

Typing text in the box is a lot of work. Therefore, you can always read from a text file (or even a .py file). If you chose Text.. Import, this will load the file into the box on the right. However, it will not encode the text until you chose to do so. Hence, the text box will be blue after the file is loaded. Similarly, you can save the decoded text to a file with Text.. Export. These file features will be very useful for debugging more complex messages.
As we describe in the instructions below, your encode and decode operations will support full Unicode (Asian characters, emojis, etc.). However the font that Kivy uses cannot support emojis; it will display them as boxes with a cross in them (to indicate “missing”). For example, if you import this text into the application, you will see this

But if you export that text to a file, and open it up with an editor that can display emojis, it will look correct. If you want to encode emojis, write them in a text editor, import them, and encode. To get emojis back from a message, you decode and export.
The undo functionality works for all of these features as well. Choosing to undo will remove the most recently encoded message, restoring to a previously encoded message.
The Integrated Test Script
As with Turtles, debugging everything visually can be tricky. That is why we have provided you with a (partial) test script to help you with this assignment. This test script is integrated into the Imager application. To run it, type
python imager --testThe application will run test cases (provided in a6test.py) on the classes
Image, Filter, and Encoder, in that order. This is incredibly useful,
since you cannot even use the Imager app until you finish the Image class.
These test cases are designed so that you should be able to test your code in
the order that you implement it. Howevever, if you want to “skip ahead” on a
feature, you are allowed to edit a6test.py to remove a test. Those tests are
simply there for your convenience.
This test script is fairly long, but if you learn to read what this script is doing, you will understand exactly what is going on in this assignment and it will be easier to understand what is going wrong when there is a bug. However, one drawback of this script is that (unlike a grading program), it does not provide a lot of detailed feedback. You are encouraged to sit down with a staff member to talk about this test script in order to understand it better.
As with the Turtles assignment, this test script is not complete. It does
not have full coverage of all the major cases, and it may miss some bugs in
your code. It is just enough to ensure that the GUI application is working
correctly. You may lose points during grading even if you pass all the tests in
this file (our grading program has a lot more tests). Therefore, you may want
to add additional tests as you debug. With that said, we do not want you to
submit the file a6test.py when you are done, even if you made modifications
to the file.
Assignment Instructions
There are so many parts to the Imager application that this assignment can feel very overwhelming. But in these instructions we take you through everything step-by-step. As long as you pay close attention to the specifications, you should be able to complete everything. This assignment may take longer than the others, but it is well within your ability.
Task 0: Pixel Representation
You do not ever need to worry about writing code to load an image from a file.
There are other modules in imager that handle that step for you. Those modules
use the PIL module to extract
pixel data from a file. The functions in this module return the image as a
flattened list of pixels.
To understand what we mean by this, let’s talk about pixels first. A pixel is a single RGB (red-green-blue) value that instructs your computer monitor how to light up that portion of the screen. 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 pixels as an RGB object defined in
the introcs module. These were mutable objects where you could change
each of the color values, and these objects would automatically enforce the
0..255 invariant. However, the pixels in this assignment will be 3-element
tuples of integers. That is because they are faster to process, and Kivy
prefers this format. Because image processing is slow enough already, we have
elected to stick with this format. In addition, this means that you get some
experience checking and enforcing that the pixels are in the correct format.
So if that is what we mean by a pixel, what is a “flattened list of pixels”? We generally think of an image as a rectangular table of pixels, where each pixel has a row and column (indicating its position on the screen). For example, a 3x4 pixel art image would look something like the illustration below. Note that we generally refer to the pixel in the top left corner as the “first” pixel.

However, graphics cards really like images as a one-dimensional list. One-dimensional lists are a lot faster to process and are more natural for custom hardware. So a graphics card will flatten this image into the following one-dimensional list.

If you look at this picture carefully, you will notice that is it is very similar to row-major order introduced in class. Suppose we represented the 3x4 image above as follows:
E00 E01 E02 E03
E10 E11 E12 E13
E20 E21 E22 E23
The value Eij here represents the pixel at row i and column j. If were
were to represent this image as a two-dimensional list in Python, we would write.
[[E00, E01, E02, E03], [E10, E11, E12, E13], [E20, E21, E22, E23]]Flattened representation just removes those inner brackets, so that you are left with the one-dimensional list.
[E00, E01, E02, E03, E10, E11, E12, E13, E20, E21, E22, E23]This is the format that the Image class will use to store the image. If you
do not understand this, you should talk to a staff member
before continuing.
Precondition Enforcement
Throughout this assignment, you will be asked to enforce preconditions. A
common precondition that will come up over and over again is that a value is a
pixel, or a value is a pixel list. Inside of the file a6image.py are two
helper functions to help you enforce these preconditions: _is_pixel and
_is_pixel_list. The first has been completed for you. The second is
unfinished.
Before you do anything else, complete the function _is_pixel_list. Despite
the fact that this is a hidden function, we do test it in a6test.py. So you
should run the test script to verify that your
implementation is correct.
There is one important detail to this function. In this function you need
to check if data is a list. You might think that you do that with this
following code:
if type(data) == list:
do something...However, as we will explain later in class. We no longer want you using the
function type to check the type of a value. Instead you should use the
function isinstance, which works like this:
if isinstance(data,list):
do something...We will explain why you need to do this later. But if you are confused, you can
look at the code for _is_pixel for an example.
Recommended Deadline
This is not a hard function, and it is very similar to some of the nested-loop functions you have seen in class. But you did need to read all of these instructions to get this far. So we recommend that you finish this part by Saturday, October 31. Finishing this part of the assignment will demonstrate that you understand how pixels work and allow you to get started on the assignment.
Task 1. The Image Class
For some applications, flattened representation is just fine. For example, if you want to convert an image to greyscale, you do not need to known exactly where each pixel is inside of the file. You just modify each pixel individually. However, other effects like rotating and reflecting require that you know the position of each pixel. In those cases you would rather have a two-dimensional list.
The Image class has attributes and methods that allow you to treat the image
either as a flattened one-dimensional list or as a two-dimensional list,
depending on your application. This is what we mean by an abstraction.
While the data is not stored in a two-dimensional list, methods like
getPixel(row,col) allows you to pretend that it is.
The file a6image.py contains the class definition for Image. This class is
fully specified. It has a class specification with the class invariants. It
also has specifications for each of the methods. All you have to do is to
write the code to satisfy these specifications.
As you work, you should run the test cases to verify that your code is correct. To get the most use out of the testing program, we recommend that you implement the methods in the same order that we test them.
The Initializer, Getter and Setter Methods
To do anything at all, you have to be able to create an Image object and
access the attributes. This means that you have to complete the initializer
and the getters and setters for the three attributes: data, width and height.
If you read the specifications, you will see that these are all
self-explanatory. Note that these attributes are hidden, so the class invariant
is given by (hidden) single line comments
according to our specification style.
There are getters for the pixel data, pixel length, width, and height. In addition there are setters for the width and height. Because those two values have setters, it is important to enforce the invariants. Note that there is an extra invariant that the following must be true at all times:
width*height == # of pixels
You must ensure this invariant in both the initialiers and the setters. In addition, we expect you to enforce all preconditions with asserts.
Recommended Deadline
Except for the setters for width and height (which have the unusual invariant),
this part is no harder than the Length class in
Lab 19. So you should be
able to do this part quickly. We want you to get in the habit on working on this
assignment a little bit every day. That will make this assignment easier and
less stressful. That is why we recommend that you finish this part by
Sunday, November 1.
The One-Dimensional Operators
The getter getPixels already returns the image data as a flattened list of
pixels. So you might think we do not need to do anything more here. However,
notice that getPixels returns a copy of the pixel list. So it is not
useful if you want to modify the image. Instead, the class Image has
methods to allow modification of the image, while still enforcing the class
invariant.
The methods getFlatPixel and setFlatPixel methods present the image as a
one-dimensional list. They are extremely simple to implement. You should just
do the obvious thing. The primary reason they exist is so we can enforce the
method preconditions (which in-turn enforce the invariants). A simple list does
not care whether its contents are valid pixels. The setter ensures that is the
case.
Recommended Deadline
Again, this is another short bit of code. You should be able to finish this and the next part (Two-Dimensional Methods) by Monday, November 2.
The Two-Dimensional Methods
The getPixel and setPixel methods present the image as a two-dimensional
list. This is a little trickier. You have to figure out how to compute the flat
position from the row and column. Here is a hint: it is a formula that requires
the row, the column, and the width. You do not need anything else. Look at the
illustrations in our discussion of
flattened representation
to see if you can figure out the formula.
Figuring out the conversion formula is the only hard part of this exercise. Otherwise it is the same as for the one-dimensional operators. Make sure to enforce all of the preconditions.
Recommended Deadline
Because this is very similar to the one-dimensional methods, you should try to finish this by the same day: Monday, November 2. This pace will put you in good shape for the more complicated functions in Task 2.
The __str__ Method
This method is arguably the hardest one in the entire Image class. We want
you to create a string that represents the pixels in two-dimensional row-major
order. As a hint, this is a classic for-loop problem. You will need an
accumulator to store the string, and you will build it up via concatenation.
You will also want to use previous methods that you wrote as helpers.
You might think that all you need to do is to accumulate the pixels into a two-dimensional list and convert that list to a string. This would be correct except for the newlines between rows. You need to be a little more clever here. Again, use the the test script to verify that your code is correct.
Recommended Deadline
Because this method is harder than the previous ones, you may need to spend a day or so on this method, and this method alone. If you have followed the deadlines so far, you have probably been going non-stop, so we will allow you a bit of a break here (which you should use to work on Assignment 5). Ideally, you should finish this method by Wednesday, November 4.
If you get stuck on this method, you can skip it and come back to it later. The primary purpose of this method is to help you with debugging (so you can examine the contents of an image) in Task 2. But it is not required for any other part of the assignment, so you can skip ahead if you are having difficulty.
The Remaining Methods
You will notice that there are two other methods in class Image: swapPixel
and copy. We need these methods for the filtering application, and in the
previous years we had you implement these methods. However, to cut down on
some of the work that you have to do (and get you to the interesting part of
this assignment), we have completed them for you.
Task 2. The Filter Class
The module a6filter.py contains the Filter class. You will notice that it
is a subclass of the Canvas class in a6canvas.py. The Canvas class is
complete; you do not have to do anything with this class. It implements the
Undo functionality in the imager application. This class implements an
edit history and the getter getCurrent accesses the most recent update of the
image.
You do not need to understand the Canvas class at all, but you should read its
specification. Since Filter is a subclass, it will need to access the
inherited methods from Canvas. In particular, you will notice that none of
the methods in Filter take an image as an input. Instead, those methods are
to work on the current image, which they access with the method getCurrent.
To make it easier to follow all this, we have provided you with several example
methods to study. You will notice that some filters – like invert – modify
the image with the one-dimensional operators. Others – like transpose and
reflectHori – modify the image with the two-dimensional operators. Use this
code as a guide for implementing the unfinished methods.
While working on these methods, you may find that you want to introduce new
helper methods. For example,jail already has a _drawHBar helper provided.
You may find that you want a _drawVBar method as well. This is fine and is
actually expected. 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, which is standard practice in
this course. It is a severe error not to have a specification, and points
will be deducted for missing or inappropriate specifications.
We have provided you with several test cases for these filters. But the output of these test cases are limited and not always useful. A better way to test is just to load the sample images and try them out. We have provided you with the correct outputs for each filter applied to each sample image.
Method posterize
In the case of images, posterization means to drop the bit-depth of an image. The bit-depth is not the same as the resolution. The resolution is the number of pixels in the image. The bit-depth is the color variety. 32-bit color (which is what modern computers support), provides access to 1.6 million of colors. On the other hand, classic 8-bit color only supports 256 colors.
When you drop the bit-depth of an image, similar colors start to blend together, giving a “washed out effect”. For example, the image on the right is your instructor in 8-bit color.

A single bit means that you are limited to chosing two different color values. So 1-bit color means a black-or-white image. 2-bit color means you get four different color values. 3-bit color means you get eight different colors. And 8-bit color gives you 256 colors.
When we translate modern color to 8-bit color, we give 3-bits to red and green, and 2-bits to blue. We do that with the following formulas. First,
c = (c // 32) * 32is used to compute the new red or green values. This guarantees one of eight evenly spaced color values. On the other hand, for blue we use the formula
b = (b // 64) * 64This guarantees one of four evenly spaced color values. Note that unlike Assignment 3, these formulas do not require you to convert the colors to the range 0..1.
The method posterize converts an image to 8-bit color. To implement this
method, you should get the color value for each pixel, recompute a new color
value, and set the pixel to that color. This is best done by treating the image
as a one-dimensional list. Look at the method invertto see how this is done.
Recommended Deadline
This method is intended to be a warm-up and a confidence booster. You should be able to complete it and the next function in a single day. However, we also want to give you time to work on Assignment 5. That is why we suggest that you complete this part by Friday, November 6.
Method reflectVert
This method should reflect the image about a horizontal line through the middle
of the image. Look at the method reflectHori for inspiration, since it does
something similar. While this is another fairly straight-forward method, this
time you will need to use the two-dimensional list methods. That is because
this time the position of the pixel matters.
Recommended Deadline
This is another simple method, and so you should be able to finish it the same
day that you finish posterize. That means that we suggest that you complete
this part by
Friday, November 6
if you have been following along with our deadlines.
Method jail
Now that you have implemented the simple filters, it is time to work on some
that require real work. Always a crowd favorite, the jail method draws a red
boundary and vertical bars on the image. You can see the result in the picture
below. The specification is very clear about how many bars to create and how to
space them. Follow this specification clearly when implementing the function.

We have given you helper method _drawHBar to draw a horizontal bar (note that
we have hidden it; helper functions do not need to be visible to other modules
or classes). In the same way, you should implement a helper method _drawVBar
to draw a vertical bar. Do not forget to include its specification in your
code.
This method is one where you have to be very careful with round-off error, 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) until you are ready to draw the bar.
When you are finished with this method, open a picture and click the buttons Jail, Transpose, Jail, and Transpose again (in that order) for a nice effect.
Recommended Deadline
This method is a little more complicated than the previous filters, but it is still not that bad. The hardest part of this method is making sure that you are handling the round-off error correctly. So you can catch up after having worked on Assignment 5, we recommend that you finish this part by Sunday, November 8.
Method 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
where d is the distance from the pixel to the center of the image and h is
the distance from the center to any one of the corners. The effect is shown
below.

Like monochromify, this method requires unpacking each pixel, modifying the
RGB values,and repacking them. You should remember to convert back to int
before repacking, them rounding the values (do not truncate).
Unlike monochromify this operation also requires that you 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 two-dimensional methods for this method. The one-dimensionel methods
were fine for invert, posterize, and monochromify because the row and
column did not matter in those methods.
Recommended Deadline
This is a much harder method than the previous methods, and it may take you more than a day to complete it. But we also want to give you enough time to complete this assignment and study for the exam. Therefore, we recommend that you finish this method by Tuesday, November 10 That gives you five full days to work on the last part, and seven days to study for the exam.
Task 3. The Encoder Class
The last official part of the assignment is the most involved. The Encoder
class is built on top of the Filter class. That is because it is adding new
functionality to the Filter class and it needs access to the current image
via getCurrent. In fact we could have combined these two classes, but we
separated them for reasons of readability.
This class allows us to support steganography, which is “the art and science of writing hidden messages in such a way that no one apart from the intended recipient even realizes there is a hidden message.” This is different from cryptography, where the existence of the message is not disguised but the content is obscured. Quite often, steganography deals with messages hidden in pictures.
This task is much more open-ended than anything we have done in the course
before. There is no right way to hide a message, and the way that you choose to
hide messages might be different than ours. All that matters is your decode
method can extract messages hidden by your encode method.
Because this assignment is so open-ended we do not have any recommended deadlines for any of the individual methods. But if you have followed the deadlines so far, you should have five days left to work on this part of the assignment, which is more than enough time to complete it.
To decide how to best hide (and reveal) messages, you should read all of the instructions below before starting on this class.
Encoding Bytes
A byte is an integer between 0 and 255 (this should look very familiar by now).
Computers are specifically designed to work with data in byte-sized chunks, which
is why they are so common. The American Standard Code for Information Interchange
(ASCII) is a way to represent Python strings
as bytes. Each character corresponds to a number 0..255. As you saw in an
early lab, you can use the function ord to convert a character to a byte
and chr to convert a byte back to a character.
It is very easy to encode a byte in a pixel. Suppose we have a pixel whose RGB
values are 199, 222, and 142 and we want to store the byte 107 (which
corresponds to the character 'k').
We change the least significant digit of each color component to one of the
digits of 107, as shown below.
| Original Pixel | Pixel with byte 107 hidden | |||||
|---|---|---|---|---|---|---|
| Red | Green | Blue | hide byte 107 | Red | Green | Blue |
| 199 | 222 | 142 | → | 191 | 220 | 147 |
This change in each pixel is so slight that it is imperceptible to the human eye (unless the image is a rectangle of just one color).
Decoding the message, the reverse process, requires extracting the last digit of
each color component of the pixel and forming a byte from the three extracted
digits, then converting that byte back to a character. In the above example, we
would extract the digits 1, 0, and 7 from the RBG components of the pixel (using
% 10) and put them together to form
107, which is the ASCII value for 'k'.
Extracting the message does not change the image. The message stays in the
image forever.
Unfortunately, all modern text is Unicode, not ASCII. Unicode supports all possible characters, including Asian characters and emojis. And Unicode strings are supported in Python. Try this out in the interactive shell:
>>> s = '😀 World!'
>>> s[0]
'😀'To keep the international students from feeling left out, we will be using Unicode instead of ASCII.
Unicode characters are not represented by bytes. Emojis require much larger
integers than 255. But the UTF-8
encoding is a simple way to convert an unicode string into a list of bytes.
All strings have an encode method that allows you to do this conversion.
Take the string s above and try the following:
>>> b = s.encode('utf-8')
>>> list(b)
[240, 159, 152, 128, 32, 87, 111, 114, 108, 100, 33]You will note that the number of bytes is longer than the length of the string. In UTF-8, all ASCII characters are a single byte, but other characters can be anywhere from one to four bytes.
You can also convert a list of byte-size integers back into a unicode string.
You need to use the Python bytes function to covert the list into a bytes-only
sequence, and then use the decode method as follows:
>>> c = bytes([240, 159, 152, 128, 32, 87, 111, 114, 108, 100, 33])
>>> c.decode('utf-8')
'😀 World!'With this information, you can now use the technique shown above to hide or reveal any Unicode string.
Designing an Encoding
You are to write code to hide characters of a message text in the pixels of
an image in flattened representation, starting with pixel 0, 1, 2, … Before
you write any code at all, you need to think about the following three issues
and solve them.
1. Indicating an Encoding
First, you need some way to recognize that the image actually contains a message. You need to hide data in the initial pixels 0, 1, 2, … that has little chance of appearing in a real image. That way, when program detects the data in those first few pixels, it knows there is a message there. You cannot be complete sure that an image without a message does still contain that data, but the chances should be extremely small.
This beginning marker should be at least two pixels. If it is only one pixel, then we can corrupt your message by transposing the image (think about this). You can use more than two pixels, but the specification states that no more than 10 pixels may be used for encoding information other than the message text.
2. Indicating the Message Length
Next, you have to know where the message ends. You can do this in several ways. You can hide the length of the message in the first pixels in some way (how many pixels can that take?). You can also hide some unused marker at the end of the message. Or you can use some other scheme. You may assume that the message has fewer than one million bytes (e.g. the specification says that you can refuse to encode longer strings), but you must be prepared for a message with any sequence of bytes, including those produced by punctuation, emojis, and foreign characters.
3. Staying within Color Bounds
Finally, the largest value of a color component (e.g. blue) is 255. Suppose the
blue component is 252 and you want to hide 107 in this pixel. In this case, the
blue component would be changed to 257. But this impossible because a color
component can be at most 255. Think about this problem and come up with some
way to solve it. There is a way to do this without having to change the
_decode_pixel helper that we have provided for you. However, you are allowed
to change _decode_pixel if you figure out another way to do it.
As you can see, this part of the assignment is less defined than the previous
ones. You get to come up with the solutions to some problems yourself. You
should feel free to discuss this part of the problem with the course staff.
They will not tell you how to solve these problems, but they will discuss your
ideas with you and point out any problems.
Complete the Methods encode and decode
You should complete the body of the methods encode and decode in the class
Encoder. These two methods should hide a message and reveal the message in
the image. When you design decode, make sure it attempts to extract the
message only if its presence is detected.
Feel free to introduce other helper methods as needed. For example, we have
provided a helper method called _decode_pixel, which takes a pixel position
pos and extracts a 3-digit number from it, using the encoding that we
suggested above. This suggests that you might want to create a helper method
called _encode_pixel, which encodes a number into a pixel. The exact
specification of such a helper is up to you (if you start with our
specification, be sure to modify it as appropriate for your code).
Note that the answers to the three problems above greatly influence how you
write all of these methods. Therefore, the the specifications of these methods
must include any description of how you solved the three problems listed above.
For example, the specification of _encode_pixel must describe how you handle
the pixel overflow problem. In some case this may require modification of
specifications written by us. You can change anything you want in the
specification except the one line summary, the preconditions, and the last
paragraph (the one that describes the only cases in which the method may fail).
As an aside, you will also notice that we use the operator getFlatPixel in
_decode_pixel. That is because it is very natural to think of an image as
one-dimensional list when encoding text. While an image is 2-dimensional
arrangment of values, text is not. So the one-dimensional access methods are
the correct things use for this part.
Test the Methods encode and decode
We have provided some simple tests (including emoji) for these methods in
a6test.py. So you should run the provided
test script to check your answers. However, the
test script is not very useful when you have bugs and need to find them.
Debugging encode and decode can be difficult. Do not assume that you can
debug simply by calling encode and then decode to see whether the message
comes out correctly. Instead, write and debug encode fully before going on to
debug decode.
How can you debug encode without decode? Start with short messages to hide
(up to three ASCII characters, each a single byte). Use the method getPixels()
in Image and slice off that many pixels from the list. Print these out
and verify that they are what you expect.
When encode and decode are both done, try hiding and revealing a long message
(e.g. 1000, 2000, or 5000 characters). This is where you really make use of the
Imager application. Use the Text.. Import
feature to load in a text file and try to encode that. We highly recommend that
you try to encode a Python program, as that is a good test of punctuation
characters. International students are free to try to use foreign characters
(though they will not display properly in the Kivy application).
Save your messages
Clicking Image.. Save saves the image in the specified directory with the
filename you enter. The message is saved in .png format, which is a lossless
format. Saving in .jpg format would not work, because doing so tries to
compress the image, which would result in less space but would also clobber
your hidden message.
With .png, you can hide a message, save, quit, and then restart the
application with the message still there. If the message contained emojis or
foreign characters, they will not display in the Imager application, but you
can still export the result to a file with Text.. Export. You should
try to do that.
Finishing Touches
Before you submit this assignment, you should be sure that everything is working and polished. Unlike the first assignment, you only get one submission for this assignment. If you make a mistake, you will not get an opportunity to correct it. With that said, you may submit multiple times before the due date. We will grade the most recent version submitted.
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:
- You have indented with spaces, not tabs (Pulsar handles this automatically).
- Functions are each separated by two blank lines.
- Methods are each separated by one blank line.
- Lines are short enough (~80 characters) that horizontal scrolling is not necessary.
- Docstrings are only used for specifications, not general comments.
- Specifications for any new methods are complete and are docstrings.
- Specifications are immediately after the method header and indented.
- Your name(s) and netid(s) are in the comments at the top of the modules.
You will submit only three files for this assignment: a6image.py, a6filter.py,
and a6encode.py. Upload these files to CMS by the due date:
Sunday, November 15. We do not need any
other files. In particular, we do not want the file a6test.py.
Completing the Survey
As always, this assignment comes with a survey. More than any other assignment this year, we are particularly interested in the results of this survey. Please keep track of the hours that you spent on this assignment. While this has a lot of changes from previous versions of this assignment, we believe that it should take on average 15 hours. We are curious if that number has changed.
Please try to complete the survey within a day of turning in this assignment. Remember that participation in surveys is 1% of your final grade.