Pe sis en Homology o 3D Recons uc ion
E alua ion
An onio Gu ie ez1, Da id Monaghan2,
Ma ´ıa Jos´e Jim´enez1, and Noel E. O’Conno 2
1Applied Ma h Depa men , School o Compu e Enginee ing,
Uni e si y o Se ille,
Campus Reina Me cedes, 41012 Se illa, Spain
[email p o ec ed]
2CLARITY: Cen e o Senso Web Technologies,
Dublin Ci y Uni e si y, I eland
{da id.monaghan,noel.oconno }@dcu.ie
Abs ac . Space o oxel ca ing is a non-in asi e echnique ha is
used o p oduce a 3D olume and can be used in pa icula o he e-
cons uc ion o a 3D human model om images cap u ed om a se o
came as placed a ound he subjec . In [1], he au ho s p esen a ech-
nique o quan i a i ely e alua e spa ially ca ed olume ic ep esen a-
ions o humans using a syn he ic da ase o ypical spo s mo ion in
a ennis cou scena io, wi h ega d o he numbe o came as used. In
his pape , we compu e pe sis en homology o e he sequence o chain
complexes ob ained om he 3D ou comes wi h inc easing numbe o
came as. This allows us o analyze he opological e olu ion o he e-
cons uc ion p ocess, some hing which as a as we a e awa e has no
been in es iga ed o da e.
Keywo ds: oxel ca ing, olume econs uc ion, pe sis en homology,
e alua ion.
1 In oduc ion
Homology is opologically in a ian , meaning i is a p ope y o an objec ha
does no change unde con inuous (elas ic) ans o ma ions o he objec . Roughly
speaking, homology cha ac e izes “holes” in any dimension (e.g. connec ed com-
ponen s, unnels and ca i ies in a 3D space). Homology compu a ion can be
ca ied ou o e a combina o ial s uc u e called cell complex, which is buil up
by basic elemen s (cells ) o diffe en dimensions ( e ices, edges, aces, e c.). One
can ake ad an age o he combina o ial na u e o a digi al image (as a se o
oxels) o compu e homology by aking as inpu he (algeb aic) cubical complex
associa ed o he image. Pe sis en homology s udies homology classes and hei
li e- imes (pe sis ence) in he belie ha significan opological a ibu es mus
ha e a long li e- ime in a fil a ion (an inc easing nes ed sequence o subcom-
plexes). In his pape , we compu e pe sis en homology ia he Inc emen al and
Dec emen al Algo i hms o compu ing AT-models (see [5]), which allow o com-
bine an inc emen al wi h a dec emen al echnique in he case o a non-inc easing
M. Fe i e al. (Eds.): CTIC 2012, LNCS 7309, pp. 139–147, 2012.
c
Sp inge -Ve lag Be lin Heidelbe g 2012
140 A. Gu ie ez e al.
fil a ion, ha is, a sequence o subcomplexes. In he ollowing Sec ion, we de-
sc ibe he con ex in which we apply pe sis en homology compu a ion. Sec ion
3 is de o ed o ecall basic ools used in ou compu a ions. Sec ion 4 desc ibes
he applica ion o pe sis en homology o he e alua ion o he oxel ca ing
p ocess. We d aw some conclusions and ideas o u u e wo k in he las Sec ion.
2 Voxel Ca ing App oach
Space ca ing is a well-known me hod o cons uc ing h ee-dimensional models
o objec s om a se o images. The p ocess in ol es cap u ing a se ies o im-
ages o an objec , and, by analysis o hese images, de i ing a desc ip ion o he
shape o he objec . In pa icula , space (o oxel) ca ing ap oaches [2,3,9,11]
a e non-in asi e echniques ha allow he econs uc ion o a 3D human model
om he images cap u ed om a se o came as placed a ound he subjec . In
each image, fi s ly, he egion o in e es (subjec silhoue e) is segmen ed om
he backg ound by an au onomous adap i e “app oxima e median” backg ound
modelling algo i hm; hen a 3D bounding box is d awn a ound he subjec ’s ap-
p oxima e posi ion in 3D space. By using ex ac ed silhoue es om each image,
inconsis en oxels a e elimina ed om he defined olume, i e a ing h ough
each o he came as [9]. In [1], he au ho s p esen a echnique o quan i a i ely
e alua e spa ially ca ed olume ic ep esen a ions o humans using a syn he ic
da ase o ypical spo s mo ion in a ennis cou scena io. Such a quan ifica-
ion is based on he compu a ion o No malised Mean Squa e E o (NMSE)
o a g ound u h olumen ic econs uc ion (which has been conside ed a 50
came as, based on expe imen al obse a ion) agains any econs uc ion om
an in e io came a se up (wi h less came as han he se up used o ca e he
g ound u h). The aim o such an e alua ion is o somehow quan i y he ac-
cu acy o he 3D olume p oduced by he oxel ca ing p ocess wi h ega d o
he numbe o came as used. This in es iga ion was mo i a ed by he ac ha
e y li le wo k has been done o da e on e alua ing he quali y o space ca ing
esul s. In his pape , we in end o gi e a diffe en insigh in o he oxel ca ing
wo k by homologically cha ac e ising he sequence o econs uc ion olumes.
This may be in e es ing as he su aces p oduced wi h a ew came as a e qui e
noisy wi h many holes, which a e i ele an opological in o ma ion ha can be
disca ded by using pe sis en homology. Gi en he na u e o he ca ings, we
belie e ha a homology-based app oach is a mo e app op ia e quan ifica ion
han he ela i ely simple NMSE-based app oach used p e iously.
3 Homology Compu a ions on a Se o Voxels
Acell complex is a gene al opological s uc u e by which a space is decomposed
in o basic elemen s (cells) o diffe en dimensions, which a e glued oge he by
hei bounda ies (see a o mal defini ion o CW-complex in [8]). Due o he
na u e o ou inpu da a, we ocus on a special ype o cell complex: cubical
complex. A cubical complex Qin R3, is gi en by a fini e collec ion o p-cubes
Pe sis en Homology o 3D Recons uc ion E alua ion 141
Fig. 1. Voxel ca ing app oach o 3D econs uc ion. P ocess wi h 4 came as a ound
he subjec and an o e head came a.
such ha a 0-cube is a e ex, a 1-cube is an edge, a 2-cube is a filled squa e (we
call i , simply, a squa e) and a 3-cube is a filled cube ( esp. a cube); oge he
wi h all hei aces and such ha he in e sec ion be ween wo o hem is ei he
emp y o a ace o each o hem.
We conside Z/2 as he g ound ing o algeb aic compu a ions, since we do
no need o deal wi h o sion. The cubical chain complex associa ed o he cubical
complex Qis he collec ion C(Q)={Cp(Q),∂
p}pwhe e:
(a) each Cp(Q) is he co esponding chain g oup gene a ed by he p-cubes o Q,
o e Z/2;
(b) he bounda y ope a o ∂p:Cp(Q)→Cp−1(Q) connec s wo immedia e
dimensions. The bounda y o a p-cube is he o mal sum (mod 2) o all i s
ace s (p ope aces o maximal dimension). I is ex ended o p-chains by
linea i y.
Roughly speaking, he homology g oups o a cubical chain complex will be a
chain g oup whose elemen s a e equi alence classes o cycles, such ha i one cy-
cle can be ob ained om ano he by con inuous de o ma ion h ough he objec ,
hen hey a e homologous (o equi alen ). Fo example, wo e ices a e homolo-
gous i he e exis s a pa h h ough he objec be ween hem. Fo mally, a p-cycle
is a p-chain asuch ha ∂p(a)=0.I a=∂p+1b o some p+1-chainb hen ais
called a p-bounda y.Wesay ha wop-cycles aand ba e homologous i he e
exis s a (p+1)-chaincsuch ha a=b+∂p+1c. Define he p- h homology g oup
o be he quo ien g oup o p-cycles mod p-bounda ies deno ed by Hp(Q). Each
elemen [a]o Hp(Q) is a quo ien class ob ained by adding each p-bounda y
oagi enp-cycle acalled a ep esen a i e cycle o he homology class [a]. The
homology o Qis he chain g oup H(Q)={Hp(Q)}p. See [10] o u he de ails.
3.1 Inc emen al-Dec emen al Algo i hms o Compu ing Pe sis en
Homology
We ocus on homology compu a ion me hods based on he concep o AT-model
[7]. Gi en a cell complex, Inc emen al Algo i hm o compu ing AT-models [7]
142 A. Gu ie ez e al.
compu es homology in o ma ion o he cell complex by an inc emen al echnique,
conside ing he addi ion o a cell each ime. Once homology o an objec has been
compu ed, he same algo i hm can be used again o upda e homology in o ma-
ion i new cells a e added o he exis ing complex; Dec emen al Algo i hm o
compu ing AT-models [6] can be used o he same aim, in he case ha some
cells a e dele ed.
Gi en a cubical complex Q, an algeb aic- opological model (AT-model [7]) o
Qis a se o da a (Q, H, , g, φ), such ha :
–Qis he cubical complex i sel .
–His a subse o Q ha cha ac e izes he homology o Qby con aining a
p-cube o each p-homology class, o all p.In3D,Hcan only ha e poin s,
edges and squa es: each poin o H ep esen s a connec ed componen o Q,
each edge ep esen s a “ unnel” and each squa e ep esen s a “ oid” (i.e. a
connec ed componen o he backg ound inaccessible om he ou side).
– is a chain map om C(Q) oC(H). This map p o ides he equi alence
ela ion be ween cycles ( ha is, i wo cycles, aand b, a e equi alen , hen
(a)= (b)). Mo eo e , g(c)=c o any c∈H.
–gis a chain map om C(H) oC(Q). Fo each cube cin H,g(c)isa ep e-
sen a i e cycle o a homology class.
–φis a map om C(Q) oC(Q) ha is a chain homo opy (see [10]) om g
o he iden i y homomo phism on C(Q). This map can be seen as a kind o
bounda y in e se. Fo example, i cis a e ex, hen φ(c) is he pa h om c
o he e ex ∈Hhomologous o c.
Fig. 2. A simple example o execu ion o Inc emen al Algo i hm o compu ing AT-
models. a) The inpu cubical complex, a filled squa e wi h all i s aces (only he labels o
he e ices a e shown). b) The elemen s in H. c) The able wi h he in o ma ion ela ed
o ,gand φ. Read, o ins ance, (16) = 16, g(16) = 16, φ(16) = 0, φ(17) = 16 −17
(edge om 16 o 17).
In [5], he au ho s e isi he algo i hm o compu ing AT-models using an in-
c emen al echnique ha appea s in [7] (we will e e o i as he Inc emen al
Algo i hm) wi h he aim o se ing i s equi alence wi h pe sis en homology
compu a ion algo i hm [4,12]. Gi en a cubical complex Qassocia ed o a 3D
digi al image, conside a ull o de ing o i s cubes {c1,...,c
n}such ha i ciis a
Pe sis en Homology o 3D Recons uc ion E alua ion 143
ace o cj, heni<j; ake a nes ed sequence o subcomplexes ∅=Q0⊆Q1···⊆
Qn(a fil a ion o e Q) such ha Qi={c1,...,c
i}(no ice ha all he p ope
aces o cia e in Qi−1). Unde hese condi ions, Inc emen al Algo i hm can be
applied o compu e pe sis en homology o e he fil a ion.
See Fig. 2 as a simple example o execu ion o he Inc emen al Algo i hm o
compu ing AT-models.
Fig. 3. A simple example o execu ion o Dec emen al Algo i hm o compu ing an AT-
model (Q,H, ,g,φ
) a e emo ing a 2-cube ( he squa e 16 −17 −24 −23) om
Fig. 2.a. a) The ou pu cubical complex (only he labels o he e ices a e shown) a e
dele ing he squa e. b) The cubes in H. c) The able wi h he in o ma ion ela ed o
,gand φ.
Now, le (Q, H, , g, φ) be an AT-model o a cubical complex Qcompu ed by
he Inc emen al Algo i hm. Le cmbe a maximal cube o Q.ThenanAT-model
o Q=Q {cm},(Q,H, ,g,φ
), can be cons uc ed by he Dec emen al
Algo i hm gi en in [5], whe e i was edefined (wi h espec o he one o [6])
wi h he aim o ex ending he concep o pe sis en homology o objec s wi h a
fil a ion ha is no necessa ily inc easing.
See Fig. 3 as an example o execu ion o Dec emen al Algo i hm o compu ing
AT-models. No ice ha by emo ing he 2-cube om he ini ial cubical complex
on Fig. 2, a new homology class is c ea ed. The ou pu o he algo i hm is he
se (Q,H, ,g,φ
) ep esen ed in a able o m in Fig. 3.c).
Now, le ∅=Q0↔Q1↔···↔Qnbe a zig-zag il a ion, ha is, a sequence
o cell complexes such ha e e y wo consecu i e complexes diffe by a single cell
c, i.e. ei he Qi=Qi−1∪{c}o Qi=Qi−1 {c}. Then, one can compu e pe sis en
homology o e he fil a ion by combining he applica ion o Inc emen al and
Dec emen al Algo i hms depending on whe he a cell cis added o dele ed each
ime.
4 Pe sis en Homology o 3D Recons uc ion E alua ion
We a e conce ned wi h he applica ion o pe sis en homology compu a ion o
p o ide opological e alua ion o he 3D econs uc ion p ocess by he oxel
ca ing echnique. The new insigh could significan ly en ich he e alua ion made

