=Paper=
{{Paper
|id=Vol-1814/paper-04
|storemode=property
|title=Irregular Objects. Shape Detection and Characteristic Sizes
|pdfUrl=https://ceur-ws.org/Vol-1814/paper-04.pdf
|volume=Vol-1814
|authors=Sergey O. Bochkarev,Igor B. Litus,Natalia S. Kravchenko
}}
==Irregular Objects. Shape Detection and Characteristic Sizes==
https://ceur-ws.org/Vol-1814/paper-04.pdf
Irregular Objects. Shape Detection and
Characteristic Sizes
Sergey O. Bochkarev1,2 , Igor B. Litus2 , Natalia S. Kravchenko1
1
Ural Federal University, Yekaterinburg, Russia;
2
Nizhny Tagil Institute of Metal Testing, Nizhny Tagil, Russia
sergey.bochkarev@urfu.ru
Abstract. In this work, results of detecting the objects of irregular form
with image analysis are described. The offered algorithm can reduce an ir-
regular object to one of the standard shape, in which it looks like, and
choose characteristic sizes of this standard shape, where the object area
stays constant.
Keywords: Computer vision, image analysis, object search, contour
search, shape detection
1 Introduction
Nizhny Tagil Technological Institute of Ural Federal University carries out in-
vestigations of shape detection of irregular plate objects with image analysis.
Problem of research includes three subproblems:
1. Find contour of object on a picture. It is considered that the source image
is a binary-colored one. Binarization of multicolored images is the subject
of another research. The object perimeter and area are formed by using
contour.
2. Detect standard shape, in which it looks like. In this work, the following four
shapes are examined: circle, rectangle, rhombus, and ellipse. Nevertheless,
real objects can have very complex shape.
3. Find characteristic sizes of chosen standard shape, using equation (1). Char-
acteristic sizes are shown in Table 1.
Scontour = Sshape . (1)
The opencv library is used to find contour of the object and its characteristics.
The following three criteria of contour are used to detect the standard shape:
– rectness that characterizes closeness of contour to rectangle; it is calculated
by Eq. 2
Scontour
rec = , (2)
Srect
where rec is the rectness, Scontour is the area of a contour, Srect is the area
of minimum rectangle that contains this contour. It can be found by the
method GetMinAreaRect [2] in opencv. rec ≤ 1 (rec = 1 for the rectangle).
29
Table 1. Characteristic sizes of standard shapes.
Circle d–diameter
a–width
Rectangle
b–height
a–width
Rhombus
h–height
a–semimajor axis
Ellipse
b–semiminor axis
– circless that characterizes closeness of the contour to a circle; it is calculated
by Eq. (3)
Scontour
cir = , (3)
Scirle
where cir is the circless, Scontour is the area of a contour, Scirle is the area
of enclosing circle that contains this contour; it can be found by method
MinEnclosingCircle [3] in opencv. cir ≤ 1 (cir = 1 for the circle);
– compactness [1] is an universal shape criterion; if the contour is close to
the standard shape, their compactnesses are approximataly equal; it is cal-
culated by Eq. (4)
P2
C= , (4)
S
where C is the compactness, P is the perimeter of the contour, S is the area
of the contour.
2 Shape detection
All standard shapes are convex ones, but real irregular objects can have a lot of lo-
cal concavities. So before calculations, a source contour must be smoothed and
perimeter must be decreased to make it closer to perimeter of the standard
form. Real and smoothed contours are shown in Fig. (1). It can be done by
30
the GetConvexHull [4] method in opencv. It is interesting to note that perime-
ter of the source contour is 6804px, but perimeter of the smoothed contour is
only 3702px.
Fig. 1. Source and smoothed contour.
Scontour
The coefficient k = is used to return to real contour in the next
Shull
calculations. So, characteristic size a of a real contour can be calculated from
ahull
size of the smoothed contour with this coefficient: acontour = √ .
k
Combination of three criteria (rectness, circless, and compactness) does not
allow to detect one of the standard shape uniquely. The next strategy is used:
if rec > 0.8 or cir > 0.8, than contour is counted as a rectangle or a circle
respetively. In other cases, it is neccesary to choose a shape, which compactness
is closest to the smoothed contour compactness.
3 Compactness of standard shapes
Compactness of standard shapes can be calculated by the following equations:
– circle (see Eq. 5)
2
(2πr)
C= = 4π; (5)
πr2
the circle compactness is constant; it is minimum possible compactness; in all
cases C ≥ 4π. The characteristic
r parameter (diameter) can be calculated
Scontour
using Eq. (1) as d = ;
4π
– rhombus (see Eq. 6)
(4a)2 16
C= 2 = , (6)
a sin α sin(α)
rhombus compactness C ≥ 16 (C = 16 in the case of α = π/2, i.e. quadrate);
31
– rectangle (see Eq. 7):
(2(a + b))2 4a2 + 8ab + 4b2
C= = , (7)
ab ab
rectangle compactness C ≥ 16 (C = 16 in the case of a = b, i.e. quadrate)
– ellipse perimeter is calculated with elliptic integral [5] (see Eq. 8)
Zπ/2p
P = 1 − e2 cos2 tdt. (8)
0
This intergal cannot be expressed in terms of elementary functions, so the fol-
lowing approximation (Eq. 9) of ellipse perimeter with the maximun error
of 0.63% is used. The strcucture of this formula can help to simplify the fol-
lowing mathematical transformations,
2
πab + (a − b)
P ≈4 . (9)
a+b
In this case, the ellipse compactness can be calculated by Eq. (10)
2
!2
4πab + (a − b)
2
P2 a+b πab + a2 − 2ab + b2
C= = = 16 3 . (10)
S πab πa b + 2πa2 b2 + πab3
The ellipse compactness C ≥ 4π (C = 4π in the case of a = b, i.e. circle).
In the cases of rectangle and ellipse, compactness depends on two parameters,
so, characteristic sizes cannot be determined uniquely. But if relation e = b/a
is used, compactness depends on one parameter, and all similar rectangles and
ellipses have the same compactness. Compactness equations are shown on Ta-
ble 2.
Table 2. Characteristic parameters of standard forms.
Shape Characteristic sizes Compactness parameter Compactness formula
Circle d–diameter — C = 4π
a–width 4 + 8e + 4e2
Rectangle e = b/a–ratio C(e) =
b–height e
a–base 16
Rhombus α–rhombus angle C(α) =
h–height sin(α)
2
a–semimajor axis (π − 2)e + e2 + 1
Ellipse e = b/a–ratio C(e) = 16
b–semiminor axis πe3 + 2πe2 + πe
32
4 Characteristic parameters
In the case of circle, characteristic size (d) is calculated uniquely using Eq. (1)
with Eq. (11) r
1 Scontour
d= . (11)
2 π
In the case of rhombus, characteristic sizes (a, h) are calculated with Eq. (6)
by Eq. (12 and Eq. 13)
r s r
S S S · P2 P
a= = = = , (12)
sin α 16/C S · 16 4
h = S/a. (13)
In the cases of rectangle and ellipse, characteristic sizes can be calculated
with well-known area equations S = ab and S = πab respectively. Using the com-
pactness parameter r e = b/a, these equations are transformed
r to S = a2 e and
S S S S
S = a2 πe, so a = , b = for rectangles, and a = ,b= for ellipses. It
e a πe πa
means that parameters e and S are sufficiant to calculate the characteristic sizes.
In the case of rectangle, e can be expressed with equation in Table 2 by Eq. (14)
√
C − 8 ± C 2 − 16C
e= . (14)
8
In the case of rhombus, dependence C(e) is very complex, but this equation
can be solved numerically.
5 Results of detection
This algorithm was applied to some real irregular objects. In this section some
examples are introduced. All results have gathered in tables. The first column
contains the original image, image with contour, and detected shape. The sec-
ond column represents the calculated data. Bold font marks the base for shape
detection.
Notations in tables are
– S is the area of contour (smoothed)
– P is the perimeter of contour (smoothed)
– C is the compacntess of contour (smoothed)
– rec is the rectness
– cir is the circless
– Cr is the compacntess of rectangle
– Cc is the compacntess of circle
– Crh is the compacntess of rhombus
– Ce is the compacntess of ellipse
– a, b, h, α, d are the characteristic parameters of detected figure (depend-
ing on shape).
33
5.1 Generated figures
This subsection contains image analysis of figures drawn upon the graphic prim-
itives (Table 3). Columns 1,2 present source figures, columns 3,4 present artifi-
cially eroded figures.
Table 3. Generated figures
generated figures ragged figures
Circle Circle
S = 13074 S = 11088
P = 405 P = 470
C = 12.59 C = 19.98
rec = 0.79 rec = 0.78
cir = 0.91 cir = 0.85
Cc = 12.56 Cc = 12.56
Ce = 12.56 Ce = 12.58
Cr = 16.00 Cr = 16.00
Crh = 16.00 Crh = 16.00
d = 64.51 d = 64.51
Rectangle Rectangle
S = 42182 S = 36323
P = 846 P = 895
C = 16.96 C = 22.05
rec = 1 rec = 0.97
cir = 0.53 cir = 0.59
Cr = 16.96 Cr = 16.94
Crh = 17.93 Ce = 13.37
Ce = 12.56 Crh = 17.88
Cc = 12.56 Cc = 12.56
a = 161, b = 262 a = 154.20, b = 249.34
Rhombus Rhombus
S = 13690 S = 11208
P = 524 P = 576
C = 20.10 C = 29.67
rec = 0.62 rec = 0.64
cir = 0.29 cir = 0.31
Crh = 20.66 Crh = 20.59
Ce = C = 15.60 Ce = C = 15.30
Cr = 18.33 Cr = 18.29
Cc = 12.56 Cc = 12.56
a = 132.95, h = 102.96 a = 128.25, h = 99.63
Ellipse Ellipse
S = 27833 S = 24534
P = 662 P = 711
C = 14.18 C = 14.47
rec = 0.79 rec = 0.77
cir = 0.53 cir = 0.50
Ce = C = 14.21 Ce = C = 14.31
Cr = 17.36 Cr = 17.50
Crh = 18.73 Crh = 19.00
Cc = 12.56 Cc = 12.56
a = 132.95, h = 102.96 a = 128.25, h = 99.63
34
5.2 Real figures similar to standard
This subsection contains image analysis of real figures similar to standard ones
(Table 4).
Table 4. Real figures similar to standard
Circle Rectangle
S = 274433 S = 1472082
P = 3887 P = 5904
C = 12.81 C = 21.32
rec = 0.78 rec = 0.99
cir = 0.83 cir = 0.35
Cc = 12.56 Cr = 21.49
Ce = 12.60 Ce = 21.91
Cr = 16.03 Crh = 26.99
Crh = 16.07 Cc = 12.56
d = 303 a = 699.14, b = 2129.82
Rhombus Ellipse
S = 306123 S = 1075559
P = 4640 P = 3915
C = 21.23 C = 14.25
rec = 0.65 rec = 0.77
cir = 0.26 cir = 0.54
Crh = 23.56 Ce = 13.69
Ce = 16.83 Cr = 16.51
Cr = 19.78 Crh = 17.02
Cc = 12.56 Cc = 12.56
a = 748.29, h = 508.11 a = 699.14, b = 2129.82
5.3 Irregular figures
This subsection contains image analysis of real irregular figures (Table 5).
6 Conclusion
The given algorithm provides to detecting the standard shape of irregular ob-
ject, in which it looks like. Combination of three criteria (rectness, circless, and
compactness) gives good results. Algorithm detects standard shape and charac-
teristic sizes of it using area equivalence and compactness criterion.
35
Table 5. Irregular figures
Rectangle Rhombus
S = 432967 S = 235564
P = 2455 P = 2012
C = 13.92 C = 17.18
rec = 0.92 rec = 0.68
cir = 0.72 cir = 0.45
Cr = 16.01 Crh = 18.43
Ce = 12.66 Ce = 13.59
Cc = 12.56 Cr = 17.21
Crh = 16.03 Cc = 12.56
a = 637.61, b = 679.03 a = 520.92, h = 452.20
Rectangle Ellipse
S = 2298000 S = 852466
P = 6027 P = 3798
C = 15.81 C = 16.92
rec = 0.89 rec = 0.76
cir = 0.51 cir = 0.39
Crh = 23.56 Ce = 15.71
Ce = 16.83 Cr = 18.99
Cr = 19.78 Crh = 21.99
Cc = 12.56 Cc = 12.56
a = 748.29, h = 508.11 a = 699.14, b = 2129.82
References
1. Rick Gillman. Geometry and Gerrymandering, Math Horizons, Vol. 10, 1 (Sep,
2002) 10-13
2. GetMinAreaRect Method. http://www.emgu.com/wiki/files/1.5.0.0/Help/html/748c1975-
172a-9b73-a102-cdb695182d68.htm
3. MinEnclosingCircle Method. http://www.emgu.com/wiki/files/2.4.0/document/html/784a59ae-
b9a2-4eb0-b94b-3aed1614e4b0.htm
4. Convex hull. http://docs.opencv.org/2.4/doc/tutorials/imgproc/shapedescriptors/hull/hull.html
5. Adlaj, Semjon. An eloquent formula for the perimeter of an ellipse, Notices of the
AMS 76 (8): 1094–1099, doi:10.1090/noti879, ISSN 1088-9477