Introduction au Well-Known Binary

Lucidiot — Informatique — 2022-01-16
Beaucoup de contexte pour la prochaine aventure de parsing de données géographiques.

Nous avons vu dans la précédente série d'articles le format Well-Known Text pour représenter des géométries telles qu'elles sont utilisées dans les bases de données géospatiales. Cet article est l'introduction d'une nouvelle série, cette fois-ci sur l'alter ego du Well-Known Text : le Well-Known Binary, abrégé WKB. Avant de vous parler de ce que je compte faire avec ce format binaire, je vais d'abord faire un tour dans les concepts et l'histoire derrière ce format, car elle montre sa complexité.

Une définition très rapide du WKB d'abord : de la même manière que le WKT, c'est un format pour permettre l'échange de géométries entre des systèmes d'information géographiques. Les logiciels peuvent faire ce qu'ils veulent dans leurs implémentations, mais pour parler avec les autres, ils utiliseront ce langage commun. Un format texte a l'avantage d'être lisible par un humain, mais un format binaire est souvent plus rapide à générer ou à interpréter par un logiciel et nécessitera beaucoup moins d'espace disque. On retrouve aujourd'hui ce format dans quasiment tous les programmes qui travaillent avec des données géospatiales, comme PostGIS, ArcGIS, ou Shapely.

Entités

Au cœur de tous les systèmes d'informations géographiques se trouve la notion de feature. En géographie, les features, ou entités en français, sont très abstraites : cela peut désigner par exemple un continent, un océan, une montagne entière, juste un pic sur cette montagne, une ville, une rue, un passage piéton, etc. Le glossaire du comité technique de l'organisation internationale de normalisation ISO/TC 211, responsable de certains standards géospatiaux, définit une entité et en donne des sous-types :

Entité: Abstraction d'un phénomène du monde réel. Bon courage.
Entité géographique: Entité ayant une position géographique. Cela implique que toutes les entités ne sont pas forcément géographiques, et c'est pour ça qu'on peut travailler dans un monde purement géométrique, mathématique, avec les données géospatiales.
Entité simple: Entité restreinte à une géométrie à deux dimensions avec une interpolation linéaire entre les vertex, avec des attributs spatiaux et non-spatiaux.; Autrement dit, tout ce qu'on a vu jusqu'à présent en 2D. L'interpolation linéaire signifie que si plusieurs points sont reliés entre eux, on trace directement des lignes droites, sans considérer la possibilité de l'existence d'une courbe.
Entité complexe: Entité contenant d'autres entités. C'est le cas par exemple des MULTIPOINT ou des GEOMETRYCOLLECTION qu'on a affronté dans les précédents articles. Notez qu'une entité complexe n'est donc pas exactement le contraire d'une entité simple !

Cette notion très abstraite d'entité fait partie des raisons pour lesquelles il y a autant de types de géométries ; par exemple, les réseaux triangulés irréguliers (TIN) sont utilisés pour représenter la topologie, qui peut être une entité à elle seule si on pointe à l'intégralité d'une vallée.

Standards

On avait déjà eu pour le Well-Known Text affaire à une spécification de l'Open Geospatial Consortium qui dictait la grammaire de notre format texte. Pour le Well-Known Binary, bien entendu, il y a la même chose — en fait, le même document que précédemment contient aussi des informations sur le Well-Known Binary, mais il n'est pas le seul à entrer en jeu. Voyons un peu comment ce document est apparu et qui d'autre interfère.

Pourquoi un standard ?

On peut grossièrement créer un standard de deux façons : quand personne n'a encore implémenté quoi que ce soit, par exemple pour inciter des gens à développer des technologies, ou alors quand beaucoup l'ont déjà implémenté, ou que les choix d'une implémentation particulière ont été suivis par tous les autres, et qu'on veut plus clairement documenter ces choix et les rendre plus faciles d'accès à de nouveaux arrivants.

