Bewegungsanalyse in digitalen Bildfolgen

Die Erfindung betrifft die Analyse von Bewegungen realer Gegenstände in digitalen Bildfolgen. Insbesondere bei Anwendungen von 'Augmented Reality', bei denen einem realen Videostrom virtuelle Objekte überlagert werden, ist eine Beeinflussung der Bildinhalte durch im Bild sichtbare reale Objekte sinnvoll. Ein einfaches Beispiel einer solchen Anwendung ist in dem Artikel von V. Paelke, Ch. Reimann und D. Stichling, "Foot-based mobile Interaction with Games", ACE2004, Singapore, Juni 2004, beschrieben, bei dem ein virtueller Fußball durch den realen Fuß des Spielers anzustoßen ist. Hierzu wird eine Einrichtung benötigt, die aus dem Videobild die Bewegung des Fußes bestimmt. Eine der hierzu bekannten Methoden ist die Bestimmung von Kanten im Videobild, und darauf aufbauend die Bewegungsanalyse der extrahierten Kanten. Um die Kantenbewegung bestimmen zu können, wird zunächst versucht, die Kanten durch Polygonzüge zu approximieren. Das gilt auch für den o.g. Artikel; siehe S.2, linke Spalte, Absatz unter

Fig. 2, erster Satz: "To perfom collision detection, straight edges inside the ROI are vectorized and tracked between two consecutive images". Es werden gerade Kanten (in dem interessierenden Bereich, ROI = region of interest) vektorisiert und deren Bewegung nachvollzogen. Dazu müssen die vektorisierten Kanten der zweier Bilder einer Folge einander zugeordnet werden, unter Berücksichtigung, dass der neue Vektor sowohl eine andere Lage im Raum als auch eine andere Länge haben kann, aber beide Werte unterhalb einer vorgegebenene Schranke liegen. Diese Berechunung sind relativ aufwändig .

Andere Methoden sind hauptsächlich unter zwei Stichwörtern zu finden: 'Tracking' und 'Optical Flow'. Unter 'Tracking' sind auch Techniken zu finden, die die Bewegung einer Kamera bestimmen und daher hier nicht relevant sind.

Eine übersicht über den Stand der Technik im Bereich des 'Tracking' ist in dem technischen Bericht TR VRVis 2001 025, "State of the Art Report on Optical Tracking" von Miguel

Ribo, Wien 2001, enthalten. Für Anwendungen der oben genannten Art entfallen dabei alle Verfahren mit besonders präparierten Gegenständen sowie solche, bei denen ein Modell des zu verfolgenden Gegenstands vorgegeben sein muss. Die verbleibenden Verfahren setzen entweder Kantenverfolgung oder aufwendige Matrixoperationen ein, um diejenige Bewegung zu bestimmen, mit der eine minimale Abweichung der Bildinformation bestimmt wird. Darunter fallen auch Verfahren, wie sie im Artikel von C-L. Huang, Y. -R. Choo und P. -C. Chung, "Combining Region-based Differential and Matching Algorithms to Obtain Accurate Motion Vectors for Moving Object in a Video Sequence", ICDCSW02, 2002, beschrieben sind. Bekannt sind dabei die dort aufgeführten Verfahren von Horn-Schunk oder Lucas-Kanade, die zu den Optical-Flow-Verfahren zählen. Sie bestimmen die Gradienten durch Differentialbildung und benötigen erheblichen Rechenaufwand. Gleiches gilt für die in dem Artikel von B. Galvin, B. McCane, K. Novins, D. Mason und S. Mills, "Recovering Motion Fields: An Evaluation of Eight Optical Flow Algorithms", BMVC98, 1998, dargestellen

Verfahren. Die meisten der genannten Methoden haben zudem den Nachteil, empfindlich gegen Bildstörungen zu sein und zu deren Kompensation weitere Schritte zu benötigen. Bewegungsanalyse für aufeinander folgende Videobilder wird auch in den MPEG-Codierverfahren verwendet, in denen für

Kompressionszwecke die Bewegung von Pixelblöcken fester Größe bestimmt wird. Dabei ist es unerheblich, ob diese der Bewegung von Bildobjekten entspricht; diese Methoden sind daher im Rahmen von 'Augmented Reality' nicht verwendbar. Die im Folgenden näher beschriebenen Methoden sind hingegen wesentlich einfacher, schneller und robuster als die bislang bekannten Methoden. Sie benötigen kein Modell des im Bild ganz oder teilweise sichtbaren Gegenstands und verlangen keine Vektorsierung von Kanten; sie zudem relativ unempfindlich gegen Bildrauschen und andere Störungen, die bei einer herkömmlichen Kantenerkennung das Kantenbild stören .

