Embed Size (px)
Citation preview
Die Bestimmung des Optical Flow aus Bildsequenzen
Busa Fekete Robert
Horvath Peter
Die Algorithmen
Was bedeutet eigentlich: Optical Flow?
• Optical Flow: Vektoren, die die Bewegungen zwischen 2 Bildsequenzen zeigen
Bestimmung maximal 1 Pixel großer Bewegungen
),(),(),(),( 111,11
min yjxiIjiIyxjim kkyx
k
1
1
1
11
1
1
1
111,11
),(),(),(),( minu v
ku v
kyx
k yvjxuiIvjuiIyxjim
Wie könnte man die Bewegungen detektieren, die größer sind als 1 Pixel
• Verkleinert man das Bild, dann werden auch die Bewegungen im Bild verkleinert, zB. ist die 2 Einheiten große Bewegung im oberen Bild im unteren Bild, das nur halb so gross ist, nur noch 1 Einheit groß.
Aufbau der Pyramide• Den vorherigen Gedankengang fortführend: wenn man
das Bild n-mal verkleinert, dann würden die 2n großen Bewegungen im n-sten Bild nur noch 1 groß sein. Also wenn wir wissen, dass es maximal n große Bewegungen gibt, dann müssen wir log2 n Stück Bilder fertigen.
Anfertigung der Pyramide 1.• Als Maske benutzen wir die normal verteilte Gauss 2D Standard
Matrix (die Summe der Einträge der Matrix ist auf 1 normalisiert). Am schnellsten funktioniert es, wenn wir 3x3 große Matrix anwenden, aber ich empfehle die Größe 5x5 oder 7x7.
0.003 0.013 0.022 0.013 0.0030.013 0.060 0.098 0.060 0.0130.022 0.098 0.162 0.098 0.0220.013 0.060 0.098 0.060 0.0130.003 0.013 0.022 0.013 0.003
xexf
x
,2
1)(
2
2
22
)(
,
Anfertigung der Pyramide 2.
• Wir koennen auf folgende Weise von einem 2n+1 x 2n+1 großen Bild eines der Größe n+1 x n+1 erzeugen.
Backwards- Strategie 1.
Vom kleineren OF der Pyramide können wir das größere so aufbauen:
• 1. Man verdoppelt die Vektoren
• 2. Die (2i, 2j), (2i+1, 2j), (2i, 2j+1), (2i+1, 2j+1)-sten Vektoren des großen OF bekommen den Wert des Doppelten der Größe des (i, j)-sten Vektors des kleinen OF.
Backwards- Strategie 2.
• 3. Verfeinerung: Suche der maximal 1 Pixel großen Bewegung. Wir haben grobe Schätzungen hinsichtlich der Bewegungen. Jetzt wird dies verfeinert mit Hilfe der früher gezeigten Methode.
Mehr als zwei Sequenzen• Wenn wir mehr als zwei Sequenzen haben, dann kann bei
der Anfertigung des n+1-sten Bildsequenzes das n-ste helfen. Wenn die Sequenzen einander zeitlich häufig folgen, werden mit großer Wahrscheinlichkeit die Vektoren der Bewegungen im n-sten Bild nur etwas abweichen von denen im n+1-sten Bild.
Homogene Gebiete
• Der Algorithmus kann in seinem gegenwärtigem Stand nicht zur Detektierung homogener Gebiete benutzt werden (zB.: rote Schnee fällt im roten Hintergrund ), in solchen Fällen erachten wir es als eine gute Lösung, wenn hierbei der Wert der Bewegung 0 ist.
• Deshalb wird die 3x3 Matrix vor der Aussiebung des Minimums mit einer N(0.0, 3.0) Standard normal verteilten Gauss Matrix multipliziert. Dies beeinflusst in derart geringem Maß die Untersuchung der nicht homogenen Gebiete, dass es in der Praxis keine Probleme bereitet, trotzdem werden die homogene Gebiete gut ausgefiltert.
• Zwecks Beseitigung der auftretenden Fehler glättet man die Vektoren zu ihrer Umgebung. Mehrere solche Methoden können angewandt werden, z.B.:
• 3x3 Maske:
• Man benutzt im gegenwärtigen Algorithmus die früher vorgestellte Gauss N(0.0, 1.5) Matrix in der Größe 5x5.
Glätten 1.
121
242
121
16
1
Glätten 2.OF ohne Erweichung:
Erweichte OF:
Paralelle Rechnungen
• Weil jede Operation nur lokale Bildinformationen benutzt, so koennen wir die Algorithme auf paralelle Rechner implementieren. Also mit Hilfe der Pixel paralelle Rechnungen kann man die Prozesse verschnellern.
Laufzeit
• Laufzeit:• Aufbau der Pyramide:
• Backwards-Strategie:
• Erweichung:
• Insgesamt:
)(...42
...42
22222
222
2 ncnabnnn
nan
an
aan
)(...42
...42
22222
222
2 ncnabnnn
nan
an
aan
)(...42
...42
22222
222
2 ncnabnnn
nan
an
aan
)()(3 22 nn
Erneuerungen
• Gauss Pyramide
• Homogene Bereiche
• Erweichung
Implementation
Das gegenwärtige System
• ANSI C++• Unter Windows entwickelt, aber nur mit
Verwendung von Standard Headers, so ist es platformunabhängig
• Es behandelt Portable Grayscale Map (.pgm 8 bit) und Portable Pixel Map (.ppm 24 bit color) Bilddaten
• Erreichbar:• http://www.stud.u-szeged.hu/Horvath.Peter.3
Class Diagramm
CGaussMatrix classCGaussMatrix::CGaussMatrix(int size, double muf, double sigmaf)
{
...
const1 = 1 / (sqrt(2*M_PI)*sigma);
for (i=0;i<size;i++){
for (j=0;j<size;j++){
tav = sqrt((-((size-1)/2)+i)*(-((size-1)/2)+i)+(-((size-1)/2)+j)*(-((size-1)/2)+j));
Elements[i][j] = const1 * exp( - ( ( (tav - mu)*(tav - mu) ) / (2*sigma*sigma) ));
}
}
i=0;
for (i=0;i<size;i++){
for (j=0;j<size;j++){
norm += Elements[i][j];
}
}
for (i=0;i<size;i++){
for (j=0;j<size;j++){
Elements[i][j] *= (1/norm);
}
}
printf("CGaussMatrix class (new Gaussmatrix %d x %d): succesfull...\n", size, size);
}
CImagePyramid ClassCImagePyramid::CImagePyramid(char *FileName, int Depth, int GaussSize){...
if (Depth > 0){for (int i = 1; i < Depth; i++){
sx = sx >> 1;sy = sy >> 1;if (sx < 1) sx = 1;if (sy < 1) sy = 1;Pyramid[i] = new CPMImage(sx, sy);
}}for(int i = 0; i < Depth-1; i++){ for (incX = 0; incX < Pyramid[i]->GetSizeX(); incX+=2){ for (incY = 0; incY < Pyramid[i]->GetSizeY(); incY+=2){ tmpr = 0.0; tmpg = 0.0; tmpb = 0.0; for (GaussX = - GaussSize / 2; GaussX < GaussSize / 2 + 1; GaussX++){ for (GaussY = - GaussSize / 2; GaussY < GaussSize / 2 + 1; GaussY++){ r += (double)(Pyramid[i]->GetPixel(incX + GaussX, incY + GaussY) & 0x0000FF) *
Gauss->GetXY(GaussX, GaussY); } } }}
}
Experimentelle Ergebnisse
Testumgebung
• Rechner:• PIII Celeron 1200Mhz CPU, 128 Mb RAM
Bildgröße Laufzeit (s)
3x3 Gauss 7x7 Gauss
256x256 15.85 17.34
512x512 61.49 70.17
Experiment 1.
• Rotation (3 Grad nach links):
Experiment 2.
• Verschiebung (x->5 pixel, y->3)
Experiment 3.
Scale (103%)
Referenzen
Referenzen
• [1] P. J. Burt and E. H. Adelson: The Laplacian Pyramid as a Compact Image Code
• [2] P. Anandan: A Comutational Framework and an Algorithm for the Measurement of Visual Motion
• [3] P. Bouthemy and E. Francois: Motion Segmentation and Qualitative Dynamic Scene Analysis from an Image Sequence
• [4] T. Lin J. L. Barron: Image Reconstruction Error for Optical Flow
