Algo i hm o Compu e a Minimal Leng h Basis o
Rep esen a i e Cocycles o Cohomology Gene a o s
Mabel Iglesias-Ham1,2, Edel Ga c´ıa-Reyes1,
Wal e G. K opa sch2and Roc´ıo Gonzalez-D´ıaz3
1CENATAV, Pa e n Recogni ion Depa men , Ha ana, Cuba.
2Vienna Uni e si y o Technology, Pa e n Recogni ion and Image P ocessing G oup, Aus ia.
3Uni e si y o Se ille, Applied Ma h Depa men , Spain.
{miglesias,ega cia}@cena a .co.cu,{k w,mabel}@p ip. uwien.ac.a ,[email p o ec ed]
Abs ac An algo i hm o compu e a minimal leng h basis o ep esen a i e cocycles o
cohomology gene a o s o 2D images is p oposed. We based he compu a ions on combina-
o ial py amids o eseeing i s u u e ex ension o 3D objec s. In ou esea ch we a e looking
o a mo e e ined opological desc ip ion o de o mable 2D and 3D shapes, han hey a e
he o en used Be i numbe s. We de ine con ac ions on he objec edges owa d he inne
o he objec un il he bounda ies ouch each o he , building an i egula py amid wi h
his pu pose. We show he possible use o he algo i hm seeking he minimal cocycles ha
connec he con ex de iciencies on a human silhoue e. We used minimali y in he numbe
o cocycle edges in he basis, which is a obus desc ip ion o o a ions and noise.
Keywo ks cohomology; combina o ial py amids; ep esen a i e cocycles o cohomology
gene a o s.
1 In oduc ion
The use o opological in a ian s is a p omising al e na i e in o de o desc ibe de o mable shapes
in 2D and 3D [16]. This has mo i a ed a lo o esea ch o ob ain e icien algo i hms on di e en
opological objec decomposi ions (simplicial complexes [3, 4], cubical complexes [12], i egula
py amids [15, 10], and o he s [8, 1]). Howe e , mos o he algo i hms a e looking o gene a o s
o homological g oups in o de o cha ac e ize he objec by he numbe o connec ed componen s
and holes (1-dimensional holes).
Pu suing a mo e e ined desc ip ion i is possible o use shape ea u es on he holes. Bu ,
usually he bounda ies o he holes a e se iously a ec ed by noise in eal wo ld applica ions o
image p ocessing and objec modeling [17]. The inal goal o ou esea ch, is o ind a new
desc ip o ha imp o es he lowe obus ness o he p esen objec opological desc ip ions.
Taking in o accoun he dual ela ionship be ween he homology and cohomology [6], we in end
o show ha a e ined desc ip ion based on he minimal leng h basis o cocycle is mo e obus o
noise and can be used o e alua e he simila i y be ween objec s in 2D and 3D.
The ep esen a i e cocycles ha we e compu ed in an i egula g aph py amid be o e [5],
associa ed o a pa h in he Region Adjacency G aph (RAG) going om one hole bounda y o
he ou side bounda y, can now be compu ed wi h minimal leng h. In his way, i can be used
as an s able ea u e o noise in he hole bounda y and o o a ions. Also, he associa ed pa h in
he RAG will now be ollowing s aigh lines as long as possible, and will be desc ibed wi h he
minimum numbe o edges needed.
The minimum basis o ep esen a i e cocycles o cohomology gene a o s a e he minimum
numbe o edges associa ed wi h pa hs in he RAG, connec ing all he holes bounda ies and he
ou side bounda y. I we conside he hole bounda ies and he ou side bounda y as nodes, and he
121
pa hs in he RAG as edges connec ing hose nodes, hen he minimal leng h basis o ep esen a i e
cocycles can be seen as a minimal spanning ee.
We selec ed as he unde line ep esen a ion combina o ial py amids due o 2D combina o ial
maps a e easily ex endable o 3D, whe e he p oposed algo i hm could be adap ed. The minimal
leng h cocycle basis can be used as a desc ip o o how s ong is a shape, wi h applica ions o
medicine in measu ing s eng h o bone s uc u es.
In Sec ion 2 a ecall abou combina o ial py amids is gi en. In Sec ion 3 he new algo i hm
o compu ing he minimal leng h basis o ep esen a i e cocycles is p esen ed. Then, in Sec ion
4 we show expe imen al esul s ollowed by conclusions and u u e wo k in Sec ion 5.
2 Recall: Combina o ial Py amids
A Combina o ial Py amid is an I egula G aph Py amid whe e each le el in ep esen ed by a
Combina o ial Map. The Combina o ial Maps a e encoding he opology o he o iginal da a.
E e y le el ep esen s a educed ep esen a ion o he le el below, and in gene al o he base le el
ep esen ing he da a in de ail. On op le el is he minimal opologically equi alen ep esen a ion
o he ini ial da a.
A 2D combina o ial map is de ined by a iple M = (D,β1,β2) whe e D is a se o da s and β1
and β2a e wo pe mu a ions. The in ui i e way o unde s anding his ep esen a ion is s a ing
wi h a g aph, we spli each edge in wo da s and he se o all he da s is named D. Then, β1
wo ks as a connec ion be ween he wo da s ha belongs o he same ini ial edge. I we ha e and
edge d ha was spli in da s d1and d2, hen β1(d1)=d2and β1(d2)=d1. (See Fig. 1)
Figu e 1: Example o a agmen o a combina o ial map. The da s ob ained om he edges
a ound he cen e e ex a e labeled o demons a ion.
The second pe mu a ion β2encodes he o de o da s a ound a e ex clockwise. In he
example o he igu e o he cen e e ex he esul o applying he second pe mu a ion is shown
in he able 2.
Figu e 2: Table shows he esul o applying he β2pe mu a ion o e he da s a ound he cen al
e ex in Fig. 1
We can ob ain all he da s a ound a ace in coun e -clockwise o de applying al e na i ely he
wo ope a ions as shown in he Fig. 3. A e ex in a le el lo a py amid ep esen s a se o e ices
in he base le el ( ecep i e ield). This se o e ices ha e been con ac ed o join o a single one
by successi ely applying con ac ions o neighbo ing simila e ices on e e y in e media e le el
122
up o l. A e joining o con ac ing a pai o e ices, he edge in be ween disappea s. In gene al
a e applying he se o con ac ions in one le el a numbe o edges disappea . The es o he
edges encodes he opology o he ep esen ed da a bu wi h possible edundancies. The ope a ion
o elimina ing he edundan edges is called simpli ica ion. A his poin , he emaining edges
su i es o he nex le el and a e called b idges. B idges p oduces a new edge in he nex le el,
connec ing su i ing nodes p oduc o he con ac ion o i s end poin s. The in e es ed eade can
ind mo e de ailed p ope ies and de ini ions in [11, 13, 2].
Figu e 3: Al e na i e applying he wo pe mu a ions leads o a a e sal o all he da s a ound a
ace.
We call he in ini e ace o he one ha gi es all he da s in he ou side o he image,
which a e bounding he in ini e o unknown ace. Finally, he e is some p e ious wo k showing
he py amid can be cons uc ed wi h log(m) heigh in he numbe o e ices in he base le el.
(See [14, 7]).
3 Algo i hm o Compu e a Minimal Basis o Cohomology
S a ing om a whi e and black image, we i s build a combina o ial map which is ini ialized in
he aces wi h he colo o he espec i e pixel plus a label iden i ying he bounda y i is adjacen
o. In he case o inside aces, he label is ini ialized in ze o (See Fig. 4). In he igu e (b), black
pixels ep esen inside aces, and he es o he o eg ound pixels (no whi e pixels), a e iden i ied
wi h di e en colo s depending o i s adjacen bounda ies.
a) b)
Figu e 4: Labeling o aces nex o bounda ies in he ini ializa ion s ep: a) o iginal image b) image
wi h bounda y labels.
In p inciple, he edges ha a e allowed o be con ac ed a e edges om he o eg ound egion
only, educing he numbe o compu a ions. The aim o he me hod is o expand bounda y labels
un il hey mee i s closes bounda y (a cocycle is ound) aking in o accoun he momen whe e a
cocycle basis is ob ained (all bounda ies a e connec ed wi h a spanning ee o pa hs in he RAG).
123
He e, simila adjacen e ices1a e he ones ha apply o wo p ope ies depending on i s
labels:
1. Only edges be ween aces wi h di e en labels can be emo ed, i.e. neighbo ing e ices wi h
di e en labels can be con ac ed.
2. Di e en labels ha a e al eady connec ed by a cocycle a e no conside ed di e en anymo e,
i.e. neighbo ing e ices wi h di e en labels ha a e al eady connec ed by a cocycle can
no be con ac ed anymo e2.
In his way, he no ion o simila e ices is de e mined by he alues o i s labels. We only
conside he g ay alue o he inpu image (bina y) o iden i y he o eg ound egion. A e he
ini ial labeling o he o eg ound egion, he decision o wha a e conside ed neighbo ing simila
e ices o be con ac ed is de e mined by he condi ions desc ibed abo e. Following hose ules,
he con ac ions will be desc ibing expansions o he bounda y labels, un il hey mee in he closes
ones. As a esul , he cocycle basis will be made o cocycles wi h minimum leng h.
When wo aces a e con ac ed, he su i ing ace will keep he label o he expanded bounda y
label o an a bi a y one om he child aces in case o a bounda y mee ing (cocycle ound).
Remo als o deg ee wo e exes a e no allowed he e, as hey a e ep esen ing di e en possible
ways o ex ending he ac ual pa hs o he cocycles.
In o de o keep ack o he u u e cocycle, e e y ace will sa e he index o he exi edge o
he pa h ha a i es o i . In he case o a ace ep esen ing a pixel nex o a bounda y, i s exi
edge will be he one ha sepa a es he ace wi h he backg ound. A e a con ac ion, he new
ace labeled (bounda y label expansion) will be sa ing he exi edge as he con ac ed one. Then,
when a cocycle is ound we sa e as a cocycle he mee ing edge and he aced exi edges s a ing
om bo h mee ing aces.
4 Expe imen s
In his sec ion we show some examples o minimal cocycle basis ob ained om es images and
a human silhoue e. In igu e 5 we show he base le el combina o ial map om a sample image.
Edges in ed show he ones belonging o he cocycle basis wi h minimal leng h compu ed.
Figu e 5: In ed he edges belonging o he minimal leng h cocycle basis o cohomology is shown.
In igu e 6 we show he esul o an image and i s o a ed e sion. No ice ha e en hough
he edges ha belong o he cocycle basis changes, he leng h in he numbe o edges o he esul
emains he same.
1 e ices ep esen ing a pixel o ace, in o de o keep he same no a ion o he igu es.
2They a e conside ed he same label om his momen on.
124
a) b)
c) d)
Figu e 6: Minimal cocycle basis o image in a) and i s o a ed e sion c) a e shown in b) and d)
espec i ely. Di e en colo s ( ed and blue) iden i ies di e en cocycles.
Finally, in igu e 7 we show an example o a minimal basis o cocycles compu ed on a human
silhoue e. In his case, as he human silhoue e does no con ain many holes, we conside a
p ep ocessing s ep whe e i s con ex de iciencies will be he new holes [9]. Fo doing ha , all
poin s ou side he con ex hull o he human silhoue e, and inbe ween he op and he bo om o
he silhoue e heigh , will become o eg ound (see Fig. 7 b)). In his way, he compu ed cocycles
wi h go inside o he o iginal human shape connec ing he con ex de iciencies h ough i s closes
poin s (see Fig. 7 c)).
5 Conclusions
In his pape we p esen ed an algo i hm o ob ain he minimal leng h basis o ep esen a i e
cocycles on a combina o ial py amid om 2D images. We show he use o he algo i hm seeking
he minimal cocycles ha connec s he con ex de iciencies o he human silhoue e. The new
ea u e is obus o noise and o a ions o he objec , and could ha e applica ions in a eas like
medicine o measu e s eng h o shapes like bones. In u u e wo ks we will y i s ex ensions o
3D objec s aking ad an age o he unde line objec ep esen a ion based on combina o ial maps.
Finally, we plan o include demons a ions ha p o es he edges associa ed o pa hs in he RAG
connec ing all he bounda ies a e in ac a basis o Cohomology.
Re e ences
[1] M. Allilli, D. Co i eau, and D. Ziou. Mo se homology desc ip o o shape cha ac e iza ion.
In 17 h In e na ional Con e ence on Pa e n Recogni ion, pages 27–30, 2004.
125

