CS585 Fall of 2018, Assignment 2

Assignment 2

YIDA XIN

Part 1. Paper-and-pencil Assignment: NCC, Circularity, Least Squares Method
See the in-class paper submission. (Here is the PDF version.)

Part 2. Programming Assignment
Please see this link to my Jupyter-Notebook–converted HTML page. (Note: Further modification may apply, prior to the 09/28/2018 demo date.) For detailed explanations of every step of my implemented algorithms and many of the results displayed, please view my Jupyter-Notebook–converted HTML page.

As a brief discussion of what I did: For Task 0 (Image Purification), I used Bilateral Filtering and K-means Clustering to clean up the noisy images, but because later on Yifu has provided us with optimized clean images and because I don’t understand the math behind the range parameter and the spatial parameter of Bilateral Filter, I won’t go into details of discussing this cleaning part; note that K-means returns labels for each of the original pixel positions. For Task 1 (Background Colors), I used the labels provided by K-means; namely, for each clean image, I let the color in the color that corresponds to the most frequent label be the background color; also, of course, note that because K-means have already provided all the labels after successfully clustering all the pixels, the labels for the blobs are automatically there. For Task 2 (Border Following), for each clean image, I first convert that clean image into grayscale, then obtain all the masks (one mask per blob) from that grayscale image using OpenCV’s threshold() function, then for each mask I obtain the border pixels for that mask’s corresponding blob using my own border-following algorithm; the details of my border-following algorithm can be found in the specification of the function “my_border_following()” that I wrote myself. Although I attempted to compare the results of my own border-following algorithm against the results of OpenCV’s “findContours()” function, I wasn’t able to get good results using “findContours()” for some reason, so I eventually gave up trying to compare them. For Task 3 (Border Classification), I again refer to each clean image and the border pixels that correspond to each mask of each such clean image. For each mask, iterate through all of its border pixels and look at each pixel’s N8-neighborhood: For each border pixel, if it has a neighbor that’s “out of bound,” then classify this border as “Border of the Whole Image”; if it has a neighbor that has background color, then classify this border as “Border against Background.” If after iterating through all the pixels of the current border and neither of the two if-statements above checks out, then classify this border as “Border against Another Blob.” Finally, for Task 4 (Shape Classification), I implemented a very coarse algorithm, and here’s the idea: First, observe that, for perfect shapes, a circle’s np.vstack((left_border_pixels, right_border_pixels)) completely overlaps with its np.vstack((top_border_pixels, bottom_border_pixels)), and its left, right, top, and bottom all have the same number of pixels, so we will check both the “vstack”s and the left/right/top/bottom pairwise (so 6 pairs in total, because in practice shapes aren’t perfect, so I hope to increase the probability of successful recognition by increasing the number of such pairwise comparisons); otherwise, a square’s left, right, top, and bottom all have the same number of pixels, and we will also check them pairwise; otherwise, a triangle’s left and right have the same number of pixels, but top and bottom are significantly different. And, of course, I need an additional “otherwise” for unrecognized shape, anticipating that recognition may not occur for my often-imperfectly-shaped blobs.

As a brief discussion of what I didn’t succeed in: For Task 4 (Shape Classification), I observe that classifications are mostly (if not entirely) “square”s and “circles.” This means that something is wrong with the way I implemented the algorithm that I described above. I think my translation from my natural-language description of my plan to the formal-language disjunction and conjunctions was not entirely correct, and this is certainly something that can (should) be looked into and debugged in the future.