Effiziente Punktumnummerierung für Koordinaten aus Bildmessungen

[Hypothraxer]

Die Situation ist folgendermassen:

Ich habe einen Algorithmus, der mir jeweils zwischen zwei Bildern, automatisch die identischen Punkte findet. Die Punkte werden als <Punktnummer> <X in Pixel> <Y in Pixel> abgespeichert.

Die Messungen speichere ich jeweils in zwei Dateien ab. Da ich meistens mehr als nur ein Bildpaar habe, sieht die Datei-Namensgebung so aus:

Bildpaar_bildname.txt

Wenn ich also Bild1.jpg und Bild2.jpg prozessiert habe, erhalte ich die Dateien:

0_Bild1.jpg.txt
0_Bild2.jpg.txt

Die Punktnummerierung ist jeweils abhängig vom Bildpaar. Bei Bildpaar 0 beginnt die Nummerierung bei 0 und geht bis N. Bei Bildpaar 1 geht es von N + 1 bis M usw.

Jetzt wäre die Idee, dass ich zum Schluss alle Bildmessungen von einem Bild in eine Datei schreibe. Konkret für folgendes Beispiel:

0_Bild1.jpg.txt
0_Bild2.jpg.txt
1_Bild2.jpg.txt
1_Bild3.jpg.txt
2_Bild1.jpg.txt
2_Bild3.jpg.txt
3_Bild2.jpg.txt
3_Bild4.jpg.txt
4_Bild3.jpg.txt
4_Bild4.jpg.txt
5_Bild2.jpg.txt
5_Bild3.jpg.txt

Will ich am Schluss vier Dateien haben:

Bild1.jpg.txt
Bild2.jpg.txt
Bild3.jpg.txt
Bild4.jpg.txt

In diesen stehen alle Bildmessungen der jeweiligen Datei drin. Jetzt ist es so, dass in diesen Dateien Duplikate auftauchen - weil ein Punkt in mehr als zwei Bildern gemessen werden kann.

Beispiel (für einen identischen Punkt im Objekt)

Punkt 20 ist in Bild1 und Bild2 gemessen (in Bild1 und Bild2 hat er die Punktnummer 20)
Punkt 80 ist in Bild1 und Bild3 gemessen (in Bild1 und Bild3 hat er die Punktnummer 80)
Punkt 240 ist in Bild2 und Bild3 gemessen (in Bild1 und Bild3 hat er die Punktnummer 240)

Der Punkt hat in Bild1 die ~gleiche Koordinate (euklidische Distanz <= 1.5 pixel). D.h. der Punkt kommt in Bild1 zweimal vor. Somit muss der Koordinaten-Wert (X/Y) in Bild1 gemittelt/der median gemittelt werden und ein Eintrag gelöscht werden. Zusätzlich kommt der Punkt in Bild2 ebenfalls zweimal vor (20 & 240) muss ebenfalls gemittelt werden und die Nummer auf 20 gesetzt werden (und ein Eintrag raus). In Bild 3 sind ebenfalls zwei Punkte identisch (80 & 240) - auch hier wiederum: Mittelung und Koordinatensetzen auf '20' und Entfernen eines Eintrages.

Und so rasselt es sich dann zusammen.

Mein Problem ist jetzt, dass ich keine Implementation hinkriege die a) einigermassen rasant und b) speichereffizient ist. Momentan verfahre ich so, dass ich die einzelnen Dateien (Bild1.jpg.txt, Bild2.jpg.txt, ...) generiere und dann in der jeweiligen Bilddatei cluster erstelle - in diesen Clustern befinden sich die jeweiligen identischen/ähnlichen Koordinaten. Ich ersetze dann jeweils die Punktnummern (d.h. ein Cluster = eine Punktnummer) und sehe nach ob in den entsprechenden verknüpften bildern die Koordinaten ebenfalls in einem Cluster sitzen (mehrfach gemessene Punkte).

Das funktioniert +/- o.k. (Falschmessungen werden nicht abgefangen und so ganz korrekt scheint es nicht zu sein) - aber bei recht grossen Datensätzen (~4.5 Millionen Punkte, 55 Bilder) überläuft mir der 16 GiB grosse Arbeitsspeicher recht schnell.

Jetzt die Frage: Hat jemand eine Idee, wie das Ganze effizient und speicherschonend gemacht werden könnte?

