An Efficient Descriptor-Based Approach for Dominant Point Detection in Shape Contours
Abstract:
Dominant points, or control points, represent areas of high curvature on shape contours and are extensively utilized in the representation of shape outlines. Herein, we introduce a novel, descriptor-based approach for the efficient detection of these pivotal points. Each point on a shape contour is evaluated and mapped to an invariant descriptor set, accomplished through the use of point-neighborhood. These descriptors are then harnessed to discern whether a point qualifies as a dominant one. Our proposed methodology eliminates the need for costly computations typically associated with evaluating candidate dominant points. Furthermore, our algorithm significantly outperforms its predecessors in terms of speed, relying solely on integer operations and obviating the necessity for an optimization phase. Experimental outcomes, derived from the widely used MPEG7_CE-Shape-1_Part_B, denote a minimum enhancement of 2.3 times in terms of running time. This implies that the proposed methodology is particularly suitable for real-time applications or scenarios managing shapes comprising a substantial number of points.
1. Introduction
Dominant points, also referred to as control points, are instrumental in delineating the contours of digital planar shapes [1], [2]. When connected via straight lines, these points generate a sequence of line segments that approximate an image's outline. This form of approximation, known as polygonal approximation (illustrated in Figure 1), is employed in various applications, including shape modeling [3] and recognition [4]. The primary rationale behind utilizing this approximation-based modeling approach is its proficiency in effectively managing contour noise [3], [5]. Furthermore, polygonal approximation offers a more concise representation of the contour [1]. As a result, there has been a considerable amount of research over several decades dedicated to developing efficient algorithms for polygonal approximation [3], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19].
Numerous polygonal approximation algorithms have been developed with the primary goal of identifying dominant points situated along the contour of a shape. These dominant points subsequently function as vertices in the construction of the approximating polygon [5], [10]. Typically, these approximation methodologies aim to minimize specific error criteria, such as the weighted mean squared error [8], [14], [20].
A prevalent approach shared by these algorithms involves establishing a significance measure for each point along the contour [18]. This measure is instrumental in guiding the selection of a subset of contour points, either by emphasizing the most significant ones [7], [17] or by systematically eliminating less significant, redundant points [3], [5], [10].
The selection process necessitates a definition of the relative importance of contour points. This importance level can be determined using a predefined threshold [10] or by optimizing error measurements. It is noteworthy that research indicates optimization methods generally surpass threshold-based approaches in performance [3], [5]. The primary goal of these algorithms is to yield an accurate and efficient polygonal approximation that effectively encapsulates the fundamental characteristics of the shape contour.
This study aims to advance the current state-of-the-art in dominant point detection. Rather than relying on thresholds or costly optimization methods to select dominant points, it proposes employing intuitive, human-like heuristics. Humans often examine a point and its neighborhood to determine whether it is a dominant point. We aim to replicate this process algorithmically. Our method involves examining a point on a shape contour, using its neighborhood to ascertain whether it is part of a curve or a straight line. If the point is identified as part of a curve, it is retained for further investigation. If not, it is classified as a non-dominant point in a process we term ‘point suppression’.
To this end, we have developed novel rotation-invariant shape descriptors that effectively encapsulate the shape outline. These descriptors can be computed without recourse to expensive computational operations. As a result, descriptor-based point suppression paves the way for a highly efficient dominant point detection algorithm, albeit at the cost of slightly less optimized approximation. To the best of our knowledge, this is the first study to use descriptors for dominant point detection in offline shapes.
The novelty of the proposed approach can be summarized as follows:
i. Innovative point suppression method using shape descriptors.
ii. Rapid algorithm that avoids costly optimizations compared to other methods.
iii. Utilization of adaptive local and global features for dominant point detection.
The paper is structured as follows: Section 2 gives an overview of the existing research on dominant point detection. Section 3 details the proposed algorithm. Section 4 provides a comprehensive analysis of the experimental results, and finally, Section 5 presents our conclusions.
2. Related Works
Numerous algorithms have been proposed for the detection of dominant points in digital planar curves, falling broadly into two main categories. The first category includes algorithms that strive to minimize the number of edges or vertices required to approximate the curve, subject to defined error criteria [21], [22], [23]. The second category, by contrast, comprises algorithms that pinpoint specific points along the curve as dominant points [3], [5], [7], [10], [11], [12], [14], [16], [17], [24].
Algorithms in the first category aim to achieve optimal digital curve approximations. However, these methodologies are often parametric, necessitating the determination of parameters such as the initial vertex or the maximum allowable error prior to generating an approximation. For instance, the method presented in the study [21] approximates a contour using a polygon with the minimum number of vertices, ensuring a predefined acceptable approximation error and an initial vertex. This algorithm iteratively identifies the smallest set of vertices for the polygonal approximation, commencing with a preselected initial vertex [18].
In contrast, algorithms in the second category typically exhibit increased robustness when applied to a variety of shapes. Given the plethora of dominant point detection algorithms chronicled in existing literature, our focus will be directed towards the more recent and relevant approaches [18]. Comprehensive evaluations of various dominant point detection algorithms can be found in the study [25].
A substantial number of dominant point detection algorithms initiate the process by applying filters to contour points based on various criteria. These may include orientation-specific predefined masks [7] or the detection of break-points [3], [10], [11]. Following this initial screening, each point on the contour, $C$, is allocated a significance measure, and the points deemed less significant are subsequently discarded.
Researchers have leveraged a myriad of techniques to compute this measure. For example, Chau and Siu [7] utilized cosine angles to define a significance measure for each potential dominant point. This measure was then employed to suppress less critical dominant points. In contrast, Masood [11] introduced the Associated Error Value (AEV) for each dominant point (DP), and an iterative process was applied to eliminate DPs with the lowest AEV. This was followed by an optimization procedure aimed at enhancing the Integrated Squared Error (ISE) of the resulting polygonal approximation. However, this scheme lacks a well-defined stopping criterion, which may limit its effectiveness.
Some researchers introduced the concept of a support region for each point along contour $C$ [3], [10], [13], [24]. This support region for a point includes the points along $C$ within a specific range defined by $\left\{p_{i-k}, \ldots, p_i, \ldots, p_{i+l}\right\}$ on $C$ for some $k$ and $l$. Subsequently, the significance measure for $p_i$ is computed using mathematical operations that consider the support region of $p_i$. Consequently, less significant points can be removed from the set of dominant points, using the process call point-suppression [3], [10], [24].
The concept of point suppression was originally introduced by Marji and Siy [10]. Their approach, however, is constrained by a fixed suppression threshold. Carmona-Poyato et al. [24] refined this method by incorporating an optimization procedure to determine the threshold value for collinear-points suppression. Building upon their work, Carmona-Poyato et al. [5] further improved their technique by iteratively removing dominant points until a specific condition was met. Nonetheless, the performance of their algorithm can fluctuate significantly depending on the chosen final condition [18].
Both algorithms presented in studies [5], [24] fall into the realm of global optimization techniques and employ a single suppression parameter applicable to the entire contour. Conversely, the method presented in the study [3] highlighted the advantages of a local optimization strategy. This approach involves using distinct, adaptively estimated suppression thresholds for different segments of the contour, effectively taking into account the varying levels of detail within the contour [18].
Most of the algorithms discussed above determine the significance of a point based on its distance to the approximate straight line. This approach carries two primary disadvantages: firstly, the process of computing the significance in this manner is computationally intensive; secondly, a threshold is required to establish the cut-off distance. This study aims to circumvent these drawbacks by adopting a completely different approach: The significance measure of a point is estimated based on the shape formed around the point under consideration. As demonstrated in the experimental results section, this approach leads to a highly efficient dominant point detection algorithm.
3. Algorithm
The methodology proposed in this study is rooted in the use of invariant shape descriptors to characterize segments of a shape contour. We first elucidate how a shape can be represented using these descriptors. Following this, we discuss how these descriptors can be employed to suppress points along the shape outline.
A shape contour (also known as an outline or stroke), $C$, is defined as an ordered sequence of $n$ points $\left(x_i, y_i\right)$, $i=1,2, \ldots, n$ [19]. Here, point $\left(x_i, y_i\right)$ has two neighbors: $\left(x_{i-1}, y_{i-1}\right)$ and $\left(x_{i+1}, y_{i+1}\right), i=2,3, \ldots, n-1$. In the case where shape $C$ represents an online stroke, it's important to note that the endpoints in $C$ will have only one neighboring point. In this section, we focus only on a sub-set $S$ of $C$, such that |S|=(m+1)<n. That is, $S$ contains a set of consecutive points from $C$, where pj is the middle point in $S$. The value m = |S| − 1 is considered as the region of support (as describe earlier) or strength for pj . We now describe how this segment $S$ of contour $C$ is described by a shape descriptor.
Consider a set of descriptors, denoted as $D$, which characterizes the directional movement of points in $S$. Our objective is to construct $D$ in such a way that every descriptor, represented as $d \in D$, remains invariant to rotation, translation, and scale changes. The specific descriptors employed in this study are outlined in Table 1. Consequently, each segment $S$ can be described using one of three descriptors: straight_line, ccw_curve, and cw_ curve.
The procedure for associating a segment $S$ with a descriptor is explained next. To illustrate this process, please refer to Figure 2 and Figure 3. Subgraphs (a) and (b) as well as (c) and (d) of Figure 2 display a shape (referred to as ‘camel’ from the popular MPEG7_CE-Shape-1_Part_B database [26]) and the corresponding contour that requires modeling by a shape descriptor. Figure 3 demonstrates how a contour segment is mapped to a descriptor from Table 1.
As shown in the bottom-left corner of Figure 3, we partition the 2D planar space into eight regions. This division serves a purpose akin to the well-known quantization technique, allowing us to quantize a shape trajectory into a limited set of discrete descriptors [27]. Now, consider a segment $S$ (extracted from subgraph (d) of Figure 2). Suppose we aim to determine the descriptor for the segment with endpoints $\left\{e p_i, e p_{i+1}\right\}$, as depicted in Figure 3.
To determine the appropriate descriptor from $D$ that matches segment $S$, we introduce another point along $S$, which we'll call midi,i+1. This point represents the midpoint of the segment $S$. Now, given a tuple P=<epi, midi,i+1, epi+1>, corresponding to the segment $S$, we derive the descriptor $d \in D$ as follows:
We start by translating the points in $P$ so that $mid_{i, i+1}$ becomes the origin. Then, we estimate the positions of $e p_i$ and $e p_{i+1}$ within the 2D space, following the subdivision shown in Figure 3. Let's denote these positions as pos $\left(e p_i\right)$ and $\operatorname{pos}\left(e p_{i+1}\right)$ respectively. Additionally, we determine the parameter $l o c \, (mid_{i, i+1})$, which specifies the location of point $mid_{i, i+1}$ in relation to the directional line-segment stretching from $e p_i$ to $e p_{i+1}$. It's worth noting that $l o c \, (mid_{i, i+1})$ can take one of two values, ‘left’ or ‘right’, based on whether $mid_{i, i+1}$ resides to the left or right of the directional line-segment between $e p_i$ and $e p_{i+1}$.
With these parameters established, we map the stroke segment $S$ to a descriptor $d \in D$ using the guidelines outlined in Table 2. To provide a clearer illustration, please refer to Figure 4, which presents an example of a stroke with segments mapped to $D$ [27].
Straight Line (straight_line) | |
Counter-clock-wise Curve (ccw_curve) | |
Clock-wise Curve (cw_curve) |
Descriptor | Symbol | Fitting Criteria |
straight_line | S | pos(epi+1)=pos(epi)+4, mod 8 |
cw_curve | C | $\neg \mathrm{S} \wedge \operatorname{loc}\left(\mathrm{mid}_{i, i+1}\right)=$‘left’ |
ccw_curve | V | $\neg \mathrm{S} \wedge \operatorname{loc}\left(\mathrm{mid}_{i, i+1}\right)=$‘right’ |
In this section, we discuss the concept of point-suppression and how point-suppression is used in this work. Our discussion of point-suppression is more general than the concept of collinear–points suppression used in studies [3], [5], [10]. Collinear-points suppression was used successfully for smoothing the contour (boundary of a curve) in 2-dimension [28]. We will used collinear-points suppression as post-processing phase in our dominant point detection method, as discussed later.
The Idea of point-suppression is to decide whether a point $P$ on the shape contour $C$ should be retained as a dominant point or not. For this purpose, we need to define a significance value for $P$. This significance value of $P$ can be defined in numerous ways. In this work, we define this significance value of $P$ in two different ways, that lead to two different ways of point suppression:
• Point suppression by distance thresholding and
• Point suppression by descriptor modeling.
Point suppression by distance thresholding. Let $P_j, P_{j+1}$, and $P_{j+2}$ be three points on $C$ in sequence (not necessarily consecutive). In point suppression by distance thresholding, $P_{j+1}$ is suppressed if the distance $\delta$ from $P_{j+1}$ to the line joining $P_j$ and $P_{j+2}$ is less than some predefined threshold $\tau$. Several researchers have used the perpendicular distance from $P_{j+1}$ to the line joining $P_j$ and $P_{j+2}$ as the distance $\delta$ [5], [10]. Parvez and Mahmoud [3] showed that using $\delta$ as the minimum distance from $P_{j+1}$ to the line-segment joining $P_j$ and $P_{j+2}$ can have superior performance in preserving shape of the curve $C$.
Figure 5 illustrates the concept of points suppression by distance thresholding. Here, $\delta$ is taken as the perpendicular distance from $P_{j+1}$ to the line joining $P_j$ and $P_{j+2}$. The point $P_{j+1}$ will be removed as the distance $\delta$ is greater than the threshold $\tau$. The new piecewise linear curve $C^{\prime}$ resulted due this suppression will have one segment less than $C$.
This concept of suppression of points can be applied to all the points on $C$ and thus the ‘redundant’ points on $C$ can be deleted. The number of segments and the shape of the resulting curve $C$ ' will depend on the threshold $\tau$ and the order in which the points on $C$ are considered in the removal process.
There are several ways to determine the value of the threshold $\tau$. Some researchers have used a fixed value for $\tau$ [10], others have determined the value of $\tau$ adaptively [3], [5], [22]. These adaptive schemes use some optimization techniques to compute the threshold that optimize some performance measures (like weighted sum square error). These schemes are more robust and can be applied to curves of different dimensions and resolutions.
The following procedure $SuppressionByThresholding$ summarizes the concept of point suppression by distance thresholding. The results of applying $SuppressionByThresholding$ are illustrated in subgraphs (b) and (c) of Figure 5.
Procedure SuppressionByThresholding
Input: $P=\left\{\left(x_i, y_i\right)\right\}, i=1,2, \ldots, n$, a sequence of $n$ points on contour $C$.
A threshold $\tau$.
Output: $P^{\prime}$, a subset of $P$.
Start
$P^{\prime} \leftarrow P$
Iterate until points cannot be suppressed anymore
For each point $p_i$ from $P^{\prime}$
$\circ \rightarrow$ Suppress $p_i$ if $\delta<\tau$.
$\cdot \rightarrow P^{\prime} \leftarrow P^{\prime}-\left\{p_i\right\}$
End
Point suppression by descriptor modeling. Here, we also consider three points on $C$ in sequence: $P_j, P_{j+1}$, and $P_{j+2}$. However, instead of measuring the distance from $P_{j+1}$ to the line segment connecting $P_j$ and $P_{j+2}$, we consider the shape formed at point $P_{j+1}$. For this purpose, refer again to Figure 3. If we map $P_j, P_{j+1}$, and $P_{j+2}$ to $e p_i, mid_{i, i+1}$, and $e p_{i+1}$ respectively, then the curve segment bounded by $P_j$ and $P_{j+2}$ can be mapped to one of the descriptors from Table 2. In point suppression by descriptor modeling, point $P_{j+1}$ will be suppressed if the curve segment bounded by $P_j$ and $P_{j+2}$ is mapped to the descriptor ‘straight_line'.
It should be noted here that, to suppress points by descriptors, we need to bound a segment by end points (that is, $P_j$ and $P_{j+2}$ need to be fixed). Since the mapping of the segment to a descriptor can vary based on the locations of $P_j$ and $P_{j+2}$, we use the following iterative process to suppress points using descriptors. For that purpose, let us define width of a segment $S$ of $C$ be the number of points in $S$. For example, the width of the segment in Figure 3 is 17. Based on this definition of width of $S$, the following $SuppressionByDescriptors$ procedure captures the process of point suppression using descriptors discussed earlier.
Procedure SuppressionByDescriptors
Input: $P=\left\{\left(x_i, y_i\right)\right\}, i=1,2, \ldots, n$, the sequence of $n$ points on contour $C$.
Set of descriptors from Table 2
Output: $P^{\prime}$, a subset of $P$.
Start
$P^{\prime} \leftarrow P$
Iterate until points cannot be suppressed anymore
For $w=1$ to maxwidth $/ / \max$ Width to be determined experimentally For each point $p_i$ from $P^{\prime}$
$\circ \rightarrow$ Consider the segment $S$ of width $=w+1$, where $p_i$ is the middle point of $S$
$\circ \rightarrow$ if $S$ is mapped to straight_line.
$\begin{aligned} & -\rightarrow \text { Suppress } p_i \\ & P^{\prime} \leftarrow P\end{aligned}$
End For
End For
End
Equipped with the invariant descriptors and the concept of point suppression, we are now in a position to develop a fast and effective dominant point detection algorithm. The proposed algorithm is illustrated with a block diagram (along with an example) in Figure 6. In the following discussion, we delve into the details of each block represented in Figure 6.
Once the contour $C$ of a planar shape is extracted (Block-1), contour $C$ is passed to SuppressionByDescriptors procedure to extract the initial set of dominant points (Block-2). This phase of SuppressionByDescriptors is run in uniform division mode. This means, when we consider three points on $C$ in sequence <Pj, Pj+1, and Pj+2>, the number of points between $P_j$ and $P_{j+1}$ and number of points between $P_{j+1}, P_{j+2}$ is same (that is, $P_{j+1}$ falls exactly at the middle of the segment being mapped to a descriptor). These initial set of dominant points from Block-2 are then suppressed by SuppressionByThresholding procedure with a fixed threshold of 1 (Block-3). This phase of suppression of points with fixed threshold is needed to suppress any collinear points that may remain from the previous phase (Block-2). Using a fixed threshold at this phase avoid estimating the optimal threshold values, unlike other methods [3].
In the next phase (Block-4), the current set of dominant points once again go through SuppressionByDescriptors procedure, but in non-uniform division mode. This mode differs from the previous phase (Block-2) of uniform division in a number of ways. Again, suppose we consider three points on $C$ in sequence <Pj, Pj+1, and Pj+2>. In non-uniform division, all points from $P_j, P_{j+1}$, and $P_{j+2}$ are from the set of dominant points retained by Block-3. In addition, the number of points between $P_j$ and $P_{j+1}$ and number of points between $P_{j+1}, P_{j+2}$ is not necessarily the same (that is, $P_{j+1}$ doesn't necessarily fall at the middle of the segment being mapped to a descriptor). Moreover, in the segment defined by $P_j$ and $P_{j+2}, P_{j+1}$ is the only other dominant point retained by Block-3.
Quality measures of the approximations produced by our method can be enhanced by an optional efficient optimization phase. This optimization is called shift optimization. Shift optimization is a simple optimization process where we try to move a dominant point in its neighborhood along contour $C$, such that some quality measures (discussed in the next section) are optimized. Experimental results show that shift optimization phase adds very little overhead to the running time, compared to the significant improvements obtained by the optimization.
4. Experimental Results
The proposed method has been extensively evaluated to estimate the quality of approximations and the efficiency of the algorithm. The results have proven to be very promising, especially considering the significant reduction in running time for the MPEG7_CE-Shape-1_Part_B database [24]. In the subsequent sections, we first describe some quality measures commonly used by researchers to estimate the quality of detected dominant points. Following that, we present our experimental results.
Evaluating the quality of an approximation is of utmost importance to assess performance, and researchers have introduced various measures for this purpose [6], [9], [10], [22], [29]. These measures are briefly outlined below.
The compression ratio is used to quantify the normalized compression rate of an approximation. It is denoted as $C R=n / n_d$, where $n$ is the number of contour points and $n_d$ is the number of dominant points. However, it doesn't consider the approximation error. An alternative is the integral sum of squared error, ISE $=\sum_{i=1}^n e_i^2$. $ISE$ measures the error of an approximation as the distance $e_i$ from a contour point $p_i$ to the resultant approximating line segment. Nonetheless, $ISE$ can always be minimized by increasing the count of dominant points. This issue with $ISE$ leads us to the use of the weighted sum of square error, $W E=I S E / C R$. Many researchers have adopted this measurement, which merges both the compression ratio and the sum of squared errors [18].
Rosin [20] recognized an imbalance in the two constituents of the $W E$ measure, leading to a bias in favor of approximations with lower ISE (achieved by increasing the number of detected dominant points). This characteristic makes it less suitable for comparing contours with varying numbers of dominant points. Rosin introduced two components, namely fidelity and efficiency. Fidelity evaluates how well the polygonal approximation aligns with the contour in comparison to the optimal polygon in terms of approximation error [20]: Fidelity $=\left(E_{\text {opt }} / E_{\text {approx }}\right) \times 100$. Here, $E_{\text {approx }}$ represents the error of the polygonal approximation, and $E_{\text {opt }}$ signifies the error associated with the optimal algorithm, both adjusted to yield the same number of lines. The optimal polygon achieves the lowest possible error for a given dominant point count.
To achieve a more balanced measure, $W E$ (Weighted Efficiency) has been adjusted by various researchers, resulting in a modified version denoted as $W E_x=I S E / C R^x$, where $x$ is a parameter that regulates the influence of the denominator, thus mitigating the imbalance between the two terms. Common choices for $x$ include 1, 2, and 3 [5], [9], [11], [12]. Carmona-Poyato et al. [5] notably showed that $W E_2$ outperforms $W E$. In line with this, we have adopted the $W E_x$ measures to assess the results produced by our algorithm.
To better understand the effects of various measures, consider the example shown in Figure 7. As can be seen in subgraphs (b) and (c) of Figure 7, the $I S E$ is lower in the approximation in subgraph (b) of Figure 7, albeit, with more and sometimes unnecessary dominant points. In contrast, the approximation in in subgraph (c) of Figure 7 uses less number of dominant points, resulting in higher $ISE$ compared to the subgraph (b) of Figure 7. However, the approximation in subgraph (b) of Figure 7 is preferred over the approximation in subgraph (b) of Figure 7, as the approximation in in subgraph (c) of Figure 7 has lower $W E_3$ value.
Initially, the proposed algorithm is applied to four widely recognized shapes: chromosome, leaf, semicircles, and infinity. These shapes have commonly been used as benchmarks for evaluating dominant point detection algorithms in prior research [3], [5], [7], [10], [11], [12], [16], [17], [24]. The results obtained by our algorithm for these four shapes are depicted in Figure 8 [19]. Furthermore, we present a comparative evaluation of the current algorithm against other reported methods in Table 3.
As can be seen in Table 3, the outputs from the proposed method are very much comparable with other methods, especially the $W E_3$ measure. Note that, the proposed method achieves excellent $W E_3$ measures, although the method only employs a simple shift optimization at the end of the algorithm.
Shape | Method | nd | CR | ISE | WE | WE2 | WE3 |
Chromosome (n=60) | Marji and Siy [10] | 10 | 6.00 | 10.01 | 1.66 | 0.277 | 0.046 |
Carmona-Poyato et al. [24] | 11 | 5.36 | 9.60 | 1.79 | 0.334 | 0.062 | |
Masood [11] | 15 | 4.00 | 3.88 | 0.97 | 0.243 | 0.061 | |
Carmona-Poyato et al. [5] | 15 | 4.00 | 4.27 | 1.07 | 0.267 | 0.067 | |
Parvez and Mahmoud [4] | 10 | 6.00 | 14.34 | 2.39 | 0.398 | 0.066 | |
Nguyen and Debled-Rennesson [13] | 18 | 3.33 | 4.06 | 1.22 | 0.366 | 0.110 | |
Parvez [18] | 11 | 5.46 | 7.09 | 1.30 | 0.238 | 0.044 | |
Parvez [19] | 10 | 6.10 | 33.54 | 5.50 | 0.901 | 0.148 | |
Proposed | 10 | 6.10 | 15.70 | 2.57 | 0.422 | 0.069 | |
Leaf (n=120) | Marji and Siy [10] | 17 | 7.06 | 28.67 | 4.06 | 0.575 | 0.081 |
Carmona-Poyato et al. [24] | 17 | 7.00 | 37.36 | 5.33 | 0.761 | 0.109 | |
Masood [11] | 23 | 5.22 | 9.46 | 1.81 | 0.347 | 0.067 | |
Carmona-Poyato et al. [5] | 23 | 5.22 | 10.68 | 2.05 | 0.391 | 0.075 | |
Parvez and Mahmoud [4] | 21 | 5.71 | 13.82 | 2.42 | 0.423 | 0.074 | |
Nguyen and Debled-Rennesson [13] | 33 | 3.64 | 5.56 | 1.53 | 0.419 | 0.115 | |
Parvez [18] | 21 | 5.71 | 11.98 | 2.10 | 0.367 | 0.064 | |
Parvez [19] | 23 | 5.26 | 32.50 | 6.17 | 1.174 | 0.223 | |
Proposed | 19 | 6.36 | 20.07 | 3.15 | 0.495 | 0.078 | |
Semicircles (n=102) | Marji and Siy [10] | 15 | 6.80 | 22.70 | 3.34 | 0.491 | 0.072 |
Carmona-Poyato et al. [24] | 11 | 9.18 | 59.06 | 6.03 | 0.700 | 0.076 | |
Masood [11] | 26 | 3.92 | 4.05 | 1.03 | 0.263 | 0.067 | |
Carmona-Poyato et al. [5] | 26 | 3.92 | 4.91 | 1.25 | 0.319 | 0.082 | |
Parvez and Mahmoud [4] | 17 | 6.00 | 19.02 | 3.17 | 0.528 | 0.088 | |
Nguyen and Debled-Rennesson [13] | 25 | 4.12 | 5.42 | 1.32 | 0.319 | 0.078 | |
Parvez [18] | 15 | 6.80 | 18.22 | 2.24 | 0.329 | 0.048 | |
Parvez [19] | 21 | 4.91 | 24.47 | 4.99 | 1.017 | 0.207 | |
Proposed | 19 | 5.42 | 20.22 | 3.73 | 0.688 | 0.127 | |
Infinity (n=45) | Carmona-Poyato et al. [24] | 9 | 4.89 | 7.34 | 1.50 | 0.306 | 0.063 |
Masood [11] | 11 | 4.09 | 2.90 | 0.71 | 0.173 | 0.042 | |
Carmona-Poyato et al. [5] | 10 | 4.50 | 5.29 | 1.18 | 0.261 | 0.058 | |
Parvez and Mahmoud [4] | 9 | 5.00 | 7.35 | 1.47 | 0.294 | 0.059 | |
Parvez [18] | 7 | 6.43 | 7.69 | 1.20 | 0.186 | 0.029 | |
Parvez [19] | 9 | 5.00 | 14.60 | 2.92 | 0.584 | 0.117 | |
Proposed | 11 | 4.18 | 4.40 | 1.05 | 0.252 | 0.060 |
While the four basic shapes are simple and provide some insights into the performance of a dominant point detection algorithm, they do not provide extensive information, particularly if we want to evaluate the running time. For this purpose, we experiment with the popular shape database MPEG7_CE-Shape-1_Part_B [26], which is widely used by researchers for testing shape analysis and recognition related works. This dataset contains images with a large number of contour points, making it suitable for testing dominant point detection algorithms. Figure 9 illustrates some outputs of the proposed method for some shapes from the MPEG7_CE-Shape-1_Part_B dataset.
Table 4 shows the statistics of the MPEG7_CE-Shape-1_Part_B dataset and the average number of dominant points for different algorithms for the same dataset. As can be observed from Table 4, our algorithm is comparable to other methods in terms of the average number of dominant points. However, for a more thorough comparison with detailed statistics, please refer to Table 5.
Dataset | Sample Count | Average # of Contour Points | Average Number of Dominant Points |
| ||
Marji and Siy [10] | Parvez and Mahmoud [3] | Parvez [18] | Proposed | |||
MPEG7_CE-Shape-1_Part_B [26] | 1402 | 1272.7 | 98.6 | 53.5 | 81.34 | 90.61 |
Table 5 compares the proposed method with three other methods based on four parameters. Table 5 gives us a lot of insights. First, results from other reported methods in Table 5 give us a clue to measure the maxWidth parameter in $SuppressionByDescriptors$ procedure. The average CR for other reported methods is around 20, which means, on average, each segment of a shape contour in MPEG7_CE-Shape-1_Part_B dataset is of length of around $n/20$, where $n$ is the number of contour points of a shape. Thus, we set $maxWidth$ to $n/20$. However, to make things general, $maxWidth$ can be always set to $n/2$.
As can be seen in Table 5, the proposed method has very much similar CR compared to other methods. However, the average $ISE$ is slightly higher for the proposed method. This is expected, as the proposed method is not based on optimizations, except that our method uses a simple optimization process as a post-processing step. Higher average $ISE$ of the proposed method leads to higher average $WE_3$ measure, although the difference with other methods in terms of $WE_3$ is tolerable.
However, the biggest gain of the proposed method is in terms of running time. All the methods reported in Table 5 have been implemented by MATLAB and run on a MacbookPro (M1-Pro) with 16 GB of RAM. As can be seen in Table 5, the proposed method runs a minimum of 2.56 times faster compared to other methods. When compared with the most optimal algorithm [18], the proposed method is 13 times faster! This huge gain in running time is due to the simple descriptor-based suppression technique of the proposed method, as opposed to costly operations used in other methods. This indicates that the proposed method can be very suitable for real time applications or for processing shapes with large number of points.
Algorithm | Statistics |
| ||
Average CR | Average ISE | Average WE3 | Running Time (sec) | |
Marji and Siy [10] | 20.52 | 285.41 | 0.229 | 112.08 |
Parvez and Mahmoud [3] | 29.24 | 1783.71 | 0.154 | 180.70 |
Parvez [18] | 24.26 | 280.30 | 0.126 | 569.46 |
Proposed [with all phases] | 23.35 | 2095.59 | 0.681 | 43.64 |
Proposed [w/o phase 4] | 17.95 | 457.39 | 0.513 | 43.35 |
Proposed [w/o phase 5 (optimization)] | 23.35 | 2891.36 | 0.932 | 41.47 |
Proposed [w/o phase 4 and phase 5] | 17.95 | 782.29 | 0.678 | 42.27 |
The proposed method is primarily tailored for offline planar shapes. However, the method discussed in this work can also be applied to online strokes, wherein the algorithm is executed after the user completes the stroke. To illustrate the results of the proposed method for online strokes, please refer to Figure 10. In Figure 10, we showcase a few examples from the Online-KHATT database [30] for online Arabic handwritten text, along with the results obtained from our algorithm.
5. Conclusions
In this study, we introduce a novel dominant point detection algorithm based on descriptors. Our innovative algorithm evaluates each point along a shape contour, assigning it a set of invariant descriptors relative to its neighboring points. These descriptors dynamically determine whether a given point qualifies as a dominant point. Notably, our approach circumvents the need for resource-intensive computations typically required to classify a point as a potential dominant point. In addition, our technique demonstrates remarkable speed when compared to other existing methodologies, owing to its reliance on integer operations and its independence from optimization phases. However, the approximations resulting from the current method exhibit higher $ISE$, as no optimizations are performed while producing the approximations. The presented method could be improved by investigating strategies to reduce the $ISE$ of the estimated approximations.
The data used to support the research findings are available from the corresponding author upon request.
The authors declare no conflict of interest.