Object tracking using adaptive block-size matching along object boundary and frame-skipping when object motion is low

• US 7,095,786 B1
• Filed: 01/11/2003
• Issued: 08/22/2006
• Est. Priority Date: 01/11/2003
• Status: Expired due to Fees

• Current Assignee: Intellectual Ventures I LLC (Intellectual Ventures LLC)
• Original Assignee: NEO Magic Corporation
• Inventors: Raffy, Philippe, Hariharakrishnan, Karthik, Schonfeld, Dan, Yassa, Fathy
• Primary Examiner(s): PHILIPPE, GIMS S
• Application Number:
  US10/248,348
• Time in Patent Office: 1,319 Days
• Field of Search: 375/240.08, 375/240.09, 375/240.24, 375/240.16, 382/236, 382/300, 382/190, 382/243, 382/242, 382/256, 382/234
• 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 of frames is tracked by object masks generated for frames in the sequence. Macroblocks are motion compensated. Blocks matching entirely within a prior-frame object mask are used to generate an average object motion. When the average motion is below a motion threshold, frames are skipped at larger intervals, but more frequent frames are processed when high motion occurs. When the macroblock best matches a prior-frame block that has the object'"'"'s boundary passing through the block, the macroblock is uncertain and is sub-divided into smaller sub-blocks that are again motion compensated. Sub-blocks matching blocks within the object mask in the base frame are added to the new object mask for the current frame while sub-blocks matching a block containing the object boundary are uncertain and can again be sub-divided to further refine the object boundary. Frame skipping and adaptive-size blocks on the object boundary reduce computational load.

Claims

1. An object tracker comprising:

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

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

a motion thresholder, 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;

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 object location, for generating motion vectors representing displacements from sub-regions in the current frame to best-matching sub-regions in the base frame; and

an object-location generator, coupled to the adaptive region-size motion estimator, for generating a current object location for the current frame by including regions matching best-matching regions that are within the object location and including sub-regions matching best-matching sub-regions that are within the object location,

whereby frame skipping is modulated based on motion of regions matching within the object location and whereby adaptive region-size matching along a boundary of the object location in the base frame refines the object location in the current frame.

2. The object tracker of claim 1 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 object location,

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

3. The object tracker of claim 2 further comprising:

a gradient calculator for generating a gradient within a sub-region and for comparing the gradient to a gradient threshold, the gradient calculator preventing the adaptive region-size motion estimator from further sub-dividing a sub-region when the gradient of the sub-region is below the gradient threshold,

whereby sub-dividing of low-gradient sub-regions is halted.

4. The object tracker of claim 3 wherein the gradient is generated from a luminance value or chrominance values of pixels within the sub-region, the gradient being a maximum difference or an average or a variance or a standard deviation of the luminance value or the chrominance values or both luminance and chrominance values.

5. The object tracker of claim 4 further comprising:

a contour copier, coupled to the adaptive region-size motion estimator, for copying a boundary of the object location to a sub-region in the current frame that best matches a sub-region in the base frame that includes the boundary of the object location in the base frame;

wherein the object-location generator includes the boundary copied for sub-regions that best match sub-regions falling along the boundary of the object location.

6. The object tracker of claim 1 wherein the regions are blocks of pixels or triangular regions of pixels, and wherein each regions is sub-divided into at least four sub-regions.

7. The object tracker of claim 1 wherein the regions are macroblocks each having 16 by 16 pixels.

8. A computer-implemented method for generating a new object contour in a current frame of a video from a base frame in the video 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 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 the new object contour to include areas of certain regions and areas of certain sub-regions in the current frame,

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

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

for uncertain sub-regions,

reading boundary information that indicates a precise location of the object contour within a matching base sub-region;

copying the boundary information from the matching base sub-region to the matching current sub-region, and

using the boundary information copied to the matching current sub-region to refine the new object contour,

whereby boundary information copied for uncertain sub-regions refines the new object contour.

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

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

whereby sub-regions are sub-divided until the minimum sub-region size is reached.

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

generating a gradient for a sub-region from pixel values within the sub-region;

comparing the gradient to a gradient threshold; and

when the gradient does not meet the gradient threshold, halting sub-dividing of the sub-region,

whereby sub-regions with insufficient pixel gradients are not sub-divided.

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

for all certain regions, generating a motion vector representing a relative difference in locations of the matching current region and the matching base region;

combining motion vectors for all certain regions to generate an average motion vector;

comparing the average motion vector to a motion threshold; and

reducing a number of frames skipped between the base frame and the current frame when the average motion vector exceeds the motion threshold and repeating searching for matching base regions for a new current frame that is closer to the base frame,

whereby a number of frames between the base frame and the current frame is modulated for different pairs of base and current frames in a video sequence.

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

after the new object contour is generated, incrementing the base frame to the current frame and selecting a new current frame that is more than one frame ahead of a prior current frame;

wherein the computer-implemented method is repeated for a new base frame and the new current frame.

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

using an affine model to combine motion vectors for all certain regions to generate an average motion vector.

15. 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;

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;

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;

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;

new object boundary means, coupled to the sub-block categorization means, for generating a new object boundary for the current frame, the new object boundary being drawn through the uncertain sub-blocks to surround the certain blocks; and

advancing frame means for advancing the video stream to select 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 object boundaries are generated by categorizing matching blocks linked by motion vectors and by splitting uncertain blocks on the object boundary into smaller blocks.

16. The computer-program product of claim 15 wherein the motion estimation means generates motion vectors by searching for a best-fit matching block in the base frame that best matches pixels in the block in the current frame;

wherein the best-fit matching block searched for in a limited range of the base frame;

wherein the sub-block motion estimation means generates motion vectors by searching for a best-fit matching sub-block in the base frame that best matches pixels in the sub-block in the current frame;

wherein the best-fit matching sub-block searched for in a limited sub range of the base frame;

wherein the limited sub range is smaller than the limited range,

whereby motion estimation search ranges are reduced for sub-blocks.

17. The computer-program product of claim 16 wherein the blocks are arbitrarily-shaped regions of uniform size or are rectangular macroblocks or triangle-shaped regions.

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

average motion means, coupled to the 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.

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

segmentation means, coupled to the average motion means, for segmenting the base frame to determine the object boundary when the base frame is an initial frame in a video scene, or when the base frame and the current frame are sequential frames and the average motion still exceeds the threshold,

whereby segmentation to re-initialize the object boundary is performed for new video scenes or for large motions between sequential frames.