DE19549216C2

DE19549216C2 - Verfahren zur Bildauswertung

Info

Publication number: DE19549216C2
Application number: DE19549216A
Authority: DE
Inventors: Axel Korn; Lothar Berger
Original assignee: Fraunhofer Gesellschaft zur Forderung der Angewandten Forschung eV
Current assignee: Fraunhofer Gesellschaft zur Forderung der Angewandten Forschung eV
Priority date: 1995-12-30
Filing date: 1995-12-30
Publication date: 1999-09-09
Anticipated expiration: 2015-12-31
Also published as: DE19549216A1

Description

Die Erfindung betrifft ein Verfahren zur Bildauswertung gemäß dem Oberbegriff des Anspruchs 1, wie es aus der DE 39 13 620 C1 der Anmelderin bekannt ist und bezieht sich insbesondere auf die Lokalisierung und quantitative Beschreibung von Bildstrukturen, deren Kontrast auch sehr gering sein kann. Dazu gehören unter anderem auch Schattierungen in Form langsam veränderlicher Grauwertverläufe, deren Erkennung zu wesentlichen Erleichterungen bei der Interpretation von Ergebnissen einer Berechnung von Konturelementen oder von Flecken führen, die durch Schwellwertoperationen im Originalgrauwertbild erzeugt werden.

Die Erfindung baut auf dem o. g. Verfahren zur Berechnung des Grauwertgradienten auf, auf das bezüglich hier nicht weiter ausgeführte Informationen ausdrücklich verwiesen wird. Auch hier wird Gebrauch gemacht von der Invarianz des Gradientenwinkels gegenüber Multiplikation oder Addition der Grauwertfunktion mit Konstanten.

Aus dem Stand der Technik sind weitere Verfahren und Einrichtungen zur Bildauswertung bekannt, die sich jedoch nicht auf Flächen bzw. Grauwerte derselben beziehen. So ist aus der EP 712 094 A2 bekannt, linienbehaftete Zeichnungen (line art) oder Graphiken, Karten, Buchstaben bzw. Zahlen zu erfassen. Auch in der US 54 50 531 werden Kanten und die zugehörigen Winkel bzw. Lage im Koordinatensystem mit den entsprechenden Gradienten und Gradientenwinkeln detektiert, berechnet und ausgewertet. Weiterhin werden nach der DE 43 08 776 A1 Straßen, also linienhafte Werte und dreidimensionale Objekte bzw. deren Kanten erfasst und ausgewertet. Die Erfindung bezieht sich demgegenüber auf die Analyse und Auswertung von Grauwerten bzw. Grauwertgradienten und den Histogrammen derselben.

Aufgabe der Erfindung ist es, die Auswertung noch präziser zu machen, um z. B. Häuser, Straßen und Fahrzeuge besser zu unterscheiden und auswerten zu können, um z. B. Kollisionsmöglichkeiten von Fahrzeugen anzuzeigen.

Erfindungsgemäß wird dies erreicht durch das Verfahren nach Anspruch 1. Vorteilhafte Weiterbildungen des Verfahrens sind in den Unteransprüchen gekennzeichnet.

Beschreibung der Erfindung

