Algorithmen zur Auswertung von Punktmustern gesucht

[Edzard Egberts]

Es geht um die Auswertung von aufeinander folgenden Wolkenbildern:

Ich habe schon einen Algorithmus, der Wolkenbilder in (zum Teil
geschachtelte) Einzelobjekte mit Schwerpunkt umwandelt, so dass ich ein
Wolkenbild in ein Muster von Punkten umwandeln kann. Zur Bestimmung von
Bewegungen (Windrichtung, Windgeschwindigkeit) und für das "Nowcasting"
(kurzfristige Prognose von Verschattungen) möchte ich nun diese Muster
in aufeinander folgenden Bildern auswerten. Dazu brauche ich eine
Punkt-zu-Punkt-Zuordnung, aber auch so etwas wie eine "globale
Verschiebung" und alles mit der Nebenbedingung, dass sich "Punkte" auch
mal auflösen, überlagern oder sonst wie verändern. Auch kann es ganze
Bereiche geben, die sich unterschiedlich bewegen, nämlich hohe Wolken
hinter tiefen Wolken. So hemdsärmelige Methoden nach dem Motto "jetzt
gucken wir mal, wo dieser Punkt im anderen Bild sein könnte" stoßen da
wahrscheinlich schnell an ihre Grenzen.

Was gibt es also für Algorithmen, die sich auf eine solche
Problemstellung anwenden ließen? Ich suche keine konkrete Lösung,
sondern möchte nur eine Vorstellung entwickeln, wie "so etwas" gemacht
wird, da gibt es sicherlich schon einige Idee im Bereich "Mustererkennung"?

Ein Beispiel dazu wäre das "Agglomerative Hierarchische Clustering", mit
dem ich ein Problem bei der Objektzuordnung lösen konnte. Ich suche
jetzt ähnliche Verfahren zur Definition und Auswertung von
"Objektbeziehungen", mit denen ich herumbasteln kann. Phasenkorrelation
kann ich auch, das will ich mir als erstes ansehen. Weitere Tipps?

[Hans-Peter Diettrich]

Mit 3D Bildern schon möglich, mit 2D eher nicht.

DoDi

[Edzard Egberts]

Post by Hans-Peter Diettrich
Mit 3D Bildern schon möglich, mit 2D eher nicht.

Mal davon abgesehen, dass ich 3D schon realisiert habe
(Wolkenhöhenbestimmung mit zwei Kameras anhand des stereoskopischen
Versatzes) kann man sehr wohl auch mit einer Kamera arbeiten. Aus den
aufeinander folgenden Bildern kann nicht nur die Windrichtung bestimmt
werden, sondern es ist auch ein Punkt-Forecasting möglich: Anhand der
Wolkengeschwindigkeit in Pixeln ist absehbar, wann eine bestimmte Wolke
die Sonne erreicht und dann genau den Standort der Kamera abdeckt.
Nur um die Geschwindigkeit in m/s zu ermitteln, muss man die Höhe der
Wolke kennen.

Zur Zeit ist die Erkennung von Verschiebungen über den Optical Flow
realisiert, aber meine objektorientierte Höhenbestimmung ist so gut
geworden (die Höhen aufeinander folgender Sequenzen haben eine sehr
geringe Abweichung), dass ich die Objekte jetzt auch für die
Bewegungsanalyse einsetzen will, besonders für das Tracking.

Dazu muss ich aber Schwerpunkte sortieren, habe das auch schon
erfolgreich mit einem agglomerative hierarchical clustering für die Höhe
realisiert, und interessiere mich für weitere Sortieralgorithmen oder
Methoden, Objektbeziehungen zu finden, bzw. zu definieren. Das
Clustering wollte ich eigentlich für ein anderes Problem einsetzen und
bin dann (rein zufällig, weil der k-Means-Algorithmus eine Vorgabe
braucht ;o) darüber gestolpert, dass man damit beim Objekt-Matching
false positives aussortieren kann.

Also ganz grundsätzlich weiß ich schon so ungefähr, was ich hier tue. ;o)

[Jens Kallup]

was ist, wenn Du einen verallgemeinerten Hintergrund als
Grundlage (schwarz) als Layer hinter den Wolkenbildern
legst, und einen Raycast-Strahl durch die Wolkenbilder
schickst, und die Wolkendichte berücksichts?
Dann hast Du doch sowas wie Gradientbilder, die Di dann
weiter verarbeiten kannst.
Je kleiner der Gradient, desto höher ist die Wolkendichte
und natürlich umgekehrt genau das gleiche.

Das verfälscht natürlich die eigentliche Wolke(n), aber
Du kannst ja vorher noch eine schwarz-Maske von der
Originalwolke machen und dann den Gradienten drüber legen.

Gruß, Jens

[Edzard Egberts]

