EP1988505B1

EP1988505B1 - Method and system for initializing templates of moving objects

Info

Publication number: EP1988505B1
Application number: EP07008960.2A
Authority: EP
Inventors: Fabian Friedrichs; Faraz Siddiqui; Klaus Zimmermann
Original assignee: Sony Deutschland GmbH
Current assignee: Sony Corp
Priority date: 2007-05-03
Filing date: 2007-05-03
Publication date: 2020-05-06
Anticipated expiration: 2027-05-03
Also published as: US8045812B2; CN101299272B; EP1988505A1; EP3683768A1; CN101299272A; US20080273806A1; EP3683768B1

Description

The invention relates to a method and a system for initializing templates of moving objects and a corresponding computer program product.

BACKGROUND

In image processing template tracking is used e.g. for tracking of faces in videos, or for satellite surveillance. Also in front view cameras in automotive applications template tracking is used for tracking movements of vehicles in front of an own vehicle. The templates are usually initialized manually or by classification, which is possible, since the perspective does not change in front view applications. However, in side-view applications or blind spot monitoring for vehicles, the perspective changes and commonly used classification cannot be performed.
The publication "Statistical approaches to tracking-based moving object extraction", Information Intelligence and Systems, 1999, Proceedings, pages 375 - 381, discloses a tracking-based moving object extraction algorithm, wherein object location and tracking is achieved by using a template matching scheme using a threshold based segmentation technique. The structural regions of a moving object are detected and represented on a coarse block resolution. Then, interest regions of the moving objects are further formed by region merging according to spatial temporal similarity measures. Finally, the moving objects are located by temporal tracking.
Prior art document US 2006/088191 A1 discloses a real-time video motion analysis method and system, wherein motion vectors are determined from a pair of successive images. Determining is performed by segmenting one of the pair of successive images into a plurality of blocks of pixels, then selecting blocks corresponding to at least one feature in the image, determining luminance values corresponding to respective selected blocks, matching the selected blocks to blocks of pixels in the other of the pair of successive images based on said luminance values, and finally determining motion vectors which are associated with matched blocks in the pair of successive images. In addition, an affine model of a camera's motion is estimated based on the motion vectors, wherein the estimated affine model determines a set of camera motion parameters.
Document AU 2002318859 A1 discloses a method for video object detection and tracking, which is based on 3D segment displacement. In the method a 3D pixel data block is formed from a sequence of video frames. On the basis of the color said 3D data block is formed into a block of 3D segments using 3D spatial temporal segmentation. Absolute motion of each 3D segment is estimated by calculating a vector difference between a 2D centroid of an intersection of 3D segment with a view plane and a 2D centroid of an intersection of said 3D segment with said view plane in a previous frame interval. Each 3D segment is classified, wherein 3D segments having absolute motion exceeding in any direction a calculated bound of said intersection of said 3D segment with a view plane in that direction are classified as significant. Finally, adjacent significant 3D segments are grouped into a segmented video object. Document US 2007/0014432 A1 discloses a motion-object tracking control apparatus, system, and method, wherein a plurality of calculation points is arranged on a specified region and a group of local motion vectors is determined for the calculation points. A moving-object motion vector is obtained based on the determined local motion vectors. A group of calculation points is continuously used to calculate the local motion vectors and is updated by moving the position of the group of calculation points along the moving object motion vector.
Document WO 2004/013810 A1 discloses a system and a method for segmenting a first image feature in a first video image from an adjacent second image feature in the first video image on the basis of motion and on an image property-like color or luminance.
It is an object of the invention to provide a improved method and an improved system for initializing templates of moving objects.
The object is solved by a method, a system and a computer program product according to claims 1, 7 and 9.
Further embodiments are defined in the dependent claims.
Further details of the invention will become apparent from a consideration of the drawings and ensuing description.

BRIEF DESCRIPTION OF THE DRAWINGS

Fig. la shows main steps of one embodiment of the invention, explaining motion estimation and segmentation steps;
Fig. 1b shows main steps of a combination of initializing the template and afterwards tracking the template;
Fig. 2 shews a block diagram of a further embodiment of the invention, as it might be applied in automotive computer vision;
Fig. 3 shows a block diagram of a further embodiment of the invention, where the initialization unit is just triggered if an update is necessary;
Fig. 4 shows an exemplary template as used in a further embodiment of the invention;
Fig. 5 shows an exemplary image, in which the template from Fig. 4 is tracked,
Fig. 6 shows a block diagram of a further embodiment of the invention as it can be applied for consumer electronics with arbitrary content/video sequences;
Fig. 7 shows a further exemplary template as used in a further embodiment of the invention for consumer electronics; and
Fig. 8 shows a further exemplary consumer electronics image with a tracked template from Fig. 7.

