CS 585 Homework 2

CS 585 HW 2
Teammate: Di Zhu, Jinghui Ning
Sep.26, 2018

Problem Definition

A set of images is given as input. Each image contains one to four different shape blobs(square, triangle, circle) in different colors.
The requirents to the program are:

  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. For each shape blob, come up with an algorithm that can recognize its shape type (square, circle, or triangle).

Method and Experiments

We used the original dataset as our input.

Step1. Denoising and Determine the background color

The original image is in JPEG format. Due to the compression algorithm used in JEPG images, the original images are high-noised. As illustrated below, the colors on the edges of blobs are somehow blurred, indicating that in one blob there are several different colors. We need to denoise the image before finding the contours.

To denoise the image, we used the average filter function Blur: void blur(InputArray src, OutputArray dst, Size ksize, Point anchor=Point(-1,-1), int borderType=BORDER_DEFAULT ).
In our case, the parameter ksize = Size(3, 3).

To determine the background color, we examine the color of each pixel and calculate the number of their appearances. The color that appears the most is considered the background color.

Step2. Label shape blobs

To label the shape blobs, we scan the image pixel by pixel. If the current pixel satisfy both of these assumptions:
(1) The color of the current pixel is not the same as or close to(threshold = 10) the background color.
(2) The current pixel is not at the intersection of two shape blobs
mark the current pixel white.If the pixel has color of the background, mark it black.

Then we convert this image to binary image and feed it to the FindBinaryLargeObjects(const Mat &binaryImg, vector > &blobs) function in lab2 to label and recolor the shape blobs.

Step3. Find Contours of Image

The labeled and recolored image is ready for us to find its contours. For each pixel in the image, we examine the RGB value of itself and of every pixel in its N8 neighbourhood. If the RGB value of this pixel is different from the RGB value of one of the pixels in its neighbourhood, this pixel is marked as contour.The width of the contours we got from this step is 1 pixel.

Step4. Classify the borders

We could classify the borders now that we have contours, the background color and colors in each shape blob is unified.We simply go through all the pixels in the image. If the current pixel is next to a background pixel, the current pixel will be labeled as border against the background.If none of the current pixel's N8 neighbor is background pixel, the current pixel is considered border between two shape blobs. If the pixel is on the boundary of the image with color different from the background, it is border against the boundary of the image.

We use different colors to represent different borders.

  • Blue, Vec3b(255, 0, 0) - border against the background.
  • Green, Vec3b(0, 255, 0) - border between two shape blobs.
  • Red, Vec3b(0, 0, 255) - border against the boundary of image.
  • Step5. Determine shapes

    We use slopes to determine the shape. We select up to 32 pixels on the blob's border against the background and store them in a vector.

  • To classify squares, we calculate the slope of the line determined by two adjacent pixels in the vector. If at least 75% values of all slopes are 0, the blob is a square.
  • For triangles, we choose the first pixel as the starting point and , we calculate the slope of the line determined by the starting point and another pixel in the vector. If a certain proportion of the slopes is near 1.732 or -1.732, the blob is a triangle.
  • Otherwise, the blob is a circle.
  • We use white to represent squares, orange to represent triangles and indigo to represent circles.

    Step6. Calculate the precision

    To calculate the presicion, we calcuate the centroid of each blob. We check whether it is on one of the white blobs of the annotation masks. If so, we compare the filename with estimated shape type to get TP and FP.


    Trial Source Image Background color Shape blobs Borders Classified Borders Blobs Annotations


    Shape TP FP Precision
    Square 303 15 0.95
    Triangle 356 11 0.97
    Circle 345 46 0.88
    Overall 1004 72 0.93


    Discuss your method and results: