CS 3243 - Foundations of Artificial Intelligence

Homework #2 - Simple 2D Object Recognition through Vectorization

You should submit your working version of the assignment by the midnight on the due date. The IVLE workbin will accept late submissions. Late submissions are subject the the late submission policy (read carefully). Your submission should contain a plain .txt file called students.txt which should have the same format as given in the hyperlink (in fact, why don't you save the linked file now and adapt it before you submit it?). Make sure your files are in plain ASCII text format -- MS Word files or other word processing files will NOT be entertained. Your team's work should be done independently of other groups; see our classes' section on Academic Honesty Policy if you have questions about what that entails.

This homework specification was written by Huang Weihua. Please address your questions, concerns and answers to him.

Background

Vectorization, also known as raster-to-vector conversion, is a very popular technique used in Image Analysis and recognition applications, such as recognizing graphs and engineering drawings. The most obvious advantage of vectorization is the dramatic reduction of information to be processed. Comparing to thousands or even millions of pixels in an image, vectors only require several parameters to be specified and stored for further interpretation. For example, a vector for a straight line only contains the coordinates of the starting point and the ending point, which are 4 values in 2D space or 6 values in 3D space. A vector for an arc requires a little bit more: the coordinates of the starting point, the ending point and the center. Furthermore, vectors are much easier to process. Finding geometric relationships between two vectors are easy. For example, we can find out whether two straight lines are parallel or perpendicular to each other without any problem. We can also check if two vectors share the same endpoint or common center points. If we can achieve this, then we can recognize certain objects by converting its edges into vectors and examining their relationships. Despite of these obvious advantages, vectorization is yet a difficult task. First of all, a real-life image contains a lot of noise, which can cause significant errors during the process. Secondly, thickness of the lines and arcs need to be considered, which significantly increase the complexity of the process. Currently, research is still going on to enhance the performance of vectorization. There are some quite mature vectorization techniques that are proved or claimed to work well. Liu and Dori [1] developed a sparse pixel vectorization algorithm for straight line vectorization. They also proposed an incremental arc segmentation algorithm [2] to deal with arcs. Recently, another group of people proposed a Line Net Global (LNG) algorithm [3] that also works on straight line vectorization, and it is claimed to be faster.

Your task

This homework assignment is broken down into three parts. Your group needs to do all three well to do well in this assignment.

Vectorizing 2D image (40%)
In this assignment, we are dealing with simple black-and-white images. These images are synthetic and clean, so no noise removal is required. Since arc vectorization is relatively harder to achieve, the content of the image is restricted to straight line segments only. The thickness of all the lines is 1, to make the process simpler.
Note that a straight line segment in the discrete image plane is not a single smooth segment. It actually consists of a number of short segments that are horizontal or vertical. So you need to think of a way to detect these short segments and merge them together. (Hint: all short segments belonging to the same line segment should have similar length and the same orientation.)
Finding basic shapes (30%)
Now you should have a set of vectors representing the straight lines in the image. In this part, you are going to examine their relationships, namely: parallelism, perpendicularity and convergence. For the former two cases, you need to calculate the slop of the lines. For the last one, you only need to consider the distance between a pair of endpoints.
After this, you should be able to find out the following 2 shapes:
- Rectangle: 2 parallel pairs, 4 perpendicular pairs, 4 common endpoints.
- Triangle: 0 parallel pairs, 0-1 perpendicular pairs, 3 common endpoints.
Constructing object models (30%)
An object can be modeled by a set of components (shapes) and a set of constraints specifying the layout of the components. We already have the set of shapes. To locate an object in the given image, the remaining task is to examine the layout of these shapes. You need to give your own set of constraints that is specific enough to locate the object.

Testing images

Two testing images will be provided, and you can use them to test each part of your program. In the end, we are going to use them to test your program based on two major criteria: accuracy and efficiency. You are encouraged to produce your own testing image besides these two, bonus marks will be rewarded if you do so.


Testing Image 1: A robot.	Testing Image 2: A dog standing next to a tree.

Image Format: Bitmap only (BMP).

Preferred Programming language: C/C++, Java.

References

W. Liu and D. Dori, "Sparse Pixel Vectorization: An Algorithm and Its Performance Evaluation", IEEE Transactions on Pattern Analysis and Machine Intelligence, 1999, vol. 21, pg. 202-215.
D. Dori and W. Liu, "Incremental Arc Segmentation Algorithm and Its Evaluation", IEEE Transactions on Pattern Analysis and Machine Intelligence, 1998, vol. 20, pg. 424-431.
J. Song, F. Su, J. Chen, C. Tai and S. Cai, "Line Net Global Vectorization: an Algorithm and Its Performance Evaluation", CVPR 2000, pp. 383-388.