Le Web se développe de nos jours plutôt de la deuxième façon : Google prend une décision unilatérale, en faisant parfois semblant d'écouter les avis des autres, puis implémente quelque chose dans Chrome. Les autres navigateurs, minoritaires, se retrouvent contraints de suivre, surtout si le changement affecte les sites de Google lui-même vu que même les utilisateurs hors de Chrome vont utiliser Google. Vu que tout le monde a l'air de suivre la même chose, maintenant, on en fait le standard.

Je n'étais pas là quand tout ça a été développé, mais il me semble assez clair au vu de mes différentes lectures des standards et des documentations de divers logiciels tels que PostGIS et GEOS que le premier standard, développé par l'Open Geospatial Consortium, est sorti bien tardivement, pour tenter de définir des formats d'échange entre les différentes implémentations. Et je dis tardivement, parce que les systèmes d'information géographiques dépassaient largement les fonctionnalités définies par ce standard.

Simple Feature Access

L'ensemble de standards qui définit aujourd'hui la structure générale des bases de données géospatiales est appelé Simple Feature Access, du nom du tout premier standard, numéroté 05-126. On l'abrège parfois Simple Features, ou juste avec l'acronyme SFA. Avec SFA, l'OGC définit ce qui correspond un peu à ce qu'on a vu au début de notre parsing pour la XSD : simplement les points, lignes, polygones, les ensembles de ceux-ci, et la collection de géométries, le tout en deux dimensions seulement.

Mais comme je l'ai dit, SFA est maintenant un ensemble de standards. En fait, SFA est même « co-standardisé » : l'OGC travaille avec un autre organisme pour éditer des standards. L'ISO s'est emparé de ce premier standard et a publié ISO 19125-1, avec exactement le même titre, mais avec pas mal de différences. On y a notamment vu arriver des types de géométries plus complexes, ainsi que la dimension Z et la notion de mesure.

L'OGC avait publié d'autres standards, définissant plus précisément des fonctionnalités en SQL, avec CORBA ou avec COM/OLE. Le standard lié à SQL, intitulé Simple Feature Access - Part 2: SQL Option (06-104r4), et souvent abrégé en SFS, est le seul que l'ISO aie repris, en tant que ISO 19125-2, avant de finalement s'en débarrasser officiellement en 2018.

L'OGC n'a cependant pas arrêté de publier ses standards, et une de ces raisons est probablement qu'un standard ISO est moins lisible et surtout payant ; comptez environ 150 euros pour acheter un seul PDF. Les standards OGC sont quand à eux gratuits, donc la version actuelle de SFA, 06-103r4, que nous avions consultée précédemment, est un réalignement du standard OGC avec celui ISO. Il y a cependant moult différences, et une annexe de ce standard les liste. On a donc deux standards qui ont le même nom mais ne sont pas les mêmes, et qui sont tout autant valides l'un que l'autre aujourd'hui.

Notons que le standard s'intitule Simple Features, et ne devrait donc définir que des entités simples en toute logique. Mais des entités complexes sont aussi définies dans ce standard, comme le MultiPoint ; le standard viole son propre nom.

SQL Multimedia and Application Packages

Mais les standards ne s'arrêtent pas là. Un autre groupe de travail que celui des données géospatiales a travaillé sur le sujet, celui des bases de données elles-mêmes, et a sorti ISO/IEC 13249-3, la sous-partie géospatiale d'un plus vaste standard nommé SQL Multimedia and Application Packages et abrégé en SQL/MM. Ce standard définit moult extensions pour les bases de données SQL, comme des fonctions de moteur de recherche, du stockage d'images, ou de la gestion d'historique.

Cette partie géospatiale est apparue bien avant la copie par l'ISO du standard SFA. Par conséquent, elle contient encore d'autres définitions des mêmes concepts que SFA. Elle ajoute cependant bien d'autres notions qu'on rencontre plus rarement telles que la topologie ou les courbes. Des révisions ultérieures des deux standards ont finalement pu accorder les violons, et la version actuelle de la partie géospatiale de SQL/MM n'est plus autant en conflit avec un autre standard de la même organisation. Les différences avec le standard OGC restent cependant présentes.

