Bei der Verarbeitung digitaler Bildfolgen von Straßenver¬ kehrsszenen für Zwecke der Detektion, Verfolgung und Klas¬ sifikation von Fahrzeugen wirkt sich oft störend aus, daß die Fahrzeuge im Falle direkter Sonneneinstrahlung einen Schatten auf die Fahrbahn werfen, welcher nicht auf einfa¬ che Weise vom Fahrzeug getrennt werden kann. Hierdurch wird eine Klassifikation von Fahrzeugen nach ihren geometrischen Abmessungen, insbesondere nach ihrer Breite häufig er- schwert, wenn nicht unmöglich gemacht.

Bisherige Ansätze zur Lösung dieses Problems greifen auf Fahrzeugmodelle zurück (G.D. Sullivan, K.D. Baker: Model¬ based isio :using cues to select hypotheses. SPIE Vol. 654 Automatic Optical Inspection (1986), pp. 272-277), welche mit dem Bild zur Übereinstimmung gebracht werden (matching) , wodurch eine Abspaltung des Schattens nicht er¬ forderlich ist. Dieser Ansatz hat jedoch den Nachteil, daß er sehr rechenintensiv ist und daß bei dem jetzigen Ent- wicklungsstand der Bildverarbeitungshardware eine Realisie¬ rung solcher Verfahren in Echtzeit innerhalb eines sinnvol¬ len Kostenrahmens nicht möglich erscheint.

Der vorliegenden Erfindung liegt daher die Aufgabe zugrun- de, ein Verfahren zur Detektion und .Abspaltung des Schat¬ tens sich bewegender Objekte in einer digitalen Bildsequenz anzugeben, welches für die Anwendung in den oben erwähnten Bildverarbeitungsverfahren geeignet ist, und welches sich in Echtzeit auf der Grundlage kostengünstiger Hardware Mo- dule realisieren läßt. Diese Aufgabe wird erfindungsgemäß durch ein Verfahren zur Detektion und Abspaltung des Schat-

tens sich bewegender Objekte in einer digitalen Bildsequenz nach Anspruch 1 gelöst.

Bei diesem Verfahren wird zunächst aus einer Bildsequenz eine Sequenz von Hintergrundbildern ermittelt, welche nur den unbewegten Bildhintergrund der Bildsequenz, nicht aber die bewegten Objekte enthält. Daran anschließend werden Ob¬ jektkanten aus der Bildsequenz extrahiert, indem zu jedem Bild der Bildsequenz und zu dem jeweils entsprechenden Hin- tergrundbild der Hintergrundbildsequenz jeweils ein Kanten¬ grauwertbild ermittelt wird. Durch vertikale bzw. horizon¬ tale Projektion dieser Kantengrauwertbilder werden jeweils entsprechende vertikale bzw. horizontale Kantenhistogra me zu den Kantengrauwertbildern ermittelt. Kanten, die nicht zu BewegtObjekten oder Schatten von BewegtObjekten gehören, werden eliminiert, indem die Kantenhistogramme eines Hin¬ tergrundbildes von den entsprechenden Kantenhistogrammen des zum gleichen Zeitpunkt gehörenden Bildes der Bildse¬ quenz substrahiert werden, und indem die auf diese Weise gebildeten Differenzkantenhistogramme einer SchwelIwertent- Scheidung unterworfen werden, wodurch diejenigen Kanten eliminiert werden, welche nicht den eigentlichen Bewegtob¬ jekten, sondern einem Schatten eines sich bewegenden Objek¬ tes entsprechen.

Zur Durchführung dieses Verfahrens ist ein wesentlich ge¬ ringerer Rechenaufwand erforderlich, als zum Matching von Objektmodellen auf Bildbereiche.

Bei einer bevorzugten Ausführungsform der Erfindung werden die Kantengrauwertbilder vor der Ermittelung der Kantenhi¬ stogramme binarisiert. Durch diese Maßnahme kann der Re¬ chenaufwand bei der Verarbeitung der Kantenhistogramme wei¬ ter reduziert werden.

Eine weitere Verringerung des Rechenaufwandes wird dadurch möglich, daß vor der Durchführung der Schritte b) bis e)

des durch Anspruch 1 charakterisierten Verfahrens diejeni¬ gen Bildbereiche ermittelt werden, welche bewegten Objekten - ggf. einschließlich ihres Schattens - entsprechen, und bei dem die Schritte b) bis e) nur auf diese Bildbereiche angewendet werden.

Bei einer weiteren bevorzugten Ausführungsform des erfin¬ dungsgemäßen Verfahrens werden Kantenhistogramme, die zu ein und demselben Bewegtobjekt gehören, zu einer zeitlichen Folge von Kantenhistogrammen zusammengefaßt und die Elimi¬ nation von Schattenkanten wird durch eine Identifikation einander entsprechender Kanten verbessert.

Bei einer weiteren bevorzugten Ausführungsform des Verfah- rens wird die Elimination der Schattenkanten weiter verbes¬ sert, indem Vorwissen über die Seitenlage der Schattenkan¬ ten in bezug auf die Objektkanten verwendet wird. Dieses Vorwissen kann bevorzugt dadurch erlernt und fortlaufend überprüft werden, daß die Seitenlage der Schattenkanten in adaptiver Weise aus der Bildfolge ermittelt wird. Durch diese Maßnahme läßt sich die Praxistauglichkeit und Robust- heit des erfindungsgemäßen Verfahrens weiter verbessern.

Figur 1 zeigt in schematischer Weise ein Kantengrauwertbild eines Bildes der Bildsequenz mit den zughörigen vertikalen bzw. horizontalen Kantenhistogrammen.

Figur 2 zeigt ein zu einem Hintergrundbild gehörendes Kan¬ tengrauwertbild mit den dazu gehörenden horizontalen und vertikalen Kantenhistogrammen.

Figur 3 zeigt schematisch den Zusammenhang zwischen den Kantenhistogrammen des Bildes der Bildfolge und des Hinter¬ grundbildes mit dem Differenzkantenhistogramm und den durch Schwellwertentscheidung ermittelten Kantenhistogramm am Beispiel vertikaler Kantenhistogramme.

