Method and apparatus for detecting object movement within an image sequence

Description of equivalent WO 9622588 A1

METHOD AND APPARATUS FOR DETECTING OBJECT MOVEMENT WITHIN AN IMAGE SEQUENCE

0002BACKGROUND OF THE INVENTION >5 1. Field of the Invention

0003The invention relates to an image processing system and, more particularly, to such a system that digitally processes pixels of successive image frames (an image sequence) derived from a video camera viewing a scene such that the system detects object movement within the image 0 sequence. One particular embodiment of the invention is a vehicular traffic monitoring system.

00042. Description of the Background Art

0005Various types of traffic monitoring systems that utilize image 5 processing are known in the prior art and examples thereof are respectively disclosed in U.S. patents 4,433,325, 4,847,772, 5,161,107 and 5,313,295. However, there is a need for a more robust traffic monitoring system that is computationally efficient and yet is relatively inexpensive to implement.

0006Further, the present invention makes use of pyramid teachings 0 disclosed in U.S. patent 4,692,806, which issued to Anderson et al. on September 8, and image flow teachings disclosed in the article "Hierarchical Model-Based Motion Estimation" by Bergen et al., appearing in the Proceedings of the European Conference on Computer Vision, Springer- Verlag, 1992. Both of these teachings are incorporated herein by 5 reference.

0007SUMMARY OF THE INVENTION The invention relates to an improved digital image processing technique as applied to a vehicular traffic monitoring system that includes 0 a video camera having a given field of view for recording successive image frames of road traffic within its field of view. The digital image processing means, is responsive to pixel information defined by each of the successive image frames.

0008Specifically, the digital image processing technique comprises first 5 means responsive to an initial train of the successive image frames for deriving a stored initial reference image defining only stationary objects within the field of view and thereafter updating the stored initial reference image with a reference image derived from an image frame recorded later than the initial train, with each pixel's digital amplitude level of each of the reference images being determined by illumination conditions existing when the initial train and when the later recorded frame were recorded; second means for modifying each pixel's digital amplitude level of one of a current image frame and the stored reference image then being stored to make their corresponding pixels defining stationary objects substantially equal to one another; third means responsive to the digital amplitude-level difference between corresponding pixels of each of successively-occurring ones of the successive image frames and the then stored reference image for deriving successive images defining only moving objects within the field of view; fourth means for discriminating between those moving objects that remain substantially fixed in position with respect to one another in each of the successively-occurring ones of the successively-occurring images and those moving objects that substantially change in position with respect to one another in each of the successively-occurring ones of the successively- occurring images; and fifth means responsive to the variance of the digital amplitude levels of the pixels of those ones of the objects that remain substantially fixed in position with respect to one another for distinguishing and then eliminating those ones of the moving objects that remain substantially fixed in position with respect to one another that define non- physical moving objects, such as shadows and headlight reflections cast by physical moving objects, from the moving objects that remain substantially fixed in position with respect to one another that define the physical moving objects.

0009BRIEF DESCRIPTION OF THE DRAWING Figs, la and lb show alternative real time and non-real time ways of coupling a video camera to a traffic-monitoring image processor; Figs. 2a, 2b and 2c relate to the image field of a video camera viewing a multi-lane roadway;

0010Fig. 3 is a functional block diagram of the preprocessing portion of the digital image processor of the present invention;

0011Fig. 4 is a functional block diagram of the detection and tracking portion of the digital image processor of the present invention;

0012Figs. 5 and 5a illustrate the manner in which image pixels of a 2D delineated zone of a roadway lane are integrated into a ID strip; FIG. 6 depicts a flow diagram of a process for updating the reference images;

0013FIG. 7 depicts a flow diagram of a process for modifying the reference images; FIG. 8 depicts a block diagram of a 2D to ID converter; and

0014FIG. 9 depicts an alternative image filter.