144 A. Gu ie ez e al.
Fig. 4. 3D Recons uc ions using a) 4 came as and b) 10 came as. Rep esen a i e
cycles o homology a e highligh ed in bo h cases. c) Ba code associa ed o he whole
sequence o 3D econs uc ions wi h inc easing numbe o came as ( om 1 o 50). d)
3D econs uc ion using 50 came as, wha is conside ed he g ound u h model.
in [1] by means o NMSE quan ifica ion. Fo his aim, we mus conside he
sequence o diffe en 3D models, ob ained by oxel ca ing unde inc easing
numbe o came as, as a whole objec on which we ha e o se up a fil a ion
o e which o compu e pe sis en homology. This way, in pa icula , we can ge
an es ima ion o he minimum numbe o came as needed in o de o ob ain a
opologically co ec 3D model (which in gene al has only one connec ed com-
ponen and no unnels o oids).
We deno e by Rk he cubical complex associa ed o he 3D econs uc ion
oba ined using kcame as (which a e andomly chosen). S a ing om he fi s
econs uc ion R1(ob ained by “one ca ing” o he ini ial 3D bounding box), we
can use Inc emen al Algo i hm o compu e i s homology. No ice ha Rk+1 may
be ob ained om Rkby emo ing some oxels (cubes, oge he wi h all hei
aces in he cubical complex). This ac makes his con ex good o making
use o he Dec emen al Algo i hm o ge ing homology compu a ions h ough
inc easing numbe o came as. Bo h, Inc emen al and Dec emen al Algo i hms
p o ide all he pai s o cells esponsible o he c ea ion/des uc ion o homology
classes along he p ocess, wha allows o ollow he e olu ion o hese classes wi h
espec o ime, ha is, he numbe o came as used. Ac ually, o compu e pe sis-
en homology o he whole sequence o 3D models, {Rk}k, he zigzag fil a ion is
gi en by he sequence {Rk}ki sel wi h he inclusion, be ween Rkand Rk+1,o
a sequence o complexes {Rik
k}ik=1...nkgi en by he addi ion o dele ion o a cell,
each ime. Compu e, hen, a big ba code o isualizing he hole compu a ion in
Pe sis en Homology o 3D Recons uc ion E alua ion 145
Fig. 5. 3D Recons uc ions ( iewed om diffe en angles) using diffe en numbe o
came as: a) 4 came as, b) 15 came as and c) 24 came as, which is simila o he one
ob ained wi h 50 came as (g ound u h model). Rep esen a i e cycles o homology a e
highligh ed. Below, ba code associa ed o he whole sequence o 3D econs uc ions
om 1 o 50 came as.
o de o easily analyze he s abili y o he elemen s o homology. We wan also
o ema k ha , due o he na u e o he oxel ca ing p ocess, only oxels on he
su ace o he objec a e emo ed each ime, so diffe en connec ed componen es
and unnels (bu no ca i ies) may a ise.
We ha e used o compu a ion fi e diffe en ames ex ac ed om a 3D ideo
sequence wi h a oxel esolu ion o 4 cm, ha is, he spacing be ween each
oxel is 4 cm in he OX,OY and OZ di ec ions. This means 15,625 oxels
pe cubic me e. We ha e app ecia ed, as i was expec ed, ha simple poses
o he subjec p oduce simple ba codes while mo e complex poses gi e place
o mo e in e es ing homological in o ma ion. Fig. 4 shows ha he ca ing p o-
cess, in a case o simple pose, s abilizes a 10 came as (wi h a unique connec ed
componen ), while below ha poin , 3 diffe en unnels ha e been li ing o
some ime. Tha means ha , in o de o p oduce a opologically co ec model,
146 A. Gu ie ez e al.
a leas 10 came as a e needed. Fig. 5 eflec s a mo e complex pose, hough i
also co esponds o a 3D objec wi h one connec ed componen and no unnels
o oids. No ice he mo e complex ba code associa ed (in which 2 connec ed
componen s and 16 unnels a e ep esen ed) and, especially, he ac ha a
1–homology class is c ea ed a ime k= 15, ha pe sis s un il k= 23. So
s abiliza ion o one connec ed componen as final s a e, occu s much la e han
in he o me case.
We a e wo king also on o he app oaches:
–To compu e pe sis en homology o he sequence o 3D diffe ence complexes
{Dk}kwi h espec o he g ound u h model (R∞), whe e Dk=Rk R∞.
Now he ba code o he whole sequence will p o ide diffe en in o ma ion
abou he whole p ocess ha migh complemen he one gi en by he econ-
s uc ions hemsel es.
–To compu e pe sis en homology o he sequence o 3D complexes gene a ed
by he con ex deficiencies o each 3D econs uc ion, ha is, he complexes
ob ained by he subs ac ion o each 3D econs uc ion o i s 3D con ex hull.
5 Conclusions and Fu u e Wo k
Pe sis en homology compu a ion p o ides an in e es ing new insigh in o he
3D model econs uc ion p ocess explained in his pape . The e a e lo s o ideas
and expe imen a ion s ill o be in es iga ed. An impo an poin is o s udy he
dependence o he obse a ions on he esolu ion o he inpu da a. An al e na-
i e app oach could be o compu e some homology-based ea u es ex ac ed om
each econs uc ion Rkand o compa e hem agains a g ound u h model. These
ea u es should be measu able so ha a dis ance wi h espec o he g ound u h
model could be compu ed. These pa ame e s could be ex ac ed om he com-
pa ison o weigh ed his og ams o connec ed componen s ( o 0-homology s udy)
o minimal-leg h (in some sense) ep esen a i e cycles o 1-homology. Ano he
in e es ing ques ion a ises by fixing a ce ain numbe o came as and conside ing
he sequence o 3D econs uc ions along ime. Holes can be p oduced along ime
by diffe en mo emen s o he body ha should no be s able along he com-
ple e scene, so he homological analysis o oxel ca ing pe o mance o ideo
sequences could shed some ligh on he classifica ion o hese mo emen s.
Re e ences
1. Monaghan, D., Kelly, P., OConno , N.E.: Quan i ying Human Recons uc ion Ac-
cu acy o Voxel Ca ing in a Spo ing En i onmen . In: ACM MM, Sco sdale,
AZ, No embe 28 - Decembe 1 (2011)
2. B oadhu s , A., D ummond, T., Cipolla, R.: A p obabilis ic amewo k o space
ca ing. In: Con . on Compu e Vision, ol. 1, p. 388 (2001)
3. Culbe son, W.B., Malzbende , T., Slabaugh, G.: Gene alized oxel colo ing. In:
In e n. Wo kshop on Vision Algo i hms: Theo y and P ac ice, pp. 100–115 (1999)
Pe sis en Homology o 3D Recons uc ion E alua ion 147
4. Edelsb unne , H., Le sche , D., Zomo odian, A.: Topological pe sis ence and sim-
plifica ion. In: FOCS 2000, pp. 454–463. IEEE Compu e Socie y (2000)
5. Gonzalez-Diaz, R., Ion, A., Jimenez, M.J., Poya os, R.: Inc emen al-Dec emen al
Algo i hm o Compu ing AT-Models and Pe sis en Homology. In: Real, P.,
Diaz-Pe nil, D., Molina-Ab il, H., Be ciano, A., K opa sch, W. (eds.) CAIP 2011,
Pa I. LNCS, ol. 6854, pp. 286–293. Sp inge , Heidelbe g (2011)
6. Gonzalez-D´ıaz, R., Med ano, B., S´anchez-Pel´aez, J., Real, P.: Simplicial Pe -
u ba ion Techniques and Effec i e Homology. In: Ganzha, V.G., May , E.W.,
Vo ozh so , E.V. (eds.) CASC 2006. LNCS, ol. 4194, pp. 166–177. Sp inge ,
Heidelbe g (2006)
7. Gonzalez-Diaz, R., Real, P.: On he cohomology o 3D digi al images. Disc e e
Applied Ma h. 147(2-3), 245–263 (2005)
8. Ha che , A.: Algeb aic Topology. Camb idge Uni e si y P ess (2002)
9. Ku ulakos, K.N., Sei z, S.M.: A heo y o shape by space ca ing. In e n. Jou nal
o Compu e Vision 38, 199–218 (2000)
10. Munk es, J.: Elemen s o Algeb aic Topology. Addison-Wesley Co. (1984)
11. Sei z, S.M., Cu less, B., Diebel, J., Scha s ein, D., Szeliski, R.: A compa ison and
e alua ion o mul i- iew s e eo econs uc ion algo i hms. In: IEEE Con e ence on
Compu e Vision and Pa e n Recogni ion, ol. 1, pp. 519–528 (2006)
12. Zomo odian, A., Ca lsson, G.: Compu ing pe sis en homology. Disc e e and
Compu a ional Geome y 33(2), 249–274 (2005)