1. Für jede Parzelle eines parzellierten Bildes werden der mittlere Grauwert L_m sowie die minimalen und maximalen Grauwerte L_min bzw. L_max berechnet. Deren Differenz L_max-L_min wird als Spannweite S_p einer Parzelle P bezeichnet (siehe Fig. 1). Anschließend werden eine mittlere Spannweite S_m und deren Standardabweichung für das gesamte Grauwertbild aus den Spannweiten aller Parzellen des parzellierten Bildes berechnet. Dieser Mittelwert S_m wird als Schwellwert zur Definition auffälliger Parzellen benutzt: Eine Parzelle ist auffällig, wenn deren Spannweite S_p größer als S_m ist. Darüber hinaus werden die Abstände von Maxima im Histogramm der Grauwert-Gradienten richtungen zur Definition auffälliger Bereiche herangezogen (siehe Fig. 1). Abstände von ca. 180° bzw. 90° signalisieren parallele Kanten bzw. orthogonale Kanten. Das "Spannweiten-Verfahren" wurde mit dem "Richtungshistogramm-Verfahren" kombiniert für die Detektion künstlicher Objekte (z. B. Fahrzeuge, Häuser, Straßen).
2. In jedem auffälligen Bereich werden Flecke berechnet, in deren Umgebung später nach passenden Kanten gesucht wird (s. Punkt 3). Es werden Flecke für helle Strukturen mit Hilfe eines Schwellwertes L_max - k₁ . ΔL_max bestimmt, wobei L_max der mittlere maximale Grauwert und ΔL_max dessen Standardab weichung darstellen, die sich durch Mittelwertbildung der maximalen Grau werte aller Parzellen ergeben. Über den Faktor k kann noch verfügt werden. Als günstig hat sich ein Wert k₁ = 1 herausgestellt.
Ganz analog zu der eben beschriebenen Vorgehensweise wird ein Schwellwert L_min - k₂ . ΔL_min für die Berechnung von Flecken für dunkle Strukturen bestimmt, wobei L_min der mittlere minimale Grauwert aller Parzellen, ΔL_min dessen Standardabweichung und k₂ eine Konstante darstellt. In vielen Fällen hat sich k₂ = 1 als ein geeigneter Wert erwiesen.
Für den Fall, daß mehrere nahe benachbarte Flecke erzeugt werden, wird mit Hilfe der Methode "Minimal spannende Bäume" eine Ballung zu einem einzigen Fleck vorgenommen.
3. Flecke reichen bei stark strukturierten Objekten im allgemeinen für die Detek tion nicht aus. Deshalb wird in jedem auffälligen Bereich das jeweilige Gradienten-Richtungshistogramm auf das Vorhandensein gradliniger und/oder orthogonaler Vorzugsrichtungen geprüft, indem die Winkelabstände relevanter Maxima des Richtungshistogramms ausgewertet werden. Darüber hinaus werden mit Hilfe des Gradientenbetrages Konturlinien berechnet, deren örtlich linear verlaufende Segmente durch Strecken approximiert werden.
In einem letzten Schritt wird in der Umgebung des Schwerpunktes jedes einzelnen Fleckes nach Strecken gesucht, welche mit vorgegebener Genauigkeit orthogonal zueinander sind, wobei zusätzlich Informationen bezüglich Vorzugsrichtungen aus der Auswertung des Richtungshistogramms herangezogen werden. Falls eine bestimmte Anzahl passender Strecken gefunden wird - z. B. vier orthogonale Strecken - werden diese Strecken zu einem Rechteck verbunden. Mit dieser sogenannten Figur-Hintergrundtrennung ist die Detektionsphase abgeschlossen. Für die anschließende Klassifikation wird die Grauwertverteilung innerhalb des berechneten Recktecks benutzt.

Detektion auffälliger Bildbereiche durch Histogrammauswertung

Bereits in der DE 39 13 620 wurde ein leistungsfähiges Verfahren vorgestellt, welche auf der Auswertung von Maxima oder der Korrelation von Histogrammen der Gradientenrichtung beruhen. Signifikante Maxima des Richtungshistogramms sind Hinweise auf geradlinig verlaufende Konturen innerhalb des gewählten Bildfensters, welche als Teilstrukturen möglicher Ziele in Frage kommen und deshalb als "auffällig" bezeichnet werden.

Ein weiteres wichtiges Merkmal zur Objekt-Hintergrundtrennung ist der Kontrast eines Objektes, welcher durch die Grauwertunterschiede zwischen Objekt und Hintergrund, aber auch zwischen Strukturen innerhalb des Objektes zustande kommt. Ein Maß für den Kontrast ist der Betrag des Grauwertgradienten, für dessen Berechnung die Diffe renz zweier unmittelbar benachbarter Grauwertbereiche gebildet werden muß.

Die Größe dieser Bereiche hängt von der Maskengröße des Gradientenoperators ab, welche im Fall des z. B. verwendeten NAG-(Normierte Ableitung einer Gaußfunktion)- Operators durch die Standardabweichung σ der verwendeten Gaußfunktion bestimmt wird. Neben diesen lokalen, auf die Maskengröße bezogenen Kontrasten besteht ein Bedarf an globalen Kontrastmaßen für beliebige Bildausschnitte bis hin zum gesamten Bild.

Markierung von Bildbereichen mit Hilfe der Spannweite von Grauwerthistogrammen

