Occlusion/disocclusion detection using K-means clustering near object boundary with comparison of average motion of clusters to object and background motions

• US 7,142,600 B1
• Filed: 04/21/2003
• Issued: 11/28/2006
• Est. Priority Date: 01/11/2003
• Status: Expired

• Current Assignee: Intellectual Ventures I LLC (Intellectual Ventures LLC)
• Original Assignee: Neomagic Corporation
• Inventors: Raffy, Philippe, Hariharakrishnan, Karthik, Schonfeld, Dan, Yassa, Fathy
• Primary Examiner(s): DIEP, NHON THANH
• Application Number:
  US10/249,577
• Time in Patent Office: 1,317 Days
• Field of Search: None
• US Class Current: 375/240.16
• CPC Class Codes: G06T 7/215 Motion-based segmentation
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/57 Motion estimation characterised by a search window with variable size or shape
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

An object in a video sequence is tracked by object masks generated for frames in the sequence. Macroblocks are motion compensated to predict the new object mask. Large differences between the next frame and the current frame detect suspect regions that may be obscured in the next frame. The motion vectors in the object are clustered using a K-means algorithm. The cluster centroid motion vectors are compared to an average motion vector of each suspect region. When the motion differences are small, the suspect region is considered part of the object and removed from the object mask as an occlusion. Large differences between the prior frame and the current frame detect suspected newly-uncovered regions. The average motion vector of each suspect region is compared to cluster centroid motion vectors. When the motion differences are small, the suspect region is added to the object mask as a disocclusion.

Claims

1. An object tracker comprising:

a backward motion estimator, receiving a base object location in a base frame, for generating backward motion vectors representing displacements from regions in a current frame to best-matching regions in the base frame;

an object-location generator that generates a current object location for the current frame by including regions from the current frame that match best-matching regions in the base frame that are within the base object location and including sub-regions in the current frame matching best-matching sub-regions that are within the base object location;

a forward motion estimator, receiving the current object location in the current frame, for generating forward motion vectors representing displacements to best-matching regions in a second frame from the current frame;

an occlusion detector, receiving the forward motion vectors, the occlusion detector comprising;

a forward difference generator that finds a suspect covered region in the current frame and within the current object location, the suspect covered region not having a best-matching region in the second frame;

an object clusterer that divides regions in the current object location into a plurality of object clusters by minimizing variance of backward motion vectors of regions within an object cluster, each object cluster being represented by a centroid motion vector;

a motion-similarity comparator that compares an average motion vector for the suspect covered region to the centroid motion vector for each object cluster and signals an occlusion when a minimum difference between the average motion vector and the centroid motion vectors is less than an occlusion threshold; and

an occlusion remover that receives the current object location and removes the suspect covered region when the motion-similarity comparator signals the occlusion,

whereby suspect covered regions are removed as occluded regions when the motion-similarity comparator signals the occlusion.

2. The object tracker of claim 1 further comprising:

a disocclusion detector, receiving the centroid motion vectors from the object clusterer, and the backward and forward motion vectors, the disocclusion detector comprising;

a backward difference generator that finds a suspect uncovered region in the current frame and outside the current object location, the suspect uncovered region not having a best-matching region in the base frame;

a second motion-similarity comparator that compares an average motion vector for the suspect uncovered region to the centroid motion vector for each object cluster and signals a disocclusion when a minimum difference between the average motion vector and the centroid motion vectors is less than a disocclusion threshold; and

a disocclusion adder that adds the suspect uncovered region to the current object location when the motion-similarity comparator signals the disocclusion, whereby suspect uncovered regions are added to the current object location as disoccluded regions when the motion-similarity comparator signals the disocclusion.

3. The object tracker of claim 2 further comprising:

a motion averager, receiving backward motion vectors from the backward motion estimator for regions that match best-matching regions that are within the base object location in the base frame, for generating an average object motion from the backward motion vectors for regions matching best-matching regions that are within the base object location but excluding the backward motion vectors for regions matching best-matching regions that are outside the base object location or not entirely within the base object location when generating the average object motion; and

a motion modulator, receiving the average object motion from the motion averager, for comparing the average object motion to a motion threshold and adjusting a frame-skipping parameter to skip frames between the base frame and the current frame when the average object motion exceeds the motion threshold, but not skipping frames and processing sequential frames when the average object motion is below the motion threshold;

whereby frame skipping is modulated based on motion of regions matching within the base object location but not motion of regions matching outside or partially within the base object location.

4. The object tracker of claim 3 further comprising:

