5.2. Coördinaten en regio’s

Beeldverwerking werkt op pixels, en om op een pixel te kunnen werken moet een algoritme die via een coördinaat kunnen aanspreken. Om op een rechthoek van pixels te werken geldt hetzelfde – de rechthoek moet worden beschreven op een manier waar het algoritme en de applicatiecode het over eens zijn. De conventie die de image-module hanteert voor coördinaten en rechthoeken is eenvoudig, met één detail dat lezers die gewend zijn aan de wiskundige conventie in plaats van de computergrafiek-conventie kan verrassen, en dat het waard is om vooraf expliciet te benoemen.

5.2.1. Het pixelraster

Pixel (0, 0) is de linkerbovenhoek van een afbeelding. De x-as loopt naar rechts, dus een grotere x betekent verder naar rechts. De y-as loopt naar beneden, dus een grotere y betekent verder naar beneden in de afbeelding. Een afbeelding van breedte bij hoogte bevat pixels op gehele coördinaten van (0, 0) tot en met (width - 1, height - 1); er is geen pixel op (width, 0) of (0, height) – die posities zijn de rechter- en onderrand, één stap voorbij de laatste werkelijke pixel in elke richting.

De naar beneden lopende y-as is het detail dat hierboven werd genoemd. Een lezer die gewend is aan ruitjespapier-meetkunde verwacht dat een grotere y hoger betekent; hier is die intuïtie precies omgekeerd. De reden voor de omkering is dat zowel digitale sensoren als digitale beeldschermen werken vanaf de linkerbovenhoek en naar rechts door elke rij lopen, van boven naar beneden, en het op dezelfde manier in het geheugen plaatsen van pixels maakt de relatie tussen “positie i in de buffer” en “rij r, kolom c van de afbeelding” zo eenvoudig mogelijk rekenkundig – de positie i van pixel (x, y) is gewoon y * width + x. Elke beeldbibliotheek werd het tientallen jaren geleden om dezelfde reden eens over die opstelling, en de prijs is één kleine mentale aanpassing wanneer je voor het eerst met afbeeldingen werkt.

Het beeldcoördinatensysteem: oorsprong in de linkerbovenhoek, x naar rechts lopend, y naar beneden lopend. Een rechthoekige regio binnen de afbeelding wordt aangeduid door de linkerbovenhoek (x, y) en de afmetingen (w, h).

5.2.2. Rechthoeken

De meeste bewerkingen op een afbeelding houden zich minder bezig met een enkele pixel dan met een rechthoek van pixels – een gebied om in te kijken, een regio om uit te kopiëren, een frame binnen een frame om statistieken over te berekenen. De vorm om een rechthoek aan te duiden kiest de eenvoudigst mogelijke uitbreiding van de enkele-pixelconventie: geef de coördinaat van de linkerbovenhoek, gevolgd door de afmetingen van de rechthoek, samengevoegd tot een vier-tuple (x, y, w, h). De pixels binnen de rechthoek bevinden zich in de kolommen x tot en met x + w - 1 en de rijen y tot en met y + h - 1.

Het detail dat hier expliciet vermeld moet worden, is dat w en h afmetingen zijn, geen coördinaten van de rechteronderhoek. De rechthoek (10, 20, 4, 3) beslaat de kolommen 10, 11, 12, 13 en de rijen 20, 21, 22 – twaalf pixels in totaal – niet een regio die loopt van (10, 20) tot (4, 3). De conventie is uniform over de hele module, dus zodra die geïnternaliseerd is, houden de vergissingen op, maar de eerste keer betrapt het mensen wel.

De vorm (x, y, w, h) duikt op drie plaatsen op die afzonderlijk lijken maar dezelfde conventie delen. De eerste is wanneer een afbeelding haar eigen omvang beschrijft: de rechthoek die de hele afbeelding beslaat is (0, 0, width, height). De tweede is wanneer een detectiemethode een resultaat met een begrenzingsvak teruggeeft – een blob, een rect, een apriltag – en het vak wordt teruggemeld als (x, y, w, h). De derde is wanneer een methode moet worden verteld om op een subregio van de afbeelding te werken in plaats van op het hele frame; het roi-sleutelwoordargument dat de bewerking afbakent, neemt hetzelfde vier-tuple aan.

Een begrenzingsvak van de ene methode oppikken en het in de roi van de volgende methode laten vallen, is een van de meest voorkomende patronen in beeldverwerking. Het begrenzingsvak van een grove eerste detectie versmalt het zoekgebied voor een fijnere tweede, en het uniforme vocabulaire over detectieresultaten en methodeargumenten heen is wat dat patroon zo eenvoudig maakt als het is – één tuple-vorm, op beide kanten van de overdracht op dezelfde manier gebruikt.

5.2.3. Gehele adressen, fractionele zwaartepunten

Pixeladressen zelf zijn gehele getallen. Een pixel bevindt zich wel of niet op een gegeven gehele kolom en rij, en vragen wat er op coördinaat (40.5, 30.7) zit, is geen welgevormde vraag – er zit geen pixel precies op die positie. Een handvol grootheden die de image-module afleidt uit pixelposities zijn echter fractioneel, en het is de moeite waard om te begrijpen waarom, zodat het onderscheid de applicatie later niet betrapt.

