HW2: Programming Assignment

CS 585 HW 2
Guangxing Ren
Yueying Li
Xi You

Problem Definition

This Problem require our team to design and implement algorithms that can analyze and recognize random shape The shapes are categorized into three types: square, circle and equilateral triangle.
We have five specific problems:

1.For each shape image, determine its background color and label each and every shape blobs according to their color.
2.For each shape blob, implement a border following algorithm to find its outermost contour (i.e. the border pixels) and compare it with OpenCV's "findContours" function.
3.For each shape blob, classify its border pixels (in other words, segment its outermost contour) into three types: borders against the background, borders against another shape blob and borders that are a border of the whole image.
4.(Optional) You may also segment the border according to their convexity, i.e. find out all convex segments and concave segments. This may help you analyze its shape type.
5.For each shape blob, come up with an algorithm that can recognize its shape type (square, circle, or triangle).

Method and Implementation

Problem 1 Method:
We traverse the whole image twice. For the first time, we use a colorMap to record every pixel’s color. After that, we merge some color according to the threshold. And for the second time we compare each color in the colorMap with the current pixel and mark each pixel by the color they match. Finally, the output of the function is an image marked by object’s label and a vector contained the points of each object.
Problem 2 Method:
For the second problem, we use Moore-Neighbor Tracing Algorithm to solve the problem. The link attaches on the bottom of the page. We only introduce briefly at this part.
   1. Find a start pixel named point c
   2. Find the N4(N, W, S, E) neighbor of c and mark the west pixel of c as b
   3. Among N8(NW, N, NE, W, E, SW, S, SE) neighbor of c, starting with b, search clockwise to look for the first boundary pixel.
   4. Let b becomes the new c and the previous b becomes the new b
   5. Repeat 3&4 until c becomes the start c

Problem 3 Method:
Find the average value(central point) of the points on the coincident edge(of two objects for example, object 1 and object 2). If the point of average value on the object 1(the value of central point equals object 1), the object 1 blocks the object 2. If point on the object 2, the object 2 blocks the object 1. This object can be the object on the image or the boundary.
problem 4 method:
In Problem 3 we find out the average points on the coincident edge, If the point of average value on the object 1, this segement is a convex part of object 1, on the other hand, this segement is a convex part of object 1 concave part of object 1.
Problem 5 Method:
For this problem we find leftmost point, rightmost point, top point and bottom point. And then we connect each point to calculate the degree of their angle. If one of the angle is 90 degree we mark it as square and if one of the angle is 60 degree we mark it as equilateral triangle and if it's none of them we mark it as circle.


Experiments Environment: window 10/visual studio 2017
Size of the image: 128p*128p

Our method can be applied to the png image provided in each job, and some of them are applicable to the provided jepg image.


trial 1 1027.png
orginal image

as you can see, we successfully label 5 color
opencv findcontour
diy findcontour

as you can see,our accuracy is 0.28, although the number is not high but we find all contours and visually matching.

as you can see, we recongize which object is being block and which is a whole image

object segement that against each other mark RED

we correctly recognize three of four object shape


Discuss your method and results:


The color and position of the image can be transformed by changing the RGB value and the position of the pixel.The image in real life is hard to process as it is not perfect.

Credits and Bibliography

The solution of problem one got the suggestion from Xueying Han
Moore-Neighbor Tracing https://www.cnblogs.com/biglucky/p/4136946.html
Template of this homework: http://www.cs.bu.edu/faculty/betke/cs585/restricted/hw-instructions/cs585-homework-template.html

All the problems came across during the possess discussed with Yueying Li and Xi You