Les standards de WKB

En résumé, on a donc aujourd'hui trois standards encore actifs qui vont influencer la définition du Well-Known Binary :

ISO 19125-1, qui définit les géométries de base qu'on a déjà vu précédemment ;
OGC 06-103r4, l'équivalent de ISO 19125-1 par l'OGC ;
ISO 13249-3, qui ajoute les courbes, la topologie, etc.

Quand je me retrouve avec une seule spécification assez abstraite, c'est déjà bien compliqué, alors s'il faut en réconcilier plusieurs et que deux coûtent quelques centaines d'euros (ou une bonne maîtrise de l'art de la recherche Google), c'est la fête. Mais ça ne s'arrête pas là.

WKB étendu

Quand l'OGC a sorti sa première version officielle de SFA, numérotée 1.1, en 1999, elle ne contenait que des géométries à deux dimensions et sans notion de système de référence spatiale. J'ai déjà parlé plusieurs fois du SRS, souvent par leurs identifiants, les SRID : ce sont ces chiffres qui indiquent dans quel format des coordonnées sont écrites. On a très rapidement besoin de la notion de SRID quand on travaille avec des données géospatiales.

De nos jours, WGS84 (SRID 4326) est le plus courant, puisque c'est avec ce système que sont écrites les coordonnées GPS, mais on utilise souvent sans le savoir un autre système de référence appelé Web Mercator (SRID 3857). Ce système de référence assume que la Terre est parfaitement sphérique, et plus on se rapproche des pôles, plus il y a un décalage important entre Web Mercator et WGS84 : la même coordonnée dans l'un et dans l'autre peut donner des décalages de plusieurs dizaines de kilomètres. La plupart des fournisseurs de cartes en ligne comme Google Maps, Apple Maps, Bing Maps ou OpenStreetMap utilisent cette projection, notamment parce qu'elle est moins complexe à calculer qu'une projection de carte qui assumerait une Terre elliptique comme WGS84. Vous pouvez facilement savoir si cette projection est utilisée en essayant de vous promener près des pôles : si tout s'arrête vers 85° ou -85° au lieu de 90° et -90°, alors c'est un Web Mercator.

Avec rien que ces deux systèmes de référence, il devient donc nécessaire d'associer à ces coordonnées leur système de référence pour qu'un ordinateur puisse faire les conversions nécessaires et éviter des erreurs de plusieurs kilomètres, de la même manière qu'on associe un fuseau horaire à une heure pour que quelqu'un ailleurs dans le monde puisse convertir à son fuseau et avoir la même heure que nous.

Quand SFA 1.1 est sorti, les bases de données géospatiales avaient déjà incorporé des notions de dimensions Z et M pour indiquer l'altitude et une mesure arbitraire non-spatiale, ainsi que cette notion de SRID. Le Well-Known Binary et le Well-Known Text ont donc tous deux rapidement montré leurs limites, puisqu'ils ne pouvaient pas vraiment être utilisés comme un format d'export ou d'import par les bases de données sans risquer de perdre des informations.

En réaction, PostGIS a choisi de définir ce qui a été baptisé l'Extended Well-Known Binary ou EWKB. Cette extension utilise trois bits qui ont été laissés inutilisés dans le format original pour indiquer si la géométrie a un SRID et si elle utilise une dimension Z ou M. Nous verrons plus en détail la structure de ce format dans un prochain article ; ça nous fait en tous cas une nouvelle variante du WKB à considérer.

Comme je l'ai dit plus haut, SFA s'est amélioré au fil du temps et les deux autres dimensions ont été ajoutées au WKB. Cependant, la notion de SRID est restée sur la touche, donc l'EWKB reste encore aujourd'hui pertinent. De plus, le support des géométries en XYZ, XYM et XYZM a été implémenté différemment de la manière que PostGIS a utilisé, donnant donc lieu à l'existence de deux façons différentes d'utiliser des dimensions supplémentaires.