Figur 4 zeigt ein Beispiel eines Bildes der Bildsequenz.

Figur 5 zeigt ein Beispiel eines Bewegtobjektbildes, indem die Bewegtobjekte als schwarze Gebiete sichtbar sind.

Figur 6 zeigt die Markierung bewegter Objekte einschließlich ihres Schattens durch einschließende Rechtecke innerhalb eines Bildes der Bildsequenz.

Figur 7 zeigt ein Hintergrundbild zu der betrachteten Bild¬ sequenz.

Figur 8 zeigt ein Bild mit der Zuordnung der vertikalen Hi¬ stogramme zu den Bewegtobjekten.

Figur 9 zeigt die Markierung bewegter Objekte unter Aus¬ schluß ihres Schattens durch einschließende Rechtecke in einem Bild der Bildsequenz.

Im folgenden wird die Erfindung durch bevorzugte Ausfüh- rungsbeispiele und mit Hilfe der Figuren näher erläutert.

In der Figur 4 ist eine typische Straßenverkehrsszene zu einem bestimmten Zeitpunkt dargestellt, wie sie von einer Kamera, welche (z. B. auf einer Brücke oberhalb der Fahr¬ bahn) aufgebaut ist, aufgenommen wird. Die bewegten Objekte werfen aufgrund des seitlich in diesem Fall von links ein¬ fallenden Sonnenlichtes einen deutlich erkennbaren Schatten zu ihrer rechten Seite auf die Fahrbahn. Daß dieser Schat- ten sich störend auf die Ermittlung der geometrischen Ab¬ messungen, insbesondere der Breite der bewegten Objekte auswirkt, zeigt besonders ein Blick auf Figur 5, in der die bewegten Objekte einschließlich ihrer Schatten als schwarze Markierungen in der Bildebene dargestellt sind. Figur 6 zeigt die sich anhand dieser Verhältnisse ergebenden ein¬ schließenden Rechtecke der Bewegtobjekte einschließlich ih-

rer Schatten, welche zu erheblichen Überschätzungen der Ab¬ messungen der Bewegtobjekte führen.

Aus verschiedenen Veröffentlichungen (W.Feiten et.al.: A video-based System for extracting traffic flow Parameters, Proc. 13th DAGM 1991, Munich, pp. 507-514; K.P. Karmann, A.v. Brandt: Moving object segmentation based on adaptive reference images, Proc. of EUSIPCO 1990, Barcelona) sind Verfahren zur Ermittelung von Hintergrundbildsequenzen zu Bildsequenzen bekannt. Diese Hintergrundbildsequenzen haben die Eigenschaft, daß bewegte Objekte, welche in der ur¬ sprünglichen Bildsequenz enthalten sind, in dieser Hinter¬ grundbildsequenz nicht enthalten sind.

Figur 7 zeigt ein Hintergrundbild zu der durch Figur 4 repräsentierten Bildsequenz. Ein solches Hintergrundbild wird in adaptiver Weise aus der ursprünglichen Bildsequenz berechnet, wodurch alle langsam veränderlichen Änderungen der ursprünglichen Bildsequenz auch in der Hintergrund- bildsequenz enthalten sind. Die Berechnung derartiger

Hintergrundbildsequenzen ist aus der Literatur bekannt und stellt somit kein besonderes technisches Problem im Zu¬ sammenhang mit der vorliegenden Erfindung dar. Wie aus den Figuren 4, 5 und 6 ersichtlich, werden jedoch nicht nur die sich bewegenden Objekte, sondern auch, falls vorhanden, der zu diesen Objekten gehörige Schattenwurf, in diesem Fall auf die Fahrbahn, aus der Hintergrundbildsequenz eliminiert. Aus diesem Grunde sind auch diese Schatten und nicht nur die eigentlichen Bewegtobjekte in den durch Differenzbildung aus der Bildsequenz und der Hin- tegrundbildsequenz erzeugten Objektbildern enthalten. Um diese Schatten von den eigentlichen Bewegtobjekten zu trennen, wird nun erfindungsgemäß zu jedem Bild der Bildsequenz und auch zu jedem entsprechenden Bild der Hintergrundbildsequenz ein Kantengrauwertbild unter

Verwendung bekannter Methoden, die in der Literatur be¬ schrieben sind, berechnet. Eine Reihe von klassischen Ver-

fahren zur Extraktion von Kanten aus digitalen Bildsequen¬ zen wird in dem Buch von Y.Shirai, Three-Dimensional Compu¬ ter vision, Springer Verlag, 1987, besonders auf den Seiten 32 ff. beschrieben. Die Berechnung von Kan engrauwertbil- dern stellt somit im Zusammenhang mit der vorliegenden Er¬ findung kein technisches Problem dar.

Figur 1 zeigt den typischen Verlauf der Kanten in einem Bild der Bildsequenz zu einer Straßenverkehrsszene. Die Kanten 11, 12 und 13 markieren die Fahrbahnränder bzw.

Fahrbahnmitte, die Kanten 14 bis 17 markieren ein auf der linken Fahrbahn sich bewegendes Objekt und die Kanten 18, 19 und 110 markieren die Ränder des zu dem Objekt gehören¬ den Schattenwurfs. Unterhalb bzw. links neben dem schema- tisch dargestellten Kantengrauwertbild sind die zugehörigen horizontalen (HH1) bzw. vertikalen (HV1) Kantenhistogramme dargestellt. Derartige Kantenhistogramme werden mit Stan¬ dardverfahren aus dem Kantengrauwertbild ermittelt, die im Bereich der Bildverarbeitung jedem Fachmann ohne weiteres geläufig sind und deshalb im Zusammenhang mit der vorlie¬ genden Erfindung keiner weiteren Darstellung bedürfen. Diese Kantenhistogramme werden durch vertikale bzw. hori¬ zontale Projektion des Kantengrauwertbildes, d. h. durch Aufsummation der Grauwerte längs der entsprechenden Zeilen und Spalten des digitalen Bildes ermittelt.

