Sage Journals: Discover world-class research

Abstract

Up to present, there have been numerous articles on ellipse detection. However, it is still a great challenge especially for embedded application with restricted available computing and memory resources. To handle this problem, a novel and effective method is presented for ellipse detection. The method consists of two main steps: extraction of elliptic edge contours and edge contours grouping. These two steps are integrated to improve the accuracy and speed of the method. Finally, the aim of this method is to process high-resolution image for embedded system, which needs fast and accurate ellipse detection with limited computational and memory resources.

Keywords

Image processing ellipse detection embedded system contours following method real time contours detection

Introduction

The ellipse detection is an important investigation area in pattern recognition and computer vision since elliptic objects are the commonest objects in real images. General consensus shows that approaches used now mainly fall into three categories: fitting-based method, voting-based method (Hough transform (HT)-based method), and contours following method.

As one of the earliest methods, fitting-based method is mostly based on least square.^1–5 In least square–based method, first, edge points are put into the mathematical model of ellipse, and the ellipse fitting is transformed into elliptical parameter equations. Then, the solution is obtained by minimizing the residue in elliptical parameter equations. Evidently, fitting-based method is not suitable for using alone since each edge point used in this method is required to be on the boundary of same ellipse.

HT was proposed for the purpose of line detection at first⁶ and was found applicable for ellipse detection,⁷ which is well known as simplified Hough transform (SHT). However, practical application of SHT is difficult because of massive computation and large memory demand. To settle those problems, some prior researches were conducted based on modified HT mainly in two categories. One is to reduce the number of voting points^8–11 such as randomized Hough transform (RHT)^8,9 and probabilistic Hough transform (PHT).¹⁰ Despite the fewer inputs, there still exist lots of problems in such method, such as invalid sampling and too much iteration, especially for noisy image. In the other category, the five-dimensional parameter space is divided into lower dimensional subspaces according to geometric property of ellipses.^12–15 Unfortunately, they show obvious disadvantage that they are not appropriate for small-scale ellipses due to large error.

In contrast to HT-based methods, which focus on global contours, the following method pays attention to local contours. Generally, it consists of two steps: the first is to connect the adjacent edge to form contours, and the second is to apply election strategies to group the contours that belong to same ellipse and to estimate elliptic parameters by fitting-based methods or HT-based methods. Contours following methods are advantageous over HT-based methods in terms of the amount of computations and execution time. Much research has been conducted recently based on contours following method. For the first step, arcs are obtained from segmentation^16,17 or merging algorithm.^18,19 For the second step, grouping of arcs are performed based on continuity,^18,19 convexity,^17,20 curvature,^17,21 centers of ellipses,^17,20,22 and ellipse fitting error.²¹ However, some of them are constrained by various problems in real images. For instance, continuity is valid for grouping only if arcs on the same ellipse are not far from each other.

While most of the research devoted to ellipse detection focus on handling general cases of occlusion, overlapping, and noise and ignore embedded application. In one of our ongoing projects, a series of satellite mockups are required to estimate pose, for which real-time ellipse detection should be performed as the first step. On-orbit operation puts strict requirements on weight, power consumption, and volume of the hardware, and such requirements restrain the computational capability and memory resource of hardware. Moreover, the large-resolution image (2048 × 2048 pixels) needs to be processed. In summary, high computing speed and low-memory resource demand is required for ellipse detection algorithm under this circumstance.

This article focuses on embedded application. Figure 1 shows the overview of the proposed approach. For the first step, extraction of elliptic edge contours is performed in three major blocks: edge point detection and thinning, edge contour detection, and segmentation and merging. Smooth edge contours without any branches are obtained from this step. For the second step, edge contours that satisfy three conditions are grouped. Consequently, detected ellipses, represented by groups of edge contours, are obtained.

Figure 1.

Flowchart of the proposed algorithm.

An example of hardware structure for our ongoing project is shown in Figure 2. Since the edge point detection and thinning process are for the whole image, which leads to mass calculation, they are implemented quickly in field-programmable gate array (FPGA) through pipeline operation, while other algorithms are running in digital signal processor (DSP) for its excellent floating-point arithmetic.

Figure 2.

Block diagram of the hardware structure.

Extraction of elliptic edge contours

This section presents the extraction of smooth edge contours without any branches. First of all, edge points are extracted from the input image, and thinning algorithm is used to obtain one-pixel-wide edge as mentioned in MATLAB. Then, a novel algorithm is proposed to connect adjacent edge points and form edge contours. Finally, a fast image segmentation and merging method is performed on contours to obtain smooth edge contours.

Edge point detection