DETAILED DESCRIPTION

In the following, embodiments of the invention are described. It is important to note, that all described embodiments in the following may be combined in any way, i.e. there is no limitation that certain described embodiments may not be combined with others.
In Fig. la, in step S100 each of the images of a sequence are partitioned into blocks. Each block might comprise 8 x 8 or 16 x 16 pixels, but not only square blocks but blocks of other shapes or with another number of pixels are also possible. Images might be referred to also by "frames" or "fields". The images are taken, e.g. by a digital video camera and are stored pixel-wise in a memory.
In step S102 blocks which have been moved between consecutive images of said sequence are identified. Such movement of block might be detected by calculating an error criterion for possible block displacements. The sum of absolute differences, the correlation product or other methods can be used as match criteria, for instance.
In step S103 a distance and a direction of the movement is determined, e.g. by comparing the position of the moving blocks in consecutive images. The movement in a "similar" direction by a "similar" distance might also be determined by calculating a motion vector between blocks of consecutive images and comparing said motion vector.
In step S104 adjacent blocks, for which directions within a predetermined direction interval and distances within a predetermined distance interval have been determined are grouped in a first group. The predetermined direction interval and the predetermined distance interval are used to detect a movement in basically the same direction by basically a same distance. The predetermined intervals might be fixed or might be adaptive, e.g. to the actual directions or distances of said moving blocks.
Thus, moving blocks which basically move in the same direction by a same distance are grouped together.
In case further moving objects are present within said sequence of images and these moving objects move differently, corresponding further groups might be generated by grouping corresponding further blocks with movements in basically the same direction and basically the same distance as described above.
Instead of the wording "grouping" also the wording "segmenting", "segmentation" or "clustering" is used within this description.
A block might be considered to be adjacent to a further block if the block is at least one of four (or eight) direct neighboring blocks of the further block.
In step S106 an initial template for said moving object is initialized with said first group of blocks. Since this first group of blocks moves "together" such group of blocks is considered to belong to one moving object. So this one moving object is defined by this first group and a corresponding initial template for this moving object is build by using this group of blocks. The pixel values of said group of blocks describe an outer appearance of this moving object.
With this approach well-fitted segmentation outlines of the entire object are used as the initial template, instead of using small blocks at fixed positions, which might partially cover background.
In Fig. 1b, additionally a step S108 is performed, wherein said initial template is tracked in said sequence of images, by evaluating cross-correlation or sum of absolute differences (SAD), for instance.
With the proposed method in automotive computer vision, obstacles (cars, truck, etc.) can be detected and tracked afterwards. No classification is needed. In consumer electronics, the proposed method improves the performance of motion estimation based video processing applications such as frame rate conversion or temporal noise reduction.
According to the invention, said sequence is extended with further images. Moving blocks which have performed a movement between at least a part of said further images of said sequence are identified, a direction and a distance of said movement of said moving blocks are determined, and adjacent moving blocks, for which directions within a predetermined direction interval and distances within a predetermined distance interval have been determined are grouped into a second group of blocks. Thus blocks, which have moved within at least a part of said further images in a "similar" direction by a "similar distance", e.g. detected by evaluating corresponding motion vectors of blocks, are grouped into the second group of blocks. Afterwards the template is updated for said moving object with said second group of blocks. For instance, after a predetermined number of frames the initial template might be updated by a current match, i.e. the second group of blocks.
The proposed method for updating the template can easily cope with scale changes of objects, which occur, when the object is approaching or moving away, with shape changes, which happens, when an object is deformed, with rotation, which occurs in an object as rotating in any direction and with occlusion, which is happening when new pixels are obscured behind a moving object or revealed in front of a moving object. With the proposed method no errors are added up over time, which otherwise would result in a template drifting away from the tracked object until the tracking looses the object.
In a further embodiment said template is tracked based on a sum of absolute differences and/or a cross correlation between said template and parts of the images, in which the template should be tracked.
According to a further embodiment a search range is set around an area, where the object is expected in a subsequent image of said sequence according to its motion behavior in previous images of said sequence; and said step of tracking is performed in said search range in said subsequent image. With this approach the processing time for tracking the template might easily be reduced, since there is no need to track the template in the whole image.
In a further embodiment a correlation between the template and parts of said images of said sequence is calculated and a failure of said step of tracking is detected, if said correlation is below a predetermined correlation threshold. Thus, an update of the template might be started after such a failure of tracking the correct template within said sequence.
So the template might be updated continuously, based on e.g. predetermined time intervals which have passed or based on measurement values, which indicate that a further update might be performed, because e.g. the correlation between the used template and the images of said sequence is decreasing.
In a further embodiment an average motion vector is determined for coherent blocks of said images (representing a moving object of car) and a template motion vector for said template in subsequent images is determined as well. The template motion vector is compared to said average motion vector and said template is rejected, in case of a mismatch between said average motion vector and said template motion vector.
With the proposed use of motion estimation continuously in parallel, template tracking can be used for cross verification. False alarms which occur with motion estimation can be reduced by comparing the motion estimation results with the template tracking results. If these results match well, the template can be updated according to the motion estimation segmentation results. Otherwise, this mismatch indicates problems and may result in rejecting the template.
In a further embodiment said images of said sequence are pre-processed with a global motion estimation and global motion compensation. Within the global motion estimation and global motion compensation effects are considered, which influence all pixels of an image, e.g. due to a pan of a video camera etc. This method is suitable in particular for consumer electronics applications as frame rate conversion, temporal noise reduction, de-interlacing, etc. The global motion estimation and compensation is used to segment all locally moving objects.
In a further embodiment, said method is used for detecting moving objects in a blind spot region of a vehicle, wherein said moving objects are moving backwards in said blind spot region with respect to a movement of said vehicle. Since motion estimation methods do not perform well to detect backwards moving obstacles, the proposed method is used to initialize the template of slowing down vehicles. Slowing down means here that a vehicle has a faster relative velocity at the beginning and is then slowing down to a negative relative velocity._Therewith, automotive safety applications like blind spot region detection can be improved.
In Fig. 2 a block diagram of a further embodiment of the invention is depicted. The depicted system 200 for tracking templates of a moving object comprise an initialization unit 202 which includes a local motion estimation unit 204 and a segmentation unit 206. A video input 208, which consists of a sequence of images is inputted into the initialization unit 202 and the local motion estimation unit 204 partitions each of said images of said sequence into blocks and identifies moving blocks which have moved between consecutive images of said sequence. Afterwards, the segmentation unit 206 initializes a template for said moving objects by grouping adjacent moving blocks, for which directions within a predetermined direction interval and distances within a predetermined distance interval have been determined as it has been described before.
The initialized template is used by a tracking unit 210, which is configured to track said template in said sequence of images delivered by the video input 208. In case such a template is tracked it is output to a template tracking output 212.
In a further embodiment, depicted in Fig. 3 of the system 200 to track templates of moving objects, additionally a decision unit 300 is connected to the output of the tracking unit 210. The decision unit decides whether an update of said template should be performed. For example after a predetermined time or after an evaluated low correlation between the template and the images of the sequence the decision unit might trigger a motion based template update from the initialization unit 202.
The initialization unit 202 performs the motion estimation and groups adjacent blocks which moved for a predetermined time into a "similar" direction for a "similar" distance into a second group, as it has been described above. This second group represents the "new" or "updated" version of the initial template, and thus, the second group is used to update the template which is used afterwards by the tracking unit 210.
In Fig. 4 an example of an initialized template 400 is depicted, which shows the front side of the van, which has been initialized by the proposed method, while taking images with a camera mounted on a rear view mirror of a vehicle, thereby detecting moving objects on an adjacent lane.
In Fig. 5 a whole image, which is taken by the camera is depicted, wherein the tracked template 400 is marked with a white square. With the proposed method moving objects on an adjacent lane may be detected easily and can be used to derive warning information for a driver of the vehicle, in case the driver intends to change the lane.
In a further embodiment, which is depicted in Fig. 6 and which is well suited for being applied to consumer product applications, a global motion estimation/compensation unit is used to pre-process the sequence of images delivered by the video input 208. This global motion estimation/compensation unit 600 is used to compensate the movement, which took place for the whole image, for example due to a movement of the camera, which took the images of the sequence. With this global motion estimation/compensation unit 600 the system 200 can segment all locally moving objects within the segmentation unit 206.
In case an update of a derived template should be used, the decision unit 300 might be used as it is described with respect to Fig. 3, but this decision unit 300 is only optional, which is depicted in Fig. 6 with a dotted line.
In Fig. 7 an example of an extracted template 700 of a consumer electronics sequence, depicted in Fig. 8, is depicted. Motion estimation usually has problems with such kind of movements, because the moving objects obscure other moving objects in the background. As it is depicted in Fig. 7, the object is well segmented and the other parts of the image are not considered in the correlation or filled with zeros or equally distributed noise.
According to a further embodiment a computer program product is provided, which comprises a computer program code which when loaded into a processor performs the proposed method for tracking the moving object.
With the proposed method backward moving objects in blind spot detection devices can be detected in automotive security application, what is desired by automotive manufacturers. The proposed method and system use motion estimation based segmentation results in order to initialize and/or update template tracking of moving objects. The method and system can be used even in cases where motion estimation based approaches completely fail, e.g. for backward moving objects in a blind spot region detection.
The template of a forward and backward moving vehicle can be tracked well over many frames using cross correlation or sum of absolute differences (SAD) as soon as the initial template is found. Template tracking works well but the problem is finding the first initial obstacle template. The proposed method and system uses motion estimation based segmentation results as the initial template.
The template is updated from time to time by replacing the previous template by a template of the same size where it was detected. The template varies in size, depending on a distance to a vanishing point in blind spot detection applications. For convenience and better memory allocation, the template can be scaled to a fixed size. The search range of the cross correlation/sum of absolute differences is limited to a plausible range around the last detection and can include prediction. The proposed updating process reduces the "drifting" problem ("template update problem").
Additionally to the ability of tracking slowly moving vehicles in the backward direction, template tracking can furthermore augment or replace permanent motion estimation. A template that is once detected can be tracked well by template tracking; and motion estimation is only used if the tracking fails. The failure of the tracking can be detected if the correlation peak is below a certain (fixed or adaptive) threshold or if the template location jumps to other local maxima.
This approach improves the segmentation results, reduces the "shaking" of the segmentation and doesn't suffer from false alarms in vehicle detection process.
If motion estimation is still continuously used in parallel, template tracking can be used for cross verification. Comparing the motion estimation results with the template tracking results can reduce false alarms that occur during motion estimation. If these results match well, the template can be updated according to the motion estimation segmentation results. Otherwise a mismatch indicates problems and might result in rejecting the template.

