TELKOM
NIKA Indonesia
n
Journal of
Electrical En
gineering
Vol.12, No.6, Jun
e
201
4, pp. 4512 ~ 4
5
2
0
DOI: 10.115
9
1
/telkomni
ka.
v
12i6.539
0
4512
Re
cei
v
ed
De
cem
ber 2
5
, 2013; Re
vi
sed
Febr
uary 23,
2014; Accept
ed March 8, 2
014
A New Method of Color Tongue Image Segmentation
Based on Random Walk
Mingfeng Z
h
u
*, Jianqian
g Du
Schoo
l of Com
puter Scie
nce,
Jian
g
x
i Un
ivers
i
t
y
of
T
r
adition
al Chi
nes
e Me
dicin
e
, Nanc
ha
ng 33
00
04, Chi
n
a
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: ohog
od@
ye
a
h
.net
A
b
st
r
a
ct
T
h
is pa
per int
r
oduc
ed a ki
nd
of new
metho
d
for color ton
gue i
m
age s
e
g
m
e
n
tatio
n
by i
m
pr
ovin
g
rand
o
m
w
a
lk
alg
o
rith
m. F
i
rs
tly, w
e
introd
u
c
ed
an
impro
v
ed to
bog
ga
n
alg
o
rith
m w
h
i
c
h a
dopte
d
n
e
w
classification r
u
les
to c
l
a
ssify
a i
m
ag
e into
i
n
itial
re
gi
ons. Secon
d
ly,
w
e
b
u
ilt a
w
e
i
ghte
d
-grap
h
accord
in
g
t
o
initia
l r
egi
ons
i
n
w
h
ich
o
n
ly
those
a
d
jac
ent
reg
i
ons
w
e
re
conn
ected. T
h
i
r
dly, w
e
a
d
o
p
ted r
a
n
d
o
m
w
a
lk
alg
o
rith
m to s
e
g
m
e
n
t i
m
a
g
e
s
by n
e
w
l
y d
e
sig
ned
w
e
ig
h
t
function. F
o
urthly, w
e
us
ed
mat
h
e
m
ati
c
a
l
mor
p
h
o
lo
gy o
p
e
ratio
n
s to re
move s
m
a
ll h
o
le
s on the tar
get
regi
on of th
e
seg
m
e
n
t result
of the third st
ep.
In the
exper
i
m
ent, w
e
co
mp
a
r
ed o
u
r
met
hod
w
i
th traditi
o
n
a
l
rand
o
m
w
a
lk
a
l
gorit
hm. A
n
d
a
s
the ex
per
i
m
e
n
t
results
sh
ow
,
o
u
r meth
od achi
eves basic
ally
ide
a
l effect
s, which
are
much
better tha
n
th
o
s
e of trad
itio
na
l
rand
o
m
w
a
lk ima
ge se
g
m
ent
ation a
l
g
o
rith
m.
Ke
y
w
ords
:
color to
ng
ue i
m
a
ge s
e
g
m
en
tation, tob
ogg
an a
l
g
o
rith
m,
rand
o
m
w
a
lk
alg
o
rith
m, HSI
colo
r
mo
de
l
Copy
right
©
2014 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
Tongu
e diag
nosi
s
is o
n
e
of important
content
s in
four Tradition
al Chin
ese Medici
ne
diagn
oses. T
r
adition
al ton
gue
diagn
osi
s
d
epe
nd
s o
n
the
ob
servations
on t
he featu
r
e
s
of
tongue
s. The
results of to
ngue di
agn
oses a
r
e in
flue
nce
d
not onl
y by both the experie
nce an
d
kno
w
le
dge of
doctors, but also by the e
n
vironm
ents.
Therefore, m
any resea
r
ch
ers utili
zed di
gital
came
ra
s to t
a
ke
photo
s
of tongue
s
and
che
c
k
the to
ngue i
m
age
s
quantitively u
s
ing
co
mpute
r
s.
To
che
c
k to
ngue
imag
es qua
ntitively, we
ne
ed to
se
gment
th
e tong
ue
bo
dy re
gion f
r
om
backg
rou
nd first, i. e. tongue image seg
m
entation.
In Re
cent ye
ars,
ran
dom
wal
k
alg
o
rith
m is an
ari
s
e
n
image
se
g
m
entation al
g
o
rithm. It
utilize
s
weigh
t
values
amo
ng n
ode
s in
weig
hted-gra
ph to m
a
ke
clusteri
ng
of i
m
age
re
gion
s, so
as to
segme
n
t image
s. M
any re
se
arch
ers p
r
op
os
e
d
variou
s
kin
d
s
of tran
smut
ations of ran
dom
wal
k
algo
rith
ms. Yufeng
Yi
et al.
[1] introdu
ce
d a
kind of
ran
d
o
m wal
k
ima
ge segme
n
ta
tion
algorith
m
ba
sed on Me
an
Shift in orde
r to solve
the p
r
oble
m
that the co
ntou
r of
the obje
c
t was
easy to
be
di
sturb
ed
by th
e natu
r
al text
ure
of the b
a
c
kgro
und. M
eng Li
u
et al
.
[2] c
o
mbined
intera
ctive se
gmentation
al
gorithm
with
Kalman f
ilter
to introd
uce random
walk
algorith
m
ba
sed
on Kalman fil
t
er whi
c
h
was used to
sol
v
e shadow
a
nd occlusion
in traffic
video surveillance. Li
Guo
et al.
[3-4] introd
uce
d
a tobogga
n
base
d
ran
d
o
m
walk ima
g
e
segm
entati
on algo
rithm. L
i
Guo
et al.
[
5
] introd
uced
a meth
od
o
f
accurate v
ehicl
e d
e
tecti
on in
multi-v
ehicl
e video
b
y
rand
om walk algorithm b
a
se
d on ed
g
e
detectio
n
. Zhaoyu Pian
et al.
[6] propo
sed a n
o
v
el
approa
ch for
image segm
e
n
tation by ap
plying
stru
ctu
r
e ten
s
or to random
wal
k
. Yihua Lan
et al.
[7] propo
sed
a novel image se
gmenta
t
ion method
based on ra
ndom walk
model which
can
overcome th
e disadvanta
ge for
se
gme
n
ting the la
rg
e scale i
m
ag
e whil
e sele
cting initial val
ue
rand
omly. Ri
chard
Rze
s
zut
e
k
et al.
[8] p
r
opo
se
d a
n
e
x
tension
to
ra
ndom
wal
k
al
gorithm
with
o
u
t
signifi
cantly modifying the
original al
gorithm.
In the form
er re
sea
r
che
s
, there
we
re 2
method
s
whi
c
h mi
ght be
mentione
d a
nd could
be u
s
ed to
segm
ent
color ton
gue
image
s an
d und
er
so
me ci
rcumst
ances th
ey coul
d
su
ccessfully
segm
ent ton
gue im
age
s.
One m
e
t
hod
wa
s
HSI-ba
sed
thre
sh
ol
d metho
d
, which
wa
s intro
d
u
c
ed by Zh
ong
xu Zhao
et al
.
[9]. This me
thod tra
n
site
d RGB
col
o
r
model of
orig
inal
tongue im
age
s into
HSI col
o
r mo
del a
n
d
utilized
hue
histog
ram to
segm
ent tong
ue imag
es. T
h
e
other on
e wa
s HSI-b
a
sed
transfixation
met
hod, which wa
s intro
d
u
ce
d by Jian
qiang
Du
et al.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
A New Meth
o
d
of Color T
o
ngue Im
age Segm
entati
on Based o
n
Random
Wal
k
(Mingfe
ng Zh
u)
4513
[10]. This m
e
thod utili
zed
hue value
o
f
tongue ima
ges
as th
e key segm
enta
t
ion factor
a
nd
combi
ned
HS
I color mo
del
with tran
sfixation algo
rithm
in orde
r to se
gment tongu
e
images.
In the proble
m
of color to
ngue ima
ge segm
entation
,
becau
se th
e intensity of tongue
regio
n
may b
e
sam
e
as a
d
j
ace
n
t regio
n
s
, su
ch a
s
m
outh re
gion a
nd face
regi
o
n
, so we ca
n not
use
inten
s
ity
to build
weig
ht functio
n
a
nd
seg
m
ent t
ongu
e ima
g
e
s
. Herein,
we
intro
d
u
c
ed
b
o
th
hue a
nd i
n
te
nsity to buil
d
a comp
ound
weig
ht fun
c
tion, whi
c
h
co
nforme
d to t
he p
r
in
ciple
s
of
human visi
on
of color. In a
ddition, traditi
onal ra
ndo
m wal
k
algo
rith
m doesn’t fully take advant
age
of spatial information to
segment
im
ages. In thi
s
paper,
we fully
utilize spatial
i
n
formation
and
before
u
s
ing
rand
om
wal
k
algo
rithm to
make
final
se
gmentation
we build
a
wei
ghted-graph i
n
whi
c
h o
n
ly th
ose
adja
c
e
n
t
regio
n
s are
conne
cted. T
h
erefo
r
e,
o
u
r a
l
gorithm
i
s
m
o
re pra
c
ti
cal an
d
can achi
eve much
better
segm
entation effects. Fr
om now on, we will disc
uss the principles of
our meth
od which
we sugg
est to make color tong
ue i
m
age segm
e
n
tation.
2. HSI Color Model
Traditio
nally, a pixel is
rep
r
ese
n
ted by re
d, gree
n an
d
blue 3
kind
s
of colo
rs.
RG
B colo
r
model is u
s
u
a
lly used to repre
s
e
n
t a static image.
B
u
t in HSI colo
r model a pix
e
l is tran
sformed
into hue, saturation
and i
n
tensity 3 ki
n
d
s of color
compon
ents.
Hue i
s
u
s
ed
to determin
e
the
type of the color. Saturatio
n
is the degre
e
to whic
h a
certai
n col
o
r i
s
mixed into the other
colo
rs.
And inten
s
ity is the d
egree
of t
he bri
ght
ness of a
pixel. The
HSI color m
odel i
s
sho
w
n
as
Fig
u
re
1.
(a)
(b)
Figure 1. HSI Color M
odel
(a)
HSI 3-dim
ensi
on colo
r
spa
c
e, (b
) cro
s
s-sectio
n of HSI colo
r sp
a
c
e
As Figu
re 1(a) shows, a
n
y color
ca
n
be denote
d
as the colo
r point p in
HSI 3-
dimen
s
ion
a
l
colo
r spa
c
e. In HSI 3-dime
nsio
nal
colo
r
spa
c
e, h
ue
compon
ent is
denote
d
a
s
the
angle
betwe
e
n
vector
p an
d red
axis, sa
turation
com
p
onent i
s
den
o
t
ed as th
e len
g
th of vector
p,
and inten
s
ity comp
one
nt can be mea
s
u
r
ed by a dire
ct line throu
g
h
the cente
r
of the triangl
es.
As Fig
u
re
1
(
b)
sho
w
s, 0
-
degree
re
pre
s
ent
s
red,
12
0-de
gree
rep
r
esents g
r
ee
n an
d 2
40-de
gree
rep
r
e
s
ent
s bl
ue.
Relative to
RGB color mo
del, HSI
colo
r model
is mo
re
clo
s
e
r
to
h
u
man vi
sion
of col
o
r.
And a
s
the
forme
r
wo
rk
h
a
s
prove
d
th
at usi
ng
HSI
colo
r m
odel t
o
identify ton
gue
regi
on a
nd
segm
ent tong
ue image i
s
feasi
b
le.
3. The Principle of Image Segmenta
tio
n
Base
d on HSI Color M
odel
Some traditio
nal ima
ge
se
gmentation
m
e
thod
s u
s
e
g
r
ayscale
to
segment
imag
es.
Due
to grayscale
value of a pixel is a com
b
inati
on of re
d, green a
n
d
blue com
p
o
nents, it can
only
reflect
the b
r
i
ghtne
sss
of i
m
age
s. Altho
ugh
gray
scal
e information
of a ima
ge i
s
enou
gh fo
r m
any
Red
Blu
e
Gree
n
H
Wh
ite
Black
I
p
H
Red
Gree
n
Blu
e
p
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 6, June 20
14: 4512 – 4
520
4514
appli
c
ation
s
o
f
image segm
entation
s
. But in the
appli
c
ation of col
o
r
tongue im
age
segm
entatio
n,
using grayscale to
segment tongue
region from th
e background regi
ons, such as
teeth, mouth
and face regi
ons, is ve
ry difficult.
Figure 2. Gra
y
scal
e
Tong
u
e
Image
Figure 3. Hist
ogra
m
of Gra
y
scal
e
Tong
u
e
Image
As Figu
re 2
shows, the g
r
a
y
scal
e
value
s
of tongue re
gion an
d tho
s
e of face
regi
on are
quite clo
s
e
a
nd simil
a
r. As Figure
3 sho
w
s, the
m
a
in
pea
k of the hi
stogram
of g
r
ayscale tong
ue
image i
s
o
n
ly one. And
thi
s
pe
ak re
presents b
o
th
the
tongue
re
gio
n
and
face re
gion. Th
erefo
r
e,
we can not
disting
u
ish the tongue reg
i
on and fa
ce
region o
n
ly by grayscale
information
of
tongue ima
g
e
s
.
In HSI colo
r
model, hu
e compon
ent ca
n be u
s
e
d
to i
dentify the co
lor type of a
p
i
xel. And
the
main
colo
r
type of
tong
ue regio
n
i
s
red whi
c
h
i
s
b
a
si
cally different from
tho
s
e of teeth
reg
i
on
and face regi
on. Even if
the main colo
r type of
tongue regio
n
and that of mouth region is
clo
s
e,
the spatial p
o
s
ition
s
of tongue re
gion a
n
d
mouth re
gio
n
are differen
t. Therefore, utilizing the h
ue
informatio
n a
nd spatial inf
o
rmatio
n of color
ton
gue i
m
age
s to se
gment tong
u
e
image
s m
a
y be
feasibl
e
.
Whe
n
identif
ying the hue
value of tongue
region, t
he hue valu
e
of tongue region i
s
usu
a
lly red. The red
colo
r is 0-deg
re
e or 360
-de
g
re
e in hue hist
ogra
m
. If we
only use the hue
values to di
stinguish the
colo
r of to
ng
ue regi
o
n
, th
is may l
ead
to an in
co
rre
c
t segme
n
tation
result.
Figure 4. Hue
Image of Tongue
Figure
5. Hue
Histog
ram of
Tongue Ima
g
e
As Figu
re
4
sho
w
s, there
are
not only
hi
gh h
ue val
ue poi
nts b
u
t also l
o
w
hu
e value
points on th
e
tongu
e regio
n
. As Fi
gure
5 sho
w
s, h
u
e
value
s
of to
ngue
whi
c
h
i
s
red li
es at the
start po
sition
s and th
e e
nd po
sition
s of hue hi
sto
g
ram of the
tongue im
ag
e. And the start
positio
ns
of h
ue rep
r
esent
the tong
ue pi
xels
wi
th lo
w hue val
u
e
s
and th
e en
d
positio
ns
of h
ue
rep
r
e
s
ent the
tongue pixel
s
with hig
h
h
ue value
s
. In orde
r to let those pixels
with both low a
nd
high
hue val
ues gath
e
r
a
t
one
pea
k i
n
the
hue
hi
stogram
of the ton
gue
im
age,
we
nee
d to
transfo
rm the
range
of hue
in the hue im
age of tong
u
e
.
Concretely, if the range of
hue is from
0-
degree to
3
6
0
-de
g
ree,
we
move th
ose
hue val
u
e
s
from 0
-
de
gre
e
to 180
-de
g
re
e to the
en
d.
And
we subtra
ct 1
80-d
e
g
r
ee fro
m
all the hue values.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
A New Meth
o
d
of Color T
o
ngue Im
age Segm
entati
on Based o
n
Random
Wal
k
(Mingfe
ng Zh
u)
4515
Figure 6. Hue
Image after Tran
sfo
r
mati
on
Figu
re 7. Hue
Histog
ram af
ter Tra
n
sfo
r
m
a
tion
As Figu
re 6
sho
w
s, after
the tran
sform
a
tion as m
e
n
t
ioned befo
r
e
,
the tongue
pixels
gathers in th
e con
n
e
c
tive regio
n
and th
e tongue an
d
the mouth lie in the 2 diffe
rent re
gion
s. As
Figure 7
sh
o
w
s, th
e h
ue
histog
ram
of
the tong
ue i
m
age
after th
e tranfo
r
mati
on p
r
e
s
ent
s
a 2-
pea
k di
stribut
ion, the featu
r
e of
which can be
used t
o
se
parate th
e foreg
r
o
und
part fro
m
th
e
backg
rou
nd p
a
rt.
4. Random
Walk Image
Segmenta
tio
n
Algorithm
Ran
dom wal
k
algo
rithm is a kind of semi
-autom
atic image seg
m
entation al
gorithm,
whi
c
h
i
s
successfully applied
in
the fi
eld of im
age segmentat
ion. It utilizes
the probability
betwe
en
any
2 pixel
s
t
o
segment
imag
e. The
ra
ndo
m walk alg
o
ri
thm is mainly
divided
into
3
step
s. Firstly, cho
o
se se
g
m
entation m
a
rk
point
s. Seco
ndly, buil
d
co
nne
ction
weight fun
c
t
i
on.
Thirdly,
reali
z
e segm
entati
on by
solving transfer probabilities.
No
w, let’s
discuss this algorithm
in detail.
Firstly, we n
eed to
defin
e a
discrete
wei
ghted
-graph
G for th
e ori
g
inal
im
age. Th
e
weig
hted-gra
ph ca
n be d
enoted a
s
G
=
(V,
E), whi
c
h is com
p
o
s
ed of vertex
V
v
and edg
e
E
e
. Herein, V is
a set whi
c
h i
s
comp
osed of
finite elemen
ts of vertex v
i
and E is a set which
is co
mpo
s
e
d
of finite elements of ed
ge
e
i
. The pixels
in the origi
nal
image a
r
e d
enoted a
s
n
o
des
in weig
hted
-g
raph
and th
e
relation
shi
p
betwe
en 2 pi
xels is d
enot
ed a
s
an e
d
ge. Additiona
lly,
there i
s
a
co
nne
ction
wei
ght W
ij
o
n
e
a
ch
edg
e, which i
s
u
s
e
d
to de
scribe
the co
nne
ctivity
betwe
en 2 n
ode
s. Duri
ng
image seg
m
entation, we
ights of ed
ges a
r
e use
d
to describ
e the
differen
c
e o
r
simila
rity among adja
c
e
n
t pixels. The wei
g
ht function
can be de
note
d
as follo
wing
:
2
)
(
j
i
I
I
ij
e
W
(
1
)
Her
e
in, I
i
and
I
j
are the
i
n
tensitie
s
of
pixel i a
n
d
pi
xel j re
sp
ecti
vely and
is a
s
c
a
l
e
para
m
eter
which i
s
la
rge
r
than 0. Whe
n
takin
g
the
spatial i
n
form
ation into
co
nsid
eratio
n, the
weig
ht functio
n
can al
so b
e
denoted a
s
followin
g
:
2
2
)
(
)
(
j
i
j
i
h
h
I
I
ij
e
W
(
2
)
Her
e
in, h
i
is the po
sition of
the pixel i.
Ran
dom walk algorithm i
s
a kind of inte
ra
ctive ima
g
e
segm
entatio
n algorith
m
. After the
weig
hted-gra
ph is built, we need to
sp
ecify the s
e
e
d
s for o
b
je
ct regio
n
and
b
a
ckgroun
d re
gion.
These
see
d
s provid
e the
bases for
cla
ssifi
cation
of
unma
r
ked p
o
i
nts. After ma
nual m
a
rking
of
the seed
s, th
e no
de
s in
th
e weighte
d
-g
raph
are
di
vid
ed into
multip
le sub
s
ets.
L
e
t marke
d
n
o
des
be the
see
d
s,
the set of
which i
s
de
not
ed a
s
M. And
unma
r
ked n
ode
s are de
n
o
ted a
s
a
set
N
.
Her
e
in,
V
N
M
and
f
N
M
. Then d
e
co
mpose ma
rked poi
nt set
M to get obj
ect
see
d
s
M
O
and backg
rou
nd see
d
s
M
B
. Herein,
M
B
O
and
f
B
O
.
Therefore th
e con
nectio
n
relation
ship
betwe
en 2
n
ode
s repl
ace
d
the relatio
n
shi
p
betwe
e
n
2
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 6, June 20
14: 4512 – 4
520
4516
pixels. An
d t
he p
r
o
b
lem
of imag
e
seg
m
entatio
n
tra
n
sforms into
the p
r
obl
em
how un
marked
node
s first re
ach maxim
a
l prob
ability of the see
d
s.
Due to
the
sele
ction
of i
n
itial se
ed
s i
s
ma
nual. T
h
is m
a
y be
inco
nvenient
for the
appli
c
ation of
tongue ima
g
e
seg
m
entati
on. And the
spatial info
rm
ation in the i
m
age i
s
not fully
utilized. Mo
st
of all, the effects
of tongu
e
image
seg
m
entation m
a
y not be o
k
a
y
, when utili
zi
ng
traditional
ra
ndom
wal
k
a
l
gorithm. Ba
sed on th
e co
nsid
eratio
ns
above, we sugge
st a
kin
d
of
improve
d
ran
dom walk im
age segme
n
tation algo
ri
th
m, in which the se
ed
s are sele
cted fu
lly
automatic and the spatial
inform
ation
is al
so
fully
utilized.
Now, let’s
discuss the improv
ed
rand
om walk
image segm
e
n
tation algo
rithm in detail.
5. Impro
v
ed
Rand
om Wal
k
Image Segmenta
tion Al
gorithm
The imp
r
ove
d
ra
ndom
walk im
age
se
gmentatio
n
a
l
gorithm i
s
compo
s
ed
of
4 ste
p
s.
Firstly, impro
v
ed tobogg
a
n
algorith
m
is appli
ed
to get initial reg
i
ons. Se
cond
ly, the weighted-
grap
h i
s
built
according
to t
he initial
regi
ons.
Thirdly,
apply
rand
om
wal
k
algo
rith
m to m
a
ke fin
a
l
segm
entation
usin
g n
e
wly-built wei
ght f
unctio
n
.
Fou
r
thly, mathem
atical m
o
rp
ho
logy ope
ratio
n
s,
i. e. inflations and ero
s
ion
s
are ca
rrie
d
o
u
t on the
seg
m
entation re
sult of the thir
d step, so a
s
to
fill small holes on the tongue regi
on.
5.1. Tobogg
an Algorith
m
In 1990, Fairfield introdu
ced tobog
gan
algor
ithm to
be applied i
n
the field of image
segm
entation
.
Its basi
c
thi
n
kin
g
is th
at
we
can
sp
eci
f
y the movement directio
ns by fin
d
ing
the
minimal g
r
ad
s in th
e nei
g
hbou
rho
o
d
s
of the pixel
s
and divid
e
th
ose
pixels
wi
th minimal
grads
into one gro
up, so a
s
to segme
n
t image
s. Be
cau
s
e grayscale
information
(i. e. intensity
informatio
n) i
s
n
o
t eno
ugh
for the
se
gm
entation
of
to
ngue
i
m
ag
e,
so we will utilize both
h
ue a
nd
intensity to
d
e
scrib
e
the
di
fferences b
e
twee
n
2
pixel
s
. The i
m
proved tob
ogg
an
algorith
m
can
be
descri
bed a
s
followin
g
.
Step 1: Scan origin
al imag
e to find a se
ed whi
c
h i
s
a non-ze
ro pixe
l.
Step 2: Add
the se
ed pix
e
l to obje
c
t region,
p
u
sh the seed
pixe
l into the sta
ck
and
remove the
seed pixel fro
m
the origin
al
image.
Step 3: Repe
at following
step 4 and
st
ep
5 until the stack is empty.
Step 4: Pop up a see
d
pixe
l from stack.
Step 5: Co
nsi
derin
g the
nei
ghbo
urh
ood
s of the s
eed
pixel, if the di
fferences of i
n
tensity
and hu
e bet
wee
n
the se
ed pixel and
the neigh
b
ourh
ood
pixel are lo
we
r than a certa
i
n
threshold
s
,
we ad
d the
nei
ghbo
urh
ood
pixel to o
b
je
ct regio
n
, pu
sh
the n
e
igh
bou
rhoo
d pixel
in
to
the stack an
d
remove the n
e
ighb
ourho
o
d
pixel from the origin
al ima
ge.
Step 6: Repe
at step 1 to step 5 until there are
no n
o
n
-
zero pixels in
the origin
al image.
5.2. Cons
tru
c
tion of
Wei
ghted
-Gr
a
ph
After original
image is se
gmented into
initia
l region
s, we ca
n co
nstru
c
t the weighted
-
grap
h a
c
co
rdi
ng to th
e initi
a
l re
gion
s. T
h
e weight fu
nction is no
mo
re compo
s
e
d
of inten
s
ity, but
the com
b
inati
on of inten
s
ity and hue,
which
confo
r
m
s
to the pri
n
ci
ples of h
u
ma
n vision of
co
lor.
The wei
ght function i
s
defin
ed as follo
win
g
:
360
|
|
1
255
|
|
1
j
i
j
i
ij
H
H
I
I
W
(
3
)
Her
e
in,
an
d
are
weig
ht coefficie
n
ts,
]
1
,
0
[
,
]
1
,
0
[
,
1
, I
i
and
I
j
are
intensity valu
es of pixel i and pixel j, and H
i
and
H
j
are hue value
s
of pixel i and pixel j.
In the construction of wei
ghted-graph, to fu
lly utilize the spatial informatio
n of images,
we
only p
e
rmit those
init
ial re
gion
s
which
are
a
d
ja
cent to
ea
ch
other a
r
e
conne
cted
wit
h
a
certai
n weigh
t
value. This
rule i
s
mo
re
pra
c
tica
l t
han
that of traditi
onal rand
om
wal
k
alg
o
rith
m,
whi
c
h
ca
n tra
n
sform the
weighted
-g
rap
h
into
a
sp
a
r
se net
work,
ca
n redu
ce t
he
work of rand
om
wal
k
, an
d ca
n a
c
hieve
mu
ch
better
se
g
m
entation
effects. Ju
st
b
e
c
au
se
the we
ighted-graph is
a
spa
r
se netwo
rk, we ado
pt adja
c
en
cy list
to
denote th
e weig
hted-g
r
aph,
which can re
duce the
spa
c
e of the
data structu
r
e. The algo
rithm to
con
s
tru
c
t the weig
hted-g
r
a
ph can
be described
as
following.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
A New Meth
o
d
of Color T
o
ngue Im
age Segm
entati
on Based o
n
Random
Wal
k
(Mingfe
ng Zh
u)
4517
Step 1: Cre
a
te an array of
head
s of lin
ked li
sts, ea
ch eleme
n
t of
whi
c
h represents an
initial region.
Step 2: If region a and regi
on b are n
e
ig
hbou
rho
o
d
s
, run follo
wing
step 3 to step
7.
Step 3: Creat
e a new e
dge
node which is from region
a to region b.
Step 4: Set th
e identifier of the new e
dge
node to b.
Step 5: Cal
c
ulate the
wei
ght between
regio
n
a a
n
d
regio
n
b a
ccordin
g to formula (3),
set the wei
g
h
t
value of the
new e
dge n
o
de and
se
t the su
ccesso
r of the new ed
ge nod
e to nu
ll.
Step 6: Link the ne
w edg
e node to the ta
il of linked list
of region a.
Step 7: Do th
e sa
me a
s
from ste
p
3 to
step 6
to cre
a
te a ne
w
ed
ge no
de from
regi
on b
to region a.
5.3. Automa
tic Selection of the Initial
Seed
To apply ran
dom walk
alg
o
rithm to ton
gue ima
ge
se
gmentation,
we first nee
d
to spe
c
ify
the initial
se
e
d
whe
r
e th
e
segmentatio
n
start
s
. Here
,
we
su
gge
st a
kin
d
of
auto
m
atic
sel
e
ctio
n of
the seed. Ge
nerally spea
king, the
tongu
e regio
n
usu
a
lly lies in the
middle of the origin
al imag
e.
Therefore,
we take
the m
a
ximal re
gion
as th
e
seed
in whi
c
h
the
avera
ge of t
he di
stan
ce
s of
pixels is
clo
s
est to the cen
t
er of the origi
nal image.
5.4. Descrip
tion of Ran
d
o
m
Walk Algo
rithm
Whe
n
wei
g
h
t
ed-g
r
ap
h is built, we can a
pply random
wal
k
algorithm t
o
fina
l
segm
entation
.
The basi
c
thinkin
g
of rand
om wal
k
algo
rithm is to ma
ke cl
uste
ring
of region
s wit
h
simila
r
featu
r
es or sm
all differen
c
e
s
a
nd
the
features and
differences
are d
e
scrib
ed
by the
weig
ht values among
regi
o
n
s n
ode
s. Th
at is to
say, if the weig
ht value bet
wee
n
2 regi
on no
d
e
s
are
small
e
r th
an a
certai
n thre
shol
d, we
can
expand t
he targ
et re
gi
on from th
e o
ne re
gion to t
he
other on
e. Th
e descri
p
tion
of rando
m wa
lk algo
rithm is sho
w
n a
s
followin
g
.
Step 1: Find
the initial seed in the
o
r
iginal im
age
using th
e
method d
e
scribed i
n
previou
s
secti
on.
Step 2: Initialize the elem
e
n
ts
of vis
i
t array to all fals
e.
Step 3: If current see
d
is n
o
t visi
ted, con
t
inue the follo
wing
step
s.
Step 4: Set th
e visit tag of current se
ed to true.
Step 5: Reco
rd curre
n
t see
d
regio
n
and
add this
see
d
region to target regio
n
.
Step 6: For
a
ll adja
c
ent n
o
des
of cu
rren
t s
eed, if the
weig
ht betwe
en current
se
ed an
d
adja
c
ent no
d
e
is sm
aller t
han a certain
thres
hold, ex
ecute
step 3 to step 6 recu
rsively.
6. Experiment Re
sults a
nd Analy
ses
In the experi
m
ent, we uti
lize Visual C++
to im
ple
m
ent ou
r im
proved
ran
d
om wal
k
algorith
m
me
ntioned
abov
e and th
e tra
d
itional rand
o
m
wal
k
alg
o
ri
thm. And we
utilize b
o
th o
u
r
improve
d
ra
n
dom walk
alg
o
rithm
whi
c
h
contai
ns
4 st
eps
and t
r
adi
tional ra
ndo
m
wal
k
alg
o
rith
m
whi
c
h ta
ke
s intensity a
s
main
seg
m
entation fa
ctor to
seg
m
e
n
t the tong
u
e
imag
es. T
h
e
experim
ent d
a
ta are
five typical to
ngu
e i
m
age
s the
co
lors
of whi
c
h
are lig
ht re
d, light white, re
d,
deep red an
d purpl
e red
respe
c
tively.
The col
o
rs of these five tongue ima
g
e
s
include all t
he
typical types
of tongue
s. S
o
the
results
of the expe
ri
ment can b
e
persua
s
ive. T
he results of t
h
e
experim
ent are sho
w
n a
s
F
i
gure 8.
As we can
see from
the
result
s of ton
gue
im
age segmentatio
n,
our metho
d
achi
eves
basi
c
ally idea
l segme
n
tatio
n
effects in the 5
segm
enta
t
ion tests. Th
e edge
s of ou
r seg
m
entatio
n
result image
s basi
c
ally co
nform to the edge
s of
the tongue
s. Nev
e
rthele
s
s, tra
d
itional ra
ndo
m
wal
k
algo
rith
m make
s a m
e
ss. As the Fi
gure
8(d
)
an
d
Figure 8
(
h
)
show, the
seg
m
entation result
image
s of lig
ht red tong
u
e
and lig
ht white tong
ue
are
smalle
r than the a
c
tual size of the
tongue
s. Th
e
s
e
re
sults o
w
e m
u
ch to
that the tra
d
i
t
ional meth
o
d
takes only
inten
s
ity as the
segm
entation
facto
r
. As th
e Fig
u
re
8
(
l)
sho
w
s,
the
segmentatio
n
result ima
ge
of re
d ton
gue
is
quite wron
g, whi
c
h
conta
i
ns n
on-to
ng
ue pa
rts of t
he imag
e, such
as m
out
h and fa
ce.
The
rea
s
on
why the se
gmentat
ion re
sult ima
ge co
ntai
n
s
n
on-ton
gue p
a
r
ts may be th
at the intensity
of the tongue
and that of mouth an
d face a
r
e quite
similar. And a
s
the Figure
8(t) sho
w
s, even if
we a
pply mat
hematical mo
rphol
ogy op
e
r
ation
s
to the
target ima
g
e
,
the big h
o
llo
w in the
tong
ue
region i
s
still
difficult to fill in. The
cause of th
is result may be that the intensity values in the
cente
r
of the purpl
e re
d tongue a
r
e quit
e
diffe
rent fro
m
the surrou
nding
s of the tongue.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 6, June 20
14: 4512 – 4
520
4518
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)
(k
)
(l)
(m)
(n)
(o)
(p)
(
q
)
(
r)
(
s
)
(
t
)
Figure 8. Re
sults of Tongu
e Image Seg
m
entation
(a) light red tong
ue, (b) lig
ht red tongu
e
manual
seg
m
entation re
sul
t, (c) light re
d tongue
segm
entation re
sul
t
by our method, (d) lig
ht red
tongue
segm
entation re
sul
t
by traditional method,
(e) l
i
ght white ton
gue, (f) light
white tong
ue
manual
seg
m
entation re
sul
t, (g) light whi
t
e tongue
seg
m
entation result by our method, (h
) light
white tong
ue
segm
entation
result by trad
itional
metho
d
, (i) re
d tong
ue, (j) red ton
gue man
ual
segm
entation
result, (k) re
d tongue
seg
m
entat
ion result by our method, (l)
red to
ngue
segm
entation
result by trad
itional metho
d
, (m) de
ep red tongu
e, (n
) deep
red to
ngue ma
nual
segm
entation
result, (o
) de
ep red ton
g
u
e
segm
entati
on re
sult by our metho
d
, (p
) deep
red
tongue
segm
entation re
sul
t
by traditional method,
(q)
purpl
e re
d tongue, (r) pu
rp
le red tong
ue
manual
seg
m
entation re
sul
t, (s) pu
rple red tongu
e
se
gmentation
re
sult by our m
e
thod, (t) pu
rple
red tong
ue se
gmentation
re
sult by traditional metho
d
.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
A New Meth
o
d
of Color T
o
ngue Im
age Segm
entati
on Based o
n
Random
Wal
k
(Mingfe
ng Zh
u)
4519
To evaluate the effects of
the results of
both our im
proved
ran
d
o
m
walk m
e
th
od and
traditional
ra
ndom walk
method obj
e
c
tively and q
uantitively.
We intro
d
u
c
e
s
2 mea
s
u
r
e
m
ent
values. On
e is re
cog
n
ition
rate and the
other is e
r
ror
rate. The re
cognition rate
and erro
r rate
can be d
enot
e as follo
wing
:
FN
TP
TP
(
4
)
TP
FP
FP
(
5
)
Herein, TP is the number
of pixels whi
c
h ar
e co
rrectl
y recog
n
ized as tongu
e pixels, FN
is the
nu
mbe
r
of pixel
s
whi
c
h
are
tong
u
e
pixel
s
b
u
t i
n
co
rrectly recogni
zed
a
s
b
a
ckgroun
d pi
xels
and FP i
s
the
numbe
r of pi
xels which are ba
ckgro
und
pixels b
u
t incorrectly reco
g
n
ize
d
a
s
on
g
u
e
pixels. The re
cog
n
ition rate
s and e
r
ror ra
tes of
image
segm
entation
tests are sh
o
w
n a
s
Table
1.
Table 1. The
Re
cog
n
ition
Rate
s and Error
Rate
s of Image Segm
e
n
tation Test
s
Light red
tongue
Light white
tongue
Red
tongue
Deep red
tongue
Purpl
e
red
tongue
Our m
e
thod
Recognition
rate
s
96.98%
99.90%
94.68%
87.45%
95.89%
Error
rates
0.99%
2.98%
0.29%
1.21%
0.86%
Traditional
method
Recognition
rate
s
87.98%
80.19%
99.99%
87.45%
82.28%
Error
rates
0.03%
0.24%
28.80%
1.23%
0.03%
As Tabl
e 1
shows, mo
st o
f
the recognit
i
on rate
s of o
u
r meth
od a
r
e much hig
h
e
r than
those
of tradi
tional meth
od
and
the
erro
r rates of
our metho
d
a
r
e
quite lo
w.
When it
co
me
s to
red ton
gue
se
gmentation te
st, althoug
h the re
co
gnitio
n
rate
of tradi
tional metho
d
is a little hig
h
e
r
than that of o
u
r metho
d
, the error
rate o
f
the tr
adition
al method i
s
much l
a
rg
er t
han that of o
u
r
method. T
h
e
r
efore, th
e
se
gmentation
ef
fects
of
ou
r m
e
thod
are
mo
re
accu
rate t
han th
ose of t
he
traditional m
e
thod.
7. Conclusio
n
In this paper,
an improved
random
wal
k
algorithm for color tong
ue
image seg
m
entation
is intro
d
u
c
ed.
The imp
r
ove
d
algo
rithm
contain
s
4
ste
p
s to
seg
m
en
t tongue im
ag
es. We ad
opt
a
kind of impro
v
ed tobogga
n algorithm t
o
make init
ial
segme
n
tatio
n
and produ
ce initial regio
n
s.
Then
we con
s
tru
c
t a wei
g
hted-g
r
a
ph where
only those a
d
ja
cent
regio
n
s a
r
e
con
n
e
c
ted wi
th
weig
hts. Fu
rther m
o
re, a
method fo
r a
u
tomatic
sele
ction of the i
n
itial se
ed is
prop
osed. In
the
end, we
ado
p
t
random
wal
k
algo
rithm to
make
final
segmentatio
n
of tongue ima
ge ba
sed
on the
comp
oun
d weight functio
n
of intensity and hue.
In the experim
ent, we utilize our imp
r
ov
ed
algorith
m
an
d tradition
al algorithm t
o
pro
c
e
s
s 5
typical kind
s of tongu
e
image
s. As the
experim
ent result
s sho
w
, our
method
achi
eves
ba
sically ideal
segm
entation
re
sults, b
u
t
the
traditional m
e
thod makes a
mess.
Ackn
o
w
l
e
dg
ement
This p
ape
r is sup
porte
d b
y
the Natural Scien
c
e Fu
n
d
of Jian
gxi Province of China (No.
20114BAB201030) and th
e Youth Science F
und
of
Education Department of
Ji
angxi Province of
Chin
a (No. GJJ125
39). We are g
r
ateful
for their su
pp
orts.
Referen
ces
[1]
Yi YF
, Gao LQ, Guo L. Mean
Shift Based
Ra
ndom
W
a
lk
er Interactive Ima
ge Se
gment
ati
on Al
gorithm
.
Journ
a
l of Co
mputer-Ai
ded D
e
sign & Co
mput
er Graphics
. 2
011; 23(
11): 18
75-1
880.
[2]
Liu M, W
u
CD, W
ang L, Chu H. Method for S
had
o
w
an
d Occlusio
n Base
d
on the Improved Ra
ndo
m
W
a
lk Algorit
hm
.
Journal of Co
mp
uter-Ai
ded
De
sig
n
& Co
mputer Graph
ics
. 2010; 22(
1): 60-65.
Ton
g
ue
Metho
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 6, June 20
14: 4512 – 4
520
4520
[3]
Guo L, Ga
o L
Q, Pian Z
Y
. A
T
obogga
n B
a
sed R
a
n
dom
W
a
lk Alg
o
rith
m for Image
Segme
n
tatio
n
.
Journ
a
l of Co
mputer-Ai
ded D
e
sign & Co
mput
er Graphics
. 2
009; 21(
8): 115
0-11
54.
[4]
Guo L, Li QS, Chen J.
A Ne
w
F
a
st Rando
m W
a
lk Se
g
m
entatio
n Alg
o
rit
h
m
. Proc
ee
din
g
s of Seco
nd
Internatio
na
l S
y
mp
osi
u
m on
Intelli
ge
nt Infor
m
ati
on T
e
chn
o
l
og
y A
p
p
licati
o
n. Sha
ngh
ai. 2
008;
2: 69
3-
697.
[5]
Guo L, Gao LQ, Liu M, Pian Z
Y
. A Ne
w
A
u
tomati
c Multi
p
le Ve
hicl
e De
tection Alg
o
rith
m Based
o
n
Ran
dom Walk.
Journa
l of Ima
ge an
d Graph
i
c
s
. 2010; 15(
3)
: 392-39
6.
[6]
Pian Z
Y
, Lu PP, W
u
LX, Z
hang H
. A New
Ima
ge Se
g
m
e
n
t
ation Appr
oac
h w
i
th Structure T
ensor an
d
R
a
nd
om
Wal
k
.
Proce
edi
ngs
o
f
Secon
d
Inter
n
ation
a
l S
y
m
p
o
s
ium o
n
Inte
lli
g
ent Informati
on
T
e
chnolo
g
y
Appl
icatio
n. Sh
ang
hai. 2
008;
2: 432-4
36.
[7]
Lan YH, Z
h
a
n
g
Y, Li CH, Z
h
ao
XF
.
A Nove
l Ima
ge Se
g
m
entatio
n Metho
d
Base
d on R
and
o
m
W
a
lk
.
Procee
din
g
s
of Secon
d
A
s
ia-Pacific
Co
nferenc
e o
n
Comp
utation
a
l
Intelli
ge
nce
and In
dustri
a
l
Appl
icatio
ns. W
uhan. 20
09;
1: 207-2
10.
[8] Rzeszutek
R,
El-Mara
g
h
i T
,
Andro
u
tsos D.
Imag
e Seg
m
e
n
tation Us
in
g Scale-s
pace R
and
o
m
W
a
lks
.
Procee
din
g
s of
Internation
a
l C
onfere
n
ce o
n
Digita
l
Sig
nal P
r
ocessi
ng. San
t
orini-H
e
ll
as. 2
009: 1-4.
[9]
Z
hao Z
X
, W
a
ng MA, She
n
LS. T
he Color
T
ongue Imag
e Segm
entati
o
n Ba
se
d on
Mathematic
al
Morph
o
lo
g
y
an
d HSI Model.
J
ourn
a
l of Bei
jin
g Polytech
nic
Univers
i
ty.
199
9; 25(2): 67-7
1
.
[10] Du JQ, Lu YS,
Z
hu MF
, Z
han
g K, Din
g CH.
A Nove
l Alg
o
rit
h
m
of Co
lor T
o
ngu
e Imag
e S
e
g
m
e
n
tatio
n
Based o
n
HSI.
Procee
din
g
s of
Biomed
ical En
gin
eeri
ng a
nd Informatics. Sa
n
y
a. 200
8: 733
-737.
Evaluation Warning : The document was created with Spire.PDF for Python.