0015DESCRIPTION OF THE PREFERRED EMBODIMENTS The present invention comprises at least one video camera for deriving successive image frames of road traffic and a traffic-monitoring image processor for digitally processing the pixels of the successive image frames. As shown in Fig. la, the output of video camera 100 may be directly applied as an input to traffic-monitoring image processor 102 for digitally processing the pixels of the successive image frames in real time. Alternatively, as shown in Fig. lb, the output of video camera 100 may be first recorded by a video cassette recorder (VCR) 104, or some other type of image recorder. Then, at a later time, the pixels of the successive image frames may be readout of the VCR and applied as an input to traffic- monitoring image processor 102 for digitally processing the pixels of the successive image frames.

0016Video camera 100, which may be charge-coupled device (CCD) camera, an infrared (IR) camera, or other sensor that produces a sequence of images. In the traffic monitoring system embodiment of the invention, the camera is mounted at a given height over a roadway and has a given field of view of a given length segment of the roadway. As shown in Figs. 2a and 2b, video camera 100, by way of example, may be mounted 30 feet above the roadway and have a 62° field of view sufficient to view a 60 foot width (5 lanes) of a length segment of the roadway extending from 50 feet to 300 feet with respect to the projection of the position of video camera 100 on the roadway. Fig. 2c shows that video camera 100 derives a 640x480 pixel image of the portion of the roadway within its field of view. For illustrative purposes, vehicular traffic normally present on the length segment of the roadway has been omitted from the Fig. 2c image.

0017In a designed vehicular traffic monitoring system, video camera 100 was one of a group of four time-divided cameras each of which operated at a frame rate of 7.5 frames per second. A principal purpose of the present invention is to be able to provide a computationally-efficient digital traffic-monitoring image processor that is capable of more accurately detecting, counting and tracking vehicular traffic traveling over the viewed given length segment of the roadway than was heretofore possible. For instance, consider the following four factors which tend to result in detecting, and tracking errors or in decreasing computational efficiency:

00181. Low Contrast:

0019A vehicle must be detected based on its contrast relative to the background road surface. This contrast can be low when the vehicle has a reflected light intensity similar to that of the road. Detection errors are most likely under low light conditions, and on gray, overcast days. The system may then miss some vehicles, or, if the threshold criteria for detection are low, the system may mistake some background patterns, such as road markings, as vehicles.

00202. Shadows and Headlight Reflections:

0021At certain times of day vehicles will cast shadows or cause headlight reflections that may cross neighboring lanes. Such shadows or headlight reflections will often have greater contrast than the vehicles themselves. Prior art type traffic monitoring systems may then interpret shadows as additional vehicles, resulting in an over count of traffic flow. Shadows of large vehicles, such as trucks, may completely overlap smaller cars or motor cycles, and result in the overshadowed vehicles not being counted. Shadows may also be cast by objects that are not within the roadway, such as trees, building, and clouds. And they can be cast by vehicles going the other direction on another roadway. Again, such shadows may be mistaken as additional vehicles.

00223. Camera Sway:

0023A camera that is mounted on a utility pole may move as the pole sways in a wind. A camera mounted on a highway bridge may vibrate when trucks pass over the bridge. In either case camera motion results in image motion and that cause detection and tracking errors. For example, camera sway becomes a problem if it causes the detection process to confuse one road lane with another, or if it causes a stationary vehicle to appear to move. 4. Computational Efficiency:

0024Since vehicle travel is confined to lanes and normal travel direction is one dimensional along the length of a lane, it is computationally inefficient to employ two-dimensional image processing in detecting and tracking vehicular traffic.

0025The present invention is directed to an image processor embodied in a traffic monitoring system that includes means for overcoming one or more of these four problems.