Claims

Computer-implemented method for initializing a template for a moving object in a sequence of images, comprising:
partitioning (SI00) each of said images of said sequence into blocks;

identifying (SI02) moving blocks which have performed a movement between consecutive images of said sequence;

determining (S103) a direction and a distance of said movement of said moving blocks;

grouping (S104) adjacent moving blocks, for which directions within a predetermined direction interval and distances within a predetermined distance interval have been determined into a first group of blocks;

initializing (S106) a template for said moving object with said first group of blocks, wherein the template comprises the pixels assigned to the first group of blocks and the pixel values of said pixels describe an outer appearance of said moving object;

extending said sequence with further images;

calculating a correlation between said template and parts of said further images;

updating said template if said correlation is below a predetermined correlation threshold; and

tracking said template in said sequence of images,
wherein the step of updating said template includes steps of:
identifying moving blocks which have performed a movement between at least a part of said further images of said sequence;

determining a direction and a distance of said movement of said moving blocks;

grouping adjacent moving blocks, for which directions within a predetermined direction interval and distances within a predetermined distance interval have been determined into a second group of blocks; and

updating said template for said moving object with said second group of blocks.
Method according to the preceding claim, further comprising:
tracking (SI08) said template in said sequence based on an error criterion between said template and parts of said images.
Method according to claim 2, further comprising:
setting a search range around an area, where the object is expected in a subsequent image of said sequence according to its motion behavior in previous images of said sequence; and