Figur 2 zeigt in schematischer Weise das Kantengrauwertbild zum entsprechenden Hintergrundbild, in dem lediglich die Kanten der Fahrbahnrandmarkierungen und der Fahrbahnmitte zu sehen sind, nicht aber die Kanten des Bewegtobjekts und seines Schattens. Dementsprechend enthalten die zugehörigen Kantenhistogramme weniger bzw. gar keine Linien.

Figur 3 zeigt nun am Beispiel vertikaler Histogramme, wie die in Figur 1 bzw. 2 dargestellten Histogramme voneinander subtrahiert und einer Schwellwertentscheidung unterworfen werden, wodurch die in Figur 3 dargestellten Histogramme

HV3 bzw. HV4 gebildet werden. Das Histogramm HV3 enthält nur noch die Kanten des Bewegtobjektε und seines Schattens und das Histogramm HV4 enthält, nachdem die Schattenkante durch SchwellwertentScheidung beseitigt wurde, ausschließ- lieh die zum Bewegtobjekt gehörigen Kanten.

Nach dieser Elimination der Schattenkanten lassen sich die eigentlichen Bewegtobjektkanten in den Kantengrauwertbil¬ dern und auch in den ursprünglichen Bildern der Bildsequenz sehr leicht auffinden, wodurch eine korrekte Ermittlung der geometrischen Abmessungen der Bewegtobjekte sehr einfach möglich ist.

Bei einem bevorzugten Ausführungsbeispiel des erfindungsge- mäßen Verfahrens werden die Kantengrauwertbilder vor der

Ermittelung der Kantenhistogramme mit Standardverfahren der Bildverarbeitung binarisiert. Es ist einleuchtend, daß auf diese Weise die Menge der zu verarbeitenden Daten entschei¬ dend reduziert werden kann und daß die Berechnung der Hi- stogramme aus den Bildern hierdurch vereinfacht wird. Ein weiterer Vorteil einer Binarisierung ist in einer möglichen Reduktion des Einflusses von statistischen Rauschprozessen zu sehen, welche möglicherweise in dem ursprünglichen Bild¬ material enthalten sein können.

Bei einem weiteren Ausführungsbeispiel der Erfindung wird die Durchführung der Schritte b) bis e) des Anspruchs 1 auf diejenigen Bildbereiche beschränkt, welche bewegten Objek¬ ten - ggf. einschließlich ihres Schattens - entsprechen. Solche Bildbereiche sind in Figur 5 als schwarze Bereiche markiert. In einer Variante des erfindungsgemäßen Verfah¬ rens können anstelle der in Figur 5 schwarz markierten Bildbereiche auch die einhüllenden Rechtecke dieser Bildbe¬ reiche verwendet werden.

In einer bevorzugten Ausführungsform des erfindungsgemäßen Verfahrens werden Schatten- und oder Objektkanten zeitlich

verfolgt. Hierduch ist eine Verbesserung der Kantenklassi¬ fikation bei gleichzeitiger Reduktion des Rechenaufwandes möglich. Dazu werden zeitliche Folgen von horizontalen bzw. vertikalen Kantenhistogra en gebildet, in denen entspre- chende Kanten identifiziert werden und ihre Bewegung im Laufe der Zeit verfolgt wird. Für diesen Zweck können ver¬ schiedenartige Verfahren zur Verfolgung von Objekten in zeitlichen Bildfolgen eingesetzt werden, wie sie aus der Literatur bekannt sind (z.B. W. Feiten et. al. , 1991).

Um die Leistungsfähigkeit des Verfahrens weiter zu verbes¬ sern und den Rechenaufwand so weit wie möglich zu reduzie¬ ren, verwendet ein weiteres bevorzugtes Ausführungsbeispiel des erfindungsgemäßen Verfahrens Vorwissen über das Auftre- ten und die Seitenlage von Schattenwürfen an Objektkanten. Dazu wird eine hierarchische Systemarchitektur mit typi¬ scherweise drei Hierarchieebenen verwendet. Die höchste Verarbeitungsebene verwendet Wissen über das Kalenderdatum und die Uhrzeit um die Möglichkeit des Auftretens von Schattenwürfen zu beurteilen. Wenn also aufgrund der Jah¬ res- bzw. Tageszeit das Auftreten von Schattenwürfen ausge¬ schlossen ist, verzichtet das Verfahren auf eine entspre¬ chende Analyse. Andernfalls analysiert eine darunterliegen¬ de Verarbeitungsebene die Bewegtobjekte hinsichtlich typi- scher Attribute, wie z.B. abnorme Werte für die Objekthöhe oder Objektbreite. Dabei wird die erwartete Schattenrich¬ tung und Seitenlage sowie die wahrscheinliche Schattenform zu einer Verbesserung der Suche nach Schattenkanten in der Nähe eines detektierten Objekts herangezogen.

Eine dritte, darunterliegende Verarbeitungsebene sorgt für die Verarbeitung von Vorwissen, welches durch die Analyse zeitlich vorhergehender Bilder, also in adaptiver Weise, erworben wurde. Jeder Schatten, welcher in einem der vor- hergehenden Bilder detektiert wurde, hat mit großer Wahr¬ scheinlichkeit einen Nachfolger in einem der folgenden Bil¬ der. Durch eine entsprechende zeitliche Verfolgung von

Schattenkanten kann die Leistungsfähigkeit des Verfahrens beträchtlich gesteigert werden.

Bei der Verfolgung der Objekte durch die zeitliche Folge digitaler Bilder werden deren Positionen für zukünftige Zeitpunkte vorausberechnet. Dabei werden u.a. vorzugsweise die folgenden Objekteigenschaften protokolliert:

- momentane Position - vorhergesagte Position in einem zukünftigen Bild

- momentane Geschwindigkeit

- vorhergesagte Geschwindigkeit in einem zukünftigen Bild

