Dissimila i y Measu es o Visual Pa e n Pa i ioning*
Raquel Dosil1, Xosé R. Fdez-Vidal2 and Xosé M. Pa do1
1 Dep. de Elec ónica e Compu ación, Uni . de San iago de Compos ela,
Campus Uni e si a io Su , s/n, 15782, San iago de Compos ela, Spain
[email p o ec ed], pa[email p o ec ed]
h p://www-g a.dec.usc.es/g upo/g upo.h m
2 Escola Poli écnica Supe io , Uni . de San iago de Compos ela,
Campus Uni e si a io, s/n, 27002, Lugo, Spain
[email p o ec ed]
h p://www.lugo.usc.es/~ eeps
Abs ac . We de ine a isual pa e n as an image ea u e wi h equency com-
ponen s in a ange o bands ha a e aligned in phase. A echnique o pa i ion
an image in o i s isual pa e ns in ol es clus e ing o he band-pass il e ed
e sions o he image acco ding o a measu e o cong uence in phase o ,
equi alen ly, alignmen in he il e ’s esponses ene gy maxima. In his pape
we s udy some measu es o dissimila i y be ween images and discuss hei sui -
abili y o he speci ic ask o misalignmen es ima ion be ween ene gy maps.
1 In oduc ion
The iden i ica ion and ex ac ion o ele an low le el ea u es in an image is o g ea
impo ance in image analysis. Field s a es ha meaning ul ea u es p esen some
deg ee o alignmen in he phase o i s spec al componen s [1]. In he RGFF ep e-
sen a ional model in oduced in [2] and ex ended in [3, 4], such ea u es a e called
isual pa e ns and de ined as pa e ns wi h alignmen in a se o local s a is ics along
wide equency anges. These me hods can de ec a wide a ie y o ea u es, like
ex u es, g a ing pa e s, blobs and symme ic and an isymme ic discon inui ies in
in ensi y, ex u e, and phase. They sha e a common scheme consis ing o he decom-
posi ion o he image in o elemen a y ea u es using a bank o log Gabo il e s ol-
lowed by he clus e ing o hese ea u es acco ding o some measu e o dissimila i y
among hem.
The dis ance used in [2] and [3] is inspi ed in biological p ocesses. I combines a -
en ion mechanisms and pooling o senso ou pu s. A en ion poin s a e iden i ied as
ene gy maxima. On hei pa , Dosil e al. [4] use a dis ance based on he no malized
mu ual in o ma ion o he il e ’s esponse ene gy, which is less compu a ionally
expensi e, less pa ame e ized and less dependen on he pe o mance o low le el
p ocesses like non-maxima supp ession and scale es ima ion. Mu ual in o ma ion I is
* The au ho s desi e o acknowledge he Xun a de Galicia o hei inancial suppo o his
wo k by means o he esea ch p ojec PGIDIT04TIC206005PR.
widely employed as a measu e o image dissimila i y in a ious ields o applica ion,
wi h g ea popula i y in medical image egis a ion [5, 6]. Howe e , we ha e ob-
se ed ha he beha io o I is no comple ely sa is ac o y o il e clus e ing. In
some cases i g oups e y dissimila equency ea u es. This is due o ha I ea s
in ensi y alues quali a i ely, inc easing wi h he concu ence o weak and s ong
maxima. I is an unde cons ained measu e o dependency since i makes no assump-
ions abou he kind o unc ional ela ion be ween he images –see [7] o a de ailed
explana ion.
Then again, a measu e ha allows a gene ic dependency be ween he images may
no be he mos app op ia e in all applica ions. In he speci ic case o il e ’s e-
sponses ene gy maps i seems ha he kind o dependency ha bes e lec s he ela-
ion be ween ea u es belonging o he same isual pa e n is linea unc ional. A
measu e o simila i y ha cons ains he allowed ela ions be ween wo images o a
linea ans o ma ion is he co ela ion coe icien . To es his assump ion, he e we
make a compa ison among a se ies o dissimila i y measu es, including dis ances
based on co ela ion coe icien , mu ual in o ma ion and he o iginal measu e p o-
posed in he RGFF.
In he nex sec ion he se o dissimila i y measu es be ween pai s o il e ed im-
ages is p esen ed. In sec ion 3, he me hod o isual pa e n pa i ioning is desc ibed.
Sec ion 4 p esen s an expe imen al s udy on he pe o mance o hese measu es in he
ask o isual pa e n pa i ioning. Sec ion 5 p esen s he conclusions de i ed om i .
2 Dissimila i y be ween Ene gy Maps
All measu es p esen ed he e a e de i ed om a simila i y measu e δ by applying o i
a ans o ma ion o enhance in e clus e dis ances, in e i s ange and map i o he
in e al [0, 1]. Wha ollows is he lis o p oximi ies δ and hei co esponden dis-
ances D δ. X and Y ep esen ene gy maps and M is numbe o bins in an his og am.
a) No malized mu ual in o ma ion [4, 5]
I H s ands o en opy, hen
),()()(),( whe e,
)()(
),(
2),( YXHYHXHYXI
YHXH
YXI
YXNI −+=
+
⋅= .
() ()
(
)
2
,1, YXNIYXDNI −= . (1)
b) Co ela ion a io η [7, 8, 9]
(
)
(
)
(
)
XYXXYXηVa |EVa 1)|(
2−−=
(
)
)|(),|(max1),( 22 XYηYXηYXDη−= (2)
c) Co ela ion coe icien
This measu e has in o accoun he sign o he co ela ion coe icien , so ha an image
and i s in e se ha e maximum dis ance
)Va ()Va (),Co (),( YXYXYXρ=
()
(
)
2
2),(11),( YXρYXDρ+−= (3)
e) Toussain ’s dis ance [9, 10]
∑+
−=
ji yxyx
yxyx
yx jPiPjiP
jPiPjiP
jiPYXT
,,
,
,)()(),(
)()(),(2
),(),(
()
)1(21wi h,),(1),( max
2
max +−=−= MTTYXTYXDT (4)
) Lin’s K di e gence [9, 10]
∑+
=
ji yxyx
yx
yxdi jPiPjiP
jiP
jiPYXK
,,
,
,)()(),(
),(2
log),(),(
()
()
)1(2logwi h,),(1),( max
2
max +=−= MMKKYXKYXD di di di Kdi (5)
g) Dissimila i y measu es on ene gy maxima.
A new dissimila i y measu e D*
δ is ob ained om each Dδ as ollows
),(),(
*YXDYXD δδ ′′
= (6)
whe e X’ and Y’ a e espec i ely X and Y a e non-maxima supp ession. Maxima a e
de e mined by compa ing each poin wi h i s neighbo s in he il e ’s di ec ion.
h) RGFF dissimila i y measu e [2]
Fo each ene gy map X, he se o i s maxima ΩX is de e mined. Fo each p in ΩX a
ec o T p o leng h Q o local s a is ics is measu ed. Then, o a gi en
β
> 0
( ) () ()
()
YTXTdYXYX
Ca d
YXD p
k
p
k
Q
kk
p
p
p
XX
,
1
),(,),(
)(
1
),(
1
/1 ∑∑ =Ω∈
=
Ω
=
ω
µµ
β
β
β
.
),(),(),( 22 XYDYXDYXDRGFF
ββ
+= . (7)
whe e
ω
X is he maximum Tk o e all ΩX and all X. The local s a is ics hey employ
a e local phase, no malized local ene gy and i s en opy, con as and s anda d de ia-
ion.
2.2 Compu a ional Cos o Dissimila i y Es ima ion
One o he main ad an ages o global measu es in ela ion o he RGFF measu e is
hei lowe compu a ional cos . In he ollowing, an analysis o he asymp o ic com-
pu a ional cos o he p esen ed app oaches is p esen ed.
Le us suppose ha he inpu da a a e a olume o dimensions N × N × N, ha ou
il e bank consis s o F il e s and ha he numbe o bins used o his og am calcula-
ions is M. The calculus o
ρ
is O(N 3) while he es ima ion o NI,
η
, T and K di in-
ol es he cons uc ion o he join his og am o he wo maps, which is O(N 3), and
he pos e io accumula ion o he con ibu ions o each bin in he his og am, which is
O(M 2). Supposing ha N and M a e o he same o de o magni ude, he cos o he
dissimila i y calcula ion is O(N 3). This mus be done o each o he F(F−1) pai s o
il e s, esul ing in a compu a ional cos o O(F 2·N 3).
In he case o he RGFF dis ance, he cos o he dissimila i y calcula ions is
O(F 2·N 6). This is due o he calculus o he neighbo hood o each a en ion poin and
he local s a is ics on i . The neighbo hoods a e ela ed o he scales o each maximum
and a e de ined as he dis ance om each ene gy maxima o he nea es minimum. In
high scale il e s he neighbo hood adius is in he o de o he image size. Hence, his
calcula ions a e O(N 3) and mus be done o each a en ion poin , i.e., O(N 3) imes,
and o each il e pai , i.e., O(F 2) imes. E en i he poin s o each neighbo hood
whe e s o ed, wha would ha e a memo y cos o O(F·N 6), he calculus o he local
s a is ics di e ences main ains a o al cos O(F 2·N 6).
3 Visual Pa e n Pa i ioning Me hodology
Visual pa e n pa i ioning o a 3D image consis s o he nex sequence o s eps:
1. Selec ion o ac i e bands–wi h high in o ma ion con en
2. Calcula ion o he ene gy maps co esponden o he ac i e il e s’ esponses
3. Measu e o dissimila i y be ween pai s o ene gy maps
4. Hie a chical clus e ing o he ene gy maps based on he dissimila i y ma ix
5. Visual pa e n econs uc ion by linea summa ion o clus e ene gy maps.
In he nex subsec ions hese p ocedu es a e de ailed.
3D Fil e Bank
The il e s’ ans e unc ion T is designed as he p oduc o sepa able ac o s R and S
in he adial and angula componen s espec i ely wi h exp essions
()
(
)
{}
)(log2)(logexp; 22
iii
R
ρσρρρρ
ρ
−= , (8)
whe e
σ
ρ
is he s anda d de ia ion and
ρ
i he cen al adial equency and
()
()
{}
)2(exp,;, 22
α
σααθφθφ
−== SS ii , wi h
(
)
⋅= acos),( ii
θφα
, (9)
whe e = (cos
φ
i cos
θ
i , cos
φ
i sin
θ
i , sin
φ
i) is a uni ec o in he il e ’s di ec ion,
σ
α
is he angula s anda d de ia ion and he poin in he equency space in Ca esians.
In ou con igu a ion ele a ion is sampled uni o mly, while azimu h is non-
uni o mly sampled by main aining equal a c-leng h be ween adjacen azimu h alues
o e he uni adius sphe e. The bank has been designed using 4 ele a ions −only one
hemisphe e is needed due o symme y− and 6 azimu hs o sample hal he z = 0 plane,
yielding 23 o ien a ions wi h angula bandwid h o 25º. In he adial axis, 4 alues
ha e been aken wi h wa eleng hs 4, 8, 16 and 32 and 2 oc a e bandwid h.
Selec ion o Ac i e Bands
To dec ease he compu a ional cos , he numbe o il e s is educed by disca ding
il e s wi h wa eleng hs g ea e han hal he image size, oughly ep esen ing he
a e age in ensi y, and wi h low in o ma ion con en , named non ac i e. The measu e
o in o ma ion densi y is E = log ( |F | + 1), whe e F is he image Fou ie ans o m.
A band is ac i e i i comp ises any alue o E o e he maximum spec al noise.
The maximum noise le el is es ima ed as m + x
σ
, whe e m is he mean noise ene gy,
σ
is i s s anda d de ia ion and x ≥ 0. He e, m and
σ
ha e been measu ed in he band
o equencies g ea e ha double he la ges o he bank’s cen al equencies and x =
3.
To elimina e emaining spu ious noise “spo s” a adial median ope a o is applied,
which only conside s neighbo s ha a e an e io o pos e io in he adial di ec ion o
calcula e he median. This elimina es isola ed peaks bu p ese ing he con inui y o
s uc u es along scales. In his wo k he mask size is aken o L = 3.
Fea u e Clus e ing
He e, hie a chical clus e ing has been chosen o g oup ea u es, using a comple e-link
algo i hm, whe e he dis ance be ween clus e s is de ined as he maximum o all pai -
wise in e clus e dis ances, hus p oducing compac g oups. The numbe o clus e s
Nc is an inpu pa ame e o he algo i hm. The usual s a egy o de e mine he op imal
Nc is o un he algo i hm o each possible Nc and e alua e he quali y o each esul -
ing pa i ion acco ding o a gi en alidi y index. He e, he modi ied Da ies-Boulding
index, in oduced in [9] has p o ed o p oduce good esul s. I is a g aph- heo y based
index ha measu es he compac ness o he clus e s in ela ion o hei sepa a ion.
4 Resul s
To compa e he pe o mance o he p esen ed dissimila i y measu es, he isual pa -
e n pa i ioning me hod desc ibed in sec ion 3 has been applied using each o hem o
a se o es images. The es bench is composed o 32 images, 13 o hem 2D and he
o he 19 3D. While i is qui e easy o de e mine i he esul s ob ained o a 2D image
a e co ec by isual inspec ion, his is mo e di icul o 3D images. Fo his eason,
all he 3D images in he bench a e syn he ic. The co ec ness o he esul s is de e -
mined by compa ing hem wi h he design speci ica ions. The esul mus con ain one
clus e o each isual pa e n in he image and hei equency bands mus ma ch he
expec ed ones. 2D cases a e ei he syn he ic images o na u al images wi h clea ly
iden i iable isual pa e ns o images syn hesized as a collage o na u al B oda z ex-
u es. In his las ype he esul mus con ain one clus e o each ex u e. Addi ion-
ally, hey may appea pa e ns co esponden o ex u e bounda ies.
The esul s ob ained a e summa ized in Fig. 1. The measu es ha e been so ed by
pe cen age o co ec esul s. I can be seen ha D ρ has he bes pe o mance, ol-
lowed by D NI. In gene al he esul s a e no e y good due o he complexi y o he
ask o ma ching same-pa e n equency ea u es, which p esen s ong di e ences –
hese esul s can no be ex apola ed o o he applica ions, like image egis a ion.
Fig. 2 shows one example esul o a 3D image ha p esen s di e se isual pa -
e ns: a g a ing pa e n, a plane –e en ea u e– and a phase change –odd ea u e. In
his speci ic case all he dis ances p oduce he co ec esul , excep om DT and D*
NI
which do no de ec he phase change.
The emainde igu es illus a e he imp o emen s b ough by he use o he D ρ
dis ance in ela ion o he o he measu es. Fig. 3 shows an example o 2D syn he ic
image. I can be seen ha he D*
NI dis ance g oups o hogonal g a ing pa e ns o-
ge he while D ρ sepa a es hem. This is caused by he non null esponse o he il e s
o pa e ns wi h o ien a ion o hogonal o i . Gi en ha NI does no conside he mag-
ni ude o he di e ence be ween he esponses o he il e s, he esul ing dissimila i y
is small. Fig. 4 shows a simila example wi h a na u al image o a B oda z ex u e.
Fig. 5 and Fig. 6 p esen o he cases we e D ρ co ec s D NI esul s. In Fig. 5 mu ual
in o ma ion is no able o sepa a e he ex u e inside he ci cle. Ins ead i decomposes
he ex u e o he ou e egion in o i s e ical and ho izon al componen s. In he ex-
ample o Fig. 6 he esul s o D NI a e no shown since hey a e a o al o 7 clus e s, as
he di e en componen s o each egion ha e no been co ec ly in eg a ed.
5 Conclusions
Visual pa e n pa i ioning makes e e ence o he p ocess o isola ion o he cons i u-
en low le el ea u es ha a e pe cep ually ele an in an image. I consis s o he
clus e ing o he equency componen s o he image acco ding o some dis ance
Fig. 1. Pe cen age o co ec (OK), inco ec (X) and indecisi e (?) esul s o each dis ance.
e lec ing he deg ee o alignmen be ween hem. In his pape we ha e discussed he
sui abili y o a se o dissimila i y measu es o his ask.
We ha e plan ed he assump ion ha he kind o dependency ha appea s be ween
he equency componen s o he same isual pa e n is a linea unc ional one. This
explains he inco ec esul s ob ained wi h measu es based on mu ual in o ma ion,
o he in o ma ion di e gences and co ela ion a io. Upon his assump ion we p edic
ha a measu e based on he co ela ion coe icien should yield be e esul s.
To es his hypo hesis he dissimila i ies ha e been es ed wi h a se o 2D and 3D
images. The esul s ob ained ha e shown ha he co ela ion coe icien dis ance
sol es he p oblems obse ed wi h mu ual in o ma ion and o he global dis ances and
imp o es he o iginal measu e p oposed in he RGFF in speed and pe o mance.
Re e ences
1. Field, D.J.: Scale–In a iance and sel -simila “wa ele ” T ans o ms: An Analysis o Na u-
al Scenes and Mammalian Visual Sys ems. In: Fa ge, M., Hun , J.C.R., Vassilicos, J.C.
(eds.): Wa ele s, ac als and Fou ie T ans o ms, Cla endon P ess, Ox o d (1993) 151-193
2. Rod íguez-Sánchez, R., Ga cía, J.A., Fdez-Valdi ia, J., Fdez-Vidal, X.R.: The RGFF Rep-
esen a ional Model: A Sys em o he Au oma ically Lea ned Pa i ion o “Visual Pa e ns”
in Digi al Images, IEEE T ans. Pa e n Anal. Mach. In ell., 21(10) (1999) 1044-1073
3. Chamo o-Ma ínez, J., Fdez-Valdi ia, J.A., Ga cía, J.A., Ma ínez-Baena, J.: A equency
Domain App oach o he Ex ac ion o Mo ion Pa e ns, in IEEE In e na ional Con e ence
on Acous ics, Speech and Signal P ocessing, Hong Kong, 3 (2003) 165-168
4. Dosil, R., Fdez-Vidal, X. R. and Pa do, X. M.: Mul i esolu ion App oach o Visual Pa e n
Pa i ioning o 3D Images. In Campilho, A. and Kamel, M., (eds.) LNCS 3211: Image
Analysis and Recogni ion, Po o, Po ugal (2004) 655-663
5. S udholme, C. Hill, D. L. G. and Hawkes, D. J.: An O e lap In a ian En opy Measu e o
3D Medical Image Alignmen . Pa e n Recogni ion, 32 (1999) 71-86
6. Viola, P. A.: Alignmen by Maximiza ion o Mu ual In o ma ion. Massachuse s Ins i u e
o Technology, A i icial In elligence Labo a o y, Technical Repo 1548 (1995)
7. Roche, A., Malandain, G. and Ayache, N.: Uni ying Maximum Likelihood App oaches in
Medical Image Regis a ion. In . J. o Imaging Sys ems and Technology, 11 (2000) 71-80
8. Roche, A., Malandain, G., Pennec, X. and Ayache, N.: The Co ela ion Ra io as a New
Simila i y Measu e o Mul imodal Image Regis a ion. In LNCS 1496: MICCAI’98,
Sp inge -Ve lag (1998) 115-1124
9. Sa u , D. and Migue S. Simila i y Measu es o Image Regis a ion. 1s Eu opean Wo k-
z = 0 x = 0 y = 0
Fig. 2. Top le : C oss sec ions o he o iginal 3D da a. Remainde : Sec ions o he h ee pa -
e ns isola ed using D
ρ
shop on Con en -Based Mul imedia Indexing, Toulouse, F ance (1999) 263-270
10. Basse ille, M.: In o ma ion: En opies, di e gences e moyennes. Technical Repo 1020,
IRISA, 35042 Rennes Cedex F ance (1996)
11. Pal, N.R., Biswas, J.: Clus e Valida ion Using g aph Theo e ic Concep s. Pa e n Recogni-
ion, 30(6) (1997) 847-857
Fig. 3. F om le o igh : O iginal image. One o he clus e s ob ained wi h D*
NI, ep esen ed
by he e−1/2 le el cu es o he il e s’ ans e unc ion. Pa e n associa ed o he p e ious
clus e . The wo pa e ns ob ained wi h Dρ
Fig. 4. F om le o igh : O iginal image. One o he clus e s ob ained wi h D NI, ep esen ed
by he e−1/2 le el cu es o he il e s’ ans e unc ion. Pa e n associa ed o he p e ious
clus e . The wo pa e ns ob ained wi h D ρ
z = 0 x = 0 y = 0
Fig. 5. Top: C oss sec ions o he o iginal 3D da a. Middle: Sec ions o he wo pa e ns iso-
la ed using D NI. Bo om: Sec ions o he wo pa e ns isola ed using D ρ
z = 0 x = 0 y = 0
Fig. 6. Top: C oss sec ions o he o iginal 3D da a. Bo om: The wo pa e ns isola ed using D ρ
