Articles tagués Javascript

L’art de dessiner des graphes

Publié par Pierre COUCHET dans 1. Généralités le 9 septembre 2017

“L’important n’est pas le but, mais le chemin qui y conduit.”

Lao Tseu

À priori, rien de plus facile que de tracer un graphe. Il suffit de prendre deux points et de les relier entre eux par un trait. Le point de départ et le point d’arrivée peuvent être nommés, A et B par exemple. Mais les choses se compliquent lorsque les points et les liens sont nombreux ou doivent contenir des informations supplémentaires. Un point peut être géolocalisé par exemple (Graphe 1, Graphe 2).

Maillage

Graphe 1 : Réseau géodésique français pour la réalisation de la carte d’État-major au 1/40 000 élaborée entre 1825 et 1866. http://buclermont.hypotheses.org/3231

paris-metro

Graphe 2  : Diagramme de Sankey 3D du flux de passagers dans le métro parisien par Etienne Come avec mapbox.com. http://www.comeetie.fr/galerie/sankeystif/index_map.html

Dérivé du grec ancien γράφος, gráphos « écrit ou dessiné», le graphe correspond à un ensemble de nœuds (sommets) reliés par des arêtes (arcs) qui servent de modèle pour décrire le réel et tenter d’en prédire certains comportements. Pour le mathématicien, les arbres, les chaînes, les réseaux et les cycles sont des sortes de graphes. Euler propose dès 1735 une étude pour décrire les chemins rendus possibles par les sept ponts de Königsberg desservant deux îles centrales de la cité. Il fonde ainsi la théorie des graphes, branche des mathématiques discrètes dont les applications s’étendent à de multiples domaines (Ghys 2010, Zeste de savoir 2016).

Les mathématiques proposent des abstractions si bien qu’un sommet peut symboliser n’importe quoi dans un ensemble. Classiquement, il peut s’agir d’une station de métro, d’un document d’archive ou de bibliothèque, d’une expression linguistique, d’une organisation, d’un objet, d’une molécule, d’un individu, d’une espèce, d’un composant électronique ou encore d’une table de données. Les arêtes indiquent des relations, des liens. Elles peuvent symboliser un trajet, un pont, un fleuve, une relation parentale, un lien hypertexte, une relation entre champs de tables dans une base de données. Globalement, la valeur d’un graphe dépend de sa capacité à décrire le réel et à répondre à des objectifs. Ainsi une carte routière devient plus intéressante lorsque des informations (des métadonnées) comme des limites de vitesse ou des lieux d’embouteillage sont liées aux arêtes. L’estimation de l’heure d’arrivée sera meilleure.

Lorsque les nœuds et les arêtes sont nombreux, on parle alors de réseau.  Des réseaux guident les transports des passagers et des marchandises (réseaux routiers, de voies navigables et aériennes), de l’énergie et des fluides (eau, gaz, électricité), de l’information (Internet, téléphonie, monnaie). Des réseaux sont susceptibles de montrer des dynamiques, de cohabiter, coopérer, fusionner ou bien d’entrer en compétition. Les graphes modélisent des actions guidées par des intentions, comme le montre l’arbre utilisé pour l’enseignement du secourisme (Graphe 3), la chaîne de production mise en place dans le cadre d’une fabrication automobile (Graphe 4), ou bien le graphe des flux de capitaux entre pays produisant des biens et les centres financiers offshore (Graphe 5). Basés sur l’expérience et la pratique, des graphes et des réseaux guident les jeux, l’apprentissage et l’action.

tableau-sst-1

Graphe 3 : Arbre de décision en enseignement du secourisme dans lequel les personnes et les objets sont symbolisées à l’aide de logos de couleurs significatives.

chaine_fabrication_auto

Graphe 4 : Les trois stades de la fabrication dans une chaîne automobile. Chaque avancée du produit sur la chaîne correspond à un cycle d’actions répétées localement de manière cyclique.

41598_2017_6322_Fig3_HTML

Graphe 5 : Centres financiers offshore: conduits et puits dans le réseau des propriétaires d’entreprises multinationales. https://www.nature.com/articles/s41598-017-06322-9/figures/3

L’informatique

En informatique, les graphes modélisent différentes choses. Des fréquences d’horloge rythment des circuits, synchronisent l’action de composants électroniques tels que des mémoires, des circuits logiques et des réseaux de machines. Des fichiers sont stockés dans des arborescences, alors que des bases de données sont dites relationnelles, orientées graphe (Neo4J) ou bien délivrent des graphes en réponse à des requêtes du type graphe, comme dans le cas des triple stores. Des formats tels que HTML, XML, TEI ou JSON fournissent une organisation de l’information interne en arbre binaire dans laquelle des marqueurs indiquent symétriquement l’ouverture et la fermeture d’un bloc.

