Rule-based moving object segmentation

• US 6,337,917 B1
• Filed: 06/21/1999
• Issued: 01/08/2002
• Est. Priority Date: 01/29/1997
• Status: Expired due to Term

• Current Assignee: Abdullah Aydin Alatan, Ertem Tuncel, Levent Onural
• Original Assignee: Abdullah Aydin Alatan, Ertem Tuncel, Levent Onural
• Inventors: Onural, Levent, Tuncel, Ertem, Alatan, Abdullah Aydin
• Primary Examiner(s): Bella, Matthew C.
• Application Number:
  US09/337,591
• Time in Patent Office: 932 Days
• Field of Search: 382/103, 382/107, 382/162, 382/164, 382/165, 382/173, 382/205, 382/283
• US Class Current: 382/107
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51
• CPC Class Codes: H04N 19/20 using video object coding

Abstract

A rule-based method which detects and tracks the moving objects in video frames in an automated way is invented. The method can be used in object based image sequence compression applications. Motion of pixels between two consecutive frames are estimated using a block based motion estimation method, and the resultant dense motion vector field is segmented. Using the same method, a second segmentation is achieved based on partitioning of the image according to color values of the pixels. The image, which is formed by the translation of the final segmentation results of the previous frame using the estimated motion vectors, is used as the third segmentation. By the help of a sequence of rules, which uses the three different segmentation masks as its inputs, detection and tracking of moving objects in the scene is achieved within accurate boundaries; the problems caused by occlusion or uncovered background are insignificant.

Claims

1. A method of detecting, segmenting and tracking moving objects in an image sequence, comprising,

a) obtaining a color segmentation mask by segmenting a given frame at a reference instant to regions using color information of that frame, and assigning a distinct region number to each region resulting from this segmentation;

b) estimating motion between a video frame at a reference instant and a preceding saved video frame at a previous instant;

c) obtaining a motion segmentation mask by segmenting this estimated motion information, and assigning a distinct region number to each region resulting from this segmentation;

d) predicting a final segmentation mask at the reference instant by translating, using the estimated motion information, the previously obtained and saved final segmentation mask, and assigning a distinct region number to each region of the predicted final segmentation mask by copying the corresponding region numbers from the previous final segmentation mask;

e) creating a composite segmentation mask, by merging, via a sequence of rules, the color segmentation mask, the motion segmentation mask and the segmentation mask obtained by translating the previous final segmentation mask;

f) creating current final segmentation mask by post-processing the regions in the composite segmentation mask.

2. The method in claim 1 in which the assignment of a second number, in addition to the region number, to each region of the color segmentation mask of claim 1 step a) is done by using the region numbers of the motion segmentation mask of claim 1 step c).

3. The method in claim 2 in which the second numbers are found by a method comprising,

a) aligning the color segmentation mask and the motion segmentation mask,

b) finding the intersections of a selected region on the color segmentation mask and each one of the regions on the motion segmentation mask after the alignment in step a),

c) finding the intersection whose area is the largest among the intersections of step b),

d) finding the region number of the motion segmentation mask region which corresponds to the intersection found in step c), and assigning this number as the second number of the selected region in step b),

e) assigning a second number to all the regions on the color segmentation mask by repeating the steps in steps b), c) and d) for each one of these regions.

4. The method in claim 1 in which a third number, in addition to the previously assigned two numbers, is assigned to each region of the color segmentation mask by using the region numbers of the regions on the segmentation mask which is obtained by translating the previous final segmentation mask.

6. The method in claim 1 in which each region of the motion segmentation mask claimed in claim 1 step c) is labeled as a moving region if the average of all the motion vectors included in this region exceeds a given threshold;

otherwise, it is labeled as a stationary region.

7. The method in claim 1 in which each region on the previously obtained final segmentation mask claimed in claim 1 step d) is labeled as either moving or stationary by copying the label of the corresponding region in the previously obtained final segmentation mask.

8. The method in claim 1 in which the composite mask claimed in claim 1 step e) is obtained through a sequence of rules comprising,

a) grouping of the color segmentation mask regions whose third numbers are the same;

