Mosaic generation and sprite-based coding with automatic foreground and background separation

• US 6,249,613 B1
• Filed: 03/31/1998
• Issued: 06/19/2001
• Est. Priority Date: 03/31/1997
• Status: Expired due to Term

• Current Assignee: Rakuten, Inc. (Rakuten Group, Inc.)
• Original Assignee: Sharp Laboratories of America Incorporated (Hon Hai Precision Industry Co., Ltd.)
• Inventors: Crinon, Regis J., Sezan, Muhammed Ibrahim
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Alavi, Amir
• Application Number:
  US09/052,870
• Time in Patent Office: 1,176 Days
• Field of Search: 382/232, 382/234, 382/233, 382/235, 382/236, 382/237, 382/238, 382/239, 382/240, 382/247, 382/248, 382/249
• US Class Current: 382/236
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/23 with coding of regions that are present throughout a whole video segment, e.g. sprites, background or mosaic
• CPC Class Codes: H04N 19/527 Global motion vector estimation
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

An automatic segmentation system distinguishes foreground and background objects by first encoding and decoding a first image at a first time reference. Macroblocks are extracted from a second image at a second time reference. The macroblocks are mapped to pixel arrays in the decoded first image. Frame residuals are derived that represent the difference between the macroblocks and the corresponding pixel arrays in the previously decoded image. A global vector representing camera motion between the first and second images is applied to the macroblocks in the second image. The global vectors map the macroblocks to a second pixel array in the first decoded image. Global residuals between the macroblocks and the second mapped image arrays in the first image are derived. When the global residuals are compared with the frame residuals to determine which macroblocks are classified as background and foreground. The macroblocks classified as foreground are then blended into a mosaic.

Claims

1. A method for automatically segmenting foreground and background objects in images, comprising:

encoding and decoding a first image at a first time reference;

extracting macroblocks from a second image at a second time reference;

mapping the macroblocks with corresponding arrays in the decoded first image according to a macroblock local vector;

deriving frame residuals between the macroblocks and the corresponding arrays;

mapping macroblocks to the first image according to a global motion model;

deriving global residuals between the macroblocks and the corresponding global motion compensated array in the first image;

tagging the macroblocks as a frame prediction type based on one local motion vector;

classifying the macroblocks as foreground or background by comparing the global residuals with the derived frame residuals;

classifying the macroblocks as foreground when the global residuals are greater than a function of the frame residuals;

classifying the macroblocks as background when the frame residuals are greater than some function of the global residuals;

updating the mosaic with macroblocks tagged as background;

creating a segmentation map that identifies the macroblocks in the second image as either foreground or background;

smoothing the segmentation map to remove extraneous foreground and background macroblocks in the segmentation map, wherein smoothing the segmentation map includes;

taking macroblock neighbors around a target macroblock in the segmentation map;

taking the segmentation map values for each of the macroblock neighbors and the target macroblock;

ranking the segmentation map values in increasing order; and

selecting the output of the target macroblock as the value of the ranked neighbor at a selected threshold;

updating the mosaic with the identified background macroblocks in the smoothed segmentation map;

forward warping the mosaic but not changing the contents of the mosaic when all of the following conditions occur;

pixel sample values in the macroblocks belong to a decoded video object plane;

the mosaic content is already determined at the pixel locations; and

the macroblock is labeled as foreground;

forward warping the mosaic and blending the pixel sample values into the mosaic when all of the following conditions occur;

pixels in the macroblock belong to the decoded video object plane;

the mosaic content is already determined at the pixel locations; and

the macroblock is labeled as background;

forward warping and updating the mosaic content with content of the pixel sample values in the decoded second image when all of the following conditions occur;

pixels in the macroblock belong to the decoded second image;

the mosaic content is undetermined at the pixel locations; and

the macroblock is labeled as background; and

initializing the mosaic by either inserting the first decoded image into the mosaic and then updating the mosaic in time only with macroblocks classified as background or setting a mosaic buffer to zero everywhere and then incrementally updating the mosaic in time only with macroblocks classified as background.

2. A method for automatically segmenting foreground and background objects in images, comprising:

encoding and decoding a first image at a first time reference;

extracting macroblocks from a second image at a second time reference;

mapping the macroblocks with corresponding arrays in the decoded first image according to a macroblock local vector;

deriving frame residuals between the macroblocks and the corresponding arrays;

mapping macroblocks to the first image according to a global motion;

deriving global residuals between the macroblocks and the corresponding global motion compensated array in the first image;

classifying the macroblocks as foreground or background by comparing the global residuals with the derived frame residuals; and

initializing a mosaic by inserting the first decoded image into the mosaic and then updating the mosaic in time only with macroblocks classified as background.

3. Computer code stored on a computer readable medium, comprising:

code to separate a frame into multiple macroblocks;

code to match the macroblocks with pixel arrays in a previously decoded frame according to local motion vectors and generating frame residuals associated with the macroblocks;