Het meest voorkomende geval is het zwaartepunt – het massamiddelpunt van een regio. Voor een samenhangende regio van pixels is het zwaartepunt in drijvende-kommavorm het gemiddelde van de posities van de samenstellende pixels, gewogen naar hun dichtheid. Een regio waarvan de pixels over twee kolommen verdeeld zijn, heeft een zwaartepunt-x van bijvoorbeeld 41.6 – een echte positie die het oog zou omschrijven als “het midden van die regio”, ook al zit er geen werkelijke pixel precies op die x. Detectieresultaatobjecten dragen beide vormen als alleen-lezen eigenschappen: een geheeltallig paar (cx / cy, nuttig wanneer de positie wordt teruggevoerd naar iets dat gehele pixelcoördinaten wil) en een drijvende-kommapaar (cxf / cyf, nuttig wanneer de positie in een regelkring terechtkomt die baat heeft bij subpixelresolutie).

Het andere geval is verplaatsing tussen twee frames, gemeten in het frequentiedomein. Technieken die de spectrale inhoud van een afbeelding analyseren in plaats van de pixels rechtstreeks, kunnen verschuivingen fijner dan één pixel oplossen, en zij rapporteren die verschuivingen als drijvende-komma (dx, dy)-waarden.

De vuistregel: pixeladressen zijn gehele getallen; posities en verschuivingen die uit een algoritme komen, kunnen drijvende-kommagetallen zijn. Tekenmethoden accepteren beide vormen en ronden drijvende-kommagetallen naar beneden af op de dichtstbijzijnde gehele pixel wanneer het resultaat op het raster moet landen.

5.2.4. Cartesiaans en polair

Het tot dusver beschreven systeem is Cartesiaans: elke pixel wordt aangeduid door de horizontale en verticale verschuiving ten opzichte van de oorsprong. Dat is het systeem waarin de bytes worden opgeslagen – pixel i in de buffer komt overeen met de pixel op kolom i % width en rij i // width, waarbij de rijen vanaf boven worden doorlopen – en het is het systeem waarin elke methode standaard werkt.

Een tweede representatie is de moeite van het kennen waard, omdat sommige algoritmen er veel beter in werken. Polaire coördinaten duiden elke pixel aan door de afstand tot een gekozen middelpunt en de hoek tussen die pixel en een referentierichting. De pixels van de afbeelding zijn niet verplaatst – de bytes staan nog steeds in dezelfde rij-georiënteerde buffer – maar het adresseringsschema is omgeschakeld van “hoe ver naar rechts en hoe ver naar beneden” naar “hoe ver van het midden en onder welke hoek eromheen.”

Hetzelfde punt P, op twee manieren aangeduid: Cartesiaans (x, y) vanaf de oorsprong linksboven, polair (r, theta) vanaf een gekozen middelpunt.

Waarom de moeite van het omschakelen? Vanwege twee identiteiten die moeilijke zoekopdrachten in eenvoudige veranderen.

In polaire coördinaten is het draaien van de afbeelding om het gekozen middelpunt dezelfde bewerking als het verschuiven van de pixels langs de hoek-as – de x-richting in de opnieuw geprojecteerde afbeelding. Een gedraaide kopie is het origineel naar links of rechts verschoven in polaire vorm.

In de log-polaire variant – de afstand-as gebruikt een logaritmische schaal, de hoek-as blijft lineair – is het schalen van de afbeelding om het gekozen middelpunt dezelfde bewerking als het verschuiven van de pixels langs de afstand-as – de y-richting. Een geschaalde kopie is het origineel omhoog of omlaag verschoven in log-polaire vorm.

Een algoritme dat een bekend patroon onder rotatie of schaling moet herkennen, kan zijn zoekwerk dus doen in de polaire ruimte, waar beide transformaties veranderen in gewone verschuivingen. Verschuivingen zijn veel goedkoper om naar te zoeken dan rotaties en schalingen, en de polaire herprojectie is wat die vervanging mogelijk maakt.

Polaire coördinaten vervangen Cartesiaanse niet voor het opslaan van pixels; de bytes leven altijd op het Cartesiaanse raster. De module biedt een paar methoden die een afbeelding op verzoek herprojecteren van Cartesiaanse naar polaire vorm, het algoritme dat polaire coördinaten nodig heeft doet zijn werk, en ofwel projecteert het resultaat weer terug, ofwel wordt de meting in de polaire ruimte rechtstreeks gebruikt. Dat mechanisme is de enige reden dat polaire coördinaten ergens aan het oppervlak van de module verschijnen.

Met Cartesiaanse coördinaten voor het aanduiden van individuele pixels, het (x, y, w, h)-vier-tuple voor het aanduiden van rechthoeken daarvan, en polaire coördinaten beschikbaar wanneer een algoritme er baat bij heeft, beschikt een applicatie over een volledig vocabulaire om aan te duiden waar in een afbeelding iets zich bevindt. Wat er werkelijk op een van die posities is opgeslagen, is de volgende laag van het fundament.