- Objektbreite und

- eine Plausibilität.

Zur Verfolgung geometrischer Objekteigenschaften werden da¬ bei bevorzugt Weltkoordinaten (im Gegensatz zu Bildkoordi¬ naten) verwendet. Die Objektabmessungen werden bevorzugt mit Hilfe von umschreibenden Rechtecken protokolliert. Zur zeitlichen Verfolgung aller Attribute und Parameter werden bevorzugt Kaiman-Filter eingesetzt.

Eine korrekte Separation der Schatten von den entsprechen¬ den Objekten erfordert die Verwendung von Wissen über die Schattenrichtung, welches sich aus dem Kalenderdatum, der

Uhrzeit und aus geometrischen Einflußgrößen der Straßenver¬ kehrsszene ergibt. Ist beispielsweise bekannt, daß die Schatten auf den rechten Seiten der Bewegtobjekte liegen, beginnt die Kantenextraktion auf dieser Seite eines Seg- ments und erzeugt die entsprechenden Kantenhistogramme.

Nachdem die Schatten von den Objekten separiert wurden, kann die Objektgeometrie (z.B. Breite, Höhe) zutreffend er¬ mittelt und eine Objektbeschreibung erstellt werden. Aus der ermittelten Schattenrichtung können die geometrischen Verhältnisse der Straßenverkehrsszene ermittelt und zur Verbesserung nachfolgender Verarbeitungsschritte verwendet

werden. Schließlich können verschiedene Parameter des Ver¬ fahrens und der bildgebenden Hardware unter Berücksichti¬ gung der Tatsache, daß die Fahrzeuge starre Objekte sind, optimiert und eingestellt werden.

In dieser Beschreibung wurden folgende Veröffentlichungen zitiert:

G.D. Sullivan, K.D. Baker: Model-based vision:using cues to select hypotheses. SPIE Vol. 654 Automatic Optical Inspection (1986), pp. 272-277

W.Feiten et.al.: A video-based System for extracting traffic flow Parameters, Proc. 13th DAGM 1991, Munich, pp. 507-514

K.P. Karmann, A.v. Brandt: Moving object segmentation based on adaptive reference images, Proc. of EUSIPCO 1990, Barcelona

Y.Shirai, Three-Dimensional Computer vision, Springer Verlag, 1987

Der vorliegenden Beschreibung folgen Listings von Computer- Programmen bzw. Programm-Modulen, welche zu einer Durchfüh¬ rung der vorstehend beschriebenen Verfahren auf einer elek¬ tronischen Rechenanlage benutzt werden können.

/

/*

*/ /* shadow analysis

*/

/*

*/

/* file p_clust .c */

/* translate intermetrics c Compiler

*/

/* author Michael Kilger

*/ /* version 1.0, 14/07/92

*/

/*

*/

/* includes * , +/ * + *** + + + + + + + * + + ι _ririr ι _c + + * _i .* + _{iri, i} . _i . _i .* + + _i .+**i _r *i _riri .* _ir ι _, * + ** + + * + * + <,*

*****************/

#include <stddef.h> #include <stdlib.h> #inelüde "common.h" #include "macrodsp.h"

/ _{*****************************}

/* definess */

#define ANALYSESTART 100000.OF /* Start of the clusteranalysis in ANALYSESTART mm form the camera */ #define ANALYSESOUTH 50000.0F

#define MAXWIDTH 2500.0F /* maximum aeeepted width of a vehicle */

#define XSHADET 7 /* aecount of pixels in x direction for rejeet shadowanalysis */

#define YΞHADET 7 /* account of pixels in y direction for reject shadowanalysis

*/ #define SHADELAY 30 /* account of cycles, which the shadowanalysis continues, if no shadow is detected */

#define MINWIDTH 3

#define TSTSHADELAY 20

#define CNTSTH 20

#define SHAPROP 60.0F #define SOUTHPROP 60.0F extern void toworld ( void ) ; extern int Hconvolve( int, int); extern int Vconvolve( int, int); extern int Hcondispl( int, int);

/* extern variables */ ********♦******************************

extern long OutBuf[]; extern long SegLinf]; extern long WorkBuf[] ; extern long BgBuf[]; extern struct segm SegList[]; extern long EdgThr; extern long EThr2; extern long Edofs; extern int segs; extern long sha,lscycl; extern long West,East,North,South; extern int debug;

/* function prototypes

*/ ***★*********************************

int Shadow( void ) ; int Cluster( void ); int shadowanalysis( void ); int isshadow( int *, int *); int occlusionanalyεis ( int ) ;

if (sha){ toworldO; if (tstsouth) { for (i=l; i<=segs; i++) { if (SegList [i] .next == NULL) { if (SegList [i] .Y < ANALYSESOUTH &&

SegList [i] .dp != 255 && SegList [i] .rp != 255 && SegList [i] .lp != 0) { checked++; if(Hcondispl (SOUTH, i) ) s++; }

} } if (s){ south++; } if (checked) { tstcntsth-f-i-:

} if (tstcntsth > CNTSTH) { if ( (float)south/ (float) CNTSTH*!00. OF >

ΞOUTHPROP) {

South = 1;

} tstsouth = 0;

} if (debug) { send32bit (tstsouth) ; send32bit (checked) ; send32bit (tstcntsth) send32bit (south) ; send32bit (s) ;

}

if((tst = shadowanalysis () ) == -1) { return(-1) ;

}

eise if (tst == 0) { lscycl = 0; return(0) ;

} else{ lscycl++; if (lscycl > SHADELAY) { sha = West = East = South = 0; tstsouth = 1; tstcntsth = south = 0;

} } } else{ if(debug) { send32bit(-3) send32bit (-3) send32bit (-3) send32bit (-3) send32bit (-3)

} } return(tst) }

/******************************************************** ** **************** /

/**********************************************************

/

/* send32bit (tstsha) ; */ /* send32bit (tstcnt) ; */ **********************************************************

