Extraction d’information homologique des objets discrets s’appuyant sur des graphes orientés

Jou nées du G oupe de a ail de géomé ie disc è e, Reims Image 2014 Ex ac ion d’in o ma ion homologique des obje s disc e s s’appuyan su des g aphes o ien és Aldo Gonzalez-Lo enzo1,2, Alexand a Bac1, Jean-Luc Ma i1e Ped o Real2 1Aix-Ma seille Uni e si é, CNRS, LSIS UMR 7296 (F ance) 2Uni e si é de Sé ille, Ins i u de Ma héma iques IMUS (Espagne) Résumé Tou obje disc e n-dimensionnel peu ê e ans o mé en complexe cubique, don on peu é udie les g oupes d’homologie pou mieux comp end e l’obje o iginal. Une app oche classique consis e à calcule la Fo me No male de Smi h de ma ices encodan le complexe cubique. Un ce ain nomb e de a aux dé eloppen des mé hodes pe me an de édui e la aille de ces ma ices. Dans ce a icle, nous p oposons une nou elle app oche, ini ialemen ondée su la héo ie disc è e de Mo se, calculan l’in o ma ion homologique (nomb es de Be i e cycles ep ésen a i s) sans u ilise la Fo me No male de Smi h. No e app oche s’applique en dimension quelconque e peu ê e u ilisée pou n’impo e quel ype de complexe cellulai e égulie . n-dimensional disc e e objec s can be in e p e ed as cubical complexes which a e sui able o he s udy o hei homology g oups in o de o unde s and he o iginal disc e e objec . The classic app oach consis s in compu ing he No mal Smi h Fo m o some ma ices ha encode he cubical complex. Fu he app oaches deal mainly wi h a p e-p ocessing o hese ma ices in o de o educe hei size. In his pape we p opose a new app oach, ini ially based on Disc e e Mo se Theo y, which compu es some homological in o ma ion (Be i numbe s and ep esen a i e cycles) wi hou calcula ing he No mal Smi h Fo m. I wo ks on any dimension, and i can also be applied o any kind o egula cell complex. Mo s clé : obje disc e , complexe cubique, homologie, héo ie de l’homologie e ec i e, héo ie disc è e de Mo se. 1. In oduc ion L’homologie s’es é élée comme un ès bon ou il pou la classi ica ion e la comp éhension des obje s disc e s, no- ammen quand ils on plus de ois dimensions. Elle ou ni une classe de desc ip eu s qui syn hé isen la s uc u e ba- sique de la o me considé ée. L’homologie o malise la no ion de « ou » dans un ob- je . On peu classi ie les « ous » pa leu dimension : les 0- ous son les composan es connexes; les 1- ous, les un- nels e les 2- ous, les ca i és. Le calcul de l’in o ma ion ho- mologique a pou bu , en e au es, de dé e mine le nomb e de ces ous (nomb e de Be i) e un ep ésen an de chacun (cycle ep ésen a i ou géné a eu d’homologie). Cela es e in ui i jusqu’à ois dimensions, mais en dimension qua e, on peu ou e des coe icien s de o sion dans les g oupes d’homologie, ce qui n’a pas une in e p é a ion in ui i e mais pe me cependan une classi ica ion des obje s. Le calcul de l’homologie nécessi e le choix p éalable d’un anneau de co- e icien s; a in de nous place dans le cas le plus géné al e de pou oi ob eni ces coe icien s de o sion, nous a ons choisi l’anneau des en ie s. Ce a ail s’appuie su deux app oches an é ieu es : la héo ie de l’homologie e ec i e [Se 92] e la héo ie disc è e de Mo se [Fo 02]. La p emiè e explici e le lien en e l’ob- je o iginal e ses g oupes d’homologie (mais s’a è e d’une complexi é éle ée, puisque basée su des ma ices ypique- men géan es de aille O(n2)où nes le nomb e de cellules du complexe). La deuxième app oche es en e anche ès simple e de complexi é beaucoup plus aible, mais ne pe - me pas oujou s de calcule l’homologie exac e. Dans ce a icle, nous p oposons une app oche qui com- bine ces deux héo ies, en en conse an les a an ages ou en dépassan leu s limi a ions espec i es. Nous cons uisons un obje qui géné alise le champ de ec eu s g adien disc e (ou il p incipal de la héo ie disc è e de Mo se) en au o i- san les cycles, ce qui pe me de calcule l’homologie exac e (e pas seulemen une app oxima ion). Tenan comp e de ces cycles, on ob ien la éduc ion (ou il p incipal de la héo ie de l’homologie e ec i e) elian le complexe cubique e ses c GéoDis 2014, G oupe de T a ail de Géomé ie Disc è e (h p://www.gd -im. ) Gonzalez-Lo enzo, A. e al. / Ex ac ion d’in o ma ion homologique des obje s disc e s s’appuyan su des g aphes o ien és g oupes d’homologie. Ce e éduc ion donne les géné a eu s de l’homologie. Ce e mé hode s’applique en dimension quelconque e à n’impo e quel ype de complexe cellulai e égulie . Pou plus de dé ails su l’é a de l’a e le con ex e an de la héo ie des complexes cellulai es que de l’homologie, le lec eu pou a se epo e à no e a icle [GLBMR]. 2. P éliminai es Dans ce e sec ion nous in oduisons les concep s néces- sai es. Un obje disc e de dimension nes un ensemble de cubes n-dimensionnels don le cen e a des coo données en iè es. Les complexes cubiques son p ésen és de maniè e dé- aillée dans [KMM04]. Un complexe cubique es un ype de complexe cellulai e don les cellules son des poin s (dimen- sion 0), des a ê es (dimension 1), des ca és (dimension 2), des cubes (dimension 3), e c. Le bo d d’une cellule de di- mension q(q-cellule) es l’ensemble de (q−1)-cellules de sa on iè e. Un complexe cubique peu ê e dé ini pa son diag amme de Hasse. C’es un g aphe o ien é où les somme s son les cellules du complexe, e les a cs on d’une cellule e s les cellules de son bo d. La açon la plus simple de dé ini un complexe cubique à pa i d’un obje disc e consis e à emplace chaque cube de l’obje pa une n-cellule a ec ses sous-cellules de dimen- sion in é ieu e. Une cons uc ion duale consis e à emplace chaque cube pa un poin (0-cellule) e ajou e des cellules de dimension supé ieu e selon la ela ion d’adjacence en e les cubes. Ce e de niè e cons uc ion u ilise moins de cellules, ce qui end les mé hodes de calcul de l’homologie plus pe - o man es. La igu e 1 mon e ces deux cons uc ions à pa i d’un même obje disc e . Un complexe de chaînes (C∗,d∗)es une séquence de g oupes C0,C1,... (appelés g oupes de chaînes) e d’ho- momo phismes d1:C1→C0,d2:C2→C1,... (appe- lés opé a eu s di é en iels ou de bo d) elle que dq−1dq= 0,∀q>0. On peu cons ui e une complexe de chaînes à pa - i d’un complexe cubique : les g oupes de chaînes son les g oupes lib es engend és pa les cellules de chaque dimen- sion ; l’opé a eu de bo d su une cellule donne une combi- naison linéai e des cellules de son bo d. La o mule exac e es explici ée dans [KMM04]. Le q-ème g oupe d’homologie du complexe de chaînes (C∗,d∗)es le g oupe quo ien H(C)q=ke (dq)/im(dq+1). Ce g oupe es isomo phe à Zβq×Z/λ1Z×Z/λ2Z×... ×Z/λ Z, où chaque λidi ise λi+1.βqes le q-ème nomb e de Be i e λ1,...,λ son appelés coe icien s de o sion. Rappelons que si le complexe cubique es de dimension 3, il n’y a pas de coe icien s de o sion. La héo ie de l’homologie e ec i e in odui la no ion de éduc ion : é an donné deux complexes de chaînes (C∗,d∗) e (C0 ∗,d0 ∗), une éduc ion es un iple d’homomo phismes (h∗, ∗,g∗) el que : —hq:Cq→Cq+1pou chaque q≥0 — q:Cq→C0 qes un mo phisme de chaînes ( d =d0 ) —gq:C0 q→Cqes aussi un mo phisme de chaînes (gd0=dg) —g =1−dh −hd — g =1C0 —hh =h =hg =0 Une éduc ion es une so e de simpli ica ion d’un complexe de chaînes (le deuxième complexe con ien no malemen des g oupes don les bases son plus pe i es) p ése an l’in o - ma ion homologique e ou nissan un lien en e le complexe ini ial e le complexe simpli ié. Quand le deuxième com- plexe es su isammen simple pou ne plus con eni que les g oupes d’homologie, il ou ni alo s les géné a eu s d’ho- mologie du complexe ini ial. Dans la sui e de ce e pa ie, nous p ésen ons b iè emen les no ions de base de la héo ie disc è e de Mo se. Pou une in oduc ion plus igou euse, le lec eu pou a consul- e [Fo 02]. Un champ de ec eu s disc e (disc e e ec o ield, DVF) su un complexe cubique es un couplage su son diag amme de Hasse, c’es -à-di e un sous-g aphe de ce de nie don au- cune des a ê es ne pa age un même somme . É an donné un champ de ec eu s disc e V, le g aphe de Mo se es cons ui à pa i du diag amme de Hasse, en en e san les lèches du sous-g aphe V. Les lèches issues de Vson alo s appelées in ég ales, les au es, lèches di é en ielles. Un V- chemin es un chemin su le g aphe de Mo se qui al e ne des lèches in ég ales e di é en ielles. Ainsi, un champ de ec- eu s disc e qui ne con ien pas de V-chemins e més es un champ de ec eu s g adien disc e (disc e e g adien ec o ield, DGVF). Une cellule c i ique es une cellule non cou- plée dans le champ de ec eu s g adien disc e . L’un des ésul a s ondamen aux de la héo ie disc è e de Mo se es que le nomb e de q-cellules c i iques es supé- ieu ou égal au q-ème nomb e de Be i. Quand les nomb es de Be i coïnciden a ec le nomb e de cellules c i iques, on di que le champ de ec eu s g adien disc e es pa ai . Malheu eusemen , pou ce ains complexes cellulai es, un el DGVF n’exis e pas; on appelle alo s op imal un DGVF con enan un nomb e minimal de cellules c i iques (qui peu donc ê e supé ieu au nomb e de Be i). A pa i d’un champ de ec eu s g adien disc e , on peu calcule une éduc ion associée. On dé ini ou d’abo d l’opé a eu linéai e sui an : V(σ) = (hd(τ),σi· τ,(σ,τ)es dans le couplage 0,sinon où hd(τ),σies le coe icien de la cellule σdans la chaîne d(τ). On pose alo s : h(σ) = ∑k≥0V(1−dV)k(σ) = V(σ)+ h(1−dV)(σ) (σ) = (1−dh −hd)(σ) = (1−dV)(σ) g(σ) = σ (1) 3. No e app oche No e objec i es de dépasse les limi a ions de la héo ie disc è e de Mo se en ob enan l’in o ma ion homologique c GéoDis 2014. Gonzalez-Lo enzo, A. e al. / Ex ac ion d’in o ma ion homologique des obje s disc e s s’appuyan su des g aphes o ien és Figu e 1: Un obje disc e de dimension 3 e ses deux complexes cubiques associés. No ons que dans le deuxième il y a deux composan es connexes. exac e à pa i d’un champ de ec eu s g adien disc e ; c’es une app oche pu emen combina oi e (pa opposi ion aux app oches algéb iques) qui, de plus, encode une éduc ion sous o me de g aphe. Cependan , il a é é p ou é que dé e - mine un DGVF op imal dans le cas géné al es un p oblème NP [LLT03] e que pou ce ains complexes, il n’exis e pas de DGVF pa ai (pa exemple, la maison de Bing e le « dunce ha », oi [AFTV12]). Pou ésoud e ce p oblème, no e app oche epose su l’en ichissemen des DGVF pa des cycles (soigneusemen choisis e con ôlés). Nous appel- le ons ce ype de champ de ec eu s disc e un champ de ec eu s disc e homologique (homological disc e e ec o ield, HDVF). Sans en e dans les dé ails, no e app oche es la sui- an e : é an donné un obje disc e , nous cons uisons son complexe cubique associé e é ablissons un p emie champ de ec eu s g adien disc e quelconque. Puis, no e algo- i hme es basé su la co ec ion i é a i e de ce g aphe. Chaque co ec ion élimine deux cellules c i iques en en e - san un V-chemin en e elles, ce qui peu c ée des V-chemins e més. On peu à ou momen calcule la éduc ion asso- ciée au champ de ec eu s disc e homologique en u ilisan les o mules écu si es (1). Ob eni l’image pa hou d’une cellule σpa ce e o - mule écu si e e ien à ai e un pa cou s du g aphe de Mo se à pa i de σ. Puisque no e HDVF peu con eni des cycles, il es nécessai e d’a ê e le pa cou s au bon mo- men . Nous in oduisons la no ion de somme de con luence (somme où deux cycles o ien és se ejoignen ) pou é- soud e ce p oblème. No e pa cou s s’a ê e donc aux som- me s de con luence, p oduisan un sys ème d’équa ions li- néai es (illus é dans l’exemple sui an ), que nous ésol ons pou ob eni la aleu de hou en σ. À i e d’exemple, considé ons le complexe de la igu e 2. On peu no e qu’il y a ois V-chemins (en o ange) en e les deux cellules c i iques de dimension 1 e 2. Lo squ’on calcule d su la 2-cellule c i ique, on e- ou e la 1-cellule c i ique; s’il n’y a ai qu’un V-chemin en e elles, on pou ai donc les annule (comme en héo- ie disc è e de Mo se), c’es -à-di e, en e se ce V-chemin a in qu’elles ne soien plus c i iques. Cependan , dans ce exemple, il y a ois V-chemins en e elles. Il es donc néces- Figu e 2: Champ de ec eu s g adien disc e (en ouge) su un complexe cubique. Il y a ois cellules c i iques en bleu, une de chaque dimension. sai e d’en choisi un (ici, nous p enons le plus cou ), ce qui c ée deux cycles o ien és. Si l’on souhai e, à pa i de ce g aphe, calcule l’opé a eu h(ou ) on doi d’abo d dé e mine sa aleu su le somme de con luence (nommé c, ma qué en iole dans la igu e 3). On ob ien alo s une équa ion du ype : h(c) = 2·h(c)+ x⇒h(c) = −x(2) où xes la chaîne ob enue du an le pa cou s (non explici ée ici). Pa simple ésolu ion de ce e équa ion, on ob ien alo s la aleu de h(c), qu’on u ilise ensui e pou le calcul de hen ou e cellule σ(le pa cou s depuis σes a ê é au somme de con luence ce la aleu de h(c)es alo s subs i uée dans la o mule écu si e). Dans le cas géné al on ob ien une équa ion pou chaque somme de con luence, p oduisan ainsi un sys ème d’équa- ions linéai es. Une ois ce p ocessus de co ec ion e miné, le nomb e de cellules c i iques dans chaque dimension coïn- cide a ec les nomb es de Be i s’il n’y a pas de coe icien s c GéoDis 2014. Gonzalez-Lo enzo, A. e al. / Ex ac ion d’in o ma ion homologique des obje s disc e s s’appuyan su des g aphes o ien és Figu e 3: Le champ de ec eu s disc e (homologique) ap ès le en e semen du V-chemin. Le somme de con luence es ma qué pa un poin iole . de o sion. Le cas où il y a des coe icien s de o sion e- quie des explica ions plus p écises, mais n’appo e pas de di icul és supplémen ai es. En in, on peu ob eni les géné- a eu s d’homologie en appliquan =1−dh −hd su les cellules c i iques. Les igu es 4 e 5 mon en deux exemples classiques où nous calculons un champ de ec eu s disc e homologique. Le complexe (simplicial) pou le « dunce ha » a é é ob enu de [Hac]. No e algo i hme a é é implémen é en C++ a ec les lib ai ies DG al [DG ] e Eigen [Eig]. Figu e 4: Hau : un DGVF su la maison de Bing. Bas : le HDVF ap ès la co ec ion du DGVF p écéden . Il y a une seule cellule c i ique (en bleu). Figu e 5: Hau : DGVF su le « dunce ha » a ec ois cel- lules c i iques. Bas : le HDVF ap ès la co ec ion du DGVF p écéden . L’unique cellule c i ique es 1. Les deux cycles o ien és du g aphe de Mo se son a ichés en iole . 4. Conclusion Nous p ésen ons une géné alisa ion du champ de ec- eu s g adien disc e pou laquelle nous in oduisons un al- go i hme pe me an d’ob eni les nomb es de Be i ainsi que des géné a eu s d’homologie. No e ésul a n’es pas seulemen héo ique, mais une mé hode e icace de calcul de l’in o ma ion homologique. Dans les deux exemples bien connus de la maison de Bing e du « dunce ha », no e algo- i hme abou i à un nomb e co ec de cellules c i iques dans chaque dimension (co espondan aux nomb es de Be i). c GéoDis 2014. Gonzalez-Lo enzo, A. e al. / Ex ac ion d’in o ma ion homologique des obje s disc e s s’appuyan su des g aphes o ien és Ré é ences [AFTV12] AYALA R., FERNÁNDEZ-TERNERO D., VILCHES J. A. : Pe ec disc e e Mo se unc ions on 2-complexes. Pa e n Recogn. Le .. Vol. 33, Num. 11 (aoû 2012), 1495–1500. [DG ] DG al : Digi al geome y ools and algo i hms li- b a y. h p://dg al.o g. [Eig] Eigen. h p://eigen. ux amily.o g. [Fo 02] FORMAN R. : A use ’s guide o disc e e Mo se heo y. Séminai e Lo ha ingien de Combina oi e. Vol. 48 (2002), B48c. [GLBMR] GONZALEZ-LORENZO A., BAC A., MARI J.- L., REAL P. : Compu ing homological in o ma ion based on di ec ed g aphs wi hin disc e e objec s. [Hac] HACHIMORI M. : Simplicial complex li- b a y. h p://in oshako.sk. sukuba.ac.jp/ ~hachi/ma h/lib a y/index _eng.h ml. [KMM04] KACZYNSKI T., MISCHAIKOW K., MROZEK M. : Compu a ional Homology, ol. 157. Sp inge , 2004, ch. 2, 7, pp. 255–258. [LLT03] LEWINER T., LOPES H., TAVARES G. : Towa d op imali y in disc e e Mo se heo y. Expe imen al Ma he- ma ics. Vol. 12, Num. 3 (2003), 271–285. [Se 92] SERGERAERT F. : E ec i e homology, a su - ey. h p://www- ou ie .uj -g enoble. / ~se ge a /Pape s/Su ey.pd , 1992. c GéoDis 2014.