Adaptive digital video compression system

• US 5,225,904 A
• Filed: 12/04/1991
• Issued: 07/06/1993
• Est. Priority Date: 10/05/1987
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Keith, John M., Simon, Allen H., Golin, Stuart J., Astle, Brian
• Primary Examiner(s): Kostak, Victor R.
• Application Number:
  US07/802,169
• Time in Patent Office: 580 Days
• Field of Search: 358/133, 358/135, 358/12, 358/136, 358/13
• US Class Current: 375/240.12
• CPC Class Codes: H04N 19/10 using adaptive coding
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/50 using predictive coding H04N19/61 takes precedence
• CPC Class Codes: H04N 5/85 on discs or drums
• CPC Class Codes: H04N 7/24 Systems for the transmission of television signals using pulse code modulation H04N21/00 takes precedence
• CPC Class Codes: H04N 9/8066 with insertion of the PCM audio signals in the vertical blanking interval of the PCM video signal

Abstract

A full motion color digital video signal is compressed, formatted for transmission, recorded on compact disc media and decoded at conventional video frame rates. During compression, regions of a frame are individually analyzed to select optimum fill coding methods specific to each region. Region decoding time estimates are made to optimize compression thresholds. Region descriptive codes conveying the size and locations of the regions are grouped together in a first segment of a data stream. Region fill codes conveying pixel amplitude indications for the regions are grouped together according to fill code type and placed in other segments of the data stream. The data stream segments are individually variable length coded according to their respective statistical distributions and formatted to form data frames. The number of bytes per frame is dithered by the addition of auxiliary data determined by a reverse frame sequence analysis to provide an average number selected to minimize pauses of the compact disc during playback thereby avoiding unpredictable seek mode latency periods characteristic of compact discs. A decoder includes a variable length decoder responsive to statistical information in the code stream for separately variable length decoding individual segments of the data stream. Region location data is derived from region descriptive data and applied with region fill codes to a plurality of region specific decoders selected by detection of the fill code type (e.g., relative, absolute, dyad and DPCM) and decoded region pixels are stored in a bit map for subsequent display.

Claims

1. A method of encoding a digital motion video signal having data parameters for representing images of a sequence of images formed of pixels, said signal representing a current image being encoded and at least one previous image, each image having horizontal and vertical coordinates for indicating corresponding locations within said images, comprising the steps of:

(a) selecting a current target region within said current image, said current target region having target region data parameters and target region coordinates;

(b) comparing said target region data parameters with region data parameters of at least one candidate region of said previous image, said candidate region having coordinates differing from said target region coordinates;

(c) first determining motion compensation information for said candidate region in accordance with the comparing of step (b);

(d) second determining a sub-region within said current target region in accordance with said motion compensation information of said candidate region wherein substantially all pixels in said sub-region have substantially equal motion compensation information; and

,

(e) dividing said current region into at least first and second sub-regions in accordance with said second determining.

2. The method of claim 1, wherein step (b) and step (c) comprise the steps of comparing said target region data parameters with region data parameters of a plurality of candidate regions of said previous image and determining respective motion compensation information for each of said candidate regions, comprising the further steps of selecting one of said candidate regions in accordance with said motion compensation information.

3. The method of claim 2, wherein step (c) comprises the step of determining the means square difference between at least one selected pixel of said target region and a corresponding pixel said candidate regions.

4. The method of claim 3, comprising the step of selecting a candidate region of said plurality of candidate regions having a minimum means square difference.

5. The method of claim 4, wherein step (e) comprises dividing said current region only if said minimum means square difference of said selected candidate region in below a predetermined threshold.

6. The method of claim 5, comprising the further step of adjusting said threshold.

7. The method of claim 1, comprising the further step of determining a selected candidate region displacement value in accordance with coordinates of said target region and coordinates of said selected candidate region.

8. The method of claim 7, comprising the further step of encoding said current target region in accordance with said candidate region displacement value.

9. The method of claim 1, comprising the further step of providing a plurality of differing coding methods, each coding method adapted for encoding a sub-region having predetermined region data parameters.

10. The method of claim 9, comprising the further steps of:

(f) selecting a first coding method in accordance with the region data parameters of said first sub-region and applying said first coding method to said first sub-region to encode said first sub-region; and

,

(g) selecting a second coding method in accordance with the region data parameters of said second sub-region and applying said second coding method to said second sub-region for encoding said second sub-region, whereby said first and second sub-regions of said image are encoded differing coding methods.

11. The method of claim 10, wherein step (f) and step (g) comprise the step of selecting coding methods having codes of differing lengths.

12. The method of claim 11, wherein said region data parameters have respective frequency distributions and steps (f) and (g) comprise selecting coding lengths in accordance with said frequency distributions.

13. The method of claim 1, wherein said sub-regions are repeatedly divided in half in accordance with binary tree decomposition.

14. The method of claim 1, wherein said sub-regions are repeatedly divided into quarters in accordance with quad tree decomposition.

15. A method of encoding a digital motion video signal having data parameters for representing a sequence of images having a current image being encoded and at least one previous image, each image having corresponding horizontal and vertical coordinates, comprising the steps of:

