Methods of feature extraction of video sequences

• US 6,618,507 B1
• Filed: 01/25/1999
• Issued: 09/09/2003
• Est. Priority Date: 01/25/1999
• Status: Expired due to Fees

• Current Assignee: MC Micro Compact Car AG, Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Ito, Hiroshi, Sun, Huifang, Divakaran, Ajay
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): Dang, Duy M.
• Application Number:
  US09/236,838
• Time in Patent Office: 1,688 Days
• Field of Search: 382/236, 382/235, 382/250, 382/248, 382/298, 382/233, 348/387, 348/390, 348/395, 348/397, 348/403, 348/411
• US Class Current: 382/236
• CPC Class Codes: G06F 16/786 using motion, e.g. object motion or camera motion
• CPC Class Codes: G06V 20/46 Extracting features or characteristics from the video content, e.g. video fingerprints, representative shots or key frames

Abstract

This invention relates to methods of feature extraction from MPEG-2 and MPEG-4 compressed video sequences. The spatio-temporal compression complexity of video sequences is evaluated for feature extraction by inspecting the compressed bitstream and the complexity is used as a descriptor of the spatio-temporal characteristics of the video sequence. The spatio-temporal compression complexity measure is used as a matching criterion and can also be used for absolute indexing. Feature extraction can be accomplished in conjunction with scene change detection techniques and the combination has reasonable accuracy and the advantage of high simplicity since it is based on entropy decoding of signals in compressed form and does not require computationally expensive inverse Discrete Cosine Transformation (DCT).

Claims

1. A method for identifying a frame, comprising the steps of:

determining the number of bits in the compressed bit stream associated with a first inter-coded frame represented in a compressed bit-stream corresponding to a video sequence having intra-coded frames and inter-coded frames, the compressed bit-stream including a number of bits associated with each of the inter-coded frames representing a displacement from the associated inter-coded frame to a closest matching of the intra-coded frames; and

identifying the first inter-coded frame based on the determined number of bits.

2. A method according to claim 1, wherein the frame is an object, the intra-coded frames are intra-coded objects, the inter-coded frames are inter-coded objects, and the first inter-coded frame is a first inter-coded object.

3. A method according to claim 1, wherein the determined number of bits are indicative of one of (i) a scene change within the first inter-coded frame and (ii) an object within the first inter-coded frame and not in an immediately preceding one of the intra-coded and the inter-coded frames.

4. A method according to claim 1, wherein the bits are first bits, the compressed bit-stream further includes a number of second bits associated with each of the inter-coded frames representing a difference between information within the associated inter-coded frame and information within the closest matching intra-coded frame, and further comprising the steps of:

determining the number of second bits in the compressed bit stream associated with the first inter-coded frame; and

determining the spatio-temporal compression complexity of the first inter-coded frame based upon the determined number first bits and the determined number of second bits;

wherein the first inter-coded frame is identified based upon the determined complexity.

5. A method according to claim 4, further comprising the step of:

entropy decoding the compressed bit stream;

wherein the number of first bits and the number of second bits in the compressed bit stream associated with the first inter-coded frame is determined from the entropy decoded compressed bit stream.

6. A method according to claim 4, wherein the first inter-coded frame includes a plurality of macro-blocks, each of the macro-blocks is associated with a respective portion of the determined number of the first bits and a respective portion of the determined number of the second bits, and further comprising the step of:

generating a descriptor including a first compression complexity matrix including values representing the respective portions of the determined number of first bits associated with the plurality of macro-blocks and a second compression complexity matrix including values representing the respective portions of the determined number of second bits associated with the plurality of macro-blocks;

wherein the spatio-temporal compression complexity of the first inter-coded frame is determined based on the generated descriptor.

7. A method according to claim 6, wherein the number of second bits associated with each of the plurality of macro-blocks is the same.

8. A method according to claim 6, wherein:

generating the descriptor includes averaging the values representing the respective portions of the determined number of first bits associated with the plurality of macro-blocks; and

the generated descriptor includes the average value.

9. A method according to claim 1, wherein:

the first inter-coded frame includes a plurality of macro-blocks;

each of the macro-blocks is associated with a respective portion of the determined number of bits; and

the determined number of bits is an average number of bits per macro-block which is computed based on the respective portions of the determined number of bits associated with each of the plurality of macro-blocks included in the first inter-coded frame.

10. A method according to claim 9, wherein the bits are first bits, the compressed bit-stream further includes a number of the second bits associated with each of the inter-coded frames representing a difference between information within the associated inter-coded frame and information within the closest matching intra-coded frame, and further comprising the steps of:

determining the number of second bits in the compressed bit stream associated with the first inter-coded frame, each of the macro-blocks being associated with a respective portion of the determined number of second bits; and

