HW2
Design and implement algorithms that can analyze and recognize random shapes in the "shape_train2018" folder:
TEAM MEMBER

Qian Xiang

Tong Li

DATE

09/21/2018 - 09/26/2018

SKILLS

C++

TOOLS

Visual Studio 2017

OpenCV 3.2.0/3.3.0

Problem Definition

Design and implement algorithms that can analyze and recognize random shapes in the "shape_train2018" folder:
1. For each shape image, determine its background color and label each and every shape blobs according to their color.
points: How to determine the background.
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.
point: Understanding the border following algorithm, how to define the N8 neighbors.
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.
point: Using the labeled image to determine the background label and then segment the contour.
4. (Optional) You may also segment the border according to their convexity, i.e. find out all convex segments and concave segments.
point: Recognize the convex pixel in the image.
5. For each shape blob, come up with an algorithm that can recognize its shape type (square, circle, or triangle).
point: Recognize three different shapes and find their centroids.

Method and Implementation

1. determine background and label the image

To determine the background, we observe all the image and find that if the two or more colors of the corner are the same, then that color is the background color. The background color (RGB) and the background label will be outputted. Since the label are from 0,1,..., the output image of the labeled image will be black. So we choose to output the color size and the blobs size to show that we have labeled the images.
To label the image, we store the (0,0) pixel's value in an array first. We use two for-loops to get each pixel of the image. If the color is as same as the color in the array, then label it as the index of the color in the array, else push back the new color and label the pixel as array,size()-1.
The background color and its label will be outputted.