code to match the macroblocks with pixel arrays in the previously decoded frame according to frame global motion parameters to generate a global residual;

code to classify the frame prediction type macroblocks as either foreground or background by comparing the global residuals with the frame residuals; and

code to initialize a mosaic by either inserting the frame into the mosaic and then updating the mosaic in time only with macroblocks classified as background or setting a mosaic buffer to zero everywhere and then incrementally updating the mosaic in time only with macroblocks classified as background.

4. A decoder, comprising:

a macroblock detector detecting a tagged macroblock prediction type in an encoded bit stream;

a frame decoder reconstructing macroblocks tagged as a frame prediction type according to a previously decoded frame according to frame residuals;

a mosaic decoder reconstructing macroblocks tagged as a mosaic prediction type according to a mosaic;

a global decoder receiving global residuals for a current frame and classifying assembled frame prediction type macroblocks as foreground when global residuals are greater than a function of the macroblock frame residuals and otherwise classifying the assembled macroblocks as background; and

a mosaic updater to initialize the mosaic by either inserting a decoded frame into the mosaic and then updating the mosaic in time only with reconstructed macroblocks classified as background or sing a mosaic buffer to zero everywhere and then incrementally updating the mosaic in time only with macroblocks classified as background.

5. A decoder, comprising:

a macroblock detector detecting a tagged macroblock prediction type in an encoded bit stream;

a frame decoder reconstructing macroblocks tagged as a frame prediction type according to a previously decoded frame according to frame residuals;

a mosaic decoder reconstructing macroblocks tagged as a mosaic prediction type according to a mosaic;

a global decoder receiver global residuals for a current frame and classifying assembled frame prediction type macroblocks as foreground when global residuals are greater than a function of the macroblock frame residuals and otherwise classifying the assembled macroblocks as background;

a mosaic updater to initialize the mosaic by either inserting a decoded frame into the mosaic and then updating the mosaic in time only with reconstructed macroblocks classified as background or setting a mosaic buffer to zero everywhere and then incrementally updating the mosaic in time only with macroblocks classified as background;

wherein the macroblock decoder tags the macroblocks according to the following;

single local motion vector frame prediction type for the macroblocks having a single local motion vector;

multiple local motion vector frame prediction type for the macroblocks having multiple local motion vectors;

MOSAIC prediction type for the macroblocks predicted according to global motion parameters;

SKIP prediction type corresponding to a MOSAIC prediction type for which the residual signal is zero;

INTRA prediction type for the macroblocks not using any prediction; and

the macroblock encoder classifying multiple local motion vector and INTRA prediction types as foreground, and the MOSAIC and SKIP prediction types as background.

6. A method for automatically segmenting foreground and background objects in images, comprising:

encoding and decoding a first images at a first time reference;

extracting macroblocks from a second image at a second time reference;

mapping the macroblock with corresponding arrays in the decoded first image according to a macroblock local vector representing frame to frame dynamics of the objects in the images;

deriving frame residuals between the macroblocks and the corresponding arrays in the first image representing the difference between the macroblocks and corresponding arrays in the first image matched by the local vector;

mapping macroblocks to the first image according to a global motion induced by a system receiving the images;

deriving global residuals between the macroblocks and the corresponding global motion compensated array in the first image representing the difference between the macroblocks and corresponding arrays in the first image matched by the global motion;

tagging the macroblocks as different frame prediction types based on a particular type of local vector used for mapping the macroblocks to the first image;

classifying the macroblocks as foreground or background by comparing the global residuals with the derived frame residuals; and

updating a mosaic in time only with macroblocks classified as background.

7. An automatic segmentation system for mosaic based encoding, comprising:

a macroblock separator separating a frame into multiple macroblocks;

a frame predictor matching the macroblocks with pixel arrays in a previously decoded frame according to local motion vectors representing frame to frame dynamics of images in the frame and generating frame residuals associated with the macroblocks representing the difference between the macroblocks and the pixel arrays in the previously decoded frame matched by the local motion vectors;

a mosaic predictor matching the macroblocks with pixel arrays in a mosaic according to global motion parameters and generating residuals associated with the macroblocks;

a global motion predictor matching the macroblocks with pixel arrays in the previously decoded frame according to frame global motion parameters representing image movement induced by a system receiving the images and generating a global residual representing the difference between the macroblocks and the pixel arrays in the previously decoded frame matched by the global motion parameters;

a macroblock encoder tagging the macroblocks as mosaic prediction type when the mosaic residuals are used for encoding the macroblocks, and tagging the macroblocks as frame prediction type based on a local motion vector when the frame residuals are used for encoding the macroblocks, the macroblock encoder classifying the frame prediction type macroblocks as either foreground or background by comparing the global residuals with the frame residuals and classifying the mosaic prediction type as background; and

a mosaic updater that updates the mosaic in time only with macroblocks classified as background.