computing an average number of second bits per macro-block based on the respective portions of the determined number of second bits associated with each of the plurality of micro-blocks included in the first inter-coded frame;

wherein the first inter-coded frame is identified based upon the computed average number of first bits and the computed average number of second bits.

11. A method according to claim 9, further comprising the steps of:

setting the number of bits associated with each of the plurality of macro-blocks to zero if the number of bits associated with that macro-block is less than a threshold; and

determining a value corresponding to run lengths of those of

the plurality of macro-blocks having the number of bits set to zero;

wherein the first inter-coded frame is further identified based upon the determined value corresponding to the run lengths.

12. A method according to claim 11, wherein the threshold is the computed average number of bite.

13. A method according to claim 12, wherein the value corresponding to run lengths is one of a plurality of values corresponding to run lengths of those of the plurality of macro-blocks having the number of bits set to zero, the sum of the plurality of values is equal to a total number of macro-blocks in the plurality of macro-blocks having the number of bits set to zero, and further comprising the steps of:

categorizing each of the run lengths in one of a plurality of categories, each of the plurality of categories corresponding to a different run length range; and

determining a value corresponding to the run lengths within each of the plurality of categories;

wherein the first inter-coded frame is further identified based upon the determined value corresponding to run lengths in each of the plurality of categories.

14. A method for identifying a frame, comprising the steps of:

identifying at least a first inter-coded frame and a second inter-coded frame in a compressed video bit-stream, wherein (i) the compressed video bit-stream corresponds to a video sequence having intra-coded and inter-coded frames, each of the inter-coded frames having a plurality of macro-blocks, the compressed bit-stream including a number of bits associated with each of the inter-coded frames representing a displacement from the associated inter-coded frame to a closest matching of the intra-coded frames, a respective portion of the number of bits being associated with each of the plurality of macro-blocks of that inter-coded frame and corresponding to a number of run lengths representing those of the plurality of macro-blocks of that inter-coded frame having the associated respective portion of the number of bits equaling less than a threshold, and (ii) the first and the second inter-coded frames are identified based on the number of bits associated with the first inter-coded frame and the number of bits associated with the second inter-coded frame; and

identifying only the first inter-coded frame of the identified at least first and second inter-coded frames based on the number of run lengths associated with the first inter-coded frame.

15. A method according to claim 14, wherein:

the number of run lengths associated with the first inter-coded frame is one of multiple numbers of run lengths associated with the first inter-coded frame;

each of the multiple numbers of run lengths is within one of multiple run length ranges; and

the first inter-coded frame is identified based on the number of run lengths within each of the multiple run length ranges.

16. A method according to claim 14, wherein the number of bits is an average number of bits per macro-block.

17. A method according to claim 14, further comprising the step of:

comparing a frequency of occurrence of the number of the run lengths associated with the first inter-coded frame with a frequency of occurrence of the number of the run lengths associated with the second inter-coded frame;

wherein the first inter-coded frame is identified based on a difference between the frequency of occurrence associated with the first inter-coded frame and the frequency of occurrence associated with the first inter-coded frame.

18. A descriptor, stored on a computer readable memory, for identifying a frame, comprising:

a number of bits of a compressed bit stream corresponding to a video sequence having intra-coded frames and inter-coded frames, each of the inter-coded frames including a plurality of macro-blocks, wherein the number of bits are associated with the plurality of macro-blocks of one of the inter-coded frames and represent a displacement from the one inter-coded frame to a closest matching of the intra-coded frames; and

a value corresponding to run lengths of those of the plurality of macro-blocks of the one inter-coded frame having less than a threshold number of the associated bits.

19. A descriptor according to claim 18, wherein:

each of the plurality of macro-blocks of the one inter-coded frame has an associated respective portion of the bits; and

the number of bits is an average number of bits in the respective portions of bits associated with each of the plurality of macro-blocks of the one inter-coded frame.

20. A descriptor according to claim 19, wherein the threshold is the average number of bits.

21. A descriptor according to claim 18, wherein the bits are first bits, and further comprising:

a number of the second bits associated with the one inter-coded frame representing a difference between information within the one inter-coded frame and information within the closest matching intra-coded frame.

22. A descriptor according to claim 21, wherein:

each of the plurality of macro-blocks of the one inter-coded frame has an associated respective portion of the second bits; and

the number of second bits is an average number of the second bits in the respective portions of second bits associated with each of the plurality of macro-blocks of the one inter-coded frame.

23. A descriptor according to claim 18, wherein the value corresponding to run lengths is a first value corresponding to the run lengths within a first range, and further comprising:

a second value corresponding to the run lengths of those of the plurality of macro-blocks having less than a threshold number of the associated bits and within a second range different than the first range.