5.2. Koordinaten und Bereiche

Die Bildverarbeitung wirkt auf Pixel, und um auf ein Pixel einzuwirken, muss ein Algorithmus es über seine Koordinate adressieren. Um auf ein Rechteck von Pixeln einzuwirken, gilt dasselbe – das Rechteck muss auf eine Weise beschrieben werden, auf die sich Algorithmus und Anwendungscode einigen. Die Konvention, die das image-Modul für Koordinaten und Rechtecke verwendet, ist unkompliziert, mit einem Detail, das Leser stolpern lässt, die eher an die mathematische als an die computergrafische Konvention gewöhnt sind, und das es wert ist, gleich zu Beginn klar benannt zu werden.

5.2.1. Das Pixelraster

Pixel (0, 0) ist die obere linke Ecke eines Bildes. Die x-Achse verläuft nach rechts, größeres x bedeutet also weiter rechts. Die y-Achse verläuft nach unten, größeres y bedeutet also weiter unten im Bild. Ein Bild der Größe Breite mal Höhe enthält Pixel an ganzzahligen Koordinaten von (0, 0) bis (width - 1, height - 1); es gibt kein Pixel an (width, 0) oder (0, height) – diese Positionen sind der rechte und der untere Rand, einen Schritt jenseits des letzten tatsächlichen Pixels in der jeweiligen Richtung.

Die nach unten verlaufende y-Achse ist das oben erwähnte Detail. Ein Leser, der an die Geometrie auf Millimeterpapier gewöhnt ist, erwartet, dass größeres y weiter oben bedeutet; hier ist diese Intuition genau umgekehrt. Der Grund für die Umkehrung ist, dass digitale Sensoren und digitale Displays beide oben links beginnen und Zeile für Zeile von oben nach unten nach rechts durchlaufen, und das Anordnen der Pixel im Speicher in derselben Reihenfolge macht die Beziehung zwischen „Position i im Puffer“ und „Zeile r, Spalte c des Bildes“ zu einer möglichst einfachen Rechenoperation – die Position i des Pixels (x, y) ist einfach y * width + x. Jede Bildbibliothek hat sich vor Jahrzehnten aus demselben Grund auf diese Anordnung geeinigt, und der Preis dafür ist eine kleine gedankliche Anpassung, wenn man zum ersten Mal mit Bildern arbeitet.

Das Bildkoordinatensystem: Ursprung oben links, x verläuft nach rechts, y verläuft nach unten. Ein rechteckiger Bereich innerhalb des Bildes wird durch seine obere linke Ecke (x, y) und seine Abmessungen (w, h) benannt.

5.2.2. Rechtecke

Die meisten Operationen auf einem Bild interessieren sich weniger für ein einzelnes Pixel als für ein Rechteck von Pixeln – einen Bereich, in dem gesucht wird, eine Region, die herauskopiert wird, ein Einzelbild innerhalb eines Einzelbildes, über das Statistiken berechnet werden. Die Form zur Benennung eines Rechtecks wählt die einfachstmögliche Erweiterung der Konvention für einzelne Pixel: Man gibt die Koordinate der oberen linken Ecke an, gefolgt von den Abmessungen des Rechtecks, zusammengepackt in ein Vierertupel (x, y, w, h). Die Pixel innerhalb des Rechtecks befinden sich in den Spalten x bis x + w - 1 und in den Zeilen y bis y + h - 1.

Das Detail, das hier klar benannt werden sollte, ist, dass w und h Größen sind, keine Koordinaten der unteren rechten Ecke. Das Rechteck (10, 20, 4, 3) deckt die Spalten 10, 11, 12, 13 und die Zeilen 20, 21, 22 ab – insgesamt zwölf Pixel – nicht eine Region, die von (10, 20) bis (4, 3) verläuft. Die Konvention ist im gesamten Modul einheitlich, sodass die Fehler aufhören, sobald sie verinnerlicht ist, aber sie lässt die Leute beim ersten Mal stolpern.

Die Form (x, y, w, h) taucht an drei Stellen auf, die unterschiedlich aussehen, aber dieselbe Konvention teilen. Die erste ist, wenn ein Bild seine eigene Ausdehnung beschreibt: Das Rechteck, das das gesamte Bild abdeckt, ist (0, 0, width, height). Die zweite ist, wenn eine Erkennungsmethode ein Ergebnis mit einem Begrenzungsrahmen zurückgibt – ein blob, ein rect, ein apriltag – und der Rahmen wird als (x, y, w, h) zurückgemeldet. Die dritte ist, wenn einer Methode gesagt werden muss, dass sie auf einem Teilbereich des Bildes statt auf dem gesamten Einzelbild arbeiten soll; das Schlüsselwortargument roi, das die Operation einschränkt, nimmt dasselbe Vierertupel.

Einen Begrenzungsrahmen von einer Methode aufzugreifen und ihn in das roi der nächsten Methode einzusetzen, ist eines der häufigsten Muster in der Bildverarbeitung. Der Begrenzungsrahmen einer groben ersten Erkennung verengt den Suchbereich für eine feinere zweite, und das einheitliche Vokabular über Erkennungsergebnisse und Methodenargumente hinweg ist es, was dieses Muster so unkompliziert macht, wie es ist – eine Tupelform, auf beiden Seiten der Übergabe auf dieselbe Weise verwendet.

5.2.3. Ganzzahlige Adressen, gebrochene Schwerpunkte

