TELKOM
NIKA
, Vol. 11, No. 8, August 2013, pp. 43
5
7
~4
366
e-ISSN: 2087
-278X
4357
Re
cei
v
ed
Jan
uary 5, 2013;
Re
vised
Ma
y 12, 2013; Accepted Ma
y 20
, 2013
An Optimized Iteration Algorithm based on C-V Model
and Graph Cuts
Hong La
n*
1,2
, Lequan Min
1,3
1
Schools of Aut
o
matio
n
an
d Eclectron
i
c Engi
neer
ing,
Un
iver
sit
y
of Scie
nce
and T
e
chno
log
y
Bei
j
i
ng.
Beiji
ng,1
0
0
83,
Chin
a
2
School of Infor
m
ation a
nd T
e
chno
log
y
, Ji
an
gXi Un
iversit
y
of Science a
n
d
T
e
chnol
og
y
GanZ
hou,3
4
1
0
00, Chi
n
a
3
Schools of Mathematics a
n
d
Ph
y
s
ics, U
n
iv
ersit
y
of Sci
enc
e and T
e
chno
l
o
g
y
Bei
jin
g
Beiji
ng,1
0
0
83,
Chin
a
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: lanh
on
g69
@
163.com
A
b
st
r
a
ct
C-V mod
e
l ca
n self-a
da
pt to the ch
ang
es
of cu
rve to
pol
ogy b
u
t req
u
ir
es more
iterati
ons a
n
d
nee
ds more co
mp
utin
g time. Graph cuts alg
o
rith
m is goo
d at getting the g
l
ob
al opti
m
u
m
in a short time
bu
t
not suita
b
le for
concav
e ob
je
ct ex
traction. T
o
overc
o
me th
e flaw
s of
thes
e tw
o algor
ith
m
s, an
opti
m
i
z
e
d
iteratio
n al
gorit
hm
has be
en
prop
osed.
F
i
rst the initia
l cont
our is def
or
me
d w
i
th an impr
oved C-V
mo
d
e
l,
w
h
ich w
a
s w
i
thout re-
i
n
i
tial
i
z
ation
dur
ing
it
erative
proc
es
s and
the
it
er
ation st
op c
o
n
d
itio
n is s
e
t b
y
calcul
atin
g cha
ngi
ng ar
ea w
i
thin the c
onto
u
r
. T
hen the ac
tive conto
u
r is
input to gr
ap
h cuts alg
o
rith
m.
Dilates
the
co
ntour into its nei
ghb
orh
ood
and
for
m
ed
a
n
in
ner
an
d
a
n
o
u
ter b
o
u
n
d
a
ry se
perativ
el
y,
chan
ges thes
e tw
o bounda
ries as sourc
e
and si
nk
, and obta
i
ns th
e final co
ntou
r by graph c
u
ts.
Exp
e
r
ime
n
t
s sh
o
w
th
a
t
thi
s
op
ti
mi
z
ed al
g
o
r
i
t
h
m
red
u
c
e
s
the
i
t
e
r
a
t
i
o
n tim
e
, a
n
d
ha
s be
tte
r e
ffe
ct a
n
d
h
i
gher
efficiency for i
m
a
ge se
g
m
ent
ation.
Ke
y
w
ords
: C-V mo
del, iterati
on, grap
h cuts
alg
o
rith
m, i
m
a
ge seg
m
entati
o
n
Copy
right
©
2013 Un
ive
r
sita
s Ah
mad
Dah
l
an
. All rig
h
t
s r
ese
rved
.
1. Introduc
tion
Active co
ntou
r mod
e
ls
hav
e gain
ed p
o
p
u
larity
in ima
ge segm
enta
t
ion in recent
years.
They g
ene
ral
l
y com
e
in
two
kin
d
s:
on
e ki
nd
are th
e pa
ram
e
tric mod
e
ls,
su
ch a
s
the
Sn
ake
model [1,
2], and the
othe
r are
geo
metri
c
mo
del
s, like
the Level
Se
t method [3
-5
]. The first ty
pe
model
s are the edg
e-b
a
sed model
s, d
epen
ding
on
the gradi
ents of the images. The seco
nd
kind
one
s a
r
e regi
on
-ba
s
ed, whi
c
h
re
pre
s
ent
cont
ours a
s
the
zero level
se
t of an impli
c
it
function d
e
fined in a hi
gher di
men
s
i
on and
cal
c
ul
ate the evolution of this ne
w functi
on.
Comp
ared wi
th the param
etric mo
del
s, the majo
r a
d
vantage of
geomet
ric
m
odel
s is that they
can
self-ada
p
t
to the cu
rve topolo
g
y chang
es i
n
th
e evolution
p
r
ocess, an
d t
h
is
cha
r
a
c
teri
stic
make
s up for the shortag
e
of the parameter mod
e
l
s
whi
c
h ne
ed
to track the positio
ns of the
curve evol
ution .
C-V
mod
e
l [
5
] is a
cla
s
si
c g
eom
etric
deform
a
tion
model. T
h
e
model
can
a
c
curately
segm
ent the
obje
c
t even whe
n
the initial conto
u
rs a
r
e not compl
e
tely in the internal o
r
exte
rnal
homog
ene
ou
s
regi
on
s. Bu
t duri
ng th
e p
r
ocess of ev
o
l
ution, the
co
ntour ha
s to
be
re-i
nitialized
with
sign
ed
distan
ce
fun
c
tion i
n
e
a
ch
iteratio
n, which
ma
ke
s t
he al
gorith
m
sp
endi
ng
m
o
re
comp
uting ti
me and
red
u
c
ing th
e se
g
m
entation a
c
curacy. Chun
ming Li [6] p
r
opo
se
d a n
e
w
variational le
vel set mode
l without re
-i
nitializ
ation,
whi
c
h defin
e
d
an extern
al
energy to be a
penalty fun
c
tion an
d d
r
ive
d
the
zero le
vel cu
rv
e toward th
e obj
ect bound
ary. T
h
is m
odel
sa
ved
some ite
r
atio
n time,but be
cau
s
e the p
e
nalty f
unction
was b
a
sed
on the gradie
n
t, the evolution
results was li
mited to stop
at the
bound
a
r
y nearest to the initial co
ntour.
Grap
h cut
s
[7, 8] based
on the gra
p
h
theory has
also b
een wi
dely use
d
in image
segm
entation
becau
se of t
heir effici
en
cy and glob
al optimizatio
n cha
r
a
c
teri
stics.
Min-cut/ma
x
-
flow [9] algori
t
hm is cla
ssi
cal one of the
m
. Ni
ng Xu [10] prop
osed
GCBAC (Graph Cuts Ba
sed
Active Conto
u
rs) alg
o
rith
m, which
wa
s the co
mb
in
ation of max-flow/min-cut
grap
h theo
ry and
geomet
ric
def
ormatio
n
mo
del. GCBA
C
algorith
m
imp
r
oved
com
put
ing efficie
n
cy
but not suitab
le
for
can
c
ave
i
m
age
s.
Ref [
11] ha
s presented
a
dual
Level
sets
a
l
gorithm
to i
m
prove
G
C
B
A
C.
Evaluation Warning : The document was created with Spire.PDF for Python.
e-ISSN: 2
087-278X
TELKOM
NIKA
Vol. 11, No
. 8, August 2013: 4357 –
4366
4358
The alg
o
rith
m defined t
w
o initial co
nto
u
rs i
n
the target are
a
an
d
set up t
w
o le
vel set fun
c
tions.
But two co
nto
u
rs
and t
w
o l
e
vel set fun
c
tions in
crea
se
d the co
mple
xity of
the alg
o
rithm. And t
h
e
iteration te
rmi
nation thresh
old was
set a
s
10
-4
to 10
-3
times of the i
m
age
size is
not gen
erality
for
all images.
Con
s
id
erin
g t
he cha
r
a
c
teri
stics of
C-V
model
and graph cuts,
th
e former
is
self-adapt
to
the ch
ang
es
of cu
rve topo
logy and th
e
latter is
fa
st
spp
ed. Thi
s
pape
r p
r
op
osed an
optimi
z
ed
iteration alg
o
r
ithm ba
sed
on the two al
gorithm
s. Co
ntrast
with the dual level
sets al
go
rith
m in
Ref [11], the
optimize
d
al
gorithm
de
si
gned
a sin
g
l
e
level set a
s
initial conto
u
r to si
mplify the
evolution pro
c
e
ss a
nd set the it
erative terminatio
n condition b
a
se
d on area wit
h
in the co
nto
u
r.
The p
r
op
ose
d
algo
rithm
combine
s
b
o
th
algorith
m
s’
a
d
vantage
s, ef
fectively redu
ced th
e level
set
iteration times and prevents the
evol
ution falling into the local
mi
nimum. The
algorithm makes
the conto
u
r f
a
ster
co
nverge to the obj
ect bou
nda
ry
and imp
r
ove
s
the segme
n
tation efficie
n
cy
and effective
ness.
2. Rese
arch
Metho
d
The optimi
z
e
d
algo
rithm i
s
an integ
r
ate
d
schem
a wh
ich in
clu
des f
o
llowin
g
ste
p
s
: firstly,
optimize initia
lization with i
m
prove C-V model; se
co
n
d
ly, provide a new app
roa
c
h to set iteration
terminate
d
co
ndition; thirdl
y, to improve iteration effici
ency with g
r
a
ph cut
s
algo
ri
thm.
2.1. Impro
v
e
d
C-V Model
to
Optimize Initializ
ation
C-V mod
e
l was ba
se
d on
curve evol
ution t
heory an
d level set method. Let an
image
(,
)
Ix
y
,which is
divided into t
w
o
homog
ene
ou
s re
gion
s
()
in
C
and
()
out
C
by a con
t
our
C
.
Suppo
se that
(,
)
Ix
y
is gray level distributio
n uniformity
in there two regio
n
s, obtain the
energy
function
al of the C-V mo
del
is
：
1
2
ml
l
òò
òò
2
12
1
in
(C
)
2
2
ou
t
(
C)
Le
ngt
h(
C
)
dxdy
+d
x
d
y
E
(
C
,
c
,
c
)
=
+
I
(
x,
y)
-
c
I
(
x,
y)
-
c
(1)
In whic
h
，
1
c
an
d
2
c
are
the
a
v
erage
g
r
ay
levels i
n
the
two
hom
og
eneo
us re
gio
n
s.
0
m
³
，
12
0
ll
>
,
are
wei
ghting coefficie
n
ts for
ea
ch te
rm. The first term
rep
r
e
s
en
ts the le
ngth
of closed curve
C
and the last two are glo
bal bina
ry fitting term
s.
Take
He
avisi
de and
Dira
c function into
E
quation (1
) and get the
level set evolution
equatio
n:
e
e
e
jm
j
j
j
j
dl
l
WW
W
=Ñ
+
+-
-
-
òò
òò
òò
12
2
2
11
22
1
E
(
,c
,c
)
(
)
(
)
d
x
d
y
H
(
)
d
x
d
y
(H
(
)
)
d
x
d
y
I(x
,
y
)
c
I(x
,
y
)
c
(2)
Whe
r
e
e
j
p
e
=+
æö
÷
ç
÷
ç
÷
ç
èø
12
1(
)
2
Ha
r
c
t
a
n
and
'
()
e
e
e
pe
j
dj
+
==
22
1
H
.
Minimizi
ng th
e energy functional
j
12
E
(
,c
,c
)
gets th
e fomulation
s of
1
c
and
2
c
to be:
j
j
j
W
W
=
òò
òò
1
(,
)
(
(,
)
)
()
((
,
)
)
Ix
yH
x
y
d
x
d
y
c
Hx
y
d
x
d
y
,
j
j
j
W
W
-
=
-
òò
òò
2
(,
)
(
1
(
(,
)
)
)
()
1(
(
,
)
)
I
x
y
H
x
y
dx
dy
c
Hx
y
d
x
d
y
(3)
Substitute the
rep
r
e
s
entatio
ns
(3) of
1
c
and
2
c
into e
quatio
n (2
). And th
e
n
acco
rdi
ng t
o
the variationa
l princi
ple an
d gradi
ent de
scent
flow me
thod, solutio
n
of the equation (2
) is
：
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
e-ISSN:
2087
-278X
An Optim
i
zed
Iteration Algorithm
base
d
on C-V Mo
del
and Graph Cuts (Hong L
a
n
)
4359
(
)
(
)
(
(
,)
-
)
(
(
,)
-
)
di
v
I
x
y
c
I
x
y
c
t
jj
dj
m
l
l
j
é
ù
ê
ú
ê
ú
ê
ú
ë
û
¶Ñ
=-
+
¶Ñ
22
11
2
2
(4)
In the origin
al C-V mo
de
l, the solutio
n
of Equatio
n (4)
depe
nd
s on its initia
l signe
d
disten
ce fu
nction
0
j
. Du
ring
the iteration p
r
oce
s
s, level
set fucntion
j
has to
be
re
-ini
tialized i
n
each iteratio
n
with
0
j
, beca
u
se th
e level
set fun
c
tion
is ea
sy to de
viate far from
the sig
ned
distan
ce fun
c
tion. Its soluti
on is sen
s
itive to
initial
contour and spend
s
mu
ch more com
put
ing
time.
In orde
r to solve the re
-in
i
tialization p
r
obl
em a
nd i
m
prove the
speed a
nd effi
cien
cy for
origin
al
C-V
model,
we
now refe
re
nce the
metho
d
which p
r
o
posed
by Chunmin
g Li
[6].
Introdu
ced
a
pen
alizi
ng
energy into
the si
gne
d d
i
stan
ce fu
nct
i
on, the
fo
mulation
of t
he
penali
z
ed ite
m
is :
2
()
(1
)
2
P
dx
dy
j
j
W
=
Ñ-
òò
(5)
Cal
c
ulate its
gradi
ent de
scent flow
：
1
()
(
1
)
di
v
d
i
v
t
jj
jj
jj
¶Ñ
=D
-
=
-
Ñ
¶Ñ
Ñ
é
ù
ê
ú
ê
ú
ë
û
(6)
Substuitute t
he Equatio
n (6) into Equ
a
tion (4
) an
d ge
t the evolution formulatio
n
for C-V
model with
ou
t re-initiali
z
ati
on:
22
11
2
2
(
)
[
(
)
(
-
)
(
-
)]
(
(
))
di
v
I
c
I
c
t
j
jj
dj
m
l
l
n
j
j
j
¶Ñ
Ñ
=-
+
+
D
-
Ñ
×
¶Ñ
Ñ
(7)
Whe
r
e
n
is
the weighted c
o
effic
i
ent for the las
t
term.
Usi
ng Equati
on (7
) gives t
he improved
C-V mo
del
wi
thout re-i
nitial
ization. Equ
a
tion (7
)
is b
e
tter to
a
v
oide the
re-i
nitialization
t
han E
quation
(4
) a
n
d
imp
r
oves
C-V m
odel’
s
spe
e
d
in
s
o
me
de
gr
e
e
.
C-V mod
e
l is base
d
on le
vel set functi
ons,
which in
cre
a
ses the
space dimen
s
i
ons a
n
d
comp
utation
compl
e
xity. Actually, the
ke
y point of
the
algorith
m
imp
l
ementation
for
C-V m
odel
i
s
nume
r
ical iteration. Whe
n
to
end iteratio
n depe
nd
s on
the iterat
ive stop
conditio
n
s. Althoug
h the
more time
s the algo
rithm
iterates, the
clo
s
er th
e co
ntour i
s
to the obje
c
t bou
ndary, it spe
n
d
s
much
mo
re
time eith
er. E
s
pe
cially
wh
e
n
the
co
ntou
r is quite
cl
ose to th
e o
b
je
ct bo
und
ary,
in
each iteration
the contou
r is only ch
ang
ed a little or sometime
s no
cha
nge.
Figure 1 sho
w
s an examp
l
e
abo
ut
the relation
s
of the iteration ti
mes,
co
st time an
d
segm
entation
result
s with
C-V mod
e
l.
(a)
(b)
(c
)
Figure 1. Rel
a
tion Ch
art of Evolution Cu
rve Cha
nge
Rate an
d Iteration Time
s
Evaluation Warning : The document was created with Spire.PDF for Python.
e-ISSN: 2
087-278X
TELKOM
NIKA
Vol. 11, No
. 8, August 2013: 4357 –
4366
4360
Figure 1(a) i
s
a te
sting i
m
age, bul
e a
nd re
d curve
respe
c
tively rep
r
e
s
ent
s the pla
c
e
after iterated
200 and 3
0
0
times. Figure 1(b) i
s
the relation
cha
r
t between iteration times a
nd
curve
chan
ge
rate, h
e
re
we define
S
D
den
otes the
area
su
rro
und
ed
by the curve
on the
it
h
iteration,
i
t
me
ans the itera
t
ion co
st time. curve cha
nge rate
ii
r
St
=D
/
. Figure1(c
) is
the
relation b
e
tween the iterati
on times an
d co
st time.
From figu
re 1
we can
see t
hat whe
n
the
algor
ith
m
iterated from 2
0
0
times to 30
0 times,
there’
re no
si
gnifica
nt cha
nge
s fo
r the
evolution curve. And durin
g
the whol
e iteration, the
cost
time is alm
o
st the sam
e
. Usually the
suitable it
eration time
s get
throug
h te
sts or exp
e
rim
e
nts.
The be
st on
e to be choo
sed
sh
ould
consi
der
s
e
g
m
entation a
c
curacy a
nd
cost time. In this
pape
r
we
introdu
ce
a
new metho
d
to
set the
end
condition
of it
eration
s
so t
hat imp
r
ove
the
effic
i
enc
y
of C-V model.
2.2. Iteration
Terminated
Conditio
n
ba
sed on Ar
ea
In the ori
g
ina
l
C-V m
odel,
the thre
sh
old of termin
ation iterate
d
condition
a
value i
s
usu
a
lly estim
a
ted throu
g
h
experiment
s.
In our
optimized alg
o
rith
m, we introd
uce
d
a cha
n
g
ing
variable
P
to b
e
the iteratio
n terminate
d
con
d
ition.
P
denote
s
the inner a
r
ea surround
ed by
evolution con
t
our. The formulation of calcultin
g
P
is shown as b
e
lo
w :
{}
n
ij
nn
ij
ij
h
n
ij
Ph
nu
m
i
j
h
+
j<
j-
j
=£
j<
t
å
,
1
,,
2
,
(,
)
(8)
Whe
r
e
(,
)
ij
den
o
t
es the
co
ord
i
nate of e
a
ch
pixel in the
image,
,
n
ij
j
and
n1
i,
j
+
j
are fu
nctio
n
s
r
e
sp
ec
tive
ly to
r
e
pr
es
en
t th
e
nth
and
(1
)
nt
h
+
level s
e
t func
tion. Ac
tually
P
is a finite
differen
c
e fo
rmulation, in
whi
c
h
h
is the t
i
me interval
a
nd
t
is the
spa
c
e inte
rval. T
he value
s
of
h
and
t
are se
t dependi
ng
on different
images, u
s
ually
.,
[]
01
1
h
Î
and
.,
[]
00
1
0
.
1
tÎ
.
{
}
,
(,
)
n
ij
num
i
j
h
j<
mean
s the
numbe
r of g
r
ids
whi
c
h
satisfy the co
nditional in
e
quality
,
n
ij
h
j<
. Correspon
ding to the term thre
sh
o
l
d of
termin
ation iterate
d
con
d
ition,
define
2
a=
t
h
.
In
Equation (8), when
P
satisfies the
criterion, the al
gorithm will exit
the
iteration
process
of level set functi
on. Otherwi
se the it
eration will continue. Us
ing formulation (8)
to
cre
a
te termin
ation iterated
con
d
ition for
Equation
(7)
spe
e
d
s
up th
e iteration efficen
c
y of abro
v
e
improve
d
C-V model. In o
u
r p
r
op
osed
algorith
m
, improved
C-V model i
s
u
s
e
d
to pr-proce
ss th
e
inital conto
u
r.
2.3. Graph Cuts Algo
rith
m for Image Segmenta
tio
n
Figure 2.
ST
cu
t
-
Schematic
Diag
ram
The ba
si
c id
ea of graph
cuts
algo
rith
m is to ch
an
ge the imag
e
into a gra
p
h
and then
use
s
gra
ph t
heory to
reali
z
e
se
gmenta
t
ion [7]. Give
n an
imag
e
with the
see
d
s
of obj
ect
and
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
e-ISSN:
2087
-278X
An Optim
i
zed
Iteration Algorithm
base
d
on C-V Mo
del
and Graph Cuts (Hong L
a
n
)
4361
backg
rou
nd
respe
c
tively, as sho
w
n
in Figure
2(a
)
,
O
denote
s
obje
c
t an
d
B
denote
s
backg
rou
nd. Con
s
tru
c
t
its weig
hted
g
r
a
p
h
(,
)
GV
E
=
, shown in Figu
re 2
(
b) and 2
(
c).
V
is the
vertex set of
the grap
h an
d con
s
ist
s
of
image pixels, additional includi
ng two termin
als
S
and
T
, which re
sp
e
c
tively denotes the termin
al of object and backg
ro
un
d.
E
is the edge set of the
grap
h re
presenting the
co
nne
ction relat
i
ons of a
d
ja
c
ent pixels in t
he imag
e, also inclu
d
ing th
ose
edge
s from
e
a
ch
pixel to
termin
al
S
and
T
. Com
pute
ed
ge
weig
hts
b
a
se
d o
n
e
a
ch
vertex a
n
d
its neigh
bou
rhood [12].
Define a
ST
cu
t
-
to be a sub
s
et
C
of the edge
set
E
,
CE
Ì
.
ST
cu
t
-
s
e
pr
a
t
es
the grap
h into two co
n
necte
d su
b-grap
hs. Th
e
vertices
co
nne
cting wit
h
S
and
T
are
respe
c
tivelly corre
s
p
ondin
g
to the object and backg
ro
und pixel
s
. The ca
pa
city of a
ST
cu
t
-
is
defined
as the
sum
m
ation of
t
he ed
g
e
s
weig
hts acro
ssi
ng
the
cut
, i.
e.
,,
(
,
)
(,
)
(,
)
uS
v
T
u
v
E
cS
T
cu
v
ÎÎ
Î
=
å
. According t
o
the Theore
m
of Ford-F
ulke
rson [8] , in th
e
ST
-
netwo
rk, the
maximum flow from a vertex
S
to vertex
T
is equal
to the capa
city
(,
)
cS
T
of
the minim
u
m cut sep
a
rating
S
and
T
. The
ST
-
minimu
m cut proble
m
can
be
solved by u
s
i
ng max-flo
w
algorith
m
s.
Based
on m
a
x-flow/min-cu
t
algorithm,
Ning Xu
et.al. [10] pro
p
o
s
ed
GCBAC
algo
rithm in
2007. T
he
ba
sic idea
of th
e algo
rithm i
s
to re
prese
n
t
the imag
e a
s
an a
d
ja
cen
cy grap
h. Define
an initial
cont
our a
nd dil
a
te
the co
ntou
r i
n
to it
s nei
ghb
orho
od
with the inn
e
r a
nd
outer b
oun
da
ry,
eventrally form a n
a
rro
w
b
and. Th
en tre
a
t the ve
rti
c
e
s
in th
e in
ner boun
da
ry as the sou
r
ce
S
and the
verti
c
e
s
in th
e o
u
ter b
oun
dary as the
si
nk
T
. Cal
c
ulate
the ed
ge
wei
ghts
and
use
ST
-
minimum cut method to obt
ain a ne
w bo
unda
ry.
GCBAC alg
o
r
ithm overco
mes the defe
c
ts that
the tradition
al def
ormatio
n
mo
dels a
r
e
easy to
fall in
to local optim
al, and
be
cau
s
e it
s
cal
c
ulat
ing i
s
within a
narro
w
band
, the alg
o
rith
m
is high
efficie
n
cy an
d low ti
me co
mplexit
y
. But
GCBAC algo
ritm is
not goo
d at segmentatin
g the
con
c
ave ima
ges, an
d be
cause the initial conto
u
r in
GCBAC i
s
se
t randomly, if the conto
u
r i
s
not
clo
s
e to the
obje
c
t bou
nd
ary, it will affect the n
a
rro
w
ba
nd to fo
rm and
re
sult
in the ina
c
curate
segm
entation
result
s. Figu
re 3 sho
w
s an
liver image segmentatio
n with GCBA
C.
(a) Initial contour
(b) Segment
ation result
Figure 3 Liver Image Segmentat
ion with GCBAC Algorithm
In Figure 3,
image pixel
s
of the fore
gran
d obj
ect
and the b
a
c
kgro
und
are
similar.
there’
s
a
can
c
ave i
n
si
de t
he live
r
, fro
m
Figu
re
3
(
b
)
we
ca
n
se
e it’s not
go
od fo
r G
C
BA
C’s
algorith
m
to get the object
boun
dary.
Aim at the
sh
ortage
of G
C
BAC alg
o
rith
m dep
endi
ng
on th
e initial
co
ntour,
we
use
ou
r
improve
d
C-V model to pre-pro
c
e
s
s the initial
conto
u
r. Becau
s
e
C-V mod
e
l can adapt to the
cha
nge
s of
curve to
polo
g
y, it can help G
C
BA
C algo
rithm
to reali
z
e
can
c
ave im
a
ges
segm
entation
.
On the oth
e
r ha
nd, G
C
BAC algo
rith
m can
help
C-V mo
del t
o
improve th
e
segm
enting
speed
s an
d accuracy.
2.4. Main Process o
f
th
e Optimized
Algorithm
The o
p
timize
d algo
rithm
o
f
our
pro
p
o
s
ed in
cl
ud
es two p
a
rt
s: initializatio
n opti
m
ization
and ite
r
ation
pro
c
e
s
s opti
m
ization.
Th
e main
p
r
o
c
e
s
s of the
o
p
timized
alg
o
rit
h
m i
s
sho
w
n
as
Figure 4.
Evaluation Warning : The document was created with Spire.PDF for Python.
e-ISSN: 2
087-278X
TELKOM
NIKA
Vol. 11, No
. 8, August 2013: 4357 –
4366
4362
Figure 4. The Process of the Optimized
Algorithm
In Figure 4, the first t
w
o
steps
(a)
and
(b) i
ndi
cate t
he pre-pro
c
e
ss i
n
itializatio
n with
improve
d
C-V
model a
nd t
he la
st three
step
s (c)
to
(e) sho
w
the e
v
olution process with
GCB
A
C
algorith
m
.
(1) Initializati
on optimiz
ation
. First set a sin
g
le level
set contou
r
as a
n
initial contour.
As sho
w
n in
Figure 4
(
a
)
, set an initia
l contou
r
0
l
su
rro
und
ed the
object area,
choo
se o
u
r
improve
d
C-V model, iterate the
evolution conto
u
r
by level set
without re
-init
i
alizatio
n. Wh
en
iteration sto
p
s
, get the
curve of after evolution
'
0
l
and output to the next step, sh
own a
s
Figu
re
4
(
b)
. Be
ca
use
'
0
l
has
been
pre
-
p
r
o
c
e
s
sed with
the l
e
vel set
evol
ution , mu
ch
clo
s
e
r
to th
e
obje
c
t boun
d
a
ry than ra
nd
om initial cont
our, it is
more
efficiency for next step’s furthe
r evoluti
on.
(2) Ite
r
ation
proces
s opti
m
ization
. Set
'
0
l
as a ba
sic
boun
day, expand to bidire
ction
based on the
pixel and its neighb
ood i
n
formatio
n u
n
t
il reach the
fixed width field and form the
inner bo
und
a
r
y and
oute
r
boun
dary,
sh
own
a
s
Fig
u
re 4(c). Th
en
map the
s
e
vertiex to
ST
-
netwo
rk, Id
en
tify all the vertices
co
rresp
ondin
g
to the
inne
r bo
und
ary a
s
a
sin
g
l
e
so
urce
S
an
d
the vertice
s
corre
s
p
ondin
g
to the oute
r
bou
nda
ry a
s
a
singl
e si
nk
T
, sho
w
n a
s
Figu
re
4(d
)
.
Finally, use
min-cut/max flow algo
rith
m to get
the
real obje
c
t boun
dary extractio
n
, sho
w
n as
Figure 4
(
e).
From
Figu
re
4(c) to
4(e),
the alg
o
rith
m ru
ns f
r
om
step
②—
exp
antion, st
ep
③—
mappin
g
, an
d step
④—
cutting. This p
r
ocess is a
cycle,
until the cont
our reach the desired
boun
dary.
2.5. Realiza
t
i
on Steps o
f
the Optimize
d Algorithm
Acco
rdi
ng to
the above introdu
ction o
f
t
he algorith
m
’s bai
sc id
ea, we can get the
spe
c
ific ste
p
s of the
optimi
z
ed
iterative t
e
rmin
ation
al
gorithm
ba
se
d on
the im
proved
C-V m
o
del
and graph
cut
as follows:
Step 1: Initialize the thresh
old
2
a=
t
h
and the contour
0
l
;
Step 2: Creat
e the co
rre
sp
ondin
g
level set function
0
j
;
Step 3: Use
PDE method
, ie. Equation (7) to it
erated
evolution wit
h
level set function;
Step 4: Com
pute the a
r
ea
P
in Equatio
n
(8) ,
su
rro
un
ded by
conto
u
r
after evolu
t
ion,
Jud
ge if the area is le
ss th
an
a
, if
yes, stop iteration a
nd go
to Step 5, otherwi
se,
go back step
3.
Step 5: O
u
tp
ut the final
contour
l
'
0
as a
new initial
co
ntour
, then
expand
the
contour
bidire
ction
a
lly to form a narrow b
and a
r
e
a
.
Step 6: Co
nst
r
uct th
e
ST
-
network in
cludin
g
terminal
s
of a
singl
e source and
a si
ngl
e
sin
k
with the
node’
s identit
y algrithm.
Step 7:
Use
the max-flo
w
/
m
in-cut al
gori
t
hm
to rela
zi
se th
e
seg
m
entation ,a
nd
get the
final conto
u
r
l
.
Summari
ze t
he step
s of
the algorith
m
, the
flow cha
r
t of the optimized
iterative
terminatio
n al
gorithm i
s
sh
own in Fig
u
re
5.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
e-ISSN:
2087
-278X
An Optim
i
zed
Iteration Algorithm
base
d
on C-V Mo
del
and Graph Cuts (Hong L
a
n
)
4363
Figure 5. FlowChat of the Optimi
ze
d Iterative Termi
n
ation Algorith
m
3. Results a
nd Analy
s
is
In orde
r to verify the validity of optimized
iterative termin
ation al
gorithm, the
algorith
m
has be
en
realized
with
Matlab
an
d C++ o
n
Wind
ow XP ope
rating
system
platf
o
rm.
Comp
re
hen
si
ve con
s
ide
r
in
g the factors of
the images, incl
udin
g
image types, concave an
d
noises etc. In this pape
r,
we cho
o
se three type
s image
s to test. Using tradi
tional C-V m
odel
algorith
m
, Referen
c
e
[10]
’s al
gorith
m
and
our opti
m
ized
alg
o
rit
h
m to
seg
m
ent the
s
e th
ree
image
s re
sp
e
c
tively. Comp
ared thei
r seg
m
entation results as
sho
w
n
in Figure 6 to
Figure 8.
3.1. Experiments
Figure 6 sho
w
ed t
w
o me
d
i
cal ima
g
e
s
segmentat
io
n
results. On
e i
s
lung
CT im
age with
the size of 2
11×225 pixel
s
and the ot
her is liver
M
R
image with
the size of 633
×10
31 pi
xels.
Take th
e sam
e
operation
s
.
(a)Initial Cont
our
(b)se
g
mentati
on
result of the C-V
model alg
o
rit
h
m
(c) segme
n
ta
tion
res
u
lt of Ref
[10]’s algo
rith
m
(
d
)
pr
e-
p
r
o
c
es
s
initial contour of
our alg
o
rithm
(e) segm
enta
t
ion
result of our
algorith
m
Figure 6. Co
mpari
s
o
n
Ch
art of Medical
Im
ages Seg
m
entation Re
sults by u
s
ing
Three
Algorithm
s
,
1
,,
,
(,
)
n
ij
nn
ij
ij
h
n
ij
P
nu
m
i
j
h
2
h
Evaluation Warning : The document was created with Spire.PDF for Python.
e-ISSN: 2
087-278X
TELKOM
NIKA
Vol. 11, No
. 8, August 2013: 4357 –
4366
4364
First Set an i
n
itial conto
u
r
sho
w
n a
s
Fig
u
re
6
(
a
)
. Figu
re 6(b)
sho
w
ed the segm
entation
results of tra
d
itional C-V
model al
gorit
hm, whi
c
h it
erated
300 ti
mes, respe
c
tively cost time
36.985
se
co
nds a
nd 34.
372 second
s. From Figu
re
6(b
)
we
can se
e, C-V
model alg
o
rithm
coul
dn’t get good segme
n
tation re
sults f
o
r those
ima
ges
with unh
omoge
neo
us
gray levels a
nd
there would
cause many lo
cal minim
u
ms during the ite
r
ation p
r
o
c
e
s
s.
Figure 6
(
c)
showed th
e
se
gmentation
result
s of
th
e
algorith
m
of
Referen
c
e [1
0], whi
c
h
iterated the
same time
s
with Figu
re
6(b
)
,
re
spe
c
tively cost time 8.354 second
s and 1
0
.
385
se
con
d
s.
Usi
ng thi
s
al
go
rithm the
iterati
v
e co
ntou
rs
a
r
e
almo
st cl
o
s
ed
to the
re
al target e
d
g
e
s,
better avoid the local opti
m
ums.
F
i
g
u
r
e
6(
d)
s
h
ow
ed
th
e
fir
s
t-
pa
r
t
r
e
su
lts
,
ie
. pr
e-p
r
oc
es
s in
itia
l co
n
t
o
u
r
s
w
i
th
ou
r
optimiz
ed algorithm. Set the s
a
me threhold
a
=0.025 , l
ung im
age it
erated
10
6 times
and live
r
image ite
r
ate
d
10
0 time
s.
Whe
n
ite
r
atio
n sto
ped,
get
these
conto
u
rs a
s
n
e
w init
ial contou
rs a
n
d
calle
d gra
p
h
s
cut algorith
m
for segm
enta
t
ion, get the result
s as
sho
w
n in Figu
re
6(e
)
.
The optimi
z
e
d
algorith
m
total co
st time 5.
825 se
co
n
d
s an
d 6.978
second
s respectively.
From Fig
u
re
6(e
)
we can
see that the segm
ent
ation
result
s are
quite clo
s
ed
to the desire
d
boun
dari
e
s a
nd the obje
c
t regio
n
s h
a
ve been recogni
zed
well.
Figure
7 sh
o
w
ed
t
w
o gray
image
s seg
m
entation re
sults. One is owl im
a
ge
with
the si
ze
of 168
×1
67
pi
xels a
nd th
e
other i
s
flo
w
e
r
ima
ge
with t
he
size of
14
3×1
40
pixels.
Ta
ke the
sa
me
operation
s
.
(a)Initial Cont
our
(b)se
g
mentati
on
res
u
lt of the
C-
V
model alg
o
rit
h
m
(c) se
gment
ation
result
of Ref [10]’s
algorith
m
(
d
)
pr
e-
p
r
o
c
ess
initial contour of
our alg
o
rithm
(e) segm
enta
t
ion
result of our
algorith
m
Figure 7. Co
mpari
s
o
n
Ch
art of Gray Image
s
Segm
entation Results by usin
g Thre
e Algorit
hms
First Set an initial contou
r sho
w
n a
s
figure
7(a). Fig
u
re 7(b) sho
w
ed the seg
m
entation
results of tra
d
itional C-V model alg
o
rit
h
m, whic
h iterated 3
00 times , re
spe
c
tively cost time
22.558
secon
d
s
and
28.8
8
5
second
s. F
r
om the
re
sult
we
ca
n
see
t
hat the
C-V
model
is go
o
d
a
t
segm
enting
g
r
ay ima
g
e
s
,
but be
ca
use
its spee
d in
the
curve
evo
l
ution i
s
slo
w
, it need
s
mu
ch
more time.
Figure 7
(
c)
showed the
segmentatio
n
results
of
the
algo
rithm of
Ref.[10] ,wh
i
ch o
n
ly
co
st time 6.882 se
co
nd
s a
nd 7.97 seco
nds.Th
e
algo
rithm saved ti
me and the result
s are
clo
s
ed
to the real target edge
s.
F
i
g
u
r
e
7(
d)
s
h
ow
ed
th
e
fir
s
t-
pa
r
t
r
e
su
lts
,
ie
. pr
e-p
r
oc
es
s in
itia
l co
n
t
o
u
r
s
w
i
th
ou
r
optimize
d
al
g
o
rithm. Set t
he same th
re
hold
a
= 0.0
2
, owl im
age ite
r
ated
77 time
s an
d flo
w
er
image iterate
d
50 times . Whe
n
iteratio
n stope
d, get
these contou
rs a
s
ne
w initial conto
u
rs a
nd
calle
d gra
p
h
s
cut algorith
m
for segm
enta
t
ion, get the result
s as
sho
w
n in figure 7
(
e).
The optimi
z
e
d
algorith
m
total co
st time 5.
476 se
co
n
d
s an
d 5.867
second
s respectively.
From
Fig
u
re 7(e
)
we can see
that
the se
gmentation
re
sult are q
u
ite good.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
e-ISSN:
2087
-278X
An Optim
i
zed
Iteration Algorithm
base
d
on C-V Mo
del
and Graph Cuts (Hong L
a
n
)
4365
Figure 8
sho
w
ed
two
noi
se ima
g
e
s
. On
e is
star
with
the
si
ze
of 28
3×3
87 pixels and
th
e
other is tri
ang
le with the si
ze of 90×
98
p
i
xe
ls
. T
a
ke
th
e
s
a
me
op
er
atio
n
s
.
First Set an initial contou
r sho
w
n a
s
figure
8(a). Fig
u
re 8(b) sho
w
ed the seg
m
entation
results of tra
d
itional C-V
model al
gorit
hm, whi
c
h it
erated
300 ti
mes, respe
c
tively cost time
53.909
secon
d
s
and
74.0
6
1
se
co
nd
s.. From the
re
sult
s
we
ca
n
see
that the
C-V
model i
s
wea
k
to segme
n
t the noise imag
es.
Figure 8
(
c)
showed th
e
se
gmentation
result
s of
th
e
algorith
m
of
Referen
c
e [1
0], whi
c
h
iterated 3
00 t
i
mes, respect
i
vely cost 13.
774 se
cond
s and
15.4
87 seco
nd
s.
The results sho
w
ed
the algorith
m
is rob
u
st but t
he se
gmentin
g c
onto
u
rs are far from the
desired bo
un
darie
s.
F
i
g
u
r
e
8(
d)
s
h
ow
ed
th
e
fir
s
t-
pa
r
t
r
e
su
lts
,
ie
. pr
e-p
r
oc
es
s in
itia
l co
n
t
o
u
r
s
w
i
th
ou
r
optimize
d
alg
o
rithm. Set the sam
e
threhold
a
=0.4 star image ite
r
ated 85 tim
e
s and flo
w
e
r
image iterate
d
79 times.
Whe
n
iter
atio
n stope
d, get these
conto
u
rs
as n
e
w in
itial contou
rs
and
calle
d gra
p
h
s
cut algorith
m
for segm
enta
t
ion, get the result
s as
sho
w
n in Figu
re
8(e
)
.
The optimi
z
e
d
algorith
m
total co
st time 6.
204 se
co
n
d
s an
d 8.372
second
s respectively.
From Fig
u
re
8(e) we ca
n see that the seg
m
ent
a
t
ion results
are quite
clo
s
e to the ob
ject
boun
dari
e
s,
whi
c
h proved
that
the optimized al
gorit
m is better d
enoi
sing pe
rf
orma
nce than the
firs
t two algorithms
.
(a)Initial Cont
our
(b)se
g
mentati
on
res
u
lt of the
C-V
model alg
o
rit
h
m
(c) se
gment
ation
res
u
lt of
Ref
[10]’s algo
rith
m
(
d
)
pr
e-
p
r
oc
es
s
initial contour of
our alg
o
rithm
(e) segm
enta
t
ion
result of our
algorith
m
Figure 8. Co
mpari
s
o
n
Ch
art of Two No
ised
Imag
es
Segmentatio
n Re
sults by
usin
g Three
Algorithm
s
3.2. Results An
y
l
asis
In orde
r to e
v
aluate the
Experiment
s’
resu
lts, this pape
r we choo
se FO
M(Figure of
Merit) meth
o
d
to anylasi
s the perfo
rma
n
c
e of the
algo
rithms. Th
e d
e
finition of the FOM [12] is:
{}
2
1
11
,1
t
N
i
it
i
FO
M
ma
x
N
N
d
=
=
+a
å
(9)
Whe
r
e
i
N
deno
tes the qualiti
e
s of the ed
ge’s pixe
l
s
from the manu
al segm
entati
ons,
whi
c
h is th
ou
ght as a
stan
dard
re
sult.
t
N
denote
s
the
qualitie
s of the edg
e’s
pixels from the
experim
ent’s
segme
n
tatio
n
.
a
is compe
n
sat
i
o
n
coef
f
i
cient
(u
su
ally
set
1/
9),
i
d
is the nea
re
st
distan
ce b
e
twee
n the poi
nts on the te
sting edge a
n
d
real ed
ge. T
he value of F
O
M is bet
we
en 0
and 1. Th
e value is l
a
rg
er, the effects
of t
he seg
m
e
n
tation is b
e
tter. Use FO
M on ou
r ab
ove
image
s testin
g, get Tabl
e
1. From
Tabl
e 1 we can
see th
at mo
st of the FOM
values
of o
u
r
optimize
d
alg
o
rithm a
r
e l
a
rger th
an FO
M of C-V mo
del an
d Refe
ren
c
e [1
0]’s
algorith
m
, wh
ich
prove
s
that our optimi
z
ed
al
gorith
m
hav
e good p
e
rfo
r
mance.
Evaluation Warning : The document was created with Spire.PDF for Python.
e-ISSN: 2
087-278X
TELKOM
NIKA
Vol. 11, No
. 8, August 2013: 4357 –
4366
4366
Table 1. FOM
Values Com
pari
s
on
with Thre
e Algorit
hms
FOM
(
lung)
FOM
(
liver)
FOM
(
o
w
l)
FOM
(
flo
w
er
)
FOM
(
star)
FOM
(
triangle)
C-V model
algorithm
0.7203
0.6856
0.8801
0.8423
0.3501
0.3834
Ref [10]’s
algorithm
0.7611
0.8345
0.7612
0.6921
0.5023
0.4256
optimized
algorithm
0.8203
0.8342
0.8501
0.8706
0.8801
0.8234
4. Conclusio
n
Based o
n
th
e improve
d
C-V mod
e
l a
nd gra
ph cut algorithm, th
is pap
er p
r
e
s
ented an
optimize
d
ite
r
ation al
gorith
m
for imag
e
segmentat
io
n.
Thi
s
al
gorith
m
comibin
e
s
the adva
n
tag
e
s
of these two
algorithm
s a
nd improve
s
the it
eration
spe
e
d
s
and
segm
entation
accura
cy. The
algorith
m
ma
y solve
som
e
proble
m
s
that the
trad
itional C-V model algo
rit
h
m
ne
ed m
o
re
comp
uting ti
me on
num
e
r
ical
iteratio
n
s
a
nd the
p
r
oblem th
at iteration
termi
nation
con
d
ition i
s
difficult to determin
e
. Simulation re
sult
s indicat
ed that
the pro
p
o
s
ed
algorithm i
s
robu
st and hig
h
effic
i
enc
y
.
Ackn
o
w
l
e
dg
ments
This work is jointly supp
orted by the
National Na
ture Scie
nce
Foundatio
n of China
(No.6
107
419
2), the
Re
search
Fund
of the
Ji
a
ngxi Provin
ce Edu
c
ation
Office
(G
rant
No.G
JJ114
65
) and the Fu
n
d
s of the US
T
B
(No
s
.YJ20
10-0
19, 061
0
8104
).
Referen
ces
[
1
]
M Kass,
A Witkin,
D T
e
rzopo
ulo
u
s.
Snakes:
Act
i
ve cont
o
u
r
models.
I
n
t
e
mat
i
on
al Jo
urn
a
l
of
Co
mput
e
r
Vision.
198
8;
1(4):
321-3
31.
[
2
]
V Casel
les,
R
Kimmel,
G Sap
i
ro.
Geod
esic a
c
t
i
ve cont
o
u
rs.
I
n
t
e
rnat
io
na
l Journ
a
l of
Co
mput
er Visi
on
.
199
7;
22(1):
61
–79.
[
3
]
S Osher,
R F
edki
w
.
Lev
el Se
t
Met
hods an
d
D
y
n
a
mic I
m
pl
i
c
it
Surf
aces.
Springer-Ver
lag
. N
e
w
Y
o
r
k
,
200
2.
[
4
]
Malla
di
R,
S
e
t
h
ian
JA,
Vem
u
ri
BC.
Sh
ap
e m
ode
lin
g
w
i
t
h
f
r
o
n
t
pro
p
a
gat
io
n:
a
lev
e
l s
e
t
a
p
p
r
oach.
IE
EE
T
r
ansact
i
o
n
s o
n
Pat
t
e
rn Ana
l
ysis and Mac
h
i
ne I
n
t
e
ll
ig
ence
.
1995;
1
7
(2):
1
58-1
75.
[
5
]
Cha
n T
F
,
Vese LA.
Act
i
v
e
c
ont
ours
w
i
t
h
ou
t
edg
es.
IEEE
Transactions on Image Proc
essing
.
200
1;
10(2):
26
6-2
7
7
.
[
6
]
Li C,
Xu C,
G
u
i C,
et
al.
Le
vel set
evol
ut
i
on w
i
t
h
o
u
t
re-i
nit
i
al
i
z
a
t
i
on:
a
new
variat
i
o
n
a
l
f
o
r
m
ul
at
io
n
.
Procee
din
g
s o
f
t
he 2005 I
EEE Comput
er
Societ
y
C
onf
erenc
e on Co
mput
er Visio
n
and Pat
t
e
r
n
Reco
gnit
i
on,
S
an Di
ego:
I
E
E
E
Press.
2005;
I
:
1-7.
[
7
]
Y Bo
y
k
ov,
G Funka L
ea.
Gra
ph cut
s
an
d ef
f
i
cient
N-D im
a
ge segm
ent
at
i
on.
I
n
t
e
rnat
i
o
n
a
l Jour
nal
of
Co
mp
ut
er Visi
on
.
200
6;
70(2)
:
109-13
1.
[
8
]
Bo
y
k
ov Y,
Kol
m
ogor
ov V.
An Exp
e
rime
nt
al
Comp
a
riso
n of
Min-Cut
/
M
ax-
F
lo
w
A
l
g
o
rit
h
m
s
f
o
r Energ
y
Minimiz
a
tion in Vision.
I
EEE t
r
ansact
i
ons o
n
pat
t
e
rn an
alys
i
s
and
m
a
ch
in
e int
e
ll
ig
ence
.
2
0
04;
26(9).
[
9
]
F
o
rd LR,
F
u
lk
erson D
R
.
Ma
xim
a
l f
l
o
w
t
h
ro
ugh
a net
w
o
rk
.
Cana
dia
n
Jo
urna
l of
Mat
h
e
m
at
ics
. 19
56
;
8(3):
399-
40
4.
[
10]
Ning
Xu,
Ahu
j
a
N,
Bansal
R.
Object
segm
en
t
a
t
i
on us
ing
gr
aph c
u
t
s
base
d
act
i
ve co
nt
ou
rs.
Comput
e
r
Visio
n
and I
m
a
ge Un
derst
a
ndi
ng
.
200
7;
107(
3):
210-2
24.
[
11]
YANG Jian
gon
g,
WANG Xil
i
.
I
m
age se
gmen
t
a
t
i
on a
ppr
oac
h bas
ed o
n
gr
aph c
u
t
s
an
d
dua
l lev
e
l s
e
t
met
hod.
Co
mp
ut
er Engi
ne
erin
g and Ap
pl
icat
i
ons
.
201
2;
48(
3):
195-1
97.
[
12]
Lan H
ong,
L
i
u
Xi
ant
a
o
.
Energ
y
min
i
mizat
i
on
mode
l
f
o
r imag
e segme
n
t
a
t
i
o
n
via gra
ph cut
opt
imizat
i
on.
Appl
icat
io
n Re
search of
Co
mput
ers
.
201
2;
2
9
(11):
43
81-
43
84.
[
13]
Yuan
hui
Yu,
C
h
inc
hen
Ch
an
g.
A ne
w
e
d
g
e
det
ect
i
on
ap
proac
h b
a
se
d
on im
ag
e co
nt
ext
an
al
ysi
s
.
I
m
ag
e an
d Visi
on Co
mput
in
g
.
200
6;
24:
109
0
-
110
2.
Evaluation Warning : The document was created with Spire.PDF for Python.