Method and system for compressing video data

• US 5,467,134 A
• Filed: 12/22/1992
• Issued: 11/14/1995
• Est. Priority Date: 12/22/1992
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Miller, Daniel J., Ledoux, Eric, Maymudes, David M., Laney, Stuart T.
• Primary Examiner(s): Britton, Howard W.
• Application Number:
  US07/995,504
• Time in Patent Office: 1,057 Days
• Field of Search: 348/420, 348/422, 348/409, 348/415, 348/417, 348/418
• US Class Current: 348/409.1
• CPC Class Codes: H04N 19/00 Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
• CPC Class Codes: H04N 19/107 between spatial and temporal predictive coding, e.g. picture refresh
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• 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/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/15 by monitoring actual compressed data size at the memory before deciding storage at the transmission buffer
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/182 the unit being a pixel
• CPC Class Codes: H04N 19/192 the adaptation method, adaptation tool or adaptation type being iterative or recursive
• CPC Class Codes: H04N 19/577 Motion compensation with bidirectional frame interpolation, i.e. using B-pictures
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
• CPC Class Codes: H04N 5/85 on discs or drums
• CPC Class Codes: H04N 9/8045 using predictive coding

Abstract

A method for compressing video movie data to a specified target size using intraframe and interframe compression schemes. In intraframe compression, a frame of the movie is compressed by comparing adjacent pixels within the same frame. In contrast, interframe compression compresses by comparing similarly situated pixels of adjacent frames. The method begins by compressing the first frame of the video movie using intraframe compression. The first stage of the intraframe compression process does not degrade the quality of the original data, e.g., the method uses run length encoding based on the pixels'"'"' color values to compress the video data. However, in circumstances where lossless compression is not sufficient, the method utilizes a threshold value, or tolerance, to achieve further compression. In these cases, if the color variance between pixels is less than or equal to the tolerance, the method will encode the two pixels using a single color value--otherwise, the method will encode the two pixels using different color values. The method increases or decreases the tolerance to achieve compression within the target range. In cases where compression within the target range results in an image of unacceptable quality, the method will split the raw data in half and compress each portion of data separately. Frames after the first frame are generally compressed using a combination of intraframe and interframe compression. Additionally, the method periodically encodes frames using intraframe compression only in order to enhance random frame access.

Claims

1. A method for compressing video data, the video data being formed by a plurality of pixels, the method including the computer-implemented steps:

(a) forming a plurality of pixel groupings;

(b) determining a characteristic value for each pixel grouping;

(c) specifying a tolerance;

(d) determining a variance between the characteristic values of the pixel groupings;

(e) when the determined variance is within the tolerance, specifying a specified characteristic value to represent the pixel groupings, setting the characteristic value of each pixel grouping to the specified characteristic value; and

(f) counting a number of consecutive pixel groupings having the same specified characteristic value and storing the counted number and the specified characteristic value in a compressed version of the video data.

3. The method of claim 1 wherein the characteristic value is a gray scale value.

4. The method of claim 1 wherein the characteristic value is an intensity value.

5. The method of claim 1 wherein each of the pixel groupings is formed by a single pixel.

6. The method of claim 1 wherein the characteristic value is formed by a plurality of components and wherein the step of determining the variance includes the steps:

squaring the differences of at least one of the components; and

summing the squared differences.

7. The method of claim 1, including the steps:

specifying a target range for the compressed version of the video data; and

iteratively adjusting the tolerance until the compressed version of the video data is within the target range.

8. The method of claim 7 wherein the computer-implemented step of iteratively adjusting the tolerance includes iteratively performing the steps:

determining the size of the compressed version of the video data; and

when the determined size is not within the target range, adjusting the tolerance and repeating steps (e)-(f) using the adjusted tolerance.

9. The method of claim 8 wherein the computer-implemented step of adjusting the tolerance includes:

identifying a range of permissible tolerances;

selecting a new tolerance value from the identified tolerance range; and

redefining the range of permissible tolerances as having a limit equal the newly selected tolerance.

10. The method of claim 9 wherein the new tolerance is selected from an approximate midpoint of the identified tolerance range.

11. The method of claim 9 wherein the step of selecting the new tolerance includes:

adding a predetermined value to one of the previously used tolerances.

12. The method of claim 11 wherein the predetermined value is increased with each iterative adjustment of the tolerance.

2. The method of claim wherein the characteristic value is a color value.

13. A method for mapping a video, the video being formed by a plurality of raw video frames, the frames being formed by a plurality of pixels, the method including the computer-implemented steps:

(a) forming a plurality of pixel groupings from the pixels of each raw data frame;

