Open Journal of Applied Sciences, 2013, 3, 10-15
Published Online March 2013 (http://www.scirp.org/journal/ojapps)
Mining Corner Points on the Generic Shapes
M. Sarfraz1, Z. N. K. Swati2
1Department of Information Science, Kuwait University, Adailiya Campus, P.O. Box 5969, Safat 13060, Kuwait
2Department of Computer Science and Information Technology, Karakoram International University, Gilgit-Baltistan, Pakistan
Received 2012
ABSTRACT
This paper designs and implements a corner detection algorithm for mining corner points on the generic shapes. The
proposed corner detector detects corners by using combination of one rectangle and two ellipses (REE) with different
parameter settings in their descriptions. REE combination slides along the boundary of the shape and records number of
boundary points in each rectangle and ellipses. REE setup represents both local and global views of the image outline.
The proposed technique presents a natural corners detection methodology to detect all true corners accurately. This
technique is consistent with human vision system
Keywords: mining; corner points; corner detector; planar curves; generic shapes
1. Introduction
The extraction of corner points is useful for computer
applications such as image recognition, segmentation,
description, and data compression. Corner points play
significant role in the area of computer graphics, pattern
recognition, and computer vision. Corner points take part
in document types object analysis such as map, chart,
grid, table, and graph analysis. These points are used in
multi-signal representation, shapes illustration, stereo
system visualization, to track the movement of objects,
image matching, construction of 2D mosaics [17], and
the early phase of contour drawing systems. Many corner
detection algorithms have been proposed in the existing
literature [3-22].
Rosenfeld and Johnston [8] use k-cosine angle mea-
surement to find corners. Rosenfeld and Weszka [9] in-
troduce some modification of [8] in which the maxima of
the difference between successive of the averaged
k-cosine angle on a digital curve between the k backward
and forward vector were used. Freeman and Davis [6]
corner detector contains the chain scanned [8] with line
sliding along the contour. The change in local curvature
is measured by calculating the difference in angles be-
tween consecutive segment locations and detects corners
where highest change in curve occurs. The corner detec-
tor of Beus and Tiu [3] was modification of [6] which
introduces an arm limit value τ to specify the upper
bound for length of moving line.
The problem of corner detection can be divided into
two types. First one is boundary-based approach and
second one is region-based approach. This paper pro-
poses a new corner detection algorithm using boun-
dary-based approach. It is different from ordinary tech-
niques [3 ,5,6,8-16,20] which detect cosine angle for
change in the boundary curve . The proposed algorithm
defines its setting of geometry as a rectangle (R) and two
ellipses (EE) for global, intermediate and local views
respe ctively. Hence the setting can be denoted as REE
which is different than EER which was defined in [23].
Like in [15,16], it takes different scales/views (global,
intermediate, local) of boundary curve with defined set
of shape s (REE). Different para meters, in the description
of REE determine global, intermediate, and local views
of the boundary outline curve of an image. This combi-
nation is sliding along the planer curve and curve points
are recorded at each move. Recorded curve points at
each step are used for corner selection.
The proposed method REE and the method EER in [23]
are using two ellipses and a rectangle. But the two me-
thods are very different. In the proposed method, the
rectangle used is outside the two ellipses whereas in [23],
it is opposite. In addition to the new proposed method
based on REE, the paper also makes a compa rative study
of four popular corner detection algorithms [3,4,6,15] for
boundary of shapes presented. The proposed technique is
useful to detect corners from generic shape boundaries
with or without no ise.
The organization of the paper is done as follows. Sec-
tion 2 gives basic formulation of the technique as well as
the design of the proposed corner detection algorithm.
Corner detection results are demonstrated in Section 3. A

M. Sarfraz ET AL.
comparative study, with the existing algorithms in the
current literature, is made in Section 4. The paper is fi-
nally concluded in Section 5.
2. Proposed Algorithm
Proposed technique of corner detection is based on rec-
tangle R and two ellipses E1 and E2 sliding along the
given curve. E1 and E2 are embedded in R such that
21
EER ⊃⊃
. The geometry of the rectangle and two
ellipses is shown in Figure 1. To gather information
about the locality of neighboring curve points, proposed
technique uses rectangle and ellipses shown having
common center at pi.
Figure 1. Geometrical structure of NEW Algorithm.
The mathematical relations of R and two ellipses E1 and
E2 is described in Equation (1). The geometric structure
of Figure 1 has been adopted as follows:
• The length and width of the rectangle R ar e con-
sidered to be the lengths 2A and 2B respectively.
• The semi minor axis and semi major axis of the
ellipse E1 are considered to be the lengths 3A/4
and B respectively.
• The semi minor axis and semi major axis of the
ellipse E2 are considered to be the lengths 3A/4
and B/2 respectively.
1
1
2
2 2,
3 /4,
3 /4/2,
''
R AB
E AB
E AB
slope S
π
π
θ
= ×

=××


=××


=
(1)
The length of rectangle and semi major axes of el-
lipses lie in the direction of slope ‘S’. Hence the wid th of
rectangle and semi minor axes of ellipses lie at right an-
gle to the slope ‘S’ of the contour with center at curve
point pi, 1 ≤ i ≤ n, where n is the total number of contour
points. Slope of curve point at pi is determined along the
line drawn by calculating mean of five points (including
pi) on both sides of pi.
By taking boundary point pi as center, the direction of
rectangle R is adjusted along major axes of the Ellipses.
Similarly, ellipses E1 and E2 having same center at
i
p
are
configured with same procedure. Thus
21
EER ⊃⊃
.
Figure 2. Snapshot of NEW Algorithm.
Combination of rectangle and ellipses slides on given
curve and number of adjacent points for rectangle and
each ellipse. It is recorded from
Ai
p
−
to
Ai
p+
which
lie in the area R, E1, and E2. Let nRi, nE1,i and nE2,i de-
scribe the total number of curve points in rectangle R,
ellipses E1, and E2 respectively, with centers at ith boun-
dary point. For example in Figure 2, nRi = 23, nE1,i = 18,
and nE2,i = 15. Values of nRi, nE1,i and nE2,i, for each
boundary point, are finally used while marking the abso-
lute positions of corner point s.
Proposed algorithm adopts natural corner detection
methodology by combining three levels of views.
Combin ation of one rectangle and two ellipses represents
three special views of curve points. It traces number of
counts nRi, nE1,i and nE2,i, for each boundary point. It
calculates sufficient information to mark the absolute
corners. Rectangle 1 R represents global view of boun-
dary points and allowing only those boundary points for
whi ch
0
11 =− ER
. These contour points are
represented by set the G as follows:
{ }
{ }





−==
=−==
ii
ii
nEnRPG
nEnRPG
,1
,1
Or
0
(2)
Set G describes wider view of a shape and does not take
false corners (at contour noise/irregularities). This is
demonstrated in Figure 3 which shows some snapshots
with curves noise/irregularity. Center points pi’s in Fig-
ures 3(a) and 3(b) look like corners if the local view of
contour is taken, but if we observed the global view
(broader part of the curve), these corners are rejected as
they do not qualify the Equation (2). In general,
0
11 =− ER
pointing with arrows. Curve points in Fig-
ures 3(c) and 3(d) are only be considered in group G.
Curve points lying in the set G are corner points in a
relative way, they can be considered as candidate corner
points. These points describe common region of contour
where the actual corner is located as shown in the circled
regions in Figure 4. Set G describes connected points that
repr esent a group and there is a possibility that more than
one group may exist in set G. For each group, there is
only single point which represents actual cor ner . The
curve points in E2,i of values nE2,i less than threshold
'' η
are calculated for every group and smallest value nE2,i is
E2 E1
2B
2A
11

M. Sarfraz ET AL
selected as a corner. If in a group the number of points in
E2,i are lower than
'' η
then it means that corner point
does not exist in that group.
(a) (b) (c) (d)
Figure 3. Some snapshots of NEW Algorithm for irregular boundary. (a), (b) are not qualified by G, and (c) is rejected due
threshold ‘η’.
Figure 4. Some shapes marked (bold) with contour points in
set G. Corners are marked in grey.
3. Experimental Results
To measure the accuracy of a corner detection algorithm,
the absolute location of corner points must be known
already. A board of 10 judges was used to mark the ab-
solute position of corner points for standard shapes.
Corner positions decided by majority were taken as ab-
solute position of corners [15,16].
These corner positions were used to judge the accuracy
of different corner detection algorithms. Detected corners
by proposed algorithm NEW are shown in Figure 8. One
can see that the corner points, detected by NEW, have
happened to be the same as detected by human eyes. It is
important to note that this evaluation is based on Accu-
racy, localization error, noise sensitivity, transformation
invariance, single response, parameter setting, and com-
putation time.
Figure 5. Algorithm for proposed corner detector.
0
20
40
60
80
100
120
FD BT CS AS New
%Correct %Incorrec t
Figure 6. Result comparisons for each corner detector.
12

M. Sarfraz ET AL.
Figure 7. Test shapes with actual corner points [15].
Figure 8. Corner detection by NEW Algorithm.
Figure 9. Corner detection by AS Algorithm [15].
Figure 10. Corner detection by FD algorithm [6].
Figure 11. Corner detection by BT algorithm [3].
Figure 12. Corner detection by CS Algorithm [4].
13

M. Sarfraz ET AL
4. Comparative Study
Different corner detection algorithms have been presented
for digital boundary and their comparison has also been
described by different authors. To evaluate a corner de-
tection algorithm, it will properly be tested on variety of
shapes. Four proposed Standard shapes, in Figure 7, con-
tain noise/irregularities along the boundary curves, dif-
ferent types of varying curves, and angle sharpness. These
types of variations are probable in real time shape contour.
These test shapes are used in this paper for compari-
son/evaluation of different corner detectors. Four popular
algorithms, namely BT[3], CS[4], FD[6], AS [15, 16]
have been taken for comparison in our study. The pro-
posed algorithm is referred as NEW.
A study of the five algorithms, in the light of the crite-
ria mentioned in Section 3, has been made. Figure 8-12
shows the results of the five algorithms for the proposed
test shapes in Figure 7 and their comparative graph is
described in Figure 6.
Accuracy results for true corner points detected by FD
corner detector were lowest (60%) for standard shapes. It
is clearly indicated (in im3 and im4 of Figure 10) that FD
corner detector ignores some true corners. Accurate cor-
ners marked by BT corner detector is 72% were better
than previous corner detector, but it also tends to miss
some important corners (in im4 of Figure 11). In case of
incorrect corner detection and localization errors, the per-
formance of BT is very good and is less than 10%. CS [4]
gives very good results in case of correct corner detection
which is 90%, but its false detection rate is high and is
17% which exceeds than BT. Accurate corners marked by
AS corner detector are 100%, but it also detects some
false corner points (in im2 of Figure 9). Performance of
this algorithm is better with respect to localization errors
and false detections which is 5%.
Figure 13. Corner detection by proposed Algorithm.
Figure 14. Corner detection by proposed Algorithm.
A considerable improvement can be seen in NEW that
correctly marked 100% true corners. Lowest percentage
of incorrect detection is 1% (in Figure 8) which is another
big advantage of the proposed algorithm. One can hardly
find localization error at any detected corner points. Per-
formance of this algorithm must be appreciated in heavy
noise conditions as well as complex shapes. No algorithm
could accurately find all corners of im2, due to complex
shape of the Figure. The proposed algorithm minimizes
the incorrect corner(s) detection rate. Figures 13, 14, and
15 show corner detection on some more Shapes.
Figure 15. Corner detection by proposed Algorithm.
5. Conclusion
The new corner detection technique is proposed which
does not involve curvature analysis and determination of
cosine angle, hence making it very efficient. A compara-
tive study of different corner detectors, based on proposed
parameters, is given. Proposed corner detector has various
advantages over previous corner detectors which are: (1)
most consistent with human vision of corners; (2) ratio of
false corner detection is extremely low; (3) very effi-
ciently; (4) does not affect with transformation changes (5)
highly insensitive to noise/irregularities along the curve;
(6) robust to minor changes in size and resolution; and (7)
very suitable for natural shapes/objects. Independent tun-
ing of three parameters (A, B and
η
) for optimum results,
once set appropriately, is enough for most of the shapes.
There are various applications where corner detection
algorithm can be used. Specifically in vectorizing outlines
of images [1] and other curve manipulation applications
[2], it is highly useful. The authors intend on such appli-
cations and use the proposed algorithm.
6. Acknowledgement s
This work was supported by Kuwait University, Re-
search Grant No. [WI 05/12].
14

M. Sarfraz ET AL.
REFERENCES
[1] M. Sarfraz, “Vectorizing Outlines of Generic Shapes by
Cubic Spline using Simulated Annealing,” International
Journal of Computer Mathematics, Taylor & Francis, Vol.
87, No. 8, 2010, pp. 1736 – 1751.
[2] M. Sarfraz, M. Z. Hussain and M. Hussain, “Shape
Preserving Curve Interpolation,” International Journal of
Computer Mathematics, Taylor & Francis, Vol. 89, No. 1,
2012, pp. 35 – 53.
[3] H. L. Beus and S. S. H. Tiu, “An Improved Corner De-
tection Algorithm based on Chain Coded Plane Curves,”
Pattern Recognition, Vol. 20, 1987, pp. 291-296.
[4] D. Chetverikov and Z. Szabo, “A Simple and Efficient
Algorithm for Detection of High Curvature Points in
Planner Curves,” Proceedings of 23rd workshop of Aus-
tralian Pattern Recognition Group, Steyr, 1999,
pp.175-184.
[5] E. R. Davies, “Application of the generalized Hough
transform to corner detection,” Computers and Digital
Techniques, IEE Proceedings E., Vol. 135, No. 1, 1988,
pp. 49-54.
[6] H. Freeman and L. S. Davis, “A Corner Finding Algo-
rithm for Chain-Coded Curves,” IEEE Trans. Computers,
Vol. 26, 1977, pp. 297-303.
[7] H. C. Liu and L. S. Srinath, “Corner Detection from
Chain-Code,” Pattern Recognition, Vol. 23, 1990, pp.
51-68.
[8] A. Rosenfeld and E. Johnston, “Angle Detection on Digi-
tal Curves,” IEEE Trans. Computers, Vol. 22, 1973, pp.
875-878.
[9] A. Rosenfeld and J. S. Weszka, “An Improved Method of
Angle Detection on Digital Curves,” IEEE Trans. Com-
puters, Vol. 24, 1975, pp. 940-941.
[10] M. Sarfraz and M. R. Asim, A. Masood, “Capturing Out-
lines using Cubic Bezier Curves,” Proc. of IEEE Interna-
tional Conference on Information & Communication
Technologies: from Theory to Applications, pp. 539 – 540,
2004.
[11] M. Sarfraz, A. Masood and M. R. Asim, “A Web Based
System for Capturing Outlines of 2D Objects,” Proc. of
International Conference on Information & Computer
Science, Dhahran, Saudi Arabia, 2004.
[12] P. Smith, D. Sinclair, R. Cipolla and K. Wood, “Effective
Corner Matching,” In Paul H. Lewis, Mark S. Nixon,
editors, Proc. 9th British Machine Vision Conference,
Vol. II, 1998, pp. 545-556.
[13] S. Smith and J. Brady, “SUSAN — a new approach to
low level image processing,” Int.J.Comput.Vis., Vol. 23,
1995, pp.,45 –78.
[14] C. Teh and R. Chin, “On the detection of dominant points
on digital curves”, IEEE Trans. PAMI, Vol. 8, 1990, pp.
859-873.
[15] A. Masood and M. Sarfraz, “A Novel Corner Detector
Approach using Sliding Rectangles,” The Proceedings of
The 4th ACS/IEEE International Conference on Comput-
er Systems and Applications (AICCSA-06), Sharjah, UAE,
2006, pp. 621 – 626, IEEE Computer Society Press.
[16] A. Masood and M. Sarfraz, “Corner Detection by Sliding
Rectangles along Planar Curves,” International Journal
of Computers & Graphics, Vol. 31, No. 3, 2007, pp. 440
– 448.
[17] I. Zoghlami, O. Faugeras and R. Deriche, “Using geome-
tric corners to build a 2D mosaic from a set of images,”
Proceedings of the computer vision pattern recognition,
1997, p. 420–25.
[18] F. Attneave, “Some informational aspects of visual per-
ception”, Psychological Review, Vo. 61, 1954, pp.
183–93.
[19] A. Rattarangsi and R. T. Chin, “Scale-based detection of
corners of planar curves,” Transactions on Pattern Anal-
ysis and Machine Intelligence, Vol. 14, 1992, pp. 430–4.
[20] M. Sarfraz, A. Rasheed and Z. Muzaffar, “A Novel Li-
near Time Corner Detection Algorithm, Computer
Graphics,” Imaging and Visualization – New Trends, Sar-
fraz, M., Wang, Y., and Banissi, E. (Eds.), ISBN:
3-7695-2392-7, IEEE Computer Society, USA, 2005, pp.
191-196.
[21] L. Dreschler and H. H. Nagel, “On the selection of critical
points and local curvature extrema of region boundaries
for inter-frame matching,” Proceedings of ICPR, 1982, pp.
542–44.
[22] A. J. Pritchard, S. J. Sangwine and R. E. N. Horne, “Cor-
ner and curve detection along a boundary using line seg-
ment triangles,” Electronics Division Colloquium on
Hough Transforms Digest, No. 1993/106, 1993, pp. 1–4.
[23] Z. N. K. Swati, S. Zaman, and M. Sarfraz, “A Novel
Corner Detector Approach using Sliding two Ellipses and
one Rectangle,” The Proceedings of International
Conference on Frontiers of Information Technology (FIT
2009), December 16-18, 2010, COMSATS Institute of
Information Technology, Pakistan, Article # 73, ISBN:
978-1-60558-642-7, ACM Press, 2010.
15