Open access peer-reviewed chapter

Polygonal Approximation of Digital Planar Curve Using Novel Significant Measure

Written By

Mangayarkarasi Ramaiah and Dilip Kumar Prasad

Submitted: November 26th, 2019 Reviewed: March 16th, 2020 Published: April 28th, 2020

DOI: 10.5772/intechopen.92145

From the Edited Volume

Automation and Control

Edited by Constantin Voloşencu, Serdar Küçük, José Guerrero and Oscar Valero

Chapter metrics overview

View Full Metrics

Abstract

This chapter presents an iterative smoothing technique for polygonal approximation of digital image boundary. The technique starts with finest initial segmentation points of a curve. The contribution of initially segmented points toward preserving the original shape of the image boundary is determined by computing the significant measure of every initial segmentation point that is sensitive to sharp turns, which may be missed easily when conventional significant measures are used for detecting dominant points. The proposed method differentiates between the situations when a point on the curve between two points on a curve projects directly upon the line segment or beyond this line segment. It not only identifies these situations but also computes its significant contribution for these situations differently. This situation-specific treatment allows preservation of points with high curvature even as revised set of dominant points are derived. Moreover, the technique may find its application in parallel manipulators in detecting target boundary of an image with varying scale. The experimental results show that the proposed technique competes well with the state-of-the-art techniques.

Keywords

• dominant point
• projection position
• iterative smoothing
• minimal number of points
• polygonal approximation

1. Introduction

Shape representation and shape classification are efficiently facilitated by polygonal approximation. This approach is popular due to its compact representation and insensitive to noise. These salient features are found useful in many applications [1, 2, 3, 4, 5, 6, 7, 8]. The main objective of polygonal approximation is to approximate the shape of a curve using a polygon whose vertices are specified by a subset of points on the curve. These points are referred to as dominant points and are often the points with high curvature. An example is illustrated in Figure 1. A digital curve representing the shape of snowflake is displayed in Figure 1(a), and its identified dominant points are shown in Figure 1(b). The anticipated output of polygonal approximation using dominant point can be seen in Figure 1(c). Broadly polygonal/closed curve approximation of a digital planar curve may be cast as min ε problem or min ≠ problem. In min ε problem, the techniques derive polygonal approximation with specified number of line segments or dominant points. These techniques ensure that the deviation between the curve and the approximate polygon is minimal, condition to the specified number of dominant points. Min # techniques derive polygonal approximation with a specified error. These techniques generate the approximate polygon with minimal number of dominant points while ensuring the measure of closeness is not larger than the specified error. In recent years, there are many dominant point-based polygonal approximation techniques that were presented in the literature [9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19].

And few older ones can be found in [20, 21, 22]. The techniques presented in [9, 10, 12, 20, 21] use reverse polygonization, where instead of detecting the real points the techniques make a search to detect redundant points and delete points iteratively. The methods in [11, 15] use breakpoint suppression, where the techniques apply criterion measure on the finest approximated set of points to suppress the redundant points and make the approximation. The methods in [3, 13, 16, 18] present a solution using dynamic programming, where the techniques make exhaustive search to detect points on curve, thereby making final approximation. The method in [14] makes polygonal approximation by detecting ADSS (Approximate Digital Straight Segment). The method in [17] uses MIP (mixed integer programming) model. The method in [19] uses vertex relocation procedure around neighbors. In this method, while approximating the output curve by detecting the dominant point, the technique allows neighborhood points to become a dominant point provided that new dominant point facilitates in reduction of approximation error. The method in [22] uses split and merge, where the method makes a search to find the points with maximum deviation in the splitting stage using the proposed criterion function and merge all the points identified in the splitting stage using the threshold value. Most of the dominant points [9, 10, 11, 12] detecting methods use the magnitude of orthogonal projection of a point on the line segments, which connect adjacent high curvature points to influence the process of detecting dominant points. The methods in the literature [9, 10, 11, 12, 14, 15, 20, 23] do not address the issue where the projection of point lies beyond its candidate line segment, where the situation may be often anticipated during approximation. The techniques that neglect to check this criterion may miss good curvature points, which are critical for shape representation. The technique proposed in this chapter measures the positions of projections of a point on the curve, thereby invoking different metrics for computing the significant measure of the dominant points. This practice makes the proposed technique to preserve the original shape of the curve even at very minimal number of dominant points. Such characteristic is very essential for compact representation. And it is very essential for object detection and shape classification applications. Especially, the proposed technique can facilitate the parallel manipulators in cutting and milling operations by preserving the actual shape of the target boundary points. The rest of the chapter is organized is as follows: Section 2 presents a brief review of some of the state-of-the-art methods along with an insight into their demerits wherever possible. Section 3 presents the proposed work. Section 4 summarizes the experimental results. Section 5 concludes the chapter.

2. Background

Several polygonal approximation techniques have been proposed in the recent decades. Some of them use various optimization approaches [3, 13, 16, 17, 18, 19]. On the other hand, there are other techniques that use local/global geometric features of a curve to influence the process of determining the polygon with minimal number of line segments [9, 10, 11, 12, 23, 24, 25, 26], and these techniques prove its competence against many real-time datasets. Among these, this section briefly analyzes some of the bench mark techniques.