Avec un standard ISO qui coûte cher et qui est arrivé fort tardivement, et toujours des différences entre OGC et ISO, le seul format véritablement fiable a été l'EWKB de PostGIS. Par conséquent, la plupart des implémentations vont utiliser ce format dès qu'il y a plus de deux dimensions ou qu'il y a un SRID, même s'il ne correspond à aucun standard.

Vue d'ensemble du format

La librairie GEOS, une des plus utilisées pour la manipulation de géométries, fournit une page de documentation sur le WKB qui donne un aperçu de la situation et de ce que la librairie prend en charge. C'est avec l'aide de cette page que j'ai pu comprendre correctement le format EWKB, puisque la documentation de PostGIS laisse à désirer, et aussi à partir de là que j'ai pu creuser pour découvrir le standard géospatial de SQL/MM.

Les développeurs de GEOS découpent le WKB en trois "goûts", pour spécifier leur façon de traiter chaque variante du format, et je vais donc suivre moi aussi cette subdivision pour les prochains articles :

WKB ISO: Le WKB tel qu'il est défini par les standards SFA et SQL/MM. C'est le moins fréquemment rencontré. Les dimensions Z et M sont disponibles, mais pas le SRID.
WKB étendu: L'EWKB défini par PostGIS, qu'on trouvera dès qu'on utilise les dimensions Z et M ou le SRID. Ces dimensions sont définies différemments que pour le WKB ISO.
WKB standard: Ce n'est pas le WKB conforme aux standards ! C'est l'intersection des deux autres variantes du WKB, le WKB vraiment sûr, uniquement en deux dimensions et sans SRID.

Objectif

Toute cette aventure technocratique est bien théorique, mais elle n'explique pas pourquoi je m'attarde autant au format WKB. En fait, j'ai déjà rencontré ce format maintes fois, que ce soit au niveau professionnel puisque je travaille souvent avec des coordonnées cartésiennes (de la géométrie pure, pas de géographie), ou au niveau personnel, vu que j'ai travaillé avec des données GPS pour mes scans de réseaux Wi-Fi. J'ai une bonne maîtrise du format Well-Known Text vu qu'il est relativement simple à comprendre — tant qu'on n'en fait pas des expressions régulières — mais je ne connais que très peu le WKB, et vu que c'est le format utilisé par les machines, je me retrouve parfois à devoir tenter de le décoder pour comprendre certains bugs.

Je veux donc essayer de mieux comprendre le WKB, et pour cela rien de mieux que d'écrire beaucoup trop d'articles de blog dessus tout en essayant de formaliser sa spécification. Je ne veux pas prétendre faire quelque chose de mieux que les organismes de normalisation ou quelque chose de plus digeste que divers manuels ou tutoriaux sur le sujet, je veux apprendre et disposer plus tard d'une documentation dans un format que je connais.

Le format que j'ai choisi n'est heureusement ni une expression régulière ni une XSD cette fois, mais quelque chose d'un peu plus récent. J'ai récemment découvert Kaitai Struct au cours de pérégrinations dans d'autres projets dont je parlerai plus tard. Kaitai Struct permet de décrire un format binaire à l'aide d'un fichier YAML, puis de générer du code dans divers langages, tels que Java, JavaScript, Python, Lua ou C#, qui permettra de lire ce format binaire facilement.

J'ai eu une assez bonne expérience en l'utilisant pour d'autres projets, donc je me suis dit que ça pourrait être une bonne idée de l'utiliser ici aussi. Ça me fournira une documentation que j'arriverai à lire, puisque je comprends le format de Kaitai, et je pourrais aussi utiliser ça dans du code rapidement pour lire des données binaires et m'aider à résoudre des problèmes.

Nous commencerons donc la semaine prochaine par traiter un petit bout du WKB, avec des géométries auxquelles on s'est déjà confronté précédemment.

Commentaires

Il n'y a pour l'instant aucun commentaire. Soyez le premier !