Pixeladressen selbst sind ganze Zahlen. Ein Pixel befindet sich entweder an einer gegebenen ganzzahligen Spalte und Zeile oder nicht, und die Frage, was sich an der Koordinate (40.5, 30.7) befindet, ist keine wohlgeformte Frage – es gibt kein Pixel, das genau an dieser Position sitzt. Eine Handvoll Größen, die das image-Modul aus Pixelpositionen ableitet, sind jedoch gebrochen, und es lohnt sich zu verstehen, warum, damit der Unterschied die Anwendung später nicht überrascht.

Der häufigste Fall ist der Schwerpunkt – der Massenmittelpunkt einer Region. Für eine zusammenhängende Region von Pixeln ist der Schwerpunkt in Gleitkommaform der Durchschnitt der Positionen der zugehörigen Pixel, gewichtet nach ihrer Dichte. Eine Region, deren Pixel sich über zwei Spalten erstrecken, hat einen Schwerpunkt-x von beispielsweise 41,6 – eine reale Position, die das Auge als „die Mitte dieser Region“ beschreiben würde, obwohl kein tatsächliches Pixel genau an diesem x sitzt. Erkennungsergebnis-Objekte tragen beide Formen als schreibgeschützte Eigenschaften: ein ganzzahliges Paar (cx / cy, nützlich, wenn die Position in etwas zurückgespeist wird, das ganzzahlige Pixelkoordinaten erwartet) und ein Gleitkomma-Paar (cxf / cyf, nützlich, wenn die Position in eine Regelschleife eingeht, die von Subpixel-Auflösung profitiert).

Der andere Fall ist die Verschiebung zwischen zwei Einzelbildern, gemessen im Frequenzbereich. Verfahren, die den spektralen Inhalt eines Bildes statt direkt seiner Pixel analysieren, können Verschiebungen feiner als ein Pixel auflösen und melden diese Verschiebungen als Gleitkomma-Werte (dx, dy).

Die Faustregel: Pixeladressen sind ganze Zahlen; Positionen und Verschiebungen, die aus einem Algorithmus herauskommen, können Gleitkommazahlen sein. Zeichenmethoden akzeptieren beide Formen und runden Gleitkommazahlen auf das nächstkleinere ganzzahlige Pixel ab, wenn das Ergebnis auf dem Raster landen muss.

5.2.4. Kartesisch und polar

Das bisher beschriebene System ist kartesisch: Jedes Pixel wird durch seinen horizontalen und vertikalen Abstand vom Ursprung benannt. Das ist das System, in dem die Bytes gespeichert sind – Pixel i im Puffer entspricht dem Pixel in Spalte i % width und Zeile i // width, wobei die Zeilen von oben durchlaufen werden – und es ist das System, in dem standardmäßig jede Methode arbeitet.

Eine zweite Darstellung ist es wert, bekannt zu sein, weil einige Algorithmen in ihr viel besser arbeiten. Polare Koordinaten benennen jedes Pixel durch seinen Abstand von einem gewählten Mittelpunkt und den Winkel zwischen ihm und einer Referenzrichtung. Die Pixel des Bildes haben sich nicht bewegt – die Bytes liegen weiterhin im selben zeilenweise angeordneten Puffer – aber das Adressierungsschema hat von „wie weit rechts und wie weit unten“ zu „wie weit vom Mittelpunkt entfernt und in welchem Winkel um ihn herum“ gewechselt.

Derselbe Punkt P, auf zwei Arten benannt: kartesisch (x, y) vom Ursprung oben links, polar (r, theta) von einem gewählten Mittelpunkt.

Warum überhaupt wechseln? Wegen zweier Identitäten, die schwierige Suchen in einfache verwandeln.

In polaren Koordinaten ist das Drehen des Bildes um den gewählten Mittelpunkt dieselbe Operation wie das Verschieben seiner Pixel entlang der Winkelachse – der x-Richtung im umprojizierten Bild. Eine gedrehte Kopie ist das Original, in polarer Form nach links oder rechts verschoben.

In der log-polaren Variante – die Abstandsachse verwendet eine logarithmische Skala, die Winkelachse bleibt linear – ist das Skalieren des Bildes um den gewählten Mittelpunkt dieselbe Operation wie das Verschieben seiner Pixel entlang der Abstandsachse – der y-Richtung. Eine skalierte Kopie ist das Original, in log-polarer Form nach oben oder unten verschoben.

Ein Algorithmus, der ein bekanntes Muster unter Drehung oder Skalierung erkennen muss, kann seine Suche also im polaren Raum durchführen, wo beide Transformationen zu gewöhnlichen Verschiebungen werden. Nach Verschiebungen zu suchen ist viel günstiger als nach Drehungen und Skalierungen, und die polare Umprojektion ist es, die diese Ersetzung verfügbar macht.

Polare Koordinaten ersetzen kartesische nicht für das Speichern von Pixeln; die Bytes leben immer auf dem kartesischen Raster. Das Modul stellt ein Paar von Methoden bereit, die ein Bild bei Bedarf von der kartesischen in die polare Form umprojizieren, der Algorithmus, der polare Koordinaten benötigt, verrichtet seine Arbeit, und entweder wird das Ergebnis zurückprojiziert oder die Messung im polaren Raum wird direkt verwendet. Dieser Mechanismus ist der einzige Grund, warum polare Koordinaten überhaupt irgendwo an der Oberfläche des Moduls auftauchen.

Mit kartesischen Koordinaten zur Benennung einzelner Pixel, dem Vierertupel (x, y, w, h) zur Benennung von Rechtecken aus ihnen und polaren Koordinaten, wenn ein Algorithmus von ihnen profitiert, verfügt eine Anwendung über ein vollständiges Vokabular, um zu benennen, wo in einem Bild sich etwas befindet. Was an einer dieser Positionen tatsächlich gespeichert ist, ist die nächste Schicht des Fundaments.