Prasad [23] proposed a non-parametric framework to detect points of high curvature. The framework uses the maximum deviation incurred between pixels from a digitized boundary as an upper bound to make approximation. The authors proved that the analytical bound can be incorporated by dominant point detection framework to get rid of specification in terms of the tolerable error (for min # approaches) or the number of points (for min ϵ approaches). The authors established the robustness of their framework against scaling invariance as well as noise tolerance. However, there are applications in which the curve needs to be approximated using a specified number of dominant points, which is not possible through this framework. Though the approximation bounded below to digitization value, points detected on the curve seem to be redundant for human visual perception. Prasad [24] used metrics such as precision and reliability as measures to fit the polygon edges. Depending upon the threshold values for these measures, the technique produces coarser or finer approximation. Thus, this technique can flexibly control the degree of smoothness required for an application. And also the paper suggests some performance metrics to quantify the techniques. Parvez [19] obtained the digital boundary using contour extraction techniques. The objective of the method was to produce approximate polygon with minimal error possible. To attain this goal, the method relaxes the criteria that dominant points need not be on the contour. The technique computes neighborhood points for every point pi on the contour Cd and introduces a new point on the contour provided its presence should reduce the approximation error. The neighborhood points are not the ones computed using 4 connected graph or 8 connected graph; instead, the technique adaptively defines the width for every point on the curve, and thereby, it obtains the neighborhood points. Fernandez [25] produced symmetric approximation for symmetric contours. The technique obtains first initial point p1 as the farthest in terms of distance from the centroid of the curve. The next point p2 is the farthest to p1 . The method proceeds to find point p4 , which is farthest from p2 , and point p3 , which is farthest from p1 . Likewise, the technique obtains the all possible line segments such as {p1 , p2 }, {p3 , p4 }, until the maximum deviation from the curve does not exceed a threshold value that constitutes the boundary point set. The authors demonstrate that their method of choosing initial points ensures symmetricity. The technique then identifies all possible candidate points (q1 , q2 , ..., qm ) from the boundary point set between every two initial points and computes a significant value by ensuring symmetry property. Additionally, the technique presents various thresholding methods to normalize the significant values of the boundary points. Though the technique produces symmetric approximation for symmetric curve, it did not establish geometric invariance. And in real-time data sets, in most of the cases, the points are always distributed asymmetrically on the planar curve. The main objectives of this chapter are to i) present a framework that considers the projection position of a point and thereby invokes the proper criterion measure to compute the contribution; ii) produce output polygon without missing significant points; iii) produce polygon with minimal possible number of points; and iv) present a technique that is reasonably strong enough against rotation invariance. These objectives are achieved and demonstrated through experimentations of the proposed technique using benchmarking data sets.

3. Proposed work

3.1 Problem formulation

The problem formulation is as follows: let Cd  = {p1 , p2 , …pn } where pi  = (xi ,yi ) is a digital curve consisting of n points in clockwise direction in the discrete two-dimensional space. Such curves are the ones extracted from the boundaries of the digital images using contour detection or edge detection methods. The coordinates of these n points are integers since these points are extracted from the digital boundary. The objective of polygonal approximation of Cd is to derive a subset D = {p1 , p2 , …, pm } from the super set of Cd , subject to the condition the polygon formed by the elements of D should represent the shape of the original curve. The technique starts with any three consecutive points pi , pj and pk on the curve Cd , to detect the collinearity of these points (pi , pj , pk ), the distance measured from a point pj to the line segment connecting pi and pk . The method shall conclude the three points are collinear, provided the measured distance is very minimal. On the other side, the method shall conclude non-collinearity, provided the measured distance is not very minimal and thus pj becomes an element of D. Thereby, the polygonal approximation technique finds all the elements of D. With this problem formulation, our chapter focuses on the choice of the significant measure metric. Conventionally, the distance metric is the length of the line dropped from the point pj on the line segment pipk . This is being referred to as the perpendicular distance. This metric is generally good for smooth curves, but in some cases (explained later), it may miss significant points and reject sharp turn, which are essential in shape representation applications. Dunham [27] makes initial approximation using distance to a line segment. Ramaiah [28] uses distance to a line segment as a measure to make polygonal approximation, but the metric used in the technique to compute deviation is capable of preserving sharp turnings but fails to preserve the original shape of digital curve. Apart from the criterion measure proposed in any technique, the methodology is also an important factor to produce the output polygon without compromising its actual shape. This implies that the used metric in [28] is unsuitable for iterative smoothing. The framework proposed in this chapter automatically chooses the suitable significant measure metric based on the candidate point projection, as explained next.

3.2 Proposed technique

In this section, we present our proposed method to make polygonal approximation of Cd . The initial segmentation points are obtained using Freeman chain code [28], such as given in Algorithm 1. These initially segmented points are referred as initial set of dominant points. Example of initial segmentation for the snowflake curve is shown in Figure 1(a) and (b) where the dominant points are highlighted in bold markers and the final approximated curve is given in Figure 1(c).

To compute the significant measure of every initial dominant point sk , the proposed method uses the following steps: consider the scenario in Figure 2(a) where, namely sk-1 , sk and s k+1 are three dominant points on the curve with the following traversing sequence: s k-1- > s k - > s k+1. It may be interpreted as these three points are collinear by assuming the projections of a point sk that lies on the line segment, which connects (s k-1 s k+1). As a consequence, the approximation technique [9, 10, 11, 12, 14, 15, 20, 23, 29, 30] may decide to drop sk . In this scenario, the projection of a point (sk ) lies between its candidate line segment (s k-1 s k+1). Figure 3 shows the various anticipated position for possible projection of a dominant point (sk ) on the x-y plane. The proposed metric detects the position of projection. In order to predict the position of a projection, the proposed technique uses the following steps: translate the line segment connecting s k-1 and s k+1 so that the point Si coincides with the origin of the x-y coordinate system and measures the amount of angle produced by the translated line segment with the x axis. In order to align the translated line segment with the x axis, rotate the line segment with a computed amount angle. The actual x-y coordinate system and new transformed coordinate systems are displayed in Figure 2(a) and (b). In the next step, by checking transformed x coordinate of sk ’, the method chooses metric to compute the significant measure. If the x coordinate of sk ’ is less than 0, then the significant measure sig(s k ) is computed using Eq. (1) (see Figure 3(a)). If x k ’ of sk lies between 0 and the x coordinate of si , then the significant measure is computed using Eq. (2) (see Figure 3(b). If the x k value is greater than x j of s k+1, then the significant measure of sk is computed using Eq. (3) (see Figure 3(c)).

sig s k = k = s k 1 s k + 1 s x k s x k 1 2 + s y k s y k 1 2 E1
sig s k = k = s k 1 s k + 1 S y k E2
sig s k = k = s k 1 s k + 1 s x k s x k + 1 2 + s y k s y k + 1 2 E3

In all the three equations (Eqs. (1)–(3)), k range is k-1 < =k < =k + 1. (Note: the accent sign indicates the coordinates in the transformed coordinate system). While computing the significant measure associated with a dominant point, let us say sk , the significant measure of every non-dominant point/boundary point lies between its candidate line segment and is accumulated to define the significance measure of sk . These steps are repeated for each dominant point in the initial set, before making the decision to remove redundant dominant points in the next step. After measuring the significant measure of all initial dominant points, the proposed method removes the dominant point with minimal significant measure. If more than one dominant point has the same minimal significant measure, the dominant point appearing first in the order of sequence is removed. The steps to remove the dominant point and produce the final output polygon are given in Algorithm 2.

Algorithm 1. CIDP (Compute initial set of dominant points).

Input: The inputs are the coordinates of the boundary points.

Cd = pi (xi,yi),i=1,2,3…..n; n boundary points.

Output: The outputs are the curve indices of initial dominant points.

Begin

Case 1: i=0

If (x(0)-x(n-1) != x(1)-x(0)) or ((y(1)-y(0) != y(0)-y(n-1)) then

D[0]= 0;

Case 2: i=n-1

If (x(n-1)-x(n-2) != x(0)-x(n-1)) or (y(n-1)-y(n-2) != y(0)-y(n-1))

D[j]=i;

Default:

While (i<n-1)

If (x(i)-x(i-1) != x(i+1)-x(i)) or (y(i+1)-y(i) != y(i)-y(i-1))

D[j] = i

End.

Algorithm 2. Polygonal approximation by computing the significant measure of IDP.

Input: Digital curve Cd , Number of dominant points (k) in the output polygon.

Output: Output polygon with the specified number of dominant points (k).

Begin.

Step 1: Invoke the function CIDP.

Step 2: Compute significant measure associated with all initial dominant points (sk’s).

Step 3: Repeat.

1. Identify the dominant point s k with minimal significant measure in Cd .

2. Remove the dominant point s k and recalculate the significant measure of at sk-1 and sk + 1 .

3. Compute the performance measures with the available dominant points

Until (No. of DPs == k).

End

4. Experimental results

The proposed technique is tested on a variety of challenging curves to demonstrate its efficiency. The results are presented for two experiment sets. The experiment set 1 consists of synthetic curves usually used in the literature [9, 11, 16, 19, 24, 25, 31, 32, 33, 34, 35, 36, 37, 38]. In experiment 2, the proposed method is tested extensively with images in MPEG data set [39]. We first present the quality assessment metrics for polygonal approximation of digital curves. Then, we present the results on the two experimental sets. Additionally, we include one experiment to demonstrate geometric invariance of the proposed technique.

4.1 Quality assessment

The best method to assess output of polygonal approximation is visual perception. Thus, we include extensive qualitative results. Moreover, we include quantitative performance measures as well for comparison of the performance of the tested methods, including the proposed technique. This chapter considers the following metrics to measure the goodness of the results: (i) compression ratio (CR), (ii) integral square error (ISE), (iii) figure of merit (FOM), (iv) weighted sum of square errors (WE), (v) modified version of WE (WE2). Details of these metrics are provided in Table 1. These metrics are taken from [9, 10, 11, 15, 19, 33, 36]. The readers interested in them are encouraged to read these articles and the references therein.

Metric Indicator of goodness Mathematical representation
CR Larger is better CR = n k , where n is the number of points in the initial segmentation, while k is the number of dominant points in the final polygonal approximation.
ISE Smaller is better ISE = k = 1 n e k , where e k is the perpendicular distance of a point p k on the original digital curve from the nearest line segment on the polygonal approximation.
FOM Larger is better FOM = CR ISE
WE Smaller is better WE = ISE CR
WE2 Smaller is better WE 2 = ISE CR 2

Table 1.

Quality assessment metrics for comparing polygonal approximation methods.

4.2 Experimental set 1

The quantitative performance measure for the synthetic curves chromosome, leaf, semicircle and infinity in experiment set 1 is given in Table 2. The visual shots are shown in Figures 46. The methods in [16, 17, 18, 19, 34, 36, 37] present optimal solutions for the polygonal approximation. The proposed method output is close to optimal solution for all the curves and further supports reduction of the number of dominant points while retaining the shape information of the curve. Table 2 summarizes the results from various articles [9, 11, 15, 16, 17, 18, 19, 23, 24, 26, 31, 32, 33, 34, 35, 36, 37, 38] for the given input synthetic curves. For the chromosome curve display using 15 amount of dominant points, the proposed technique produces a low value for ISE than the method in [32, 33, 34]. The snapshot of chromosome curve at 6 number of points using the proposed method as well as by the methods [9, 23, 24] snapshots can be found in Figure 4. For the leaf curve, where the output curve at 21 number of dominant points, the proposed method produces the low value for ISE than [11, 24, 34] (in turn FOM value is high, which is appreciable) and high value than [19]. The snapshot for leaf output curve produced by the proposed method along with some of the state-of-the-art methods results is displayed in Figure 5. The final synthetic curve for this experiment set is a curve that intersects itself, that is, infinity-shaped curve. In the attempt of producing the output curve using 10 number of points, the proposed produce the minimal possible error than [11, 26]. And also the summarized results reveal that the proposed method output is better than [9, 11, 19, 24, 26, 33] in terms of ISE, WE and FOM. The graphic shots for the same can be found in Figure 6. According to human visual perception, four points are sufficient enough to represent the infinity curve; please see Figure 6(g). On the outset, it is perceived that the proposed technique gives the best or second best ISE values for all the cases. This indicates competitiveness of the proposed technique.

Contour Methods k CR ISE WE FOM
Chromosome Teh and Chin [32] 15 4.00 7.20 1.80 0.56
n = 60 Wu [33] 15 4.00 7.20 1.80 0.56
Masood [9] 12 5.00 7.76 1.55 0.64
Carmona et al. [11] 11 5.45 14.49 2.66 0.38
Parvez [34] 10 6.00 14.34 2.39 0.42
Madrid et al. [26] 12 5.00 5.82 1.16 0.86
Nguyen and Debled-Rennesson [35] 25 3.33 4.06 1.22 0.82
Nguyen and Debled-Rennesson [35] 15 4 5.69 1.42 0.70
Parvez [19] 11 5.45 7.09 1.30 0.77
Aguilera et al. [17] 10 6.00 8.07 1.35 0.74
Lie et al. [18] 14 4.29 7.58 1.77 0.57
Lie et al. [18] 12 5.00 7.96 1.59 0.63
PRO0.6 [24] 11 5.45 11.00 2.02 0.50
RDP2 [24] 8 7.50 59.99 8.00 0.13
RDP3 [24] 6 10.00 91.18 9.12 0.11
Proposed 15 4.00 4.87 1.22 0.82
Proposed 6 10.00 45.49 4.55 0.22
Leaf Teh and Chin [32] 29 4.14 14.96 3.61 0.28
n = 120 Wu [33] 24 5.00 15.93 3.19 0.31
Marji and Siy [15] 17 7.06 28.67 4.06 0.25
Carmona et al. [11] 21 5.71 17.97 3.15 0.32
Parvez [34] 21 5.71 13.82 2.42 0.41
Parvez [19] 21 5.71 11.98 2.10 0.48
Nguyen and Debled-Rennesson [35] 33 3.64 5.56 1.53 0.65
Backes and Bruno [36] 20 6.00 14.1 2.35 0.43
Wang et al. [16] 20 6.00 13.9 2.32 0.43
Madrid et al. [26] 22 5.45 11.16 2.05 0.49
PRO0.6 [24] 21 5.71 21.70 3.80 0.26
PRO1.0 [24] 18 6.67 36.70 5.50 0.18
RDP1 [24] 22 5.45 19.17 3.51 0.28
RDP2 [24] 16 7.50 65.46 8.73 0.11
Proposed 21 5.71 13.25 2.32 0.43
Proposed 16 7.50 44.52 5.94 0.17
Semicircle Teh and Chin [32] 22 4.64 20.61 4.44 0.23
n = 102 Yin [37] 17 6.00 19.78 3.30 0.30
Salotti [38] 14 7.29 17.39 2.39 0.42
Wu [33] 27 3.78 9.01 2.38 0.42
Marji and Siy [15] 15 6.80 22.70 3.34 0.30
Masood [9] 21 4.86 9.82 2.02 0.49
Carmona et al. [11] 26 3.92 4.91 1.25 0.80
Parvez [34] 17 6.00 19.02 3.17 0.32
Nguyen and Debled-Rennesson [35] 25 4.08 5.42 1.33 0.75
Backes and Bruno [36] 14 7.29 19.80 2.72 0.37
Wang et al. [16] 15 6.80 14.30 2.10 0.48
Parvez [19] 15 6.80 18.22 2.68 0.37
Aguilera et al. [17] 14 7.29 17.39 2.39 0.42
Madrid et al. [26] 10 10.20 40.79 4.00 0.25
Lie et al. [18] 14 7.29 29.30 4.02 0.25
PRO 0.6 [24] 18 5.67 18.12 3.20 0.31
Proposed 18 5.67 15.45 2.72 0.37
Proposed 17 6.00 16.59 2.76 0.36
Proposed 14 7.29 17.73 2.43 0.41
Proposed 12 8.50 40.62 4.78 0.21
Infinity Teh and Chin [32] 13 3.46 5.93 1.71 0.58
n = 45 Wu [33] 13 3.46 5.78 1.67 0.60
Masood [9] 11 4.09 2.90 0.71 1.41
Carmona et al. [11] 10 4.50 5.29 1.18 0.85
Parvez [34] 9 5.00 7.35 1.47 0.68
Parvez [19] 7 6.43 7.69 1.20 0.84
Madrid et al. [26] 10 4.50 6.40 1.42 0.70
PRO0.6 [24] 9 5.00 6.29 1.26 0.79
PRO1.0 [24] 7 5.63 19.94 3.54 0.28
RDP1 [24] 9 5.00 6.67 1.33 0.75
RDP2 [24] 7 6.43 19.94 3.10 0.32
RDP3 [24] 5 9.00 53.82 5.98 0.17
Masood [9] 8 5.63 10.24 1.82 0.55
Carmona et al. [11] 6 7.50 31.68 4.22 0.24
Proposed 10 4.50 4.44 0.99 1.01
Proposed 5 9.00 35.61 3.96 0.25

Table 2.

Comparative results of synthetic contour (chromosome, leaf, semicircle, infinity).

4.3 Experiment set 2

In this section, the performance of the proposed methods has been demonstrated using image in MPEG database [39]. Fernandez [25] presents a technique to produce output polygon from a given digital boundary. Authors in [25] demonstrated the efficiency of their method by comparing their results with method [23], which is capable of producing output polygon in non-parametric mode. So the better counterpart method to compare the proposed method is the one proposed in [25]. Table 3 summarizes the results of the proposed method along with the results claimed as the best in [25] for the contours in MPEG database [39]. For the bell-7 contour, the snapshot at 23, 22, 20 and 7 number of dominant points, the proposed method produces a less approximation error in terms of ISE WE WE2 than others mentioned in [9, 11, 23, 25]. Especially the output approximation at 7 DPs, the proposed method and Rosin [40] method produce the curve with the mandatory points compared to others, but the proposed method produces minimal error measure than Rosin [40], and the output can be found in Figure 7(c) and (h).

Contour Methods k CR ISE WE WE2
Bell-7 Fernandez [25] 23 17.65 165.14 9.35 0.53
n = 407 Fernandez [25] 22 18.45 200.93 10.89 0.59
Fernandez [25] 20 20.3 255.083 12.56 0.61
Rosin [40] 7 58 2186.6 37.7 0.65
Masood [9] 20 20.35 408.08 20.5 0.98
Carmona [11] 23 17.69 332.563 8.84 0.23
Prasad [23] RDP 28 14.53 97.60 6.71 0.46
Proposed 22 18.5 176.54 9.54 0.51
Proposed 20 20.35 210.16 10.32 0.50
Proposed 7 58.14 453.91 7.80 0.13
Octopus-14 Fernandez [25] 79 15.33 236.62 15.44 1.00
n = 1211 Fernandez [25] 55 22.02 1270.17 57.69 2.62
Fernandez [25] 50 24.22 1847.81 76.29 3.15
Rosin [40] 43 28.16 2617.37 92.94 3.30
Masood [9] 201 6.02 9268.43 1538.36 255.75
Prasad [23] RDP 55 22.01 392.15 17.81 0.80
Proposed 79 15.33 212.00 13.83 0.90
Proposed 43 28.16 1927.15 68.43 2.42
Ray-17 Fernandez [25] 35 19.69 240.26 12.20 0.62
n = 689 Fernandez [25] 28 24.61 660.00 26.82 1.09
Fernandez [25] 24 28.71 1152.83 40.16 1.40
Rosin [40] 14 49.21 6999.71 142.23 2.89
Masood [9] 24 28.71 749.01 26.09 0.91
Masood [9] 14 49.21 8627.89 175.31 3.56
Prasad [23] RDP 54 12.75 342.36 26.93 2.10
Proposed 35 19.69 208.48 10.59 0.53
Proposed 14 49.21 455.32 9.25 0.18
Chicken-5 RDP [29, 30] 255 5.35 285.54 53.38 9.98
n = 1364 Masood [9] 401 3.40 147.86 43.47 12.79
Carmona et al. [11] 134 10.18 906.52 89.06 8.74
Fernandez [25] 54 25.26 2424.51 95.99 3.80
Prasad [23] RDP 218 6.25 782.53 125.20 20.3
Proposed 255 5.35 275.42 51.49 9.61
Proposed 54 25.26 1994.15 78.95 3.12
Device 6–9 RDP [29, 30] 50 31.80 303.37 9.54 0.30
n = 1590 Masood [9] 84 18.93 189.89 10.03 0.53
Carmona [11] 22 72.27 3395.17 46.98 0.65
Fernandez [25] 33 48.18 348.22 7.23 0.15
Prasad [23] RDP 38 41.84 741.416 17.02 0.42
Proposed 84 18.93 216.24 11.42 0.60
Proposed 22 72.27 761.58 10.54 0.14
Bell-10 RDP [29, 30] 110 10.92 181.25 16.59 1.52
n = 1202 Masood [9] 4 4.95
Carmona [11] 104 11.78 549.52 46.64 3.96
Fernandez [25] 42 28.61 687.56 24.03 0.84
Prasad [23] RDP 81 14.83 326.47 22.01 1.48
Proposed 110 10.92 241.45 22.06 2.02
Proposed 42 28.61 615.77 7.98 0.75
Truck-07 n = 277 RDP [29, 30] 40 6.92 24.45 3.53 0.50
Masood [9] 40 6.92 37.17 5.37 0.77
Masood [9] 11 25.18 1133.29 45.00 1.78
Carmona [11] 12 23.08 1132.45 49.06 2.11
Fernandez [25] 40 6.92 24.15 3.48 0.50
Prasad [23] RDP 33 8.39 59.17 7.05 0.84
Proposed 12 23.08 319.24 13.83 0.59
Proposed 11 25.18 318.34 12.64 0.50
Butterfly-13 RDP [29, 30] 344 5.19 383.30 73.85 14.23
n = 1786 Masood [9] 525 3.40 199.06 58.54 17.22
Carmona-Poyato et al. [11] 171 10.44 1450.70 138.95 13.31
Fernandez [25] 65 27.47 2195.88 79.93 2.91
Proposed 525 3.40 197.58 58.11 17.09
Proposed 65 27.47 2063.91 75.13 2.73

Table 3.

Comparative results for the MPEG database contours.

For the octopus-14 contour, the proposed efficiently produces the output curve with minimal deviation from the original curve compared to others. By observing Figure 8(e), the proposed produces an outlying approximation that is visibly excellent than [25]. In order to support this claim, the output curve for octopus-14 can be found in Figure 8 along with results of [11, 23, 25]. When the input is the ray-17 contour, at 14 number of DPs, the new proposal produces minimal error than the results of [9, 40], and then for the same curve at 35 DPs, the results are good than [25] in terms of ISE, WE and WE2. The graphic shots of the proposed method along with [11, 23, 25, 40] can be found in Figure 9. When the input for the proposed method is chicken-5 curve, the proposed method approximation error measures are compared with results produced by the techniques in [9, 11, 23, 25, 29, 30], and by using all the quantitative performance evaluators, the proposed work produces the output curve with minimal error possible, and the visual snapshots are shown in Figure 10. For the input curve device 6-9, the proposed method results are compared with the results in [9, 11, 23, 25, 29, 30], it is been conceived that the proposed one produces the minimal error (ISE ,WE) than the error produces by the methods in [9, 11, 23, 25]. The output curve for device 6–9 can be found in Figure 11. Then finally for the truck-07 curve, the results of the proposed method at 40, 12 and 11 dominant points are compared with the results of [9, 11, 23, 25]. In all iterations against the mentioned dominant points, the proposed method outperforms well than others. Especially output curve at 11 dominant points, the proposed method efficiently chooses the good curvature points in such a way that the output curve does not deviate much than the original input curve (please see the snapshot at Figure 12(a), (b) with (g)).

4.4 Rotation invariance

To test the efficiency of the proposed method against rotation invariance, bell-7 contour is rotated using varying amount angle. Then, the rotated contour is given as an input to the proposed method as well as to the technique in [9]. The results are summarized for the reader’s perusal. How do researcher determine a polygonal approximation is rotation invariant or not and what extent? The answer is the metrics such as area of polygon, perimeter and compactness may be suggested to use along with results from human perception. The authors in [41] use the above-mentioned metrics to prove whether the technique is able to produce the polygon with the same positioned points before as well as after the rotation. This can be measured using compactness metric. Moreover, the authors in [41] demonstrated that the techniques proposed in [9, 11, 12] are scaling as well as translation invariant using compactness metric.

The mathematical interpretation of compactness metric (COMP) has been mentioned in Eq. (2). Table 4 summarizes the value obtained by using COMP for the bell-7 contour by the proposed method.

Contour k max(dm) ISE Area Perimeter Compactness
Bell-7 20 2.03 210.164 9231 299.13 0.10
Bell-7 at 20° 2.60 281.57 9.2475e+03 343.81 0.07
Bell-7 at 30° 2.70 348.868 9260 358.08 0.07
Bell-7 at 70° 2.91 325.29 9.254.5e+03 344.83 0.07
Bell-7 at 80° 2.59 319.50 9151 327.10 0.08
Bell-7 at 180° 2.03 210.164 9231 299.13 0.10

Table 4.

Robustness of the proposed method against rotation using quantitative measurement.

comp = Area / Perimeter 2 E4

To compare the robustness of the technique against rotation, the snapshots using bell-7 contour are displayed in Figures 13 and 14. The output polygon at 20 amounts of dominant points is used here to check if the technique is robust enough against rotation invariance. Most of the techniques considered in this chapter produce polygon in non-parametric mode. The best thing to compare the efficiency of rotation invariance is to compare the output at minimal possible amount of points since the input curve may contain more redundant points. So the result of the proposed method is compared with Masood [9]. By using [9], any researcher can produce a curve with specified number of dominant points. In Table 4, the value for geometric invariance assessment metrics (area of polygon, perimeter and compactness) reveals that the results by proposed method using rotated contours measure against compactness metric are more or less nearer to the value produced by the proposed method before rotation, and the visual snapshots in Figure 13 also support the same. The results of Masood [9] in terms of quantitative measurements can be found in Table 5. Bell-7 at 30° value for compactness metric varies high while comparing the results obtained before rotation. In the remaining angles, the rotated contours compactness metric is more or less nearer to the value obtained by the method before rotation. Masood [9] snapshots can be found in Figure 14. When the authors noticed that in the output curve produced by Masood [9], the position of the dominant point is heavily dislocated after rotation, whereas the proposed methods try to maintain the same positioned dominant points in the rotated contours too (see Figure 13).

Contour k max(dm) ISE Area Perimeter Compactness
Bell-7 20 3.48 315.00 6835 321.78 0.06
Bell-7 at 20° 2.77 311.84 9130 333.32 0.08
Bell-7 at 30° 1.99 270.51 9.1255e+05 190.61 0.25
Bell-7 at 70° 3.79 381.35 9.1615e+03 343.59 0.07
Bell-7 at 80° 2 266.677 9.1585e+03 326.90 0.08
Bell-7 at 180° 3.487 315.00 6835 306.95 0.07

Table 5.

Robustness of Masood [9] against rotation using quantitative measurement.

5. Conclusion

The proposed significant measure computing metric predicts the position of a projection of every boundary point between its candidate line segment, thereby invoking suitable significant measure computing metric and accumulating its significant measure to define the significant value of every candidate of dominant points. The technique is demonstrated using wide variety of data sets, where the image contours are with different level details in terms of curvature as well as size. The proposed technique suits for parallel manipulators aspiring to produce the digital boundary with minimal number points without compromising its shape according to human perception as well as using benchmarking performance measuring metrics.

Acknowledgments

This research did not receive any specific grant from any funding agencies in the public, commercial or not-for-profit sectors. But the authors thank all anonymous reviewers for their comments on an earlier manuscript for improving the quality of the chapter.

References

1. 1. Lavallee S, Szeliski R. Recovering the position and orientation of free-form objects from image contours using 3D distance maps. IEEE Transactions on Pattern Analysis and Machine Intelligence. 1995;17:378-390. DOI: 10.1109/34.385980
2. 2. Elder JH, Goldberg RM. Image editing in the contour domain. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2001;23:291-296. DOI: 10.1109/34.910881
3. 3. Kolesnikov A, Fränti P. Reduced-search dynamic programming for approximation of polygonal curves. Pattern Recognition Letters. 2003;24:2243-2254. DOI: 10.1016/S0167-8655(03)00051-5
4. 4. Yang R, Zhang Eye Z. gaze correction with stereovision for video-teleconferencing. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2004;26:956-960. DOI: 10.1109/TPAMI.2004.27
5. 5. Kolesnikov A, Fränti P. Data reduction of large vector graphics. Pattern Recognition. 2005;38:381-394. DOI: 10.1016/j.patcog.2004.07.005
6. 6. Brunner D, Soille P. Iterative area filtering of multichannel images. Image and Vision Computing. 2007;25:1352-1364. DOI: 10.1016/j.imavis.2006.09.002
7. 7. Mokhtarian F, Mackworth A. Scale-based description and recognition of planar curves and two-dimensional shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence. 1986;8:34-43. DOI: 10.1109/TPAMI.1986.4767750
8. 8. Prasad DK, Leung MKH, Cho S-Y. Edge curvature and convexity based ellipse detection method. Pattern Recognition. 2012;45(9):3204-3221. DOI: 10.1016/j.patcog.2012.02.014
9. 9. Masood A. Dominant point detection by reverse polygonization of digital curves. Image and Vision Computing. 2008;26(5):702-715
10. 10. Masood A, Haq SA. A novel approach to polygonal approximation of digital curves. Journal of Visual Communication and Image Representation. 2007;18(3):264-274
11. 11. Carmona-Poyato A, Madrid-Cuevas FJ, Medina-Carnicer R, Muñoz-Salinas R. Polygonal approximation of digital planar curves through break point suppression. Pattern Recognition. 2010;43(1):14-25
12. 12. Ramaiah M, Ray BK. Polygonal approximation of digital planar curve using local integral deviation. International Journal of Computational Vision and Robotics. 2015;5(3):302-319
13. 13. Kolesnikov A, Fränti P. Polygonal approximation of closed discrete curves. Pattern Recognition. 2007;40(4):1282-1293
14. 14. Bhowmick P, Bhattacharya BB. Fast polygonal approximation of digital curves using relaxed straightness properties. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2007;29(9):1590-1602
15. 15. Marji M, Siy P. Polygonal representation of digital planar curves through dominant point detection—A nonparametric algorithm. Pattern Recognition. 2004;37(11):2113-2130
16. 16. Wang B, Brown D, Zhang X, Li H, Gao Y, Cao J. Polygonal approximation using integer particle swarm optimization. Information Sciences. 2014;278:311-326. DOI: 10.1016/j.ins.2014.03.055
17. 17. Aguilera-Aguilera EJ, Carmona-Poyato A, Madrid-Cuevas FJ, Marín-Jiménez MJ. Fast computation of optimal polygonal approximations of digital planar closed curves. Graphical Models. 2016;84:15-27. DOI: 10.1016/j.gmod.2016.01.004
18. 18. Liu Z, Watson J, Allen A. A polygonal approximation of shape boundaries of marine plankton based-on genetic algorithms. Journal of Visual Communication and Image Representation. 2016;41:305-313. DOI: 10.1016/j.jvcir.2016.10.010
19. 19. Parvez MT. Optimized polygonal approximations through vertex relocations in contour neighborhoods. Image and Vision Computing. 2015;34:1-10. DOI: 10.1016/j.imavis.2014.10.012
20. 20. Pikaz A, Dinstein IH. An algorithm for polygonal approximation based on iterative point elimination. Pattern Recognition Letters. 1995;16(6):557-563
21. 21. Zhu P, Chirlian PM. On critical point detection of digital shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence. 1995;17(8):737-748. DOI: 10.1109/34.400564
22. 22. Pavlidis T, Horowitz SL. Segmentation of plane curves. IEEE Transactions on Computers. 1974;100(8):860-870
23. 23. Prasad DK, Leung MK, Quek C, Cho SY. A novel framework for making dominant point detection methods non-parametric. Image and Vision Computing. 2012;30(11):843-859
24. 24. Prasad DK. PRO: A novel approach to precision and reliability optimization based dominant point detection. Journal of Optimization. 2013;1-15. DOI: 10.1155/2013/345287
25. 25. Fernández-García NL, Martínez LD, Carmona-Poyato A, Madrid-Cuevas FJ, Medina-Carnicer R. A new thresholding approach for automatic generation of polygonal approximations. Journal of Visual Communication and Image Representation. 2016;35:155-168. DOI: 10.1016/j.jvcir.2015.12.013
26. 26. Madrid-Cuevas FJ, Aguilera-Aguilera EJ, Carmona-Poyato A, Muñoz-Salinas R, Medina-Carnicer R, Fernández-García NL. An efficient unsupervised method for obtaining polygonal approximations of closed digital planar curves. Journal of Visual Communication and Image Representation. 2016;39:152-163. DOI: 10.1109/TPAMI.1986.4767753
27. 27. Dunham JG. Optimum uniform piecewise linear approximation of planar curves. IEEE Transactions on Pattern Analysis and Machine Intelligence. 1986;Jan(1):67-75. DOI: 10.1109/TPAMI.1986.4767753
28. 28. Ramaiah M, Ray BK. An iterative point elimination technique to retain significant vertices on digital planar curves. International Journal of Computational Vision and Robotics. 2016;6(4):354-368
29. 29. Ramer U. An iterative procedure for the polygonal approximation of plane curves. Computer Graphics and Image Processing. 01 November 1972;1(3):244-256. DOI: 10.1016/S0146-664X(72)80017-0
30. 30. Douglas DH, Peucker TK. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica: The International Journal for Geographic Information and Geovisualization. 01 October 1973;10(2):112-122. DOI: 10.3138/FM57-6770-U75U-7727
31. 31. Freeman H. On the encoding of arbitrary geometric configurations. IRE Transactions on Electronic Computers. 1961; Jun(2):260-8. DOI: 10.1109/TEC.1961.5219197
32. 32. Teh CH, Chin RT. On the detection of dominant points on digital curves. IEEE Transactions on pattern analysis and machine intelligence. August 1989;11(8):859-872. DOI: 10.1109/34.31447
33. 33. Wu WY. An adaptive method for detecting dominant points. Pattern Recognition. 01 october 2003;36(10):2231-2237. DOI: 10.1016/S0031-3203(03)00087-6
34. 34. Parvez MT, Mahmoud SA. Polygonal approximation of digital planar curves through adaptive optimizations. Pattern Recognition Letters. 01 October 2010;31(13):1997-2005. DOI: 10.1016/j.patrec.2010.06.007
35. 35. Nguyen TP, Debled-Rennesson I. A discrete geometry approach for dominant point detection. Pattern Recognition. 01 January 2011;44(1):32-44. DOI: 10.1016/j.patcog.2010.06.022
36. 36. Backes AR, Bruno OM. Polygonal approximation of digital planar curves through vertex betweenness. Information Sciences. 10 February 2013;222:795-804. DOI: 10.1016/j.ins.2012.07.062
37. 37. Yin PY. Genetic algorithms for polygonal approximation of digital curves. International journal of pattern recognition and artificial intelligence. November 1999;13(07):1061-1082. DOI: 10.1142/S0218001499000598
38. 38. Salotti M. Optimal polygonal approximation of digitized curves using the sum of square deviations criterion. Pattern Recognition. 01 February 2002;35(2):435-443. DOI: 10.1016/S0031-3203(01)00051-6
39. 39. MPEG-7 Core Experiment CE-Shape-1Test set (Part B). Benchmarking Image Database for shape Recognition Techniques http://www.cis.temple.edu/∼latecki/TestData/mpeg7shapeB.tar.gz
40. 40. Rosin PL. Unimodal thresholding. Pattern recognition. 2001 Nov 1;34(11):2083-2096. DOI: 10.1016/S0031-3203(00)00136-9
41. 41. Ramaiah M, Ray BK. A brief review of closed curve approximation technique using iterative point elimination. In 2017 International conference on Microelectronic Devices, Circuits and Systems (ICMDCS) 2017 Aug 10 (pp. 1-6). IEEE. . DOI: 10.1109/ICMDCS.2017.8211729

Written By

Mangayarkarasi Ramaiah and Dilip Kumar Prasad

Submitted: November 26th, 2019 Reviewed: March 16th, 2020 Published: April 28th, 2020