(a) selecting a current target region within said current image, said current target region having target region data parameters and target region coordinates;

(b) comparing said target region data parameters with region data parameters of at least on candidate region of said previous image, said candidate region having coordinates differing from said target region coordinates;

(c) determining motion compensation information for said candidate region in accordance with the comparing of step (b); and

,

(d) dividing said current target region into at least first and second sub-regions in accordance with said motion compensation information of said candidate region.

16. The method of claim 15, wherein steps (b) and (c) comprise comparing said target region data parameters with region data parameters of a plurality of candidate regions of said previous image and determining respective motion compensation information for each of said candidate regions, comprising the further step of selecting one or said candidate regions in accordance with said motion compensation information.

17. The method of claim 16, wherein said regions are formed of pixels and step (c) comprises the step of determining the means square difference between at least one selected pixel of said target region and corresponding pixel within said candidate regions.

18. The method of claim 17, wherein said selecting in accordance with motion compensation information comprises the step of selecting a candidate region of said plurality of candidate regions having a minimum mean square difference.

19. The method of claim 18, wherein step (d) comprises dividing said current region only if said minimum mean square difference of said selected candidate region is below a predetermined threshold.

20. The method of claim 19, comprising the further step of adjusting said threshold.

21. The method of claim 20, comprising the further step of determining a selected candidate region displacement value in accordance with coordinates of said target region and said coordinates of selected candidate region.

22. The method of claim 21, comprising the further step of encoding said current target region in accordance with said candidate region displacement value.

23. The method of claim 15, comprising the further step of providing a plurality of differing coding methods, each coding method being adapted for encoding a sub-region having predetermined region data parameters.

24. The method of claim 23, comprising the further steps of:

(e) selecting a first coding method in accordance with the region data parameters of said first sub-region and applying said first coding method to said first sub-region to encode said first sub-region; and

,

(f) selecting a second coding method in accordance with the region data parameters of said second sub-region and applying said second coding method to said second sub-region for encoding said second sub-region, whereby said first and second sub-regions of said image are encoded by differing coding methods.

25. The method of claim 24, wherein step (e) and step (f) comprise selecting coding methods having codes of differing lengths.

26. The method of claim 25, wherein said region data parameters have respective frequency distributions and step (e) and step (f) comprise selecting coding lengths in accordance with said frequency distributions.

27. The method of claim 15, wherein said sub-regions are repeatedly divided in half in accordance with binary tree decomposition.

28. The method of claim 15, wherein said sub-regions are repeatedly divided in quarters in accordance with quad tree decomposition.

29. A method of encoding a digital motion video signal having data parameters for representing an image having at least two split directions, comprising the steps of:

(a) selecting regions of said image;

(b) determining edge information for said selected regions; and

,

(c) selecting a split direction for spatial splitting of said image in accordance with said determined edge information.

30. The method of claim 29, wherein step (b) comprises the further steps of:

(d) determining the number of horizontal edges within said selected regions; and

,

(e) determining the number of vertical edges within said selected regions.

31. The method of claim 30, comprising the further steps of:

PG,89

(f) determining the number of edges eliminated by splitting said image in a first split direction; and

,

(g) determining the number of edges eliminated by splitting said image in a second split direction.

32. The method of claim 30, comprising the further steps of:

(h) determining a horizontal edge information factor in accordance with the determining of step (d); and

,

(i) determining a vertical edge information factor in accordance with the determining of step (e).

33. The method of claim 32, wherein step (c) comprises selecting a split direction of said at least two split directions in accordance with said horizontal and vertical edge information factors.

34. A method of encoding a digital motion video signal having rows and columns formed of pixels for representing an image having at least first and second split directions, each pixel having at least one pixel data parameter, comprising the steps of:

(a) determining a respective row data parameter for each of said rows in accordance with said pixel data parameters of said pixels forming each row;

(b) determining a respective column data parameter for each of said columns in accordance with the pixel data parameters of said pixels forming each column;

(c) determining a substantially uniform vertical gradient in accordance with said determined row data parameters;

(d) determining a substantially uniform horizontal gradient in accordance with said determined column data parameters;

(e) comparing said determined row data parameters with said vertical gradient;

(f) comparing said determined column data parameters with said horizontal gradient; and

,

(g) selecting a split direction for splitting said image in accordance with the comparisons of step (e) and step (f).

35. The method of claim 34, wherein step (a) and step (b) comprise the steps of determining a vertical and horizontal luminance value for each of said rows and columns in accordance with average luma values of said pixels forming said rows and columns.

36. The method of claim 34, wherein step (e) and step (f) comprise the steps of:

(h) determining a vertical error term in accordance with the difference between said determined row data parameters and said substantially uniform vertical gradient; and

,

(i) determining a horizontal error term in accordance with the difference between said determined column data parameters and said substantially uniform horizontal gradient.

37. The method of claim 36, wherein step (g) comprises the further step of splitting said image vertically if said horizontal error term in greater than said vertical error term.