an adaptive region-size motion estimator, for sub-dividing regions in the base frame into sub-regions for regions matching best-matching regions that are partially within the base object location, for generating backward motion vectors representing displacements from sub-regions in the current frame to best-matching sub-regions in the base frame, whereby adaptive region-size matching along a boundary of the base object location in the base frame refines the current object location in the current frame.

5. The object tracker of claim 4 wherein the adaptive region-size motion estimator continues to sub-divide sub-regions into smaller sub-regions for sub-regions in the current frame best matching sub-regions in the base frame that are partially within the base object location,

whereby sub-regions along the boundary of the current object location are further sub-divided to more precisely refine the boundary of the current object location.

6. The object tracker of claim 2 wherein the regions are macroblocks but the suspect covered regions and suspect uncovered regions are not macroblocks but have irregular and varying shapes.

7. The object tracker of claim 2 wherein the object clusterer performs a K-means clustering routine that adaptively sets a number K of clusters to minimize variance.

8. A computer-implemented disocclusion method for detecting new regions to add to an object mask that predicts an object location in a frame of a video sequence of frames comprising:

motion compensating an object mask for a base frame using a current frame in the video sequence to generate a compensated current frame;

finding differences greater than a threshold value between the current frame and the compensated current frame, the differences being suspect regions;

motion compensating an object mask for the current frame using a second frame in the video sequence to generate a second compensated current frame;

calculating an average motion vector between the current frame and the second frame for each suspect region;

dividing the object mask for the current frame into a plurality of object clusters, each object cluster containing a plurality of macroblocks each having a block motion vector representing motion of the macroblock;

generating a cluster centroid motion vector for each object cluster, the cluster centroid motion vector being an average of the block motion vectors for macroblocks within each object cluster;

for each suspect region, comparing the average motion vector for the suspect region to the cluster centroid motion vector of each object cluster to obtain a motion difference; and

when the motion difference is below a threshold difference, adding the suspect region to the object mask as a disoccluded region;

whereby suspect regions with a small motion difference to a cluster centroid motion vector are added to the object mask during disocclusion processing.

9. The computer-implemented disocclusion method of claim 8 further comprising:

iterating allocation of macroblocks to object clusters using a K-means process to minimize variation of block motion vectors within object clusters,

whereby the object mask is divided by K-means clustering.

10. The computer-implemented disocclusion method of claim 8 further comprising:

enlarging the object mask to generate an enlarged object mask;

discarding suspect regions outside of the enlarged object mask,

whereby suspect regions far from the object mask are discarded.

11. The computer-implemented disocclusion method of claim 8 wherein the base frame is a frame prior to the current frame and the second frame is a frame after the current frame,

whereby backward and forward motion estimation are used to detect disocclusion.

12. The computer-implemented disocclusion method of claim 11 wherein the base frame and the current frame are separated by one or more skipped frames when motion is below a modulation threshold, but the base frame and the current frame are successive frames without an intervening frame when motion is above the modulation threshold;

wherein the second frame and the current frame are separated by one or more skipped frames when motion is below the modulation threshold, but the second frame and the current frame are successive frames without an intervening frame when motion is above the modulation threshold,

whereby processing is modulated wherein frames are skipped for low motion but not skipped for high motion.

13. The computer-implemented disocclusion method of claim 8 which further comprises occlusion processing which comprises:

motion compensating an object mask for the current frame using the second frame in the video sequence to generate the second compensated current frame;

finding differences greater than a threshold value between the current frame and the second compensated current frame, the differences within the object mask being suspect covered regions;

calculating an average motion vector between the current frame and the base frame for each suspect covered region;

for each suspect covered region, comparing the average motion vector for the suspect covered region to the cluster centroid motion vector of each object cluster to obtain a covered motion difference; and

when the covered motion difference is below a covered threshold difference, removing the suspect covered region from the object mask as an occluded region;

whereby suspect covered regions with a small motion difference to a cluster centroid motion vector are removed from the object mask during occlusion processing.

14. The computer-implemented disocclusion method of claim 13 further comprising:

removing smaller suspect regions and smaller suspect covered regions by filtering.

15. The computer-implemented disocclusion method of claim 13 further comprising:

searching for matching base regions in the base frame that approximately match with current regions in the current frame;

determining when a matching base region is entirely within an object contour of the base frame and categorizing a matching current region in the current frame as a certain region;

determining when the object contour passes through the matching base region of the base frame and categorizing a matching current region in the current frame as an uncertain region;

for uncertain regions in the current frame, sub-dividing the uncertain region into a plurality of sub-regions that are each smaller than the uncertain region;

searching for matching base sub-regions in the base frame that approximately match with current sub-regions in the current frame;

