TELKOM
NIKA Indonesia
n
Journal of
Electrical En
gineering
Vol.12, No.4, April 201
4, pp. 2559 ~ 2
5
6
4
DOI: http://dx.doi.org/10.11591/telkomni
ka.v12i4.4808
2559
Re
cei
v
ed Se
ptem
ber 6, 2013; Re
vi
sed
Octob
e
r 16, 2
013; Accepte
d
No
vem
ber
18, 2013
Semi-Supervised Affine Alignment of Manifolds
Rui Jia*
1
,
Tin
g
Lu
2
1
Departme
n
t of Electronic Info
rmation En
gin
e
e
rin
g
,
Chiens
hi
ung i
n
stitute te
chno
log
y
2
T
a
icang se
nio
r
high sch
ool
of Jiangs
u provi
n
ce
*Corres
p
o
ndi
n
g
author, em
ail
:
35113
47
9@q
q
.com
A
b
st
r
a
ct
High di
mensi
o
nal data
is us
ually
pro
duce
d
by the so
urce
that onl
y
enj
o
ys a li
mite
d n
u
mber
of
degr
ees
of freedo
m. Ma
nifo
l
d
le
ani
ng t
e
ch
niq
ue
plays
an
importa
nt part
in fin
d
i
ng th
e
correlati
on
a
m
on
g
the hi
gh d
i
men
s
ion
a
l d
a
ta dat
asets. By mak
i
ng us
e of
mani
fold al
ig
n
m
ent,
the pair
ed
ma
ppi
ng re
latio
n
s
h
i
p
can be
expl
ore
d
easi
l
y. How
e
ver, the common
man
i
fo
l
d
ali
g
n
m
e
n
t alg
o
rit
h
m c
an o
n
ly g
i
ve the
ma
ppi
n
g
result of the trainin
g
set, and
cann
ot dea
l w
i
th a new
comin
g
poi
nt. A new
ma
nifo
ld al
ign
m
e
n
t alg
o
rith
m is
prop
osed
in th
is pap
er. T
he
ben
efit of our
alg
o
rith
m
is two fold: First, the meth
o
d
is a
semi-s
up
ervis
ed
appr
oach, w
h
ic
h
makes
b
e
tter use
of the
loc
a
l g
e
o
m
etry
inf
o
rmatio
n
of th
e
un
pair
ed
poi
nt
s an
d i
m
pr
ove
s
the l
earn
i
n
g
eff
e
ct w
hen th
e
l
abe
led
pr
oporti
on
is very
low
.
Secon
d
, a
n
ext
end
ed s
pectra
l
ag
gressi
on tri
ck
is used
in the
algorithm
,
whic
h can pr
oduce
a linear
m
a
pping between the raw dat
a space and the aligned
space. T
he ex
peri
m
e
n
ts resu
lt show
s that, the corre
la
ti
on
ma
pp
ing c
an b
e
precis
ely o
b
tain
ed, the h
i
dd
e
n
space ca
n be a
lign
ed effectiv
e
l
y, and the cost
of map
p
in
g a
comin
g
poi
nt is very low
.
Ke
y
w
ords
:
ma
nifol
d
ali
g
n
m
en
t, out of sampl
e
, a
ffine transformatio
n
, spec
tral regress
i
on
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. Prefix
High
dime
nsi
onal
data i
s
usu
a
lly prod
uce
d
by th
e
sou
r
ce that
only enjoy
s
a limited
numbe
r
of d
egre
e
s of fre
edom
(e.g.
many
he
ad i
m
age
se
que
nce
obtai
ned
only by
ch
a
nging
light and po
s paramete
r
s).
This kind of
data c
an be
thought of as having a lo
w-di
men
s
ion
a
l
manifold
emb
edde
d, an
d t
he d
egree
of
the fre
edom
i
s
the
intri
n
si
c dime
nsio
nali
t
y. By unfolding
the manifold,
the influential
factor
ca
n b
e
ob
se
rv
ed. In re
ce
nt years, many te
ch
nique
s [1-6]
are
prop
osed to
distill the
em
bedd
ed l
o
w-d
i
mensi
onal
m
anifold. Th
ese alg
o
rithm
s
avoid the
curse
of
dimen
s
ion
a
lity and have
been
su
ccessfully applie
d
to the fields of high
-di
m
ensi
onal d
a
ta
visuali
z
ation,
data com
p
ression, data
cla
ssifi
cation, co
rre
sp
ond
en
ce
learnin
g
[7].
Corre
s
p
onde
nce
lea
r
nin
g
is p
r
ima
r
ily
inspectin
g
t
he inn
e
r correspon
den
ce
between
data set
s
, learnin
g
the share
d
latent stru
ct
ure, an
d finding the
mapping
rel
a
tionship. Gi
ven
some
paired
corre
s
p
ondin
g
points, if the two hi
g
h
di
mensi
onal d
a
t
a sets
can b
e
mapp
ed int
o
a
global lo
w-di
mensi
onal
sp
ace, the rel
a
tionshi
p
between them ca
n be inspe
c
ted cle
a
rly. This
pro
c
ed
ure is
somethi
ng li
ke aligni
ng the
manifold
s to
gether with
some give
n inf
o
rmatio
n. Th
ere
has b
een a b
ody of work related to this
probl
em. Ha
m et al[8] use
s
a glob
al La
place gra
ph [
2
] to
descri
be th
e l
o
cal
geo
metry stru
cture of
multiple
high
-dime
n
si
onal
data
sets, a
n
d
get thei
r lo
w-
dimen
s
ion
a
l embed
ding b
y
spect
r
al de
comp
ositio
n. Verbe
e
k et a
l
[9] use Ga
ussian p
r
o
c
e
s
s
reg
r
e
ssi
on to
learn the
sh
ared l
a
tent st
ructu
r
e
a
m
on
g data sets. Shon et al [1
0] use
s
exten
ded
Gau
ssi
an p
r
o
c
e
ss m
odel t
o
study the relation
ship
b
e
twee
n motio
n
data an
d the rob
o
tic ge
st
ure
data. Lafo
n
e
t
al [11] u
s
e
Diffusio
n
Ma
ps to
get
the
manifold
s
of different
dat
aset
s
sep
a
rat
e
ly,
then u
s
e Ny
strom
algo
rithm to find a
n
affine tran
sform
a
tion to
align them.
The alg
o
rith
m is
su
ccessfully applie
d to the pro
b
lem
s
o
f
lip-rea
d
ing
and imag
e ali
gnment. Bai
et al’s metho
d
is
simila
r to
Laf
on’s.
He
u
s
e
ISOMAP [5] to tra
n
sf
o
r
m
the e
m
bed
node
s
of gra
phs into
a m
e
tric
spa
c
e fo
r g
r
a
ph-m
a
tchi
ng.
Ho
wever, all
these te
ch
ni
que
s are no
n
-
linea
r, which
can
not give
a
clea
r m
appin
g
bet
wee
n
th
e traini
ng
dat
a an
d the
ali
gned
data. A
s
a
re
sult, th
ey have to
re
train
all data wh
en
a new poi
nt is co
ming.
A linear ma
ni
fold alignm
en
t algorithm b
a
s
ed o
n
affine
transfo
rmatio
n is propo
se
d
in this
pape
r. In this algorithm, th
e clea
r tran
sf
ormatio
n
bet
wee
n
origi
nal
sample
spa
c
e and the hid
den
spa
c
e
ca
n b
e
obtain
ed d
u
ring th
e trai
ning
step, which
ca
n be
use
d
to re
ali
z
e the fa
st a
nd
accurate out of sample tra
n
sformation.
Unli
ke
so
me
comm
on line
a
r su
bspa
ce l
earni
ng meth
ods
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 4, April 2014: 2559 – 2
564
2560
(PCA, LPP et al.) which
ca
n reflect the chara
c
te
r of only one data set, manifold alignme
n
t ba
sed
on affine tra
n
sformation
can
refle
c
ts
the com
m
on
cha
r
a
c
ter o
f
multiple da
ta sets. In o
u
r
approa
ch, the Lapla
c
ian
eigenm
ap
s [2] is used to get the nonli
near ali
gnme
n
t result, the
n
an
extended
sp
ectral
reg
r
e
s
sion
metho
d
[13, 1
4
] is used to
o
b
t
ain the
affine tra
n
sfo
r
ma
tion
para
m
eters. The effect o
f
our metho
d
is va
lidate
d
by image
sequ
en
ce a
lignment in the
experim
ents.
2. The Principle of Semi-superv
ised Affine Align
m
ent
Suppo
se, the
two high
-dim
ensi
onal d
a
ta
sets to be
al
ign are
1
,,
x
x
d
n
Xx
x
,
1
,,
y
y
d
n
Yy
y
, and they can be alig
ne
d together b
y
applying two sets of affine
transfo
rmatio
n paramete
r
s
x
T
,
y
T
. The
aligne
d low dimensio
nal
data set is noted
b
y
1
,,
z
z
d
n
Zz
z
(
x
z
dd
,
yz
dd
), where
x
Z
,
y
Z
r
e
sp
ec
tive
ly r
e
pr
es
e
n
t
th
e lo
w
-
dimen
s
ion
a
l maping
re
sult
of
X
,
Y
. In
the ideal case, the labeled m
a
chin
g point
s sho
u
ld be
mappe
d to th
e same point
in the
low-di
mensi
onal sp
ace, so we le
t
lx
y
Z
ZZ
to represe
n
t
the interse
c
tion of
x
Z
and
y
Z
.
l
is u
s
ed to
re
pre
s
ent the
n
u
mbe
r
of mat
c
hin
g
point
s, and the
numbe
r of points in
Z
is
zx
y
nn
n
l
.
The prin
ciple
of semi-sup
e
r
se
d af
fine alignment is
descri
bed a
s
Figure 1.
Figure 1. The
Principl
e of the Semi-sup
ervise
d Affine Alignment
3. Semi-sup
erv
i
sed Affin
e
Alignment
Algorithm
3.1. The Con
s
train
t
of La
place Gra
ph and Nonline
a
r Alignment
The La
pla
c
e
grap
h is
use
d
here to de
scribe
th
e lo
cal g
eomet
rical inform
atio
n of the
high-dimen
s
i
onal data. Th
ough the
r
e a
r
e many me
th
ods to defin
e
Lapla
c
e gra
ph, rand
om
walk
is u
s
e
d
he
re
for its inva
rian
ce
of tran
slati
on. Ge
nerally, let’s ma
ke
a
gra
ph to
de
scrib
e
the
hig
h
-
dimen
s
ion
a
l
data set
X
,
the conn
e
c
tion
stren
g
th of
i
x
,
j
x
in
X
is defined b
y
2
2
,e
x
p
/
2
xi
j
wi
j
x
x
, where
is
a scale p
a
rameter
.
L
e
t
i
denote th
e
colle
ction of
i
x
's
k
-
c
l
o
s
e
neigh
bors.,
,
i
xx
j
di
w
i
j
denote the density at the
neighbor of
i
x
,
then the approximate m
a
trix could b
e
written a
s
1
x
xx
LI
D
W
. Similarly
,
there is approximate matr
ix
1
yy
y
LI
D
W
for
Y
.
The a
pproximate error for
X
and
Y
is
described by
e
.
2
2
xx
y
y
F
F
eZ
L
Z
L
(1)
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Sem
i
-Supervi
sed Affine Alignm
ent
of Manifolds (Rui
Ji
a)
2561
Whe
r
e
F
.
deno
tes
F
r
o
beniu
s
no
rm. Let
x
S
,
y
S
as 0-1 sele
ction matrix satisfying
x
x
Z
ZS
,
yy
Z
ZS
, and
let
x
y
SS
S
,
{,
}
x
y
Ld
i
a
g
L
L
,
T
B
SL
SL
,
the formula (
1
)
c
o
u
l
d
b
e
written a
s
:
2
T
F
e
Z
SL
trac
e
Z
BZ
(2)
Whe
n
minimi
zing form
ula
(2), for the propo
se
of ensurin
g the
uniquen
ess of the solution,
z
T
d
Z
ZI
i
s
i
m
p
o
s
e
d
a
s
anothe
r re
stri
ction. The
best solution
for minimizi
n
g
formula
(2)
can
be obtain
e
d
by calculat
ing
B
's 2nd to
1
z
d
nd sm
allest eigenvalue respo
nding
eigenvectors.
Then the
best non-linea
r solution is
denoted as
x
Z
and
y
Z
.
3.2. Spectral
Regre
ssion
and Affine
Alignment
x
Z
,
y
Z
obtained above as t
h
e
b
e
s
t
s
o
l
u
t
i
o
n
can give the accu
rate coincidence
of
the matching
points. However
,
the
ma
pping is non
-linear and cannot be ap
plied to
a
new
testing point. In our method, spectral regre
ssio
n
[
1
3
]
is used to prese
r
ve the af
fine
transformation relationsh
i
p when aligning the man
i
fold.
For a n
o
rm
al
point
i
x
in
X
, we want to find
an affine tra
n
s
form
ation
x
T
, by
applyin
g
which the result
x
i
z
can mostly approximate to
the
best solution
x
i
z
in
x
Z
, that
is
:
1
i
x
ix
x
i
x
zT
z
(3)
The erro
r of approxim
ation
is den
oted a
s
:
2
2
1
i
x
ix
i
x
x
i
x
ea
T
z
(4)
Whe
r
e
x
i
a
is th
e parameter
influencing the coinciden
ce accura
cy of the matching points. Is
this paper
, it'
s
defined as:
1
x
il
xi
x
il
zZ
a
zZ
(5)
Her
e
is
a
const val
ue to
distin
gui
sh
different influ
ence b
e
twe
e
n
mat
c
hing
p
o
ints
and
un
-
matchin
g
poi
nts. The total approxim
ate error
can
be accumul
a
ted as:
2
xx
i
x
x
x
F
i
ee
T
X
Z
A
(6)
Whe
r
e
1
1
x
n
X
X
,
1
,,
x
xx
x
n
A
di
ag
a
a
.
Whe
n
minimi
zing formula (6), the optima
l
affine transf
o
rmatio
n ca
n be obtain
ed a
s
:
1
**
TT
TT
xx
T
Z
AA
X
XAA
X
I
(
7
)
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 4, April 2014: 2559 – 2
564
2562
Her
e
,
R
. Similarly,
1
**
TT
T
T
yy
TZ
A
A
Y
Y
A
A
Y
I
(
8
)
By applying
*
x
T
,
*
y
T
to
X
and
Y
, the optimal affine tran
sform
a
tion
for them are
**
1
1
x
xx
n
X
ZT
and
**
1
1
y
yy
n
Y
ZT
.
4. Experiments and
Disc
ussion
The expe
rime
nt of image seque
nce alig
nment
is u
s
e
d
here to vali
date the effectiveness
of our al
gorit
hm. COIL2
0
are d
a
ta set about ro
tatin
g
toys, and
CUbi
C Fa
cePi
x is data set about
head po
s. T
w
o imag
e se
quen
ce
s in COIL2
0
are
sho
w
e
d
in Figure 2, where each im
ag
e is
obtaine
d by rotating the to
y every 5 de
gree. It’s
clea
r that the em
bedd
ed ma
nifold is a
circul
ar.
Two ima
ge seque
nces in
CUbiC Fa
ce
Pix are sh
o
w
ed in Figure 3, where ea
ch image is ta
ken
from different
head po
s. It’s cle
a
r that th
e embed
ded
manifold is h
a
lf circl
e
.
(a) o
b
j1
(b) o
b
j2
Figure 2. Two
Image Sequ
ences of COIL20
(a) o
b
j1
(b) o
b
j2
Figure 3. Two
Image Sequ
ences of CUb
i
C FacePix
In the experi
m
ent, every d
a
ta set is
ran
domly
divided
into two pa
rts, one p
a
rt fo
r trainin
g
denote
d
by
small solid p
o
i
n
t, and a
not
her
part fo
r t
e
sting
den
oted by bi
g ho
llow p
o
int. T
hen
some mat
c
hi
ng points a
r
e
taken from the trainin
g
po
ints denote
d
by big solid p
o
int. By applying
the affine tra
n
sformation
o
b
tained i
n
trai
ning, t
he two
high-dimen
s
i
onal d
a
tasets can
be ali
g
n
e
d
in a glob
al lo
w-di
men
s
ion
a
l spa
c
e. Fo
r the contin
uo
us line
a
r
cha
r
acter
of affine tran
sform
a
tion,
the mappin
g
result of traini
ng point
s
and
testing point
s are m
e
lted togethe
r.
The Figu
re 4
is the alignin
g
result of tw
o image sequ
ences in
COI
L20. The affine align
algorith
m
can
find the em
b
edde
d manifo
ld of se
pa
rate
data set, and
the low-dim
e
nsio
nal d
a
ta i
s
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Sem
i
-Supervi
sed Affine Alignm
ent
of Manifolds (Rui
Ji
a)
2563
aligne
d ap
proximately tog
e
ther. Th
e Fi
gure
5 i
s
the
alignin
g
result of two im
age
seq
uen
ces in
FacePix. Th
e
mappi
ng
re
sult of testin
g
points and
training point
s are unifo
rmly
distri
buted, a
n
d
the mating po
ints are al
mo
st coin
cid
ed.
(a) o
b
j1
(b) o
b
j2
(c
) obj1
+
o
b
j2
Figure 4. Affine Alignme
n
t of COIL20
Da
taset
(a) o
b
j1
(b) o
b
j2
(c
) obj1
+
o
b
j2
Figure 5. Affine Alignme
n
t of CUbi
C
Fa
cePix Dataset
The
co
st tim
e
for proje
c
ting a
ne
w
po
int between
affine alig
nm
ent an
d
retra
i
ning i
s
listed in
Tabl
e 1. It’s cl
ea
r that the tim
e
for p
r
oje
c
ti
ng a n
e
w
po
int is la
rgely
cut off by ou
r
algorith
m
.
Table 1. The
Co
st Time for Projectin
g
a Ne
w Point
Dataset Affine
alignment(s)
R
etraining(s)
COIL20
2.1
4
e
1.4
1
e
CUbiC FacePix
7.
3
5
e
3.1
1
e
4. Conclusio
n
Semi-supe
rvi
s
ed ma
nifold
alignment b
a
se
d on affine transfo
rmat
ion pro
p
o
s
ed
in this
pape
r
simulta
neou
sly fulfils the two
req
u
i
reme
nts
of
manifold alig
nment and
re
taining
th
e
lin
ear
mappin
g
. It obtains the
cle
a
r map
p
ing
relation
ship b
e
twee
n the o
r
iginal
spa
c
e
and the alig
n
e
d
spa
c
e, a
nd th
e linea
r map
p
ing can b
e
use
d
to give
a fast and
accurate out of
sampl
e
map
p
i
ng
transfo
rmatio
n.
Referen
ces
[1]
Ro
w
e
is ST
, Saul
LK. Non
l
i
n
ear d
i
mens
ion
a
lit
y re
ductio
n
b
y
Loc
all
y
Li
near Em
bed
di
ng.
Science.
200
0; 290(
550
0): 2323
–2
326.
[2
]
Be
l
k
in
M, Niy
og
i
P.
La
plac
ia
n Ei
gen
maps
and
sp
ectral t
e
chn
i
qu
es for
embe
ddi
ng
an
d cl
usterin
g
.
Advanc
es in
N
eura
l
Informati
on Proc
essin
g
S
y
stem
s 1
6
, Vanco
u
ver, Ca
n
ada: T
he MIT
Press. 200
2:
585
–5
91.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 4, April 2014: 2559 – 2
564
2564
[3]
Z
hang Z
Y
, Z
h
a
HY. Princi
pa
l
Manifo
lds a
nd
Nonl
in
ear D
i
m
ensi
on R
e
d
u
cti
on vi
a L
o
cal
T
ange
nt Spac
e
Alig
nment. CSE-02-0
19, T
e
chnic
a
l Re
port, CSE, Penn Sta
t
e Univ. 200
2.
[4]
Donoho DL,
Grimes C.
He
ssian
ei
ge
n
m
a
p
s: New
l
o
ca
ll
y li
near
e
m
be
ddi
ng t
e
chn
i
q
u
e
s for
hi
gh-
di
me
nsio
nal da
ta
. Proceedi
ng
s of the Nation
al Acad
em
y
of
Scienc
es. 200
5; 102(2
1
): 742
6–7
43
1.
[5]
T
enenba
um J
B
, de Si
lva V,
Lan
gford J
C
. A glo
bal
ge
omet
ric frame
w
ork
for no
nli
n
e
a
r di
mensi
ona
li
t
y
reducti
on.
Scie
nce.
200
0; 290
(550
0): 231
9–2
323.
[6]
Lafon
S, Le
e
AB. Diffusio
n
maps
and
c
oarse-
g
rai
n
in
g:
A un
ified
fra
m
e
w
ork for
di
mensi
ona
lit
y
reducti
on, gr
ap
h p
a
rtition
i
ng,
and
data
set p
a
rameter
i
zatio
n
.
IEEE Trans
actions
on Pattern A
nalys
is
and Mac
h
in
e Intelli
ge
nce.
20
06; 28(9): 1
393
–14
03.
[7]
van d
e
r Maate
n
LJP, Postma
EO, van den
Herik HJ
. Dim
e
n
sio
nal
it
y
r
edu
ction: A compa
r
ative revi
e
w
.
IEEE Transactions on Patter
n
Analys
is and M
a
chi
ne Intel
lig
e
n
ce
. 200
7.
[8]
Ham J, L
ee
D, Saul
L.
S
e
misu
pervis
e
d
Alig
n
m
e
n
t of
Manifo
lds.
P
r
ocee
din
g
s of
the T
ent
h
Internatio
na
l W
o
rksho
p
on Arti
ficial Intel
lig
enc
e and Statistics
, Barbados. 2
0
05; 120-
12
7.
[9]
Verbe
e
k J, Vla
ssis N. Gaussi
an fie
l
ds for s
e
mi-superv
i
se
d regressi
on an
d
corresp
ond
en
ce
le
arni
ng.
Pattern Reco
g
n
itio
n.
200
6; 39(10): 18
64
–18
75.
[10]
Shon AP, Groc
ho
w
K,
H
e
rtzmann A, R
ao
R.
Lear
nin
g
sh
are
d
late
nt structu
r
e for i
m
a
ge sy
nthesis
an
d
robotic i
m
it
atio
n
. Advances i
n
Neura
l
Information Proc
essi
ng S
y
stems 20
, Vancouver, C
ana
da. 20
06
:
123
3–
124
0.
[11]
Lafon S, Kell
er
Y,
Coifman RR. Data F
u
sio
n
and Mu
lticue
Data Matchin
g
b
y
D
i
ffusio
n
Maps.
IE
EE
T
r
ansactio
n
s o
n
Pattern Ana
l
ysis and Mac
h
i
ne Intell
ig
ence.
2006;
2
8
(11): 178
4-17
97.
[12]
Bai
X, Y
u
H,
Ha
ncock E
R
.
Graph M
a
tchin
g
Us
ing
S
pectral
E
m
be
d
d
in
g a
n
d
Ali
g
nment.
17
th
Internatio
na
l C
onfere
n
ce o
n
Pattern Re
co
gn
ition, Cam
b
rid
g
e
,
2004: 39
8-40
1.
[13]
Cai
D, H
e
X,
Ha
n J.
Sp
ectral re
gress
i
on
for effici
ent r
egu
lari
z
e
d s
u
b
s
pace
le
arni
ng
. IEEE 11t
h
Internatio
na
l C
onfere
n
ce o
n
Comp
uter Visi
on, Rio d
e
Jan
e
iro, Brazi
l
. 20
07: 1-8.
[14] Cai D, He
X, Han J.
Spectral
regressi
on: A unifi
ed ap
pro
a
c
h for sparse s
ubsp
a
ce le
arn
i
ng.
IEEE 7th
Internatio
na
l C
onfere
n
ce o
n
Data
Min
i
ng, Omaha, Ne
brask
a
. 2007: 7
3
-82.
Evaluation Warning : The document was created with Spire.PDF for Python.