Als Maß für den globalen Kontrast können gemäß Anspruch 1 beispielsweise Mittelwerte der Gradientenbeträge verwendet werden. Für ein globales Kontrastmaß hat sich jedoch die Differenz der maximalen und minimalen Grauwerte in den einzelnen Parzellen der Gradientenbetrags- oder der Originalbilder als geeigneter erwiesen. Dieses Maß entspricht zum Teil den in der Psychophysik üblichen Kontrastdefinitionen

K1 = (L_max - L_min)/(L_max + L_min) (1)

K2 = (L_max - L_min)/L_m(2)

wobei L_max, L_min und L_m jeweils die maximale, minimale und mittlere Leuchtdichte in dem betrachteten Bildbereich bezeichnen. In Gl. (2) wird statt der mittleren Leuchtdichte L_m sehr häufig die Hintergrundleuchtdichte verwendet in der Annahme, daß bei der Detektion relativ kleiner Testzeichen in einer homogenen Umgebung das Auge auf die Hintergrundleuchtdichte adaptiert. Der Schwellenkontrast für die Sichtbarkeit einer Bildstruktur hängt also nicht nur von der maximalen Leuchtdich tedifferenz ab, sondern auch von der mittleren Leuchtdichte auf die das Auge adap tiert ist (Adaptationsleuchtdichte).

Die Spannweite (L_max - L_min) ist gut geeignet bestimmte Bildbereiche aufgrund hoher Kontraste als auffällig (als Parzelle) zu markieren. Schwierigkeiten treten auf, wenn ein fester Schwellwert vorgegeben wird und alle Kontraste größer als dieser Wert als "hoch" bezeichnet werden. Deshalb wird eine mittlere Spannweite S_m und deren Standardabweichung für das gesamte Grauwertbild aus den Spannweiten aller Parzellen des gerasterten Bildes berechnet.

Die bisher durchgeführten Untersuchungen mit S_m als Schwellwert zur Detektion von Bildbereichen, die aufgrund ihrer überschwelligen Spannweiten auffällig sind, ha ben zu guten Ergebnissen geführt, wie weiter unten gezeigt wird. Lediglich bei Bil dern, in denen große Spannweiten ("Kontraste") in einem größeren Bildbereich (z. B. Siedlungen im IR-Bild) zu einem hohen Mittelwert führen, liegen die Spannweiten in teressierender (kontrastschwacher) Straßen, wie zu erwarten, unterhalb von S_m und werden deshalb mit der in diesem Abschnitt beschriebenen Methode nicht als auffäl lig markiert. In diesem Fall können jedoch die weitgehend kontrastunabhängigen Vorzugsrichtungen herangezogen werden, deren Bestimmung parallel zu der Berechnung von Spannweiten erfolgt.

In einem zweiten Schritt wird eine bessere Lokalisierung von Objekten innerhalb der als auffällig markierten Bildbereiche versucht. Zu diesem Zweck werden für alle Parzellen innerhalb örtlich getrennter Auffälligkeitsbereiche neben der mittleren Spannweite die Mittelwerte des minimalen und des maximalen Grauwertes und deren Standardabweichung bestimmt. Die Idee bei dieser Vorgehensweise ist, mit Hilfe dieser Meßwerte Grauwertschwellen zur Erzeugung von hellen und dunklen Flecken zu definieren, deren Gruppierung unter Berücksichtigung von orthogonalen Vorzugsrichtungen eine Objekt-Hintergrundtrennung ermöglicht. Diese Methode wird nun anhand von Beispielen veranschaulicht.

Experimentelle Ergebnisse

Im folgenden werden Ergebnisse für drei verschiedene Szenarien diskutiert, deren Grauwertverteilungen in den Abb. 2.1, 2.6 und 2.11 wiedergegeben sind. Zur Verdeutlichung der Vorgehensweise ist in Abb. 2.2 ein Raster eingeblendet. Für jede der 30 × 30 Pixel großen Parzellen, die sich zu 50% überlappen (Verschiebung 15 Pixel jeweils in Zeilen- und Spaltenrichtung) werden die Spannweiten der Original- Grauwerte oder der Gradientenbeträge (wählbar) berechnet und eine Analyse des Hi stogramms der Gradientenrichtungen durchgeführt. Die Größe einer Parzelle beein flußt den Wert der Spannweite. Bei dem vorliegenden Maßstab hat sich als Richtwert eine Parzellengröße von 20 × 20 Pixel bewährt. Die 30 × 30 Pixel-Parzellen mit 50% Überlappung in Abb. 2.2 eignen sich jedoch besser zur Veranschaulichung, da der Bildinhalt deutlicher sichtbar bleibt. Die gröbere Ortsauflösung und die geringe Ände rung der mittleren Spannweite gegenüber einem 20 × 20 Pixel-Raster wirken sich hier nur unwesentlich aus.