for (height){
for(width){
for (; k < colorSet.size(); k++) {
if (row[j] == colorSet[k]) {
row2[j] = k;
}
} }

2. boundary following algorithm

For this part, we looked up a lot of information on the internet, since we have difficulty define the 8 neighbors and how to search clock wise. There is an easy way to define the directions using two-dimensional array. After set the start point, search clock wise. If find the border(not 0), then set the new start point and the scanning direction is counterclockwise rotation of two grids, because anti-clockwise rotation of three lattice pixels is absolutely not the boundary, otherwise the current point will not be the boundary.If the starting point is found after a circle, the boundary search is complete. We process the image at first, the background are all 0, and the rest of the pixel is 255.
The behavior of findcontour() is better than boundary following algorithm. The contours of the image will be drawn and outputted.

int directions[8][2] = { {0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1} };

3. classify border pixels

Using the labeled image and two for-loops:
Border of the whole image: Firstly, if the pixel is around the image and the pixel is not background, then it is the border of the whole image. Use [255,255,255] to draw the border.
Border against the background: For every pixel except the around, if the pixel itself is the background and one of its 4 neighbors is not background, then it is the border against the background, Use [0,255,0] to draw the border
Borders against another shape blob: For every pixel except the around, if the pixel itself is not the background and one of the 4 neighbors is not background and is not equal to itself, then it is the border against another shape blob. Use [0,255,255] to draw the border.
The output images are in the "classifiedBorder" folder.

for(height){
for(width){
if (r == 0 || l == 0 || r == label_image.rows - 1 || l == label_image.cols - 1) {}
if (row[l] == imgBackgroundLabel && (row[l - 1] != imgBackgroundLabel || row[l + 1] != imgBackgroundLabel || label_image.at(r - 1, l) != imgBackgroundLabel || label_image.at(r + 1, l) != imgBackgroundLabel)) {}
if (row[l] != imgBackgroundLabel && ((row[l - 1] != imgBackgroundLabel && row[l - 1] != row[l]) || (row[l + 1] != imgBackgroundLabel && row[l + 1] != row[l]) || (label_image.at(r - 1, l) != imgBackgroundLabel && label_image.at(r - 1, l) != row[l]) || (label_image.at(r + 1, l) != imgBackgroundLabel && label_image.at(r + 1, l) != row[l]))){}
} }

4.(Optional) convexity

Use convexHull() to find the convex point and then draw the contours. The output images are in the "convexity" folder.

convexHull(Mat(contours[i]), hull[i], false);

5. recognize the shape type

Using "findContours" to find all the borders of shapes.
Using "drawContours" to draw the contours of circles.
Using "approxPolyDP" to get the contours of squares and triangles.
Using moments to caculate the centroids.
The output images are in the "shapeType" folder.

vector mu(contours.size());
for (int i = 0; i < contours.size(); i++)
{
mu[i] = moments(contours[i], false);
}
vector mc(contours.size());
> for (int i = 0; i < contours.size(); i++)
{
mc[i] = Point2f(mu[i].m10 / mu[i].m00, mu[i].m01 / mu[i].m00);
}

Experiments

1. For the question 1, 3 and 4, we use for-loops to read 500 images and use them as the input of the functions to get the output. The program will show which image is being processed. For the second question, if we use for-loops to read image, it will have error "CRT detected that the application wrote to memory after end of heap buffer" and we can not solve it till the deadline. But with each single image, it can works well. For the fifth problem, we have a problem of getting all the images with the same image number in the annotations and didn't have enough time to solve it, so we choose 30 images to test the accuracy.
2. Output results:
(1) Output the background color and its label using cout<<;
(2) The contours of the image will be drawn and outputted.
(3) The output images are in the "classifiedBorder" folder. Border drawn with different colors: border of the whole image using [255,255,255], border against the background using [0,255,0] and borders against another shape blob using [0,255,255]
(4) The output images are in the "convexity" folder. The convex point will be connected.
(5) The output images are in the "shapeType" folder. The borders and centroids are drawn in different colors: circles using green, squares using red, triangles using blue and centroids using black.
3. The running time is pretty good, for the 500 images, the time is between 130~150 seconds. The result of the first problem if nearly 100%(if the image is 100% clean and there is no noise in them); The result of the second problem is to output the outer-most contours searching by different algorithm.The behavior of findcontour() is better than boundary following algorithm. Since the boundary following is to find a connected boundary, if there is another boundary not connected with the boundary algorithm found, then it will not be found as the result shown
The result of the fifth problem can be shown by randomly choosing 30 images and calculates their precison: TP/(TP+FP). As three tables shown below, the precision turns out to be 58.8%.

Results

result 1 background + number of blobs

result 2 border follwing + findcontour

result 5 recognize shape

result 3 classified borders

result 4 convexity




result 5 recognize shape type and calculate precision

Discussion

1. Strengths:

The running time is better than we thought. We use pointer to get pixels this time, so we think this is one of the reasons.

2. Weaknesses:

For the problem 2, the code still has some problem with for-loop input 500 images although it can detect the boundary very well.
For the problem 5, because of the failure of using Hough transform to get the contour and centroid of circles, the result is not as good as we thought before.

3. Limitation:

If the image changed, for example, the four corners of the background are covered with blobs, then our method will not able to find background. So is in the problem 5, if the edge is covered by the shape, the shape cannot be defined accurately. What's more, we used optimized image as the input and the result is pretty good. However, if the images are more complicated as images in the "shapes_train2018", which we used in the first place, our method will fail too.

4. Expectation:

Know more about image processing, and also get familiar with OpenCV.
Improve the precesion of algorithms we have implemented.

5. Potential future work:

For the images in the "shapes_train2018", we could try to use kmeans to denoise images. The result of precision turns out to be not so well. We can optimize it further by using GetAreaMaxContour function or turning shapes into hsv.
Speed up the running rate.

Conclusions

1. Since we are not familiar with OpenCV and its functions, we were really struggling finishing this homework. Maybe the result is not as good as other students', but we tried our best to implemented all five experiments.
2. Through this homework, we found that pre-processing is really important for image processing. To get better and preciser result, the image should be smoothing or denoise first.
3. With the implementation of algorithms, we get to know much better how the functions provided by OpenCV work.

Credits and Bibliography

1. Help offered by TA.
2. Boundary following algorithm: https://blog.csdn.net/u011974126/article/details/17283443,https://blog.csdn.net/u010555688/article/details/50803021, 9/23/2018
3. Boundary following algorithm: https://www.codeproject.com/Articles/1105045/Tracing-Boundary-in-D-Image-Using-Moore-Neighborho#_comments, 9/23/2018
4. OpenCV documents to find some methods and functions: https://docs.opencv.org/3.2.0/annotated.html, 9/22/2018-9/26/2018
5. Recognize the shape type: https://blog.csdn.net/xuxunjie147/article/details/76577298, 9/24/2018
6. Get the centroid:https://blog.csdn.net/qq_34914551/article/details/78916084, 9/25/2018