# Homework 2

CS 585 HW 2
Yuansheng Dong
Boqi Chen
09/26/2018

## Problem Definition

Homework2 aims at finding and recognizing the basic shapes in an image. This contains finding the background of the image, the border of the shapes and discriminating different shapes. Specifically, we mark the background of the image as black, the border of the shapes as blue, green or red, based on their neighbor pixels, and recognize the shapes according to the number of inflection points. The main challenge in this assignment is that a shape in the image might be covered by another, which complicates the recognizing process.

## Method and Implementation

For each part of homework2, we create a new image to save the results. Below are the details of each part:

1. Background Image: It can be seen from the dataset that border pixels are mostly background. Hence, we count the number of different colors at the image border, and select the one that appears the most as the background color. We then scan the whole image and background is extacted by selecting the pixels that has the same color as the background color. These pixels are marked as black while the rest are as usually.
2. Outermost Contour: As shapes may be covered by other shapes in the image, colors at the outermost contour has to change from either the background color to any other color or any other color to the background color. We scan the whole image row by row and column by column while marking these pixels as blue. However, the outermost contour may also appear at the image border. We therefore include the pixels at the border with colors that are different from the background color.
3. Border Image: Just as what had done to the outermost contour, we select the border between shapes by choosing the pixel with color changes from one to the other, but neither of them are the same as the background color. We mark these pixels as green while the border of the background mentioned above as blue and the border of the image as red.
4. Recognize: The prerequisite of shape recognition is finding the borders of each blob. The intersection of two shape blobs would surely affect the recognition of the blob, so the border against another shape blob is of vital importance. We should judge the border belongs to which blob or the border of another shape blob would influence the feature of the shape. After deciding the contour of the blobs, we could recognize the shape of the blob by evaluating the relationship between the points of the border. The three given shapes have characteristics and we use the function called approxpoly to judge the approximate figure of the blob. Since the triangles are all regular triangles, the slop of each edge should be either around the value of square root 3 or positive square root 3 and both the circle or square don't share this feature. After finding the triangles, we should find the circles. Since all curves are saved as many points, but after using the function approxpoly, the linear points would be removed except the two end points. In that case, the contour of circle would certainly have much more points than the square, and we could judge the shape by counting the point numbers. The remaining shape is square and in our algorithm, the square should have the edges that are verticle so the slope of the edge should be either infinity or minus infinity.

## Experiments

For this assignment, there are total 500 images with at least one shape, varies from circle, square to triangle. Background and each shape blob is marked as a different color. We aim to discriminate the background from the shapes and also to recognize the shape blobs according to their contour. We test our program using the recognizing accuracy and also view the correctness of the detected three kind of contours. The accuracy of this assignment should be TP/(TP+FP)=420/500.

## Results

All the 500 images are tested in our experience and the recognizing rate is about 82%. Below is an example of our output images and the detected result.

 Input The Input Image Output1 The Background Image The Blobs Image Output2 The Outermost Contour Image The Contour Image

From the above images, we can see that our algorithm can correctly detect most of the background, blobs, the outermost contour and the three types of contour marked as different colors in the above image. However, there are still some difficulties in discriminating the shapes due to the quality of the images, which we will focus more in the future.

## Discussion

In our method, the background pixels and the borders can be correctly discriminated based on the color difference between shapes and background. However, there might occasionally happen that most image borders are covered with shapes, which make the background detection not accurate. The covered shapes would always have holes on them and this would to some extent affect the precison of our algorithm. Besides this, with the shape partly covered, there are some difficulity in discrinmiating them, which decreases the recognition accuarcy. This will need future discussion. The program is still limited to recongzing the optimized png image. This happens because the jpeg format compresses the image, which differs the pixel value, even though they may look the same to human eyes. We tried to denoise the image using the "fastNlMeansDenoisingColored" fuction provided in OpenCV and give a range of 10 for each channel to decide whether the two pixels are the same. What's more, we also tried other denoising methods like gaussianBlur to remove the noise in the image. However, error still occurs and we will try to solve this problem in the futue.

## Conclusions

The program is able to gain a high accuarcy on recognizing shape blobs. However, there are still some difficuilties in discrinminating circles and triangles, especially when there are noises in the image since we use the number of points in the contour to judge whether a shape is circle or not and in that case the noises would made the contour unclears and they would have much more edges caused by the noises. In the future, the method need to be improved as mentioned in the 4th requirements, we could try to distinguish convex segments from concave segments which may help to improve analyzing the shape.

## Credits and Bibliography

[1] http://www.cs.bu.edu/faculty/betke/cs585/restricted/hw-instructions/cs585-homework-template.html, 09/10/2018
[2] http://www.cs.bu.edu/faculty/betke/cs585/restricted/lab1/CS585_Lab2.pdf, 09/09/2018
[3] https://docs.opencv.org/3.3.0, 09/07/2018
[4] https://blog.csdn.net/nanguazhuo/article/details/53537705, 12/09/2016