Segmenting moving objects and determining their motion

• US 6,766,037 B1
• Filed: 10/01/1999
• Issued: 07/20/2004
• Est. Priority Date: 10/02/1998
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Le, Delphine Anh Dao, Lennon, Alison Joan, Hitter, Mathieu
• Primary Examiner(s): Patel, Jayanti K.
• Assistant Examiner(s): Tabatabai, Abolfazl
• Application Number:
  US09/410,735
• Time in Patent Office: 1,754 Days
• Field of Search: 382/103, 382/107, 382/164, 382/171, 382/173, 382/177, 382/179, 382/199, 382/256, 382/268, 348/169, 348/170, 348/171, 348/172, 348/54, 348/55, 734/88
• US Class Current: 382/107
• CPC Class Codes: G06T 7/215 Motion-based segmentation
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds

Abstract

The method discloses a method of segmenting moving objects and determining their motion from video data. The method generates (104) a motion vector field by comparing the current frame of video data with the previous frame, where a motion vector is determined for each pixel of the current frame. The method then generates (106) a motion parameter field by sliding a window over the motion vector field of the current frame, and determining a set of motion parameters for each pixel based on a motion model of the motion vector field. The method then distributes (108) seeds throughout the motion parameter field so that fewer seeds are allocated to those areas of the motion parameter field having homogeneous motion parameter sets. The method then grows (110) regions from said seeds so as to segment the motion parameter field into a number of regions. The method considers a number of pixels that border the growing regions and the pixel that has a motion vector that is most similar to the motion parameter field of a region it borders is appended to that region. The method then updates the set of motion parameters of the appended region. The method continues until there are no more pixels bordering the growing regions.

Claims

1. A method of segmenting moving objects and determining their motion from video image data, wherein said method comprises the steps of:

distributing seeds in areas of a current frame of video data as a function of motion of pixels of the current frame as compared to a previous frame, wherein fewer seeds are allocated to those areas of the current frame having homogeneous motion; and

growing regions from the seeds so as to segment the current frame into a number of objects, wherein a number of pixels that border the growing regions are considered and that pixel of the number having a motion that is most similar to a motion of a region it borders is appended to that region and the motion of the region that includes the appended pixel is updated and said growing step is repeated until no pixels bordering the growing regions are available.

2. A method as claimed in claim 1, wherein said distribution step comprises the sub-steps of:

dividing the current frame into a plurality of areas;

allocating, for each divided area, one or more seeds as a function of a difference in the motion of the pixels within the area and the size of the divided area as compared to the size of the current frame; and

storing the locations of each allocated seed.

3. A method as claimed in claim 1, wherein said growing step comprises the sub-steps of:

generating a list of pixels and corresponding motions that border the growing regions;

scanning a number of the listed pixels in a predetermined manner;

determining a value, for each scanned pixel, indicative of the similarity of the corresponding motion of the pixel and the corresponding motion of a growing region that the pixel borders;

selecting a pixel that has a minimum value;

appending the selected pixel to the region bordered by the selected pixel;

updating the motion of the region that includes the appended pixel; and

repeating the sub-steps of said growing step until the current frame is segmented.

4. A method as claimed in claim 3, wherein said selection step selects the first scanned pixel of the list having a value below a minimum threshold.

5. A method as claimed in claim 3, wherein said selection step selects one of the pixels of the list having a value which is the minimum of all the pixels of the list.

6. A method as claimed in claim 1, wherein the method further comprises a step of merging the grown regions which have similarities.

7. A method of segmenting moving objects and determining their motion from video image data, wherein said method comprises the steps of:

comparing a current frame with a preceding frame of the video image data to compute a motion parameter field having a plurality of sets of motion parameters, wherein each pixel of the current frame has a corresponding set of motion parameters;

distributing seeds in areas of the motion parameter field as a function of the motion parameter sets within those areas, wherein fewer seeds are allocated to those areas of the motion parameter field having homogeneous motion parameter sets; and

growing regions from the seeds so as to segment the current frame into a number of objects, wherein a number of pixels that border the growing regions are considered and that pixel of the number having a set of motion parameters that is most similar to a set of motion parameters of a region it borders is appended to that region and the set of motion parameters of the region that includes the appended pixel is updated and said growing step is repeated until no pixels bordering the growing regions are available.

8. A method as claimed in claim 7, wherein said comparing step comprises the sub-steps of:

comparing the current frame with a preceding frame of the video image data to compute a motion vector field having a plurality of motion vectors, wherein each pixel of the current frame has a corresponding motion vector; and

sliding a window block over the motion vector field and generating a set of motion parameters for each pixel, wherein the motion parameters are based on a motion model of the motion vector field.

9. A method as claimed in claim 7, wherein said distribution step comprises the sub-steps of:

dividing the current frame into a plurality of areas;

allocating, for each divided area, one or more seeds as a function of a difference between the sets of motion parameters within the area and the size of the divided area as compared to the size of the current frame; and

storing the locations of each allocated seed.

10. A method as claimed in claim 7, wherein said distribution step comprises the sub-steps of:

selecting the current frame or a previously divided area of the current frame as the current area;

seeding the center of the current area when a difference between sets of motion parameters within the current area is less than a first predetermined threshold;

subdividing the current area when the size of the current area is greater than a second predetermined threshold and the difference is greater than or equal to the first predetermined threshold;

uniformly seeding the current area in a low density manner when the size of the area is less than or equal to the second predetermined threshold and the difference is greater than or equal to the first predetermined threshold and less than a third predetermined threshold;

subdividing the current area when the size of the area is greater than a fourth predetermined threshold and less than or equal to the second predetermined threshold and the difference is greater than or equal to the third predetermined threshold;

uniformly seeding the current area in a high density manner when the size of the area is less than or equal to the fourth predetermined threshold and the difference is greater than or equal to the third predetermined threshold; and

repeating the sub-steps of the said distribution step until all of the divided areas are seeded.

11. A method as claimed in claim 10, wherein said subdividing steps comprise subdividing the current area into four sub-areas.

12. A method as claimed in claim 10, wherein the difference is determined in accordance with the formula:

$\mathrm{difference}=\underset{0}{\overset{t=5}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>w_t<br><br>\text{\hspace{1em}<br><br>}<br><br>{\left(\min <br><br>\text{\hspace{1em}<br><br>}<br><br>\left({\mathrm{\alpha <br><br>}}_t\right)-\max <br><br>\text{\hspace{1em}<br><br>}<br><br>\left({\mathrm{\alpha <br><br>}}_t\right)\right)}^2$

where $w_t=\frac{1}{{\mathrm{\sigma <br><br>}}_t^2}$

and σ

_t² is the variance of the motion parameters α

_t within the designated area.

13. A method as claimed in claim 7, wherein said distribution step comprises the sub-steps of:

separating the motion parameter field of the current frame into a plurality of motion maps, wherein each motion map comprises motion parameters of the same type;

performing the following sub-steps for each motion map;

dividing the motion map into a plurality of areas; and

allocating, for each divided area, one or more seeds as a function of a difference between the maximum motion parameter and minimum motion parameter of the motion map within the divided area and the size of the divided area as compared to the size of the motion map; and

storing the locations of the allocated seeds of all motion maps in one list.

14. A method as claimed in claim 7, wherein said distribution step comprises a first sub-step of:

separating the motion parameter field of the current frame into a plurality of motion maps, wherein each motion map comprises motion parameters of the same type; and

said distribution step further comprises performing the following second sub-steps for each motion map;

selecting the motion map or a previously divided area of the motion map as the current area;

seeding the center of the current area when the difference between a maximum motion parameter and a minimum motion parameter within the current area is less than a first predetermined threshold;

subdividing the current area when the size of the current area is greater than a second predetermined threshold and the difference is greater than or equal to the first predetermined threshold;

uniformly seeding the current area in a low density manner when the size of the area is less than or equal to the second predetermined threshold and the difference is greater than or equal to the first predetermined threshold and less than a third predetermined threshold;

subdividing the current area when the size of the area is greater than a fourth predetermined threshold and less than or equal to the second predetermined threshold and the difference is greater than or equal to the third predetermined threshold;

uniformly seeding the current area in a high density manner when the size of the area is less than or equal to a the fourth predetermined threshold and the difference is greater than or equal to the third predetermined threshold; and

repeating the sub-steps of the said distribution step until all of the divided areas are seeded.

15. A method as claimed in claim 14, wherein said subdividing steps comprise subdividing the current area into four sub-areas.

16. A method as claimed in claim 7, wherein said growing step comprises the sub-steps of:

generating a list of pixels and corresponding set of motion parameters that border the growing regions;

scanning a number of the listed pixels in a predetermined manner;

determining a value, for each scanned pixel, indicative of the similarity of the corresponding set of motion parameters of the scanned pixel and the corresponding set of motion parameters of a growing region that the scanned pixel borders;

selecting a pixel that has a corresponding minimum value;

appending the selected pixel to the region bordered by the selected pixel;

updating the set of motion parameters of the region that includes the appended pixel; and

repeating the sub-steps of said growing step until the current frame is segmented.

17. A method as claimed in claim 16, wherein said selection step selects the first scanned pixel having a value below a minimum threshold.

18. A method as claimed in claim 16, wherein said selection step selects one of the pixels of the list having a value which is the minimum of all the pixels of the list.

19. A method as claimed in claim 7, wherein the method further comprises a step of merging the grown regions which have similarities.

20. A method as claimed in claim 19, wherein said merging step comprises the sub-steps of:

determining for each pair of neighboring grown regions a clique function value representative of the similarity of motion of the pair of neighboring grown regions;

selecting the pair of grown regions with the smallest clique function value;

merging both sat selected regions to produce a merged region and updating the merged region'"'"'s clique functions with neighboring regions, if the smallest clique function value is less than a predetermined threshold;

repeating the sub-steps of said merging step until the smallest clique function value is greater than or equal to the threshold.

21. A method of segmenting moving objects and determining their motion from video image data, wherein said method comprises the steps of:

(a) comparing a current frame with a preceding frame of the video image data to compute a motion vector field having a plurality of motion vectors, wherein each pixel of the current frame has a corresponding motion vector;

(b) sliding window blocks over the motion vector field and generating a motion parameter field, wherein each pixel of the current frame has a corresponding set of motion parameters and the sets of motion parameters are based on a motion model of the motion vectors;

(c) allocating pixels as seeds in areas of the current image as a function of the corresponding motion parameter sets within those areas, wherein fewer seeds are allocated to those areas of the current frame having homogeneous motion parameter sets and wherein the seeds form growing regions;

(d) generating a list of pixels and corresponding sets of motion parameters that border the growing regions;

(e) scanning a number of the pixels of the list;

(f) determining, for each scanned pixel, a value indicative of the similarity of the corresponding set of motion parameters of the scanned pixel and the corresponding set of motion parameters of a growing region that the scanned pixel borders;

(g) selecting a pixel that has a minimum value;

(h) appending the selected pixel to the growing region bordered by the selected pixel;

(i) updating the set of motion parameters of the region that includes the appended pixel;

(j) repeating said steps (d) to (i) until there are no more pixels that border the growing regions; and

(k) merging neighboring grown regions to produce a merged region if their similarity is less than a predetermined threshold, wherein the merged regions represent the moving objects and their corresponding sets of motion parameters represent their motion.

22. An apparatus for segmenting moving objects and determining their motion from video image data, wherein said apparatus comprises:

means for distributing seeds in areas of a current frame of video data as a function of motion of pixels of the current frame as compared to a previous frame, wherein fewer seeds are allocated to those areas of the current frame having homogeneous motion; and

means for growing regions from the seeds so as to segment the current frame into a number of objects, wherein a number of pixels that border the growing regions are considered and that pixel of the number having a motion that is most similar to a motion of a region it borders is appended to that region and the motion of the region that includes the appended pixel is updated and said means for growing regions is repeatedly applied until no pixels bordering the growing regions are available.

23. An apparatus for segmenting moving objects and determining their motion from video image data, wherein said apparatus comprises:

means for comparing a current frame with a preceding frame of the video image data to compute a motion parameter field having a plurality of sets of motion parameters, wherein each pixel of the current frame has a corresponding set of motion parameters;

means for distributing seeds in areas of the motion parameter field as a function of the motion parameter sets within those areas, wherein fewer seeds are allocated to those areas of the motion parameter field having homogeneous motion parameter sets; and

means for growing regions from the seeds so as to segment the current frame into a number of objects, wherein a number of pixels that border the growing regions are considered and that pixel of the number having a set of motion parameters that is most similar to a set of motion parameters of a region it borders is appended to that region and the set of motion parameters of the region that includes the appended pixel is updated and said means for growing regions is repeatedly applied until no pixels bordering the growing regions are available.

24. An apparatus for segmenting moving objects and determining their motion from video image data, wherein said apparatus comprises:

means for comparing a current frame with a preceding frame of the video image data to compute a motion vector field having a plurality of motion vectors, wherein each pixel of the current frame has a corresponding motion vector;

means for sliding window blocks over the motion vector field and generating a motion parameter field, wherein each pixel of the current frame has a corresponding set of motion parameters and the sets of motion parameters are based on a motion model of the motion vectors;

means for allocating pixels as seeds in areas of the current frame as a function of the corresponding motion parameter sets within those areas, wherein fewer seeds are allocated to those areas of the current image having homogeneous motion parameter sets and wherein the seeds form growing regions;

means for generating a list of pixels and corresponding sets of motion parameters that border the growing regions;

means for scanning a number of the pixels of the list;

means for determining, for each scanned pixel, a value indicative of the similarity of the corresponding set of motion parameters of the scanned pixel and the corresponding set of motion parameters of a growing region that the scanned pixel borders;

means for selecting a pixel that has a minimum value;

means for appending selected pixel to the growing region bordered by the selected pixel;

means for updating the set of motion parameters of the region that includes the appended pixel;

means for repeating the operations of said generating means, scanning means, determining means, selecting means, appending means, and updating means until there are no more pixels that border the growing regions; and

means for merging neighboring grown regions to produce a merged region if their similarity is less than a predetermined threshold, wherein the merged regions represent moving objects and their corresponding sets of motion parameters represent their motion.

25. A computer program product including a computer readable medium having recorded thereon a computer program for segmenting moving objects and determining their motion from video image data, wherein said computer program product comprises:

code for distributing seeds in areas of a current frame of video data as a function of motion of pixels of the current frame as compared to a previous frame, wherein fewer seeds are allocated to those areas of the current frame having homogeneous motion; and

code for growing regions from the seeds so as to segment the current frame into a number of objects, wherein a number of pixels that border the growing regions are considered and that pixel of the number having a motion that is most similar to a motion of a region it borders is appended to that region and the motion of the region that includes the appended pixel is updated and said code for growing regions is repeatedly applied until no pixels bordering the growing regions are available.

26. A computer program product including a computer readable medium having recorded thereon a computer program for segmenting moving objects and determining their motion from video image data, wherein said computer program product comprises:

code for comparing a current frame with a preceding frame of the video image data to compute a motion parameter field having a plurality of sets of motion parameters, wherein each pixel of the current frame has a corresponding said set of motion parameters;

code for distributing seeds in areas of the motion parameter field as a function of the motion parameter sets within those areas, wherein fewer seeds are allocated to those areas of the motion parameter field having homogeneous motion parameter sets; and

code for growing regions from the seeds so as to segment the current frame into a number of objects, wherein a number of pixels that border the growing regions are considered and that pixel of the number having a set of motion parameters that is most similar to a set of motion parameters of a region it borders is appended to that region and the set of motion parameters of the region that includes the appended pixel is updated and said code for growing regions is repeatedly applied until no pixels bordering the growing regions are available.

27. A computer program product including a computer readable medium having recorded thereon a computer program for segmenting moving objects and determining their motion from video image data, wherein said computer program product comprises:

code for comparing a current frame with a preceding frame of the video image data to compute a motion vector field having a plurality of motion vectors, wherein each pixel of the current frame has a corresponding motion vector;

code for sliding window blocks over the motion vector field and generating a motion parameter field, wherein each pixel of the current frame has a corresponding set of motion parameters and the sets of motion parameters are based on a motion model of the motion vectors;

code for allocating pixels as seeds in areas of the current frame as a function of the corresponding motion parameter sets within those areas, wherein fewer seeds are allocated to those areas of the current image having homogeneous motion parameter sets and wherein the seeds form growing regions;

code for generating a list of pixels and corresponding sets of motion parameters that border the growing regions;

code for scanning a number of the pixels of the list;

code for determining, for each scanned pixel, a value indicative of the similarity of the corresponding set of motion parameters of the scanned pixel and the corresponding set of motion parameters of a growing region that the scanned pixel borders;

code for selecting a pixel that has a minimum value;

code for appending the selected pixel to the growing region bordered by the selected pixel;

code for updating the set of motion parameters of the region that includes the appended pixel;

code for repeating the operations of said generating code, scanning code, determining code, selecting code, appending code, and updating code until there are no more pixels that border the growing regions; and

code for merging neighboring grown regions to produce a merged region if their similarity is less than a predetermined threshold, wherein

the merged regions represent the moving objects and their corresponding sets of motion parameters represent their motion.