/ clanalyse = shanalyse = w = e = 0 ; for (i=l; i<=segs; i++) { if (SegList [i] .next == NULL) { if (SegList [i] .Y < ANALYSESTART && SegList [i] .Width > MAXWIDTH) { clanalyse=l ; if( (isha) && (! stsha) ) { shanalyse = 1;

} else{ shanalyse = 0;

} break;

} } } if (tstsha) { clanalyse = 1; if (isshadow(&w, &e) ) { tstcnt++; if (w > e) west++; eise if (e > w) east++; if (tstcnt > TSTSHADELAY) { if (west > east) { if ( ( (float)west / (float)TSTSHADELAY)*100.0F > SHAPROP) { sha = 1; West = 1; }

} eise if (east > west) { if ( ( (float) east / (float)TSTSHADELAY)

east = 0; tstsha = 0;

}

5 if(shanalyse) { if (tstsha. = isshadow(&w, &e) ) { clanalyse = 1; tstcnt = 1; if (w > e) { 10 west = 1; east = 0;

} eise if (e > w) { east = 1; 15 west = 0;

} else{ east = 0; west = 0; 20 }

} } if (debug) { 25 send32bit (tstsha) ; send32bit (tstcnt) ; send32bit (w) ; send32bit (e) ;

30 send32bit (west) ; send32bit (east) ; }

35 return(clanalyse) ;

} **********************************************************

****************

40 /* isshadowO

*/

/*

*/

/* input : addresses of the west and east varibles in 45 Cluster() */

/* output: update of the east and west variables

*/

/* 1 shadow detected

*/ 50 /* 0 no shadow detected

*/

/*

*/ ********************************************************** r- ~ ****************

int isshadow( int *ws, int *es )

{ int i,we, ea; we = ea = 0; for (i=l; i<=segs; i++) { if (SegList [i] .next == NULL) { if (SegList [i] .Y < ANALYSESTART) { if (Vconvolve(WEST, i) ) we++; if (Vconvolve(EAST,i) ) ea++; } } } *ws = we; *es = ea; if (we I I ea) return(1) ; return(0) ;

} **********************************************************

**************** int shadowanalysis ( void )

{ int i; int shadetected, checked; shadetected = checked = 0; for (i=l; i<=segs; i++) { if (SegList [i] .next == NULL) { if (SegList [i] .Y < ANALYSESTART) { checked = 1; if (West) if (Vconvolve(WEST, i) ) shadetected++; if (East) if (Vconvolve (EAST, i) ) shadetected++; if (South) if(Hcondispl (SOUTH, i) && .West && !East) shadetected++;

} } } if (checked) return(shadetected) ; eise retur (-1) ;

} ********************************************************** ******************/

EOF

********************************************************* * ς **********-* ^■ ****** /

/* */ /* low-level routines */

10 /*

*/ /* file d_llevel.c */ /* translate intermetrics c Compiler

15 */

/* author Michael Kilger

*/

/* version 1.0, 04/08/92

*/

20 /*

*/ **********************************************************

***************** / oς /********************************************************** ***************** /

/* includes

*/ **********************************************************

^■ 3 Q *****************

#include <stddef.h> #include <stdlib.h> #include "common.h" 5 «include "macrodsp.h"

********************************************************* * ***************** 0 /* defines

*/ **********************************************************

***************** 5 extern void toworld ( void ) int Hcondispl ( int, int) ; ********************************************************** 0 ****************

/* extern variables

*/ /*********************************+************************

**************** 5

extern long OutBuf[] ; extern long SegLinϊϊ; extern long WorkBuf[] ; extern long BgBuf[] ; extern struct seg SegList[]; extern long EdgThr; extern long EThr2; extern long Edofs; extern int segε; extern long sha,lscycl; extern long West,East,North,South; extern int debug;

/******************************************************** **

***************

/* function prototypes */ / _{******************************************************* ***}

*************** / int Hconvolve( int , int int Vconvolve( int , int

********************************************************* * ****************** int Hconvolve( int dir, int nr ) { int lp,rp,dp,up; /* coord. of the segment */ int xwidth,ywidth; /* width and height of the s. */ int x,y; /* loop counter */ int tl,t2; /* help variables */ long *ConvBufl, *ConvBuf2, *ShowBuf; /* convolve buffers */ int d; /* direction */ long edgsum,edgsuml,edgsum2; /* help variables */ int Edg; /* edge threshold */ int edge=l;

if (SegList[nr] .lp > 0) lp = (int)SegList[nr] .lp; /* calculate */ eise lp = 1;

/* the start */ /* line and */

if (SegList [nr] .rp < X_INT) (int) SegList [nr] .rp; /* pixel eise if (SegList [nr] .up > 0) (int) SegList [nr] .up; eise if (SegList [nr] .dp < Y_INT) (int)SegList [nr] .dp; eise xwidth = rp-lp+1; and height of the segment */ ywidth = dp-up+1; pixels */

Edg = xwidth/IOL + Edofs; function to determine the first edge 7 if (dir == SOUTH) { the two convolve buffers */

ConvBufl = WorkBuf + lp + (current image and back- */

ConvBuf2 = BgBuf +lp + dp* ground image) for each */

ShowBuf = OutBuf + lp + dp* direction (west and east) */ d = -1;

} eise if ( dir == NORTH) {

ConvBufl = WorkBuf + lp + up*X_INT;

ConvBuf2 = BgBuf + lp +up*X_INT;

ShowBuf = OutBuf + lp + up*X_INT; d = 1; } for ( y=0; abs (y)<=ywidth; y+=d) { edgsuml = edgsum2 = 0; for (x=0; x<=xwidth; x++) { tl = (1) * * (ConvBufl + x-1 + (y-l)*X_INT) + /* convolve */

(2) * * (ConvBufl + x + (y-l)*X_INT) +

(1) * * (ConvBufl + x+1 + (y-l)*X_INT) +

(0) * * (ConvBufl + x-1 + y*X_INT) +

(0) * * (ConvBufl + x + y*X_INT) + (0) * * (ConvBufl + x+1 + y*X_INT) + (-1) * * (ConvBufl + x-1 + (y+l)*X_INT)

(-2) * * (ConvBufl + x + (y+l)*X_INT) + (-1) * ConvBufl + x+1 + (y+1) *X_INT) ;

t2 = (1) * *(ConvBuf2 + x-1 + (y-l)*X_INT)

(y-l)*X_INT) + + (y-l)*X_INT) + + y*X_INT) + y*X_INT) + + y*X_INT) + + (y+l)*X_INT)

(y+l)*X_INT) + + (y+1) *X_INT) ;

