TELKOM
NIKA Indonesia
n
Journal of
Electrical En
gineering
Vol. 14, No. 1, April 2015, pp. 173 ~ 1
8
4
DOI: 10.115
9
1
/telkomni
ka.
v
14i1.746
7
173
Re
cei
v
ed
Jan
uary 7, 2015;
Re
vised Ma
rch 13, 2015; A
c
cepted Ma
rch 28, 2015
An Effic
i
ent Converging Snake Algorithm for Locating
Object Bounda
ries
Atiqur Rahm
an*
1
, Rash
ed
Musta
f
a
2
Dep
a
rtment of Comp
uter Scie
nce
& Engi
ne
e
r
ing, Un
iversit
y
of Chittago
ng, Chittag
o
n
g
, Bangl
ades
h
*Co
rre
sp
ondi
ng autho
r,
email: atiqcs
e0
9
@
cu.ac.bd
1
, b
u
lb
ul.cse.cu@
gmail.c
o
m
2
A
b
st
r
a
ct
Active conto
u
r are now
esta
bli
s
hed
as a tech
niq
ue for extra
c
ting sal
i
e
n
t co
ntours fro
m
an
imag
e
.
A snak
e is
an
active co
ntour
for repr
ese
n
ting
obj
ect co
ntour
. T
r
adition
al s
n
ake a
l
g
o
rith
ms
are ofte
n us
ed
t
o
repres
ent the c
ontour
of
a s
i
n
g
le
obj
ect. A di
fferent conto
u
r
search
al
gorith
m
is
pres
ente
d
in this
pa
per t
h
a
t
provi
des a
n
ef
ficient co
nverg
ence to t
he o
b
ject
co
ntours
than b
o
th th
e
kass et al
an
d gre
edy s
nak
e
alg
o
rith
m (GSA).Our propos
ed al
gorith
m
p
r
ovid
es a st
rai
ghtforw
ard ap
proac
h for snake conto
u
r rapi
d
splittin
g
and c
onn
ectio
n
, w
h
ich usua
lly can
not be grac
efu
lly ha
ndl
e by traditi
ona
l snak
e
s
. T
h
is algorith
m
compar
es w
i
th other tw
o co
nventi
o
n
a
l a
p
p
r
oach
e
s is
fas
t
er accord
in
g to ne
ed
ed
exe
c
ution ti
me. T
h
i
s
pap
er te
lls
us
w
h
ich
on
e
is
better
by c
o
mp
arin
g
eac
h
other. T
h
e ex
peri
m
e
n
tal
res
u
lts of v
a
ri
ous
test
sequ
enc
e i
m
a
g
e
s w
i
th a sin
g
l
e
ob
ject sh
ow
n goo
d p
e
rfor
ma
nce, w
h
ich
pro
v
ed t
hat th
e pr
opos
ed
alg
o
rit
h
m
is faster amon
g those.
Ke
y
w
ords
:
act
i
ve conto
u
r, snake, para
m
etri
c curv
e, finite d
i
fferences, gre
edy al
gorith
m
Copy
right
©
2015 In
stitu
t
e o
f
Ad
van
ced
En
g
i
n
eerin
g and
Scien
ce. All
rig
h
t
s reser
ve
d
.
1. Introduc
tion
Snake
s
a
r
e
mainly use
d
to dynamically loca
te the
conto
u
r of a
n
obje
c
t. In orde
r to
answe
r the
q
uestio
n
what
is a
n
a
c
tive
conto
u
r
and
how do
es it
work and
wh
at se
pa
rate
s
the
different
activ
e
contou
r
me
thods from
e
a
ch
othe
r,
a
brief
revie
w
of the m
a
in
rese
arch
pa
p
e
rs
dealin
g with
active co
ntou
rs
will be giv
en, follo
we
d
by a detailed
analysi
s
of the theo
ry be
hind
the Kass
et a
l
[20], sn
ake
and th
e g
r
ee
dy sn
ake alg
o
rithm [1
4]. The rea
s
on
for ch
oo
sing th
e
s
e
two alg
o
rith
ms for a
clo
s
er compa
r
i
s
on is that th
e Kass et
al
pape
r
wa
s the first pap
e
r
to
sug
g
e
s
t energy minimizin
g
sna
k
e
s
for i
m
age segm
e
n
tation. The
gree
dy sna
k
e
algorithm o
n
th
e
other ha
nd is interestin
g to examine si
nce it
deal
s with discrete
values wh
e
n
minimizin
g
th
e
sna
k
e’
s en
ergy. Most of the rem
a
inin
g
sna
k
e al
gori
t
hms a
r
e al
so more
or le
ss va
riation
s
of
these t
w
o al
gorithm
s. To
answe
r the
que
stion
ho
w would a
n
active conto
u
r alg
o
rithm
be
impleme
n
ted
in MATLAB, both the Kass et al.
sna
k
e
and the gree
dy sna
k
e will
be implem
ent
ed
in MATLAB.
By runni
ng
a
num
ber of
e
x
perime
n
ts,
with the
two i
m
pleme
n
ted
sna
k
e
s
, b
o
th
on
synthetic
and
real im
age
s the qu
estio
n
s
unde
r whic
h
con
d
ition
s
do
es a
n
a
c
tive conto
u
r p
e
rfo
r
m
satisfa
c
to
ry, unde
r whi
c
h
conditio
n
s
doe
s an acti
ve contou
r p
e
rform u
n
satisfacto
ry will be
sou
ght answered. Fin
a
lly the stren
g
ths and wea
k
n
e
s
ses of ea
ch
of the three snake algo
rith
ms
will be di
scu
s
sed. In the p
r
ocess of
writ
ing th
is
repo
rt and implem
enting the al
gorithm
s I al
so
hope
to a
c
q
u
ire
a
deep
e
r
u
nde
rsta
ndi
ng of
active
conto
u
rs,
sin
c
e thi
s
i
s
an
area
of mu
ch
intere
st to our. It should al
so be noted th
at to limit
the
scope of this
thesi
s
we
sha
ll only deal wi
th
para
m
etri
c active contours
and not
Ge
od
esi
c
active co
ntours.
The re
st
of
t
h
is pap
er will
be org
ani
ze
d
a
c
co
rdi
ng t
o
the foll
owin
g structu
r
e:
section
2
literature review; impl
ementation framework
will
be il
lustrated in section 3; sect
ion 4
elucidat
es
results; sectio
n 5 discu
ssi
o
n
and sectio
n
6 con
c
lud
e
s
this pap
er.
2.
Litera
ture R
e
v
i
e
w
This
sectio
n will start with
a gene
ral
int
r
odu
ct
ion
of what an activ
e
contou
r
i
s
use
d
fo
r
and ho
w it works. He
rea
fter a brief literatu
r
e
revie
w
is present
ed whi
c
h hig
h
lights the m
a
in
differenc
es
for s
o
me of the mos
t
wi
d
e
ly known active contour m
e
tho
d
s.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 14, No. 1, April 2015 : 173 – 18
4
174
Active contou
rs are u
s
e
d
i
n
the
domai
n
of
ima
ge
pro
c
e
ssi
ng to
lo
cate the
co
nto
u
r
of an
obje
c
t [20]. T
r
ying to
lo
cat
e
an
obj
ect
contour pu
rely
by runnin
g
a
low level im
age
pro
c
e
s
si
ng
task
su
ch as Canny edg
e
detection is
not particu
larly successful
[17]. Often the edge i
s
not
contin
uou
s, i.
e. there mig
h
t be
hole
s
along
t
he
ed
ge, an
d
spu
r
ious ed
ge
s
can b
e
p
r
e
s
e
n
t
becau
se
of n
o
ise. A
c
tive
contours try to
improve
o
n
t
h
is
by imp
o
si
ng d
e
si
rabl
e
prop
ertie
s
su
ch
as
co
ntinuity and
smo
o
thn
e
ss to the
co
ntour
of
the
obje
ct. This
mean
s that t
h
e a
c
tive con
t
our
approa
ch ad
ds a certai
n degree of
pri
o
r kno
w
le
dge
for d
ealin
g
with the
probl
e
m of findi
ng
the
obje
c
t conto
u
r
.
An active co
ntour i
s
mod
e
led a
s
pa
ra
metric
cu
rve; this cu
rve a
i
ms to minim
i
ze its
internal e
nergy by movin
g
into a loca
l minimu
m. The positio
n
o
f
the snake i
s
given by the
para
m
etri
c curve, in pra
c
tice the
cu
rve is
often
closed whi
c
h me
an
s that v(0)
= v(1).
Furthe
rmo
r
e t
he cu
rve is a
s
sumed to be
param
eteri
z
e
d
by arc len
g
th [15].
A close
d
parametri
c sna
k
e curve i
s
illustrated
in Fig
u
re 1. Each p
o
int along the
curve i
s
unde
r the
infl
uen
ce of
bot
h internal
an
d extern
al
fo
rce
s
, a
n
d th
e
sn
ake conti
n
uou
s
ly trie
s to
positio
n itself so that the co
mbined e
n
e
r
g
y
of these force
s
is minimi
zed.
Figure 1. Illustration of a pa
rametri
c
sna
k
e curv
e v(s). The blue d
o
t marks the
sta
r
ting point an
d
end poi
nt of the sn
ake cu
rve. Ideally th
e sna
k
e
will h
a
ve minimize
d its energy whe
n
it has
positio
ned itself on the con
t
our of the obj
ect
2.1. Analy
s
is of the
Kas
s
et al. & Gre
e
d
y
snake [20]
In the previou
s
se
ction a sh
ort introdu
ctio
n to
what an active conto
u
r
is and ho
w it works
wa
s pre
s
e
n
te
d, followed u
p
by a review of some of
the best kn
ow pa
ramet
r
i
c
active co
ntour
model
s. In thi
s
chapte
r
we
will continu
e
with a
m
o
re
thoro
ugh
anal
ysis of th
e Ka
ss
et al. an
d the
gree
dy sn
ake algo
rithm.
Thereafter p
o
ssible
ex
ten
s
ion
s
a
nd im
provem
ents t
o
the two
sn
ake
algorith
m
s wi
ll be examined. However,
let us first take a loo
k
a
t
the parame
t
ric cu
rve an
d
examine why it is used a
s
the ba
sis for t
he sn
ake mo
del.
The mo
st basic way of rep
r
ese
n
ting a cu
rve
in two di
mensi
o
n
s
is the explicit form:
y
=
f
(
x
)
(
1
)
N
e
ar
ly a
ll s
i
mp
le
cu
r
v
es c
a
n
be
r
epr
e
s
e
n
t
ed
usi
n
g the expli
c
it form, but
for more
c
o
mplex c
u
r
v
es
w
i
th tw
o
or
mor
e
y-
values
for
a
singl
e co
rrespon
d
i
ng x-value t
he expli
c
it form
fails [20]. Mo
reove
r
the ex
plicit form
ha
s p
r
obl
e
m
s
with modelin
g
curve
s
parall
e
l to the y-ax
is,
sin
c
e th
e
slo
pe fo
r
su
ch
a
cu
rve te
nd
s
towards infini
ty [20]. These sho
r
tcomi
n
gs
exclu
d
e
s
t
he
use of the
explicit form
for curve
s
su
ch
a
s
ci
rcles, ellip
se
s and othe
r coni
cs. The
two
dimen
s
ion
a
l i
m
plicit curve
equation
ca
n be u
s
ed t
o
rep
r
e
s
ent
any cu
rve, thus
avoiding
the
limitations of the explicit curv
e. Unfo
rtu
nately the inhere
n
t form
of the implicit curve eq
uati
on
doe
s not allo
w us to com
p
ute points on
the curve
directly, often requirin
g
the so
lution of a non-
linear eq
uatio
n for ea
ch
po
int. Furthe
rm
ore
both
the
explicit a
nd i
m
plicit fo
rm
requires that t
h
e
unde
rlying fu
nction
is kno
w
n, a
nd i
n
p
r
actice
whe
n
dealin
g
with
complex d
e
forming
cu
rves
su
ch
as
sna
k
e
s
thi
s
is not the
case. T
h
is l
e
a
d
s u
s
to
co
nsi
der th
e pa
ra
metric fo
rm
of a curve
whi
c
h, in
vector form, is sp
ecifie
d as:
f(x
,
y)=
0
(2)
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
An Efficient Convergi
ng Sn
ake Algo
rithm
for
Locating Obje
ct Bound
arie
s (Atiqu
r Rahm
an
)
175
The pa
ram
e
tric
cu
rve onl
y has o
ne in
depe
ndent p
a
ram
e
ter
s which i
s
vari
e
d
over
a
certai
n inte
rval, usu
a
lly [0; 1]. By using
the
pa
ram
e
tric
rep
r
e
s
e
n
tation we avoi
d the p
r
obl
e
m
s
that both
the
explicit a
nd i
m
plic
it fo
rm
s
have. Fo
r i
n
stance
we
ca
n
have
multipl
e
y-valu
es fo
r a
singl
e x-value
,
this is easy to see
in the parametric
form of a unit
circle with
cente
r
at origin.
Finally u
s
ing
the
paramet
ric re
pr
esent
ation
al
so
en
able
s
the
curve
to be ind
e
pen
dent of the
particula
r co
o
r
dinate
syste
m
used [18].
3. Implemen
tation Fr
ame
w
o
r
k
This
section
will contain a br
ief introduction to how
the implem
ented snakes
are
run,
together
with an explan
atio
n of so
me of the implem
ent
a
tion detail
s
.
The two
sna
k
e al
go
rithms have b
een
develop
ed a
nd te
sted u
s
i
ng MATLAB
R20
1
0
a
runni
ng on
wi
ndo
ws 7 version Hom
e
pre
m
ium. The progra
m is ru
n from the MATLAB comma
n
d
line and ta
ke
s 3 co
mman
d
line argu
men
t
s. All 3 input
argu
ment
s are string
s. The
first argu
me
nt
can
either b
e
Kass o
r
g
r
eedy
sp
ecif
ying wh
ether
to run th
e
Kass et al.
or g
r
ee
dy sn
ake
algorith
m
. The next argu
ment can b
e
either user
or ci
rcl
e
, this decide
s
wh
ether the sn
ake
sho
u
ld be
m
anually inp
u
t by the use
r
o
r
input a
s
a
circle. T
he la
st argu
ment sp
ecifie
s wh
eth
e
r
s
c
ale s
p
ace c
ontinuation
s
h
ould be on or off. So
f
o
r ins
t
ance if the us
er wis
h
es
to run the
gree
dy sna
k
e, input the
sna
k
e
contro
l point
s
ma
n
ually and
ha
ve scale
sp
a
c
e
co
ntinuati
o
n
turned o
n
he
sho
u
ld input t
he com
m
an
d line of the MATLAB con
s
ol
e belo
w:
main('
greedy'
,
'user', 'off')
The file main
.m runs the
snake pro
g
ra
m, it
also co
ntains n
early
all of the paramete
rs
and th
re
shol
ds u
s
e
d
. So i
f
the input im
age
sho
u
ld
b
e
ch
ang
ed
or the pa
ram
e
ter
β
adju
s
te
d it
can
be
don
e
by editing thi
s
file. If the
u
s
er ha
s
ch
osen to i
n
put th
e sna
k
e m
a
n
u
ally the im
a
ge
will be
sho
w
n
and the u
s
e
r
then cli
c
ks i
n
the po
si
tion
of the image
whe
r
e a
sna
k
e
control poi
nt
sho
u
ld b
e
in
serted. O
n
ce finish
ed the
u
s
er s
houl
d cli
ck
so
me
whe
r
e outsi
d
e the
image to
sta
r
t
the sna
k
e al
g
o
rithm.
The sna
k
e p
r
ogra
m
is
dep
ende
nt on th
e Image Processing T
oolb
o
x for MATL
AB being
installe
d, as functio
n
s fro
m
the toolbox are
u
s
ed fo
r doing
convol
ution. For ap
proximatin
g the
dire
ctional g
r
adient
s G
x
and G
y
of the image fun
c
tion I(x; y), we us
e
convolutio
n with Sobel filters.
The gradie
n
t magnitud
e
used in the ima
ge ene
rgy terms is the
n
co
mputed a
s
:
∥
I (x,
y
)
∥
=
√
G
x
2
+G
y
2
(3)
In the Kass e
t
al. snake im
plementatio
n the va
lue h u
s
ed in the fini
te differen
c
es is set
to h = 1. This
spe
e
d
s
up th
e comp
utatio
n and in
pract
i
ce the sna
k
e
still evolves satisfa
c
to
ry.
Below i
n
Fig
u
re
2 a
data-flow dia
g
ram
is
sho
w
. Thi
s
dia
g
ram gi
ves an
overvi
ew of
all
the MATLAB files and h
o
w
the function
s
invoke e
a
ch other.
The main fu
nction in mai
n
.m contain
s
mo
st of the param
eters and thre
sh
ol
ds u
s
ed,
furthermore it
also h
andl
es drawin
g th
e
sna
k
e
ev
oluti
on in
the i
m
a
g
e. Th
e Ka
ss Sna
k
e fu
ncti
on
cal
c
ulate
s
h
o
w
the
sn
ake
moves, give
n
the init
ial p
o
s
ition a
nd th
e
image
ene
r
g
y
, based
on
the
Kass et al.
sn
ake
mod
e
l. In the G
r
eedy
Snake
fun
c
tio
n
the evol
utio
n os the
sna
k
e is
cal
c
ul
ate
d
on the b
a
si
s of the gree
dy sna
k
e
al
gorithm. T
h
e getAvgDis
t
func
tion
returns
the
average
distan
ce
bet
wee
n
all the
sna
k
e
cont
rol points i
n
the sna
k
e. Th
e getMod
u
lo
function i
s
u
s
ed
extensively by the Greedy Snake f
uncti
on. This is b
e
ca
use we want to make sure that wh
en a
loop i
s
a
pplie
d to iterate th
roug
h all
the
sna
k
e
control
point
s the fi
rst an
d la
st p
o
int will
be th
e
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 14, No. 1, April 2015 : 173 – 18
4
176
same. Fin
a
lly the sna
k
e
Resam
p
le fun
c
tion tries to resam
p
le the
sna
k
e
cont
rol
points
so th
at
they are equ
a
lly spaced
alo
ng the sn
ake curve.
Figure 2. Illustration of the data-flo
w
bet
wee
n
the vari
ous fun
c
tion
s in the implementation
Determinatio
n of interse
c
ti
on se
gment
s equatio
n is:
value=(b
1
·
b
2
≤
0 && b
3
·
b
4
<0)
ǁ
(b
1
·
b
2
<0 &
&
b
1
·
b
2
≤
0
)
(
4
)
Splitting and con
n
e
c
ting contours eq
uat
ion is:
value=(
Ā
i
·
Ā
k
)
˂
(
Ā
i
·
Ā
k-1
)
(
5
)
3.1. Our Proposed
Algorithm of th
e
Boundary
Detection o
f
a O
b
jects
The algo
rithm
of the bound
ary detectio
n
of a object is
sho
w
n a
s
foll
ows:
Step 1
: Converge
nce process: ca
l
c
ulate
the energy f
unctio
n
s a
nd
minimize the energy
terms of sn
a
k
e poi
nts. If the iteration reac
he
s the final step, sto
p
.
Otherwi
se, go to step
2.
Step 2
: Th
e p
r
ocess
of det
ermini
ng i
n
terse
c
tion:
if the
sn
ake p
o
int i
n
tersect
s
seg
m
ent
s
i
estimated by
the equatio
n (3.2), then go
to step 3. Otherwi
se, go to
step 1.
Step 3
: The
splitting an
d con
n
e
c
ting
pro
c
e
ss: sp
lit the conto
u
r by rem
o
ving the
unne
ce
ssary Point
v
k
.
Snake point
s, wh
ich belo
ng to
t
he same si
de, are conn
ected by
equatio
n(3.3
)
and then, go
to step 4.
Step 4
: Reo
r
gani
zing
the seq
uen
ce
of the
sn
a
k
e
po
int process:
a ne
w seque
nce
i
s
formed fo
r each
conto
u
r. Go to step 1.
4. Results
Both the gre
edy sna
k
e, th
e Kass et al. sna
k
e & ou
r
approa
ch, th
at were analy
z
ed a
nd
descri
bed in
cha
p
ter 3, ha
ve been impl
emented in
MATLAB. In this chapte
r
we will test these
three
sn
akes
on different types of ima
g
e
s
. Some
of
th
e imag
es will
be
synthetic
while
othe
rs
will
be real ima
g
e
s
captu
r
e
d
by a digital
camera.
All the syntheti
c
i
m
age
s h
a
ve
been
mad
e
u
s
ing
Photosh
op 1
0
.0.
4.1. Test nu
mber 1; Bou
ndar
y
concav
it
y
Figure 3. Illustrating an obj
ect with a bo
unda
ry con
c
a
v
ity
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
An Efficient Convergi
ng Sn
ake Algo
rithm
for
Locating Obje
ct Bound
arie
s (Atiqu
r Rahm
an
)
177
The initial sn
ake forms a
circle a
r
o
und t
he obje
c
t and
con
s
ist
s
of 50 sna
k
e p
o
int
s
.
The imag
e we will u
s
e in t
he first te
st is
a synthetic i
m
age d
e
si
gn
ed to sh
ow o
ne of the
wea
k
n
e
sse
s
that the Kasset al. sna
k
e, greedy
sn
ake an
d ma
ny other sna
k
e
s
have. The
probl
em
app
e
a
rs
whe
n
tryi
ng to
lo
cate t
he
conto
u
r of
an o
b
je
ct whi
c
h
ha
s
a b
o
u
ndary
con
c
av
ity.
In Figure 3
we se
e the i
n
itial sn
ake a
n
d
the obj
ec
t of
whic
h
we
wis
h
to find the c
ontour. The
obje
c
t ha
s
a
large
con
c
avi
t
y and a
s
we
will
se
e th
e
either the Ka
sset al
.sna
ke
or the
greed
y
sna
k
e i
s
abl
e
to move com
p
letely into this con
c
avity.
The initial
sn
ake i
n
Figu
re
3 ha
s 50
cont
rol
points and both the two snakes will
start
evolving from this position.
Figure 4. Finals state of th
e Kass
et al.Esna
k
e. Iterati
ons 8
000,
α
= 0:035,
β
= 0:0
005,
δ
=
3, scale
spa
c
e
contin
uation off and
resa
mplin
g o
n
In Figure 4 we see th
e re
sult for the Ka
ss
et al. sna
k
e. The sna
k
e
param
eters
were
α
=
0:035,
β
= 0:
0005,
α
= 3 a
nd scal
e
spa
c
e
contin
uati
on was off while resampli
ng was on. T
he
sna
k
e
ran
8
000 iteration
s
which i
s
th
e maximum
numbe
r of iteration
s
. Th
e
rea
s
on th
at the
sna
k
e
did n
o
t stop
soo
n
e
r
i
s
that ne
w
po
ints k
eep
bei
ng in
serte
d
in
the ho
rizonta
l
stret
c
h a
bov
e
the cavity. These
ne
w poin
t
s slo
w
ly mov
e
out to
the sides
as th
ey are in
se
rted
and the
sna
k
e
never
co
nverges a
c
cordi
n
g to o
u
r
stop
p
i
ng
crite
r
i
on,
see
sectio
n 3
.
3.2. From
Fi
gure
3
we
cl
e
a
rly
see th
at the
snake is
not a
b
le to move i
n
to t
he cavity. This b
ehavi
o
r i
s
cau
s
ed
by a co
mbin
a
t
ion
of the
sna
k
e
s
inte
rnal
en
ergie
s
and
th
e imag
e e
nergy. The el
ast
i
city ene
rgy t
r
ies to
kee
p
t
he
sna
k
e
from
stretchin
g
and
if the
sn
ake
is to
move
down into
th
e cavity the
elasti
city ene
rgy
woul
d have t
o
be in
crea
sed. Ho
weve
r if t
he image
energy wa
s some
ho
w p
u
lling the
sn
ake
downward
s
i
n
to the cavity the ela
s
ticity e
nergy
co
uld b
e
overcom
e
,
but that is not
the case. Th
e
image en
ergy of 4.1 is only pulling
the snake out to the side
s of
the
cavity and not down
w
a
r
d
s
in
any way. In Figure 5.3 th
e final
state
of the g
r
ee
dy sn
ake is sho
w
n. Fo
r th
e g
r
eedy
sn
ake
the
final state wa
s rea
c
h
ed after 55 iteratio
ns. The p
a
ra
meters we
re
α
= 1,
β
= 1,
ɤ
= 1:2,
δ
= 3,
neigh
borhoo
d
si
ze wa
s 3
ˣ
3and
scal
e space continuation was
off. The red
snake
control
poi
nts
indicate poi
nts for which the
β
valu
e h
a
s
been
rela
xed by the
a
l
gorithm,
so
a corn
er
co
u
l
d
develop. Fi
gu
re 5
cl
early
shows th
at also the g
r
e
edy
sna
k
e
also h
a
s
pro
b
lem
s
with movin
g
i
n
to
the cavity. Actually it does slight
ly wo
rse
than the Kass et. al. sn
a
k
e, since the
Kasset al. sn
ake
protrude
s so
mewh
at deep
er into the ca
vity.
If we wish to corre
c
tly seg
m
ent an obje
c
t wi
th boun
d
a
ry con
c
aviti
e
s u
s
ing a snake we
must ma
ke
sure that the i
n
itial sna
k
e i
s
placed in
sid
e
the co
ncavity. This way the sna
k
e will
be
cau
ght by the image ene
rg
y and stick to the conto
u
r.
The gradie
n
t vector flow
sna
k
e
whi
c
h
was
briefly
descri
bed i
n
the literature
review
se
ction
sho
u
ld, by itself, be able to m
o
ve into bou
nda
ry con
c
avitie
s, but this sna
k
e h
a
s
not be
en
impleme
n
ted
and will the
r
e
f
ore not be te
sted.
Figure 5. Final state of the greedy sna
k
e. Iterations 5
5
,
α
= 1,
β
= 1,
ɤ
= 1:2,
δ
= 3, neighb
orh
o
od
siz
e
3
ˣ
3 and
scal
e
sp
ace contin
uation
off
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 14, No. 1, April 2015 : 173 – 18
4
178
4.2. Test nu
mber 2; Nois
y
Image
This te
st is d
e
sig
ned to ex
amine the
pe
rfor
ma
nce of
the two
sna
k
es o
n
noi
sy image
s,
both with
an
d
with
out
u
s
i
ng scale spa
c
e co
nti
nuati
on. The
ima
ge
see
n
in
F
i
gure
6
sh
ows a
black
squ
a
re
on a
white b
a
ckgroun
d. A high d
egree
of Gau
ssi
an
noise ha
s b
e
en ad
ded to t
he
image. Th
e
noise was a
dde
d
in MATL
AB with the comma
nd noi
syImg =
imnoise(im
g
,'
gau
ssi
an',0.5,
2); wh
ere 0.5
is the me
an
and 2 i
s
the
varian
ce of th
e Gau
s
sian.
As
in the last te
st the initial sn
ake
cu
rve co
nsi
s
ts
of 50
control p
o
ints
placed in a
ci
rcle
aro
und t
h
e
obje
c
t we wit
h
to find the contour of.
Figure 6. Image of a black
squ
a
re o
n
a white
ba
ckground
with a h
i
gh deg
ree of
noise. Initial
sna
k
e
con
s
i
s
ts of 50 sn
ake
control p
o
int
s
In the first two test ru
ns
we will ru
n the
sn
a
k
e
s
with scale spa
c
e continuatio
n
turned off.
Whe
n
scale
space co
ntinu
a
tion is turne
d
off we
only blur the ima
g
e
once with a
Gaussia
n
of
ᵟ
=
3 and th
en le
t the sna
k
e
run its
cou
r
se
on the bl
ur
re
d image. Fi
g
u
re 7
sh
ows
the final state
of
the Kass et. al. sna
k
e. We use
d
the param
eters
α
= 0:05,
β
= 0:0005,
α
= 3 an
d had re
sam
p
ling
on. Unfortu
n
a
tely the sna
k
e wa
s not a
b
le to
converge acco
rdin
g
to our stoppi
ng crite
r
ion a
n
d
ran
all 80
00 i
t
eration
s
. Even thou
gh th
e sn
ake run
s
8000
iteratio
ns it a
c
tually
moves ve
ry li
ttle,
sin
c
e it quickl
y
gets stuck o
n
the artifact
s
that the noise cre
a
tes in t
he image e
n
e
r
gy.
Figure 7. Final state of the Kasset al. sn
ake.
Iterations
8000,
α
= 0:05,
β
= 0:0005,
ɤ
= 3,
scale spa
c
e continuatio
n off and re
sampl
i
ng
on
Figure 8. Final state of the greedy sna
k
e.
Iterations
5,
α
= 1,
β
= 1,
ɤ
= 1:2,
δ
= 3,
neigh
borhoo
d
size 5
ˣ
5 an
d scale spa
c
e
contin
uation off
Figure 8
sho
w
s th
e final
state of the g
r
eedy
sna
k
e o
n
the
same i
m
age. Fo
r th
e greedy
sna
k
e the pa
ramete
rs
we
re set at
α
= 1,
β
= 1,
ɤ
= 1:2,
δ
= 3 an
d a neighb
orhood of si
ze
5
ˣ
5.
Again we ob
serve th
at the sna
k
e
qui
ckly gets
st
uck be
cau
s
e
of the noise. Actually the greedy
sna
k
e
stop
s
after only 5 iteration
s
in thi
s
exampl
e.
From these re
sults it is
cle
a
r that the amo
unt
of noise a
dde
d pre
s
ent
s a signifi
cant ch
alleng
e to both of the sna
k
e algorith
m
s.
For th
e next t
w
o te
st run
s
we
will tu
rn
scal
e
space
continuatio
n o
n
. This shoul
d help
in
makin
g
th
e
sna
k
e
s
more
ro
bu
st in
th
e p
r
e
s
en
ce
of noi
se. T
h
e impl
ement
ed
scale
sp
ace
contin
uation
use
s
4 different
scal
es.
Starting at
a
ro
ugh scale
wit
h
δ
= 15
an
d
then
re
du
cin
g
δ
by
4 until we rea
c
h
a scale
of
δ
= 3. At
each in
dividu
al scal
e th
e
snake i
s
allowed to
ru
n
unti
l
it
conve
r
ge
s o
r
until 1/4 of the
total iterations have run.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
An Efficient Convergi
ng Sn
ake Algo
rithm
for
Locating Obje
ct Bound
arie
s (Atiqu
r Rahm
an
)
179
In Figu
re
9 th
e final
re
sults of the Ka
sse
t
al. sn
ake, with scale
spa
c
e continu
a
tio
n
on, i
s
sho
w
n. It too
k
4
300
iterati
ons for th
e
snake to
co
nverge
to thi
s
result, a
nd th
e
paramete
r
s
were
α
= 0:
0
5
,
β
= 0:0005, scal
e
spa
c
e continuation on a
nd re
sam
p
lin
g on. It is quite evident from
looki
ng at Figure 9 that scale sp
a
c
e
co
ntinuation hel
ps ma
ke the
Kasset al. snake mo
re ro
b
u
st.
We can no
w
actually see that the sna
k
e
has foun
d the conto
u
r of the sq
uare.
The
co
rre
sp
o
nding
re
sult f
o
r the
greedy
sn
ake is sho
w
n in
Fig
u
re
10. The
pa
ra
meters
wer
e
α
=
1,
β
= 1,
ɤ
= 1:
2
,
δ
= 3, nei
g
hborhoo
d si
ze 5
ˣ
5
andth
e
numbe
r of it
eration
s
wa
s
76
.
Again we
se
e
that scale
space contin
u
a
tion
h
e
lp
s
si
gnifica
ntly, which
was to
b
e
expe
cted
al
so
for the gre
e
d
y
snake.
The two sna
k
es both find t
he co
ntour q
u
ite well con
s
iderin
g the a
m
ount of noise in the
image. Ho
we
ver it seem
s
the Kasset al
. snake pe
rfo
r
ms
slightly b
e
tter than the
greedy
sna
k
e
.
The greedy snake doe
s no
t find the lower le
ft corner
of the squa
re
in Figure 10.
Figure 9. Final state of the Kasset al. sn
ake
with scale
sp
ace
contin
uat
ion on. Iterations
4300,
α
= 0:
0
5
,
β
= 0:0005
and re
sa
mpli
ng on
Figure 10. Final state of the gree
dy sna
k
e with
scale spa
c
e continuatio
n o
n
. Iterations 7
6
,
α
=
1,
β
= 1,
ɤ
= 1:2 and nei
gh
borh
ood
size 5
ˣ
5
4.3. Test nu
mber 3; Image of a Lea
f
Now that we
have tested the snakes on two
synthetic images we
w
ill try to apply them
to a real image. The imag
e is cut out of a la
rger im
age sh
owi
ng
a numbe
r of leafs lying on
a
table.
The initial sn
ake h
a
s be
e
n
initialized
manually for
this test. This was do
ne to
illustrate
how a m
anu
ally initialized
sna
k
e
shoul
d be pla
c
ed,
but also b
e
cause pla
c
ing
the sna
k
e in
a
circle
aro
und
the leaf g
a
ve bad
re
sult
s. In Fi
gure 1
1
the ma
nual
ly place
d
initi
a
l sn
ake
can
be
see
n
. There is 78 sna
k
e control poi
nts i
n
the initial sn
ake.
In Figure 12
we see the final re
sult for t
he Kasset al. snake. The para
m
eters were
α
=
0:035,
β
=
0:
0005, re
sam
p
ling on and
scale sp
acecont
inuatio
n o
n
. The
sna
k
e
co
nverg
ed
a
fter
6161 ite
r
atio
ns.
We
see
that the
sna
k
e ha
s fou
nd t
he ge
ne
ral
shape
of the l
eaf contou
r q
u
ite
well. The
r
e is howeve
r
so
me pro
b
lem
s
with the upp
er right corne
r
and lo
wer l
e
ft corne
r
of the
leaf. This ca
n be attribut
ed to the fact the the im
age is q
u
ite bl
urry in thi
s
p
a
rt so the
exact
transitio
n bet
wee
n
the tabl
e and the leaf
is hard to ma
ke out.
Figure 11. Image sho
w
ing
a leaf laying on a
table. Initial snake co
nsi
s
ts of 78 sna
k
e
control
points
Figure 12. Final state of
the Kasset al. snake.
Iterations
6161,
α
= 0:035,
β
= 0:0005,
resampli
ng o
n
and scal
e space co
ntinu
a
tion
on
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 14, No. 1, April 2015 : 173 – 18
4
180
The final
po
si
tion of the
g
r
eedy
sna
k
e
i
s
sho
w
n
in
Figure
13.
The
para
m
eters
were
α
=
1,
β
=
1,
ɤ
= 1:2,
neigh
bo
rhood si
ze
5
ˣ
5 and
scale
space continu
a
tion on.
Whi
l
e the n
u
mbe
r
of
iteration
s
ru
n
s
we
re 12
8.
Figure 13. Final state of
the gree
dy sna
k
e.
Iterations
128,
α
= 1,
β
= 1,
ɤ
= 1:2,
neigh
borhoo
d
size 5
ˣ
5 and
scal
e
sp
ace
contin
uation on
Figure 14. Final state of our app
ro
ach
The g
r
eedy
snake also se
ems to
captu
r
e the
gen
eral
conto
u
r of th
e leaf. Ho
wev
e
r the
r
e
is a few
more errors ma
d
e
, comp
ared
to the Kass
e
t. al. snake. As with the K
a
ss et. al. sn
ake
the gre
edy
snake al
so h
a
s
p
r
oble
m
s
with the upp
er
right
corner a
nd the lo
we
r l
e
ft corner
of the
leaf. Furthe
rmore the
gre
edy sna
k
e al
so ha
s
some
probl
em
s wit
h
the uppe
r l
e
ft corn
er a
n
d
the
tip of the leaf
[13].
5. Discussio
n
5.1. Compari
ng Compu
t
a
t
ional Speed
We have
ob
served h
o
w
well both of the
three
sna
k
e
s
find different
obje
c
t conto
u
r
s. Now
we will
briefly
examine the
computat
ional speed. In the table the ti
me it takes each
snake to
run
100 iteratio
ns is sho
w
n.
Table 1. Co
m
parin
g the ru
nning time of the Kass
et al. & greedy snake to the ru
nning time of
Our ap
pro
a
ch
Snake
Running time for
100 iterations
Kass
G
r
e
edy
Our a
pproach
0.893994 second
s
4.111357 second
s
0.5123 seconds
The
te
st wa
s run
on
a HP G62 Note
boo
k
P
C
2.
0
0
G
H
z.
with
4
G
B
ram.
The
shark to
oth
image
wa
s u
s
ed
with the f
o
llowin
g
pa
ra
meters. Kass et al.:
α
=0:
0
5,
β
= 0:00
05,
re
sampli
ng
on
and scale sp
ace co
ntinuat
ion
on. Gre
e
d
y:
α
=
1:2,
β
= 1,
ɤ
= 1:2,
neigh
bo
rh
ood size
5
ˣ
5 and
scale sp
ace contin
uation
on.
Th
e
Ka
ss et al.
sn
ake
is se
en
to b
e
si
gnificantly faste
r
tha
n
t
he
gree
dy sn
ake
whe
n
it com
e
s to runni
ng
a hun
dre
d
it
e
r
ation
s
. In pra
c
tice
ho
wever the Kass et
al.
sna
k
e al
so
h
a
s to comple
te a far great
er num
be
r of
iteration
s
to conve
r
ge. Th
us in
reality the
gree
dy sna
k
e
actu
ally co
n
v
erge
s fa
ster than th
e
Ka
ss et
al. sn
ake
.
My app
roa
c
h sna
k
e i
s
se
en
to be si
gnificantly faster th
an the Ka
ss
et al. sn
a
k
e&
the gre
edy sn
ake
wh
en it comes to
ru
nni
ng
a hund
red ite
r
ation
s
.
Our expe
rime
ntal results show that sn
a
k
e
s
c
an b
e
used to se
gme
n
t a variety of different
sha
p
e
s
. It wa
s al
so
e
s
tabli
s
he
d that
scale
spa
c
e
co
ntinuation
greatly red
u
ced
the influ
e
n
c
e of
noise in the image
s.
Comp
ari
ng th
e re
sults fro
m
both the Kass et
al. sn
ake a
nd the
gree
dy sn
ake
with my
approa
ch l
e
a
d
s
us to the
concl
u
si
on th
a
t
my app
ro
a
c
h sna
k
e
gives slig
htly bette
r results
overall.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
An Efficient Convergi
ng Sn
ake Algo
rithm
for
Locating Obje
ct Bound
arie
s (Atiqu
r Rahm
an
)
181
One of the re
aso
n
s fo
r the
better re
sults is of cou
r
se that our re sa
mpling meth
o
d
increa
se
s the
numbe
r of co
ntrol point
s which
en
able
s
the
sna
k
e
to
f
i
nd
the
conto
u
r of
fine
r
d
e
tails. Ho
wever
if
we try to in
crease the nu
m
ber of p
o
ints i
n
t
he greedy
sna
k
e, the
sn
ake
point nei
ghbo
rho
o
d
s
can
start to ove
r
l
ap. This l
ead
s to un
de
sire
d effe
cts
su
ch as th
e sna
k
e
curve
ove
r
lappi
ng in
some
places, o
r
e
v
en that the
distan
ce b
e
t
ween
sn
ak
e
points b
e
gi
ns to in
crea
se. The
r
efo
r
e we
recomme
nd t
o
use aroun
d 50 sna
k
e
control poi
nts
in the gre
e
d
y
sna
k
e, this numbe
r can
of
cou
r
se be in
crea
sed if high
resol
u
tion im
age
s are u
s
e
d
.
We al
so re
co
mmend that if the object to
be seg
m
en
ted contai
ns
boun
dary co
ncavitie
s
and n
o
ise th
at the initial
sna
k
e i
s
m
a
nually initia
li
zed. The
clo
s
er the i
n
itial
sna
k
e i
s
to t
h
e
desi
r
ed
contour the greater the pr
obability is of the snake al
so
convergi
ng to the desired
conto
u
r. Having to initiali
ze the sna
k
e
close to
the
de
s
i
re
d
c
o
n
t
our
ca
n
o
f
c
o
urs
e
pr
es
e
n
t
s
o
me
probl
em
s if a
compl
e
tely a
u
tomatic
syst
em for cont
o
u
r d
e
tectio
n i
s
sou
ght after. The
pro
b
le
m of
needi
ng to find a good ini
t
ial position to increa
se th
e cha
n
ce of finding the de
sire
d co
ntou
r is
actually o
ne
of the inhe
re
nt probl
em
s with sna
k
e
s
. This p
r
o
b
lem
has l
e
ad to m
u
ch
re
sea
r
ch
into
how to be
st initialize the
snake cu
rve.
Another p
r
obl
em with sna
k
es is the fact that
the para
m
eter of the sna
k
e often h
a
s to be
adju
s
ted for e
a
ch n
e
w
kin
d
of image in o
r
de
r to give the be
st re
sult
s. Findin
g sui
t
able value
s
for
the para
m
ete
r
s relie
s on m
anual tunin
g
based on trial
and error. Th
is pro
c
e
s
s ca
n often be time
con
s
umi
ng. In the above t
e
st ru
ns th
e p
a
ram
e
ters we
re adj
ust
s
for
each sna
k
e i
n
ea
ch ima
g
e
to
give the best
possibl
e re
sul
t
.
5.2. Extensio
ns and Improv
ements
In this section extensions to the original
algorithm
s will be presented along with the
improvem
ent
s we h
a
ve made in orde
r to better the al
gorithm
s
.
5.2.1. Stopping Crite
r
ion for th
e Ka
ss
et al. Snake
In the origin
al pape
r by Kass et al. no indi
cation
was give
n as to wh
en the sn
ake
evolution
sho
u
ld be
sto
p
p
ed. In the g
r
eedy alg
o
rith
m we
wo
uld
stop the
itera
t
ions
whe
n
ei
ther
the maximu
m numbe
r of
iteration
s
ha
d been
exce
eded o
r
whe
n
the num
be
r of sn
ake p
o
ints
moved in the
last iteration
was b
e
lo
w a thre
shold.
Setting an upper limit on
the numbe
r of
ite
r
a
t
io
ns
ru
n
,
c
a
n o
f
co
ur
se
a
l
so
be
us
ed
fo
r
the
Kass et. al.
sna
k
e. Ho
weve
r we ca
nnot
use
the
numbe
r of po
int moved as
a stoppi
ng
cri
t
erion for
th
e Kass
et. al. snake. This i
s
becau
se mo
st
of the points in the sna
k
e
keep m
o
vin
g
even wh
en
the sna
k
e h
a
s rea
c
he
d its minimu
m, the
movement at
the minim
u
m is h
o
weve
r very
sma
ll.
Knowi
ng tha
t
the movem
ent of the
sn
ake
points at the
minimum wil
l
be quite sm
all, we
su
gge
st to stop th
e sna
k
e al
go
rithm wh
en the
followin
g
term drop
s bel
o
w
a given thresh
old
Whe
r
e the vector v(s)t contain
s
the indices
to the sna
k
e poi
nts at time step t and v(s)t
̶
1
contai
ns the sna
k
e poi
nts at time step t
̶
1. We divide by n which is the total numbe
r of con
t
rol
points in th
e sna
k
e. Usu
a
ll
y a greate
r
n
u
mb
e
r
of co
ntrol poi
nts will
lead to the term
ǁ
v(
s
)
t
̶
v(
s
)
t
̶
1
ǁ
taking o
n
larg
er value
s
, whi
c
h is
why we
divide by n.
This imp
r
ov
ement of the Kasset al. sna
k
e h
a
s bee
n in
corpo
r
ated i
n
to our
impleme
n
tation.
5.2.2. Activ
e
Res
a
mpling of the
Kas
s
et al. Snake
Curv
e
In this sectio
n we th
erefo
r
e pre
s
e
n
t an
impr
ovem
en
t to the origi
nal Kass et
al. sna
k
e
algorith
m
whi
c
h ma
ke
s su
re that the distan
ce
s between all the snake cont
rol
points remai
n
more o
r
less
equal.
Once the sna
k
e h
a
s
starte
d evolving th
ere i
s
no g
u
a
r
antee th
at the sn
ake
co
ntrol points
are
equ
ally spaced, ho
we
ver the
sna
k
e cu
rve
c
an
be dyna
mical
l
y resample
d
while it
evol
ves.
The re
sam
p
li
ng step that
we have a
d
d
ed to the or
i
g
inal Kass et
al. snake first com
pute
s
the
averag
e di
sta
n
ce
between
all the
sna
k
e
cont
rol p
o
int
s
. The
n
we it
erate
s
throug
h all the
sn
a
k
e
control poi
nts while
rem
o
ving poi
nts in
parts
of
the
snake where the poi
n
ts a
r
e
clo
s
e tog
e
th
er
comp
ared to
the ave
r
ag
e
dista
n
ce. At the same
time
the re
sa
mpling step
also
insert
s new
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 14, No. 1, April 2015 : 173 – 18
4
182
points i
n
p
a
rt
s of the
sna
k
e wh
ere poi
nts a
r
e fa
r a
part comp
ared t
o
the ave
r
ag
e dista
n
ce. When
a new
point i
s
in
serte
d
, it is in
serte
d
in the
middl
e of the line conn
ecting the t
w
o points th
at are
far apart. Th
e resamplin
g
is not perfo
rmed after e
a
ch iteration
of the s
nake, in the actual
impleme
n
tation we h
a
ve, in orde
r to re
duce com
put
ation, set the
resamplin
g to be pe
rform
ed
every time the sna
k
e h
a
s i
t
erated 15 tim
e
s.
Let u
s
ta
ke
a loo
k
at an
example
an
d see
ho
w a
dding
the
re
sampli
ng
ch
a
nge
s the
result. In Fig
u
re 1
5
the ini
t
ial sna
k
e i
s
sho
w
, it co
nsist of 100
sn
ake
co
ntrol p
o
ints lai
d
out
in a
circle aro
und
the
obj
ect we wish
to segm
en
t. Ru
nning th
e K
a
ss et al.
sn
ake,
with
sn
ake
resampli
ng tu
rned
on, resu
lts in the
sna
k
e
conve
r
gi
n
g
after 21
63 i
t
eration
s
to t
he state th
at is
see
n
in Figu
re 16. We n
o
tice that when
the
sna
k
e
ha
s co
nverged i
t
hasin
crea
se
d the numb
e
r of
control p
o
ints to 195. T
h
is
is to b
e
expe
cted,
si
n
c
e th
e re
sam
p
ling
function
is
more i
n
cli
ned
to
add point
s to the snake ra
ther than re
m
o
ve them
. This inclin
ation
can h
o
weve
r
be ch
ange
d by
adju
s
tinga th
reshold valu
e in the resample fun
c
tion. Adding addition
al po
int to the snake
actually give
s a better fit to the contou
r, si
nce more
points mea
n
that finer details along th
e
conto
u
r can
be m
odele
d
by the
cu
rv
e. Anothe
r thin
g to n
o
tice
is
that the
sna
k
e in th
e
right
half
of Figu
re
16
is n
o
t abl
e to
move into
the
co
ncave
p
a
rt
of the
obj
ect
.
This is a
tra
i
t that both
th
e
gree
dy
sna
k
e an
d the
K
a
sset al.
sn
a
k
e
exhibits,
and
we
will
discu
s
s it in
more
detail
i
n
the
experim
ental results chapt
er.
Figure 15. Th
e initial state of
th
e
s
n
ak
e
Figure 16. Th
e final state o
f
the sna
k
e
wh
en usi
ng
resampli
ng, a
fter 2163
iteration
s
Figure 17. Th
e final state o
f
the sna
k
e
without re
sam
p
li
ng.
The final stat
e occurre
d
after
2346 iteration
s
To co
mpa
r
e t
he re
sult
we
got wh
en hav
ing re
sa
mplin
g turne
d
on,
we ran the K
a
sset al.
sna
k
e al
gorit
hm in its origi
nal form i.e. with
re
sam
p
ling turne
d
on
the same te
st image. We set
the initial sn
ake to con
s
i
s
t of 195 co
ntrol point
s
to make
su
re
that the end result i
s
directly
comp
arable
with the
re
sul
t
obtaine
d fro
m
having
resampling
turne
d
on.
The
con
v
erged
sna
k
e
is
s
h
ow
n
in
F
i
gu
r
e
1
7
,
th
is
time
c
o
n
v
er
gen
c
e
to
ok
2
346
ite
r
a
t
io
ns
.
Whe
n
compa
r
ing the t
w
o result
s we qui
ckly
see that
not usi
ng ou
r resamplin
g
method
gives worse result
s for the final segm
ent
ation. This
is
most noticea
ble in the lower left part of the
obje
c
t in Fig
u
re 1
7
where the sna
k
e
curve
doe
s
not follow the c
ontour very well. It is
als
o
notice
able th
at the sna
k
e
control p
o
ints are
mo
stly
concentrate
d o
n
the ri
ght
si
d
e
of the o
b
je
ct in
Figure 17 whi
l
e being mu
ch further a
p
a
r
t on the left
side. We can t
herefo
r
e
con
c
lud
e
that usi
n
g
our
sug
g
e
s
te
d sn
ake re
sa
mpling te
chni
que n
o
t only
help
s
keep th
e point
s mo
re
evenly sp
aced,
whi
c
h in turn make
s th
e curvatu
r
e
term more
preci
s
e. B
u
t also dire
ctly improve
s
the
segm
entation
of the object in que
stion.
5.2.3. Rando
mizing Snak
e Points for the Gree
d
y
A
l
gorithm
The last imp
r
ovement that has bee
n implem
ente
d
is
con
c
e
r
ne
d wi
th the greedy
sna
k
e
algorith
m
. It
wa
s noted du
ring initial test runs,
wh
en impleme
n
ting
the greedy snake algo
rith
m,
that the sna
k
e sometime
s wo
uld hav
e a tenden
cy to rotate. The rotatio
n
is parti
cula
rly
notice
able
when the i
m
ag
e ene
rgy i
s
more
or l
e
ss
con
s
tant th
ro
ugho
ut the snake. Thi
s
ro
tation
is due to the fact that the for-l
oop, whi
c
h run
s
throu
g
h
all the snake points com
puting their n
e
w
positio
n, doe
s so
con
s
e
c
u
t
ively. So if o
ne of t
he con
t
rol points in
the sna
k
e i
s
moved clo
s
e
r
to
anothe
r co
ntrol point, and
the image energy an
d cu
rvature ene
rgy is more o
r
less co
nsta
nt
thought the
sna
k
e, it will
tend to p
u
sh the next
control
point.
This i
s
b
e
ca
use th
e ela
s
t
i
city
energy for th
e greedy
sn
a
k
e
alway
s
tri
e
s to
k
eep th
e point
s eve
n
ly sp
aced.
Once o
ne of
the
Evaluation Warning : The document was created with Spire.PDF for Python.