Method and apparatus for performing two pass quality video compression through pipelining and buffer management

• US 6,101,276 A
• Filed: 06/21/1996
• Issued: 08/08/2000
• Est. Priority Date: 06/21/1996
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Compaq Computer Corporation (HP Inc.)
• Inventors: Galbi, Duane E., Adiletta, Matthew James, Ho, Samuel William, Wheeler, William Ralph, Rose, Robert Clint, Chow, King-Wai
• Primary Examiner(s): Lee, Thomas D.
• Assistant Examiner(s): Chen, Wenpeng
• Application Number:
  US08/670,199
• Time in Patent Office: 1,509 Days
• Field of Search: 382/236, 382/233, 382/234, 348/416, 348/699, 348/402, 348/409, 348/390, 348/415, 348/413, 348/405, 348/384
• US Class Current: 382/236
• CPC Class Codes: H04N 19/114 Adapting the group of pictures [GOP] structure, e.g. number of B-frames between two anchor frames H04N19/107 takes precedence
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/127 Prioritisation of hardware or computational resources
• CPC Class Codes: H04N 19/132 Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
• CPC Class Codes: H04N 19/14 Coding unit complexity, e.g. amount of activity or edge presence estimation H04N19/146 takes precedence
• CPC Class Codes: H04N 19/149 by estimating the code amount by means of a model, e.g. mathematical model or statistical model
• CPC Class Codes: H04N 19/159 Prediction type, e.g. intra-frame, inter-frame or bidirectional frame prediction
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/177 the unit being a group of pictures [GOP]
• CPC Class Codes: H04N 19/31 in the temporal domain
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/423 characterised by memory arrangements H04N19/433 takes precedence
• CPC Class Codes: H04N 19/436 using parallelised computational arrangements
• CPC Class Codes: H04N 19/46 Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/577 Motion compensation with bidirectional frame interpolation, i.e. using B-pictures
• CPC Class Codes: H04N 19/587 involving temporal sub-sampling or interpolation, e.g. decimation or subsequent interpolation of pictures in a video sequence
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/82 involving filtering within a prediction loop
• CPC Class Codes: H04N 19/87 involving scene cut or scene change detection in combination with video compression
• CPC Class Codes: H04N 19/93 : Run-length coding

Abstract

An apparatus and method a method for performing two-pass real time video compression is provided. Tactical decisions such as encoding and quantization values are determined in software, whereas functional execution steps are performed in hardware. By appropriately apportioning the tasks between software and hardware, the benefits of each type of processing are exploited, while minimizing both hardware complexity and data transfer requirements. One key concept that allows the compression unit to operate in real time is that the architecture and pipelining both allow for B frames to be executed out of order. By buffering B frames, two-pass motion estimation techniques can be performed to tailor bit usage to the requirements of the frame, and thereby provide a more appealing output image.

Claims

1. A method of performing a single path real-time compression and decompression of video data input to a video compression/decompression unit including motion estimation, said video data being apportioned into a plurality of frames including frames identified as reference frames, a subset of said plurality of frames being dependent frames having dependencies on one or more of said reference frames for compression purposes, said method comprising the steps of:

first compressing said reference frames as they are input, by using spatial compression techniques;

storing said dependent frames in memory until said one or more reference frames have been compressed;

performing motion estimation on said dependent frames;

dropping selected dependent frames after evaluation if and when said memory is full;

replacing dropped frames with synthetic frames similar to a proximate reference frame;

retrieving the stored dependent frames from said memory one by one; and

responsive to said reference frames having been compressed, then compressing said dependent frames from said memory.

2. The method according to claim 1, wherein each said step of compressing further comprises the steps of:

determining motion characteristics for each of said frames;

providing compressed data for each of said frames responsive to said motion characteristics; and

wherein said step of determining motion characteristics operates on a first frame simultaneously in parallel with said step of providing compressed data which operates on a second frame.

3. The method according to claim 2, wherein each of said frame is further apportioned into a plurality of macro-blocks, and wherein said step of determining motion characteristics further comprises the steps of:

calculating one or more motion vectors for each macro-block of each frame, said motion vectors for indicating a change in location of a matching macro-block in a different frame; and

calculating an energy characteristic for each of said macro-blocks.

4. The method according to claim 3, wherein said step of determining motion characteristics further comprises the steps of:

responsive to said motion vectors and said energy characteristics of each of said macro-blocks, determining a coding type for said macro-block, said coding type including a spatial encoding type and a temporal encoding type.

5. The method according to claim 4, wherein said step of calculating said motion vectors is implemented in hardware, and wherein said step of determining a coding type is implemented in software.

6. The method according to claim 2, wherein each of said frame is further apportioned into a plurality of macro-blocks and wherein said step of determining motion characteristics for each of said frames includes the step of providing a coding type for each macro-block of each frame, and wherein said step of providing compressed data for each of said macro-blocks for each of said frames further comprises the step of:

responsive to said coding type of said macro-block being a temporal encoding type macro-block, providing an error macro-block indicative of the change of pixel values between said one of said macro-blocks and said one or more reference macro-blocks.

7. The method according to claim 6, wherein said step of providing compressed data for each of said macro-blocks further comprises the step of:

applying a transform function to either said error macro-block if said coding type of said macro-block is a temporal coding type or alternatively applying said transform function to said macro-block if said coding type is not a temporal coding type to provide a frequency macro-block.

8. The method according to claim 7, further comprising the step of applying a constant coefficient to said frequency macro-block to provide a quantized macro-block.

9. The method according to claim 8, further comprising the step of:

translating said quantized macro-block into tokens indicating the value and location of elements within each quantized macro-block.

10. The method according to claim 9, further comprising the step of:

encoding each of said tokens into a unique code to provide a resulting bit stream representing the compressed video data.

11. The method according to claim 10, wherein said step of applying a transform function are implemented in hardware and wherein said steps of translating and encoding are implemented in software.

12. The method according to claim 2, wherein each of said frame is further apportioned into a plurality of macro-blocks and wherein said step of determining motion characteristics for each of said frames includes the step of providing a coding type for each macro-block of each frame, and wherein said step of providing compressed data for each of said macro-blocks for each of said frames further comprises the step of applying a transform function to each of said macro-blocks to provide a transformed macro-block, said method of providing compressed data further comprising the steps of:

translating said transformed macro-block into a plurality of tokens representative of the location and value of elements within said transformed macro-block; and

assigning to each of said tokens a unique code, such that the resulting macro-block is defined by a bits stream that is storable in memory.

13. An apparatus for performing a single path real-time two-pass compression and decompression of video data input to a video compression/decompression unit including motion estimation, said video data being apportioned into a plurality of frames including reference frames, a subset of said plurality of frames being dependent frames having dependencies on one or more of said reference frames for compression purposes, said apparatus comprising:

means for compressing said reference frames as they are input;

means for storing said dependent frames in memory until said associated one or more reference frames have been compressed and means for retrieving said dependent frames from said memory;

means for dropping selected dependent frames after evaluation, if and when said memory is full;

means for replacing each dropped from with a synthetic replacement frame similar to a reference frame proximate to the each dropped frame; and

means, responsive to said associated reference frames having been compressed, for then compressing said associated dependent frame.

14. The apparatus of claim 13, wherein each said means for compressing further comprises:

means for determining motion characteristics for each of said frames; and

means for providing compressed data for each of said frames responsive to said motion characteristics, wherein said means for determining motion characteristics operates on a first frame in parallel with said means for providing compressed data operating on a second frame.

15. The method according to claim 14, wherein each of said frame is further apportioned into a plurality of macro-blocks, and wherein said means for determining motion characteristics further comprises:

means calculating one or more motion vectors for each macro-block of each frame, said motion vectors for indicating a change in location of a matching macro-block in a different frame; and

means for calculating an energy characteristic for each of said macro-blocks.

16. The method according to claim 15, wherein said means for determining motion characteristics further comprises:

means for assigning, responsive to said motion vectors and said energy characteristics of each of said macro-blocks, a coding type for said macro-block, said coding type including a spatial encoding type and a temporal encoding type.

17. The method according to claim 16, wherein said means for calculating said motion vectors is implemented in hardware, and wherein said means for assigning a coding type is a software program.

18. The method according to claim 14, wherein each of said frames is further apportioned into a plurality of macro-blocks and wherein said means for determining motion characteristics for each of said frames includes means for providing a coding type for each macro-block of each frame, and wherein said means for providing compressed data for each of said macro-blocks for each of said frames further comprises:

means, responsive to said coding type of said macro-block being a temporal encoding type macro-block, for providing an error macro-block indicative of the change of pixel values between said one of said macro-blocks and said one or more reference macro-blocks.

19. The method according to claim 18, wherein said means for providing compressed data for each of said macro-blocks further comprises:

means for applying a transform function to either said error macro-block if said coding type of said macro-block is a temporal coding type or alternatively for applying said transform function to said macro-block if said coding type is not a temporal coding type to provide a frequency macro-block.

20. The method according to claim 19, further comprising means for applying a constant coefficient to said frequency macro-block to provide a quantized macro-block.

21. The method according to claim 20, further comprising:

means for translating said quantized macro-block into tokens indicating the value and location of elements within each quantized macro-block.

22. The method according to claim 21, further comprising:

means for encoding each of said tokens into a unique code to provide a resulting bit stream representing the compressed video data.

23. The method according to claim 19, wherein said means for applying a transform function is implemented in hardware and wherein said means for translating and encoding are implemented via a software program.

24. A method for performing a single path real-time compression and decompression of video data input to a video compression/decompression unit including motion estimation, said video data being apportioned into a plurality of frames including frames identified as reference frames, a subset of said plurality of frames being dependent frames having dependencies on one or more of said reference frames for compression purposes, said method comprising the steps of:

first compressing said reference frames as they are input;

storing said dependent frames in a memory of a coupled processing system until said associated one or more reference frames have been compressed;

dropping selected dependent frames after evaluation, if and when said memory is full

replacing each dropped frame with a synthetic replacement frame similar to a reference frame proximate to each dropped frame; and

retrieving said stored dependent frames one by one from said memory of said coupled processing system and compressing said dependent frames after completion of the compression of said associated reference frames.