IEEE TRANSACTIONS ON IMAGE PROCESSING 3
Some researchers generalize the LS detection method to
be a multi-functional detector which can jointly detect the
LS and elliptic arcs. ELSDc proposed by P
˘
atr
˘
aucean et al.
[15] uses an improved LSD [26] version for detecting LS,
and then iteratively searches the remaining LSs from the
start and end points of the detected LS. Eventually, both LS
detection and grouping tasks are established simultaneously.
Notably, ELSDc stands out other methods by detecting LSs
from the greyscale image instead of binary edge such that
abundant gradient and geometric cues can be fully exploited.
ELSDc and our proposed method are both based on LSD
[26] for LS detection from the greyscale image, but they are
fundamentally different from the generated LS type, ellipse
candidates generation and validation strategies. Our method
merely generates the arc-support LSs and do not chain them
in the LS generation step. Moreover, ELSDc fits and validates
the locally grouped LSs, omitting the global situation, which
may be prone to produce the false positives (Fig. 1(g)).
Arc-support LS is our previous work as introduced in [27],
each pair of which is successfully used for circle detection.
However, it cannot handle the ellipse detection scheme since
an arbitrary ellipse cannot be determined by two paired LSs.
Admittedly, ellipse detection owns much higher complexity
and requires more geometric cues. For example, the continuity
feature, which is neglected in [27], can be fully embodied in
the arc-support group and is important in ellipse detection.
Therefore, the careful arc-support groups forming, compli-
cated geometric constraints, accurate ellipse generation and
clustering, and novel validation strategy accustomed to ellipse
detection are required, which will be addressed in this paper.
The main research purpose of this paper is to propose
a high-quality ellipse detection method to handle the long-
standing issue that cannot detect ellipses both accurately and
efficiently in ellipse detection field. To that end, for the first
time, we take the advantage of arc-support LSs for ellipse
detection. The arc-support groups are formed by robustly
linking the consecutive arc-support LSs which share similar
geometric properties in point statistics level. Each arc-support
group will be measured and assigned a saliency score. Sec-
ondly, we generate the initial ellipse set by two complemen-
tary approaches both locally and globally. The superposition
principle of ellipse fitting and the novel geometric constraints,
which are polarity constraint, region restriction and adaptive
inliers criterion, are employed to consolidate the proposed
method’s accuracy and efficiency. Thirdly, we decompose the
5D ellipse parameter space into three subspaces according to
ellipse center, orientation and semi-axes and perform three-
stage efficient clustering. Finally, the candidates which pass
the rigorous and effective verification will be refined by fitting
again.
The rest of this paper is organized as follows. Section
II introduces the preliminaries about arc-support LS and
superposition principle of ellipse fitting. Section III presents
the high-quality ellipse detection framework, as a four-stage
detection procedure: arc-support groups forming, initial ellipse
set generation, clustering, and candidate verification. Section
IV analyzes the computation complexity of the proposed
ellipse detection algorithm. Experimental results, as well as the
P
Level-line angle
Gradient angle
(a)
(b)
(c)
Fig. 2. Level-line angle and two types of LS. (a) the level-line angle is
acquired by clockwise rotating the gradient angle 90
◦
; (b) greyscale image;
(c) straight and arc-support LSs generated from (b).
Gradient
Direction
Acr-support
Direction
Gradient
Direction
Acr-support
Direction
Fig. 3. Features of arc-support LS. (a) the overall gradient direction in the
local greyscale area is same as arc-support direction and the three main angles
in the corresponding level-line map change anticlockwise; (b) the conter-
example of (a).
accuracy and efficiency detection performance of the proposed
method, are detailed in Section V. Section VI concludes the
paper.
II. PRELIMINARY
In this section, the arc-support LS and its appendant proper-
ties are introduced as the basic geometric primitives for ellipse
detection. Then we develop a superposition principle of fast
ellipse fitting, which will save running time for the ellipse
generation.
A. Arc-support LS
In image processing, LS mainly derives from two situations,
as shown in Fig. 2. The first type LS comes from the support
region where points share nearly the same level-line angle and
overall distribute straight. Another type of LS derives from the
arc-support region whose distribution changes like a curve.
Thus, we call the LS approximated from arc-support region
as “arc-support LS”. Arc-support LS is built on top of LSD
[26] as it is superior to other methods due to its efficiency and
false control ability. The corresponding extraction procedures
can be found in [27]. With the help of arc-support LS, the
straight LS can be pruned while the arc geometric cues remain.
Hereon, some properties of arc-support LS critical for ellipse
detection are detailed.
1) Arc-support Direction: Different from conventional LS,
arc-support LS carries the nature of convexity, standing for
the ellipse center direction of an elliptic arc, namely the arc-
support direction, as shown in Fig. 3. Assume that the two
terminals of the circumscribed rectangle of the support region
are A and B and the centroid is C. Thus the main angle of
the support region is denoted as ∠
−−→
AB and can be set to
arctan
P
p
i
∈Region
sin(level-line angle(p
i
))
P
p
i
∈Region
cos(level-line angle(p
i
))
!
. (1)