PA 6 - Images
In this programming assignment, you will be working with images. You will implement key parts
of an image processing library, which serves to abstract out the low-level details of manipulating
pixels and images. As an extra credit problem, you can then use this library to implement a full
application: green screen substitution. Besides giving you some exposure to images, this
assignment focuses on more advanced data structures, specifically providing practice with
structs and dynamic memory.
Summary
The graphics we have been using throughout this course (such as karel) was built upon open
source graphics libraries (called SDL and STB). For this assignment, we will be leveraging
these same libraries and our own image processing library as an abstraction on top of it. The
extra credit problem illustrates how you could then use this abstraction to efficiently implement
something like green screen substitution.
The starter code for this PA consists of a lot of pre-built code for you to look at and learn from,
including the graphics libraries. Do not feel overwhelmed by this; the code organization is
detailed in General Instructions and you only need to work with very few of the files. The others
are mainly included for your interest.
This assignment only takes about half the time of a normal assignment. You will be asked to
implement the following functions:
To submit the work, please follow the Submission Instructions.
Image create_blank_image(int width, int height) 10 pt
void free_image(Image image) 10 pt
void set_pixel(Image image, int x, int y, Pixel new_pixel) 15 pt
Pixel get_pixel(Image image, int x, int y) 15 pt
void greenscreen(Image* imagePtr, Image small_image) (Extra credit) 15 pt
General Instructions
Setup and Goals
In this assignment, you will look at how images can be represented and manipulated. At the
most fundamental level, images are simply a collection of bits. However, when we want to write
programs that manipulate images, we would like to be able to think about them in a more
convenient way. Rather than saying “change these bits”, we would like to do something like
“change the color of the pixel at coordinate (5,9) to green”.
To achieve this, we need a library of functions that allows us to hide the underlying low-level
details. It should instead provide a convenient interface so we can think about the problem at a
high level of abstraction (pixels and colors rather than bits).
For this programming assignment, you will write the main parts of such a library to work
with images and then use it to implement actual image processing. Make sure you login to the
servers using a method that can show graphical output (i.e., not pure ssh).
Starter Code
To get the starter code for this assignment, execute the following command In your home
directory:
$ getStarter PA6
This will create a new subdirectory, called “PA6”. The different files you find in there are
discussed in the next section.
Code Structure
You will find quite a few files in the startercode. Don’t worry. Most of them you don’t have to
modify. They are there as examples for you to look through and to give you a feel for a larger
software project. In fact, we gave you access to all the code this time, and you could now write a
complete graphical program (like karel) from scratch if you wanted to.
The files are organized as shown in the diagram on the next page. Only the draw.c has a main()
inside, and when compiled together with the appropriate helper files (the ones with a yellow
background), it will yield an executable. You are encouraged to create additional files with a
main() to test your code; the Makefile supports this. However, it is important to note that the
files in yellow should not contain a main(). The files with the red names (manipulate.c and
image_basics.c) are the only ones you need to submit.
Our Image Processing Library
This library provides a number of useful functions to work with images. In this PA, you will be
writing a key part of this library.
image.h: Do not change this file. This is the library header file and needs to be included in any
program that uses our library (such as draw.c). This .h file is important as it defines the data
structures we will be using to represent images: the custom types Image and Pixel. These
will be discussed in detail in Working with Images.
image_basics.c: The code in this file supports basic tasks such as creating a blank image and
setting pixels in an image to a particular color. You will need to implement these functions. The
details are explained in Assignment Details.
image_show.c and image_rw.c: They support displaying images and storing images; they are
already provided for you and don’t need to be modified, but have a look at the code.
framework: This directory contains the files of the supporting graphics libraries. Basically, we
are building our library on top of two existing open source graphics libraries, to provide a more
convenient level of abstraction. If you are interested, this is explained a bit more in Background:
Images in SDL and STB. Those libraries, which are popular in computer game design, are in the
framework folder.
images: This directory contains image files used by our demo programs.
Helper Functions
manipulate.c: For the extra credit part, you are asked to write the image processing function
greenscreen(). It will go in this file. As mentioned before, do not include a main() in this file.
Instead, we can call the function from draw.c or any other test file you may create. To implement
our image processing function, we’ll rely on the image processing library you created in
image_basics.c.
Main C-program
draw.c: This program contains a main(). It is meant to illustrate and test the supporting
functions you created in image_basics.c and manipulate.c. You can modify this file as you
please for testing purposes. We will not ask you to submit it.
Our Debugging Library
The files prototypes.h and prototypes.o are not really part of the main code structure. We have
created them to help you debug and test your code. After you are done implementing your own
code, you won’t need them anymore. If you look in image_basics.c and manipulate.c, you will
notice that the functions you are asked to write are already there, but they call a demo version
of themselves. These demo versions are in prototypes.o, and are basically our solutions. It is
your task to delete the call to the demo code and write your own code instead that implements
the desired functionality.
Compiling Your Code
To compile your code, run the Makefile with the appropriate target (without the .c extension). For
example, to compile draw.c, type:
$ make draw
This will create the executable draw. You can do the same for the other C-program with a
main() that you may wish to create for testing purposes.
Testing Your Code
You will start this PA by writing your own library functions. It is important to test each individual
function thoroughly before moving on to the next one. This divide-and-conquer strategy for
building and verifying your code is an essential part of software design. The library functions
themselves only take a few lines of code, but involve a thorough understanding of the data
structures involved. It is important you struggle through this yourself as much as possible to
solidify your handle on these topics. We have provided you with debugging versions to compare
the behavior of your code against (see Our Debugging Library). You need to write your own
tests. You can do this by modifying draw.c, for example, or by creating your own .c program with
a main() specifically to test your functions.
Since you will be working with dynamic memory, it is advisable to also check that no memory
leaks occur. This is possible with the valgrind tool. The use of valgrind is briefly explained in
Chapter 7. For example, to run it on the executable draw:
$ valgrind ./draw
However, before you do so, you should set the constant SHOW in draw.c to 0 (and recompile).
As a result, the images will not be shown when executing draw (please go through the code in
draw.c and make sure you understand what SHOW does). The reason we have to do this is that
valgrind is not compatible with the image library we are building upon. The output of valgrind will
report any memory leaks.
When writing your own image processing function greenscreen() also make sure to
thoroughly test your code. Again, you can use draw.c as a starting point, but you should expand
it to more test cases (try different image sizes, etc.).
Throughout this PA, do not use global variables.
Working with Images
As mentioned earlier, there is a difference between how we conceptually think about images
and how they are stored internally. Our image processing library is meant to bridge that gap: it
provides an interface that corresponds to how we like to work with images and then translates
that to the actual low-level details under the hood. The low-level details of how to handle images
is done by the SDL and STB graphics libraries we are building on. Basically, they provide a lot
of useful functions for image handling, but they are not intuitive to work with. For example, they
do not store images as 2D objects. The purpose of our library is to enable us to think about
images in a more natural way and provide this as a convenient interface to the user.
We will start with the high-level conceptual view of how engineers typically think and work with
images, and then move to the implementation details of our library.
How We Think about Images
Images are nothing more than a collection of pixels, arranged in a rectangular grid. The
standard labeling convention is shown below. The coordinates are zero-indexed, which means
that the first pixel is at coordinate (0,0). Also, the origin is in the top-left corner, with the y-axis
pointing down. Each pixel is simply a set of RGB values, representing the color of that pixel (see
Background: Representing Colors).
Our Image Representation
It is up to the programmer to choose the data structure they want to use to hold this grid of RGB
values. The choice depends on the specific needs of the program, and often involves a tradeoff
between convenience and memory usage. To store the images in our library, we will be using a
custom data structure that is defined in image.h.
Each pixel in the image is represented by a new type Pixel, which is defined as the struct
shown below. It has the R (red), G (green) and B (blue) values of the pixel as the member fields.
An Image is also defined as a struct. The members width and height contain the dimensions of
the image in number of pixels. For the example in the earlier figure, width is 10 and height 7.
The third member field is a pointer to Pixel and this will be a pointer to dynamic memory.
The pixels member points to a dynamic 1D array of Pixels. The length of this array is the
total number of pixels in Image, so width*height. The pixels of our 2D image are packed into this
array row-wise (row-by-row). For the example below, pixels[0] is the pixel at (x,y)=(0,0), pixels[1]
the pixel at (1,0), pixels[2] the pixel at (2,0), pixels[3] the pixel at (0,1), and so on.
You may wonder why not use a 2D array instead? The reason is that we need a dynamic array
rather than a static one, as we don’t know a priori the dimensions of the image will contain. And
for dynamic memory, it turns out that creating 1D arrays is far easier and less error prone than
creating 2D versions. However, we want to create the illusion that we are working with a 2D
structure, which is much more natural to think about. This is where the library functions you will
be asked to build come in.
typedef struct {
int red;
int green;
int blue;
} Pixel;
typedef struct {
int width;
int height;
Pixel *pixels;
} Image;
Interfacing with Images
The goal of the library functions we are creating in Task 1 - Basic Image Processing Library
Functions is thus to provide a high-level interface to these data structures. With this interface,
image manipulations occur at a high level of abstraction without having to worry about
implementation details (e.g., how pixels are packed in the 1D dynamic array, etc.).
For example, suppose we have the Image called test_image as shown below. We could have
access the pixel at coordinate (0,1) as
However, image processing code would be much easier to write, debug and reason about if we
had a library function get_pixel(image, x, y) that returns the pixel at position (x,y) in an
image:
The benefit is that people can now think about images as 2D grids of pixels at certain
(x,y)-coordinates without having to worry about how they are represented internally.
x = test_image.pixels[3];
x = get_pixel(test_image, 0 , 1);
Assignment Details
Task 1 - Basic Image Processing Library Functions
First, you need to implement a few of the image processing library functions that provide access
to our image data structures (which were described in Interfacing with Images). The main goal is
for you to think through the details of the data structures (structs and dynamic memory
allocation). This is not trivial, as the data structures are reasonably complex. However, these
functions require very few lines of code. The challenge is mainly in understanding how to work
with structs, pointers and dynamic memory. To make your testing easier, we have provided
default implementations (as mentioned in Our Debugging Library).
All of the functions you need to implement here should go in image_basics.c. Your code has to
replace the demo functions calls that are provided.
Create Blank Image
Implement the function below:
Image create_blank_image(int width, int height)
It should create a blank image of a certain width and height. What this means in practice is that
it returns a variable of type Image that has the width and height members set appropriately. It
also needs to allocate the dynamic memory to hold all the Pixel values. When creating this
memory allocation, set all the Pixels to zero .
1
Free the Memory
This function should free the dynamic memory that was allocated with create_blank_image()
above.
void free_image(Image image)
Modify Pixel
This function sets the pixel at coordinate (x,y) to the value new_pixel.
void set_pixel(Image image, int x, int y, Pixel new_pixel)
Note that internally, the pixels of an image are stored in a 1D dynamic array. This function thus
provides the interface from our 2D conceptual view of images to the actual implementation in
specific data structures.
1 Since Pixels are structs, setting them to zero sets all the members of the Pixel struct to zero. This
means that red, green and blue are 0 for each pixel, representing the color black.
Read Pixel
This function does the opposite of set_pixel(). It returns the Pixel value in the image at
coordinate (x,y).
Pixel get_pixel(Image image, int x, int y)
Task 2 - Extra Credit: Green Screen Substitution (Optional)
This task is for extra credit. The goal is to do some interesting processing on an image, using
the functions you developed for the image processing library. Specifically, you need to
implement the following function in manipulate.c:
void greenscreen(Image *imagePtr, Image small_image)
This function does a green screen substitution. The idea is illustrated below. It copies the
non-green pixels of small_image into the top-left corner of the image referred to by
imagePtr. We consider a pixel green when G > 100 and R < 100 and B < 100.
Again, you can run the code in draw.c to see this function in action. Test this on images of
various sizes. Your code will be tested on other images. You may assume that small_image is
always smaller than the base image (so you don’t need to check for this).
Submission Instructions
To submit your assignment, run the following command:
$ submit PA6
This will turn in your files image_basics.c and manipulate.c. We will be testing your functions
with our own main(). Note that these two files cannot contain a main() function themselves.
Background: Representing Colors
Colors can be represented by mixing three
base colors. The way this is done on a
computer is by additive mixing. For example, if
you combine red light and green light, it will
appear as yellow. The image on the right
illustrates this idea. Only three light sources,
red, green and blue, are used to represent
(almost) all colors.
To represent a color on our computer, we only
need to specify the amount of red, green and
blue it contains. These are known as the RGB values. Typically, each of these is a
number between 0 and 255 (i.e., 8 bits). Below are some examples:
If you want to experiment with these
RGB values, most drawing programs
allow you to set them directly. For
example, on the right is a screenshot
from Paint under Windows. Similar
tools exist for iOS as well.
R = 255 G = 255 B = 255 R = 255 G = 255 B = 255
R = 0 G = 255 B = 0 R = 0 G = 0 B = 0
R = 0 G = 0 B = 255 R = 127 G = 127 B = 127
R = 0 G = 0 B = 100 R = 201 G = 237 B = 20
Background: Images in SDL and STB
Open Source Image Libraries
To implement the basic image functionalities, we used open source libraries. Our own library is
essentially a wrapper built on top of those. SDL2 (https://www.libsdl.org/) is a cross-platform
library that transparently wraps OpenGL (on Linux) or DirectX (on Windows). It is popular for
game design, and supports access to sound, interface devices and graphics hardware. Our
karel simulator was built in SDL2. We’re also using stb_image of the STB library
(https://stb.handmade.network/). The needed library are in the framework/ directory of the
starter code.
Why Wrapping these Libraries?
As mentioned earlier, the data structure used to store information does not have to correspond
directly to how we as humans like to think about that information. We saw, for example, how we
could represent our 2D images as a 1D dynamic array. Our library was meant to provide an
interface to make image manipulations convenient and easy to understand.
In principle, we could have decided to build our library functions directly upon the data
representation used by SDL and STB (which will be discussed next). Instead, we created the
Image and Pixel types as they are more intuitive and to give you some practice working with
dynamic memory and structs. But as a result, we also had to convert from the internal data
representation of SDL/STB to our data structures. This is done in image_rw.c and
image_show.c and the code there in turn calls functions you can find in the framework/
subdirectory.
Data Representation
Images are stored in both SDL and STB as dynamic arrays of type uint32_t (integers of 32 bits,
or 4 bytes). As in our Image data type, the pixels are stored in a 1D linear array in a row-wise
order. However, our Image data type has, in addition to the dynamic memory array, two member
fields that contain the dimensions of the image. As a result, we don’t need to store this
information in separate variables.
The type of data in the 1D array is also different, however. In the two open source libraries the
array represents the pixels as uint32_t values, rather than data of type Pixel. These 32-bit
uint32_t values encode the 8-bit R, G and B data for each pixel. There are two ways in which
this encoding is done, with the two libraries using different conventions on the order in which
red, green and blue are encoded.
This is illustrated in the figures below (the numbers underneath represent the bit positions). In
image_rw.c and image_show.c, there are functions that convert our Pixel data type to these
uint32_t representations. Have a look at that code and specifically the functions
pack_pixel_RGB(), unpack_pixel_RGB() and unpack_pixel_BGR(). They are a good example
of bit-wise operations in C.