Penser graphe (modéliser des relations, classer, normaliser, trouver un chemin optimisé) s’avère intéressant dans plusieurs cas de figure. Il peut s’agir d’un côté de respecter des formats largement adoptés. Cette opération rend possible l’interopérabilité, c’est à dire le partage d’objets numériques et leur lecture par des outils standards comme un navigateur par exemple. Il peut s’agir encore de créer de nouveaux standards comme sont amenés à le faire le W3C et d’autres organismes. Ainsi, le langage d’API GraphQL proposé en 2012 par Facebook détrônera-t-il peut être prochainement le protocole REST actuellement en usage. Comme pour les expressions de langage ou les achats, certains aspects sociaux semblent régir l’usage des langages et des formats informatiques.

L’histoire des matériels et des logiciels peut être évoquée avec un graphe. Quoi de plus facile que de copier ou développer une information numérique, particulièrement si celle-ci est en accès libre. Ainsi, l’étonnant logiciel Gource génère à partir des logs d’un gestionnaires de code source tel que « git » la vidéo d’un arbre animé, image de l’activité des développeurs d’un projet informatique. Linux, espèce d’un nouveau genre en constante évolution, se différencie pour former un arbre du type cladogramme (Graphe 6).

linux-timeline

Graphe 6 : La frise chronologique des distributions Linux : http://telecharger-linux.roozeec.fr/2010/11/01/la-timeline-des-distributions-linux/

Gestion des connaissances

genealogie-sciences

Graphe 7 : Une distribution généalogique des sciences et des arts principaux. Encyclopédie de Diderot, 1751.

Penser graphe s’avère de nouveau utile lorsque de vastes ensembles de connaissance doivent être gérés de manière professionnelle (Graphe 7). Succédant aux entrées des grandes encyclopédies du XVIIIème siècle, les articles de Wikipédia peuvent être considérés comme des feuilles liées entre elles d’un arbre de connaissance multilingue dont l’anglais s’avère être parfois la langue la mieux renseignée.

Dans le domaine des archives, Martin Grandjean (Grandjean 2014) considère que les dossiers, collections et documents d’archives sont des éléments d’un vaste graphe de connaissance. L’archive devient alors un entrepôt de savoirs dans lequel des sources primaires servent de preuve lors d’études historiques, géographiques (Leturcq 2016), généalogiques ou sociales. Au-delà des sciences de l’information, la gestion des savoirs concerne de nombreux domaines, incluant les bibliothèques, les musées, les disciplines académiques et l’industrie.

Triplet RDF

Graphe 8 : Un triplet RDF

L’idée principale du web sémantique est que toute connaissance peut être représentée sous forme d’un triplet RDF (Resource Description Framework) dans lequel un sujet est relié à un objet par un prédicat (Graphe 8). Des opérations logiques du type inférence deviennent alors possibles sur de multiples triplets éléments d’un même graphe stockés dans un triple store ou dans une base de donnée orientée graphe. Des ontologies écrites en OWL (Langage d’ontologie du web) formalisent la nature des nœuds (sujet ou objet) et des arêtes (prédicats). Le web sémantique devient alors complémentaire des traditionnels moteurs de recherche, introduisant des syntaxes d’interrogation spécialisées comme SPARQL.

Réseaux sociaux

Tout le monde a bien conscience de faire partie de plusieurs réseaux relationnels définissant des familles, des cercles, des communautés. Des groupes d’individus partagent des liens de parenté, des liens générationnels, des émotions, des langages, des lieux, des routines, des modes de vie et des événements, bref des cultures. 

Quelques réseaux classiquement étudiés par les historiens des sciences et les sociologues s’avèrent emblématiques. La «République des Lettres» s’étend de la Renaissance au Siècle des Lumières. Un espace d’échanges épistolaire et de rencontres dans des salons et académies réunit des littéraires et des scientifiques européens autour d’idées de diffusion de la connaissance. Sont éditées alors en italien, en allemand, en français, en anglais et en russe les premières encyclopédies. Plus de 150 érudits et savants ainsi que quatre éditeurs collaborent ainsi à l’Encyclopédie ou Dictionnaire raisonné des sciences, des arts et des métiers. D’Alembert et Diderot coordonnent l’édition de l’ouvrage publié en 1751. A cette même époque effervescente en matière de mouvement des personnes et de partage des savoirs, Voltaire et Locke entretiennent une volumineuse correspondance. Leurs réseaux de correspondance sont cartographiés (Dan Edelstein, 2010, Graphe 9). 

