Occlusion/disocclusion detection using K-means clustering near object boundary with comparison of average motion of clusters to object and background motions
First Claim
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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
43 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
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. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15)
-
-
16. A computer-program product comprising:
-
a non-transitory 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. - View Dependent Claims (17, 18, 19, 20)
-
-
21. An object tracker comprising:
-
a first motion estimator configured to receive a base object location in a base frame and generate first motion vectors representing displacements from regions in a current frame to best-matching regions in the base frame; an object-location generator configured to generate 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; a second motion estimator configured to receive the current object location in the current frame and generate second motion vectors representing displacements to best-matching regions in a second frame from the current frame; an occlusion detector configured to receive the second motion vectors, the occlusion detector comprising; a first difference generator configured to find 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; a motion-similarity comparator configured to compare an average motion vector for the suspect covered region to a centroid motion vector for at least a portion of the current object location and signal an occlusion when a difference between the average motion vector and the centroid motion vector is less than an occlusion threshold; and an occlusion remover configured to receive the current object location and remove the suspect covered region when the motion-similarity comparator signals the occlusion. - View Dependent Claims (22, 23, 24, 25, 26, 27)
-
-
28. A computer-implemented disocclusion method comprising:
-
motion compensating an object mask for a base frame using a current frame in a video sequence of frames 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; generating a cluster centroid motion vector for at least a portion of an object location, the centroid motion vector comprising an average of a plurality of motion vectors associated with the object location; for each suspect region, comparing the average motion vector for the suspect region to the centroid motion vector to obtain a motion difference; and when the motion difference is below a threshold difference, adding the suspect region to the object mask. - View Dependent Claims (29, 30, 31, 32, 33, 34, 35)
-
-
36. A computer-program product comprising:
-
a non-transitory computer-usable medium having computer-readable program code embodied therein for tracking an object boundary in a video stream, the computer-readable program code comprising code that, when executed, causes a processor to; generate motion vectors for blocks of pixels in a current frame relative to a base frame; compare a location of a matching block in the base frame to an object boundary in the base frame; generate 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; generate motion vectors for blocks of pixels in the current frame relative to a second frame that is not the base frame; locate a suspected covered region of pixels in the current frame that do not match a corresponding region of pixels in the second frame; generate a centroid motion vector that is an average of a plurality of motion vectors associated with a respective plurality of blocks within the object location; compare a motion vector of the suspected covered region to the centroid motion vector to determine when a difference in motion is below a threshold; and remove 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. - View Dependent Claims (37, 38, 39, 40)
-
-
41. An object tracker comprising:
-
first motion estimation means for receiving a base object location in a base frame and generating first motion vectors representing displacements from regions in a current frame to best-matching regions in the base frame; object-location generating means for generating 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; second motion estimation means for receiving the current object location in the current frame and generating second motion vectors representing displacements to best-matching regions in a second frame from the current frame; occlusion detection means for receiving the second motion vectors, the occlusion detection means comprising; first difference generation means for finding 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; motion-similarity comparing means for comparing an average motion vector for the suspect covered region to a centroid motion vector for at least a portion of the current object location and signal an occlusion when a difference between the average motion vector and the centroid motion vector is less than an occlusion threshold; and occlusion removing means for receiving the current object location and removing the suspect covered region when the motion-similarity comparing means signals the occlusion.
-
-
42. A method for processing a video sequence comprising:
-
receiving the video sequence; coupling at least a portion of the video sequence to an object tracker configured to implement a disocclusion method, the disocclusion method 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; generating a cluster centroid motion vector for at least a portion of an object location, the centroid motion vector comprising an average of a plurality of motion vectors associated with the object location; for each suspect region, comparing the average motion vector for the suspect region to the centroid motion vector to obtain a motion difference; and when the motion difference is below a threshold difference, adding the suspect region to the object mask; and obtaining processed video sequence data from the object tracker. - View Dependent Claims (43)
-
Specification