COMP1921 14s2 Assignment
Image Processing with Quad-Trees
Aims
This exercise aims to give you practice in dealing with dynamic data structures, specifically lists and trees. The goal is to complete the implementation of a small program that can do simple image processing.
Assessment
Marks: 15 (Criteria: correctness, readability, design)
What to submit: img.c, QuadTree.c, ImageList.h, ImageList.c (NOTE: You should not submit QuadTree.h since you are not required to make any changes in this file.)
Submit before: Midnight, Friday, 31st October 2014 (Week 13)
Change Log
We may make minor changes to the spec to address/clarify some outstanding issues. These may require minimal changes in your design/code, if at all. Students are strongly encouraged to check the change log regularly.
Version 1: Released on 29 August 2014.
Background
Image processing is one of the most common and useful tasks to which computers have been applied. On computers, images are represented by a two-dimensional array of picture elements (or pixels). Each pixel represents a "point" in the image and has an associated colour. In this assignment we will only deal with black and white images so each pixel is either "on" or "off". As images increase in size (resolution) it becomes more important to consider efficient methods for storing images. One early data structure developed for storing images was the quad-tree and it will be used in this assignment. In this assignment you are to write a program to maintain a list of images in quad-tree format (some code will be provided to assist you) and capable of loading images, listing the images available, printing images, etc. You might think of this program as an electronic photo album.
The main objectives of this assignment are:
use and manipulate dynamic data structures (like linked lists) to solve a complex problem
learn how to implement a linked list data structure and functions for maintaining the data structure
gain experience with a more complex data structure (a quad-tree) for storing simple images and write some functions for maniupulating this data structure
learn how to organise your programs into multiple files and use them in completing a project.
writing a properly documented C program that adheres to the course Style Guide
NOTE: You should think carefully about the appropriate data structures and algorithms to use in your program. Before starting to write any code it is important that you fully understand the problem and determine the data structures that you will require and the algorithms to use. It is highly recommended that you start coding only after you have spent some time on these considerations. In particular, you must not make any assumptions about the number or size of images; this means that you must use dynamically-allocated linked-list data structure to manage the image collection.
Image Files
In this assignment we will not be dealing with real image files, but will instead use files of ASCII characters to represent images. However, the same principles apply to our image representation as apply to real images such as those in RAW digital camera format.
In our image representation, the space character ' ' acts as a white pixel and the hash character '#' (or any non-space character in fact) acts as a black pixel. For example, consider the following 8 × 8 image:
As an ascii text file, this image would be represented as (where '\n' represents the newline character):
## \n
#### \n
## ## \n
## ## \n
###### \n
## ## \n
## ## \n
\n
Some sample image files will be supplied but you should also create some of your own for testing.
Quad-Tree Data Structure
In the 1970s, the quad-tree data structure signalled a revolution in image processing. Quad-trees allowed for a compact representation of images together with straightforward algorithms for certain graphical manipulations.
The basic idea behind quad-trees is quite simple. An image is divided into equal quadrants:
NW
NE
SW
SE
Here the quadrants are labelled North West (NW), South West (SW), North East (NE) and South East (SE).
Quad-trees are a hierarchical collection of linked nodes. There are two kinds of nodes: leaf nodes and internal nodes. Leaf nodes represent a part of the image where all pixels have the same colour. Each leaf node contains a single value (using ' ' to represent white and '#' to represent black). Any part of the image which is not uniformly black or white is further subdivided into equal sized sub-quadrants and the corresponding node is an internal node with four child nodes — one for each sub-quadrant — and the process continues.
The following diagram shows a single internal node, with links to the nodes at the roots of the subtrees for its four sub-quadrants:
In our diagrams, we represent internal nodes by black circles with links leading from them to four subtrees. Leaf nodes are represented by either black or white squares, indicating the colour of the quadrant. Consider the following two very simple 2 × 2 images and their corresponding quad-trees, each of which contains one internal node and four leaf nodes:
Consider now a 4 × 4 image. We first consider the groups of 4 pixels in the NW, SW, NE, SE quadrants. In the NW quadrant, all of the pixels are black, so that gives a black leaf node in the first level of the quad-tree. In the NE quadrant, all of the pixels are white, so that gives another leaf node in the first level of the quad-tree, which however is white. The SW and SE quadrants are not uniformly "coloured" and so need to be decomposed further in an additional level of the quad-tree.
For a more complex example, the image of the letter 'A' above would be represented by the following quad-tree:
Note how each node is either a leaf or has four children. Hence the name quad-tree.
Note that quad-trees work with images that are of size 2n × 2n pixels for some integer value of n. We will assume that the images supplied to our program are also of such dimensions. If they are not, the function that reads images "pads" the image to an appropriate size by filling it with white pixels. For example, a 5 × 5 image would be "padded" as if it had been an 8 × 8 image (where we have used '.' characters to show more clearly where spaces (white pixels) have been added):
Original: Padded:
#####\n #####...\n
#####\n #####...\n
#####\n #####...\n
#####\n #####...\n
#####\n #####...\n
........\n
........\n
........\n
A Collection of Images
As outlined above, your program manages a collection of images, and needs to keep track of some data regarding each image that you acquire. In Stage 1 you will implement commands to obtain this data from the user. For each image, you will need to keep track of at least:
filename
The name of the file containing the image.
dimension
Each image will be dim × dim pixels in size where dim = 2n for some integer value n (i.e., the dimension is a power of 2).
quadtree data structure
The quad-tree data structure is a representation of the image being stored.
You will be given C code to load an image from a file and return the quad-tree data structure and code to print the image from the quad-tree data structure.
Supplied Material
A ZIP archive src.zip is available containing the following:
Makefile
Configuration file that builds the executable img program.
img.c
Main function that collects and organises processing of user commands.
QuadTree.h, Quadtree.c
Library of functions to manage quad-trees.
ImageList.h, ImageList.c
Library of functions to manage the list of images in main().
images/
Directory containing sample image files, including many (poorly drawn) flags.
You will need to add code to img.c, QuadTree.c and ImageList.c. This in turn may require changes to ImageList.h. However, you should not make any changes to QuadTree.h. Note that you only need to add code for implmenting the rotate and flip functions in QuadTree.c.
Note that the ImageList library is not a generic library, since it is used only to manage the single ImageList object that is declared in the main() function. You are free to define the interface and functions for this "library" in any way that fits with your usage of the ImageList object. Note that ImageList.h contains a dummy definition for the ImageList type, just so that the main function will compile.
If you unpack the src.zip file into your directory for this assignment and then run the make command, you should observe the following:
$ make
gcc -Wall -g -c img.c
gcc -Wall -g -c QuadTree.c
gcc -Wall -g -c ImageList.c
gcc -o img img.o QuadTree.o ImageList.o
$
You can see that this produces an executable program called img. If you run this program, you can do the following:
$ ./img
IMG (? for help) > ?
A - Add image from file
L - List of images
P - Print current image
<k>- make image number k the current image
D - Delete image
S - Search for an image
R - Rotate image clockwise
F - Flip image (reflect horizontally)
Z1 - zoom into North West corner
Z2 - zoom into South West corner
Z3 - zoom into North East corner
Z4 - zoom into South East corner
O - zoom Out
? - Help
Q - Quit
IMG (? for help) q
Bye!
$
Note that the only commands that do anything in the supplied code are ? (Help) and Q (Quit). Note also that the program maps all upper-case input to lower-case, so you could type the commands in either upper- or lower-case (e.g. Q or q).
For each of the operations that you are required to implement, you should perform suitable error-checking and produce a message for any error condition that you detect. You should produce exactly the same error message as that produced by the sample solution.
Note that "reflect horizontally" means that the image should be reflected on the horizontal axis (i.e. swap top and bottom, as the sample solution does).
In developing your solution for ImageList.c, you are allowed to copy chunks of code from the List.c library from lectures, if you find it helpful. If you use code like this, you must mark it with a comment to indicate its source, e.g.
// This code adapted from COMP1921 lecture example
Stage 1 - Adding, Indexing and Printing images
The img program maintains a collection of images. These should be stored using a linked list whose data type you need to design, and whose definition you put in ImageList.h. You will need to declare a list object in img.c. You should try to put most of the list management code in ImageList.c, but it is acceptable to do some list manipulation in img.c.
For Stage 1, you will need to implement these commands:
A - Add image from file
L - List of images
P - Print current image
The A command allows the user to add a new image from a specified file. For example, if the image is a filed called "canada", it could be added by typing
a canada
The function getImage() in the file QuadTree.c has been supplied to help you:
QTnode *getImage(char *filename, int *dim)
It takes the name of the file as a string filename and returns a pointer to the quad-tree data structure and the dimension of the image. The pointer to the quad-tree node is the return value of the function, while the dimension is passed via the argument dim, which needs to be passed by reference to the function. You will need to store and keep track of all this information in the linked list data structure that you design. You will also need to keep track of the image number of each loaded image so that you can access them (see below).
After each new image is added, your program should print the image number, dimension and name of the newly added image, as follows:
* 1 [16] canada
The star * at the beginning of the line indicates that this is the current image. When a new image is added, it always goes to the tail of the list and becomes the current image.
The L command should print a list of all the stored images, in the order in which they were added. For example:
1 [16] canada
2 [ 8] tonga
*3 [16] australia
The current image should be distinguished by a star * at the beginning of the line; the other images should begin their line with a blank space. The dimension of each image should be printed with a minimum of 2 characters, using the format "[%2d]".
The P command should print the current image using the function printImage() from QuadTree.c
void printImage(QTnode *qt, int dim)
Stage 2 - Navigating/maintaining the List
For Stage 2, you will need to implement these commands:
<k>- make image number k the current image
D - Delete image
S - Search for an image
When the user types a number k, the image with that image number should become the current image. If there is no image with the specified image number, this command should print the message No such image and leave the current image unchanged.
The D command should remove the current image from the list and free up any memory it occupied. The new current image should be the next one after the deleted image. If the deleted image was the last image in the list, the previous image (which is now the last image) should become the current image. After a deletion, the remaining images should be re-numbered to fill the gap created by the deleted image.
The S command should search for the first image whose filename contains a specified string, and make it the current image. If no such image exists, then the command should print the message No such image and leave the current image unchanged.
For example, to search for the first image whose name contains the substring "trali", you would type the command
f trali
After each successful <k>,D or S command, your program should print the image number, dimension and name of the current image (as described above).
Stage 3 - Rotating, Flipping and Zooming
For Stage 3 you will need to implement these commands:
R - Rotate image clockwise
F - Flip image (reflect horizontally)
Z1 - zoom into North West corner
Z2 - zoom into South West corner
Z3 - zoom into North East corner
Z4 - zoom into South East corner
O - zoom Out
The zoomed-in image should keep the same dimension, and therefore occupy the same amount of space on the screen as the original image.
If the image has already been zoomed into a leaf node (all black or all white), the commands Z1,Z2,Z3,Z4 should have no effect. If the image has been zoomed out to its original scale, the O command should have no effect.
When a zoomed-in image is rotated (or flipped), the entire image should be rotated (or flipped), but only the currently visible portion should remain visible. In other words, the combination of zooming in, rotating and zooming out should have the same effect as rotating the original image.
After each R,F,Z1,Z2,Z3,Z4 or O command, your program should print the current view of the current image using the function printImage() in QuadTree.c
Sample Output
Here is an example session with the img program:
IMG (? for help) > a tonga
*1 [ 8] tonga
IMG (? for help) > p
###
# ###
### ###
# ###
###
########
########
########
IMG (? for help) > z1
##
##
######
######
##
##
IMG (? for help) > q
Bye!
For a more detailed understanding of what's required, a compiled solution to the assignment (i.e. a working img program) has been provided for you in
~cs1921/bin/img
Your program should produce exactly the same output as this executable.
Submission
The due date is Friday (midnight), 31st October 2014 (Week 13).
15% penalty will be applied to the (maximum) mark for every 24 hours late after the deadline. No submissions will be accepted after 5 November 2014.
The submit command is:
give cs1921 assignment img.c QuadTree.c ImageList.h ImageList.c
You MUST submit all 4 files mentioned above. You are NOT required to submit QuadTree.h.
Be sure that your program compiles using the usual compiler flags (on a computer in CSE).
You can submit as many times as you like — later submissions will overwrite earlier ones. You can check that your submission has been received by using the following command:
1921 classrun -check
Additional information may be found in the FAQ and will be considered as part of the specification for the project. Questions relating to the project can also be posted to the Course Forum on the course Web page. If you have a question that has not already been answered on the FAQ or the MessageBoard, you can email it to your tutor.
Plagiarism Policy
Group submissions will not be allowed. Your program must be entirely your own work. Plagiarism detection software will be used to compare all submissions pairwise (including submissions for similar projects in previous years, if applicable) and serious penalties will be applied, particularly in the case of repeat offences.
DO NOT COPY FROM OTHERS; DO NOT ALLOW ANYONE TO SEE YOUR CODE
Please refer to the on-line sources to help you understand what plagiarism is and how it is dealt with at UNSW:
Learning Centre: Plagiarism and Academic Integrity
MyUNSW: Plagiarism and Academic Misconduct
CSE: Addendum to UNSW Plagiarism Guidelines
CSE: Yellow Form (whose terms you have agreed to)
Marking
This project will be marked on functionality in the first instance, so it is very important that the output of your program be EXACTLY correct (identical to the output of the sample solution). Since your submssion will be automarked, if it does not exactly match the expected output, it will be recorded as incorrect. it is your responsibility to test it appropriately to ensure that it does produce recognisably correct output.
Submissions which score correct on the automarking will be awarded full marks on the testing component of the marking. Submissions which score very low on the automarking will be looked at by a human and will receive some marks, provided the code is well-structured and commented.
Programs that generate compilation errors will receive a very low mark, no matter what other virtues they may have. In general, a program that attempts a substantial part of the job but does that part correctly will receive more marks than one attempting to do the entire job but with many errors.
The marking breakdown is as follows:
Stage 1 - 4 marks
Stage 2 - 4 marks
Stage 3 - 4 marks
Comments, programming style, clarity and adherence to the style guide - 3 marks.
Finally ...
Have fun! Michael