carrying this group of regions as a single region into the composite segmentation mask by labeling this single region as a moving region if all the regions on the translated previous segmentation mask corresponding to the common third number are labeled as moving regions, and if all the regions on the motion segmentation mask corresponding to the second numbers of the regions in the group are also labeled as moving regions;

assigning the common third number of the color segmentation mask regions as the region number of this single region on the composite segmentation mask,

b) grouping of the color segmentation mask regions whose third numbers are the same;

carrying this group of regions as a single region into the composite segmentation mask by labeling this single region as a stationary region if all the regions on the translated previous segmentation mask corresponding to the common third number are labeled as stationary regions, and if all the regions on the motion segmentation mask corresponding to the second numbers of the regions in the group are also labeled as stationary regions;

assigning the common third number of the color segmentation mask regions as the region number of this single region on the composite segmentation mask,

c) grouping of the color segmentation mask regions whose third numbers are the same;

carrying this group of regions as a single region into the composite segmentation mask by labeling this single region as a moving region if all the regions on the translated previous segmentation mask corresponding to the common third number are labeled as stationary regions, and if all the regions on the motion segmentation mask corresponding to the second numbers of the regions in the group are labeled as moving regions;

assigning the common third number of the color segmentation mask regions as the region number of this single region on the composite segmentation mask,

d) grouping of the color segmentation mask regions whose third numbers are the same;

carrying this group of regions as a single region into the composite segmentation mask by labeling this single region as a stationary region if all the regions on the translated previous segmentation mask corresponding to the common third number are labeled as moving regions, and if all the regions on the motion segmentation mask corresponding to the second numbers of the regions in the group are labeled as stationary regions;

assigning the common third number of the color segmentation mask regions as the region number of this single region on the composite segmentation masks,

e) grouping of the color segmentation mask regions whose third numbers are the same;

splitting this group into two parts and carrying these two parts into the composite segmentation mask if all the regions on the translated previous segmentation mask corresponding to the common third number are labeled as moving regions, but not all the regions on the motion segmentation mask corresponding to the second numbers of the regions in the group are labeled as moving regions;

labeling these two regions by copying the labels from the regions in the motion segmentation mask corresponding to their second numbers;

assigning the common third number of the group as the region number of the larger of the two regions and assigning a new region number to the smaller one,

f) grouping of the color segmentation mask regions whose third numbers are the same;

splitting this group into multiple parts and carrying these multiple parts into the composite segmentation mask if all the regions on the translated previous segmentation mask corresponding to the common third number are labeled as stationary regions, but not all the regions on the motion segmentation mask corresponding to the second numbers of the regions in the group are labeled as stationary regions;

labeling these regions by copying the labels from the regions in the motion segmentation mask corresponding to their second numbers;

assigning the common third number of the group as the region number of the largest of these regions and assigning a new region number to the other ones.

9. The method in claim 1 in which the post-processing claimed in claim 1 step f) carries the regions of the composite mask, together with their labels and numbers, to the final segmentation mask.

10. The post-processing in claim 9 in which if the size of a region in the composite segmentation mask is smaller than a threshold, then the region number of this region is altered by copying the region number of its largest size neighbor region having the same type of label as this small region;

then the region is carried to the final segmentation mask.

11. The post-processing in claim 9 in which if the size of a region in the composite segmentation mask is larger than a threshold, and if it is labeled as a moving region, then the region number of this region is altered by copying the region number of its largest size neighbor region having the moving region label;

then the region is carried to the final segmentation mask.

5. The method claimed in 4, where the assignment of the third number is done by,

a) aligning the color segmentation mask and the translated previous final segmentation mask;

b) finding the intersections, of a selected region on the color segmentation mask and each one of the regions on the segmentation mask which is obtained by translating the previously obtained final segmentation mask, after the alignment claimed in step a),

c) finding the intersection whose area is the largest area among the intersections claimed in step b),

d) finding the region number of the translated previously obtained final mask region which corresponds to the intersection found in step c), and assigning this number as the third number of the selected region in step b),

e) the assignment of a third number to all the regions on the color segmentation mask by repeating the steps in steps b), c) and d) for each one of these regions.