Sobel operator is used to detect edge points. We defined every detected edge points as $P^{1} = {p_{i}^{1}} = {(x_{i}, y_{i})} (i = 1, 2, \dots, m_{1})$ and its corresponding gradient as $θ^{1} = {θ_{i}^{1}}$ where $θ_{i} \in [0, 2 π]$ is the anticlockwise angle from the positive direction of x coordinate to the direction of gradient. After two rows of image data are stored in FPGA, Sobel operator can be performed when the third row of image data comes to FPGA as shown in Figure 3.

Figure 3.

Algorithm implementation in FPGA.

Edge thinning

In this subsection, one-pixel-wide edge image is obtained to improve extraction accuracy. Given an edge point $p_{i}^{1} \in P^{1}$ , we can encode it by its eight-connectivity points

p_{i}^{1} = \sum_{j = 0}^{7} (n_{j} \times 2^{j})

(1)

where $2^{j}$ , $j = 0, 1, \dots, 7$ , represent encode table and $n^{j}$ , $j = 0, 1, \dots, 7$ , are the eight-connectivity points as shown in Figure 4. The method in Lam et al.²³ is used to perform thinning process. Let $P^{2} = {p_{i}^{2}} (i = 1, 2, \dots, m_{2})$ denote the set of all edge points on the one-pixel-wide edge image, while its corresponding gradient and encoding value are $θ^{2} = {θ_{i}^{2}} (i = 1, 2, \dots, m_{2})$ and $C^{2} = {c_{i}^{2}} (i = 1, 2, \dots, m_{2})$ , respectively.

Figure 4.

Encode table (left) and eight neighborhoods (right).

Edge contour detection

After obtaining single-pixel edge, a novel algorithm is employed to connect adjacent edge points and form edge contours without any branches. First, a new contour begins with an edge point that is defined as end point. Second, the position of next point on the contour can be calculated with the encoding value of current point. Finally, the type of the new point is detected. If it is the point defined as process point, then the second step and the last step are repeated. Otherwise, detection of this contour is completed. The key points are described as follows:

The edge points in $P^{2}$ are divided into four categories: isolated point, end point, process point, and branch point based on their encoding value. Given an edge point $p_{i}^{2} \in P^{2}$ , $p_{i}^{2}$ is defined as isolated point if there is zero 8-connectivity point, that is, the corresponding encoding value satisfy $c_{i}^{2} = 0$ . Similarly, $p_{i}^{2}$ is defined as end point if there is one 8-connectivity point, that is, $c_{i}^{2} = 1, 2, 4, 8, 16, 32, 64, 128$ . $p_{i}^{2}$ is defined as process point if there are two 8-connectivity points, for example, $c_{i}^{2} = 5, 10, 18, 20, 36, 40, 72 and so on$ . $p_{i}^{2}$ is defined as branch point if there are more than two 8-connectivity points, for example, $c_{i}^{2} = 21$ , 42, 74, 84, 85, 112, 146, 164, and so on.

Suppose an end point $p_{i}^{2}$ as the starting point of a contour l, the direction from $p_{i}^{2}$ to the next point $p_{i + 1}^{2}$ can be specified by the encoding value $c_{i} = 2^{m}$ as shown in equation (2)

directio n_{i} = m

(2)

Contrarily, we define the direction from $p_{i + 1}^{2}$ to $p_{i}^{2}$ as shown in equation (3)

