5.2. Coordonnées et régions

Le traitement d’image agit sur des pixels, et pour agir sur un pixel un algorithme doit l’adresser par sa coordonnée. Pour agir sur un rectangle de pixels, c’est la même chose – le rectangle doit être décrit d’une manière sur laquelle l’algorithme et le code de l’application s’accordent. La convention utilisée par le module image pour les coordonnées et les rectangles est simple, avec un détail qui surprend les lecteurs habitués à la convention mathématique plutôt qu’à la convention de l’infographie, et qu’il vaut la peine d’expliciter d’emblée.

5.2.1. La grille de pixels

Le pixel (0, 0) est le coin supérieur gauche d’une image. L’axe x va vers la droite, donc un x plus grand signifie plus à droite. L’axe y va vers le bas, donc un y plus grand signifie plus bas dans l’image. Une image de largeur par hauteur contient des pixels aux coordonnées entières de (0, 0) jusqu’à (width - 1, height - 1) ; il n’y a pas de pixel à (width, 0) ni à (0, height) – ces positions sont les bords droit et inférieur, un pas au-delà du dernier pixel réel dans chaque direction.

L’axe y orienté vers le bas est le détail mentionné plus haut. Un lecteur habitué à la géométrie du papier millimétré s’attend à ce qu’un y plus grand signifie plus haut ; ici cette intuition est exactement inversée. La raison de cette inversion est que les capteurs numériques et les écrans numériques fonctionnent tous deux à partir du coin supérieur gauche et parcourent chaque ligne vers la droite, de haut en bas, et disposer les pixels en mémoire dans le même ordre rend la relation entre « la position i dans le tampon » et « la ligne r, la colonne c de l’image » aussi simple arithmétiquement que possible – la position i du pixel (x, y) est simplement y * width + x. Toutes les bibliothèques d’imagerie se sont accordées sur cet agencement il y a des décennies pour la même raison, et le coût est un petit ajustement mental lorsqu’on travaille avec des images pour la première fois.

Le système de coordonnées de l’image : origine au coin supérieur gauche, x allant vers la droite, y allant vers le bas. Une région rectangulaire à l’intérieur de l’image est désignée par son coin supérieur gauche (x, y) et ses dimensions (w, h).

5.2.2. Rectangles

La plupart des opérations sur une image s’intéressent moins à un pixel isolé qu’à un rectangle de pixels – une zone où regarder, une région à copier, une trame dans une trame sur laquelle calculer des statistiques. La forme servant à désigner un rectangle choisit la plus simple extension possible de la convention du pixel unique : donner la coordonnée du coin supérieur gauche, suivie des dimensions du rectangle, regroupées dans un quadruplet (x, y, w, h). Les pixels à l’intérieur du rectangle se trouvent aux colonnes x à x + w - 1 et aux lignes y à y + h - 1.

Le détail qu’il vaut la peine d’expliciter ici est que w et h sont des tailles, et non des coordonnées du coin inférieur droit. Le rectangle (10, 20, 4, 3) couvre les colonnes 10, 11, 12, 13 et les lignes 20, 21, 22 – douze pixels au total – et non une région allant de (10, 20) à (4, 3). La convention est uniforme dans tout le module, donc une fois assimilée les erreurs cessent, mais elle surprend les gens la première fois.

La forme (x, y, w, h) apparaît dans trois endroits qui semblent distincts mais partagent la convention. Le premier est lorsqu’une image décrit sa propre emprise : le rectangle couvrant l’image entière est (0, 0, width, height). Le deuxième est lorsqu’une méthode de détection renvoie un résultat avec une boîte englobante – un blob, un rect, un apriltag – et que la boîte est rapportée sous la forme (x, y, w, h). Le troisième est lorsqu’on doit indiquer à une méthode de travailler sur une sous-région de l’image plutôt que sur la trame entière ; l’argument nommé roi qui délimite l’opération prend le même quadruplet.

Récupérer une boîte englobante d’une méthode et la transmettre au roi de la méthode suivante est l’un des schémas les plus courants en traitement d’image. La boîte englobante d’une première détection grossière restreint la zone de recherche pour une seconde détection plus fine, et le vocabulaire uniforme entre les résultats de détection et les arguments des méthodes est ce qui rend ce schéma aussi simple qu’il l’est – une seule forme de tuple, utilisée de la même manière des deux côtés du relais.

5.2.3. Adresses entières, centroïdes fractionnaires

Les adresses de pixels elles-mêmes sont des entiers. Un pixel est ou n’est pas à une colonne et une ligne entières données, et demander ce qui se trouve à la coordonnée (40.5, 30.7) n’est pas une question bien formée – il n’y a aucun pixel situé exactement à cette position. Une poignée de grandeurs que le module image dérive des positions des pixels sont toutefois fractionnaires, et il vaut la peine de comprendre pourquoi afin que cette distinction ne prenne pas l’application au dépourvu plus tard.