performing said step of tracking in said search range in said subsequent image.
Method according to any one of the preceding claims, further comprising:
determining an average motion vector for a coherent group of blocks of said images;

determining a template motion vector for said template in subsequent images;

comparing said average motion vector with said template motion vector; and

rejecting said template in case of a mismatch between said average motion vector and said template motion vector.
Method according to any one of the preceding claims, further comprising:
pre-processing said images of said sequence with a global motion estimation and global motion compensation.
Method according to any of claims 1 to 5, wherein said method is used for detecting moving objects in a blind spot region of a vehicle, said moving objects moving backwards in said blind spot region with respect to a movement of said vehicle.
System (200) for initializing a template for a moving object in a sequence of images, comprising:
a local motion estimation unit (204) configured to partition each of said images of said sequence into blocks, to identify moving blocks which have moved between consecutive images of said sequence and to determine a direction and a distance of said movement of said moving blocks;

a segmentation unit (206) configured to initialize an initial template for said moving objects by grouping adjacent moving blocks, for which directions within a predetermined direction interval and distances within a predetermined distance interval have been determined, wherein the initial template comprises the pixels assigned to the first group of blocks and the pixel values of said pixels describe an outer appearance of said moving object;

a decision unit (300) configured to decide whether an update of said template should be performed, said decision unit (300) being connected to said local estimation unit (204); and a tracking unit (210) configured to track said template in said sequence of images.
System (200) according to claim 7, further comprising:
a global motion estimation unit (600) configured to perform a global motion estimation and global motion compensation of said images of said sequence.
Computer program product,
comprising a computer program code, which when loaded into a processor performs the method according to any of claims 1 to 6.