voltaire-locke

Graphe 9 : Correspondance de Locke en bleu et de Voltaire en orange avec Palladio

Moreno propose en 1934 l’usage du sociogramme pour décrire les relations sociales entre enfants de différentes classes d’âge placés en milieu scolaire. Un graphe décrit les relations amicales. Des graphes reflètent les structures de groupe telles qu’elles se développent et évoluent dans un groupe d’écoliers en période d’apprentissage (GrandJean 2014).

En 1967,  le psychosociologue Milgram élabore la théorie du « petit monde ». Son hypothèse de départ est que tout individu habitant les États Unis est relié à un autre par un nombre de relations interpersonnelles limité, de l’ordre de 6. Une expérience dans laquelle des personnes se transmettent de main à la main un document est effectuée afin d’éprouver la théorie.

Introduit dans les années 2000, le nombre d’Erdős enfin est un indicateur bibliométrique spécifique des mathématiques. Il évalue la distance d’un auteur dans le cadre de publications conjointes à Paul Erdős, le fameux hongrois aux 1500 articles et plus de 500 collaborations, théoricien lui-même du graphe aléatoire. Structurées en cycles, arbres et réseaux interconnectés, les sociétés apparaissent plus petites que notre intuition ne le laissait penser.

Le développement rapide d’Internet, des réseaux téléphoniques et du commerce en ligne ont focalisé l’intérêt sur la question des communautés sociales, professionnelles et marchandes. Wikipédia, Google, Facebook, Twitter, Amazon, Uber, AirBnB, Meetic et d’autres deviennent des objets d’études et le graphe s’impose comme outil de représentation des données, personnes ou bien objets et produits du commerce. Les résultats d’une recherche de livres sur Amazon, ou de vidéo sur Youtube sont ainsi visualisés sous forme de graphe (Graphe 10). Pour le théoricien McLuhan, en matière d’information le « message est le medium », en matière de communication le « village est global ».

aws-graph

Graphe 10 : Recherche chez Amazon des livres en anglais relatifs à la visualisation des graphes. Exploration de vidéos sur YouTube. Les résultats sont présentés sous forme d’un graphe avec le framework javascript VivaGraphJS d’Andrei Kashcha. Changez de sujet à l’aide du formulaire situé en haut à gauche de la page.

Biologie

Terminons ce rapide tour d’horizon des graphes et de quelques unes de leurs applications par un mot de biologie. Des graphes sont utilisés pour modéliser le fonctionnement de différents appareils et systèmes chez l’homme et l’animal comme l’appareil circulatoire, respiratoire, urinaire ou le squelette. Des maladies infectieuses se propagent en suivant les logiques des réseaux sociaux (Basileu 2012). Transitant par des plaques tournantes modulaires, des réseaux de neurones transmettent un flux nerveux à la base de la pensée, de la communication et des mouvements moteurs. Les interactions entre protéines peuvent encore être décrites à l’aide de graphes, à l’aide de services web tels que Gene Cloud par exemple. Darwin confronté à l’évolution dans le temps des espèces imagine dès 1837 le cladogramme (Graphe 11), objet principal de la cladistique. 

darwin-1837

Graphe 11 : « Transmutation Notebook B » – I think, juillet 1837, Darwin, Archives de Cambridge

Art et symbolique

A quoi sert le graphe ? Tout comme le dessin, l’écriture ou une équation mathématique, le graphe est susceptible de décrire le réel voire l’imaginaire et les relations qui les constituent. Les symboliques du graphe s’avèrent multiples. Des notions comme le lien, le voyage, le pont, la porte, le passage, la gare peuvent être des éléments d’un graphe. Les notions de parenté ou de distinction, de relation, de mouvement sont alors mis en évidence. Des nœuds disposés en cercle peuvent symboliser l’égalité, l’unité, comme le propose Christopher Baker (Graphe 12).

Pour l’amateur de philosophie antique romaine, Janus est le dieu des passages et des portes. Une sculpture à deux visages fixant simultanément deux directions opposées orne les portes et passages. Janus préside aux commencements et aux fins, aux choix et au temps. En tant que dieu des transitions, il est invoqué lors des naissances et des échanges. Il se trouve fréquemment associé à Portunus, dieu des portes et des ports dont l’attribut est la clé. Le citoyen romain fait appel à ce dieu mineur lors des transactions commerciales, des voyages et des embarquements.

