Discussion:
Bewegungserkennung
(zu alt für eine Antwort)
Stefan Ram
2018-08-03 15:21:42 UTC
Permalink
Ich glaube so etwas Ähnliches wurde hier schon einmal
behandelt, ich finde es jetzt nicht mehr:

Gegeben seien zwei Bilder (als digitale Bilddateien): Das
eine ist gegenüber dem anderen verschoben, aber mindestens
80 Prozent der Fläche der beiden Bilder überlappen sich.
Dort, wo sie sich überlappen, enthalten die Pixel mit dem
gleichen Inhalt allerdings nicht immer die gleichen
RGB-Werte: Durch Rauschen oder kleine Änderungen im Original
können diese voneinander abweichen. Aber ein Mensch kann
klar erkennen, daß beide Bilder praktisch denselben Inhalt
zeigen, und beim zweiten nur der Bildausschnitt etwas
verschoben ist.

Gesucht ist jetzt ein Algorithmus, welcher den
Verschiebungswert findet: Wie muß man das zweite Bild
verschieben, damit die Pixel zum "gleichen Inhalt" im
Überlappungsbereich sich an derselben Position befinden wie
beim ersten Bild?

Brute-Force-Algorithmus: Man probiert alle
Verschiebungsvektoren +(x,y) durch und berechnet den (ggf.
geeignet normierten) Korrelationskoeffizienten der RGB-Werte
der beiden Bilder im Überlappungsbereich. Der gesuchte
Verschiebungsvektor ist derjenige, bei welchem der
Korrelationskoeffizient maximal ist.

Nun ist die Frage, ob es noch effizientere Algorithmen als
jenen Brute-Force-Algorithmus gibt?
Ralf Goertz
2018-08-03 15:32:34 UTC
Permalink
Am 3 Aug 2018 15:21:42 GMT
Post by Stefan Ram
Ich glaube so etwas Ähnliches wurde hier schon einmal
Gegeben seien zwei Bilder (als digitale Bilddateien): Das
eine ist gegenüber dem anderen verschoben, aber mindestens
80 Prozent der Fläche der beiden Bilder überlappen sich.
Dort, wo sie sich überlappen, enthalten die Pixel mit dem
gleichen Inhalt allerdings nicht immer die gleichen
RGB-Werte: Durch Rauschen oder kleine Änderungen im Original
können diese voneinander abweichen. Aber ein Mensch kann
klar erkennen, daß beide Bilder praktisch denselben Inhalt
zeigen, und beim zweiten nur der Bildausschnitt etwas
verschoben ist.
Vermutlich wird es bei den Video-Encodern effiziente Algorithmen geben:

https://en.wikipedia.org/wiki/MPEG-1#Motion_vectors
Andreas Leitgeb
2018-08-03 17:38:25 UTC
Permalink
Post by Stefan Ram
Ich glaube so etwas Ähnliches wurde hier schon einmal
Habs damals nicht genau verfolgt, aber irgendwer hat eine
Fourier-(oder andersnamige) Transformation vorgeschlagen,
aus der man dann zu jedem Pixel (mit den Verschiebungs-
koordinaten) die "Ähnlichkeit" nach entsprechender
Verschiebung ablesen konnte.

Keine Haftung für die Genauigkeit dieser Zusammenfassung.
Christian Gollwitzer
2018-08-03 18:09:42 UTC
Permalink
Post by Stefan Ram
Ich glaube so etwas Ähnliches wurde hier schon einmal
Gegeben seien zwei Bilder (als digitale Bilddateien): Das
eine ist gegenüber dem anderen verschoben, aber mindestens
80 Prozent der Fläche der beiden Bilder überlappen sich.
Dort, wo sie sich überlappen, enthalten die Pixel mit dem
gleichen Inhalt allerdings nicht immer die gleichen
RGB-Werte: Durch Rauschen oder kleine Änderungen im Original
können diese voneinander abweichen. Aber ein Mensch kann
klar erkennen, daß beide Bilder praktisch denselben Inhalt
zeigen, und beim zweiten nur der Bildausschnitt etwas
verschoben ist.
Gesucht ist jetzt ein Algorithmus, welcher den
Verschiebungswert findet: Wie muß man das zweite Bild
verschieben, damit die Pixel zum "gleichen Inhalt" im
Überlappungsbereich sich an derselben Position befinden wie
beim ersten Bild?
Da gibt's eine ganze Menge Algorithmen dafür. FFT ist ein naheligendes
Verfahren: Die Kreuzkorrelation ist im Fourierraum das Produkt der
Transformierten von Deinen Bildern. Wenn als FT(A) die FFT vom Input A
ist, dann gilt

FT(C) = FT(A)*conj(FT(B)),

wobei conj() Komplexkonjugation heißen soll. Dann hat man mit 2 FFT und
einer IFFT die ganze Kreuzkorrelationsfunktion und muss nur noch das
Maximum suchen. Meistens ist das Maximum da ziemlich unscharf. Ein
verbessertes Verfahren ist die Phasenkorrelation, wo man im Fourierraum
die Amplitude wegschmeißt. also man rechnet zunächst auch

FTC = FT(A)*conj(FT(B))
C = IFT(C / abs(C))

(die Null muss man natürlich filtern). Da ergibt sich dann in der Regel
ein einzelner sehr scharfer Peak. Die direkten Verfahren sind allerdings
im Subpixelbereich genauer als die Fourierverfahren.

Dann kommt noch ein Problem hinzu, Du schreibst dass der Überlapp 80%
beträgt, das ist in meinen Augen schon eine gewaltige Verschiebung. Bei
der FT wird ja in der Regel eine periodische Fortsetzung am Rand
angenommen. Bei dieser Verschiebung hättest Du also schon 20% Pixel, die
die "falsche" Korrelationinformation ergeben. Das kann man mit Padding
und evtl. Windowing verbessern, also nach außen hin mit Nullen auffüllen
und die Werte innen mit einer nach Null abfallenden Funktion
multiplizieren, etwa einem Gauß.

Das Stichwort zum Googlen lautet auch "digital image correlation (dic)"

Viel Spaß,

Christian
Jens Kallup
2018-08-03 18:15:34 UTC
Permalink
Hallo,

schaust mal hier:
http://kallup.freecluster.eu/detect.zip

Gruß, Jens

Loading...