Model-based video encoding and decoding

• US 9,578,345 B2
• Filed: 12/21/2012
• Issued: 02/21/2017
• Est. Priority Date: 03/31/2005
• Status: Active Grant

• Current Assignee: Euclid Discoveries LLC
• Original Assignee: Euclid Discoveries LLC
• Inventors: DeForest, Darin, Pace, Charles P., Lee, Nigel, Pizzorni, Renato
• Primary Examiner(s): Czekaj, Dave
• Assistant Examiner(s): Sullivan, Tyler W
• Application Number:
  US13/725,940
• Publication Number:
  US 20130107948A1
• Time in Patent Office: 1,523 Days
• US Class Current: 1/1
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/503 involving temporal prediction adaptive coding with adaptive selection between spatial and temporal predictive coding H04N19/107; adaptive coding with adaptive selection among a plurality of temporal predictive coding modes H04N19/109

Abstract

A model-based compression codec applies higher-level modeling to produce better predictions than can be found through conventional block-based motion estimation and compensation. Computer-vision-based feature and object detection algorithms identify regions of interest throughout the video datacube. The detected features and objects are modeled with a compact set of parameters, and similar feature/object instances are associated across frames. Associated features/objects are formed into tracks and related to specific blocks of video data to be encoded. The tracking information is used to produce model-based predictions for those blocks of data, enabling more efficient navigation of the prediction search space than is typically achievable through conventional motion estimation methods. A hybrid framework enables modeling of data at multiple fidelities and selects the appropriate level of modeling for each portion of video data.

Claims

1. A method of encoding video data, comprising:

encoding raw video data using a multiple fidelities encoder executed via at least one computer processor by;

encoding the raw video data at multiple levels of fidelities for a model-based compression, such that encodings are provided at the multiple levels of fidelities;

(A) a macroblock encoding level, (B) a macroblock as feature encoding level, (C) a feature encoding level, and (D) an object encoding level, wherein the (A) macroblock encoding level uses a block-based motion estimation and compensation (BBMEC) application to find predictions for each tile from a limited search space in previously decoded reference frames, the macroblock encoding level generating an H.264 macroblock encoding prediction for a target macroblock;

wherein the (B) macroblock as feature encoding level (i) uses a first BBMEC application identical to the macroblock encoding level to find a first prediction for the target macroblock from a most-recent reference frame, (ii) uses a second BBMEC application to find a second prediction for the first prediction by searching in a second-most-recent frame, (iii) creates a track for the target macroblock by applying BBMEC applications through progressively older frames, and (iv) generates a macroblock as feature encoding level prediction from among the resulting track instances for the target macroblock;

wherein the (C) feature encoding level detects and tracks features independent of the macroblock grid and associates a feature with an overlapping macroblock such that a corresponding feature track of a feature overlapping the target macroblock is used to navigate previously-decoded reference frames to find a better match (prediction) for the overlapping macroblock by using offsets between the target macroblock and respective feature track instances to generate an indirect prediction for the target macroblock; and

if multiple features overlap the target macroblock, of the multiple features, the feature with greatest overlap with the target macroblock is selected to model the target macroblock, and

wherein the (D) object encoding level detects and tracks objects (features that overlap at least portions of multiple macroblocks including the target macroblock), such that object tracks are used to navigate previously-decoded reference frames to find better matches (predictions) for all macroblocks overlapping the object by using offsets between the target macroblock and respective object track instances to generate an indirect prediction for the overlapping macroblocks, so that a single motion vector is calculated for all of the macroblocks associated with the object resulting in computation and encoding size savings, the better matches having the most encoding size savings;

comparing compression efficiency of the (A) macroblock encoding level, (B) macroblock as feature encoding level, (C) feature encoding level, and (D) object encoding level; and

selecting, based on the comparison of compression efficiency, which one of the encodings has the fewest number of bits;

(A) macroblock encoding level, (B) macroblock as feature encoding level, (C) feature encoding level, and (D) object encoding level.

2. The method of claim 1, wherein the multiple fidelities are examined sequentially.

3. The method of claim 1, further including determining the compression efficiency of the (A) macroblock encoding level by comparing the bit size of the H.264 macroblock encoding prediction to a threshold;

responding to a determination that the (A) macroblock encoding level is efficient by accepting the macroblock level H.264 encoding prediction as a suitable encoding for a target macroblock; and

if the H.264 macroblock encoding prediction is not determined to be efficient, examining the multiple fidelities in competition mode by comparing the compression efficiency of the (B) macroblock as feature encoding level, (C) feature encoding level, and (D) object encoding level.

4. The method of claim 3, wherein the competition mode further includes selecting one encoding level out of the multiple fidelities encoding levels of fidelities based on results from competition mode as a best prediction for a target macroblock, and the best prediction is integrated with the additional steps of residual calculation, transform, quantization, and entropy encoding to generate a best encoding for the target macroblock.

5. The method of claim 4, wherein selecting, based on the comparison of compression efficiency, which one of the encodings has the fewest number of bits further includes examining all the multiple fidelities encoding levels, the (A) macroblock encoding level, (B) macroblock as feature encoding level, (C) feature encoding level, and (D) object encoding level, together in “

competition”

to determine which prediction produces the smallest encoding for the target macroblock in terms of the fewest number of bits, such prediction then being declared the best prediction for the target macroblock.

6. The method of claim 5, wherein encoding costs for each prediction are determined by integrating the prediction with the additional steps of residual calculation, transform, quantization, and entropy encoding.

7. The method of claim 5, wherein the multiple fidelities encoding levels are examined sequentially, from simplest (macroblock encoding level) to most complex (object encoding level), in which if lower-level (simpler) predictions are deemed to be satisfactory, higher-level (more complex) predictions are not examined.

8. The method of claim 7, wherein comparing the compression efficiency further includes examining the macroblock encoding level first by generating a conventional (H.264) encoding for the target macroblock to determine whether the conventional encoding is efficient;

and, if the conventional encoding is deemed efficient, the macroblock encoding level is determined to have produced the best prediction for the target macroblock.

9. The method of claim 8, wherein selecting which one of the encodings has the fewest number of bits further includes determining that the conventional encoding of the target macroblock is efficient if the encoding size is less than a predetermined threshold and inefficient if the encoding size is greater than that threshold.

10. The method of claim 8, wherein selecting which one of the encodings has the fewest number of bits further includes determining that the conventional encoding of the target macroblock is efficient if the target macroblock is a skip macroblock.

11. The method of claim 1, wherein encoding data at multiple levels of fidelities for a model-based compression at the feature encoding level detects features using nonparametric feature detection algorithms such as SIFT or SURF that generate feature descriptor vectors that model the detected features and are used to track the features over multiple frames.

12. The method of claim 11, wherein encoding data at multiple levels of fidelities for a model-based compression generates multiple feature level predictions for evaluation in competition, each prediction comprising a tracker, a key prediction model, a key prediction sampling scheme, a subtiling scheme, a reconstruction algorithm, and a secondary prediction scheme.

13. The method of claim 12, wherein, if the secondary prediction exists as one of the multiple feature level predictions, a composite prediction may be generated that sums the primary (key) prediction and a weighted version of the secondary prediction, the composite prediction becoming another feature level entry into the competition.

14. A method for encoding video data, comprising:

encoding raw video data using a multiple fidelities encoder executed via at least one computer processor by;

encoding the raw video data at multiple levels of fidelities for a model-based compression, the multiple fidelities including at least the first three of a macroblock encoding level, a macroblock as feature encoding level, a feature encoding level, and an object encoding level,

wherein the macroblock encoding level uses a block-based motion estimation and compensation (BBMEC) application to find predictions for each tile from a limited search space in previously decoded reference frames, the macroblock encoding level modeling generating an H.264 macroblock encoding prediction for a target macroblock,

wherein the macroblock as feature encoding level (i) uses a first BBMEC application identical to the macroblock encoding level to find a first prediction for the target macroblock from a most-recent reference frame, (ii) uses a second BBMEC application to find a second prediction for the first prediction by searching in a second-most-recent frame, (iii) creates a track for the target macroblock by applying BBMEC applications through progressively older frames, and (iv) generates a prediction from among the resulting track instances;