De nombreux types d’arbres, de buissons, de réseaux et de cycles sont évoqués dans des textes religieux (Torrens, 2013). La symbolique des réseaux apparaît également vaste et ancienne (Musso 1999) alors qu’une philosophie des réseaux intéresse certains philosophes. Arbres et cycles ne sont ils pas deux types de graphes distincts qui permettent de représenter de manières complémentaire les notions d’espace et de temps ? 

mymap_daterange

Graphe 12 : Réseau d’échange de mails par Christopher Baker (plasticien du numérique), 2007

Conclusion

Retracer des passés oubliés, optimiser des trajets, concevoir des objets, envisager des possibles, faciliter des recherches : voilà le genre de choses pour lesquelles penser, dessiner ou se laisser guider par un graphe est bienvenu. A l’artisan de trouver une représentation efficace et plaisante. Pour tracer de beaux arbres, de jolis cycles et de magnifiques réseaux quelques outils bien affûtés sont nécessaires, un soupçon de théorie, une pointe de scepticisme envers les données, la pratique d’outils adaptés.

Le web rend aisément accessible de nombreux langages informatiques et logiciels spécialisés dans la représentation des graphes, des réseaux et des cycles. Graphviz, Gephi ou Cytoscape peuvent être cités. Des frameworks javascript tels que VivaGraphJS, D3.js, vis.js ou SigmaJS méritent d’être signalés. Basé sur Node.js et D3.js notamment, le service web Palladio intéressera sans doute certains historiens. Des outils web comme jsfiddle.net facilitent les tests de frameworks javascripts. Des sociétés telles que Linkurious, Elastic (Graph) ou Amazon (Neptune) proposent des produits adaptés à des données volumineuses. Des forces de répulsion concurrentes des liens donnent à un réseau une forme et un comportement comparable à ce qui est observé dans le vivant (Graphe 13). Certains modèles s’avèrent remarquablement précis. Comme si la nature obéissait aux mathématiques, alors que celles-ci sont créées collectivement pour tenter de la comprendre. 

hb-blckhole

Graphe 13 : Graphe HB/blckhole (2121 noeuds, 6370 arêtes) d’après Andrei Kashcha, avec ViviGraphJS. http://www.yasiv.com/graphs#HB/blckhole

[A suivre…]

Webographie

Pour les curieux

Services web

Les services web rendent possible la manipulation des données, la création d’images de graphes et le test de bibliothèques javascripts à l’aide d’un simple navigateur.

Publicités

, , ,

2 Commentaires

Affichage d’images en haute résolution avec OpenSeadragon

Publié par Pierre COUCHET dans 5. Données et traitement des données le 29 juillet 2015

« Pour voir loin, il faut y regarder de près » Pierre Dac

OpenSeadragon est une bibliothèque javascript Open Source (Licence BSD) qui facilite la visualisation des détails d’une image haute résolution dans un navigateur en permettant de facilement zoomer et dézoomer sur une zone, avec la souris, avec les doigts (écran tactile), ou bien en cliquant sur un ensemble de boutons dédiés.On passe alors facilement d’une vue générale à l’exploration des détails, de manière simple, fluide, sans latence. Le temps de chargement d’une image lourde devient réduit et la bande passante est ainsi économisée.

De multiples options permettent de finement configurer OpenSeadragon et de l’adapter à différents besoins. Il est notablement possible de visualiser des diaporamas d’images zoomables, de créer des sur-couches mettant en évidence des zones particulières, de comparer sur le même écran deux images haute résolution différentes. Les bibliothèques, les musées et les archives sont les principaux utilisateurs de cette bibliothèque javascript qui sert souvent à afficher des cartes, des manuscrits anciens, des photographies, des œuvres d’art numérisées. Basée sur OpenSeadragon, la visionneuse Mirador (Stanford, Harvard) se distingue. Elle permet par exemple de visualiser simultanément deux images, de naviguer dans des ensembles d’images par l’intermédiaire de vignettes, pour consulter un livre ancien par exemple. Mirador est testé actuellement par Biblissima (Campus Condorcet) qui propose une démonstration intéressante pour les amateurs d’archives et de documents anciens.

