A Simple Pattern Recognition Algorithm

Artificial Intelligence, Machine Learning, Pattern Recognition and Computer Vision are fascinating fields. I want to encourage college students to pursue these subjects. Advanced high school students can learn the basics of these subjects as well. Here’s a project for college and advanced high school students.

Project: develop a computer program that classifies (recognizes) shapes as triangles, squares, or circles.

Input: a gray-scale image consisting of pixels.

For the input you can have a N by N array. Each element of the array is represented by a number from 0 to 10. Number 0 represents the black color and 10 is the white color. The numbers between 0 and 10 represent the shades of gray.

Difficult part: edge detection

I assign the difficult part as homework. You can scan the numbers in this NxN array and extract shapes by detecting transitions from black to gray or white. Basically, you need to find a way to group the non-zero elements into an area. The area of the cluster of non-zero elements is a shape. Does this shape resemble a triangle, a square or a circle?

Easy part: shape recognition algorithm

Once you establish the clusters – by knowing where the edge is – you can then compute the perimeter length and the area of that particular cluster.

No interpolation of the edges. Just count the cells (elements) along the edge and also count the elements included in this perimeter. The area count should include the cells that you counted when you were computing the perimeter length.

Now, I will remind you the relationship between the area and the perimeter of the geometric shapes. Speaking of basics, the tutorial video at Khan Academy is very nicely done.

Now, I want you to bring up Excel and compute the the areas, perimeters and the ratios of perimeters to areas of various triangles, squares, rectangles and circles.

Ratio of perimeter to area for the circle

$Ratio=\frac{perimeter}{area}=\frac{2 \pi r}{\pi r^2}=2/r$

Ratio of perimeter to area for the square

$Ratio=\frac{perimeter}{area}=\frac{4a}{a^2}=4/a$

Do you see any pattern yet?

Tricky part: normalization

You cannot see the pattern unless you normalize areas. What does “normalization” mean? Normalization of area means that you force the areas of the clusters you observed in the input array to 1. So, prepare a secondary set of normalized figures where each cluster has area equal to 1.

If there is a perfect circle in your secondary set then the Ratio of that shape will be 3.544…

If there is a square in your secondary set then the Ratio of that shape will be 4.

What about the triangle? If the triangle area is normalized to 1 then the Ratio of that shape will be greater than 4. If it is an equilateral triangle then Ratio=4.559014… which is the highest ratio.

Now we can see the pattern. With figures (clusters) where area=1 the highest Ratio clusters will resemble an equilateral triangle. Clusters with Ratio in the neighborhood of 4 will resemble a square and clusters with Ratio in the neighborhood of 3.5 will resemble a circle.

So, you can classify your clusters into three categories: 1) clusters resembling a circle 2) clusters resembling a square 3) clusters resembling an equilateral triangle 4) other.

In the “other” category, if the Ratio approaches 1, then this cluster starts resembling a curve or a cross rather than a geometric figure.

Triangle maximizes the perimeter-to-area ratio

The investigation can be summarized with the following generalizations:

• Given area=1 the geometric figure that has maximum perimeter is the equilateral triangle.

or equivalently

• Given area=1 the equilateral triangle has the maximum perimeter-to-area ratio

This is why architects use triangular structural elements in their buildings.  Triangular structures are the most stable because the edges provide support for a smaller area compared to other arrangements.

This is why nature uses triangular elements too. Don’t worry! This is not part of the student project. This is my homework.

**************************************************************************

Image credits:
Image 1
Image 2