Algorithm to Compute a Minimal Length Basis of Representative Cocycles of Cohomology Generators

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