La fabrication et l’affichage des images avec OpenSeadragon se fait en deux étapes :

  1. Création d’images zoomables : L’image haute résolution d’origine est transformée automatiquement en une série d’images de petites dimensions appelées « tuiles » (tile en anglais), de forme carrée et localisées dans une arborescence spéciale. Cette transformation peut être faite de manière programmée (C++, PHP, Python, PERL, .NET, Node.js) ou bien à l’aide de logiciels de bureautique libres tels que Deep Zoom Composer (Microsoft) ou bien MapTiler (Klokan Technologies). OpenSeadragon accepte les formats de tuiles DZI et TMS.
  2. Affichage de l’image dans le navigateur : la bibliothèque javascript permet l’affichage des images ainsi créées et ajoute les boutons qui permettent le zoom, le déplacement et le passage plein écran de l’image.

Quelques liens

Démos :

Quelques sites et pages :

Tutoriel

Voici un rapide tutoriel qui va vous permettre de tester OpenSeadragon et de réaliser vous-même des images zoomables. Vous disposez d’un serveur local et d’un PC sous windows (c’est un peu ringard mais ça marche et c’est ce que j’ai souvent sous la main !).

  1. Téléchargez la version zip d’OpenSeadragon ici.
  2. Dézippez le fichier.
  3. Copiez le répertoire « openseadragon-bin-2.0.0 » sur le répertoire du serveur local en le renommant « openseadragon ».
  4. Convertissez votre image haute résolution. Téléchargez Deep Zoom Composer.
  5. Installez Deep Zoom Composer et ouvrez un nouveau projet avec « New Project ».
  6. En haut à droite, ajoutez une image avec « Add Image ».

    dzc-import

    Appuyer sur Import

  7. Cliquez en haut sur « Compose » et glissez l’icone de votre image en bas à gauche dans le panneau du milieu. Peu importe où.

    Appuyez sur Compose

    Appuyez sur Compose

  8. Cliquez en haut sur « Export », entrez à droite le nom du répertoire d’export dans « Name » et le lieu dans « Location » (le répertoire du serveur). Sélectionnez « Export as a composition (single image) ».

    Appuyez sur Export

    Appuyez sur Export

  9. Cliquez sur « Export » en bas à droite.
  10. Cliquez sur « View Image Folder » pour bien repérer la localisation du fichier « dzc_output.xml » à paramétrer dans le code sous le nom « tileSources ».
  11. Le répertoire « dzc_output_files » contient l’image convertie.
  12. Adaptez et insérez le code dans votre page HTML, visualisez dans votre navigateur favori et voilà.

openseadragon

Une version de Virgile imprimée en 1561 et annotée (bibliothèque d'Harvard), visible avec OpenSeadragon

Une version de Virgile imprimée en 1561 et annotée (bibliothèque d’Harvard), visible avec OpenSeadragon/Mirador, Biblissima (Campus Condorcet)

Conclusion

OpenSeadragon est une bibliothèque javascript libre développée et maintenue par Ian Gilman et utilisée entre autres par des organismes du type université, bibliothèque nationale, laboratoire de recherche. Il est tout à fait possible d’envisager l’usage de cette fort intéressante bibliothèque javascript dans une multitude de domaines scientifiques, non seulement en humanités numériques, mais encore en archéologie, agronomie, études sur l’environnement, médecine et biologie (microscopie), physique, astronomie qui exploitent des images en haute résolution. Des services dans le cloud pourraient être créés, susceptibles de faciliter la gestion d’images de ce type, analogue au maintenant disparu Zoom.it de Microsoft. Des modules DZI/OpenSeadragon existent déjà, permettant d’augmenter les possibilités des grands gestionnaires de contenus libres que sont Drupal ou WordPress, des gestionnaires de documents tels que DSpace, Omeka, Pleade.

La technologie libre OpenSeadragon semble prometteuse dans l’objectif de rendre accessible et aisément manipulable des images en très haute résolution. Des technologies libres potentiellement équivalentes sont Leaflet (Open Street map), OpenLayers, PanoJS. D’autres systèmes libres s’avèrent plus difficiles à mettre en œuvre comme IIPImage, digilib. Certains systèmes propriétaires peuvent être cités tels que jQuery Image Viewer, zoomify, ajax-zoom, shockwave-flash (Adobe) ou gigapan (NASA, Google). Des bibliothèques javascript comme StoryMap JS permettent finalement de raconter des histoires avec une image au format gigapixel.

À noter également pour des images de taille standard la possibilité d’utiliser des bibliothèques javascript (jquery ou autre) dédiées au zoom, ou bien un code javascript utilisant les fonctionnalités d’HTML5. La génération de tuiles n’est alors pas nécessaire.

, , , ,

Poster un commentaire