TELKOM
NIKA Indonesia
n
Journal of
Electrical En
gineering
Vol.12, No.5, May 2014, pp
. 3272 ~ 32
8
0
DOI: http://dx.doi.org/10.11591/telkomni
ka.v12i5.4946
3272
Re
cei
v
ed O
c
t
ober 1
7
, 201
3; Revi
se
d Novem
b
e
r
26, 2013; Accept
ed De
cem
b
e
r
12, 2013
Automatic 3D Model Annotation by a Two-Dimensional
Hidden Markov Model
Guo Jing*
,
Z
hou Mingqu
an, Li Chao
Coll
eg
e of Information Sci
enc
e and T
e
chno
l
o
g
y
, North
w
e
s
t Universit
y
, Xi’
an, Chi
n
a
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: apal
ad
a@so
hu.com
A
b
st
r
a
ct
In this p
a
p
e
r,
a n
e
w
met
hod
of 3D
mod
e
l
aut
o
m
atic
an
n
o
tation
is
prop
osed
bas
ed
o
n
a tw
o-
dim
e
nsional Hidde
n Mark
ov
Model (2-D
HMM).
Growing importance
in the last year
s Hidden Mar
k
ov
Mode
ls are a
w
i
dely use
d
method
ol
ogy for sequ
enti
a
l
dat
a mo
de
lin
g. Recent year
s, H
MMs are appl
i
ed to
researc
h
of
aut
omatic a
n
n
o
tation, suc
h
as i
m
a
ges
an
d
mo
dels
an
notati
o
n. T
he thre
e b
a
sic pr
obl
e
m
s
w
i
th
HMM-like
d
mo
del
are
als
o
s
o
lved
in
our
mo
del. Our
mod
e
l
i
ng
proc
ess h
a
s
tw
o steps, th
ose
are tra
i
ni
n
g
and testin
g. In the prop
os
ed
appr
oach, e
a
c
h
obj
ect is sep
a
rated i
n
to sev
e
ral b
i
ns by a
spid
erw
eb mo
de
l
and
a sh
ap
e fu
nction
D2
is co
mp
uted f
o
r eac
h bi
n. T
hese
f
e
ature vect
ors a
r
e then
arra
ng
ed i
n
a s
e
q
uen
tia
l
fashio
n to co
mpose
a se
qu
en
ce vector, w
h
ic
h is us
ed to
trai
n HMMs. In 2-
D HMM, w
e
as
sume that fe
atur
e
vectors are st
atistically
de
p
end
ent
on
an
und
erlyi
ng state proc
ess w
h
ich h
a
s tran
sition pr
ob
abi
li
ties
cond
ition
i
n
g
the states of two
nei
ghb
ori
ng
bins. T
hus the
depe
nd
ency
of tw
o dimens
ions is reflect
e
d
simulta
neo
usly
. To classify
a
n
o
b
ject, the
maxi
mi
z
e
d
poste
riori prob
ab
ility
is
ca
lcul
ated by
a give
n mo
de
l
and
the
obs
erv
ed s
equ
enc
e o
f
an u
n
kn
ow
n o
b
ject. C
o
mpar
i
ng w
i
th th
e g
e
n
e
ral
HMM, 2-D
HMM gets
mor
e
infor
m
ation from
the neig
hboring bins. So the system
of
2-D HMM perform
s well on im
ages and mode
l
ann
otatio
n. Analysis a
nd ex
p
e
ri
ment
al resu
l
t
s s
how
that the pro
pos
ed
appr
oach
perf
o
rms b
e
tter than
existin
g
on
es in datab
ase.
Ke
y
w
ords
:
3D mod
e
l
cl
a
ssificatio
n
,
hid
den mark
ov mo
de
l,
tw
o-dime
nsi
ona
l
hi
d
den mark
ov mo
de
l,
expectati
on
ma
ximi
z
a
tio
n
(EM) algorit
h
m
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. lntroduc
tion
In the past few years, we have observe
d the av
ailabi
lity of technol
ogie
s
for the effective
acq
u
isitio
n of
digital 3D
m
odel
s of re
al
obje
c
ts
, the e
s
tabli
s
hme
n
t of open
stan
d
a
rd
s for
3D
d
a
ta
interchan
ge, and the increasi
ng u
s
e o
f
3D model
s
in a variety of applicatio
ns in medi
ci
ne,
engin
eeri
ng, and cultural heritag
e etc.
As a re
su
lt, many colle
cti
ons of 3
D
m
odel
s are
cre
a
ted
and are available for stu
d
y
and usag
e, such as
Pri
n
ceto
n Unive
r
sity [1, 2], N
a
tional Tai
w
a
n
Univers
i
ty [3, 4], Kons
tanz
[5, 6]etc
.
To ma
ke
full
use
of a
d
van
t
ages of exi
s
ting digi
tal
3
D
data,
cla
ssifi
cation
is usu
a
lly the
first ste
p
. Putting the u
n
kn
own
sa
mple i
n
to a p
r
ed
ef
ined o
b
je
ct cl
ass [7, 8] is the ba
si
c targ
et of
3D mo
del cl
a
ssif
i
cat
i
on.
I
n
some p
r
a
c
t
i
cal ap
p
lications such as
Molecu
la
r Biology, Astron
omy,
Mech
ani
cal E
ngine
erin
g, M
edical Imag
e
s
et
c, we
onl
y need to
kn
ow the
lab
e
l
of the obj
ect.
So
cla
ssifi
cation
is very valuab
le in so
ciety and economy.
Gene
rally, p
eople try to
descri
p
tion a
3D obj
ect b
y
characte
rs.
Description
of a 3D
model in
clud
es glo
bal an
d local featu
r
es. Ma
ny
algorithm
s are
used to extract featu
r
e
s
of
model
s. O
s
a
da u
s
ed
sh
a
pe di
stributio
ns [9] a
s
th
e glob
al feat
ure to
rep
r
e
s
ent 3
D
sha
pe.
Surface cu
rv
ature
s
[10] are e
s
timate
d at a
geo
metry vertex of the 3D obje
c
t mesh
by
con
s
id
erin
g the variatio
ns of the surfa
c
e no
rmal
over the platel
e
t
of vertex. T
hese algo
rith
ms
mainly
focus on
the
glob
al
feature
s
of a
3
D
mo
del. Other metho
d
s rep
r
e
s
e
n
t 3D
m
odel
s b
y
a
seri
es
of local sha
pe feat
ure
s
[11]. Th
ese m
e
t
hod
s which ad
opt
visual features for
simila
rity
comp
ari
s
o
n
g
r
adu
ally co
m
e
to a reali
z
a
t
ion of
its limi
t
ations. Th
ese metho
d
s
assume
that th
ere
is an i
nhe
ren
t
mapping
be
tween l
o
w-le
vel feature
s
and hi
gh-l
e
ve
l sema
ntics. No
w, it beco
m
es
clea
r that th
e assum
p
tio
n
doe
s n
o
t hold for
man
y
application
s
. Ho
w to n
a
rrow
do
wn
the
sema
ntic ga
p
still remain
s
an ope
n issu
e. Auto
matic model an
nota
t
ion has em
erged a
s
a maj
o
r
approa
ch to b
r
idge the
sem
antic ga
p.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Autom
a
tic 3D Model Annot
ation by a T
w
o-Dim
e
n
s
ion
a
l Hidd
en Ma
rko
v
Mo
del (Guo Ji
ng)
3273
In this pape
r, a new metho
d
of 3D mode
l aut
omatic cl
assificatio
n
is propo
se
d ba
sed on
2-D
HMM. HMM is intro
d
u
ce
d as a
ge
neral fr
ame
w
ork fo
r conte
x
t depende
nt classifie
r
s.
Our
method co
nst
r
uct
s
a statist
i
cal stru
ctu
r
e by
a
2
-
D HM
M. The
ob
servation of
HM
M is de
scrib
e
d
by a set of l
o
cal
feature
vector
s. Th
e
seq
uen
ce i
s
then a
r
range
d by a
ce
rtai
n fashion th
a
t
is
related to glo
bal feature
s
. The structu
r
e
in the
classi
fication algo
ri
thm takes mi
xture of glob
al
and local feature
s
in 3D m
odel as its cl
a
ssifi
cation crit
erion
whi
c
h p
e
rform
s
very well in pra
c
tice.
The
re
st of t
he p
ape
r i
s
o
r
gani
ze
d a
s
follows.
Se
cti
on 2
i
s
p
r
evi
ous works o
n
HMM.
Secti
on 3
pre
s
ent
s gen
eration of the
2-D
HMM. Section 4 i
s
o
u
tline of our
algorith
m
. Experim
ent re
sults
are sho
w
n in
se
ction 5. Section 6 is a
su
mmary of the full.
2. Pre
v
ious
Work
s on HMM
Since th
e th
eory of
hidd
e
n
Ma
rkov mo
dels (HMM
s) was devel
o
ped i
n
the
1
960
s by
Baum a
nd P
e
trie
(19
6
6
)
,
Baum a
nd E
agon
(
1967
),
Baum
(1
972
), HM
Ms hav
e be
en
wid
e
l
y
applie
d to
sp
eech recognit
i
on context [1
2]. And it is
o
n
ly in the la
st
decade
that
they have b
e
e
n
widely u
s
e
d
for several
o
t
her ap
plications, a
s
h
a
n
d
written
ch
aracter re
co
gni
tion, DNA a
nd
protein m
odel
ing, gestu
re reco
gnition, a
nd beh
avior a
nalysi
s
and
synthesi
s
etc.
Re
cently yea
r
s, HMM i
s
a
p
p
lied to
auto
m
atic
cla
ssif
i
cat
i
on,
su
ch
as
im
age
s an
d
mod
e
ls
cla
ssifi
cation.
In ima
g
e
s
cl
assificatio
n
, p
r
eviou
s
wo
rk
extended
the
1-D
HMM [1
3
], a p
s
eu
do
2
-
D
HMM [1
4, 15
] and
2D HM
M [16]. To
cl
assify image
s, the sample
s are
divide
d i
n
to blo
c
ks,
a
nd
feature
s
of bl
ocks a
r
e
com
puted for giv
en a se
que
nce of obvious.
[13] pre
s
ent
s a spatial
-
HM
M
(SHMM
)
for
automatically cla
ssifying
a
nd an
notat
in
g natu
r
al ima
ges. T
w
o
ge
nerali
z
atio
n o
f
the
traditional
HMM are train
ed in the sen
s
e that
both vertical an
d hori
z
ontal tra
n
sition
s betwee
n
hidde
n states are take
n into con
s
ide
r
ati
on. J.Li
et al.
[16] propo
se
d
a new 2D M
H
MM to cla
ssify
image
s into
categ
o
rie
s
and p
r
op
aga
te annotatio
ns fro
m
keywords
whi
c
h
were man
u
a
lly
assign
ed to
those
categ
o
ri
es. O
n
e
of ex
ist issu
es
of t
hese m
e
thod
s i
s
cho
o
si
ng
bloc
k si
ze
s.
T
he
same
proble
m
also
exist
s
in 2
D
HM
M. To
solve
this p
r
oble
m
, some
m
e
thod
s in
si
gnal
pro
c
e
ssi
ng a
r
e p
r
op
osed.
Trelli
s codin
g
[17]
in ima
ge comp
re
ssi
on provide
s
an exampl
e
by
usin
g context
inform
ation. Other
works [18,
19]
have
looked into
ways of takin
g
advantage
of
context information to improve
classifi
cation p
e
rfo
r
mance. Both block
si
ze
s and cl
assification
rule
s can vary accordi
ng t
o
co
ntext. The impr
ove
m
e
n
t achieve
d
demon
strates the potential
of
c
ontext to help c
l
as
s
i
fic
a
tion.
3. Genera
tio
n
of 2D
HMM
In the proce
s
s of Cl
assification, one
HMM is
trained
for ea
ch
cla
s
s of obj
ect
s
. We u
s
e
a
first-o
r
de
r
HMM for trai
ni
ng. A stand
ard HMM i
s
d
e
fined a
s
a
sta
t
e seq
uen
ce
12
(,
,
.
.
.
,
)
T
q
qq
q
and ob
se
rva
b
le se
que
nce
12
(
,
,
...
,
)
T
o
oo
o
gene
rated
by the state seq
uen
ce.
Similarly, we
con
s
id
er that
observabl
e fe
ature ve
ctors of 3D
obje
c
t’s surfa
c
e
poi
nts a
r
e relate
d to the
spati
a
l
stru
cture of 3D obje
c
t. Practi
cally ob
servable
featu
r
e vecto
r
s a
r
e obse
r
vabl
e
and the spa
t
ia
l
stru
cture of 3
D
mod
e
l is u
nob
serva
b
le. For exam
ple,
a car m
odel i
s
co
nstituted
by the body a
n
d
the bottom
of the four wheels
. In
o
r
d
e
r t
o
mod
e
l relati
on bet
wee
n
spatial st
ru
cture and
ob
se
rved
feature vecto
r
, a set of observation
s of traini
ng o
b
ject
s are used to e
s
timate HM
M
param
eters.
3.1. Definitio
n
of Hidde
n Markov
Model
To de
scrib
e
p
r
ocess
of pro
duci
ng the
pa
ttern
, a first o
r
de
r Hi
dde
n
Markov Mo
de
l, which
statistical stru
cture i
s
depi
cted by a para
m
eter vecto
r
(,
,
)
A
B
, is defined a
s
followi
ng.
: The initial state probabilit
y dist
ribution,
representing
pr
obabilities of initial
states, that is to
say
,
1
[]
ii
P
qs
，
1
iN
.
A
: The state transitio
n matri
x
，
ij
A
a
, where
1
[]
,
1
ij
t
j
t
i
aP
q
s
q
s
t
T
,
s
a
tis
f
ying
1
1,
1
,
N
ij
j
ai
j
N
.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 5, May 2014: 3272 – 32
80
3274
B
: The con
d
itional pro
babilit
y matrix,
={
(k)}
,
j
B
b
sat
i
sf
y
i
ng
()
[
]
,
j
j
k
t
kP
q
b
s
v
w
h
er
e
N
is
the numbe
r o
f
states,
M
is the numbe
r of observation
s.
3.2. Observ
a
ble Sequenc
e of t
w
o
-
dim
e
nsional HM
M
The
spa
c
e o
f
3D obj
ect i
s
de
com
p
o
s
ed by a
spid
erweb m
odel
[9], as illust
rated by
Figure 1. In
Figure 1
start
i
ng from
po
si
tive
dire
ction
of the first
pri
n
cipl
e axis
1
U
，
each bin i
s
observed
se
quentially
by clo
c
kwi
s
e
to get
an
ob
serva
b
le
se
q
uen
ce. Th
e f
eature
vecto
r
is
extracted i
n
e
a
ch bi
n by sh
ape fun
c
ti
on
D2[20]. The f
eature ve
ctor
of bin
(,
)
ij
is de
no
ted by
,
ij
o
, where
(,
)
ij
rep
r
ese
n
ts the j-t
h
bin of the i-th sh
e
ll. He
nce a
3D o
b
j
ect co
rrespo
nds to a
n
observabl
e seque
nce as
0,
0
0
,
1
,
(
,
,
.
..
,
.
..
)
ij
O
oo
o
,
0
,
1
,
2,
.
..,
1
iw
,
0,
1
,
2,
...
,
1
jj
z
.
3.3. Prepare
d
Work on 2
D
HMM
The 2D HMM
assu
me
s that feature vectors
a
r
e ge
nerated by a Markov mod
e
l that may
cha
nge
state
on
ce eve
r
y
bin. Th
e transitio
n
p
r
ob
abilities
co
nd
ition on th
e
state
s
of t
w
o
neigh
bori
ng b
i
ns sho
w
ed in
Figure 2.
Suppo
se that
there a
r
e
M
states
{1
,
.
.
.
,
}
M
, and the
state of bin
(,
)
ij
is den
oted by
,
ij
s
. The feature
vector of bin
(,
)
ij
is
,
ij
o
. Denote
'
'
(,
)
(
,
)
ij
j
i
, i
f
'
<i
i
or
'
i
i
and
'
j
j
, in
whi
c
h ca
se, we say
that
the
bin
'
'
(,
)
j
i
is before bin
(,
)
ij
. In 2D
HMM, we ma
de an
assum
p
tion
that
''
''
,,
,
,
,
'
'
:(
,
)
)
(,
ij
m
n
l
jj
ii
j
i
P
ss
o
a
, wh
ere
''
''
{(
,
)
:
,
(
,
)
}
ij
jj
ii
1,
,
1
,
,,
i
j
ij
ij
mn
l
s
ss
. In above assumptio
n
, we
cal
c
ulate the
transitio
n probability of o
n
e
state by
kno
w
ing th
e
states of th
e two adja
c
e
n
t
bi
ns in
da
rker
sha
de in
figu
re 2. T
he
st
ate
transitio
n of 2
D
HM
M is ex
plaine
d by Fi
gure
3.
The
seco
nd a
s
sum
p
tion is that t
he den
sity of the
observation
o
in state
s
follows a
Gau
s
si
an di
strib
u
tio
n
. On
ce
th
e
state of
a bi
n
is
kn
own, the
feature
vecto
r
is
co
ndition
al
ly indep
end
e
n
t of th
e
corresp
ondi
ng fe
ature
s
of oth
e
r
bins.
Fo
r a
bin
with state
s
and feature vect
or
o
,
the distri
bution ha
s de
nsity
1
1
()
()
2
1
()
(2
)
t
s
k
s
s
s
oo
o
s
be
, where
s
is the cova
rian
ce matrix, and
s
is the mean
vec
t
or
.
Figure 1. Gen
e
ration of Ob
serva
b
le Seq
uen
ce
Fi
gure 2. Explanation of Ad
jace
nt Bins of Bin
(,
)
ij
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Autom
a
tic 3D Model Annot
ation by a T
w
o-Dim
e
n
s
ion
a
l Hidd
en Ma
rko
v
Mo
del (Guo Ji
ng)
3275
Figure 3. Explanation of State Tran
sition
of 2D HMM
4. An Outline of the
Algorithm
An outline of our alg
o
rithm
is as follo
ws.
Step 1 Traini
ng
a.
Divide traini
n
g
obje
c
ts into
spide
r
web m
odel
an
d extract feature vector for e
a
ch bin.
b.
Select the nu
mber of state
s
for HM
M.
c.
Estimate mod
e
l para
m
eters base
d
on a set of
obse
r
vable se
que
nce
s
of training o
b
ject
s.
Step 2 Testin
g
a.
Gene
rate ob
servable
seq
u
ence (same a
s
step
Ⅰ
a
)
for a testing 3D
obje
c
t.
b.
Search for t
he set of cl
asses with
maxi
mizing a
posteriori
probability, given the
corre
s
p
ondin
g
seq
uen
ce o
f
feature vect
ors to the trai
ned HM
M.
4.1. Training
Given a
set
of ob
se
rvabl
e sequ
en
ce
s
O
, tr
a
i
n
i
ng
th
e mo
de
l, is pe
r
f
o
r
me
d us
in
g
th
e
stand
ard Ba
u
m
-Welch re
-estimation p
r
oce
dure to determin
e
the
param
eter
(,
,
)
A
B
tha
t
maximizes t
he probability
()
PO
. This method is
ba
se
d on the
well-kno
w
n Expectatio
n
Maximiz
a
tion (EM) algorithm [21].
The EM alg
o
rithm p
r
ovi
des
an itera
t
ive
computa
t
ion of maximization,
wh
en the
observed
dat
a a
r
e in
co
mpl
e
te. The
term
“in
c
om
plete”
refle
c
ts the f
a
ct that
we
n
eed to
e
s
tima
te
the distri
butio
n
x
of in sam
p
le sp
ace
, but we can o
n
ly obse
r
ve
x
indire
ctly
thro
ugh
s
in
sampl
e
s
p
a
c
e
S
. In many ca
se
s, there
is a map
p
in
g
()
x
sx
from
to
S
, and
x
is only
kno
w
n to lie i
n
a sub
s
et of
, denoted by
()
s
, which is d
e
t
ermine
d by the eq
uation
()
s
sx
. We po
stulat
e a family of
distrib
u
tion
()
f
x
, with parameters
, on
x
. The distrib
u
tion o
f
()
s
,
()
g
s
can b
e
de
rived as
()
()
(
)
s
g
sf
x
d
x
.
The EM algo
rithm aims at
finding a
th
at maximizes
()
g
s
given an observe
d
s
.
Before de
scri
bing the algo
rithm, we introdu
ce a fun
c
tion
''
()
(
l
o
g
(
)
,
)
QE
f
x
s
that is the
expecte
d value of
'
lo
g
(
)
fx
acco
rding to the
con
d
itional di
stributio
n of
x
given
s
and
para
m
eters
. The
expe
ctation i
s
a
s
su
med to
exist
for
all pai
rs
,
'
()
. In pa
rticul
ar, it is
assume
d that
()
0
fx
for
.
The EM iterat
ion
()
(
1
)
pP
is defined as follows.
1) E-step: Co
mpute
()
()
p
Q
.
2) M-step: Ch
oose
(1
)
P
to be a value of
tha
t
maximiz
e
s
()
()
p
Q
.
When
usi
n
g HMMs,
a
practi
cal
b
u
t funda
men
t
al issue
to
be
add
re
ssed i
s
the
determi
nation
of thei
r
stru
ct
ure,
namely t
he top
o
logy
a
nd the
nu
mbe
r
of
state
s
. In
this p
ape
r, th
e
numbe
r of sta
t
es ca
n be ch
oosed in ra
ng
e of 2 to given limitation 10.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 5, May 2014: 3272 – 32
80
3276
Specifically to say, in
E-step, the co
mplete data
x
are
,,
{,
:
(
,
)
}
ij
ij
ij
so
, and the
inc
o
mplete data
y
are
,,
{,:
(
,
)
}
ij
i
j
ij
co
.
Th
e function i
s
Equation (1).
,,
,
1,
,
1
,
,
(,
)
(,
)
,
''
'
()
(
)
(
,
)
'
'
'
(:
,
,
)
(
,
,
:
)
'
'
'
.(
,)
.
,,
mn
l
m
m
ij
i
j
ij
ij
ij
ij
ij
ij
fx
s
P
u
s
sm
n
l
P
u
s
m
a
P
P
P
a
u
sss
s
s
(1)
Then we get Equation (2) from (1
).
,
1,
,
1
,
,
,
(,
)
(
,
)
,,
'
()
'
'
'
lo
g
l
o
g
lo
g
(
,
)
ij
i
j
ij
ij
ij
ij
ij
i
j
x
f
P
ao
s
ss
s
s
(2)
Furthe
r, we
can make the equatio
n 3 directly
by takin
g
expectatio
n
s
on Equatio
n
(2).
()
()
()
,
,
1,
,
1
,
,
(,
)
(
,
)
11
'
'
''
((
)
,
)
(
)
(
)
(
,
)
,,
,,
lo
g
l
o
g
lo
g
.
pp
p
ij
ij
ij
i
j
i
j
ij
ij
i
j
ss
fx
y
P
P
sy
sy
o
E
P
a
s
sss
s
(3)
In the M-s
t
ep, we
s
e
t
(1
)
p
to the
'
that max
i
mize
s
(3) . In equ
ation
(3
), two
part
s
can be
maximize
d by choo
sin
g
co
rrespon
ding p
a
ram
e
ters. When maximi
zi
ng the first pa
rt, we define:
()
()
,,
1,
,
1
,
(,
)(
,
,
)
(
,
)
p
p
mn
l
i
j
ij
ij
s
ij
mn
l
s
y
ss
s
P
H
I
(4)
As the probability of being in state
m
at bin
(1
,
)
ij
, state
n
at bin
(,
1
)
ij
,and state
l
at
bin
(,
)
ij
,
given the
ob
served fe
ature
ve
ct
o
r
s,
cla
s
se
s,
an
d mo
d
e
l
()
p
. Equatio
n
(5) can
be
de
duced from
Equation (4).
()
,,
(,
)
,,
()
,,
1(
,
)
(,
)
'
(,
)
p
mn
l
ij
mn
l
p
M
mn
l
ti
j
ij
ij
H
a
H
(5)
Next, co
nsi
der th
e m
a
ximization
of the
se
con
d
pa
rt in (3
).
We
let
()
()
,
(,
)
(
)
(
,
)
p
p
m
ij
s
ij
m
P
s
y
I
s
L
, whi
c
h i
s
the probabilit
y of being in
state
m
at blo
c
k
(,
)
ij
,
given the
o
b
se
rved
feat
ure
vecto
r
s,
and
mo
del
()
p
. T
he
ab
ove exp
r
e
ssi
on i
s
th
en
()
,
1(
,
)
'
'
(,
)
l
o
g
(
,
)
M
p
ij
m
m
m
mi
j
ij
P
o
L
.It is
k
n
own that for
Gauss
i
an
di
s
t
ributions
, the ML
es
timate
'
m
of is the
sa
m
p
le ave
r
ag
e
of the
data, a
nd the
ML
e
s
timate
'
m
of is the
sam
p
le
co
varian
ce
matrix of the
data. Since, i
n
our
ca
se, th
e data a
r
e
we
ighted by
()
(,
)
p
m
ij
L
, the ML es
timat
e
of
'
m
and
'
m
are:
()
,
,
()
,
(,
)
'
,
(,
)
p
m
ij
ij
m
p
m
ij
ij
o
L
ij
L
'
()
,
,
,
()
,
'
(,
)
(
)
()
'
(,
)
t
p
m
ij
ij
m
ij
m
m
p
m
ij
ij
o
L
o
ij
L
.
In summa
ry, the estimatio
n
algorith
m
iterativ
ely improves the mo
del estimatio
n
by the
f
o
llowin
g
st
ep
s.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Autom
a
tic 3D Model Annot
ation by a T
w
o-Dim
e
n
s
ion
a
l Hidd
en Ma
rko
v
Mo
del (Guo Ji
ng)
3277
1.
Given the cu
rrent mod
e
ls
()
()
()
(
)
(,
,
)
pp
pp
AB
.
2.
Given the
ob
serve
d
featu
r
e vecto
r
s
,
ij
o
, th
e
me
an
vec
t
or
a
n
d
c
o
va
r
i
an
c
e
ma
tr
ic
es
are up
dated
by:
()
,
,
(1
)
()
,
(,
)
,
(,
)
p
m
ij
ij
p
m
p
m
ij
ij
o
L
ij
L
(1
)
()
(1
)
,
,
,
(1
)
()
,
(,
)
(
)
()
(,
)
t
p
p
p
m
ij
ij
m
ij
m
p
m
p
m
ij
ij
o
L
o
ij
L
,
Whe
r
e,
1,
,
1
,
,
,
()
()
()
()
,
,
,,
(,
)
(
,
)
1
((
)
)
(
,
)
(
).
.
.
(
,
).
i
j
ij
ij
ij
ij
p
p
p
p
m
ij
ij
s
ij
ij
ICs
c
ij
I
m
P
s
L
au
sss
s
s
The transition probab
ilities are
updated by:
()
,,
,
(1
)
,,
()
,,
1,
(,
)
(,
)
p
MN
L
ij
p
mn
l
M
p
MN
L
li
j
ij
ij
H
a
H
,
Whe
r
e,
,
()
()
()
()
,,
1,
,
1
,
,
,
1,
,
1
,
(,
)
(
,
)
1
(,
)
(
(
)
)
(,
,
)
.
.
.
(
,
)
.
,,
ij
p
p
p
p
MN
L
i
j
ij
ij
ij
ij
i
j
ij
ij
s
ij
i
j
ij
I
C
s
c
Im
n
l
P
ss
s
a
u
H
ss
s
s
s
{(
,
)
:
0
,
0
}
ij
i
w
j
z
, refers to all the bin
s
of an obje
c
t.
3.
Rep
eat step
2, until
()
{}
p
conve
r
ge
s to som
e
con
s
tant ap
proximately.
4.2. Testing
The cla
s
sifica
tion step is p
e
rform
ed by assi
gni
ng an
unkno
wn obj
ect to the cla
ss of the
model sho
w
i
ng the maximum likelih
o
od. i.e.,
assigning an u
n
known item
to the class whose
model
sho
w
s the maximal likeliho
o
d
arg
m
ax[
(
)]
Po
.
o
is an ob
se
rvabl
e sequ
en
ce
of unkn
o
wn
obje
c
t that is generated u
s
ing the above
method.
,
,
,,
,,
,
1,
,
1
,
(,
)
(
,
)
()
(
,
)
:,
,
()
()
(
,
,
:
)
(,
)
ij
ij
mn
l
m
m
ij
i
j
ij
ij
s
s
sss
s
s
s
s
ij
ij
Ps
P
o
s
mn
l
m
Po
Ps
P
o
s
a
P
au
5. Experiment Re
sults
Our expe
rime
nts are ba
se
d on the Princeton
Sha
pe Bench
m
ark d
a
taba
se (2
00
5). Thi
s
publi
c
datab
ase
ha
s bee
n larg
ely use
d
in obje
c
t reco
gnition lit
eratu
r
e. It co
ntains
1814
3D
model
s whi
c
h
have been split into a training dat
ab
ase and a test databa
se. We use mo
dels of
training
data
base to trai
n
HMM’
s pa
ra
meters an
d t
he othe
rs of
testing d
a
tab
a
se to
test.
We
comp
are ou
r method
with
adaptive
we
ighted a
s
ym
metric
(AdaB
oost) hid
den
Markov mo
dels
(ADHMM) an
d Shap
e
Dist
ribution
(SD)
prop
osed i
n
re
feren
c
e
s
[2
0
,
22] an
d result sh
ow that
our
method pe
rfo
r
ms b
e
tter.
We teste
d
our app
roa
c
h
by varying the fr
ee param
eters of the tech
niqu
es. T
he first
experim
ent d
e
mon
s
trate
s
that the a
c
cu
racy
of
ch
an
ges
und
er
di
fferent pa
ra
meters, i.e., the
numbe
r of bi
ns
L
, and the
numbe
r of
states of
HMM
s
n
. We s
e
t
Lw
z
, where
w
is n
u
mb
er of
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 5, May 2014: 3272 – 32
80
3278
cir
c
le
s,
z
is nu
mber
of bin
s
in ea
ch
circl
e
. We
do n
o
t want to
ch
o
o
se
a la
rge
size si
nce thi
s
obviou
s
ly ent
ails
crude
cla
ssifi
cation. B
u
t if we
cho
o
s
e
a
small
si
ze, o
n
ly very
local p
r
o
pert
i
es
belon
ging to
the sm
all bi
n
are
examin
e
d
in
cla
ssifi
ca
tion. Some in
formation
ab
out surroun
di
ng
bins i
s
negl
ected. We set the numb
e
r of
bins form 1
6
to 80.
We
cho
o
se
100 m
odel
s f
o
rm 2
0
cate
gorie
s
of trai
ning d
a
taba
se, whi
c
h m
a
y includ
e
some
cate
go
ries
su
ch a
s
h
u
man, spo
r
ts_ca
r
, fight
er_j
et, etc. In each cate
gory, we use 5 mo
de
ls
to train HM
M
s
an
d the re
st to test. From the
Tabl
e
1, we can
see that the system pe
rforms
unsatisfa
ctoril
y when
16
L
.
Clea
rly
,
t
he ac
cu
r
a
cy
in
cre
a
s
e
s
g
r
adu
ally with the numb
e
r of bin
s
L
incre
a
ses. A
c
tually, even
i
f
we
set
4
n
, th
e s
y
s
t
em is
a
b
le
to
r
e
c
o
gn
ize
th
e o
b
j
ec
ts
w
i
th
an
accuracy la
rg
er than 75%.
In particul
a
r,
the accu
ra
cy can a
rrive at
98% with
80
,
6
L
n
.
The
se
con
d
experim
ent i
s
to inve
stigat
e the
accu
ra
cy of th
ree
m
e
thod
s. In thi
s
stage,
we sele
ct 100 obje
c
ts o
f
25 catego
ri
es (each
category contai
ns at lea
s
t 6 obje
c
ts) from
databa
se. In
each
categ
o
ry 5 obj
ect
s
are u
s
ed
for
tra
i
ning, the
oth
e
rs a
r
e
used
for te
sting. T
he
results a
r
e th
en compute
d
usin
g the be
st configu
r
atio
n of paramet
ers
de
ri
ved from the p
r
evio
us
analysi
s
, i.e. usin
g
10
8
,
6
Ln
. The performances of the thr
ee methods are illustrated in
Figure 4. It is
clea
r that our
method
pe
rfo
r
ms b
e
tter th
an the other
one
s.
The la
st exp
e
rime
nt is to
demon
strate
our te
ch
niqu
e is i
n
vari
ant
to mod
e
l rotation an
d
transfo
rmatio
n. And then 15 different
model
s ar
e
selecte
d
form the databa
se.
For each mo
del,
we perfo
rm 2
scalin
g
(scal
e
facto
r
s:0.5 and 1.5
re
sp
ectively),
3 ro
tations (90
de
gree
s aroun
d
x-,
y-, z-
axis respectively). So
we g
e
t mo
re
5 ne
w mo
del
files of ea
ch
model
and
pu
t them togeth
e
r
with the
o
r
igi
nal m
odel
s. I
n
this
way, a
sm
all te
st d
a
taba
se
with
90 m
odel
s
of 15
catego
rie
s
i
s
gene
rated.
We the
n
sel
e
ct rand
omly model
s form
the test d
a
taba
se to t
e
st. Cla
s
sification
accuraci
es are propo
sed
in
Table
2.
Fro
m
the figu
re,
we
can
se
e t
hat the
syste
m
is ve
ry rob
u
st
and b
o
th me
thods
are i
n
sen
s
itive to the mod
e
l’s
rotation an
d tran
sform
a
tion
, and produ
ce
comp
arable result
s.
Table 1. The
Accu
ra
cy of Different Parameters
L=
n=
2×8
4×8 6×8
8×8 10×8
2
0.7172
0.7256
0.7561
0.7608
0.7813
3
0.7374
0.7481
0.7590
0.7747
0.7810
4
0.7690
0.7863
0.8002
0.8012
0.8142
5
0.7898
0.7978
0.8149
0.8363
0.8891
6
0.8182
0.8381
0.89397
0.9412
0.9815
7
0.8444
0.8491
0.8528
0.9434
0.9300
8
0.8576
0.8580
0.8723
0.9014
0.9079
9
0.8662
0.8508
0.8966
0.8827
0.8967
10
0.8800
0.8817
0.7699
0.8523
0.8815
Figure 4. The
Average Accura
cy of the Three M
e
thod
s
0
0.
1
0.
2
0.
3
0.
4
0.
5
0.
6
0.
7
0.
8
0.
9
1
human
f
i
g
hter
_jet
po
tted_pl
ant
s
po
r
t
‐
human
2DHMM
ADHMM
SD
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Autom
a
tic 3D Model Annot
ation by a T
w
o-Dim
e
n
s
ion
a
l Hidd
en Ma
rko
v
Mo
del (Guo Ji
ng)
3279
Table 2. The
Re
sult of the Third Expe
ri
ment
2DHMM
ADHMM
SD
bed 91.4
80.6
83.0
Tree
88.7
80.8
76.5
bicy
cle
90.0
85.5
79.6
tank 88.3
79.3
80.0
track 92.5
66.0
87.1
6. Conclusio
n
In this pa
per,
a
ne
w meth
od fo
r a
u
tom
a
tic 3
D
obje
c
t Annotation
has be
en
propo
sed
based on th
e two-dimen
s
ion
a
l Hid
d
e
n
Markov M
odel ap
pro
a
ch. Specifically, each mod
e
l is
sep
a
rate
d int
o
seve
ral bin
s
by spi
derweb mod
e
l.
Fo
r ea
ch bin, th
e feature of
D2 is
com
put
ed.
The sequ
en
ces of ve
ctors (one fo
r e
a
ch bin)
are su
bse
que
ntly modele
d
u
s
ing
HMM
s
, payi
n
g
particula
r attention to the
initialization
a
nd the
m
odel
sele
ction i
ssues.
Cla
ssifi
cation is ca
rri
ed
out by usin
g
a nea
re
st nei
ghbo
r rul
e
, where
dist
a
n
ce is compute
d
usin
g the
HMM likeliho
od
function. A thoro
ugh
exp
e
rime
ntal evaluation h
a
s
sho
w
n that t
he propo
se
d
approa
ch i
s
very
promi
s
in
g for cla
s
sifying 3
D
obj
ect
s
fro
m
larg
e d
a
ta
base. Fu
rthermore, th
e p
r
opo
sed
meth
od
remai
n
s q
u
ite
accurate eve
n
in ca
se of model of tran
sform
a
tion, scale a
nd rotat
i
on.
An intere
stin
g extensi
on o
f
the method
coul
d
go to
ward the i
n
vestigation of th
e use of
the 3
D
mo
d
e
l segme
n
tation. In p
a
rticular,
we
are
investig
ating
the
sep
a
rat
e
3
D
mo
del
into
meanin
g
ful p
a
rts by HM
M
s
.
Ackn
o
w
l
e
dg
ements
The work de
scribe
d in thi
s
pap
er
wa
s supp
orte
d b
y
the Nation
al Scien
c
e F
ound
ation of
Chin
a (G
rant
No. 6073
60
08) an
d No
rt
hwe
s
t Unive
r
sity National
Scien
c
e Fo
undatio
n (G
rant
No.ND0
936, No.JD1
031
6).
Referen
ces
[1]
3D model sear
ch engine,
http://shape.cs.princeton.edu.
[2]
P Min, JA Hald
erman, M Kazh
dan, T
A
F
unkhouser.
Early
ex
peri
ences w
i
th
a 3D
mod
e
l se
arch en
gi
ne
.
W
eb 3D S
y
m
p
osium. F
r
ance.
2003; 7
–18.
[3]
3D mod
e
l retri
e
val s
y
stem,
http://3d.csie.ntu.
edu.t
w
/˜
dy
n
a
mi
c/.
[4]
DY Che
n
, XP
T
i
an, YT
Shen, M Ouh
y
oun
g.
On visual s
i
mil
a
rity base
d
3
D
mo
del r
e
trieva
l
. Comput
e
r
Graphics F
o
ru
m (EG 2003 Procee
din
g
s). Sp
ain. 20
03; 22(
3
)
: 223-23
2.
[5]
3D model similarit
y
se
arch engine, http://mer
kur
01.inf.uni-konst
anz.de/CCCC/.
[6] DV
Vrani
′
c.
A
n
i
m
pr
ove
m
en
t of rotatio
n
i
n
vari
ant 3
D
s
hap
e d
e
scri
p
tor b
a
sed
o
n
functions
o
n
co
n
c
en
tri
c
sp
he
re
s
.
Image Pr
ocessi
ng. In ICIP 2003, 20
03; 2: III - 757-60.
[7]
Csaka
n
y
P, W
a
llace AM. Repr
esentat
i
o
n
and classific
a
tion of 3D ob
j
e
cts.
IEEE Tr
ansactions
on
Systems, Man,
and Cyb
e
n
e
tic
s
, Part B
: C
y
b
e
m
etics. 2003; 3
3
(4): 638-
64
7.
[8]
Hub
e
r D, K
a
p
u
ria
A, Do
nam
ukkal
a
R
R
.
Pa
rts-based
3D
obj
ect class
i
fic
a
tion
.
Comp
ut
er Visi
on
an
d
Pattern Reco
g
n
itio
n, 200
4. CVPR 200
4.
W
a
shin
gton, DC, USA. 2004; 2:
82-8
9
.
[9]
Mihael Ankerst, Gabi
Kaste
n
m
üller, Ha
ns-
P
eter
Kri
ege
l, T
homas
Seid
l.
3D
Sha
p
e
Hi
stogra
m
s fo
r
Similar
i
ty Sear
ch and Cl
assifi
cation i
n
Spati
a
l Data
bases
.
6th Internatio
n
a
l S
y
m
posi
u
m, SSD’99. Hon
g
Kong, Ch
in
a. 1999; 20
7-2
26.
[10] Vand
eb
orre
JP
.
A practical a
p
p
roac
h for 3D
mo
de
l in
dexi
n
g
by combi
n
in
g l
o
cal a
nd
glo
bal
invari
ants
.
3D Data Proc
e
ssing Vis
ual
iza
t
ion an
d T
r
ansmission, 2
002
Processi
ng. Ital
y
. 2
002; 6
44-6
47.
[11]
Liu
yi, W
a
n
g
xulei, Z
h
a ho
ng
bin. 3
D
Partia
l
Shap
e Retri
e
v
a
l Bas
ed o
n
L
o
cal B
ag of W
o
rds Mo
dels.
Acta Scientiar
u
m Natur
a
li
u
m
Univers
i
tatis P
e
kin
ensis
. 2
0
0
9
; 45(6): 96
7-9
68.
[12] La
w
r
ence
R
R
abi
ner.
A T
u
to
rial o
n
H
i
dd
en
Markov Mo
de
ls an
d Sel
e
cte
d
App
licati
ons
in Sp
eec
h
Reco
gniti
on.
P
r
ocee
din
g
s of the IEEE. 1989;
77(2): 257
–2
8
6
.
[13]
F
e
i
y
an
g Yu, Horace HS.
Aut
o
matic Se
ma
n
t
ic Annotatio
n
of Im
ag
es usi
ng Spati
a
l Hi
d
den Mark
ov
Mode
l
. IEEE In
ternatio
nal C
o
n
f
erence o
n
Mul
t
imedi
a and E
x
po. Can
a
d
a
.
2006; 30
5-3
08.
[14]
SS Kuo, OE Agazzi.
Mach
in
e
vision for key
w
ord spotting
usin
g pse
udo
2D hi
dd
en Mar
k
ov mode
ls
.
Acoustics, Spe
e
ch, and Si
gn
a
l
Processi
ng. Minn
eap
olis. 1
993; 5: 81
–84.
[15]
CC Yen, SS Kuo.
Degr
ad
ed docu
m
ents
rec
ogn
ition usin
g
pseu
do 2D
hid
den Mark
ov mode
ls in Gray-
scale i
m
ages
.
SPIE Proceedi
ngs. 199
4; 227
7: 180–
19
1.
[16]
Jia Li, Amir
Naj
m
i, Rob
e
rt M Gra
y
.
Imag
e Cl
assificati
on by
a T
w
o-Dimensi
ona
l Hi
dde
n M
a
rkov Mo
de
l
.
Acoustics, Spe
e
ch, and Si
gn
a
l
Processi
ng. 1
999; 6: 33
13-3
316.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 5, May 2014: 3272 – 32
80
3280
[17]
A Gersho, RM Gra
y
. Vector
Quantiz
atio
n and
Signa
l Compr
e
ssio
n
. Boston
, MA: Klu
w
er.1
992: 62
3.
[18]
CH Fosg
ate,
H Krim, W
W
Irving, W
C
K
a
rl,
AS
W
illsk
y
.
Mu
ltiscal
e
segme
n
tatio
n
and an
omal
y
enh
anc
ement
of SAR imager
y.
Ima
ge Proc
e
ssing
. 19
97; 6(
1): 7-20.
[19]
J Li, RM Gray
.
Context bas
ed
mu
ltiscal
e
clas
sificatio
n
of images
. ICIP 98. Chica
go. 1
998;
3: 566-57
0.
[20]
R. Osada et al. Shape D
i
strib
u
tions.
ACM T
r
ansacti
ons o
n
Graphics
. 20
02
; 21(4): 811-8
1
3
.
[21]
Yuji
an L
i
et al.
Hidd
en Mark
o
v
mo
dels w
i
th
states dep
en
di
ng o
n
obs
erva
tions
. Pattern
Recognition
Letters. 200
5; 26 (7): 977
–9
8
4
.
[22]
Liu
xia
o
mi
ng,
Yin
jia
n
w
e
i,
F
eng
zhi
l
i
n
, Do
ng J
i
n
x
i
a
n
g
. 3
D
mo
del
cl
ass
i
ficatio
n
b
a
se
d
on
a
d
a
p
tiv
e
w
e
ig
hted
as
ym
metric AdaB
oo
st hidd
en M
a
rk
ov mod
e
ls.
Jo
urna
l of Z
h
e
jia
ng U
n
ivers
i
ty
(Engi
neer
in
g
Scienc
e). 200
6
;
40(8): 130
0-1
305.
Evaluation Warning : The document was created with Spire.PDF for Python.