Heatmaps de réseaux Wi-Fi, épisode 3

Lucidiot — Informatique — 2021-11-20
Oui, il est tout à fait possible de générer des images en SQL.

Dans les articles précédents, nous avons pu compter des réseaux et récupérer notre fond de carte. Il est maintenant temps de sortir nos statistiques sous la forme d'une image pour permettre un assemblage.

Une personne saine d'esprit utiliserait peut-être ST_AsGeoJSON ou ST_AsKML ou même ST_AsSVG pour essayer d'exporter des données géographiques en une image ; mais si vous lisez ces articles, vous savez que je ne fais jamais les choses de la manière la plus simple.

Portable Anymap

Le format Portable Anymap, abrégé PNM, a été créé dans les années 1980 pour permettre d'envoyer des images par e-mail sans utiliser des pièces jointes. Les spécifications liées aux e-mails sont incroyablement complexes, notamment via le format MIME, donc il n'était vraiment pas étonnant à l'époque d'avoir des problèmes entre différents clients ou serveurs de messagerie. Ça s'est heureusement amélioré aujourd'hui, notamment grâce aux évolutions sur l'encodage du texte ou sur l'adaptation des clients et des serveurs aux problèmes de certaines implémentations. Le format PNM existe pourtant toujours et sa librarie principale, netpbm, est toujours maintenue.

Le format s'appelait initialement Portable Bitmap, ou PBM, car il n'était conçu que pour envoyer des images en noir et blanc, même pas en niveaux de gris. Un fichier PBM simple pourrait ressembler à ça :

P1
7 5
0 1 0 0 0 1 0
0 0 0 0 0 0 0
1 0 0 0 0 0 1
0 1 0 0 0 1 0
0 0 1 1 1 0 0

Cette image toute petite ressemble à ça :

Un smiley en Portable Bitmap — Un pauvre smiley mal dessiné en Portable Bitmap

Il est aussi possible de "compresser" les données de ce fichier :

P1
7 5
01000100000000100000101000100011100

Quand on parle de PNM, on parle en fait de 3 formats qui ont chacun deux variantes. Le P1 au début du fichier PBM ci-dessus désigne le fichier comme étant un Portable Bitmap en ASCII. Il existe aussi P2 pour Portable Graymap (PGM) où on passe aux niveaux de gris et P3 pour Portable Pixmap (PPM) où on a 3 canaux classiques, rouge, vert et bleu. P4, P5 et P6 correspondent respectivement aux variantes binaires des trois formats précédents ; par exemple, avec P4, chaque bit sur la troisième ligne est un pixel et pas chaque caractère. Avec P5, 8 bits sont utilisés, et avec P6 24 bits. Les implémentations modernes de PNM sont aussi capables de gérer jusqu'à 65535 teintes sur un seul canal, donc on peut utiliser 16 bits en P5 et 48 bits en P6.

Avec les Portable Graymap et Pixmap, un paramètre supplémentaire s'ajoute après la hauteur et la largeur : le nombre de teintes disponibles. Cela permet de faire un choix dans un équilibre entre précision des données et espace disque utilisé, ce qui peut être pratique pour certains services de messagerie limités. Voici par exemple notre pauvre smiley en tant que Portable Graymap :

P2
7 5 3
0 2 0 0 0 2 0
0 0 0 0 0 0 0
1 0 0 0 0 0 1
0 2 0 0 0 2 0
0 0 3 3 3 0 0

Notre smiley ressemble maintenant à ceci :

Un pauvre smiley mal dessiné en Portable Graymap

On a défini 3 comme étant la valeur maximale, donc le 0 devient du noir et le 3 du blanc, et 1 et 2 représentent un gris à 66% et 33%. Les couleurs sont complètement inversées, car seul PBM définit 0 comme étant du blanc et 1 comme du noir ; PGM et PPM définissent tous les deux 0 comme étant noir.