(b) determining a characteristic value for each pixel grouping;

(c) specifying a tolerance;

(d) determining a variance between the characteristic values of the pixel groupings; and

(e) when the determined variance is within the tolerance, specifying a specified characteristic value to represent the pixel groupings, and setting the characteristic value of each pixel grouping to the specified characteristic value.

14. The method of claim 13 wherein the characteristic value is a color value.

15. The method of claim 13 wherein the characteristic value is a gray scale value.

16. The method of claim 13 wherein the characteristic value is an intensity value.

17. The method of claim 13 wherein each of the pixel groupings is formed by a single pixel.

18. The method of claim 13 wherein the characteristic value is formed by a plurality of components and wherein the step of determining the variance includes the steps:

squaring the differences of at least one of the components; and

summing the squared differences.

19. The method of claim 13, including the computer-implemented steps:

(f) specifying a range of tolerances;

(g) specifying a range of acceptable resolution for the mapped video;

(h) determining the resolution of the mapped video; and

(i) when the determined resolution is not within the range of acceptable resolution, selecting a new tolerance value from the specified range of tolerances, redefining the range of tolerances as having an end-limit equal to the selected new tolerance; and

(j) iteratively repeating steps (e), (h) and (i) until the mapped video is within the range of acceptable resolution.

20. The method of claim 19 wherein the new tolerance is selected from an approximate midpoint of the range of tolerances.

21. The method of claim 19 wherein the new tolerance is selected by adding a predetermined value to one of the previously used tolerances.

22. The method of claim 21 wherein the predetermined value is increased with each iterative adjustment of the tolerance.

23. A method for compressing a video, the video being formed by a plurality of raw data video frames, the frames being formed by a plurality of pixels, the method including the computer-implemented steps:

(a) forming a plurality of pixel groupings from the pixels of each raw data video frame;

(b) determining a characteristic value for each pixel grouping;

(c) specifying a tolerance;

(d) determining a variance between the characteristic values of the pixel groupings;

(e) when the determined variance is within the tolerance, specifying a specified characteristic value to represent the pixel groupings, and setting the characteristic value of each pixel grouping to the specified characteristic value; and

(f) counting a number of consecutive pixel groupings having the same specified characteristic value and storing the counted number and the specified characteristic value in a compressed data video frame.

24. The method of claim 23 wherein the characteristic value is a color value.

25. The method of claim 23 wherein the characteristic value is a gray scale value.

26. The method of claim 23 wherein the characteristic value is an intensity value.

27. The method of claim 23 wherein the pixel groupings are formed by a single pixel.

28. The method of claim 23 wherein the characteristic value is formed by a plurality of components and wherein the step of determining the variance includes the steps:

squaring the differences of at least one of the components; and

summing the squared differences.

29. The method of claim 23, including the steps:

specifying a target range for the compressed data video frame; and

iteratively adjusting the tolerance until the compressed data video frame is within the target range.

30. The method of claim 29 wherein the computer-implemented step of iteratively adjusting the tolerance includes iteratively performing the computer-implemented steps:

determining a size of the compressed data video frame; and

when the determined size is not within the target range, adjusting the tolerance and repeating steps (e)-(f) using the adjusted tolerance.

31. The method of claim 29 wherein the computer-implemented step of iteratively adjusting the tolerance includes the computer-implemented steps:

identifying a previously determined effective tolerance;

repeating steps (e)-(f) using the effective tolerance and determining the size of the compressed data video frame;

when the determined size using the effective tolerance is not within the target range, specifying a maximum tolerance, repeating steps (e)-(f) using the maximum tolerance and determining the size of the compressed data video frame; and

when the determined size using the maximum tolerance is within the target range, specifying a heuristically determined tolerance, repeating steps (e)-(f) using the heuristically determined tolerance and determining the size of the compressed data video frame.

32. The method of claim 29, including the computer-implemented steps:

specifying a maximum value;

when the tolerance is greater than the maximum value, splitting the raw data video frame into a plurality of raw data portions; and

repeating steps (a)-(f) using each raw data portion as a raw data video frame.

33. The method of claim 32, including the computer-implemented step of:

substituting one of the raw data portions for one of the raw data frames following the split raw data video frame.

34. A method for compressing a video, the video being formed by a plurality of raw data video frames, the frames being formed by a plurality of pixels, the method including the computer-implemented steps:

(a) forming a plurality of pixel groupings from the pixels of each raw data video frame;

(b) determining a characteristic value for each pixel grouping;

(c) specifying an interframe tolerance;