Post by Jens Kallup
was ist, wenn Du einen verallgemeinerten Hintergrund als
Grundlage (schwarz) als Layer hinter den Wolkenbildern
legst, und einen Raycast-Strahl durch die Wolkenbilder
schickst, und die Wolkendichte berücksichts?
Dann hast Du doch sowas wie Gradientbilder, die Di dann
weiter verarbeiten kannst.
Je kleiner der Gradient, desto höher ist die Wolkendichte
und natürlich umgekehrt genau das gleiche.

Da bin ich schon viel weiter, ich habe nach der Auswertung mit OpenCV
alle Wolken mit genau definierten Konturen, Hierarchien, Schwerpunkten
und Transparenzwerten. Das war echt Arbeit! ;o)

Wenn ich nur die Schwerpunkte nehme und die Bilder nacheinander ablaufen
lasse, gibt das ein Gewusel von Punkten und Punktgruppen, in dem ich
Bewegungsmuster erkennen und definieren möchte. Charakteristisch sind
z.B. Korridore, in denen sich die Wolken auflösen, 5 Punkte am Rand
werden auf dem Weg in die Mitte immer weniger und sind irgendwann weg.

Gibt es irgendwelche Leute, die mit variablen Vektorfeldern arbeiten
müssen? Ich habe die ganzen Daten, rätsele aber eben noch, wie ich die
auf der Zeitachse modellieren kann. Sollte ich da eher bei den Physikern
nachfragen? Ich suche auch keine konkrete Lösung, sondern allgemeine
Anregungen, wie ähnliche Probleme normalerweise gelöst werden. Die
Ausbreitung von Wirbeln in einer Strömung wäre ein ähnliches Gebiet
(eigentlich sogar fast das gleiche).

[Jens Kallup]

Post by Edzard Egberts
Sollte ich da eher bei den Physikern
nachfragen? Ich suche auch keine konkrete Lösung, sondern allgemeine
Anregungen, wie ähnliche Probleme normalerweise gelöst werden. Die
Ausbreitung von Wirbeln in einer Strömung wäre ein ähnliches Gebiet
(eigentlich sogar fast das gleiche).

da bist Du schon richtig hier, da Du ja anscheinend auch Informatik
und Programmierkenntnisse hast.
Die Informatiker-Ecke ist meist mit konkreten Sachen beschäftigt, die
von Mathematikern oder auch Physikern zugetragen sind.
Die Frage ist nur, ob Dir die "alten" Vektorgebilde gefallen.
Es ist natürlich einfacher Vektorgrafiken zu erstellen, und diese zu
verarbeiten.

Du könntest doch aus "Deinen" punktgewussel Mittelwerte berechnen,
und mit diesen Werten Vektoren bilden.
Dann brauchst Du nicht jeden Punkt einzeln zu Verfolgen, sondern kannst
dann Pfade festlegen, die sich verändern können - wesentlich hierbei
ist, dass man weniger Daten zu berücksichtigen muss/kann.

Hier ein Beispiel, für ein Programm, das 5 Minuten in die Zukunft
schauen kann:
http://pages.iai.uni-bonn.de/gall_juergen/download/jgall_anticipation_cvpr18.pdf

oder: Seite 24
http://pages.iai.uni-bonn.de/gall_juergen/download/gall-diplomarbeit.pdf

[Edzard Egberts]

Post by Jens Kallup

  Sollte ich da eher bei den Physikern
nachfragen? Ich suche auch keine konkrete Lösung, sondern allgemeine
Anregungen, wie ähnliche Probleme normalerweise gelöst werden. Die
Ausbreitung von Wirbeln in einer Strömung wäre ein ähnliches Gebiet
(eigentlich sogar fast das gleiche).

da bist Du schon richtig hier, da Du ja anscheinend auch Informatik
und Programmierkenntnisse hast.

Na ja, ich habe eine Mission, den Rest muss ich mir eben erarbeiten!
Alternativ könnte ich auch auf der Straße verhungern, aber das wollen
wir doch nicht! ;o)

Post by Jens Kallup
Du könntest doch aus "Deinen" punktgewussel Mittelwerte berechnen,
und mit diesen Werten Vektoren bilden.

Der Trick ist scheinbar, die Punkte durch Knoten zu ersetzen und den
Knoten Werte zuzuweisen, z.B. die Winkel und Abstände zu den nächsten
Punkten. Damit sind die Muster schon einmal positionsunabhängig und
haben vergleichbare Eigenschaften. Als Histogramm sieht das schon
vielversprechend aus, ganz klare Peaks.

Post by Jens Kallup
Dann brauchst Du nicht jeden Punkt einzeln zu Verfolgen, sondern kannst
dann Pfade festlegen, die sich verändern können - wesentlich hierbei
ist, dass man weniger Daten zu berücksichtigen muss/kann.

Das sind zum Glück gar nicht so viele. Ich habe festgestellt, dass auch
die simplen Methoden wie "vergleiche jeden Punkt mit allen anderen
Punkten" schnell genug laufen.

Post by Jens Kallup
oder: Seite 24
http://pages.iai.uni-bonn.de/gall_juergen/download/gall-diplomarbeit.pdf

