AForge.NET :: Detecting some simple shapes in images
Detecting some simple shapes in images
by Andrew Kirillov
The article describes how to detect/check some simple shapes like circles, quadrilaterals, triangles, rectangles, etc.
Posted: June 30, 2010&&
Programming languages: C#&&
AForge.NET framework: 2.1.3&&
Introduction
Doing image processing and especially blob analysis it is often required to check some objects' shape and
depending on it perform further processing of a particular object or not. For example, some applications may
require finding only circles from all the detected objects, or quadrilaterals, rectangles, etc. The article
will describe some basic techniques, which may allow detecting such shapes like circles, triangles and quadrilaterals
(plus their subtypes, like rectangle, rhombus, rectangled triangle, etc.). Note: most of the code snippets provided
in the article are based on the , but can be easily implemented
using any other library providing similar image processing routines.
Prerequisites
Before we go into shape analysis, we need to locate objects we are going to check and their edge pixels,
since they will be used as the input for shape analysis algorithms we are going to discuss. First thing to note
is that we'll suppose our input images contain objects of different colors on a black background. If the background
is not black, then it should be turned into black using, for example, some
, before we start with
described below steps. Here is a sample source image we are going to process and detect shapes of objects on it:
The first step to do is to locate each separate object in the input image, which is done using
// create instance of blob counter
BlobCounter blobCounter = new BlobCounter( );
// process input image
blobCounter.ProcessImage( bitmap );
// get information about detected objects
Blob[] blobs = blobCounter.GetObjectsInformation( );
The array with information about blobs contains such values for each detected blob like its rectangle, centre
of gravity, mean color, standard deviation of color, etc. Some of these values can be use for filtering of blobs.
For example, user may not need to do further processing of blobs which have too small width or height.
For analyzing of blobs' shapes we'll need to get their edge pixels. For this purpose the blob counting class
provides 3 methods, which allow to get left/right edge pixels, top/bottom edge pixels and all edge pixels. The
methods are ,
The image below demonstrates edge pixel detected by each of these methods).
Now we can start with developing a shape detection algorithm, which should detect type of a shape for a given
set of shapes' edge pixels. For these purpose we'll use the
which provides all edge points, so the detection could be more accurate.
Circle detection
The idea of circle detection algorithm is based on the assumption, that all circle's edge points have the same distance
to its center, which equals to circle's radius. Of course doing different image processing tasks it may happen that circles may
have some distortion of their shape, so some edge pixels may be closer or further to circle's center. But this variation in
distance to center should not be very big and should reside in certain limits. If it is too big, than most probably the object
has other than circle shape.
For a given set of circle's edge pixels it is quite easy to estimate its center and radius by finding bounding rectangle
for the specified set of points
method can be used, for example):
// get bounding rectangle of the points list
IntPoint minXY, maxXY;
PointsCloud.GetBoundingRectangle( edgePoints, out minXY, out maxXY );
// get cloud's size
IntPoint cloudSize = maxXY - minXY;
// calculate center point
DoublePoint center = minXY + (DoublePoint) cloudSize / 2;
// calculate radius
float radius = ( (float) cloudSize.X + cloudSize.Y ) / 4;
When we have estimated circle's radius and center, all we need to do is to go through the list of the shape's edge pixels,
calculate their distance to the estimated center and check the difference with estimated radius - distance between provided edge
points and estimated circle. Instead of checking each individual distance value for each edge pixel, we may just calculate mean distance:
// calculate mean distance between provided edge points
// and estimated circle's edge
float meanDistance = 0;
for ( int i = 0, n = edgePoints.C i & i++ )
meanDistance += Math.Abs(
(float) center.DistanceTo( edgePoints[i] ) - radius );
meanDistance /= edgePoints.C
Now, when we have calculated mean distance between provided shape's edge points and estimated circle, we just need to check if
the value falls into certain range or not. If it is too big, then it means that the specified shape is not a circle, since its
edge points are quite away on the average from the estimated circle. Ideally the value should be close to 0 meaning that all specified
edge points fit very well the estimated circle. But, as we already mentioned, we may allow some distortion of the shape.
Which level of distortion do we want to allow for circle shapes? Definitely we can not set any fixed value. The distortion limit
should depend on shape's size, so it would allow higher level of distortion for bigger shapes and lower value of distortion for smaller
shapes. For example, distortion level may be calculated this way:
float maxDitance = ( (float) cloudSize.X + cloudSize.Y ) / 2 *
relativeDistortionL
The relativeDistortionLimit value can be made configurable, so user could affect acceptable distortion level and precision of circles'
recognition. Experimentally I found that 0.03 value (3%) works quite well and allows to filter circles from other shapes.
The approach with relative distortion limit works well, but there is one issue, which we may need to resolve. In the case if we
deal with small circles, like 10x10 pixels in size, the calculated distortion limit will be equal to 0.3. If a circle has some little
distortion, then it may not be recognized as circle. For example, doing some image processing we may get circles which are 9x10 or
11x10 in size, which potentially may lead to higher calculated distortion than the specified limit. To avoid this we may add additional
parameter, which is minimum acceptable distortion. So the resulting formula looks like this:
// some parameters, which also are exposed as properties
private float minAcceptableDistortion = 0.5f;
private float relativeDistortionLimit = 0.03f;
float maxDitance = Math.Max( minAcceptableDistortion,
( (float) cloudSize.X + cloudSize.Y ) / 2 * relativeDistortionLimit );
All we need to do now is to compare previously calculated meanDistance with the maxDitance. If it is less or equal to
maxDistance, then we have a circle, otherwise we have too big distortion, which means the shape is not a circle most probably.
All the above code is also available as a single call in the AForge.NET framework:
Finally, here is a small sample showing how to use/test this method and some results:
// locate objects using blob counter
BlobCounter blobCounter = new BlobCounter( );
blobCounter.ProcessImage( bitmap );
Blob[] blobs = blobCounter.GetObjectsInformation( );
// create Graphics object to draw on the image and a pen
Graphics g = Graphics.FromImage( bitmap );
Pen redPen = new Pen( Color.Red, 2 );
// check each object and draw circle around objects, which
// are recognized as circles
for ( int i = 0, n = blobs.L i & i++ )
List&IntPoint& edgePoints = blobCounter.GetBlobsEdgePoints( blobs[i] );
if ( shapeChecker.IsCircle( edgePoints, out center, out radius ) )
g.DrawEllipse( redPen,
(int) ( center.X - radius ),
(int) ( center.Y - radius ),
(int) ( radius * 2 ),
(int) ( radius * 2 ) );
redPen.Dispose( );
g.Dispose( );
The first two sample images above demonstrate detection of more or less ideal circles. We can see there that ellipses and
other shapes are not misclassified as circles. On the third image we have two circles, which have some distortion in their
shape, but still are recognized successfully as circles.
Detection of quadrilaterals
Detection of quadrilaterals and triangles has pretty much the same idea - we are checking mean distance between provided
shape's edge pixels and the edge of estimated quadrilateral/triangle. The only difference here is the way how to estimate parameters
of the shape we want to recognize and how to check distance to the estimated shape.
Let's start with quadrilaterals first. For a given shape we can make an assumption that it is a quadrilateral, find
its four corners (using
for example) and then using similar method as we've used for circles we can check if our assumption is correct or
not - check how good the shape fits into the quadrilateral with assumed parameters. The below code and picture demonstrate
the idea of finding quadrilateral points for different types of shapes:
// locate objects using blob counter
BlobCounter blobCounter = new BlobCounter( );
blobCounter.ProcessImage( bitmap );
Blob[] blobs = blobCounter.GetObjectsInformation( );
// create Graphics object to draw on the image and a pen
Graphics g = Graphics.FromImage( bitmap );
Pen bluePen = new Pen( Color.Blue, 2 );
// check each object and draw circle around objects, which
// are recognized as circles
for ( int i = 0, n = blobs.L i & i++ )
List&IntPoint& edgePoints = blobCounter.GetBlobsEdgePoints( blobs[i] );
List&IntPoint& corners = PointsCloud.FindQuadrilateralCorners( edgePoints );
g.DrawPolygon( bluePen, ToPointsArray( corners ) );
bluePen.Dispose( );
g.Dispose( );
As we can see on the image above, we may have different objects and quadrilateral finder provides different results
for them. For shapes which really look like quadrilateral, the quadrilateral finder is able to find their corners more
or less correctly (problem may occur in the case if object has rounded corners). But for other types of objects
(circles, starts, etc.), quadrilateral finder does not provide any good result. And this is correct, since this routine
supposes the given shape is really quadrilateral.
Now, when we made the assumption that a subjected object is quadrilateral and we got its corner, we just need to see
how good is the fit of the object into the quadrilateral with those found corner - we need to make sure there are no edge
points of the given shape which are too far away from the edge of the assumed quadrilateral. And here we'll apply the same
algorithm as we used for circle checking. The only difference is the way of calculating distance between point and the
closest quadrilateral' edge ...
int cornersCount = corners.C // should be 4 for quadrilateral
// 1 - prepare for calculations of distance between a point
and the quadrilateral
// lines coefficients (for representation as y(x)=k*x+b)
double[] k = new double[cornersCount];
double[] b = new double[cornersCount];
double[] div = new double[cornersCount]; // precalculated divisor
bool[] isVert = new bool[cornersCount];
for ( int i = 0; i & cornersC i++ )
IntPoint currentPoint = corners[i];
IntPoint nextPoint = ( i + 1 == cornersCount ) ?
corners[0] : corners[i + 1];
if ( !( isVert[i] = nextPoint.X == currentPoint.X ) )
k[i] = (double) ( nextPoint.Y - currentPoint.Y ) /
( nextPoint.X - currentPoint.X );
b[i] = currentPoint.Y - k[i] * currentPoint.X;
div[i] = Math.Sqrt( k[i] * k[i] + 1 );
// 2 - calculate distances between edge points and quadrilateral sides
float meanDistance = 0;
for ( int i = 0, n = edgePoints.C i & i++ )
float minDistance = float.MaxV
for ( int j = 0; j & cornersC j++ )
float distance = 0;
if ( !isVert[j] )
distance = (float) Math.Abs(
( k[j] * edgePoints[i].X + b[j] - edgePoints[i].Y )
/ div[j] );
distance = Math.Abs( edgePoints[i].X - corners[j].X );
// finding distance to the closest side
if ( distance & minDistance )
minDistance =
meanDistance += minD
meanDistance /= edgePoints.C
The above code does the same as we did with circles - it goes through the list of all provided shape's
edge points and finds distance between them and the assumed shape. Since we deal here with quadrilateral,
the distance between point and the assumed quadrilateral is calculated as a distance to the closest
quadrilateral's side. In the end of the above calculations we receive the same as before - mean distance
between given edge points and the edge of the assumed quadrilateral. If the mean distance is not greater
than a certain limit, then the shape seems t otherwise it is not. This check is
done in the similar way like before:
// get bounding rectangle of the corners list
IntPoint minXY, maxXY;
PointsCloud.GetBoundingRectangle( corners, out minXY, out maxXY );
IntPoint rectSize = maxXY - minXY;
float maxDitance = Math.Max( minAcceptableDistortion,
( (float) rectSize.X + rectSize.Y ) / 2 * relativeDistortionLimit );
return ( meanDistance &= maxDitance ); // true for quadrilateral
Same as with circles detection, the code for detection quadrilaterals was put into the AForge.NET framework:
And here is a small sample to test it:
// check each object and draw polygon around objects, which
// are recognized as quadrilaterals
for ( int i = 0, n = blobs.L i & i++ )
List&IntPoint& edgePoints = blobCounter.GetBlobsEdgePoints( blobs[i] );
List&IntPoint&
if ( shapeChecker.IsQuadrilateral( edgePoints, out corners ) )
g.DrawPolygon( redPen, ToPointsArray( corners ) );
As we can see on the picture above, only quadrilaterals were highlighted with a border. Other shapes, like circles, triangles,
stars, etc., were filtered out, which means that although quadrilateral finder gave us some points as 4 corners, the further check
for fitting assumed quadrilateral did not pass. Which is nice.
Detection of triangles
Idea of detecting triangles is almost the same like the idea of detecting quadrilaterals - just need to find 3 corners of the
supposed triangle and then check the fitting of specified edge points into the assumed triangle. More of it, it is even based on
the same API - .
Why is it so? Because if we take a closer look into documentation of
we may find that the function returns only 3 corners, if it cannot find the 4th one, which is the case with triangles.
For example, using the code below we can make sure it really works - we'll highlight quadrilaterals and triangles with different colors:
for ( int i = 0, n = blobs.L i & i++ )
List&IntPoint& edgePoints = blobCounter.GetBlobsEdgePoints( blobs[i] );
List&IntPoint& corners = PointsCloud.FindQuadrilateralCorners( edgePoints );
g.DrawPolygon( ( corners.Count == 4 ) ? redPen : bluePen,
ToPointsArray( corners ) );
Since the previously written code for checking fitting of provided edge points into assumed quadrilateral does not depend on
number of corners (that code actually works not just for quadrilaterals, but for any convex polygon), we can use it for triangles
as well. So nothing more needs to be written - check of triangles is the same as chec we just distinguish
these shapes by number of corners found by quadrilateral finder.
Here is a test code with new framework's function -
// check each object and draw triangle around objects, which
// are recognized as triangles
for ( int i = 0, n = blobs.L i & i++ )
List&IntPoint& edgePoints = blobCounter.GetBlobsEdgePoints( blobs[i] );
List&IntPoint&
if ( shapeChecker.IsTriangle( edgePoints, out corners ) )
g.DrawPolygon( redPen, ToPointsArray( corners ) );
Rectangles, squares, equilateral triangles, etc.
Once we made a check for quadrilateral shape and got its 4 corners, we may do some further checks to detect sub-type
of the quadrilateral: trapezoid, parallelogram, rectangle, rhombus or square. These checks are based on checking angles
between opposite/adjacent sides and their length. First we check two opposite sides - if they are parallel, then we get
at least trapezoid. Then we check two other sides - if they are parallel two, then we have parallelogram. If two adjacent
sides are perpendicular, then we got rectangle. The last check is to compare length of two adjacent sides - if they are
equal, then parallelogram becomes rhombus and rectangle becomes square. And of course we need to add small possible error,
so if angle between lines equals to 2 degrees, they are still treated as parallel. The below code shows implementation of
// get angles between 2 pairs of opposite sides
float angleBetween1stPair = Tools.GetAngleBetweenLines(
corners[0], corners[1], corners[2], corners[3] );
float angleBetween2ndPair = Tools.GetAngleBetweenLines(
corners[1], corners[2], corners[3], corners[0] );
// check 1st pair for parallelism
if ( angleBetween1stPair &= angleError )
subType = PolygonSubType.T
// check 2nd pair for parallelism
if ( angleBetween2ndPair &= angleError )
subType = PolygonSubType.P
// check angle between adjacent sides
if ( Math.Abs( Tools.GetAngleBetweenVectors(
corners[1], corners[0], corners[2] ) - 90 ) &= angleError )
subType = PolygonSubType.R
// get length of 2 adjacent sides
float side1Length = (float) corners[0].DistanceTo( corners[1] );
float side2Length = (float) corners[0].DistanceTo( corners[3] );
if ( Math.Abs( side1Length - side2Length ) &= maxLengthDiff )
subType = ( subType == PolygonSubType.Parallelogram ) ?
PolygonSubType.Rhombus : PolygonSubType.S
// check 2nd pair for parallelism - last chence to detect trapezoid
if ( angleBetween2ndPair &= angleError )
subType = PolygonSubType.T
Checking triangle subtype is even simpler. If it's all angles are near to 60 degrees, then we have
equilateral triangle. If not then we check if some of two angles are equal - isosceles triangle. Also
we may need to check if one of the angles equals to 90 degrees - this will give us rectangled triangle.
// get angles of the triangle
float angle1 = Tools.GetAngleBetweenVectors( corners[0], corners[1], corners[2] );
float angle2 = Tools.GetAngleBetweenVectors( corners[1], corners[2], corners[0] );
float angle3 = Tools.GetAngleBetweenVectors( corners[2], corners[0], corners[1] );
// check for equilateral triangle
if ( ( Math.Abs( angle1 - 60 ) &= angleError ) &&
( Math.Abs( angle2 - 60 ) &= angleError ) &&
( Math.Abs( angle3 - 60 ) &= angleError ) )
subType = PolygonSubType.EquilateralT
// check for isosceles triangle
if ( ( Math.Abs( angle1 - angle2 ) &= angleError ) ||
( Math.Abs( angle2 - angle3 ) &= angleError ) ||
( Math.Abs( angle3 - angle1 ) &= angleError ) )
subType = PolygonSubType.IsoscelesT
// check for rectangled triangle
if ( ( Math.Abs( angle1 - 90 ) &= angleError ) ||
( Math.Abs( angle2 - 90 ) &= angleError ) ||
( Math.Abs( angle3 - 90 ) &= angleError ) )
subType = ( subType == PolygonSubType.IsoscelesTriangle ) ?
PolygonSubType.RectangledIsoscelesTriangle :
PolygonSubType.RectangledT
All the above code is available in AForge.NET Framework as
Here is a quick test of it and some pictures with result:
// dictionary of color to highlight different shapes
Dictionary&PolygonSubType, Color& colors =
new Dictionary&PolygonSubType, Color&( );
colors.Add( PolygonSubType.Unknown, Color.White );
colors.Add( PolygonSubType.Trapezoid, Color.Orange );
colors.Add( PolygonSubType.Parallelogram, Color.Red );
colors.Add( PolygonSubType.Rectangle, Color.Green );
colors.Add( PolygonSubType.Square, Color.Blue );
colors.Add( PolygonSubType.Rhombus, Color.Gray );
colors.Add( PolygonSubType.EquilateralTriangle, Color.Pink );
colors.Add( PolygonSubType.IsoscelesTriangle, Color.Purple );
colors.Add( PolygonSubType.RectangledTriangle, Color.SkyBlue );
colors.Add( PolygonSubType.RectangledIsoscelesTriangle, Color.SeaGreen );
for ( int i = 0, n = blobs.L i & i++ )
List&IntPoint& edgePoints = blobCounter.GetBlobsEdgePoints( blobs[i] );
List&IntPoint&
if ( shapeChecker.IsConvexPolygon( edgePoints, out corners ) )
// check subtype
PolygonSubType subType = shapeChecker.CheckPolygonSubType( corners );
using ( Pen pen = new Pen( colors[subType], 2 ) )
g.DrawPolygon( pen, ToPointsArray( corners ) );
Taking a look at the above pictures and colors of highlighting borders, we may see that all triangles'
and quadrilaterals' sub-types were recognized quite successfully. You may ask - Why there is one triangle
with white border, which corresponds to unknown sub-type? Because it is just a triangle - not equilateral,
not isosceles and not rectangled - sub-type is unknown.
Test on a real image
Now, let's try all the above ideas on some real world image. Consider the image below. Our task is to find all
coins (circles) and see what else we can detect.
As a first step we need to remove background - make it completely black, so we could easily locate stand alone
objects. For this purpose we may try using
image processing routine:
// lock image
BitmapData bitmapData = bitmap.LockBits(
new Rectangle( 0, 0, bitmap.Width, bitmap.Height ),
ImageLockMode.ReadWrite, bitmap.PixelFormat );
// step 1 - turn background to black
ColorFiltering colorFilter = new ColorFiltering( );
colorFilter.Red
= new IntRange( 0, 64 );
colorFilter.Green = new IntRange( 0, 64 );
colorFilter.Blue
= new IntRange( 0, 64 );
colorFilter.FillOutsideRange =
colorFilter.ApplyInPlace( bitmapData );
Now we'll do detection of blobs. Although we have some noisy pixels, which were left from bright areas
of background, we are not going to use any noise suppression image processing routines. We'll just instruct
blob counter to filter objects by size, so all tiny objects are ignored:
// step 2 - locating objects
BlobCounter blobCounter = new BlobCounter( );
blobCounter.FilterBlobs =
blobCounter.MinHeight = 5;
blobCounter.MinWidth = 5;
blobCounter.ProcessImage( bitmapData );
Blob[] blobs = blobCounter.GetObjectsInformation( );
bitmap.UnlockBits( bitmapData );
And finally we'll check type of each object and highlight them with different color:
// step 3 - check objects' type and highlight
SimpleShapeChecker shapeChecker = new SimpleShapeChecker( );
Graphics g = Graphics.FromImage( bitmap );
Pen redPen = new Pen( Color.Red, 2 );
Pen yellowPen = new Pen( Color.Yellow, 2 );
Pen greenPen = new Pen( Color.Green, 2 );
Pen bluePen = new Pen( Color.Blue, 2 );
for ( int i = 0, n = blobs.L i & i++ )
List&IntPoint& edgePoints =
blobCounter.GetBlobsEdgePoints( blobs[i] );
if ( shapeChecker.IsCircle( edgePoints, out center, out radius ) )
g.DrawEllipse( yellowPen,
(float) ( center.X - radius ), (float) ( center.Y - radius ),
(float) ( radius * 2 ), (float) ( radius * 2 ) );
List&IntPoint&
if ( shapeChecker.IsQuadrilateral( edgePoints, out corners ) )
if ( shapeChecker.CheckPolygonSubType( corners ) ==
PolygonSubType.Rectangle )
g.DrawPolygon( greenPen, ToPointsArray( corners ) );
g.DrawPolygon( bluePen, ToPointsArray( corners ) );
corners = PointsCloud.FindQuadrilateralCorners( edgePoints );
g.DrawPolygon( redPen, ToPointsArray( corners ) );
redPen.Dispose( );
greenPen.Dispose( );
bluePen.Dispose( );
yellowPen.Dispose( );
g.Dispose( );
So, what did we get? As we can see from the above picture, all coins (circles) were detected successfully
and highlighted with yellow borders. Also we got one rectangle in green border, one quadrilateral (it is actually
trapezoid, we just did not make appropriate check) in blue border and 2 unknown shapes in red borders.
Everything seems to be fine except of these two last shapes in red. Why they were not recognized? With gray
box it is more or less obvious - since it has rounded corners, the quadrilateral finding routine was a bit
confused and picked up those corners, which seem to be best from its algorithm's point of view. After that
shape fitting has failed, since some edge points of the box are quite away from the supposed quadrilateral.
With Panasonic battery the failure reason is caused by the "+" connector, which was chosen as wrong corner.
Although we got two unrecognized shapes, it does not mean that all of the above ideas about shape checking
are absolutely bad and cannot be used. These two failures are actually caused not by failure of the described
shape fitting algorithm, but by quadrilateral finder, which has failed to find proper corners. And it has a
reason for this. So if we would use another algorithm for finding corners of the supposed quadrilateral, then
things could work better for the last two objects.
Conclusion
As it was already mentioned in the article, all of the code became available as part of the . Except of the few mentioned functions, there is a
which encapsulates them
all, plus has some additional methods. For example, we already have seen, that there is a method, which checks
if the specified set of edge points form a quadrilateral and provides its corners on success, which are detected
by quadrilateral finder implemented in the framework. However, there is also another method, which allows user
to specify his own quadrilateral corners. These gives user a bit more flexibility, since he may use another algorithm
for finding corners of quadrilateral and then just use framework's method for checking fitting of edge points into
the assumed quadrilateral.
In addition the framework provides a sample application, which demonstrates usage of the implemented functions
and allow to do some quick experiments. The sample application is available as part of framework's distribution
and also can be download using links in the top of the article.