(d) for a plurality of corresponding interframe pixel groupings, determining an interframe variance between the characteristic values of the interframe pixel groupings;

(e) counting a number of consecutive interframe pixel groupings whose determined interframe variance is within the interframe tolerance; and

(f) encoding a delta indicative of the counted number of consecutive interframe pixel groupings in a compressed data video frame.

35. The method of claim 34 wherein the characteristic value is a color value.

36. The method of claim 34 wherein the characteristic value is a gray scale value.

37. The method of claim 34 wherein the characteristic value is an intensity value.

38. The method of claim 34 wherein each of the pixel groupings is formed by a single pixel.

39. The method of claim 34 wherein the characteristic value is formed by a plurality of components and wherein the step of determining the variance includes the steps:

squaring the differences of at least one of the components; and

summing the squared differences.

40. The method of claim 34 wherein the computer-implemented step of encoding the delta includes the computer-implemented steps:

selecting a range of acceptable delta values; and

when the counted number of consecutive interframe pixel groupings is within the range of acceptable delta values, encoding the delta as the counted number.

41. The method of claim 40, including the computer-implemented steps:

when the counted number of consecutive interframe pixel groupings is not within the range of acceptable delta values, encoding the delta using an escape sequence, the counted number and additional positioning information.

42. The method of claim 34, including the steps:

when the determined interframe variance is not within than the interframe tolerance, specifying an intraframe tolerance and for a plurality of intraframe pixel groupings, determining an intraframe variance between the characteristic values of the intraframe pixel groupings;

when the determined intraframe variance is within the intraframe tolerance, specifying a specified characteristic value to represent each intraframe pixel grouping, and setting the characteristic value of each intraframe pixel grouping to the specified characteristic value; and

counting a number of consecutive intraframe groupings having the same specified characteristic value.

43. The method of claim 42, including the computer-implemented steps:

selecting a range of acceptable delta values;

when the counted number of consecutive interframe pixel groupings is within the range of acceptable delta values, encoding the delta as the counted number;

when the counted number of consecutive interframe pixel groupings is not within the range of acceptable delta values, encoding the delta using an escape sequence, the counted number and additional positioning information;

specifying an offset value outside of the range of delta values;

combining the offset value and the counted number; and

storing the combined value and the specified characteristic value in the compressed data video frame.

44. The method of claim 42 including the step:

storing the counted number and the specified characteristic value in the compressed data video frame.

45. The method of claim 42, including the computer-implemented steps:

specifying a target range for the compressed data video frame;

determining a size of the compressed data video frame; and

when the determined size is not within the target range, adjusting the interframe tolerance and repeating steps (e)-(f) using the adjusted interframe tolerance.

46. The method of claim 42, including the computer-implemented steps:

specifying a maximum value; and

when the intraframe tolerance is greater than the maximum value, splitting the raw data frame into a plurality of raw data portions and repeating steps (a)-(f) using each raw data portion as a raw data video frame.

47. The method of claim 42, including the computer-implemented steps:

specifying a maximum value; and

when the interframe tolerance is greater than the maximum value, splitting the raw data video frame into a plurality of raw data portions and repeating steps (a)-(f) using each raw data portion as a raw data video frame.

48. The method of claim 42, including the computer-implemented steps:

specifying a target range for the compressed data video frame;

determining a size of the compressed data video frame; and

when the determined size is not within the target range, adjusting at least one of the interframe or intraframe tolerances and repeating steps (e)-(f) using the adjusted tolerance.

49. The method of claim 42, including the computer-implemented steps:

specifying a target range for the compressed data video frame;

determining a size of the compressed data video frame;

when the determined size is not within the target range, adjusting at least one of the tolerances and repeating steps (e)-(f) using the adjusted tolerance;

specifying a maximum value; and

when the interframe tolerance is greater than the maximum value, splitting the raw data video frame into a plurality of raw data portions and repeating steps (a)-(f) using each of the raw data portions as a raw data frame.

50. The method of claim 42, including the computer-implemented steps:

designating one of the raw data video frames as a key frame; and

for a plurality of intraframe pixel groupings of the key frame, determining a variance between the characteristic values between the intraframe pixel groupings, when the determined variance is within the intraframe tolerance, specifying a characteristic value to represent the intraframe pixel grouping, setting the characteristic value of each intraframe pixel grouping to the specified characteristic value, counting a number of consecutive intraframe pixel groupings having the same specified characteristic value, and storing the counted number and the specified characteristic value in the compressed data video frame.

51. The method of claim 42, including the computer-implemented steps:

specifying a target range for the compressed data video frame;

determining a size of the compressed data video frame;