In Abb. 2.3 ist der Bildinhalt aller Parzellen dargestellt, deren Spannweite größer ist als der Mittelwert S_m = 60. Durch die zusätzliche Berücksichtigung der Bedingung, daß im Richtungshistogramm Maxima mit 180 Grad Abstand dominieren, kann eine weitere Reduktion der Parzellen erreicht werden. In Abb. 2.4 ist erkennbar, daß im wesentlichen die hier interessierenden parallelen Linien, nämlich Straßen, in den Par zellen enthalten sind. Die Bedingung, daß nach der Schwellwertoperation mit S_m als Schwellwert im Richtungshistogramm die Maxima mit 90 Grad Abstand, d. h. ortho gonale Linien, dominieren, führt zu der in Abb. 2.5 dargestellten Hervorhebung von Häusergruppen und Kreuzungen.

Etwas unklarer als im vorangegangenen Beispiel ist die in Abb. 2.6 dargestellte Land schaftsstruktur aufgrund der Abschattung durch Waldränder und die teilweise schlechten Kontraste der Fahrbahnen. Als mittlere Spannweite aller 20 × 20 Pixel- Parzellen mit 50% Überlappung ergibt sich S_m = 61, welche als Schwellwert ge nommen wird. In Abb. 2.7 sind die Mittelpunkte aller überschwelligen Parzellen durch (gelbe) Kreise markiert. Durch die Zusatzbedingung, daß im Richtungshistogramm die Maxima mit 180 Grad Abstand dominieren müssen, ergibt sich eine Reduktion der relevanten Parzellen, wie aus Abb. 2.8 hervorgeht.

Unter Benutzung der in Abb. 2.9 durch kleine Striche symbolisierten Vorzugsrichtun gen, die durch Auswertung des Richtungshistogramms der einzelnen Parzellen be stimmt werden, wird in einem nächsten Auswerteschritt die Kontinuität einer Rich tung innerhalb örtlich zusammenhängender Parzellen geprüft. Für den Fall, daß die dominierenden Richtungen des Grauwertgradienten in mindestens zwei benachbarten Parzellen ähnlich sind (Toleranz ist einstellbar), werden die Parzellen verkettet. Der örtliche Verlauf dieser Verkettung wird durch Strecken approximiert, deren Steigung sich jeweils aus dem Mittelwert der Vorzugsrichtungen ergibt, die den einzelnen Par zellen einer Kette aufgrund der jeweils dominierenden Gradientenrichtung zugeordnet wird (siehe Abb. 2.9). Eine Kette wird aufgrund der örtlichen Nachbarschaft von Par zellen aufgebaut. Ein Abbruchkriterium sorgt dafür, daß beispielsweise ein gekrümm ter Straßenverlauf durch mehrere Strecken mit unterschiedlichen Richtungen ap proximiert wird.

Aufgrund des sehr einfachen Verfahrens zur Verkettung von Parzellen sind Überlappungen von Strecken möglich, wie Abb. 2.10 zeigt, wo die Approximation der Verkettung durch weiße Linien dargestellt ist, die Kreise markieren die Mittelpunkte von diesen Linien (Strecken).

Beschreibung und Ergebnisse von Verfahren für die Objekt-Hintergrundtrennung

Die im folgenden beschriebene Vorgehensweise zur Objekt-Hintergrundtrennung be ruht im wesentlichen auf folgenden Annahmen:

1. Interessierende Objekte sind kontrastreich. Ihre Oberflächen bestehen aus ein zelnen Ebenen. Die Reflexion jeder Ebene führt im Bild zu homogenen Regio nen, so daß sich Objekte als Gruppierung von Regionen mit bestimmten Attri buten (Größe, Form, Grauwert etc.) beschreiben lassen.
2. Falls der Kontrast von Objekten z. B. aufgrund ihrer Farbe, Verschmutzung, Schattenbildung etc. so schlecht ist, daß eine automatische Schwellwertope ration im Grauwertbereich keine Merkmale liefert, sollten jedoch gerade Kan ten zu Vorzugsrichtungen des Grauwertgradienten führen. Die Detektion sol cher Richtungen ist weitgehend kontrastunabhängig. Die Verkettung von Konturpunkten ähnlicher Richtung liefert Strecken für die Formbeschreibung.
3. Die Objekte oder Teile von ihnen lassen sich im Bildbereich in guter Näherung durch Rechtecke beschreiben.

Am Beispiel des in Abb. 2.11 dargestellten Fahrzeuges soll das Verfahren veran schaulicht werden. Unter der Annahme ausreichend großer Kontraste wird die mittle re Spannweite S_m und deren Standardabweichung SD_m für alle 20 × 20 Pixel gro ßen Parzellen (bei 50% Überlappung) des Bildes berechnet. Den Bildinhalt aller Parzellen, deren Spannweite größer ist als S_m + SD_m = 95 + 29 = 134, sieht man in Abb. 2.12. Wegen des niedrigen Kontrastes des vordersten Teils des Führerhauses des LKW mit Anhänger wird eine Ecke durch den oberen Bildrand abgeschnitten. j

Wie dargestellt, ergeben sich aus dem Histogramm der Gradientenrichtungen Vor zugsrichtungen. Für bestimmte auffällige Regionen wird nach Strecken in den Vorzugsrichtungen gesucht. Eine Region wird nur akzeptiert, wenn mindestens vier Strecken gefunden werden, welche als (grobe) Approximation der vier Seiten eines Rechtecks verwendet werden können (Abb. 2.24)

Die gezeigten Beispielen zeigen, daß das erfindungsgemäße Verfahren von der Detektion auffälliger Bereiche im Gesamtbild aufgrund der Kontrast- und Richtungsverteilung bis hin zur Repräsentation der Außenkontur durch Rechtecke eine einfache Methode zur Objekt-Hintergrundtrennung darstellt.

Claims

1. Verfahren zur Bildauswertung von Bildern einer Videokamera oder eines Fernsehbildes durch Analyse und Auswertung der Richtungen von Grauwertgradienten, wobei die Grauwertgradienten des Bildes ggf. normiert werden, und Bildung des Histogramms der Gradientenrichtungen, dadurch gekennzeichnet, daß die minimalen und maximalen Grauwerte L_min bzw. L_max, deren Differenz L_max - L_min als Spannweite S_p, der Mittelwert S_m als Schwellwert zur Definition auffälliger Parzellen, und die Abstände der Maxima im Histogramm der Grauwertgradientenrichtungen gebildet werden.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß in den Parzellen Flecke für helle Strukturen mit Hilfe eines Schwellwertes L_max - k₁ . ΔL_max und ein Schwellwert L_min - k₂ . ΔL_min für die Berechnung von Flecken für dunkle Strukturen bestimmt werden.

3. Verfahren nach einem der Ansprüche 1-2, dadurch gekennzeichnet, daß für den Fall, daß mehrere nahe benachbarte Flecke gleicher Intensität erzeugt werden, mit Hilfe der Methode "Minimal spannende Bäume" eine Ballung zu einem einzigen Fleck vorgenommen wird.

4. Verfahren zur Bildauswertung von Bildern einer Videokamera oder eines Fernsehbildes durch Analyse und Auswertung der Richtungen von Grauwertgradienten, wobei die Grauwertgradienten des Bildes ggf. normiert werden, und Bildung des Histogramms der Gradientenrichtungen nach Anspruch 2, dadurch gekennzeichnet, daß in jedem auffälligen Bereich das jeweilige Gradienten- Richtungshistogramm auf das Vorhandensein gradliniger und/oder orthogonaler Vorzugsrichtungen geprüft wird, indem die Winkelabstände relevanter Maxima des Richtungshistogramms ausgewertet werden.

5. Verfahren nach Anspruch 4, dadurch gekennzeichnet, daß im Fall von vier orthogonalen Strecken in einem Fleck diese zu Rechtecken verbunden werden.

6. Verfahren nach Anspruch 5, dadurch gekennzeichnet, daß nach Bildung der Rechtecke die Grauwertverteilung innerhalb derselben zur Klassifikation verwendet werden.