determining when a matching base sub-region is entirely within the object contour of the base frame and categorizing a matching current sub-region in the current frame as a certain sub-region;

determining when the object contour passes through the matching base sub-region of the base frame and categorizing a matching current sub-region in the current frame as an uncertain sub-region; and

generating a new object contour to include areas of certain regions and areas of certain sub-regions in the current frame,

whereby uncertain regions along an object boundary are sub-divided to refine the new object contour.

16. A computer-program product comprising:

a computer-usable medium having computer-readable program code means embodied therein for tracking an object boundary in a video stream, the computer-readable program code means in the computer-program product comprising;

first motion estimation means for generating motion vectors for blocks of pixels in a current frame relative to a base frame;

base-frame block-boundary compare means for comparing a location of a matching block in the base frame to an object boundary in the base frame;

new object boundary means, coupled to the base-frame block-boundary compare means, for generating a new object boundary for the current frame, the new object boundary being drawn to include blocks in the current frame that match blocks in the base frame within the object boundary;

second motion estimation means for generating motion vectors for blocks of pixels in the current frame relative to a second frame that is not the base frame;

first difference means, coupled to the second motion estimation means, for locating a suspected covered region of pixels in the current frame that do not match a corresponding region of pixels in the second frame;

cluster means, receiving the new object boundary, for iteratively assigning blocks within the new object boundary to one or more clusters within the new object boundary, by reducing variance of motion vectors of blocks within a cluster;

centroid means, coupled to the cluster means, for generating a centroid motion vector that is an average of motion vectors for blocks within a cluster;

compare means, receiving the centroid motion vector, for comparing a motion vector of the suspected covered region to the centroid motion vector to determine when a difference in motion is below a threshold;

removal means, activated by the compare means, for removing pixels within the suspected covered region from the new object boundary to generate an updated object boundary when the difference in motion is below the threshold; and

advancing frame means for advancing the video stream to select a next second frame, a next current frame, and a next base frame, the next base frame having an object boundary already computed but the next current frame not yet having an object boundary computed,

whereby suspected covered regions are examined by motion comparison.

17. The computer-program product of claim 16 wherein the computer-readable program code means comprises:

second difference means, coupled to the first motion estimation means, for locating a suspected uncovered region of pixels in the current frame that do not match a corresponding region of pixels in the base frame;

second compare means, receiving the centroid motion vector from the centroid means, for comparing a motion vector of the suspected uncovered region to the centroid motion vector to determine when a difference in motion is within a second threshold; and

adding means, activated by the second compare means, for adding pixels within the suspected uncovered region to the updated object boundary to generate a final object boundary when the difference in motion is within the second threshold,

whereby suspected uncovered regions are examined by motion comparison.

18. The computer-program product of claim 17 wherein the computer-readable program code means comprises:

block categorization means, coupled to the base-frame block-boundary compare means, for identifying a current block in the current frame that has a motion vector to a matching block in the base frame as;

(1) a certain block when the matching block is located completely within the object boundary in the base frame;

(2) an uncertain block when the matching block is located partially within the object boundary but partially outside the object boundary in the base frame.

19. The computer-program product of claim 18 wherein the computer-readable program code means comprises:

adaptive block-size match means, coupled to receive the uncertain blocks, for splitting an uncertain block into a plurality of sub-blocks in the current frame;

sub-block motion estimation means for generating motion vectors for the sub-blocks of pixels in the current frame relative to the base frame;

base-frame sub-block-boundary compare means for comparing a location of a matching sub-block in the base frame to the object boundary in the base frame;

sub-block categorization means, coupled to the base-frame sub-block-boundary compare means, for identifying a current sub-block in the current frame that has a motion vector to a matching sub-block in the base frame as an uncertain sub-block when the matching sub-block is located partially within the object boundary but partially outside the object boundary in the base frame;

whereby object boundaries are generated by categorizing matching blocks linked by motion vectors and by splitting uncertain blocks on the object boundary into smaller blocks.

20. The computer-program product of claim 18 wherein the computer-readable program code means comprises:

average motion means, coupled to the first motion estimation means, for generating an average motion by combining motion vectors for certain blocks but not including motion vectors for uncertain blocks or for sub-blocks; and

modulation means, coupled to receive the average motion from the average motion means, for causing the advancing frame means to select as a next current frame a next sequential frame after the base frame when the average motion exceeds a threshold, but for selecting as the next current frame a frame several frames separated from the base frame when the average motion does not exceeds the threshold,

whereby frame advancement is modulated based on average motion of the certain blocks.