0026Referring to Fig. 3, there is shown a functional block diagram of a preferred embodiment of a preprocessor portion digital traffic-monitoring image processor 102. Shown in Fig. 3 are analog-to-digital (A/D) converter 300, pyramid means 302, stabilization means 304, reference image derivation and updating means 306, frame store 308, reference image modifying means 310 and subtractor 312. The analog video signal input from camera 100 or VCR 104, after being digitized by A/D 300, may be decomposed into a specified number of Gaussian pyramid levels by pyramid means 302 for reducing pixel density and image resolution. Pyramid means 302 is not essential, since the vehicular traffic system could be operated at the resolution of the pixel density produced by the video camera 100 (e.g., 640x480). However, because this resolution is higher than is needed downstream for the present vehicular traffic system, the use of pyramid means 302 increases the system's computational efficiency. Not all levels of the pyramid must be used in each computation. Further, not all levels of the pyramid need be stored between computations, as higher levels can always be computed from lower ones. However, for illustrative purposes it is assumed that all of the specified number of Gaussian pyramid levels are available for each of the downstream computations discussed below.

0027The first of these downstream computations is performed by stabilization means 304. Stabilization means 304 employs electronic image stabilization to compensate for the problem of camera sway, in which movement may be induced by wind or a passing truck. Camera motion causes pixels in the image to move. Prior art vehicular traffic systems that do not compensate for camera motion will produce false positive detections if the camera moves so that the image of a surface marking or a car in an adjacent lane overlaps a detection zone. Stabilization means 304 compensates for image translation from frame to frame that is due to camera rotation about an axis perpendicular to the direction of gaze. The compensation is achieved by shifting the current image an integer number of rows and columns so that, despite camera sway, it remains fixed in alignment to within one pixel with a reference image derived by means 306 and stored within frame store 308. The required shift is determine by locating two known landmark features in each frame. This is done via a matched filter.

0028The problem of low contrast is overcome by the cooperative operation of reference image derivation and updating means 306, frame store 308 and reference image modifying means 310. Means 306 generates an original reference image r₀ simply by blurring the first -occurring image frame i₀ applied as an input thereto from means 304 with a large Gaussian filter (so that reference image r₀ may comprise a higher pyramid level), and then reference image r₀ is stored in frame store 308. Following this, the image stored in frame store 308 is updated during a first initialization phase by means 306. More specifically, means 306 performs a recursive temporal filtering operation on each corresponding pixel of the first few image frames of successive stabilized image frames applied as an input thereto from means 304, with the additional constraint that if the difference between the reference image and the current image is too large, the reference image is not updated at that pixel. Put mathematically,

0029<img file="WO9622588A1_D0001.tif" />

0030where r_t represents the reference image after frame t, and i_t represents the t'th frame of the input image frame sequence from means 304. The constant γ determines the "responsiveness" of the construction process.

0031FIG. 6 depicts a flow diagram of an illustrative process 600 for implementing equation 1 within a practical system, i.e., FIG. 6 illustrates the operation of means 306 of FIG. 3 as described above. Specifically, a reference image and a next image in the sequence are input to means 306 at step 602. The reference image is the previously generated reference image or, if this is the initial reference image, it is a blurred version of the first image frame in the image sequence. At step 604, a pixel is selected from the reference image (r_t.α(x,y)) and a pixel is selected from the next image (i^x.y)). Next, at step 606, the pixel value of the reference image is subtracted from the pixel value of the next image producing a difference factor (DIFF= i_t(x,y)- r_t_₁(x,y)). The process then computes, at step 608, the absolute value of the difference factor ( | DIFF | ). At step 610, the absolute value of the difference factor is compared to a threshold (D). The process queries whether the absolute value of the difference factor is less than the threshold. If the query is negatively answered, then the process proceeds to step 614. If the query is affirmatively answered, then the process proceeds to step 612. At step 612, the process updates the selected reference image pixel value with a pixel value equal to the selected reference image pixel value multiplied by an update factor (U). The update factor is the difference factor multiplied by the constant γ. At step 614, the process queries whether all the pixels in the images have been processed. If not, then the process returns to step 604. If all the pixels have been processed, the process ends at step 616. The "responsiveness" setting of γ must be sufficiently slow to keep transitory objects, such as moving vehicles or even vehicles that may be temporarily stopped by a traffic jam, out of the reference image, so that, at the end of the first few input image frames to means 306 which comprise the first initialization phase, the stored reference image in frame store 308 will comprise only the stationary background objects being viewed by camera 100. Such a "responsiveness" setting of γ is incapable of adjusting r_t quickly enough to add illumination changes (such as those due to a passing cloud or the auto-iris on camera 100) to the reference image. This problem is solved at the end of the initialization phase by the cooperative updating operation of reference image modifying means 310 (which comprises an illumination/AGC compensator) with that of means 306 and frame store 308. Specifically, when the initialization phase (as shown in FIG. 6) is completed, it is replaced by a second normal operating phase which operates in accordance with the following equation 2 (rather than the above equation 1):

