Ich denke, es gibt Zeiten, in denen ich in einer Krabbe gefangen und gehoben werde, aber ich möchte analysieren, wie gewalttätig die Bewegung zu dieser Zeit war! Ich glaube nicht, dass es Fälle gibt.

Quelle: ASIAN KUNG-FU GENERATION "To Your Town" ([Solfa Remake Memorial](http://ro69.jp/news/ Detail / 13427)))

Optischer Fluss drückt die Bewegung zwischen Bildern aus (?). Optischer Fluss beschreibt, wie sich jeder Punkt zwischen zwei Bildern bewegt. Durch Berechnen ist es möglich, die Bewegung von Merkmalspunkten auf dem Bild zu analysieren, wie in der obigen Abbildung gezeigt.

In diesem Artikel möchte ich den theoretischen Hintergrund für die Berechnung des optischen Flusses und die Implementierung mit Python / OpenCV vorstellen.

Positionierung des optischen Flusses

Es gibt verschiedene Zwecke und Methoden, um dies bei der Analyse der Bewegung zwischen Bildern zu erreichen. Hier werde ich zunächst erklären, wie der optische Fluss darin positioniert ist.

Verfolgung
Zweck: Ich möchte ein bestimmtes Objekt (Person oder Objekt) in einem Bild verfolgen
Methode: Es gibt zwei Haupttypen, einen in Echtzeit und einen nicht.
-> Echtzeit-Typ: Das Zielobjekt wird durch verschiedene Methoden wie Vorlagenabgleich und mittlere Verschiebung dargestellt, und die Verfolgung wird zwischen Bildrahmen durchgeführt.
-> Stapeltyp: Nachdem alle Bilder verfügbar sind, wird die Bewegung durch eine dynamische Planungsmethode usw. zurückgerechnet.
Durchflussschätzung
Zweck: Ich möchte erkennen, was sich im Bild bewegt hat (im Gegensatz zur Verfolgung, wo das Beobachtungsziel festgelegt ist).
Methode: Es kann grob in einen spärlichen Typ unterteilt werden, der nur charakteristische Punkte im Bild analysiert, und einen dichten Typ, der die Bewegung des gesamten Pixels analysiert.
-> spärlicher Typ: Lucas-Kanade-Methode usw.
-> Dichter Typ: Horn-Schunck-Methode, Gunnar-Farneback-Methode usw.

Tatsächlich sind die Hindernisse für die Klassifizierung nicht eindeutig, wie beispielsweise die zur Verfolgung verwendete Durchflussschätzungsmethode, und sie mag ein wenig chaotisch erscheinen, da sie nach der verwendeten Methode unterteilt werden kann, aber auf diese Weise grob unterteilt ist.

Und wie der Name schon sagt, ist der diesmal eingeführte optische Fluss eine Flussschätzung.

Theorie

Jetzt werde ich den theoretischen Inhalt der Berechnung des optischen Flusses erläutern.

Es ist leicht zu verstehen, wenn Sie sich einen flatternden Cartoon vorstellen, aber am Ende ist ein Video ein kontinuierliches Bild.

Wenn Sie also die Bewegung zwischen zwei Bildern analysieren können, können Sie sie anscheinend verbinden und die Bewegung des gesamten Videos verdeutlichen.

Wie können Sie die Bewegung zwischen zwei Bildern abschätzen?

Die Tatsache, dass es Bewegung gibt, bedeutet, dass ein Punkt auf dem Bild zu einem anderen verschoben wurde. Wenn sich dagegen etwas anderes als die Position (Farbe usw.) ändert, gibt es keine Möglichkeit mehr, sie zu verfolgen. Daher sollte die Farbe (die während der Verarbeitung häufig in Graustufen umgewandelt wird, also "Helligkeit") zwischen den beiden Bildern gleich sein. Und machen Sie die Annahme.

Die Formel wird von hier herauskommen, aber bitte seien Sie versichert, dass sie nacheinander fortgesetzt wird.

Sei $ I (x, y, t) $ die Helligkeit der Punkte $ x, y $ auf dem Bild $ I $ zu einem bestimmten Zeitpunkt $ t $. Wenn die Zeit um $ \ Delta t $ vorrückt und sich die Koordinaten während dieser Zeit um $ \ Delta x, \ Delta y $ bewegen, beträgt die Helligkeit des Ziels $ I (x + \ Delta x, y + \ Delta y, t + \ Delta t) $. Da wir davon ausgegangen sind, dass sich diese nicht hätten ändern dürfen, gilt die folgende Gleichung.

I(x, y, t) = I(x + \Delta x, y + \Delta y, t + \Delta t)

Aus dieser Gleichung ist es nun möglich, endgültig $ \ frac {\ Delta x} {\ Delta t}, \ frac {\ Delta y} {\ Delta t} $ abzuleiten, dh den Betrag der Koordinatenänderung pro Zeiteinheit. Es wird das Ziel der Berechnung von sein.

Verwenden Sie zunächst die Taylor-Erweiterung, um die rechte Seite zu approximieren. Ich bin der Meinung, dass die Taylor-Erweiterung eine äußerst schwierige Technik verwendet, aber sie wird einfach in einen Wert umgewandelt, der nahe am wahren Wert liegt. Eine kurze Erklärung finden Sie unter hier.

I(x + \Delta x, y + \Delta y, t + \Delta t) = I(x, y, t) + \frac{\partial I}{\partial x} \Delta x + \frac{\partial I}{\partial y} \Delta y + \frac{\partial I}{\partial t} \Delta t + ...

Danach wird es noch lange dauern, aber im weiteren Verlauf wird es immer kleiner, also werde ich den Sprung wagen und es abschneiden, um nur die erste Entwicklung zu machen.

I(x + \Delta x, y + \Delta y, t + \Delta t) = I(x, y, t) + \frac{\partial I}{\partial x} \Delta x + \frac{\partial I}{\partial y} \Delta y + \frac{\partial I}{\partial t} \Delta ｔ

Was dann passiert, ist wie folgt.

I(x, y, t) = I(x + \Delta x, y + \Delta y, t + \Delta t) = I(x, y, t) + \frac{\partial I}{\partial x} \Delta x + \frac{\partial I}{\partial y} \Delta y + \frac{\partial I}{\partial t} \Delta ｔ

Dann $ \ frac {\ partielles I} {\ partielles x} \ Delta x + \ frac {\ partielles I} {\ partielles y} \ Delta y + \ frac {\ partielles I} {\ partielles t} \ Delta t Wenn es nicht = 0 $ ist, gelten die Gleichungen nicht, also nennen wir sie 0. Wenn Sie diese Formel durch $ \ Delta t $ dividieren, dh den Änderungsbetrag im Laufe der Zeit, erhalten Sie:

\frac{\partial I}{\partial x} \frac{\Delta x}{\Delta t} + \frac{\partial I}{\partial y} \frac{\Delta y}{{\Delta t}} + \frac{\partial I}{\partial t} = 0

Der Einfachheit halber lautet die Notation $ \ frac {\ partielles I} {\ partielles x} = I_x $ wie folgt.

I_x \frac{\Delta x}{\Delta t} + I_y \frac{\Delta y}{{\Delta t}} + I_t = 0

Schließlich kam $ \ frac {\ Delta x} {\ Delta t}, \ frac {\ Delta y} {{\ Delta t}} $ heraus. Wenn man die Bewegungsmenge pro Zeiteinheit für $ x und y $ in Form des Vektors $ \ bf {v} $ zusammenfasst, kann die folgende Gleichung endgültig gelöst werden.

I_x {\bf v_x} + I_y {\bf v_y} + I_t = 0 \\\\ \nabla I^T {\bf v} = - I_t

Aus der Schlussfolgerung kann diese Formel jedoch nicht so gelöst werden, wie sie ist. Ich habe bisher mein Bestes versucht, der Formel zu folgen, aber ich weiß es nicht! Dies ist jedoch unvermeidlich, da es nur eine Gleichung gibt, während zwei Unbekannte (zweidimensional) wie $ {\ bf v_x} $ und $ {\ bf v_y} $ vorhanden sind. Dieses Problem, mit dem wir bei der Suche nach optischem Fluss konfrontiert sind, wird als Aperturproblem bezeichnet (warum wir dies sagen, erfordert es schließlich andere Einschränkungen für eine lange Erklärung, nichts weiter als das. Ich habe es nicht gesagt, also werde ich es hier weglassen.

Um diese Situation zu lösen, müssen wir mindestens eine einschränkende Gleichung erhöhen. Dies ist das Hauptthema, und das Hauptthema verschiedener Methoden zur Bewegungserkennung ist die Anwendung dieser "Einschränkung", und es wurden verschiedene Ideen vorgeschlagen.

Hier möchte ich zwei Methoden vorstellen, die Lucas-Kanade-Methode, die für den spärlichen Typ repräsentativ ist, und die Horn-Schunck-Methode, die eine dichte Methode ist.

Lucas-Kanade-Methode

Die Lucas-Kanade-Methode setzt räumliche Integrität voraus und schränkt sie ein. Der Punkt ist anzunehmen, dass sich die umgebenden Punkte auf die gleiche Weise verhalten sollten.

Unter der Annahme, dass die peripheren Punkte $ q_1 ... q_n $ sind und sich alle ähnlich verhalten, kann die Beschränkungsgleichung wie folgt aufgeblasen werden:

I_x(q_1) {\bf v_x} + I_y(q_1) {\bf v_y} = - I_t(q_1) \\\\ I_x(q_2) {\bf v_x} + I_y(q_2) {\bf v_y} = - I_t(q_2) \\\\ ... \\\\ I_x(q_n) {\bf v_x} + I_y(q_n) {\bf v_y} = - I_t(q_n) \\\\

Hier wird jeder Term wie folgt in einer Matrix zusammengefasst.

A = \left[ \begin{array}{cc} I_x(q_1) & I_y(q_1) \\\\ I_x(q_2) & I_y(q_2) \\\\ \vdots & \vdots \\\\ I_x(q_n) & I_y(q_n) \end{array} \right] \\ b = \left[ \begin{array}{c} - I_t(q_1) \\\\ - I_t(q_2) \\\\ \vdots \\\\ - I_t(q_1) \end{array} \right]

Dann können Sie einfach wie folgt schreiben.

A{\bf v} = b

Alles was Sie tun müssen, ist diese simultane Gleichung zu lösen. Dies kann mit der Methode der kleinsten Quadrate gelöst werden(Zusamenfassend||b - A{\bf v}||^2Finden Sie den Punkt, der den quadratischen Fehler minimiert, der durch Differenzierung ausgedrückt werden kann)Schließlich kann es wie folgt ausgedrückt werden.

{\bf v} = (A^TA)^{-1} A^Tb

Um diese Gleichung zu lösen, wird vorausgesetzt, dass es in $ A ^ TA $ (reversibel) eine inverse Matrix gibt, wie in der Gleichung gezeigt, aber Harris-Eckendetektion und Shi, die typische Methoden zur Merkmalspunkterkennung sind, -Es gilt, dass es durch Tomasi-Erkennung erkannt werden kann.

Horn-Schunck-Methode

Die Horn-Schunck-Methode schränkt die „Laufruhe“ ein. Der Punkt ist, dass derjenige, der die kürzeste Strecke zurücklegt, der bessere $ {\ bf v} $ ist.

Die Kosten (Energie) der Bewegung seien $ E ({\ bf v}) $ und definieren sie wie folgt. Dies ist ein Kostenfaktor. Je kleiner er ist, desto besser.

E({\bf v}) = E_{data}({\bf v}) + \alpha E_{smooth}({\bf v})

Hier repräsentiert $ E_ {data} ({\ bf v}) $ die erste vorliegende Gleichung. Wie oben erwähnt, sollte $ I_x {\ bf v_x} + I_y {\ bf v_y} + I_t $ 0 sein. Je näher es an 0 liegt, desto besser ist $ {\ bf v} $. Im Folgenden wird die Integration durchgeführt, um das gesamte Bild zu addieren.

E_{data}({\bf v}) = \int\int (I_x {\bf v_x} + I_y {\bf v_y} + I_t) ^2 dxdy

Und $ E_ {glatt} ({\ bf v}) $ ist die Einschränkung für "Glätte".

E_{smooth}({\bf v}) = \int\int || \nabla {\bf v_x} || ^2 + || \nabla {\bf v_y} || ^2 dxdy

Dies bedeutet, dass je kleiner der Änderungsbetrag in $ {\ bf v} $ ist, desto besser, dh desto besser derjenige, der "den Punkt erreicht, an dem sich die Helligkeit mit einem geringen Änderungsbetrag nicht ändert". $ \ Alpha $ ist ein Faktor dafür, wie viel Gewicht auf diese Glättungsbeschränkung gelegt wird.

Wenn Sie diese Gleichung als Minimierungsproblem lösen, erhalten Sie das gewünschte $ {\ bf v} $. Ich werde die nachfolgende Entwicklung zum Lösen weglassen, aber dies ist die Idee der Horn-Schunck-Methode.

Praktische Ausgabe

Jetzt möchte ich die optische Flusserkennung mithilfe von OpenCV implementieren. Hier verwenden wir die Methoden Lucas-Kanade und Gunnar Farneback, für die Implementierungen bereitgestellt werden. Die Gunnar Farneback-Methode ist eine häufig verwendete Methode des dichten Typs (Einschränkungen verwenden benachbarte Punkte wie die Lucas-Kanade-Methode ...).

Das tatsächlich implementierte Beispiel ist unten aufgeführt, aber von nun an wird Domo-kun aus urheberrechtlichen Gründen in NHKs KREATIVE BIBLIOTHEK aufgeführt. mit.

icoxfog417/cv_tutorial/opticalflow

Ich verwende Python3.5, numpy1.10.4 und OpenCV3.1.0 (es ist einfacher, Anaconda / Miniconda zu verwenden). Allerdings verwendet nur Matplotlib die vorherige Version 1.4.3. Dies ist auf einen Fehler bei der Ausführung von nbagg zurückzuführen, der für die Wiedergabe von Animationen in der neuesten Version 1.5.1 ab April 2016 verwendet wurde (Notebook-Backend-Zahlen schließen spontan # 6075. matplotlib / matplotlib / issue / 6075)).

Die Grundlagen für die Implementierung sind wie im OpenCV-Tutorial. Zunächst nach der Lucas-Kanade-Methode.

Du rennst. .. .. Sie können sehen, dass die Flugbahn verfolgt werden kann. Die Lucas-Kanade-Methode erkennt Merkmalspunkte und schätzt den optischen Fluss von Punkten um sie herum. Daher sind die folgenden zwei Punkte die wichtige Verarbeitung.

Funktionspunkterkennung: goodFeaturesToTrack
Berechnung des optischen Durchflusses: calcOpticalFlowPyrLK

Beachten Sie, dass Feature-Punkte natürlich möglicherweise nicht erkannt werden (wenn sie nicht erkannt werden, wird "None" zurückgegeben). Außerdem wurde nichts erkannt, was von der Mitte in das Video geschnitten wurde. Denken Sie daran, dass das, was Sie verfolgen, von Anfang an sichtbar sein muss (ich habe viel versucht, bin mir aber nicht sicher, warum).

Wenn Sie mit der Gunnar Farneback-Methode einen dichten optischen Fluss finden, können Sie die gesamte Bewegung wie folgt erfassen.

Abgesehen davon kann die zum Laden des Videos verwendete VideoCapture auch die Bilddatei übergeben. Ich kann es schaffen Wenn Sie beispielsweise "img_% 02d.jpg " angeben, werden die Dateien mit Seriennummern wie "img_01.jpg ", "img_02.jpg " ... automatisch gelesen. Mit dieser Funktion können Sie ganz einfach einen Para-Para-Manga erstellen. Es macht also Spaß, ihn auszuprobieren.

Das ist alles für die Erklärung. Bitte versuchen Sie die unvergesslichen Bewegungen festzuhalten!

Verweise

Quantitative Biology Society Tutorial Was machen Bildinformatik-Forscher?
Blockbuster-Material. Es ist leicht zu verstehen, da es sorgfältig für andere Dinge als den optischen Fluss geschrieben wurde
Sondervortrag über Image Media Engineering (5)
[Computer Vision Adventskalender 2012] Ableitung und Funktionen der Lucas Kanade-Methode
Introduction to OpenCV
Optical Flow I/ Guido Gerig CS 6320, Spring 2012
Wikipedia (eigentlich ganz einfach zu verstehen)
Optical_flow
Lucas–Kanade method
Horn–Schunck method
OpenCV-Python Tutorials/Optical Flow
Elektronische Informations- und Kommunikationsgesellschaft "Knowledge Forest" Kapitel 4 Videoanalyse
Taylor-Entwicklungskommentar für Anfänger - Tohoku Institute of Technology
OPTFLOW_USE_INITIAL_FLOW option for cvCalculateOpticalFlowFarneback
Dense Optical Flow Expansion Based On Polynomial Basis Approximation

[PYTHON] Optischer Fluss, das von OpenCV aufgenommene dynamische Bild