A Journal of Software Engineering and Applications, 2012, 5, 78-83
doi:10.4236/jsea.2012.512b016 Published Online December 2012 (http://www.scirp.org/journal/jsea)
Copyright © 2012 SciRes. JSEA
Intelligent Approache s f or Vectori zing Image Ou t lin es
Muhammad Sarfraz
Department of Infor mation Science, Kuwait University, Adailiya Campus, P.O. Box 5969, Safat 13060, Kuwait.
Email:p rof.m.sarfraz@gmai l.co m
Received Month Day, Year (2012).
Two computing approaches, based on linear and conic splines, are proposed here in reviewed and extended for vecto-
rizing image outlines. Both of the approaches have various phases including extracting outlines of images, detecting
corner points from the detected outlines, and curve fitting. Interpolation splines are the bases of the two approached.
Linear spline approach is straight forward as it does not have a degree of freedom.in terms of some shape controller in
its description. However, the idea of the soft computing approach, namely simulated annealing, has been utilized for
conic splines. This idea has been incorporated to optimize the shape parameters in the description of the generalized
conic spline. Both of the linear and conic approaches ultimately produce op timal results fo r the approxima te vecto riza-
tion of the digital contours obta i ned from the gene ric shapes.
Keywords:I ma ging; soft computing; vectorizatio n; corner points; curve fittin g
1. Introduction
Designing and modeling some appropriate curve scheme
[9-23] is one of the important phases of capturing and
vectorizing outlines of images. It plays a significant role
in various applications. The representation of planar
objects, in terms of curves, has many advantages. For
example, scaling, s hearing, translation, rota tion and clip-
ping operations can be performed without any difficulty.
Although a good amount of work has been done in the
area [8-20], it is still desired to proceed further to exp lore
more advanced and interactive strategies. Most of the
up-to-date research has tackled this kind of problem by
curve subdivis i on or curve segmentation.
The proposed work is a motivation of work on cubic
splines [28]. A conic approach was studied in its intial
form in [29]. It was then exte nded together with a linear
spline i n [ 30]. Thi s p ap er r evi ews a nd fur the r e xtends t he
work of [30]. It provides more detailed description and
comparative study of linear and conic models.This work
is a representation of two approaches using linear and
conic interpolations. The linear interpolant approach is
straight forward. However, the conic approach is inspired
by an optimization algorithm based on simulated an-
nealing (SA) by Kirkpatrick et.al [24]. It motivates the
author to an optimization technique proposed for the
outline capture of planar images. In this paper, the data
point set represents any generic shape whose outline is
required to be captured. We present an iterative process
to achieve our objective. The algorithm comprises of
various phases to achieve the target. First of all, it finds
the contour [25-27] of the gray scaled bitmap images.
Secondly, it uses the idea of corner points [1-7] to detect
corners. T hat is, it detects t he co rner points on t he digital
contour of the generic shape under consideration. These
phases are considered as preprocessing steps. Linear and
conic interpolants are then used to vectorize the outline.
The idea of simulated annealing (SA) is used to fit a
conic spline which passes through the corner points. It
globally optimizes the shape parameters in the descrip-
tion of the conic splines to provide a good approximation
to the digital curves. In case of poor approximation, the
insertions of intermediate points are made as long as the
desired approximation or fit is achieved.
The organization of the paper is as follows, Section 2
discusses about preprocessing steps which include find-
ing the boundary of planar objects and detection of cor-
ner points. Section 3 is about the interpolant forms of
linear and conic spline curves. Section 4 is dedicated for
simulated annealing. Overall methodology of curve fit-
ting is explained in Section 5, it includes the idea o f knot
insertion as well as the algorithm design for the proposed
vectorization schemes. Demonstration of the proposed
schemes as well as comparative study is presented in
Section 6. Finally, the paper is concluded in Section 7.
2. Pre-processing
Intelligent Approaches for Vectorizing Image Outlines
Copyright © 2012 SciRes. JSEA
The prop ose d sc hemes star t wi th fi ndin g t he bo undar y o f
the generic shape and then using the output to find the
corner points [1-7]. The image of the generic shapes can
be acquired either by scanning or by some other mean.
The aim of boundary detection is to produce an object’s
shape in graphical or non-scalar representation. Chain
codes [26], in t his paper, have been used for this purpose.
Demonstration of the method can be seen in Figure 1(b)
which is the contour of the bitmap image shown in
Figure 1(a).
Figure 1 . Pre-processing Steps: (a) Ori ginal Image, (b)
Outline of the image, (c) Corner points achie ved.
Corners, in digital i mages, give important cl ues for the
shape representation and analysis. These are the points
that partition the boundary into various segments. The
strategy of getting these points is based on the method
proposed in [1]. The demonstration of the algorithm is
made on Figure 1(b). The corner points of the image are
sho wn in Fi gure 1(c).
3. Curve Fitting and Spline
The motive of finding the corner points, in Section 2,
was to divide the contours into pieces. Each piece con-
tains the data points in between two subsequent corners
inclusive. This means that if there are m corner points cp1,
cp2, …, cpm then there will be m pieces pi1, pi2, …, pim.
We treat each piece separately and fit the spline to it. In
general, the ith piece contains all the data points between
cpi and cpi+1 inclusive.After breaking the contour of the
image into different pieces, we fit the spline curve to
each piece. To construct the parametric spline interpolant
on the interval
, we have
ni ,......,1,0=
, as interpolation data, at knots ti,
ni ,......,1,0=
3.1. Linear Spline
T he c ur v e fi tte d by a linear spline is a candid ate of b est fit,
but it may not be a desired fit. This leads to the need of
introducing some extra treatment in the methodology.
This section deals with a form of linear spline. It intro-
duces parameters t’s in the description of li near spline
defined as follows:
, iii tth −= +1.
Pi and Pi+1 are corner po ints of the ith piece.
3.2. Quadratic Spline
The curve fitted by a conic spline is a candidate of best fit,
but it may not be a desired fit. This leads to the need of
introducing some shape parameters in the description of
the conic spline. This section deals with a form of conic
spline. It introduces shape parameters u’s in the descrip-
tion of conic spline define d as foll ows:
tP ,
( )
ii u
PV+= ,
ii u
PW 1
Di and Di+1 are the corresponding tangents at corner
pointsPi and Pi+1 of theith piece. The tangent vectors are
calculated, as in [29], using arithmetic mean.
Obviously, the parameters ui's, when equal to 1, pro-
vide the special case of quadratic spline. Otherwise,
these parameters can be used to loose or tighten the
curve. This paper proposes an evolutionary technique,
namely simulated annealing (SA), to optimize these pa-
rameters so that the curve fitte d is optimal.
4. Simulated Annealing (SA)
Simulated annealing (SA) [24] is a global optimization
method based on the Monte Carlo method. It works on
the ana log y of the ener gy in an n -body system where the
material is cooled to lower temperatures gradually to
result in a perfect crystal structure. The perfect crystal
structure is attained by having minimum energy in the
material. T his analog y tra nslates to the optimization do ne
in simulated annealing in finding a solution that has the
lowest obj ective functio n val ue. The solution space is all
the possible sol utions. The curr ent solution is the presen t
state of the material. The algorithm iteratively tries to
change the state of the material and check whether it has
improved. The material’s state is changed slightly to find
a neighboring state i.e. a close solution value in the solu-
tion space. It is possible that all neighboring states of
current states are worse solutions. The algorithm allows
going to a worse state with a certain probability. This
probability decreases as the algorithm iteratio ns proceed.
Finally, it only allows a change in state if it is strictly
better tha n the current so lution. Details o f SA theor y can
be found in [24]. A detailed description of the mapping
of the SA technique on the proposed problem is given in
Intelligent Approaches for Vectorizing Image Outlines
Copyright © 2012 SciRes. JSEA
the next sectio n.
5. Proposed Approach for Vectorization
Theproposed approach to the curve problem is described
here in detail. It incl udes the p hase s of pr oble m matching
with SA using conic splines, description of parameters
used for SA, curve fitting, and the overall designs of al-
5.1. Problem Mapping
Thissection describes about the SA formulation of the
current problem in detail. Our interest is to optimize the
values of conic curve parameters u such that the defined
curve fits as close to the original contour segments as
possible. We use SA for the optimization of these para-
meters for the fitted curves. Hence the dimensionality of
the solution space is 1 for conic curves. Each state in the
SA solution space represents a value of u for conics.
We start with an initial state that is a given value of u
for conics. A starting temperature is also chosen arbitra-
rily. This temperature is an inherent internal parameter of
SA and has no significance or mapping on our problem.
The algorithm maintains a record of the best state ever
reached throughout the algorithm run. This is the value
of u for co nics t hat has g ive n the b es t c ur ve fit t in g so far .
This best solution gets updated whenever the algorithm
finds a better solution. The algorith m itera tively looks for
neighb or ing st at es t hat may or ma y not b e b ette r tha n the
current one. These neighboring states are val ues of u for
conics that are slightly different from the values of u for
conics. The cooling rate in SA is the factor affecting the
likeli hoo d o f sele cting neig hb ori ng value s of u for conics
that give a curve fitting worse than the values of u for
Note that we apply SA independently for each seg-
ment of a contour that we have identified using corner
points. SA is applied sequentially on each of the seg-
ments, generating an optimized fitted curve for each
segment. The algorithm is run until the maximum al-
lowed time is reached, or an optimal curve fitting is at-
5.2. Initialization
Once we have the bitmap image of a generic shape, the
boundary of the image can be extracted using the method
described in Section 2. After the boundary points of the
image are found, the next step is to detect corner points
as explained in Section 2. This corner detection tech-
nique assigns a measure of ‘corner strength’ to each of
the points on the boundar y of the image. This step helps
to divide the boundary of the image into n segments.
Each o f these se gment s is then ap proxi mate d by inter po-
lating spline described in Sections 3.2. The initial solu-
tion of spline parameters u values for conics are ran-
domly selected within the range [-1, 1].
5.3. Curve Fitt ing
After an initial approximation for the segment is ob-
tained, better approximations are obtained through SA to
reach the optimal solution. We experiment with our sys-
tem by approximating each segment of the boundary
using the conic splines of Section 3.2.
The conic spline method is a variation of the quadratic
spline. It provides greater control on the shape of the
curve and also e fficient to compute. The tangents, in the
description of the spline, are computed using the arith-
metic mean method described in Eqn. (3). Each boun-
dary segment is approximated by the spline. The shape
parameter u, in the conic spline, provides greater flex-
ibility over the shape of the curve. These parameters are
adjusted using SA to get the optimal fit.
Since, the objective of the paper is to come up with
optimal tec hniques which ca n provide d ecent curve fit to
the digital data . Therefore, the inter est would be to co m-
pute t he curve i n suc h a way that the su m square erro r of
the computed curve with the actual curve (digitized con-
tour) is minimized. Mathematically, the sum squared
distance is given by:
[ ]
[ ]
Pi,j = (xi,j, yi,j), j = 1,2,…,mi , (12)
are the data points of the ith segment on the digitized
contour. The parameterization over t's is in accordance
with the chord length parameterization. Thus the curve
fitted in this way will be a candidate of best fit.
Once an initia l fit for a p articular se gment is obtained,
the parameters of the fitted curve u’s for conics are ad-
justed to get b etter fit. Here, we try to minimize the sum
squared error of Eqn. (11). Using SA, we try to obtain
the optimal values of the curve parameters. We choose
this technique because it is powerful, yet simple to im-
plement and as shown in Section 6, performs well for our
For some segments, the best fit obtained through itera-
tive improvement may not be satisfactory. In that case,
we subdivide the segment into smaller segments at points
where the distance between the boundary and parametric
curve exceeds some predefined threshold. Such points
are termed as intermediate points. A new parametric
curve is fitted for each new seg ment.
Intelligent Approaches for Vectorizing Image Outlines
Copyright © 2012 SciRes. JSEA
We can summarize all the phases from digitization to
optimization discussed in the previous sections. The al-
gorithms of the proposed schemes are contained on var-
ious step s. The reader is referred to [29] for the details of
the Algorithms.
Figure 2. Results of linear scheme: (a) Fitted Outline of the
image, (b) Fitted Outline of the image with intermediate
points. Results of conic scheme: (c) Fitted Outline of the
image, (d) Fitted Outline of the image with intermediate
The above mentioned schemes and the algorithms
have been implemented and tested for various images.
Reasonably quite elegant results have been observed as
can b e seen in the following Section of demonstrations.
Figure 3. Pre-processing Steps: (a) Original Image, (b)
Outline of the image, (c) Corner points achieved, (d) Fitted
Outline of the image.
6. Demonstrations
The proposed curve scheme has been implemented suc-
cessfully in this section. We evaluate the performance of
the system by fitting parametric curves to different binary
Figure 2 shows the implementation results of the two
schemes for the image “Lillah” in Figure 1(a). Figures
2(a) and 2(b) are the results for the linear scheme, re-
spectively, without and with insertion of intermediate
points. Similarl y, Figure s 2 (c) and 2(d) are the r esults for
the conic scheme, respectively, without and with inser-
tion of intermediate points.
Figure 4. Results of curve fitting. Linear curve fitting: (a)
Fitted Outline of the image, (b) Fitted Outline of the image
with intermediate points. Conic curve fitting: (c) Fitted
Outline of the image, (d) Fitted Outline of the image with
interme diat e points .
Figure 5. Pre-processi ng steps f or curve fitti ng (a) Image of
a pla ne, (b) Extr acted o utline (c) Initi a l cor ner p o ints.
Figure 6. Results of l inear scheme: (a) Fitted Outline of the
image, (b) Fitted Outline of the image with intermediate
points. Results of conic scheme: (c) Fitted Outline of the
image, (d) Fitted Outline of the image with intermediate
Figures 3 and 4 show the implementation results of a
“Plane” image. Figures 3(a), 3(b), 3(c) are respectively
the original image of the Plane, its outline, outline to-
gether with the corner points detected. Figure 4 shows
the implementation results of the two algorithms for the
Intelligent Approaches for Vectorizing Image Outlines
Copyright © 2012 SciRes. JSEA
“Plane” image in Figure 3(a). Figures 4(a) and 4(b) are
the results for the linear scheme, respectively, without
and with insertion of intermediate points. Similarly, Fig-
ures 4(c) and 4(d) are the results for the conic scheme,
respectively, without and with insertion of intermediate
Figures 5 and 6 show the implementation results of a
“Fork” image. Figures 5(a), 5(b), 5(c) are respectively
the or igi nal i mage of t he For k, its outline, o utline toget h-
er with the corner points detected. Figure 6 shows the
implementation results of the two schemes for the “Fork
image in F ig ure 5 (a). Figures 6(a) and 6(b) are the results
for the linear scheme, respectively, without and with
insertion of intermediate points. Similarly, Figures 6(c)
and 6 (d) are the results for the conic scheme, respective-
l y, w i t hout and with insertion of inter mediate points.
Table 1. N ames and contour details of images.
# of Con-
# of Contour
# of
Lillah 2 [1522+161] 14
Plane 3 [1106+61+83] 31
Fork 1 [693] 10
Table 2. Comparison of number of initial corner points,
intermediate points and total time taken (in seconds) for
conic interpo lation approache s.
Image # of Intermediate
Points in Linear
Total Time Taken For Linea r
With Inter-
Lillah.bmp 29 2.827 3.734
Plane.bmp 24 7.735 8.39
Fork.bmp 9 0.2265 0.4029
One can see that the approximation is not satisfac-
tor y whe n i t i s a c hie ved over t he co r ner p o int s onl y. This
is specifically due to those segments which are bigger in
size and highly curvy in nature. Thus, some more treat-
ment i s requi red fo r such o utline s. Thi s is the reaso n that
the idea to insert some intermediate points is demon-
strated in the schemes. It provides excellent results. The
idea of how to insert intermediate p oints is not explained
here due to limitation of space. It will be explained in a
subsequent paper.
Table 3. Comparison of number of initial corner points,
intermediate points and total time taken (in seconds) for
conic inte rpolatio n approac hes.
# of Inter-
Points in
Conic In-
Total Time Taken For Conic
With Inter-
Lillah.bmp 14 19.485 48.438
Plane.bmp 31 20.953 49.356
Fork.bmp 45 32.350 221.885
Tables I, II and III summarize the experimental results
for different bitmap images. These results highlight var-
ious information including contour details of images,
corner points, intermediate points, total time taken for
linear interpolation, and total time taken for conic inter-
7. Conclusion and Future Work
Two optimization techniques are proposed for the outline
capture of planar images. First technique uses simply a
linear interpolant and a straight forward method based on
distribution of corner and intermediate points. Second
technique uses the simulated annealing to optimize a
conic spline to the digital outline of planar images. By
starting a search from certain good points (initially de-
tected corner points), an improved convergence result is
obtained. The overall technique has various phases in-
cluding extracting outlines of images, detecting corner
points from the detected outline, curve fitting, and addi-
tion of extra knot points if needed. The idea of simulated
annealing has been used to optimize the shape parame-
ters in the description of a conic spline introduced. The
two methods ultimately produce optimal results for the
approximate vectorization of the digital contours ob-
tained from the generic shapes. The schemes provide an
optimal fit with an efficient computation cost as far as
curve fitting is concerned. The proposed sc h eme s are
fully automatic and require no human intervention. The
author is also thinking to apply the proposed methodol-
ogy for another model curve. It might improve the ap-
proximation process. This work is in progress to be pub-
lished as a subsequent work.
8. Acknowledgements
This work was supported by Kuwait University, Re-
search Grant No. [WI 05/10].
Intelligent Approaches for Vectorizing Image Outlines
Copyright © 2012 SciRes. JSEA
[1] D. Chetrikov, S. Zsabo, “A Simple and Efficient Algo-
rithm for Detection of High Curvature Points in Planar
Curves”, Proceedings of the 23rd Workshop of the Aus-
tralian Pattern Recognition Group, 1999, pp. 1751-2184.
[1] A. A. Goshtasby, “Grouping and Parameterizing Irregu-
larly Spaced Points for Curve Fitting”, ACM Transac-
tions on Graphics, Vol. 19 , No. 3, 2000, pp. 185-203.
[2] P. Reche, C. Urdiales, A. Bandera,C. Trazegnies, F.
Sandoval, Corner Detection by Means of Contour Local
Vectors”, Electronic Letter s, Vol. 38, No. 14, 2002.
[3] M. Marji, P. Siv, “A New Algorithm for Dominant Points
Detection and Polygonization of Digital Curves”, Pattern
Recognition, 2003, p p. 22 39-2251.
[4] Wu -Chih Hu, Multiprimitive Segmentation Based on
Meaningful Breakpoints for Fitting Digital Planar Curves
with Line Segments and Conic Arcs, Image and Vision
Computing, 2005, pp. 783-789.
[5] H. Freeman, L. S. Davis, A corner finding algorithm for
chain-coded curves”, IEEE Trans. Computers, Vol. 26,
1977, pp . 297-303.
[6] N. Richard, T. Gilbert, “Extraction of Dominant Points
by estimation of the contour fluctuations, Pattern Rec-
ognition, Vol. 35, 2002, pp. 1447-1462.
[7] M. Sarfraz, “Representing Shapes by Fitting Data using
an Evolutionary Approach”, International Journal of
Computer-Aided Design & Applications, Vol. 1, No. 1-4,
2004, pp 179-186.
[8] M. Sarfraz, M. A. Khan,An Automatic Algorithm for
Approximating Boundary of Bitmap Characters”, Future
Generation Computer Systems, 2004, pp. 13 27-1336.
[9] M. Sarfraz, “Some Algorithms for Curve Design and
Automatic Outline Capturing of Images”, International
Journal of Image and Graphics, 2004, pp. 301-324.
[10] Z. J. Hou, G. W. Wei, “A New Approach to Edge Detec-
tion”, Pattern Recognition, 2002, pp. 1559-1570.
[11] M. Sarfraz, “Computer-Aided Reverse Engineering using
Simulated Evolution on NURBS”, International Journal
of Virtual & Physical Prototyping, Vol. 1, No. 4, 2006,
pp. 243 – 257.
[12] M. Sarfraz, M. Riyazuddin, M. H. Baig, “Capturing Pla-
nar Shapes by Approximating their Outlines, Internation-
al Journal of Computational and Applied Mathematics,
Vol. 189, No. 1-2, 2006, pp. 49 4 512.
[13] M. Sarfraz, A. Rasheed, “A Randomized Knot Insertion
Algorithm for Outline Capture of Planar Images using
Cubic Spline”, The Proceedings of The 22th ACM
Symposium on Applied Computing (ACM SAC-07), Seoul,
Korea, 2007 , p p. 71 75.
[14] H. Kano , H. Nakata, C. F . Martin, “Optimal Curve Fitting
and Smoothing using Normalized Uniform B-Splines: A
Tool for Studying Complex Systems”, Applied Mathe-
matics and Computation, 2005, pp. 96 -128.
[15] Z. Yang, J. Deng, F. Chen, Fitting Unorganized Point
Clouds with Active Implicit Spline Curves”, B- Visual
Computer, 2005, pp. 831-839.
[16] G. Lavoue, F. Dupont, A. Baskurt, A New Subdivision
Based Approach for Piecewise Smooth Approximation of
3D Polygonal Curves”, Pattern Recognition, Vol. 38,
2005, pp . 1139-1151.
[17] H. Yang, W. Wang, J. Sun, “Control Point Adjustment
for B-Spline Curve Approximation, Computer Aided
Design, Vol. 36, 2004, pp. 639-652.
[18] J. H. Horng, An Adaptive Smoothing Approach for Fit-
ting Digital Planar Curves with Line Segments and Cir-
cular Arcs ”, Pattern Recog ni tion Letters, Vol. 2 4, No. 1-3,
2003, pp . 565-577.
[19] B. Sarkar, L. K. Singh, D. Sarkar, Approximation of
Digital Curves with Line Segments and Circular Arcs us-
ing Genetic Algorithms”, Pattern Recognition Letters,
Vol. 24, 2003 , pp. 25 85-2595.
[20] X. Yang, “Curve Fitting and Fairing using Conic Spines”,
Computer Aided Design, Vol. 6, No. 5, 2004, pp.
[21] X. N. Yang, G. Z. Wang Planar Point Set Fairing and
Fitting by Arc Splines”, Computer Aided Design, 2001,
pp. 35-43.
[22] M. Sarfraz, “Designing Objects with a Spline”, Interna-
tional Journal of Computer Mathematics, Vo l. 85, No . 7,
[23] S. Kirkpatrick, C. D. Gelatt Jr., M. P. Vecchi, "Optimiza-
tion by Simulated Annealing", Science, Vol. 220, No
4598, 1983, pp. 671-680.
[24] R. C. Gonzalez, R. E. Woods, S. L. Eddins, “Digital Im-
age Processing Using MATLAB, 2nd Ed., 2009, Gates-
mark Publishing.
[25] M. S. Nixon, A.S. Aguado, “Feature extract ion and image
processing”, 2008, Elsevier.
[26] M. Sarfraz, “Outline Capture of Images by Multilevel
Coordinate Search on Cubic Splines”, Lecture Notes in
Artificial Intelligence, A. Nicholson and X. Li (Eds.):
LNAI 5866, Springer-Ver lag Berl in Heid elber g, 2009, pp.
[27] M. Sarfraz, “Vectorizing Outlines of Generic Shapes by
Cubic Spline using Simulated Annealing”, International
Journal of Computer Mathematics, Vol. 87, No. 8, 2010,
pp. 1736 – 1751.
[28] Sarfraz, M. (2011), Capturing Image Outlines using
Simulated Annealing Approach with Conic Splines,The
Proceedings of The International Conference on
Information and Intelligent Computing (ICIIC 2011),
Hong Kong, China, November 25-27, 2011, IPCSIT Vol.
18, pp. 152 – 157, IASCIT Press Singapore.
[29] M. Sarfraz, “Vectorizing Image Outlines using Spline
Computing Approach”, The Proceedings of The 4th In-
ternational Conference on Machine Learning and Com-
puting (ICMLC 2012), Hong Kong, China, 2012, ASME