0032. , fr,_,(-«,y) + y[ι,(-e,y) - ι;_₁(-c,y)] if |ι,(x,y) - r,_₁(x,y)| &lt; D [k,r,__} (x, y) + c, otherwise

0033where k_t and c_t, are the estimated gain and offset between the reference image r_t and the current image i_t computed by means 310. Means 310 computes this gain and offset by plotting a cloud of points in a 2D space in which the x-axis represents gray -level intensity in the reference image, and the y-axis represents gray-level intensity in the current image, and fitting a line to this cloud. The cloud is the set of points (r_t-ι(x,y),i_t(x,y)) for all image positions x,y. This approach will work using any method for computing the gain and offset representing illumination change. For example, the gain might be estimated by comparing the histograms of the current image and the reference image. Also, the specific update rules need not use an absolute threshold D as described above. Instead, the update could be weighted by any function of | it(x,y)-r_t-ι(x,y) | . FIG. 7 depicts a flow diagram of an illustrative process 700 for implementing equation 2 within a practical system, i.e., FIG. 7 illustrates the operation of means 310 of FIG. 3. A reference image and a next image in the sequence are input at step 702. If this is the first time means 310 is used, the reference image is the last reference image generated by means 306; otherwise, it is a previous reference image produced by means 310. At step 704, a pixel is selected from the reference image (r_t._x(x,y)) and a pixel is selected from the next image (i_t(x,y)). Next, at step 706, the pixel value of the reference image is subtracted from the pixel value of the next image producing a difference factor (DIFF= i_t(x,y)- r_{t l}(x,y)). The process then computes, at step 708, the absolute value of the difference factor ( | DIFF | ). At step 710, the absolute value of the difference factor is compared to a threshold (D). The process queries whether the absolute value of the difference factor is less than the threshold. If the query is negatively answered, then the process proceeds to step 714. At step 714,the process modifies the selected reference image pixel value with a pixel value equal to the selected reference image pixel value multiplied by a gain (k and scaled by an offset (c_t). If the query is affirmatively answered, then the process proceeds to step 712. At stepΦ712, the process modifiesthe selected reference image pixel value with a pixel value equal to the selected reference image pixel value multiplied by an modification factor (M). The modification factor is the difference factor multiplied by the constant γ. Once the process has modified the pixel values, the process queries, at stepΦ716,whether all the pixels in the images have been processed. If not, then the process returns to stepΦ704. If all the pixels have been processed, the process ends at steρΦ716.

0034The above approach allows fast illumination changes to be added to the reference image while preventing transitory objects from being added. It does so by giving the cooperative means the flexibility to decide whether the new reference image pixel values should be computed as a function of pixel values in the current image or whether they should be computed simply by applying a gain and offset to the current reference image. By applying a gain and offset to the current reference image the illumination change can be simulated without running the risk of allowing transitory objects to appear in the reference image.

0035Returning to FIG. 3, the result is that the amplitude of the stationary background manifesting pixels of the illumination-compensated current image appearing at the output of means 310 (which includes both stationary background manifesting pixels and moving object (i.e., vehicular traffic)) will always be substantially equal to the amplitude of the stationary background manifesting pixels of the reference image (which includes solely stationary background manifesting pixels) appearing at the output of frame store 308. Therefore, subtractor 312, which computes the difference between the amplitudes of corresponding pixels applied as inputs thereto from means 310 and 304, derives an output made up of significantly-valued pixels that manifest solely moving object (i.e., vehicular traffic) in each one of successive 2D image frames. The output of subtractor 312 is forwarded to the detection and tracking portion of traffic-monitoring image processor 102 shown in Fig. 4.

0036Referring to Fig. 4, there is shown 2D/1D converter 400, vehicle fragment detector 402, image-flow estimator 404, single frame delay 406, pixel-amplitude squaring means 408, vehicle hypothesis generator 410 and shadow and reflected headlight filter 412.

00372D/1D converter 400 operates to convert 2D image information received from Fig. 3 that is applied as a first input thereto into ID image information in accordance with user control information applied as a second input thereto. In this regard, reference is made to Figs. 5 and 5a. Fig. 5 shows an image frame 500 derived by camera 100 of straight, 5-lane roadway 502 with cars 504-1 and 504-2 traveling on the second lane 506 from the left. Cars 504-1 and 504-2 are shown situated within an image zone 508 delineated by the aforesaid user control information applied as a second input to converter 400. By integrating horizontally the amplitudes of the pixels across image zone and then subsampling the vertically oriented integrated pixel amplitudes along the center of zone 508, ID strip 510 is computed by converter 400. The roadway need not be straight. As shown in Fig. 5a, curved roadway lane 512 includes zone 514 defined by user- delineated lane boundaries 516 which permits the computation of medial strip 518 by converter 400. In both Figs. 5 and 5a, the user may employ lane- defining stripes that may be present in the image as landmarks for help in defining the user-delineated lane boundaries .

0038More specifically, computation by converter 400 involves employing each of pixel positions (x, y) to define integration windows. For example, such a window might be either (a) all image pixels on row y that are within the delineated lane bounds, (b) all image pixels on column x that are within the delineated lane bounds, or (c) all image pixels on a line perpendicular to the tangent of the medial strip at position (x, y). Other types of integration windows not described here may also be used. FIG. 8 depicts a block diagram of the 2D/1D converterΦ400 as comprising a zone definition blockΦ802connected in series to an integratorΦ804which is connected in series to an image sub-samplerΦ806. The user input that defines the zones within the 2D image is applied to the zone definition blockΦ802.

0039Returning to FIG. 4, the ID output from converter 400 is applied as an input to detectorΦ402, estimator 404 and single frame delay406, and through meansΦ410 to filterΦ412. While the respective detection, tracking and filtering functions performed by these elements are independent of whether they operate on ID or 2D signals, ID operation is to be preferred because it significantly reduces computational requirements. Therefore, the presence of converter 400, while desirable, is not essential to the performance of these detection, tracking and filtering functions. In the following discussion, it is assumed that converter 400 is present.

0040Detector 402 preferably utilizes a multi-level pyramid to provide a coarse-to-fine operation to detect the presence and spatial location of vehicle fragments in the ID strip of successive image frames received from Fig. 3. A fragment is defined as a group of significantly-valued pixels at any pyramid level that are connected to one another. Detector 402 is tuned to maximize the chances that each vehicle will give rise to a single fragment. However, in practice this is impossible to achieve; each vehicle gives rise to multiple fragments (such as separate fragments corresponding to the hood, roof and headlights of the same vehicle). Further, pixels of more than one vehicle may be connected into a single fragment.

0041One technique for object detection at each strip pixel position is to compute a histogram of the image intensity values within the integration window centered at that pixel position. Based on attributes of this histogram (e.g., the number or percentage of pixels over some threshold value or values), classify that strip pixel as either "detection" or "background". By performing this operation at each strip pixel, one can construct a one- dimensional array that contains, for each pixel position, the "detection" or "background" label. By performing connected component analysis within this array, adjacent "detection" pixels can be grouped into "fragments".

0042Image-flow estimator 404 in cooperation with delay 406, which employs the teachings of the aforesaid Bergen et al. article, to permit objects to be tracked over time. Briefly, in this case, this involves, at each pixel position, computing and storing the average value contained within the integration window. By performing this operation at each strip pixel, a one- dimensional array of average brightness values is constructed. Given two corresponding arrays for images taken at times t-1 and t, the one- dimensional image "flow" that maps pixels in one array to the other is computed. This can be computed via one-dimensional least-squares minimization or one-dimensional patchwise correlation. This flow information can be used to track objects between each pair of successive image frames. The respective outputs of detector 402 and estimator 404 are applied as inputs to vehicle hypothesis generator 410. Nearby fragments are grouped together as part of the same object (i.e., vehicle) if they move in similar ways or are sufficiently close together. If the positions of multiple fragments remain substantially fixed with respect to one another in each of a train of successive frames, they are assumed to indicate only a single vehicle. However, if the positions of the fragments change from frame to frame, they are assumed to indicate separate vehicles. Further, if a single fragment of in one frame breaks up into multiple fragments or significantly stretches out longitudinally in shape from one frame to another, they are also assumed to indicate separate vehicles.

0043At night, the presence of a vehicle may be indicated only by its headlights. Headlights tend to produce headlight reflections on the road. Lighting conditions on the road during both day and night tend to cause vehicle shadows on the road. Both such shadows and headlight reflections on the road result in producing detected fragments that will appear to generator 410 as additional vehicles, thereby creating false positive error in the output from generator 410. Shadow and reflected headlight filter 412, which discriminates between fragments that produced by valid vehicles and those produced by shadows and reflected headlights, eliminates such false positive error.

0044The output from pixel-amplitude squaring means 408 manifests the relative energy in each pyramid-level pixel of the strip output of each of successive image frames from converter 400. Filter 412 discriminates between fragments that produced by valid vehicles and those produced by shadows and reflected headlights based on an analysis of the relative amplitudes of these energy-manifesting pixels from means 408. The fact that the variance in energy pixel amplitude (pixel brightness) of shadow and reflected headlight fragments is significantly less than that of valid vehicle fragments can be used as a discriminant.

0045Another way of filtering, not shown in Fig. 4, is to employ converter 400 for discriminating between objects and shadows using the background- adjusted reference image. FIG. 9 depicts a block diagram of this alternative filter. At each pixel position, the following information is computed over the integration window:

0046(a) the number of pixels with brightness value greater than some threshold p, over all image pixels within the integration window (elementΦ904);

0047(b) the maximum absolute value, over all image pixels within the integration window (elementΦ906);

0048(c) the number of adjacent pixels ( ^y,) and (x_,y.) within the integration window whose absolute difference, | Kx,,y,) - x₂,y₂) | , exceeded a threshold value (element 908). This information is used by filterΦ902to discriminate between objects and shadows using the background-adjusted reference image.

0049Fragments that have been extracted as described previously can be classified as object or shadow based on these or other properties. For example, if the value of measure (a), summed over all strip pixels within the fragment, exceeds some threshold, then the fragment cannot be a shadow (since shadows would never have positive brightness values in the images applied to converter 400 from Fig. 4. A similar summation using measure (c) provides another test measuring the amount of texture within the fragment, which can also be thresholded to determine whether a fragment is an object or a shadow. While the input to filter 412 defines all hypothesized vehicle locations, the output therefrom defines only verified vehicle locations. The output from filter 412 is forwarded to utilization means (not shown) which may perform such functions as counting the number of vehicles and computing their velocity and length.

0050Vehicle fragment detector 402, image-flow estimator 404, and vehicle hypothesis generator 410 may use pre-determined camera calibration information in their operation. Further, each of the various techniques of the present invention described above may also be employed to advantage in other types of imaging systems from the vehicular traffic monitoring system disclosed herein.