when the determined size is not within the target range, adjusting at least one of the tolerances and repeating steps (e)-(f) using the adjusted tolerance;

specifying a maximum value; and

when the intraframe tolerance is greater than the maximum value, splitting the raw data video frame into a plurality of raw data portions and repeating steps (a)-(f) using each of the raw data portions as a raw data frame.

52. The method of claim 51, including the steps:

counting a number of consecutive intraframe pixel groupings having the same characteristic value; and

storing the counted number and the specified characteristic value in the compressed data video frame.

53. The method of claim 42 wherein the step of adjusting the interframe tolerance includes:

specifying a range of interframe tolerances;

selecting a new interframe tolerance value from the specified range of interframe tolerances; and

redefining the range of interframe tolerances as having a limit equal the newly selected interframe tolerance.

54. The method of claim 53 wherein the new interframe tolerance is selected from an approximate midpoint of the range of interframe tolerances.

55. The method of claim 53 wherein the step of selecting the new interframe tolerance includes:

adding a predetermined value to one of the previously used interframe tolerances.

56. The method of claim 55 wherein the predetermined value is increased with each iteration.

57. A method for compressing a video, the video being formed by a plurality of raw data video frames, the frames being formed by a plurality of pixels, the method including the computer-implemented steps:

(a) forming a plurality of pixel groupings from the pixels of each raw data frame;

(b) determining a characteristic value for each pixel grouping;

(c) specifying an interframe tolerance;

(d) determining an interframe variance between the characteristic values of a plurality of corresponding interframe pixel groupings;

(e) when the determined interframe variance is not within the interframe tolerance, creating an intraframe compressed frame by forming a plurality of intraframe pixel groupings from one of the raw data frames, specifying an intraframe tolerance, determining an intraframe variance between the characteristic values of the intraframe pixel groupings, when the determined intraframe variance is within the intraframe tolerance, specifying a specified characteristic value to represent the intraframe pixel grouping, setting the characteristic value of each intraframe pixel grouping to the specified in characteristic intraframe value, counting a number of consecutive intraframe pixel groupings having the same specified characteristic intraframe value and storing the counted number and the specified characteristic value in a compressed data video frame;

(f) when the determined interframe variance is within the interframe tolerance, creating an interframe compressed frame by counting a number of consecutive interframe pixel groupings, encoding a delta indicative of the counted number of consecutive interframe pixel groupings in a compressed data video frame by selecting a range of acceptable delta values, and when the counted number of consecutive interframe pixel groupings is within the range acceptable delta of values, encoding the delta as the counted number, else when the counted number of consecutive interframe pixel groupings is not within the range of values, encoding the delta using an escape sequence, the counted number and additional positioning information;

(g) specifying a periodic key frame interval;

(h) designating a raw data frame as a key frame at the conclusion of the periodic key frame interval;

(i) for a plurality of intraframe pixel groupings of the key frame, specifying a key frame intraframe tolerance, determining a key frame intraframe variance between the characteristic values between the key frame intraframe pixel groupings, when the determined key frame variance is within the key frame tolerance, specifying a key frame characteristic value to represent the key frame pixel grouping, setting the key frame characteristic value of each key frame pixel grouping to the specified key frame characteristic value, counting a number of consecutive key frame pixel groupings having the same specified key frame characteristic value, storing the counted number and the specified key frame characteristic value in the compressed data video frame;

(j) specifying a target range for the compressed data video frame;

(k) determining a size of each compressed data video frame;

(l) when the determined size is not within the target range, specifying a minimum acceptable resolution level for the compressed data video frame;

(m) when the compressed data video frame is within the acceptable resolution level, adjusting at least one of the tolerances, and repeating steps (e)-(f) using the adjusted tolerance; and

(n) when the compressed data video frame is not within the acceptable resolution level, splitting the raw data frame into a plurality of raw data portions and repeating steps (a)-(f) using each raw data portion as a raw data frame.

58. A method for encoding a quantum of data formed by a plurality of data units, including the computer-implemented steps:

selecting a range of acceptable delta values;

determining the number of data units; and

when the determined number of data units is within the range of delta values, encoding a delta as the determined number of data units, wherein the delta is indicative of positioning information for a location in the quantum of data.

59. The method of claim 58, including the computer-implemented steps:

when the determined number of data units is not within the range of delta values, encoding the delta using an escape sequence, the counted number and additional positioning information.

60. The method of claim 58, including the step:

encoding a number of consecutive similar data units as a run length, wherein the run length has a magnitude value and an associated characteristic value.

61. The method of claim 60 wherein the step of encoding the run length includes the steps:

specifying an offset value;

