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