Le cas le plus courant est le centroïde – le centre de masse d’une région. Pour une région connexe de pixels, le centroïde sous forme à virgule flottante est la moyenne des positions des pixels membres, pondérée par leur densité. Une région dont les pixels chevauchent deux colonnes aura un centroïde x de, disons, 41.6 – une position réelle que l’œil décrirait comme « le milieu de cette région » même si aucun pixel réel ne se trouve exactement à ce x. Les objets de résultat de détection portent les deux formes en tant que propriétés en lecture seule : une paire d’entiers (cx / cy, utile lorsqu’on réinjecte la position dans quelque chose qui attend des coordonnées de pixels entières) et une paire à virgule flottante (cxf / cyf, utile lorsque la position alimente une boucle de contrôle qui bénéficie d’une résolution sous-pixellique).

L’autre cas est le déplacement entre deux trames mesuré dans le domaine fréquentiel. Les techniques qui analysent le contenu spectral d’une image plutôt que ses pixels directement peuvent résoudre des décalages plus fins qu’un pixel, et elles rapportent ces décalages sous forme de valeurs (dx, dy) à virgule flottante.

La règle empirique : les adresses de pixels sont des entiers ; les positions et les décalages qui sortent d’un algorithme peuvent être des flottants. Les méthodes de dessin acceptent l’une ou l’autre forme et arrondissent les flottants au pixel entier inférieur le plus proche lorsque le résultat doit tomber sur la grille.

5.2.4. Cartésien et polaire

Le système décrit jusqu’ici est cartésien : chaque pixel est désigné par son décalage horizontal et vertical par rapport à l’origine. C’est le système dans lequel les octets sont stockés – le pixel i dans le tampon correspond au pixel à la colonne i % width et à la ligne i // width, en parcourant les lignes à partir du haut – et c’est le système dans lequel chaque méthode opère par défaut.

Une seconde représentation vaut la peine d’être connue car certains algorithmes y fonctionnent bien mieux. Les coordonnées polaires désignent chaque pixel par sa distance à un point central choisi et l”angle entre lui et une direction de référence. Les pixels de l’image n’ont pas bougé – les octets sont toujours dans le même tampon en ordre ligne par ligne – mais le schéma d’adressage est passé de « à quelle distance vers la droite et à quelle distance vers le bas » à « à quelle distance du centre et à quel angle autour de lui ».

Le même point P, désigné de deux façons : cartésien (x, y) depuis l’origine en haut à gauche, polaire (r, theta) depuis un centre choisi.

Pourquoi prendre la peine de changer ? À cause de deux identités qui transforment des recherches difficiles en recherches faciles.

En coordonnées polaires, faire pivoter l’image autour du centre choisi est la même opération que de translater ses pixels le long de l’axe des angles – la direction x dans l’image reprojetée. Une copie pivotée est l’original décalé vers la gauche ou la droite sous forme polaire.

Dans la variante log-polaire – l’axe des distances utilise une échelle logarithmique, l’axe des angles reste linéaire – mettre à l’échelle l’image autour du centre choisi est la même opération que de translater ses pixels le long de l’axe des distances – la direction y. Une copie mise à l’échelle est l’original décalé vers le haut ou le bas sous forme log-polaire.

Ainsi, un algorithme qui doit reconnaître un motif connu sous l’effet d’une rotation ou d’un changement d’échelle peut effectuer sa recherche dans l’espace polaire, où ces deux transformations se transforment en translations ordinaires. Les translations sont bien moins coûteuses à rechercher que les rotations et les changements d’échelle, et la reprojection polaire est ce qui rend cette substitution possible.

Les coordonnées polaires ne remplacent pas les coordonnées cartésiennes pour stocker les pixels ; les octets vivent toujours sur la grille cartésienne. Le module fournit une paire de méthodes qui reprojettent une image du cartésien vers la forme polaire à la demande, l’algorithme qui a besoin de coordonnées polaires fait son travail, et soit le résultat est reprojeté vers l’extérieur, soit la mesure dans l’espace polaire est utilisée directement. Ce mécanisme est la seule raison pour laquelle les coordonnées polaires apparaissent quelque part dans la surface du module.

Avec les coordonnées cartésiennes pour désigner les pixels individuels, le quadruplet (x, y, w, h) pour désigner les rectangles qu’ils forment, et les coordonnées polaires disponibles lorsqu’un algorithme en bénéficie, une application dispose d’un vocabulaire complet pour désigner où dans une image se trouve quelque chose. Ce qui est réellement stocké à l’une de ces positions est la couche suivante de la fondation.