Ein kleiner Beispieldatensatz (~3 MiB) (http://n.ethz.ch/~dnovak/download/MT_small.zip)

Ein grosser Beispieldatensatz (~73 MiB) (http://n.ethz.ch/~dnovak/download/MT.zip)

[Funky Bob]

Hallo,
Nur zum Verständnis:
1.Du versuchst also in Bild 1 alle Pixel mit denen aus Bild 2 zu vergleichen und speicherst die Position, falls die Grauwerte/RGB-Werte an der gleichen Koordinate im Bild identisch sind?

Wovon berechnest du den Mittelwert? Von identischen Pixeln an den identischen Koordinaten? :freak:

Wenn der gleiche Pixel in mehreren Bildern vorkommt soll er das, wenn ich das richtig verstehe, nicht nochmal speichern?
Wenn ja:
Lade alle Bilder in separate Arrays aus Graustufen / RGB-Werten.
Erstell ein temporäres Array mit der Bildgröße. Alles einmal nullen (oder anderen Marker setzen)
for(x) {
for(y) {
for(alleBilder) {
if(derzeitigesBild != quellBild) {
if(derzeitigesBild.farbeBei(x,y) == quellBild.farbeBei(x,y)) {
markiereImTempImage(x,y)
break; //forAlle(Bilder) braucht nicht weiter prüfen -> nächster Pixel
}
}
}
}
}
//Alle Pixel, welche in irgendeinem Bild identisch waren sind markiert
for(x) {
for(y) {
if(tempImage.markiert(x,y)) {
Punkteliste.add(Punkt)
}
}
}
=> Punktnummer = Index in der Liste
Mit nen bissl Überlegung und mehr temporären Bildern kannst du alle Bilder in einem Abgang durchlaufen lassen und doppelte Prüfungen eines Pixels bei einem Pixelpaar sparen, was nochmal schneller ist.

Braucht halt entsprechend viel RAM, aber wenn du nen Int32-Array in Bildgröße hast, und ein Bild 4,5Mio Pixel hat, reichen deine 16GB ohne die Optimierungen für einige hundert Bilder.

[Hypothraxer]

Hallo

Die Koordinaten in den Files sind schon die identischen Punkte (das wurde in einem vorigen Schritt gemacht). D.h. Punktnummer 0 in Bild1 ist der gleiche Objektpunkt wie in Punktnummer 0 in Bild2 (im jeweiligen Bildpaar). Fehlmessungen hat es an sich auch (~max. 5%) aber die sind mir momentan noch egal. Die zugehörigen Koordinaten stellen hierbei die Position des Objektpunktes in Bild1 bzw. Bild2 dar.

Beispiel: Die Ecke eines Randsteins hat folgende Koordinaten:

Bild1: (340.5 / 230.2)
Bild2: (980.2 / 503.9)

(Dazu muss ich evt. noch sagen: Die Bilder wurden aus unterschiedlichen Standpunkten aufgenommen. Sprich: Es ergeben sich nicht die identischen Koordinaten für den gleichen Punkt in unterschliedlichen Bildern).

Das Problem ist, dass ich zwischen mehreren Bildern die Bildpunkte heraussuche (Also z.B. zwischen Bild1-Bild2, Bild1-Bild3 und Bild2-Bild3). Dies geschieht nicht in einem Rutsch sondern immer Paarweise. Ich erhalte darum für Bild1 mehrere Dateien.

Somit kann es sein, dass ich im Bildpaar 1-2 einen Punkt finde, der in 1-3 ebenfalls vorkommt. Um auf das Beispiel vom vorigen Post zu kommen:

Punkt 20 hat in Bild1 (Bildpaar 1-2) die Koordinate (120.5 / 354.2)
Punkt 80 hat in Bild1 (Bildpaar 1-3) die Koordinate (120.4 / 354.6)

Ich definiere hierbei den identischen Punkt als einen, der sich innerhalb eines 1.5 Pixel Radius vom anderen befindet. Nach dieser Regel ist Punkt 20 == Punkt 80 und daraus kann ich den Mittelwert oder Median von X / Y bilden (das wäre dann (120.45 / 354.4) für den Mittelwert).

Das Problem ist jetzt natürlich, dass ich nun auch noch überprüfen muss, ob in Bild 2 und 3 (und allfälligen weiteren Bildpaaren) eine ähnliche Koordinate vorkommt damit ich diese ebenfalls ändern kann (im Beispiel wäre Punktnummer 240 ebenfalls als Punktnummer 20 zu setzen).


Ich werde mir deinen Vorschlag mal noch genauer ansehen - auf jeden Fall schonmal danke dafür :) Allerdings muss ich leider sagen, dass ein Bild deutlich mehr Pixel haben kann. Ich habe hier teilweise 48 Megapixelbilder :) Die 4.5 Millionen Punkte sind im Prinzip nicht Pixel für Pixel entstanden - ich kann nicht für jeden Pixel den identischen Punkt in einem anderen Bild finden. Die Zahl rührt einfach von der Anzahl Verknüpfungen zwischen den einzelnen Bildpaaren. Pro Bildpaar gibt es max. 90'000 Punkte im grossen Beispiel.