Es handelt sich um eine Methode zur Erkennung der Bewegung von Bildausschnitten in digitalen Bildfolgen, bei der nach einer Konturenhervorhebung in einem ausgewählten Ausschnitt zu jedem Pixel der Mittelwert der Verschiebungsvektoren zu benachbarten Pixeln bestimmt und sodann der Mittelwert aller dieser Verschiebungsvektoren gebildet und als Verschiebungsvektor für einen in dem Ausschnitt sichtbaren Gegenstand verwendet wird. Vor der Anwendung der nachfolgend genauer beschriebenen Methode wird jedes einzelne Bild aus der Bildfolge durch bekannte Filter vorbehandelt. Diese Filter dienen der Farbreduktion der Bildpixel, der Verringerung des Rauschens und der Hervorhebung von Konturen bzw. Kanten. Die Art und der Umfang der Vorbehandlung ist je nach Anwendung zu bestimmen. In einer Anwendung in einem Handgerät wie einem Mobiltelefon mit Kamera war es vorteilhaft, sämtliche der folgenden Filter anzuwenden.

Farbige Ausgangsbilder werden zunächst (zum Beispiel durch Mittelwertbildung aller Farbkanäle eines jeden Pixels) in Graustufen umgewandelt. Stark verrauschte Bilder können optional durch einen Gauß-Filter geglättet werden; dies kann beispielsweise erfolgen, wenn ein Sensor eine geringe Umgebungshelligkeit feststellt. Anschließend wird aus dem Graustufenbild durch Konturenfilter ein Kantenbild erstellt. In der Praxis wird dazu oft der Sobel-Filter verwendet.

Alternativ können auch der Prewitt-Filter, der Laplace-Filter oder vergleichbare Filter zur Erzeugung eines Kantenbildes eingesetzt werden. In einer Ausprägung der Erfindung wird ein reines schwarz- weiss-Bild mit 1 Bit per Pixel verwendet, d.h. die

Helligkeitswerte werden auf ein Bit reduziert, so dass jedes Pixel binär entweder weiß (0 bzw. „keine Kante") oder schwarz (1 bzw. „Kante") ist. Der Schwellwert für diese Umwandlung kann entweder fest vorgegeben sein oder relativ zum Mittel- oder Medianwert der Graustufen bestimmt werden. Pixel mit dem Wert 1 werden im Folgenden einfacherweise als Kantenpixel bezeichnet, auch wenn die Erfindung keine Kanten

vektorisiert , sondern die Bewegung ohne die Rekonstruktion von Kanten aus Pixelbewegungen zu bestimmen erlaubt. Anstelle der expliziten Bestimmung von Kanten erfolgt gemäß der Erfindung erfolgt die Berechnung der Bewegung eines BiId- ausschnittes in zwei aufeinander folgenden Bildern (z.B. zur impliziten Kollisionserkennung mit einem virtuellen Objekt) durch zwei verschachtelte Schritte, die lediglich auf die Pixel des Bildes Bezug nehmen. Diese Pixel sind bevorzugt die o.g. Kantenpixel. 1. Für jedes einzelne Kantenpixel wird eine Bewegung berechnet (siehe Schritt 2) . Anschließend werden die Bewegungen aller Kantenpixel des Bildausschnittes gemittelt. Das Mittel ist die Bewegung des gesamten Ausschnittes und somit eines Gegenstandes, der sich ganz oder teilweise in dem Bildausschnitt befindet.

2. Da die Kantenpixel keine Attribute besitzen (wie zum Beispiel Helligkeit, Muster usw.), kann keine eindeutige Zuordnung zwischen einem Kantenpixel im aktuellen Bild und einem Kantenpixel im vorherigen Bild erfolgen. Daher wird die Bewegung eines Kantenpixels in Bezug zu benachbarten

Kantenpixeln berechnet, indem Verschiebungsvektoren zu den benachbarten Kantenpixeln bestimmt und gemittelt werden. Als Verschiebungsvektor (2-dimensional) wird der Vektor von der Position des Pixels im aktuellen Bild zur Position eines Umgebungspixels im vorherigen Bild bezeichnet.

Im nachfolgenden Beispiel wird der Einfachheit halber ein quadratischer Bildausschnitt von fünf mal fünf Punkten verwendet. Fig. Ia zeigt das Eingabebild, das in Form von Graustufen vorliegt. Nach Anwendung eines Kantenfilters verbleiben vier Pixel, wie in Fig. Ib dargestellt. Für die nachfolgende Beschreibung wurden die Pixel durchnummeriert . Angenommen, in dem Folgebild habe sich das Objekt nach oben bewegt. Das Ergebnis ist in Fig. Ic dargestellt, wobei die im vorherigen Bild besetzten Positionen durch Kreise markiert sind.

In einer ersten Variante der Erfindung wird für jedes Kantenpixel im aktuellen Bild (1', 2', 3' und 4') die

Bewegung berechnet. In diesem Beispiel wird dazu die 9er- Nachbarschaft verwendet, also alle Positionen, die direkt oder diagonal mit der aktuellen Position benachbart sind und die aktuelle Position selbst, d.h. es werden Pixel in einem vorgegebenen Abstand betrachtet. Kantenpixel 1' hat zwei benachbarte Kantenpixel im vorherigen Bild (1 und 2) . Die gemittelte Bewegung M _1' von 1' lautet somit:

Entsprechend ergeben sich für die anderen Pixel folgende Be- wegungen:

Um die gesamte Bewegung M des Bildausschnittes zu berechnen, wird das Mittel aller einzelnen Bewegungen ermittelt:

Es ist zu erkennen, dass eine starke Bewegung nach oben (- 0,5) und eine sehr geringe Bewegung nach rechts (0,083) detektiert wurde. In einem alternativen Berechnungverfahren werden alle Punkte verwendet, bei denen sich der Pixelwert geändert hat. Hierzu dient Fig. 2a zur Veranschaulichung; hier sind der übersichtlichkeit halber gegenüber Fig. Ic die schwarzen Blöcke entfernt worden und die Kreise kleiner. Punkte, bei denen sich die Pixelwerte geändert haben, sind im Beispiel die nicht eingekreisten Punkte 1 bis 3. Punkt 4 wird nicht berücksichtigt, da sich der Pixelwert nicht geändert hat. Zu jedem der (geänderten) Punkte 1 bis 3 und jedem im vorheigen Bild im Bereich gesetzten Punkte wird nun ein Abstandsvektor gebildet, dies ist in Fig. 2a für Punkt 1 durch Pfeile angedeutet und in der folgenden Tabelle aufgeführt; der Mittelwert dieser Vektoren wird durch Mittlung der x- und y-

Werte gebildet und ergibt die letzte Spalte, mit MW für Mittelwert bezeichnet:

Dabei werden nur solche Punkte berücksichtigt, die in einer vorgegebenen Umgebung des jeweiligen Punktes vorhanden sind, im Beispiel sind das zwei Pixel in x- bzw. y-Richtung, also eine 25er-Nachbarschaft . Daher entfallen die Vektoren für den Abstand vom neuen Punkt 2 zum alten Punkt 4 und vom neuen Punkt 3 zum alten Punkt 1, die deshalb in Klammern gesetzt sind. Im Unterschied zu der vorherigen Variante wurden hier nur geänderte Pixelwerte berücksichtigt, dafür jedoch ein grosserer Bereich.

Von den Mittelwerten der Punkte wird dann auf die gleiche Art ein neuer Mittelwert gebildet, der bereits das Ergebnis darstellt. Auch hier ergibt sich richtig eine Bewegung nach oben Der Wert der tatsächlichen Verschiebung ist 0/-1. In den beiden Beispielen wurden schwarz-weiss-Bilder verwendet, bei denen die schwarzen Bildpunkt durch Filter Kanten entsprechen, und nur diese schwarzen Pixel berücksichtigt wurden. Die Erfindung ist jedoch nicht hierauf beschränkt. Wenn größerer Genauigkeit im Ausgleich für mehr Rechenleistung benötigt wird, kann das Verfahren auch für Graustufen- oder farbige Bilder angewendet werden. Hierbei werden zu einem Pixel in dem aktuellen Bild zunächst alle Pixel des Vorgängerbildes ermittelt, die dem Pixel gleichwertig sind. Im Falle von Graustufen-Bildern sind das Pixel der gleichen Graustufe bezüglich einer vorgegebenen Schranke der Abweichung; bei 8 Bit oder 256 Graustufen beispielsweise 8 Graustufenwerte. Alternativ kann auch vorab das Graustufen-Bild quantisiert werden, indem von den 256 möglichen Graustufen nur 16 Graustufen verwendet werden und die übrigen auf diese 16 Werte gerundet werden, und dann exakte Gleichheit der Pixelwerte verwendet wird. Beide Ver-

fahren geben geringfügig unterschiedliche Gleichwertigkeiten, da die Quantisierung zu unterschiedlich ist. In den oben dargestellten Beispielen wurde nach den Kantenfiltern eine Quantisierung auf 1 Bit vor der Bestimmung der gleichwertigen Pixel durchgeführt und die weissen Pixel nicht verwendet. Es wurde als zunächst quantisiert und dann nur Pixel in einem vorbestimmten Intervall, hier nur die schwarzen Pixel, verwendet. Da hier der Färb- bzw. Grauwert nur noch ein Bit beträgt, ist hier nur die Gleichheit der Pixelwerte sinnvoll. Die Erfindung kann in einer Anwendung von erweiterter

Realität ( ' augmented reality') verwendet werden, um mit wenig Rechenaufwand eine Interaktion zwischen realen und virtuellen Gegenständen zu bewirken. Beispielsweise wird ein Mobiltelefon verwendet, das eine Kamera auf der Rückseite und einen Bildschirm auf der Vorderseite umfasst, und das

Kamerabild auf dem Bildschirm reproduziert wird, so das scheinbar durch den Bildschirm auf die dahinterliegende Szene geblickt werden kann. Der virtuelle Gegenstand sei, wie in dem eingangs erwähnten Artikel, ein Ball. Durch die Erfindung wird ein wesentlich verbessertes Verfahren angegeben, um die Bewegung eines realen Fusses zu erkennen und den Stoß in Richtung auf den virtuellen Ball zu erkennen. Die in dem oben genannten Artikel beschriebenen bekannten Verfahren konnten hingegen nur durch Delegation auf über ein Netzwerk ver- bundenen leistungsfähigeren Rechner in Realzeit verwendet werden .