edgsu l += tl; /* add the edge greyvalues */ edgsum2 += t2 ;

} edgsu = edgsuml - edgsum2 ; subtract the edge greyvalues of the background from those of the current image */ if ( (edgsum) > Edg) { /* if the resultmg edge grey- value is greater than a threshold lt is assumed that lt

IS a significant edge of the vehicle */ if (edge) { if (abs(y)<YSHADET) return(0) ; if (dir == SOUTH) {

SegList [nr] .dp = dp + y ■+- 1 SegList [nr] .norm = 4;

} eise if (dir == NORTH) {

SegList [nr] .up = up + y;

SegList [nr] .norm = 3;

} return(1) ;

} else{ edge = 1;

} else{ edge = 0;

return(0) ;

/******************************************************** ** *»****************

long edgsum, edgsuml, edgsum2; int Edg; int edge = 0; if (SegList [nr] .lp > 0) lp = (int) SegList [nr] .lp; eise lp = 1; if (SegList [nr] .rp < X_INT) rp = (int) SegList [nr] .rp; eise rp = X_INT-1; if (SegList [nr] .up > 0) up = (int) SegList [nr] .up; eise up = 1; if (SegList [nr] .dp < Y_INT) dp = (int) SegList [nr] .dp; eise dp = Y_INT-1; xwidth = rp-lp+1; ywidth = dp-up+1;

Edg = ywidth/EThr2 + Edofs; if (dir == EAST) {

ConvBufl = WorkBuf + lp + up*X_INT;

ConvBuf2 = BgBuf + lp + up*X_INT; d = 1; } eise if( dir == WEST) {

ConvBufl = WorkBuf + rp + up*X_INT;

ConvBuf2 = BgBuf + rp + up*X_INT; d = -1; }

for ( x=0; abs(x)<=xwidth-MINWIDTH; x+=d) { edgsuml = edgsum2 = 0; for (y=0; y<=ywidth; y++) { tl = (1) * * (ConvBufl + x-1 + (y-l)*X_INT) +

(0) * * (ConvBufl + x + (y-l)*X_INT) + (-1) * * (ConvBufl + x+1 + (y-l)*X_INT)

+

(2) * * (ConvBufl + x-1 + y*X_INT) + (0) * * (ConvBufl + x + y*X_INT) +

(-2) * * (ConvBufl + x+1 + y*X_INT) +

(1) * * (ConvBufl + x-1 + (y+l)*X_INT) + (0) * * (ConvBufl + x + (y+l)*X_INT) + (-1) * * (ConvBufl + x+1 + (y+1) *X_INT) ; t2 = (1) * *(ConvBuf2 + x-1 + (y-l)*X_INT)

+

(0) * *(ConvBuf2 + x + (y-l)*X_INT) + (-1) * *(ConvBuf2 + x+1 + (y- 1)*X_INT) + (2) * *(ConvBuf2 + x-1 + y*X_INT) +

(0) * *(ConvBuf2 + x + y*X_INT) -<- (-2) * *(ConvBuf2 + χ+1 + y*X_INT) +

(1) * *(ConvBuf2 + x-1 + (y+l)*X_INT) + (0) * *(ConvBuf2 + x + (y+l)*X_INT) +

(-1) * *(ConvBuf2 + x+1 + (y+l)*X_INT) ; if (abs(tl) > EdgThr) tl = 1 eise tl = 0 if (abs(t2) > EdgThr) t2 = 1 eise t2 = 0 edgsuml += tl; edgsum2 += t2;

edgsum = edgsuml - edgsum2; if (edgsum > Edg) { if (edge) { if (abs(x)<XSHADET) { return(0) ; } if (dir == EAST) {

SegList [nr] .lp = lp + x - 1; } eise if (dir == WEST) {

SegList [nr] .rp = rp + x + 1; } return(1) ;

} else{ edge = 1; }

}

eise edge=0 ;

}

SegList [nr] .norm = 5; return(0) ;

}

************** ₊ ******************************************* ****************** int Hcondispl ( int dir, int nr {

xwidth = SegList [nr] .rp-SegList [nr] .lp+1; ywidth = SegList [nr] .dp-SegList [nr] .up+1;

Edg = xwidth/10 + Edofs; if (dir == SOUTH) {

ConvBufl = WorkBuf + SegList [nr] .lp + SegList [nr] .dp*X_INT;

ConvBuf2 = BgBuf + SegList [nr] .lp + SegList [nr] .dp*X_INT;

ShowBuf = OutBuf + SegLis [nr] .lp + SegList [nr] .up*X_INT; d = -1;

} eise if( dir == NORTH) {

ConvBufl = WorkBuf + SegList [nr] .lp + SegList [nr] .up*X_INT; ConvBuf2 = BgBuf + SegList [nr] .lp

+SegList[nr] .up*X_INT;

ShowBuf = OutBuf + SegList [nr] .lp + SegList [nr] .up*X_INT; d = 1; }

for ( y=0; abs (y)<=ywidth; y+=d) { edgsuml = edgsum2 = 0; for (x=0; x<=xwidth; x++) { tl = (1) * * (ConvBufl + x-1 + (y-l)*X_INT) +

(2) * * (ConvBufl + x + (y-l)*X_INT) + (1) * * (ConvBufl + x+1 + (y-l)*X_INT) + (0) * * (ConvBufl + x-1 + y*X_INT) + (0) * * (ConvBufl + x + y*X_INT) + (0) * * (ConvBufl + x+1 + y*X_INT) +

(-1) * * (ConvBufl + x-1 + (y+l)*X_INT) + (-2) * * (ConvBufl + x + (y+l)*X_INT) + (-1) * * (ConvBufl + x+1 + (y+l)*X_INT) ; sobbg = (1) * *(ConvBuf2 + x-1 + (y-1) *X_INT) +

(2) * *(ConvBuf2 + x + (y-l)*X_INT) + (1) * *(ConvBuf2 + x+1 + (y-l)*X_INT) +

(0) * *(ConvBuf2 + x-1 + y*X_INT) + (0) * *(ConvBuf2 + x + y*X_INT) + (0) * *(ConvBuf2 + x+1 + y*X_INT) +

(-1) * *(ConvBuf2 + x-1 + (y+l)*X_INT) + (-2) * *(ConvBuf2 + x + (y+1) *X_INT) + (-1) * *(ConvBuf2 + x+1 + (y+1) *X_INT) ,- if ( (tl) > EdgThr) tl = 1; eise tl = 0; if ( (sobbg) > EdgThr) sobbg = 1; eise sobbg = 0; edgsuml += tl; edgsum2 += sobbg;

} edgsum = edgsuml - edgsum2; EdgHist [abs (y) ] = edgsum;

for (y=0; y<=ywidth; y++) { if (EdgHist [y] > Edg) { if (edge) { if (y<YSHADET) { break;

}

SegList [nr] .dp -= y; SegList [nr] .dp += 3; back = 1; break;

} else{ edge = 1; } } else{ edge = 0; } } return(back) ;

} /* EOF

/******************************************************** ** ****************** ₇

/* */

/* Routine to filter the tracking with a kalman filter

*/

/* Calculation of histograms is added

*/ /* Functions of mathsys.c are included

*/

/*

*/

/* Author: Michael Kilger */

/*

*/

/* Version 1.0: 19.9.1992

*/ /*

*/

/******************************************************** **

******************/

#inelüde "co mon.h"

#include <stdio.h> finclude <math.h>

#include <malloc.h> »include <stdlib.h>

#include "kalman.h"

#define MINDIST 20000 #define MINDIST_S 1200

«define MAXMALUS 1 #define MAXDIST 10000

extern int sys_times(float *, float *, float *); extern void sys_plus(float *, float *, float *); extern void sys_minus (float *, float *, float *); extern void transpose(float *, float *); extern void invert2 (float *, float *);

/*prototypes */ unsigned char create_track(struet sgmlst *,trp *,int unsigned char remove_track(trp *); int initialize_kalman( void );

27 void kalman(trp ) ; void assign_sgm (struct sgmlst ,trp *,int void assign( trp );

/******************************************************** ** *** unsigned char create_track(struct sgmlst *curseg,trp *traclst,int *track_count)

/* creates a new track with track nu ber */

/* and inserts it at the begin of traclst. */

{ int ι; /*auxiliary variable*, trp new; if((new = (struct track *)malloc(sizeof( struct track) ) ) == NULL) { printf( "allocation error - aborting"); exit ( 0 ) ; } new->X_meas = curseg->X (*new) .Y_meas = curseg->Y new->Width = curseg->Width *new) ,X_hat = curseg->X (*new) .Y_hat = curseg->Y *new) .Xdot_hat = 0.; *new) .Ydot_hat = 0.; *new) .X_tilde = curseg->X *new) .Y_tilde = curseg->Y (*new) .Xmeas_tilde = curseg->X *new) .Ymeas_tilde = curseg->Y *new) .number = *track_coun ; *new) .malus = 0 *new) .count = 1, (*new).class = 0, *new) .ass = 0; *new) .corr_sgmt = curseg; *new) .next = (*traclst) ; *traclst) = new; *track count += 1; return( }

********************************************************* * *** unsigned char remove_track(trp *traclst)

{ trp obsolete, curtrack, curtrackl;

#if DEBUG FILE *fp; fp = fopen("track.Ist", "a++") ; #endif

Z.o for (curtrack = (*traclεt); curtrack != NULL;) { if ( ( (*curtrack) . alus > MAXMALUS) ) { obsolete = curtrack; curtrack = (*curtrack) .next; if (curtrack == NULL) {

(*traclst) = NULL; }

#if DEBUG fprintf (fp, "No: %d\n count = %d, class = %d\n" ,obsolete->number,obsolete->count, obsolete->class) ; fprintf (fp, "X_hat = %6.2fm,Y_hat %6.2fm,Width = %6.2fm\n" ,obsolete->X_hat/1000, obsolete- >Y_hat/1000,obsolete->Width/1000) ; fprintf (fp, "X_meaε = %6.2fm,Y_meas %6.2fm\n",obsolete->X_meas/1000,obsolete->Y_meas/1000) ; fprintf (fp, "X_tilde = %6.2fm,Y_tilde = %6.2fm\n\n\n",obsolete->X_tilde/1000,obsolete- >Y_tilde/1000) ;

#endif free(obsolete) ;

} eise {

(*traclst) = curtrack; break; }

} for (curtrack = (*traclst); curtrack i= NULL;) { for (curtrackl = (*curtrack) .next; curtrackl != NULL; ) { if ( ( (*curtrackl) .malus > MAXMALUS) ) { obεolete = curtrackl; curtrackl = (*curtrackl) .next; #if DEBUG fprintf (fp, "No: %d\n count = %d, class =

%d\n" , obsolete->number,obsolete->count, obsolete->claεs) ; fprintf (fp, "X_hat = %6.2fm,Y_hat %6.2fm,Width = %6.2fm\n" , obsolete->X_hat/1000, obsolete- >Y_hat/1000,obεolete->Width/1000) ; fprintf (fp, "X_meaε = %6.2fm,Y_meas

%6.2fm\n" , obsolete->X_meas/1000,obsolete->Y_meas/1000) ; fprintf (fp, "X_tilde = %6.2fm,Y_tilde = %6.2fm\n\n\n",obsolete->X_tilde/1000,obsolete- >Y_tilde/1000) ; #endif free(obsolete) ; if (curtrackl == NULL) { (*curtrack) .next = NULL; break; }

} eise {

(*curtrack) .next = curtrackl; break; }

curtrack = curtrackl; } #if DEBUG fclose(fp) ; #endif return( 1 ) ; } ********************************************************** ***/

/* initialize kalman matrices

*/ int initialize_kalman()

{ float aux2[18]; int i,j ; for(i=0;i<4i++) { if (εyε_times (measure,system_kal,ca_matr) ) { printf("No correct atric multiplicationi\n") ; exit(l); /* constant update matrices */

} if(syε_times (kalmang[i] ,ca_matr,aux2) ) { printf("No correct matric multiplicationi\n") ; exit(l); /* akca_matr and kalmang */ } syε_minuε(εyεtem_kal,aux2,akca_matr[i] ) ;

} return 0; }

********************************************************* * **** void kalman(trp current_track) {

/* variables for kalman-filtermg

*/ float stateest[6] ,statepre[6] ,measpre[4] ,meas[4] ; float kalman[10] ,varpre[18] ,auxl [18] ,aux2 [18] ; float aux3 [10] ,aux4[10] ,aux5[6] ,aux6[6] ,aux7 [4] ; float aux8[6] ; stateest [0] = 4.0F; stateest [1] = 1.0F; stateest[2] = (float) (*current_track) .X_hat; εtateeεt[3] = (float) (*current_track) .Y_hat; stateest[4] = (float) (*current_track) .Xdot_hat; εtateeεt[5] = (float) (*current_track) .Ydot_hat; meaε[0] = 2.0F;

30 43

meaε[l] = 1.0F; meaε[2] = (float) (*current_track) .X_meaε meaε [3] = (float) (*current_track) .Y_meaε

εyε_timeε (system_kal, εtateeεt, εtatepre) predicted εtates at time t */ sys__tiir.es (measure, statepre,measpre) ,- /* predicted meaεurement at time t */ transpose (system_kal,auxl) ; εyε_times (variance,auxl,aux2) ; syε_times (system_kal, aux2,auxl) εys_plus (auxl, εyεnl,varpre) ; /* predicted variance at time t */ tranεpoεe(measure,aux3) ; sys_times (varpre, aux3, aux4) ; syε_times (measure,aux4, aux5) ; εys_pluε (aux5,meaεnl,aux6) ; invert2 (aux6,aux5) ; εyε_timeε (aux3 ,aux5, aux4) ; εys_times (varpre,aux4,kalman) ; /* Kaiman gain at time t */ sys_minus ( eas,meaεpre, aux7) ; εyε_timeε (kalman,aux7,aux8) ; sys_plus (statepre,aux8, stateest) ; /* with measurement corrected State variables */ sys_times (measure,varpre, aux3) ; syε_times (kalman,aux3 ,auxl) ; sys_minus (varpre,auxl,variance) ; /* variance at time t */

(*current_track) .X_hat = stateeεt[2]; (*current_track) .Y_hat = εtateeεt[3] ; (*current_track) .Xdot_hat = stateest [4] ; (*current_track) .Ydot_hat = εtateeεt [5] ; syε_timeε (εystem_kal, εtateest, εtatepre) ; /* predicted εtateε at time t+1 */

(*current_track) .X_tilde = statepre[2]; (*current_track) .Y_tilde = statepre[3]; } ********************************************************** ***** void asεign_εgmt (εtruct sgmlst **seglst,trp *traclst,int *track_count)

{ trp curtrack, curtrackl; struct sgmlst *curseg; double dist, maxx,maxy;

int aεεigned; for (curtrack = (*traclst) ;curtrack != NULL; curtrack = (*curtrack) .next) { curtrack->asε = -1; assigned = 0;

(*curtrack) .diff = MINDIST; for (curεeg = (*seglst); curseg->next != NULL; curεeg = (*curεeg) .next) { maxx = fabε ( curseg->X - (*curtrack) .X_tilde) ; axy = fabε ( curεeg->Y - (*curtrack) .Y_tilde) ; dist = (maxx >= maxy) ? maxx : maxy; if (dist < (*curtrack) .diff) { assigned = 1;

(*curtrack) .diff = (long)diεt; (*curtrack) .corr_εgmt = curseg;

} }

if( assigned == 0){

(*curtrack) .malus += 1; curtrack->ass = -1; curtrack->X_meas = curtrack->X_tilde curtrack->Y_meaε = curtrack->Y_tilde #if DEBUG printf ( "trackno. %d could not be aεεigned to a segment\n", (*curtrack) .number) ; #endif } else{ if (curtrack->corr_sgmt->aεε) { for (curtrackl = (*traclεt) ; curtrackl != curtrack; curtrackl = curtrackl->next) { if (curtrack->corr_εgmt == curtrackl- >corr_εgmt) { if (curtrack->count > curtrackl->count) { curtrackl->malus = MAXMALUS+1; assign (curtrack) ; } else{ curtrack->malus = MAXMALUS+1; } break; } } } else{ assign(curtrack) ; } } }

for (curseg = (*εeglst); curseg->next != NULL; curεeg = (*curseg) .next) {

#if DEBUG // printf( ^u curseg->Width:%f\n",curseg->Width) ; #endif if ( curseg->ass == 0 && curseg->Y < 300000.0 && curseg->Y > 50000.0) { create_track(curseg,traclst,track_count) ; curseg->ass = 1; } } remove_track(traclst) ; for (curtrack = (*traclεt) ;curtrack != NULL; curtrack = (*curtrack) .next) { kalman(curtrack) ; }

}

I **********************************************************

*************** void assign( trp curtrack) {

(curtrack->count)++; curtrack->ass = 1; curtrack->corr_εgmt->ass = 1; curtrack->X_meaε = curtrack->corr_sgmt->X curtrack->Y_meaε = curtrack->corr_εgmt->Y curtrack->Width = curtrack->corr_εgmt->Width }

/* EOF */