a) b) c)
Figu e 7: Minimal leng h cocycle basis compu ed o a human silhoue e wi h i s con ex de iciencies
as holes.
[2] Luc B un and Wal e G. K opa sch. Cons uc ion o combina o ial py amids. In GbRPR’03:
P oceedings o he 4 h IAPR in e na ional con e ence on G aph based ep esen a ions in pa -
e n ecogni ion, pages 1–12, Be lin, Heidelbe g, 2003. Sp inge -Ve lag.
[3] Del inado and Edelsb unne . An inc emen al algo i hm o be i numbe s o simplicial com-
plexes on he 3-sphe e. CAGD, 1995.
[4] J. G. Dumas, F. Heckendach, B. D. Saunde s, and V. Welke . Compu ing simplicial homology
based on e icien smi h no mal o m algo i hm. Algeb a, Geome y and So wa e Sys ems,
pages 177–206, 2003.
[5] Rocio Gonzalez-Diaz, Ad ian Ion, Mabel Iglesias-Ham, and Wal e G. K opa sch. I egula
g aph py amids and ep esen a i e cocycles o cohomology gene a o s. In And ea To sello,
F ancisco Escolano, and Luc B un, edi o s, P oceedings o he 7 h IAPR-TC15 In e na ional
Wo kshop on G aph-based Rep esen a ions in Pa e n Recogni ion, olume 5534 o LNCS,
pages 263–272, Venice, I aly, May 2009. Sp inge .
[6] Rocio Gonzalez-Diaz and Ped o Real. On he cohomology o 3d digi al images. Disc e e
Applied Ma hema ics, 147(2-3):245–263, 2005.
[7] Yll Haxhimusa, Roland Glan z, Maama Saib, Geo g Langs, and Wal e G. K opa sch. Log-
a i hmic ape ing g aph py amid, 2002.
[8] M. Hilaga, Y. Shinagawa, T. Kohmu a, and T. L. Kunii. Topological ma ching o ully
au oma ic simila i y es ima ion o 3d shapes. In SIGGRAPH01, pages 203–212, 2001.
[9] K opa sch W. G. Gonzalez R. Iglesias, M. and A. Ion. Objec classi ica ion by opology o
con ex de iciencies. Wo kshop on Compu a ional Topology in Image Con ex , 2009.
[10] Mabel Iglesias-Ham, Ad ian Ion, Wal e G. K opa sch, and Edel B. Ga c´ıa. Delinea ing ho-
mology gene a o s in g aph py amids. In 13 h Ibe oame ican Cong ess on Pa e n Recogni ion
(CIARP 2008), olume 5197 o LNCS, pages 576–584. Sp inge , 2008.
[11] Thomas Ille schko. Minimal combina o ial maps o analyzing 3d da a. Technical Repo
PRIP-TR-110, Vienna Uni e si y o Technology, Ins . o Compu e Aided Au oma ion, Pa -
e n Recogni ion and Image P ocessing G oup, 2006.
126
[12] T. Kaczynsky, K. Mischaikow, and M. M ozek. Compu a ional Homology. Sp inge , 2004.
[13] W. G. K opa sch. Building i egula py amids by dual g aph con ac ion. IEE-P oc. Vision,
Image and Signal P ocessing, 142, 6, 366-374 (1995).
[14] Wal e G. K opa sch, Yll Haxhimusa, Zygmun Pizlo, and Geo ge Langs. Vision py amids
ha do no g ow oo high. Pa e n Recogn. Le ., 26(3):319–337, 2005.
[15] Samuel Pel ie , Ad ian Ion, Wal e G. K opa sch, Guillaume Damiand, and Yll Haxhimusa.
Di ec ly compu ing he gene a o s o image homology using g aph py amids. Image and
Vision Compu ing, 27(7):846–853, 2009.
[16] S ina S ensson, Ca lo A celli, and Gab iella Sanni i di Baja. Cha ac e ising 3D objec s by
shape and opology. In Disc e e Geome y o Compu e Image y, olume LNCS 2886, pages
124–133. Sp inge -Ve lag, 2003.
[17] A. J. Zomo odian. Topology o Compu ing. Camb idge Uni e si y P ess, 2005.
127
128