\bar{c_{i}} = {\begin{matrix} 2^{m - 4} & if (m - 4) \geq 0 \\ 2^{m + 4} & otherwise \end{matrix}

(3)

In most instances except for cases mentioned in key point 4, equation (2) and (3) can be combined into equation (4) to calculate $\bar{c_{i}}$ directly by the encoding value

\bar{c_{i}} = {\begin{matrix} 1 & if c_{i} = 16 \\ 2 & if c_{i} = 32 \\ 4 & if c_{i} = 64 \\ 8 & if c_{i} = 128 \\ 16 & if c_{i} = 1 \\ 32 & if c_{i} = 2 \\ 64 & if c_{i} = 4 \\ 128 & if c_{i} = 8 \end{matrix}

(4)

Then, the position of $p_{i + 1}^{2}$ can be calculated by equation (5)

l_{i + 1} = {\begin{matrix} (x_{i} - 1, y_{i} - 1) & if c_{i} - \bar{c_{i - 1}} = 1 \\ (x_{i}, y_{i} - 1) & if c_{i} - \bar{c_{i - 1}} = 2 \\ (x_{i} + 1, y_{i} - 1) & if c_{i} - \bar{c_{i - 1}} = 4 \\ (x_{i} + 1, y_{i}) & if c_{i} - \bar{c_{i - 1}} = 8 \\ (x_{i} + 1, y_{i} + 1) & if c_{i} - \bar{c_{i - 1}} = 16 \\ (x_{i}, y_{i} + 1) & if c_{i} - \bar{c_{i - 1}} = 32 \\ (x_{i} - 1, y_{i} + 1) & if c_{i} - \bar{c_{i - 1}} = 64 \\ (x_{i} - 1, y_{i}) & if c_{i} - \bar{c_{i - 1}} = 128 \end{matrix}

(5)

In particular, $p_{i - 1}^{2}$ does not exist if $p_{i}^{2}$ is an end point, for example, $\bar{c_{i - 1}}$ .

3. If a process point $p_{i}^{2}$ is detected in a contour $l$ , the encoding value of $p_{i}^{2}$ should be updated according to equation (6)

c_{i}' = c_{i} - \bar{c_{i - 1}'}

(6)

An example is shown in Figure 5 where point 2 and point 3 are process point. First, the starting point of a contour is the end point 1 with its corresponding encoding value $c_{i} = 64$ , the position of point 2 on the contour is calculated by equations (4) and (5) as shown in Figure 5(a). Second, the position of point 3 on the contour is calculated by equations (4) and (5) and then the encoding value of point 2 is updated by equation (6) as shown in Figure 5(b). Third, the position of point 4 on the contour is calculated by equations (4) and (5) and then the encoding value of point 3 is updated by equation (6) as shown in Figure 5(c).

4. If a branch point $p_{i}^{2}$ is detected in a contour $l$ as shown in Figure 6(a), the encoding value of all eight-connectivity edge points and their types should be updated as shown in Figure 6(b). The update algorithm for branch points is summarized in Algorithm 1.

Figure 5.

Illustration of process point updating: (a) calculate position of point 2, (b) update the encoding value of point 2 and calculate position of point 3, and (c) update the encoding value of point 3 and calculate position of point 4.

Figure 6.

Illustration of branch point updating: (a) the detected branch point i and (b) update the encoding value and their types of all eight-connectivity edge points.

Algorithm 1

Update the encoding value of all eight-connectivity edge points of branch point $p_{i}^{2}$ whose encoding value is $c_{i}'$

For i = 0:7 do

if $(c_{i}^{'} - 2^{7 - i}) > 0$ then

$directio n_{i} = 7 - i$ ;

update adjacent edge points in $directio n_{i}$ according to equations (3), (5), and (6);

end if

end for

End of Algorithm 1

Keep in mind that the proposed contour detection method is especially suitable for application in embedded system since it is faster and requires lower memory resource than other methods by calculating the position of the next point on the edge contours instead of searching for its eight-connectivity points. We present the detailed analysis in section “Discussion and comparison.”

Criteria are proposed below to exclude edge contours that are not salient enough:

Exclusion criteria 1 (E1): number of points supporting the edge contour is greater than a given threshold $T h_{1}$ ;

Exclusion criteria 2 (E2): distance between lines (formed by joining the end points of the edge contour), and the middle point is larger than a given threshold $T h_{2}$ .

A set of edge contours $E^{3} = {e_{i}^{3}} (i = 1, 2, \dots, m_{3})$ (without any branch) is achieved, in which each element represents a set of adjacent edge points $e_{i}^{3} = {p_{j}^{3}} (j = 1, 2, \dots, m_{j})$ .

Contour segmentation and merging

Segmentation

Since elliptic edge contours should be smooth and contain no inflexion point, contour segmentation will be performed on edge contours at split points. Ideally, smooth edge contour means that the change of curvature between two adjacent points is almost constant. Given an edge contour as the collection of points $e^{3} = (p_{1}, p_{2}, \dots, p_{n})$ and its corresponding gradient as $θ = (θ_{1}, θ_{1}, \dots, θ_{n})$ , then, $G = (g_{1}, g_{1}, \dots, g_{n})$ represent the change of gradient that can be calculated below

G = | θ \otimes g | \Rightarrow G_{i} = θ_{i} \cdot g (1) + θ_{i + 1} \cdot g (2)

(7)

where $g = [\begin{matrix} - 1 & 1 \end{matrix}]$ is the one-dimensional convolution mask.

Finally, every local maximum value in $G = (g_{1}, g_{1}, \dots, g_{n})$ is calculated, and five maximum values of $s_{i}$ are selected as split points

\begin{matrix} S = (s_{1}, s_{1}, \dots, s_{n - 1}) \\ s_{i} = {\begin{matrix} 1 & ((g_{i} > g_{i - 1}) \land (g_{i} > g_{i + 1})) \land (abs (g_{i} - g_{i - 1}) > T h_{3}) \\ 0 & otherwise \end{matrix} \end{matrix}

(8)

where $T h_{3}$ is a given threshold. An example is shown in Figure 7(a).

Figure 7.

Illustration of segmentation and merging: (a) split points (red plus) by segmentation, (b) edge contours obtained by segmentation, and (c) new edge contour by merging.

Merging

Due to image noise or overlapping, some of the segments of an edge contour may belong to same ellipse. This may lead to additional calculations in the step of grouping. Consequently, an effective merging method is presented to improve calculation speed. Let $e^{3}$ be an edge contour that is split into seven segments $E = {e_{1} e_{2} e_{3} e_{4} e_{5} e_{6} e_{7}}$ , as shown in Figure 7(b). Given a pair of segments $e_{i}^{4}, e_{j}^{4} \in E$ , supposing both the two segments satisfy E1 and E2, $e_{i}$ and $e_{j}$ are merged as a new edge contour (Figure 7(c)) if they satisfy the pair grouping strategy, otherwise, they are marked as “irrelevant” and do not need repetition of pair grouping strategy as shown in section “Extraction of ellipse (edge contours grouping).” This is the main reason why the proposed merging method almost makes no additional computation. Moreover, the new edge contours are more discriminative for conditions I and II as shown in section “Pair grouping strategy.” Above all, the set of smooth edge contours without any branches after segmentation is defined as $E^{4} = {e_{i}^{4}} (i = 1, 2, \dots, m_{4})$ .

Extraction of ellipse (edge contours grouping)

After smooth edge contours detection, edge contours, which belong to same ellipse, are grouped together.

Pair grouping strategy

Given two edge contours $e_{i}^{4}, e_{j}^{4} \in E$ , the flowchart for determining whether two edge contours belong to same ellipse is shown in Figure 8. It should be noted that condition III is the necessary and sufficient condition, for example, two edge contours belong to same ellipse if the relationship between the two edge contours satisfies condition III and vice versa. However, the high computational complexity of condition III requires long computation time. Therefore, two relatively simple conditions (necessary conditions) are proposed to improve the efficiency.

Figure 8.

Pair grouping strategy.

Pair selection method

Condition I is inspired by the fact that “relative” gradient direction is same everywhere on the edge of an ellipse (from inside/outside to outside/inside). Given $e_{i}^{4} = P_{i}^{4} = (p_{1}, p_{2}, \dots, p_{n})$ and $θ_{i}^{4} = (θ_{1}, θ_{2}, \dots, θ_{n})$ as a edge contour and its corresponding gradient, respectively. Considering line segment $l_{i}$ formed by joining the end points of $e_{i}^{4}$ . Let $p_{n / 2}$ be the middle point on edge contour $e_{i}^{4}$ and $p_{mid}$ be the middle point on line $l_{i}$ , then we can obtain vector $v = (x_{n / 2} - (x_{1} - x_{n}) / 2, y_{n / 2} - (y_{1} - y_{n}) / 2)$ and the angle $θ_{v}$ which is the anticlockwise angle from the positive direction of x coordinate to the vector v. “Relative” gradient direction of edge contour $e_{i}^{4}$ can be defined as

D_{e_{i}^{4}} = {\begin{matrix} - & if \frac{3 π}{2} > | θ_{v} - θ_{\frac{n}{2}} | > \frac{π}{2} \\ + & otherwise \end{matrix}

(9)

As shown in equation (9), negative value represents the edge contour gradient direction from outside to inside, while positive value represents the opposite direction. Figure 9 shows two ellipses in different “Relative” gradient direction. The value of $D_{e}$ of the left ellipse is negative since the direction of vector v is opposite to the direction of gradient, while the value of $D_{e}$ of the right ellipse is positive since the direction of vector v is same as the direction of gradient. So, the condition I for two edge contours $l_{i}^{4}$ and $l_{j}^{4}$ can be expressed as

C_{1}^{12} = {\begin{matrix} 1 & if D_{l_{i}^{4}} D_{l_{j}^{4}} > 0 \\ 0 & otherwise \end{matrix}

(10)

Figure 9.

“Relative” gradient direction.

Condition II contains requirements for both the shape and location of the edge contours that belong to same ellipse. Let the function of $l_{i}$ be $f (x) = ax + by + c = 0, a \geq 0$ , we define the relative position between line $l_{i}$ and edge contour $e_{j}$ as $R_{l_{i}}^{e_{j}}$ . If $i = j$ , $R_{l_{i}}^{e_{i}}$ is obtained by equation (11)

R_{l_{i}}^{e_{i}} = {\begin{matrix} + & if f (p_{\frac{n}{2}}) > 0 \\ - & otherwise \end{matrix}

(11)

If $i \neq j$ , let $F_{i}^{+}$ be the number of point $p_{j} \in e_{j}$ that satisfy $a p_{x} + b p_{y} + c \geq 0$ while $F_{j}^{-}$ be the number of point $p_{i} \in a_{2}$ that satisfy $a p_{x} + b p_{y} + c < 0$ , then $R_{l_{i}}^{e_{j}}$ is obtained by equation (12)

R_{l_{i}}^{e_{j}} = {\begin{matrix} + & if \frac{F_{i}^{-}}{F_{i}^{+}} < T h_{4} \\ - & if \frac{F_{i}^{+}}{F_{i}^{-}} < T h_{4} \end{matrix}

(12)

where $T h_{4}$ denotes a given threshold which is a very small value. As expected, the edge contour $e_{j}$ appears in a suitable region relative to edge contour $e_{i}$ if $R_{l_{i}}^{e_{i} e_{j}} = R_{l_{i}}^{e_{i}} R_{l_{i}}^{e_{j}} < 0$ . However, the equation can only indicate location requirements. Fortunately, the combination of $R_{l_{i}}^{e_{i} e_{j}}$ and $R_{l_{j}}^{e_{i} e_{j}}$ can indicate requirements for both shape and location, without requiring any additional conditions. So, condition II for edge contours $l_{i}^{4}$ and $l_{j}^{4}$ can be

C_{2}^{ij} = {\begin{matrix} 1 & if ((R_{l_{i}}^{e_{i}} R_{l_{i}}^{e_{j}} < 0) \land (R_{l_{j}}^{e_{i}} R_{l_{j}}^{e_{j}} < 0)) \\ 0 & otherwise \end{matrix}

(13)

Condition III (necessary and sufficient conditions) is a fitting error measures. An ellipse is fit to all the supporters of two edge contours in a pair by mean square error minimization. The fitting error is defined by a ratio as follows

e r r = 1 - \frac{n}{N}

(14)

where N is the number of supporters supporting two arcs in pair and n is the number of supporters not only supporting two arcs in pair but also supporting the fitting ellipse. Obviously, there exists a high possibility that two edge contours belong to same ellipse if err is small. So, the condition III can be expressed as

C_{3}^{ij} = {\begin{matrix} 1 & if (err < T h_{5}) \\ 0 & otherwise \end{matrix}

(15)

where $T h_{5}$ denotes a given threshold.

Procedure of grouping

In section “Pair grouping strategy,” the pair grouping strategy defines three important conditions. We define detected ellipses as a set of edge contours $S^{5} = {S_{i}^{5}} (i = 1, 2, 3, \dots, m_{5})$ , and each element represent a set of edge contours $S_{i}^{5} = {e_{j}^{4}} (j = 1, 2, \dots, m_{j})$ that belong to same ellipse. The detail of grouping algorithm for the detection of ellipse (Algorithm 2) is presented in this subsection.

Algorithm 2

Group edge contours that belong to an ellipse among $E^{4}$

for all edge contours $e_{i} \in E^{4}$ do

enter $e_{i}$ into $S_{α}$

for all edge contours $e_{j} \in E^{4}$ , $j \neq i$ do

if $(S_{α}, e_{j})$ satisfy pair grouping strategy then

enter $e_{j}$ into $S_{α}$

end if

end for

enter $S_{α}$ into $S^{5}$ . Remove all edge contours in $S_{α}$ from $E^{4}$

end for

End of Algorithm 2

Finally, parameters of detected ellipses can be calculated based on least squares fitting technique for each $S^{5} = {S_{i}^{5}} (i = 1, 2, 3, \dots, m_{5})$ .

Discussion and comparison

A detailed analysis is conducted for major steps of the proposed ellipse detection theoretically by comparing them with other literature. And an example of real image (comes from our experiment) as well as all steps of detection ellipse is shown in Figure 10.

Figure 10.

Illustration of ellipse detection process: (a) test image (2048 × 2048 pixels), (b) edge image, (c) edge contours, (d) segmentation and merging effect, (e) grouping effect, and (f) fitting ellipses.

Edge contours detection

The position of each point on a contour is calculated based on encoding value as specified in section “Edge contours detection,” while other approaches search edge points around the last point.^16–18,20 However, search algorithm is very time-consuming because it searches from the whole set of edge points. Some approaches create a sparse matrix to mark edge points to improve the calculation speed according to Kovesi’s code.²⁴ On one hand, the proposed method requires lower memory resource, which allows to achieve calculation in limited-performance embedded system especially handling high-resolution images. On the other hand, the proposed method is performed faster than search algorithm in embedded system because the sparse matrix must be stored in external storage (static random-access memory (SRAM)). Table 1 shows the running time in embedded system as illustrated in Figure 2. The result shows that the proposed algorithm outperforms the most commonly used algorithm in terms of both time complexity and space complexity for the embedded system.

Table 1.

Time complexity of edge contour detection.

	Search algorithm using sparse matrix	Search algorithm	Proposed method
Execution time (ms)	8.392	44.823	8.96
Storing time to SRAM (ms)	1.667	0	0
Reading time from SRAM (ms)	13.336	0	0
Total time complexity (ms)	23.395	44.823	8.96

SRAM: static random-access memory.

Contour segmentation and merging

Contours segmentation is performed by calculating the change of gradient. Unlike the method of Prasad et al.,¹⁷ this method does not need to fit lines and is fast to calculate. A fast method, which avoids time-demanding segmentation, is proposed by Fornaciari et al.²⁰ However, Fornaciari et al.²⁰ forcibly split curves into shorter segments even if the curvature of contours changes continuously and smoothly, the procedure may generate many short contours which cause bigger calculation error of geometrical characteristics.

Pair grouping strategy

As described in section “Extraction of ellipse (edge contours grouping),” the two fast and effective necessary conditions (conditions I and II) are introduced before condition III. Condition I is based on “relative” gradient direction, while condition II indicates requirements for both shape and location. Many articles^16,20,22 compute the convexity of edge contours for grouping, while the proposed method does not need to because it is implied in condition II. Our method is faster to compute and is more discriminative. For example, for 214 edge contours (refer to Figure 10), the theoretical execution time for checking is 22,791 (calculated by combination $C_{214}^{2}$ ). With the effect of marking in merging and Algorithm 1, the execution times is reduced to 11,009 (condition I) + 5674 (condition II) + 174 (condition III), as shown in Table 2.

Table 2.

Execution times of each condition in section “Extraction of ellipse (edge contours grouping).”

	Execution times
Theoretical times in total	22,791
Condition I	11,009
Condition II	5674
Condition III	174

Discussion on control parameters

Five control parameters of the proposed method are discussed in this section. The control parameter $T h_{1}$ is used for removing short edge contours. As mentioned in E1, edge contours will be excluded if the number of points supporting the edge contour is less than $T h_{1}$ , because such short edge contours are easily effected by noise and rarely influence the detected results except more computation. The discussion can be found in Liu and Qiao²² where the range is $[2, 32]$ . We use $T h_{1} = 32$ for dataset II (section “Real images”) considering the high-resolution images, while $T h_{1} = 10$ for dataset I (section “Real images”).

The control parameter $T h_{2}$ is used for removing straight lines. The value of $T h_{2}$ can be 0 in theory, and it is preferable to set $T h_{2} = 2$ considering the possible error.

The control parameter $T h_{3}$ is used for segmentation. It is clear that too small value of $T h_{3}$ is useless for detecting split points, while too large value may miss the actual split points. Numbers of experiments show the range of the control parameter $T h_{3}$ is [5, 15], and we choose 10° as the value of $T h_{3}$ .

The control parameter $T h_{4}$ is used for condition II. The value of $T h_{4}$ will be theoretically zero if two edge contours belong to same ellipse, so we chose a small value 0.1.

The control parameter $T h_{5}$ is used for fitting error. The general range of $T h_{5}$ is $(0, 0.1)$ , which depends on the distortion of edge contour. The value in the right side of range will be preferable to use if the distortion is large, while the left side of range will be chosen in the opposite case. Here, we set $T h_{5} = 0.05$ .

Experimental results

Various experiments are conducted to evaluate the proposed method for ellipse detection, and the results are compared with some recent researches proposed by Liu and Qiao,²² Prasad et al.,¹⁷ and Fornaciari et al.²⁰ F-measure,¹⁷ precision, and recall are used to evaluate the detection effectiveness; the larger, the better. One group of synthetic images and two groups of real images are considered in experiments in sections “Synthetic images” and “Real images,” respectively. All methods are implemented in C except Prasad et al.¹⁷ and run in MATLAB on a personal computer (PC) installed with i7 system for simulation, without parallelization.

Synthetic images

The proposed method and compared methods are tested in various synthetic images which contain occluded or overlapping ellipse targets. First, m ellipses are generated in a synthetic image (300 × 300) by randomly selecting parameters of ellipse, then manual adjustments are performed if necessary to obtain occluded or overlapping ellipses. The value of semi-axis is limited in the range $[10, \sqrt{300^{2} + 300^{2}} / 2]$ according to the size of images. $m \in {4, 8, 12, 16, 20, 24}$ is selected, and 100 images of both occluded and overlapping ellipses are generated for each value of m.

Figures 11 and 12 show the performance of the proposed method and compared methods. The experiments on images show that the performance of Prasad et al.¹⁷ method and the proposed method is the best. Liu and Qiao²² method gives a poor performance especially in occluded ellipses for obvious limitations in edge contours extraction where it does not process the unsmoothed part of edge contours. Fornaciari et al.²⁰ method shows lack of capacity of detecting images with less edge pixels. Several examples of synthetic image detection are given in Figures 13 and 14.

Figure 11.

Comparison of performance of different methods for synthetic images with occluded ellipses.

Figure 12.

Comparison of performance of different methods for synthetic images with overlapping ellipses.

Figure 13.

Examples of performance of different methods for synthetic images with occluded ellipses: (a) original ellipses, (b) our proposed method, (c) Prasad et al., (d) Fornaciari et al., and (e) Liu and Qiao.

Figure 14.

Examples of performance of different methods for synthetic images with overlapping ellipses: (a) original ellipses, (b) our proposed method, (c) Prasad et al., (d) Fornaciari et al., and (e) Liu and Qiao.

Real images

The proposed method and the compared methods are evaluated on two different sets of real images. One set (called dataset I) is a portion of Caltech 256 database²⁵ with low-resolution images (about 300 × 200 pixels), the other set (called dataset II) is the set of images of satellite models taken in darkroom, with high-resolution images (2048 × 2048 pixels).

Dataset I

Images in dataset I (a total of 300 images) are randomly chosen from Caltech 256 with only one selection criteria that the image must contain at least one ellipse with adequate edge pixels (at least 20). The result of both effectiveness and execution time are shown in Table 3. Some results are depicted in Figure 15.

Table 3.

Performance on dataset I.

	The proposed method	Prasad et al.	Fornaciari et al.	Liu and Qiao
Average F-measure	0.487	0.479	0.441	0.102
Average time (ms)	14.56	178.65	8.75	34.63

Figure 15.

Examples of comparison of performance of mentioned methods in real images (dataset I): (a) original ellipses, (b) our proposed method, (c) Prasad et al., (d) Fornaciari et al., and (e) Liu and Qiao.

The proposed method gets better results than all other existing methods because of a good trade-off between execution time and detection effectiveness. Prasad et al.¹⁷ method and the proposed method are the best of all methods in detection effectiveness, but Prasad et al.¹⁷ method is quite slow for application of histogram count in its grouping step as shown in Table 1. Fornaciari et al.²⁰ method is the best of all methods in execution time. The proposed method is the second best in performance, very close to Fornaciari et al.²⁰ method in terms of execution time and the best in terms of detection effectiveness (same as Prasad et al.¹⁷ method).

Dataset II

Since the proposed method aims at real-time detection for aerospace embedded application, numbers of experiments are conducted with different illuminations, distances, and angles to obtain images of satellite models in simulation of the space environment as shown in Figure 16 to form dataset II (a total of 400 images). Images from dataset II are with higher resolution (2048 × 2048) and more noisy than dataset I. All images are outputted, and the proposed method and other methods are evaluated off-line on the personal computer. Besides, the proposed method runs on embedded system where camera, DSP, and FPGA are integrated as shown in Figure 17.

Figure 16.

Experimental environment: motive mechanism and the satellite mockup.

Figure 17.

Embedded system.

The average F-measure at different distances is shown in Figure 18, while average image shooting time at a short distance is shown in Table 3. Some detection results of the compared methods are depicted in Figure 19. It seems that Liu and Qiao²² method cannot detect correct ellipse for the reason mentioned above. And the performance of Prasad et al.¹⁷ and Fornaciari et al.²⁰ methods is inferior, especially for image shooting at a short distance. This is mainly because the large ellipse is more likely to break into a set of edge contours with small integrity, and large error may occur at the calculated center of ellipse. The proposed method is the best in terms of effectiveness and computation time. It is worth noting that the proposed method performs best for image shooting at distance between 2 and 4 m since moderate edge points can be obtained, neither too much nor too little.

Figure 18.

Comparison of performance of different methods in dataset II.

Figure 19.

Examples of performance of different methods in real images (dataset II): (a) original ellipses, (b) our proposed method, (c) Prasad et al., (d) Fornaciari et al., and (e) Liu and Qiao.

The execution time (represented by updating rate) at different distance in embedded system is shown in Figure 20. As expected, the execution time is inversely proportional to the distance because the number of edge points decreases as the shooting distance increases. And it demonstrates that the proposed method can achieve real-time ellipse detection for embedded application.

Figure 20.

Execution time in embedded system.

Conclusion

This article proposes a novel and effective method for ellipse detection, which is suitable for large-resolution images in various embedded systems. First, smooth edge contours without any branches are extracted, a new edge contour detection method is employed to reduce time and space complexity, and segmentation and merging is performed to obtain the smooth contours. Second, three conditions are proposed as a pair selection method to group edge contours that belong to the same ellipse. The results show that the performance of the proposed method is superior in both effectiveness and computation time, and it is a real-time algorithm for embedded system with limited computational and memory resources.

Footnotes

Academic Editor: Francesco Massi

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

References

Rosin

. Ellipse fitting by accumulating five-point fits. Pattern Recogn Lett 1993; 14: 661–669.

Fitzgibbon

Pilu

Fisher

. Direct least-squares fitting of ellipses. IEEE Trans Pattern Anal 1999; 21: 476–480.

Chojnacki

Brooks

Hengel

AVD

. On the fitting of surfaces to data with covariances. IEEE Trans Pattern Anal 2000; 21: 1294–1303.

Taubin

. Estimation of planar edge contours, surfaces and non-planar space edge contours defined by implicit equations, with application to edge and range image segmentation. IEEE Trans Pattern Anal 1991; 13: 1115–1338.

Chaudhuri

. A simple least squares method for fitting of ellipses and circles depends on border points of a two-tone image and their 3-D extensions. Pattern Recogn Lett 2010; 31: 818–829.

Hough

. Method and means for recognizing complex patterns. US Patent 3069654, 1962.

Duda

Hart

. Pattern classification and scene analysis. New York: Wiley Publishers, 1973.

Oja

Kultanen

. A new edge contour detection method: randomized Hough transform (RHT). Pattern Recogn Lett 1990; 11: 331–338.

McLaughlin

. Randomized Hough transform: improved ellipse detection with comparison. Pattern Recogn Lett 1998; 19: 299–305.

10.

Kiryati

Eldar

Bruckstein

. A probabilistic Hough transform. Pattern Recogn 1991; 24: 303–316.

11.

Chien

Cheng

Lin

. Robust ellipse detection based on hierarchical image pyramid and Hough transform. J Opt Soc Am A 2011; 28: 581–589.

12.

Goneid

El-Gindi

Sewisy

. Method for the Hough transform detection of circles and ellipses using a 1-dimensional array. In: IEEE international conference on systems, man, and cybernetics, Orlando, FL, 12–15 October 1997, pp.3154–3157. New York: IEEE.

13.

Chan

. A new approach for efficient Hough transform for circles. In: IEEE pacific rim conference on communication, computer and signal processing, 1–2 June 1989, pp.99–102. New York: IEEE.

14.

Chia

AY-S

Leung

Eng

H-L

. Ellipse detection with Hough transform in one dimensional parametric space. In: IEEE international conference on image processing, San Antonio, TX, 16 September–19 October 2007, pp.333–336. Canada: IEEE.

15.

Zhang

Liu

. A robust, real-time ellipse detector. Pattern Recogn 2005; 38: 273–287.

16.

Hahn

Jung

Han

. A new algorithm for ellipse detection by edge contour segments. Pattern Recogn Lett 2008; 29: 1836–1841.

17.

Prasad

Leung

Cho

S-Y

. Edge curvature and convexity based ellipse detection method. Pattern Recogn 2012; 45: 3204–3221.

18.

Mai

Hung

Zhong

. A hierarchical approach for fast and robust ellipse extraction. Pattern Recogn 2008; 41: 2512–2524.

19.

Qiao

Ong

. Connectivity-based multiple-circle fitting. Pattern Recogn 2004; 37: 755–765.

20.

Fornaciari

Prai

Cucchiara

. A fast and effective ellipse detector for embedded vision applications. Pattern Recogn 2014; 47: 3693–3708.

21.

Chia

AYS

Rahardja

Rajan

. A split and merge based ellipse detector with self-correcting capability. IEEE Trans Image Process 2011; 20: 1991–2006.

22.

Liu

Z-Y

Qiao

. Multiple ellipses detection in noisy environments: a hierarchical approach. Pattern Recogn 2009; 42: 2421–2433.

23.

Lam

Lee

Suen

. Thinning methodologies-A comprehensive survey. IEEE Trans Pattern Anal 1992; 14: 869–885.

24.

Kovesi

. MATLAB and octave functions for computer vision and image processing, http://www.peterkovesi.com/matlabfns/

25.

Griffin

Holub

Perona

. Caltech-256 object category database, http://www.vision.caltech.edu/Image_Datasets/Caltech256/

Effective ellipse detection method in limited-performance embedded system for aerospace application

Abstract

Keywords

Introduction

Extraction of elliptic edge contours

Edge point detection

Edge thinning

Edge contour detection

Algorithm 1

Contour segmentation and merging

Segmentation

Merging

Extraction of ellipse (edge contours grouping)

Pair grouping strategy

Pair selection method

Procedure of grouping

Algorithm 2

Discussion and comparison

Edge contours detection

Contour segmentation and merging

Pair grouping strategy

Discussion on control parameters

Experimental results

Synthetic images

Real images

Dataset I

Dataset II

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References