[Funky Bob]

Ist die Änderung des Winkels pro Bild denn bekannt? Oder ist sie vielleicht zwar unbekannt, aber pro Bild konstant?
Dann könnte man eventuell den Suchbereich für einen Punkt im nächsten Bild eingrenzen.
Also nach dem Motto:
1. Finde alle identischen Pixel von Bild 1 -> Bild 2
2. Berechne Differenz der Pixel und schätze Position für Pixel von Bild 1 -> Bild 3 ab.
3. Finde Pixel im geschätzten Suchbereich von Bild 1 -> Bild 3

Falls dem nicht so ist, wird es wohl schwer mit einer schnellen Suche, da du wirklich jeden Pixel eines Bildes mit allen Pixeln der anderen Bilder vergleichen musst. Immerhin lässt sich das finden dann recht einfach parallelisieren.

Soweit mir bekannt ist, ist Objektidentifikation in der Bildverarbeitung immernoch extrem aufwändig, wenn man keinerlei Informationen des Objektes hat (Ich nehme an du suchst nicht explizit nach einem bestimmten Objekt, sondern versuchst identische Objekte aller Art in den Bildern zu identifizieren).


Aber was vielleicht helfen kann:
Kann ein gesuchtes Objekt < als beispielsweise 4 Pixel sein?
Dann gäbe es vielleicht die Möglichkeit in einem Bild zusammenhängende Pixel zu suchen (beispielsweise 4 Pixel nacheinander mit ähnlicher Farbe, also eine Art Fläche) und im Vergleichsbild prüfst du dann nur noch jeden 4. Pixel auf Ähnlichkeit mit der gefunden Fläche. Ist die Ähnlichkeit relativ groß, kannst du eine Art Detailsuche in dem Bereich starten.

[Misda]

Willst du zufälligerweise einen optischen Fluss berechnen?

[Hypothraxer]

Sorry wegen der langen Antwortszeit.

Bezüglich dem Problem: Ich glaube ich formuliere das Problem nicht ganz präzis :) Die Bilder waren lediglich als Beispiel da, damit man sich das Ganze vorstellen kann.

Was ich habe:

Pro Bildpaar jeweils zwei Textfiles. In diesen Textfiles stehen schon die korrekt zugeordneten Punkte (die sind zu 95% richtig - das ist aber hier wurscht). Ich habe nun dutzende von Bildpaaren und möchte am Schluss die ganzen Dateien zusammenführen - und zwar so, dass dann allfällige Doppel-Koordinaten die selbe Punktnummer erhalten.

Beispiel:

In Bildpaar 1-2 gibt es einen Punkt 0, der die Koordinaten 100/200 in Bild 1 hat (und in Bild 2 300/400). In Bildpaar 1-3 gibt es einen Punkt 400, der die Koordinaten 100/200 in Bild 1 hat (in Bild 3 405/300)

Wenn ich die Dateien einfach nur zusammenführe, habe ich dann in Bild 1 einen Punkt, der zweimal die Koordinate 100/200 hat - ich möchte das aber nur einmal haben (also z.B. wird Nummer 0 definiert. Aus Bild 1 verschwindet der eine 100/200 Eintrag und in Bild 3 bekommt der Punkt 400, neu die Nummer 0).

Das Problem hierbei liegt, dass es halt auch sein kann, dass der Punkt auch noch in Bildpaar 2-3 vorkommt.

@Misda: Nein - das was ich zusammengebastelt habe ist eine Modifikation für den SIFT, der besser mit konvergenten Aufnahmen funktioniert :)