Il existe également le format PAM, qui ne veut pas dire Portable Anymap (ça, c'est PNM) ; PAM signifie Portable Arbitrary Map, et est désigné par le code P7. Il fournit seulement une version binaire et permet de gérer les 3 formats ci-dessous ainsi que des variantes disposant de la transparence, et nécessite un en-tête un peu plus compliqué. On ne va pas s'y attarder ici.

La dernière chose à savoir est que la librairie netpbm fournit une pléthore d'outils qu'il est parfois difficile de comprendre, car ils sont très génériques : on ne parle par moments plus vraiment d'images mais juste de matrices. La librairie permet d'utiliser ce format pour faire des calculs matriciels en tous genres !

Puisque PNM permet de décrire des images avec du texte, c'est un format assez sympathique pour générer facilement des images avec des outils qui ne le permettent pas ou qui ne sont pas du tout faits pour. Par exemple... du SQL.

Générer un PNM en SQL

Nos données de comptage n'ont qu'une seule valeur par pixel, donc nous allons utiliser le format PGM ASCII, ou P2. Ce format demandera donc trois paramètres : la hauteur, la largeur et la valeur maximale des couleurs. Puisque netpbm prend en charge jusqu'à 65535 couleurs, j'ai décidé d'utiliser directement cette valeur maximale et de faire des règles de trois pour rapporter le nombre de réseaux à cette échelle. Cela déporte la garantie d'une image de bonne qualité aux outils de conversion vers PNG de netpbm.

Pour obtenir la hauteur et la largeur, on peut profiter des valeurs i et j de ST_SquareGrid : la différence entre la valeur la plus élevée et la plus basse de chaque sera une des deux dimensions. i se trouve indiquer le numéro d'une "colonne" de cases de la grille, et j un numéro de "ligne", donc i définit la largeur et j la hauteur. On commence donc notre requête SQL par ceci :

WITH output (i, j, value) AS (
  SELECT * FROM (
    SELECT i, j, COUNT(geo)
    FROM ST_SquareGrid(0.0001, ST_SetSRID(ST_EstimatedExtent('geometries', 'geo'), 4326)) AS grid
    LEFT JOIN geometries ON ST_Intersects(grid.geom, geo)
    GROUP BY i, j
  ) a ORDER BY j, i
)
SELECT
   E'P2\n'
   || (MAX(i) - MIN(i) + 1)
   || ' '
   || (MAX(j) - MIN(j) + 1)
   || E'\n65535\n'
FROM output

Obtenir un seul pixel

Nous voilà avec un header valide pour PGM. Il nous faut ensuite générer les données qui constituent chaque pixel. Comme je le disais plus tôt, je veux faire correspondre la valeur maximale de mon nombre de réseaux à 65535. Il va donc me falloir multiplier toutes mes valeurs par un ratio qui correspondra à la valeur maximale de mon nombre de réseaux divisée par 65535. Ainsi, si dans une case j'ai 100 réseaux et dans une autre 1000, j'aurai comme pixels 6554 et 65535. On arrondira au nombre entier supérieur pour éviter de se retrouver avec un 0 là où il y a au moins un réseau ; le zéro signifiera strictement l'absence totale de réseau.

On va éviter de calculer ce ratio une fois par ligne en utilisant une autre sous-requête « de statistiques ». On va aussi ranger la hauteur et la largeur dans cette sous-requête pour rendre les choses un peu plus claires et garder toutes les agrégations à un seul endroit :

WITH output (i, j, value) AS (
  SELECT * FROM (
    SELECT i, j, COUNT(geo)
    FROM ST_SquareGrid(0.0001, ST_SetSRID(ST_EstimatedExtent('geometries', 'geo'), 4326)) AS grid
    LEFT JOIN geometries ON ST_Intersects(grid.geom, geo)
    GROUP BY i, j
  ) a ORDER BY j, i
), stats (width, height, ratio) AS (
  SELECT
    MAX(i) - MIN(i) + 1,
    MAX(j) - MIN(j) + 1,
    MAX(value) / 65535.0
  FROM output
)
SELECT
   E'P2\n'
   || width || ' ' || height
   || E'\n65535\n'
   || CEIL(value * ratio)::text
FROM output, stats

On n'utilise aucune condition de jointure, parce que la sous-requête de statistiques ne renvoie qu'une seule ligne : on n'aura donc aucune duplication des lignes de output. Mais pour l'instant, cette requête va renvoyer une ligne pour chaque case de la grille puisque nous n'avons fait aucune agrégation. Il nous donc regrouper tous les pixels ensemble en une seule chaîne de caractères.

Rassembler les pixels

PostgreSQL nous fournit une fonction d'agrégation exprès pour concaténer plein de chaînes de caractères : string_agg. On pourrait donc utiliser ceci :

SELECT
   E'P2\n'
   || width || ' ' || height
   || E'\n65535\n'
   || string_agg(CEIL(value * ratio)::text, ' ')
FROM output, stats

Mais quelques tests en utilisant cette méthode m'ont montré que deux problèmes apparaissent :

L'ordonnancement des pixels n'est pas du tout garanti malgré un ORDER BY i, j.
Moult parseurs de fichiers PGM et PPM tels que ImageMagick rejettent les fichiers qui ne séparent pas chaque ligne de pixels par un saut de ligne.

Pour régler le premier problème, on peut utiliser un bout de syntaxe spécifique à PostgreSQL qui a été ajouté rien que pour apporter une solution à ce problème particulier :

string_agg(CEIL(value * ratio)::text, ' ' ORDER BY j, i)

On trie d'abord par lignes puis par colonnes, ce qui est l'ordre attendu par PGM. Un ORDER BY classique qui se trouverait en dehors de l'agrégation ne fonctionnerait pas ici, car ORDER BY s'exécute en tout bout de chaîne ; on serait en train d'essayer de trier la seule chaîne de caractères construite en entier. En plaçant ici le ORDER BY dans l'agrégation elle-même, on instruit à PostgreSQL de donner à l'agrégation des valeurs dans un certain ordre.

Le second problème va demander un peu plus qu'une recherche sur StackOverflow. On va en fait avoir besoin de deux agrégations : une qui construira des lignes (dans le sens de lignes de tables SQL) contenant chacune une ligne (une chaîne de caractères) de pixels séparés par des espaces, puis une qui regroupera toutes ces lignes avec des sauts de ligne. On peut faire cette construction avec une autre sous-requête :

WITH output (i, j, value) AS (
  SELECT i, j, COUNT(geo)
  FROM ST_SquareGrid(0.0001, ST_SetSRID(ST_EstimatedExtent('geometries', 'geo'), 4326)) AS grid
  LEFT JOIN geometries ON ST_Intersects(grid.geom, geo)
  GROUP BY j, i
), stats (width, height, ratio) AS (
  SELECT
    MAX(i) - MIN(i) + 1,
    MAX(j) - MIN(j) + 1,
    MAX(value) / 65535.0
  FROM output
), lines (j, line) AS (
  SELECT j, string_agg(CEIL(value / ratio)::text, ' ' ORDER BY i)
  FROM output, stats
  GROUP BY j
)
SELECT
   E'P2\n'
   || width || ' ' || height
   || E'\n65535\n'
   || string_agg(line, E'\n' ORDER BY j DESC)
   || E'\n'
FROM lines, stats
GROUP BY width, height

On supprime le ORDER BY j, i dans la sous-requête output puisque c'est devenu inutile. Dans la nouvelle sous-requête lines, on groupe par ligne avec GROUP BY j, et on assemble chaque ligne avec un string_agg trié par colonne. Dans la requête principale, on n'accède plus à output directement mais à lines, et on agrège avec des sauts de ligne et en triant par ligne.

Enfin, on a un GROUP BY width, height en bas de cette requête, car width et height ne font partie d'aucune agrégation, et même s'ils ont des valeurs parfaitement fixes, PostgreSQL ne sait que faire de ces colonnes. On lui dit de grouper, et il ne fera que construire un seul groupe vu qu'il n'y a qu'une valeur possible. On récupère donc à la fin une seule chaîne de caractères.

Dans un script shell

L'échappement des caractères est un petit peu plus simple que la dernière fois. On va échapper toutes les controbliques, utiliser une sortie en CSV parce que nous utilisons quand même des \n, utiliser encore la tabulation comme délimiteur de chaîne de caractères, puis supprimer les tabulations. Dans le précédent article, on se fichait des tabulations, mais ici tout caractère qui précèderait l'en-tête P2 pourrait donner un fichier incorrect, donc on va faire du nettoyage.

psql -c "COPY (
  WITH output (i, j, value) AS (
    SELECT i, j, COUNT(geo)
    FROM ST_SquareGrid(0.0001, ST_SetSRID(ST_EstimatedExtent('geometries', 'geo'), 4326)) AS grid
    LEFT JOIN geometries ON ST_Intersects(grid.geom, geo)
    GROUP BY j, i
  ), stats (width, height, ratio) AS (
    SELECT
      MAX(i) - MIN(i) + 1,
      MAX(j) - MIN(j) + 1,
      MAX(value) / 65535.0
    FROM output
  ), lines (j, line) AS (
    SELECT j, string_agg(CEIL(value / ratio)::text, ' ' ORDER BY i)
    FROM output, stats
    GROUP BY j
  )
  SELECT
     E'P2\\n'
     || width || ' ' || height
     || E'\\n65535\\n'
     || string_agg(line, E'\\n' ORDER BY j DESC)
     || E'\\n'
  FROM lines, stats
  GROUP BY width, height
) TO STDOUT WITH (FORMAT CSV, QUOTE E'\\t')" |
  tr -d "\t" > stats.pgm

Exemple de résultat

Représentation en blanc sur noir de la densité de réseaux Wi-Fi — Représentation en noir et blanc de la densité de réseaux Wi-Fi

Voici le genre d'image qu'on peut obtenir avec la requête ci-dessus, convertie au format PNG pour la rendre lisible par vos navigateurs. Vous pouvez télécharger l'image originale au format PGM. C'est encore loin de ressembler à une carte vraiment visible, mais on peut déjà commencer à distinguer certains chemins empruntés ou à observer de grands cercles correspondant à des mesures vraiment très imprécises.

Conclusion

Nous avons enfin récupéré toutes les pièces du puzzle ! Il ne restera plus qu'à les mettre ensemble pour générer une toute première heatmap. Pour cela, il va nous falloir apprendre moult notions sur le traitement d'images en ligne de commande. On aura cinq couches de langages de programmation et de syntaxes particulières imbriquées les unes dans les autres...

Commentaires

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