12-04-2012, 05:13 PM
Image Processing Programming Projects in an Upper Division Algorithms Course
10.1.1.97.1041.pdf (Size: 183.33 KB / Downloads: 99)
Introduction
We have been assigning image processing programming projects in our algorithms course for the
past three years. This course is the fourth course in the major, following Introduction to Computer
Science, Programming I, and Data Structures. Students usually take the course in the second
semester of their sophomore year. At this point in time, the approach has been used for five sections
of the course with approximately 70 students overall. We have used the Corman text[2] all
three years. There are four to five programming projects assigned during the semester. All are
written in Java. We are currently using the Java 2 Platform, Standard Edition, version 1.4.1.
Examples of Assignments
All assignments corresponded to topics covered in class. All required an analysis of time complexity
of algorithms used. All were geared to process so much data that empirical time complexity
was a real issue. All required submission of source code for a Java graphical application plus a
typed report describing algorithms, classes, methods and objects plus problems encountered and
how they were solved.
Array Manipulations:
Since some of the students had never done Java graphics, the first assignment was chosen so that it
used data structures which the students knew well (one and two dimensional arrays). They could
then focus on the GUI and image related issues. They built a Java application which displayed an
image and allowed the user to modify that image. Modifications differed each term. Gradually
blackening the image, turning it upside down, and switching the red and blue pixel values are
a sample of these operations. They were required to move the image into a 2D array, do the
modification then create a new image, which required transferring the pixel values to a 1D array.
Search Tree Algorithms:
Rather than implementing algorithms that used binary trees, we extended our data structure to a
quadtree, often used to represent images in different resolutions as well as for image compression.
The Java application took an image file with its name input at run time, and averaged pixel values,
Greedy Algorithms:
When greedy algorithms were introduced, a popular assignment was to make a stippled or pointillistic
image of any given image. This project required a defense of why their chosen algorithm was
greedy. Some used standard greedy algorithms, some created their own. We then took photos of
everyone and ran each student’s photo through their own algorithm. Since their individual algorithms
were all greedy but not all identical, the results varied significantly. These were posted on
the department bulletin board. A sample image and pointillistic result can be seen in Figure 3.
Compression Algorithms:
Huffman coding was implemented by using it to compress an image and then comparing the results
to other compressions such as Unix or Run Line Encoding. This gave us a good opportunity to
discuss compression algorithms using large files, something which had eluded the author in the past.
Summary
Now wrapping up its third year, we have tentatively declared the project to be a success. Although
initial student reactions have often been hesitant, end of course feedback has been generally positive.
At the same time, it has been clear that the strong students were more satisfied than those who
were not so strong. However, this has been generally true regardless of how the course is taught.