counting the number of consecutive similar data units;

combining the offset value and the counted value; and

encoding the magnitude of the run length using the combined value.

62. The method of claim 60 wherein the step of encoding the run length includes the steps:

counting the number of consecutive similar data units; and

encoding the magnitude of the run length using the counted value.

63. A method for encoding a delta, wherein the delta is indicative of a number data units in a second data grouping that are similar to identically positioned data units in a first data grouping, including the computer-implemented steps:

selecting a range of acceptable delta values;

determining the number of consecutive data units; and

when the determined number of consecutive data units is within the range of delta values, encoding the delta as the determined number of consecutive data units.

64. The method of claim 63, including the computer-implemented steps:

when the determined number of consecutive data units is not within the range of delta values, encoding the delta using an escape sequence, the counted number and additional positioning information.

65. The method of claim 63, including the step:

encoding a number of consecutive similar data units as a run length, wherein the run length has a magnitude value and an associated characteristic value.

66. The method of claim 65 wherein the step of encoding the run length includes the steps:

specifying an offset value;

counting the number of consecutive similar data units;

combining the offset value and the counted value; and

encoding the magnitude of the run length using the combined value.

67. The method of claim 65 wherein the step of encoding the run length includes the steps:

counting the number of consecutive similar data units; and

encoding the magnitude of the run length using the counted value.

68. A method for encoding data, the method including the computer-implemented steps of:

determining a directional offset;

encrypting a delta as a single value, the value representing a magnitude of the directional offset, the delta having a maximum delta value;

adding the maximum delta value to a length of run value to define a first run length value;

encoding the first run length value;

determining a characteristic value to define a second run length value; and

encoding the second run length value.

69. A method for creating a decompressed version of video data from a plurality of compressed data groupings, the compressed data groupings formed by a plurality of run length data groupings, each run length data grouping formed by a characteristic value and a proportional magnitude value, and a plurality of deltas, each delta having a maximum possible delta value, the method including the computer-implemented steps:

retrieving a compressed data grouping;

when the compressed data grouping is a run length representation, determining the characteristic value of the representation, determining a run length value of the representation by subtracting the maximum possible delta value from the proportional magnitude value, and, for a number equal to the run length value, writing the characteristic value in a number of data locations of the decompressed version of the video data; and

when the compressed data grouping is a delta unit, determining a value of the delta unit and moving a positioning pointer a number of data units equal to the value of the delta unit.

70. A method for creating a decompressed version of video data from a compressed version of video data, the method including the computer-implemented steps:

retrieving a compressed data grouping from the compressed version of video data;

identifying a range of acceptable delta values;

determining a magnitude of the compressed data grouping; and

when the magnitude of the compressed data grouping is within the range of acceptable delta values, moving a portioning pointer a number of data units equal to the magnitude of the compressed delta grouping.

71. In a computer system, an apparatus for compressing video data to a range of target sizes, wherein the video data is formed by a plurality of pixels, the apparatus comprising:

means for determining a variance between a first and a second pixel by comparing a characteristic value for the first pixel with a characteristic value for the second pixel, the first and the second pixel being from among the plurality of pixels that form the video data;

means for specifying a single characteristic value for the first and the second pixel when the determined variance is within a provided tolerance; and

means for storing the single characteristic value in a compressed version of the video data, wherein the stored single characteristic value represents the characteristic value for the first pixel and the characteristic value for the second pixel.

72. The apparatus of claim 71, further comprising:

means for iteratively adjusting the provided tolerance until the compressed version of the video data is within the range of target sizes.

73. In a computer system, an apparatus for compressing a video, the video having at least two frames wherein each frame is formed by a plurality of pixels, and wherein each pixel has a characteristic value, the apparatus comprising:

means for determining a number of consecutive pixels of a first frame that, relative to similarly positioned pixels of a second frame, have characteristic values that are within a specified tolerance; and

means for storing the determined number in a compressed version of the second frame, the stored determined number indicating a number of consecutive pixels of the second frame that do not have to be altered when decompressing the compressed version of the second frame.

74. The apparatus of claim 73, further comprising:

means for specifying a target range for the compressed version of the second frame;

means for adjusting the specified tolerance when the compressed version of the second frame is not within the specified target range;

means for discerning a number of consecutive pixels of the first frame that, relative to the similarly positioned pixels of the second frame, have characteristic values that are within the adjusted tolerance; and

means for updating the compressed version of the second frame by storing the discerned number in the compressed version of the second frame, the stored discerned number indicating a number of consecutive pixels of the second frame that do not have to be altered when decompressing the compressed version of the second frame.