Seite 15 "List of Algorithms" kommt mir mehr entgegen, die Konvergenz
auf Seite 24 sagt mir gerade nicht so viel, konnte bisher aber auch
gerade mal zwei Tage daran arbeiten. Das mit den Knoten habe ich aus dem
Clustering...

[Jens Kallup]

Das mit den Knoten habe ich aus dem Clustering...

ja, auf Seite 24, wollte ich andeuten, das was Du
schon rausgefunden hast - Knoten zu Punkten.

Es ist nämlich so, das es ja unterschiedliche
Wolken-Arten mit unterschiedlichen Namen, und
unterschiedlicher Höhe und Vorkommens gibt.

Dann musst Du auch die Höhe von Null aufsteigend
berǘcksichtigen;

Weil, an Küsten, und Gebirge unterschiedliche
Werte vorhanden sind - ich weiß jetzt nicht ob es
auch eine kostenlose GeoInformation gibt, die für
jeden Vektor(Kartenausschnitt) Vektoren genutzt
werden können.

Im einfachsten Fall erstellst Du halt statisch
erzeugte Daten; sprich, Du erstellst mehrere
2D Kurven, die Du ja mit den Winkelfunktionen
berechnen kannst; und dann überlayern kannst.
Sind dann halt immer die gleichen Werte...

Gruß, Jens

[Edzard Egberts]

Post by Jens Kallup

Das mit den Knoten habe ich aus dem Clustering...

ja, auf Seite 24, wollte ich andeuten, das was Du
schon rausgefunden hast - Knoten zu Punkten.
Es ist nämlich so, das es ja unterschiedliche
Wolken-Arten mit unterschiedlichen Namen, und
unterschiedlicher Höhe und Vorkommens gibt.

Egal, die kann man alle über den Schwerpunkt der Kontur beschreiben und
landet dann bei Punktmustern. Das funktioniert, im Vergleich zum Optical
Flow steht die Windrichtung jetzt wie festgenagelt, obwohl ich gerade
nur den Peak auswerte. Bei einem 15s-Intervall ist das aber keine Kunst,
spannend wird es für längere Intervalle und hohe Windgeschwindigkeit,
dann kann man den "nächsten Punkt" nur noch über das Muster bestimmen...

[Jens Kallup]

Post by Edzard Egberts
dann kann man den "nächsten Punkt" nur noch über das Muster bestimmen...

was ist mit einen Berghang?
Wo Wolken durch Aufwind hochgezogen, und dadurch kleiner werden?

[Edzard Egberts]

Post by Jens Kallup

Post by Edzard Egberts
dann kann man den "nächsten Punkt" nur noch über das Muster bestimmen...

was ist mit einen Berghang?
Wo Wolken durch Aufwind hochgezogen, und dadurch kleiner werden?

Was soll damit sein? Die werden eben kleiner und sind irgendwann weg.
Das passiert auch mit Wolken, die quer durch das Bild ziehen, da gibt es
richtige Korridore.

Die Aufgabenstellung ist übrigens, Bewegungsrichtung und Geschwindigkeit
festzustellen, ich habe den Eindruck, dass Du über etwas anderes
nachdenkst. ;o)

[Hans-Peter Diettrich]

Post by Edzard Egberts
Die Aufgabenstellung ist übrigens, Bewegungsrichtung und Geschwindigkeit
festzustellen, ich habe den Eindruck, dass Du über etwas anderes
nachdenkst. ;o)

Dabei auch an Kondensstreifen denken - sehe ich viele jeden Morgen, in
vielen Richtungen. Das wäre was für einen späteren Filter...

DoDi

[Edzard Egberts]

Post by Hans-Peter Diettrich

Post by Edzard Egberts
Die Aufgabenstellung ist übrigens, Bewegungsrichtung und
Geschwindigkeit festzustellen, ich habe den Eindruck, dass Du über
etwas anderes nachdenkst. ;o)

Dabei auch an Kondensstreifen denken - sehe ich viele jeden Morgen, in
vielen Richtungen. Das wäre was für einen späteren Filter...

Ein französischer Meteorologe (frag' mich jetzt nicht, von welcher Uni)
benutzt das, um die Windgeschwindigkeit ganz oben zu messen. Der Trick
dabei ist, dass die Flugdaten öffentlich sind und man herausfinden kann,
in welcher Höhe der Kondensstreifen produziert wurde, dann noch die
Verschiebung bestimmen, etwas Geometrie und voila - [m/s].

Ich habe auch schon einen Ansatz zur automatischen Erkennung von
Kondensstreifen ausprobiert, aber die Hough-Transformation ist daran
erbärmlich gescheitert, weil das keine richtigen Linien sind (bei
genauer Betrachtung). Wäre ja schon toll, wenn man die Chemtrails
erkennen könnte, bevor sie einem auf den Kopf fallen! ;o)

[Jens Kallup]

Wäre ja schon toll, wenn man die Chemtrails erkennen könnte, bevor sie
einem auf den Kopf fallen! ;o)

pssst.