US 7,095,786 B1Granted

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

AssigneeNeo Magic Corp.

InventorsDan Schonfeld, Karthik Hariharakrishnan, Philippe Raffy, Fathy Yassa

Life of this patent

Estimating the term…

Loading patent…

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.

Claims19

Dependent claims

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.

4 more elements

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.

7 more elements

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.

11 more elements

Dependencies are inferred from the claim text.