wherein the feature encoding level detects and tracks-features independent of the macroblock grid and associates a feature with an overlapping macroblock such that a corresponding feature track (the track belong to the feature overlapping the macroblock) is used to navigate previously-decoded reference frames to find a better match (prediction) for the overlapping macroblock by using offsets between the macroblock and respective feature track instances to generate an indirect prediction for the target macroblock; and

where multiple features overlap the target macroblock, the feature with greatest overlap is selected to model the target macroblock, and

wherein the object encoding level detects and tracks objects (that overlap at least portions of multiple macroblocks) and associates an object with all overlapping macroblocks, such that object tracks are used to navigate previously-decoded reference frames to find better matches (predictions) for all macroblocks overlapping the object by using offsets between the target macroblock and respective object track instances to generate an indirect prediction for the overlapping macroblocks, so that a single motion vector is calculated for all of the macroblocks associated with the object resulting in computation and encoding size savings, the better matches having the most encoding size savings in terms of number of bits;

generating model-based predictions for the target macroblock from the multiple encoding levels of fidelities;

comparing compression efficiency of the multiple encoding levels of fidelities; and

determining, based on the comparison of the compression efficiencies, the best prediction for the target macroblock from among the multiple encoding levels of fidelities based on which of the model-based prediction from the multiple encoding levels of fidelities has the smallest encoding size in terms of the number of bits; and

integrating the best prediction with the additional steps of transform, quantization, and entropy encoding to produce a best encoding for the target macroblock.

15. A data processing system encoding video data, comprising:

a multiple fidelities encoder stored on a non-transitory medium, executed by at least one computer processor, that encodes raw video data at multiple encoding levels of fidelities for a model-based compression, the multiple encoding levels of fidelities including a macroblock encoding level, a macroblock as feature encoding level, a feature encoding level, and an object encoding level, the multiple encoding fidelities encoder to model the data using the multiple fidelities for model-based compression including;

the macroblock encoding level using a block-based motion estimation and compensation (BBMEC) application to find predictions for each tile from a limited search space in previously decoded reference frames, the macroblock level modeling generating an H.264 macroblock encoding prediction for a target macroblock,

the macroblock as feature encoding level (i) using a first BBMEC process substantially identical to the macroblock encoding level to find a first prediction for the target macroblock from a most-recent reference frame, (ii) using a second BBMEC application to find a second prediction for the first prediction by searching in a second-most-recent frame, (iii) creating a track for the target macroblock by applying BBMEC applications through progressively older frames, and (iv) generating a macroblock as feature encoding level prediction from among the resulting track instances;

the feature encoding level detecting and tracking features independent of the macroblock grid and associating a feature with an overlapping macroblock such that a corresponding feature track (the track belonging to the feature overlapping the macroblock) is used to navigate previously-decoded reference frames to find a better match (prediction) for the overlapping macroblock by using offsets between the macroblock and respective feature track instances to generate an indirect prediction for the macroblock; and

where multiple features overlap a given target macroblock, the feature with greatest overlap is selected to model that target macroblock, and

the object encoding level detecting and tracking objects (features that overlap at least portions of multiple macroblocks) and associating an object with all overlapping macroblocks, such that object tracks are used to navigate previously-decoded reference frames to find better matches (predictions) for all macroblocks overlapping the object by using offsets between the target macroblock and respective object track instances to generate an indirect prediction for the overlapping macroblocks, so that a single motion vector is calculated for all of the macroblocks associated with the object resulting in computation and encoding size savings, the better matches having the most encoding size savings;

the modeler generating model-based predictions for the target macroblock from the multiple encoding levels of fidelities;

an encoder, in communication with the modeler, to determine the best prediction for the target macroblock from among the multiple encoding levels of fidelities; and

the encoder integrating the best prediction with transform, quantization, and entropy encoding to produce a best encoding for the target macroblock.