Eine unkonventionelle Alternative zur bildbasierten Suche
Die OSINT-Sicherheitsexpertin Sofia Santos veröffentlichte das Drohnenluftbild eines Strandresorts und forderte die Community heraus, den Namen des Resorts, die Koordinaten der Insel sowie die Ausrichtung der Kamera zu ermitteln. Das Foto enthielt weder GPS-Koordinaten noch Metadaten zu Kamera oder EXIF — zu sehen waren lediglich Palmen, weißer Sandstrand und drei entfernte Landmassen auf dem Meer.
Die meisten Teilnehmer versuchten zunächst, inverse Bildsuchmaschinen zu nutzen, um die Strandstruktur oder Gebäude zu identifizieren. Der Entwickler yassa9 wählte jedoch einen völlig anderen Ansatz: Er schloss das Suchfeld, schrieb eine maßgeschneiderte Algorithmen-Pipeline und lud den weltweiten 882MB großen Küstenlinien-Vektordatensatz komplett in den VRAM einer Grafikkarte.
Angesichts hochgradig homogener Naturlandschaften versagen generische Bilderkennungsmodelle häufig und erzeugen bei tropischen Stränden eine Vielzahl von Fehlalarmen. Das Suchproblem auf eine deterministische Geometrie zu reduzieren, erwies sich als einziger Weg aus der Wahrscheinlichkeitsfalle.
Abb.: Das von Sofia Santos veröffentlichte OSINT-Challengematerial mit drei separaten Inseln. Quelle: yassa9 Blog
Umwandlung von drei Inselumrissen in geometrische Fingerabdrücke
Auf dem Bild sind drei Landmassen klar erkennbar: die Resort-Insel P0 im Vordergrund, die flache Insel P1 auf der rechten Seite und die Insel P2 mit Gebirgszügen auf der linken Seite. Diese drei physischen Punkte bilden auf der 2D-Ebene ein spezifisches Dreieck.
Das Seitenverhältnis und die Innenwinkel des Dreiecks bilden ein unfälschbares geometrisches Merkmal. Unter Berücksichtigung von Perspektivenverzerrung und Linsenabberration stellte der Algorithmus ein Toleranzintervall von ±20% für dieses Merkmal ein und definierte es als maschinell durchsuchbaren „geometrischen Fingerabdruck“.
Der erste Schritt der Datenverarbeitung war das Laden des globalen Küstenlinien-Vektordatensatzes land-polygons-split-4326 von OpenStreetMap mit einer ungepackten Dateigröße von 882MB. Um eine Explosion des Rechenaufwands zu verhindern, nutzte die Pipeline eine mehrstufige räumliche Kompressionsstrategie:
Basierend auf tropischen Vegetationseigenschaften wurde die Suchbreite auf ±30° um den Äquator begrenzt. Dadurch fiel die Anzahl der verbleibenden Landpolygone schlagartig von Millionen auf 141.131. Dieser Schritt eliminierte 68% der weltweiten Landpolygone und begrenzte den Rechenbereich strikt auf den Tropengürtel.
Anschließend reduzierte eine räumliche Dichtebeprobung im Abstand von 5km die Anzahl der Knotenpunkte auf 51.576. Eine räumliche Clusterbildung in einem Radius von 20km teilt diese in 23.500 Inselcluster auf. Durch die Aufzählung aller Drei-Punkt-Kombinationen innerhalb der Cluster entstanden schließlich 80.690.777 Kandidatendreiecke. Diese 80,69 Millionen Kandidaten verwandelten eine auf Intuition basierende Suche in ein standardisiertes mathematisches Brute-Force-Problem.
Abb.: Verteilung der Kandidatenstandorte innerhalb des Toleranzbereichs nach geometrischer Filterung und CUDA-Beschleunigung. Quelle: yassa9 Blog
204 Millisekunden GPU-Brute-Force-Matching
Die Traversierung von 80,69 Millionen geometrischen Kombinationen auf einer herkömmlichen CPU würde mehrere Dutzend Minuten dauern, was den größten Engpass der Ingenieursausführung darstellte. yassa9 schrieb einen dedizierten CUDA-Kernel und wies jede Kombination einem unabhängigen GPU-Rechendthread zu.
Auf einer preiswerten Einsteiger-Grafikkarte NVIDIA RTX 3050 mit lediglich 5,2GB VRAM-Belegung benötigte der CUDA-Kernel für alle 80,69 Millionen Dreiecksvergleiche lediglich 204,1 Millisekunden. In Bruchteilen einer Sekunde wurden 99,8% der ungültigen Kombinationen verworfen, woraufhin 158.784 Kandidatendreiecke verblieben.
Die parallelen Stream-Prozessoren einer Grafikkarte eignen sich hervorragend für unabhängige geometrische Prüfungen. Die Kernel-Laufzeit von 0,2 Sekunden steigerte die Sucheffizienz um das Tausendfache.
Ein mehrstufiges Datenfilterungs-Pipeline-System
158.784 Kandidaten lagen noch immer weit über der Grenze manueller Überprüfung. Daher musste eine mehrdimensionale Datenfilter-Pipeline aufgebaut werden. Der Algorithmus führte zunächst eine räumliche Duplikateliminierung durch und führte benachbarte Dreiecke zusammen, was die Anzahl der Ziele auf 8.915 reduzierte.
Es folgte die Prüfung auf offene Gewässer: Über Bounding-Boxen wurden Binnenseen und dichte Inselgruppen ausgeschlossen, sodass 948 Knotenpunkte verblieben. Um der Korallenriffstruktur des Fotos zu entsprechen, führte der Algorithmus den Polsby-Popper-Kompaktheitsindex ein (Verhältnis von Küstenumfang zu Fläche), was die Kandidatenzahl weiter auf 213 senkte. Die Kompaktheitsberechnung filterte stark unregelmäßige, zerklüftete Küstenlinien erfolgreich heraus und bewahrte Inseln mit ausgeprägten Atoll-Merkmalen.
Eine anschließende Filterung nach Ellipsen-Füllgrad reduzierte die Zahl auf 137. An diesem Punkt bündelte der Algorithmus Fernerkundungs-Satellitendaten und nutzte den NDVI-Vegetationsindex mit einem Schwellenwert von 0,6. Der hohe Vegetationsindex eliminierte nackte Sandbänke und unbebaute künstliche Strukturen augenblicklich, wodurch 66 Kandidaten übrig blieben.
Hürde der Automatisierung war die Höhenabfrage über Copernicus DEM 30m-Daten. Der Algorithmus verglich das Profil der Gebirgszüge von Insel P2 auf dem Foto mit den Höhenprofilen und forderte das Vorhandensein von Erhebungen spezifischer Höhe. Dadurch verengte sich das Feld auf genau 26 Kandidaten. Der Abgleich von Höhenmodellen mit 30 Metern Auflösung eliminierte zahlreiche flache Korallenriffe und vollendete den letzten Schlag der automatisierten Pipeline.
Manuelle Endprüfung trifft auf Algorithmen im Militärstandard
Nachdem die automatisierte Pipeline 80,69 Millionen Optionen auf 26 verdichtet hatte, wurde die verbleibende Verifikation manuell durchgeführt. yassa9 prüfte die Satellitenbilder in der Reihenfolge der algorithmischen Priorität und identifizierte beim 8. Kandidaten das exakte Ziel.
Die bestätigte Position war die Insel Oan in den Föderierten Staaten von Mikronesien (Koordinaten: 7°21’48.4”N 151°45’20.7”E). Das Resort auf dem Foto war das Oan Island Resort; die Drohnenkamera blickte zum Aufnahmezeitpunkt nach Nordwesten (324,97°).
In Diskussionen auf Hacker News wiesen zahlreiche Ingenieure darauf hin, dass diese Lösung im Wesentlichen das Prinzip der TERCOM-Navigation (Terrain Contour Matching) von Marschflugkörpern reproduziert. Auch das NASA Jet Propulsion Laboratory (JPL) setzte bei der Landung des Mars-Rovers Perseverance (Mars 2020) ähnliche geometrische Merkmalsvergleiche ein, um die Landeelepse um eine Größenordnung zu verkleinern.
Experimentell bewies dieses Projekt eine technische Realität: Egal ob es um die Verortung von Inseln aus Dutzenden Kilometern Entfernung oder die Präzisionslandung auf dem Mars geht — die Verwendung deterministischer geometrischer Beschränkungen zur Eliminierung visueller Unsicherheiten ist ein außerordentlich zuverlässiger Ingenieurspfad.
Rechenleistung überwindet Erfahrungsgrenzen
Von 882MB Küstendaten bis zur 204-Millisekunden-Ausführung auf der Grafikkarte demonstriert dieses Experiment zur Ortung einer unbewohnten Insel die Wucht moderner ingenieurmäßiger Problemlösung.
Die Umrisse der drei Inseln auf dem Foto waren im Grunde genommen geometrische Längen- und Breitengrade, die auf die Erdoberfläche geschrieben sind. Sobald physikalische Merkmale in berechenbare Datenstrukturen übersetzt werden, kann der riesige unbekannte Suchraum im Dröhnen der Rechenleistung rasend schnell komprimiert werden.
Wenn GPU-Brute-Force auf strikte geometrische Beschränkungen trifft, wird die traditionelle, auf Erfahrung und Glück basierende visuelle Erkennung durch Maschinen-Enumeration von Grund auf neu gestaltet.
Referenz-Links:
- yassa9 Blog: Geolocating an Island Photo
- Hacker News Diskussion: Geolocating an Island Photo
- gralhix OSINT Challenge: Challenge #004
