Adaptive digital video compression system

• US 4,868,653 A
• Filed: 10/05/1987
• Issued: 09/19/1989
• Est. Priority Date: 10/05/1987
• Status: Expired due to Term

• Current Assignee: Intel Corporation, RCA Corporation
• Original Assignee: Intel Corporation
• Inventors: Keith, John M., Simon, Allen H., Golin, Stuart J., Astle, Brian
• Primary Examiner(s): Groody, James J.
• Assistant Examiner(s): Kostak, Victor R.
• Application Number:
  US07/104,457
• Time in Patent Office: 715 Days
• Field of Search: 358/133, 358/141, 358/105, 358/136, 358/135, 358/260, 358/261, 382/56
• US Class Current: 375/240.23
• 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 for encoding a digital motion video signal comprising:

compressing a first frame of a sequence of frames of said motion video signal by means of a compressor having variable thresholds in accordance with a given compression procedure;

compressing a second frame and at least one further frame of said sequence by means of a compressor having variable thresholds in accordance with a different compression procedure;

monitoring the number of bytes per frame;

estimating the decoding time per frame;

adjusting said compressor threshold in accordance with said number of bytes per frame and said estimated decoding time per frame; and

forming an output signal from said compressed frames and including an identification code signifying each compression procedure used in each frame.

2. A method for compressing a digital motion video signal comprising:

compressing said signal with a compressor having a variable threshold;

monitoring the number of bytes per frame;

estimating the decoding time per frame; and

adjusting said compressing threshold in accordance with said number of bytes per frame and said estimated decoding time per frame to provide a processed output signal.

3. The method set forth in claim 2 wherein the step of estimating decoding time comprises generating a sum, T, of products given by ##EQU2## wherein each term A_i represents the total number of times a particular decoding action is performed and the term K_i represents the maximum decoding time associated with the action.

4. The method set forth in claim 2 wherein the step of estimating decoding time, estimates the decoding time for each frame.

5. The method set forth in claim 2 wherein the step of estimating decoding time, determines a running estimate over a plurality of successively encoded frames.

6. Apparatus for compressing a frame of video data, comprising:

means for applying said frame of video data;

means, including means coupled to said means for applying said frame, for hierarchically determining fill data including absolute fill data, DPCM fill data and corresponding region descriptive parameters;

means for generating header data including data descriptive of the type of frame data and information corresponding to the amount of region and fill data generated to describe the frame of data;

means for independently examining each of the types of fill data on an entire frame basis, and the region descriptive parameters for the entire frame, to determine respective optimum variable length code sets, for each type of data, forming a table of variable length code sets, and encoding the respective types of fill and region header data according to the optimum variable length code determined for the respective type of data.

7. The apparatus set forth in claim 6 wherein the means, including means for hierarchically determining fill data, further includes means for subsampling said frame of data to produce a reduced frame of data having fewer pixel values than said frame of data, and for applying said reduced frame of data to said means for hierarchically determining fill data.

8. The apparatus set forth in claim 6 wherein said means for hierarchically determining fill data also generates relative fill data and corresponding region descriptive parameters.

9. A method of compressing a succession of frames of video data representing moving images, comprising:

dividing a frame of video data into regions; and

generating region parameters descriptive of the position and size of respective regions;

comparing pixel values in each region with corresponding pixel values in a like sized region from a previously occurring frame to develop respective pixel differences;

determining relative fill data descriptive of pixel differences for respective region;

determining DYAD ill data for respective regions in which relative fill data cannot be determined;

determining DPCM fill data for respective regions in which relative fill data cannot be determined and for which DYAD fill data cannot be determined; and

variable length coding said relative fill data, said DYAD fill data, said DPCM fill data; and

corresponding region parameters.

10. The method set forth in claim 9 wherein said frame is divided into regions and each region is examined to determine relative fill data, and if relative fill data cannot be determined with predetermined tolerances successively subdividing each region into subregions and examining each subregion to determine relative fill data, and if relative fill data cannot be determined after said subregions are divided into subregions of predetermined minimum size, then determining DYAD or DPCM fill data for said subregion of predetermined minimum size.

11. The method of claim 9 further including the steps of:

estimating decoding time of the region descriptive parameters and fill data, and comparing the estimated decoding time to a predetermined value; and

if the estimated decoding time is greater than said predetermined value, repeating the steps of claim 10 with different tolerances established for generating said fill data.

12. The method set forth in claim 11 wherein the step of estimating decoding time comprises generating a sum, T, of products given by ##EQU3## wherein each term A_i represents the total number of times a particular decoding action is performed and the term K_i represents the maximum decoding time associated with the action.

13. The method set forth in claim 12 wherein the step of generating said sum of products comprises forming a sum of products of (a) the number of regions described by respective types of fill data times respective first constants, (b) the number of pixels included in each type of region times respective second constants, and (c) the number of rows of pixels included in respective types of regions times respective third constants, and comparing said sum of products to a predetermined value, and wherein type of region refers to the type of fill data used to describe pixels in respective regions.

14. The method set forth in claim 11 wherein the step of estimating decoding time, determines a running estimate over a plurality of successively encoded frames.

15. A method of compressing a frame of video data, represented by an array of rows and columns of pixel values, comprising:

(A) dividing said array into regions and generating region parameters descriptive of the size and location of respective regions within said array;

(B) determining absolute fill data describing respective regions;

(C) determining DPCM fill data describing respective regions for which absolute fill data cannot be determined;

(D) variable length encoding said absolute and DPCM fill data and corresponding region descriptive parameters;

(E) determining an estimate of decompression time from said variable length encoded absolute and DPCM fill data and corresponding region descriptive parameters;

(F) providing said variable length encoded fill data and corresponding region parameters if said estimate is less than a predetermined value, and if not, repeating steps (A)-(F) using a different tolerance in determining said absolute fill data.

16. The method set forth in claim 15 wherein the step of determining an estimate of decompression time comprises generating a sum, T, of products given by ##EQU4## wherein each term A_i represents the total number of times a particular decoding action is performed and the term K_i represents the maximum decoding time associated with the action.

17. The method set forth in claim 16 wherein the step of generating said sum of products includes forming a sum of products of (a) the number of regions described by respective types of fill data times respective first constants, (b) the number of pixels included in the respective types of regions times respective second constants and (c) the number of rows of pixels included in respective types of regions times respective third constants, and comparing said sum of products to a predetermined value, wherein `type of region` refers to the type of fill data used to describe pixels in respective regions.

18. A method of compressing a frame or a succession of related frames of video data, comprising:

(A) resampling a frame of video data including N rows and M columns of values to a reduced frame of video data of R rows and S columns of values, where N, M, R and S are integers and R is less than N and S is less than M;

(B) dividing said reduced frame into regions of pixel values and generating region parameters descriptive of the position and size of respective regions within a frame;

FOR STILL FRAMES;

(C) determining absolute fill data describing respective regions;

(D) determining DPCM fill data for regions for which absolute fill data cannot be determined;

FOR FRAMES OF A SUCCESSION OF RELATED FRAMES;

(E) determining relative fill data describing respective regions;

(F) determining absolute fill data describing respective regions for which relative fill data cannot be determined;

(G) determining DPCM fill data for respective regions for which neither relative nor absolute fill data can be determined;

For both still frames and frames of a succession of related frames;

(H) encoding the region parameters, absolute fill data, relative fill data and DPCM fill data with variable length codes;

(I) estimating decoding time of respective frames of the variable length encoded data; and

(J) providing the variable length encoded data as compressed video output data if the estimated decoding time is less than a predetermined value and if not, repeating steps (B) thru (J) with different tolerances applied to the determination of absolute and relative fill data.

19. The method of claim 18 wherein the step of dividing said reduced frame comprises dividing the array of data representing the reduced frame in half to develop regions and further dividing each region in half, and after each division examining the data of respective regions to determine if fill data can be generated, and if so, terminating subdivision of such region, and if fill data cannot be generated for a region after subdivision to a region of predetermined minimum size, DPCM encoding the pixel values of said region of minimum size.

20. The method set forth in claim 18 wherein the step of estimating decoding time comprises generating a sum, T, of products given by ##EQU5## wherein each term A_i represents the total number of times a particular decoding action is performed and the term K_i represents the maximum decoding time associated with the action.

21. The method of claim 20 wherein the step of generating said sum of products includes forming a number corresponding to the sum of products of (a) the number of regions described by each type of fill data times respective first constants (b) the number of pixels included in each type of region times respective second constants, and (c) the number of rows of pixels included in the respective types of regions times respective third constants, and comparing the sum of products to a threshold value.

22. The method set forth in claim 18 wherein the step of estimating decoding time, estimates the decoding time for each frame.

23. The method set forth in claim 18 wherein the step of estimating decoding time, determines a running estimate over a.plurality of successively encoded frames.

24. A method for compressing a frame or succession of frames of video signal, each frame being represented by an array of rows and columns of pixel value samples, comprising:

(A) dividing said array into regions;

(B) for each region generating coefficients for a bilinear polynomial of the form Ax+By+C to describe each pixel value in said region, where A, B, and C are said coefficients and x and y are relative coordinate axes along said row and columns respectively;

(C) generating respective pixel values using said bilinear polynomial for each pixel in a respective region;

(D) comparing pixel values generated using said bilinear polynomial with corresponding actual pixel values in said region to determine respective error values;

(E) determining an aggregate error value of the error values over said region, and comparing the aggregate error value to a first threshold value;

(F) performing a boundary value check on comparing ones of said error values corresponding to pixel values located around the periphery of said region to determine if said ones of said error values satisfy predetermined constraints;

(G) generating a code including an indication of the size and location of the region within said array and said coefficients on the condition that said aggregate error value is less than said first threshold and said error values corresponding to pixel values located around the periphery of said regions satisfy said predetermined constraints, and if these conditions are not satisfied dividing said region into smaller regions and performing steps (B)-(C) on said smaller regions.

25. The method set forth in claim 24 wherein the step of determining an aggregate error value comprises generating the mean square error of the error values over said region.

26. The method set forth in claim 24 wherein the step of generating coefficients comprises performing a least square fit on the pixel values in said region.

27. A method for compressing a succession of frames of video signal, each frame being represented by an array of rows and columns of pixel value samples, comprising:

(A) dividing a frame of pixel values into regions;

(B) comparing pixel values in said region with corresponding pixel values in a like sized region of a previously occurring frame to form a region of corresponding pixel difference values;

(C) generating coefficients for a bilinear polynomial of the form Ax+By+C to describe each pixel difference value in said region, where A, B and C are said coefficients and x and y are relative coordinate axes along said rows and columns respectively;

(D) generating respective pixel difference values using said bilinear polynomial;

(E) comparing pixel difference values generated using said bilinear polynomial with corresponding pixel difference values in said region to generate error values;

(F) forming an aggregate error value for said error values over the region and comparing said aggregate error value to a first threshold value;

(G) performing a boundary check on ones of said error values corresponding to pixels located around the periphery of said region, to determine if said ones of said error values satisfy predetermined constraints; and

(H) generating a code descriptive of the size and position of said region within said array and including said coefficients on the condition that said aggregate error value is less than said first threshold value and said ones of said error values corresponding to pixels located around the periphery of said region satisfy said predetermined constraints, and if these conditions are not satisfied performing steps (A)-(H) on said region.

28. The method set forth in claim 27 further including

if after repeated performance of steps (A)-(H) said conditions are not satisfied determining a translated region in said previously occurring frame and performing steps (A)-(H) using said region and said translated region.

29. The method set forth in claim 27 wherein the step of forming an aggregate error value comprises generating the mean square error of said error values.

30. The method set forth in claim 27 wherein the step of generating coefficients comprises performing a least square fit on said pixel difference values.

31. A digital video encoder, comprising:

a source for providing a frame of digital video signal to be encoded;

compressor means for encoding said frame by region transformation to provide a plurality of region codes representative of picture element regions of varying areas;

quantizing means for quantizing said region codes;

area determining means coupled to said compressor means for controlling said quantizing means as a predetermined function of said area.

32. The digital video encoder set forth in claim 31 wherein said quantizing means quantizes region code samples into samples having different numbers of bits, with region code samples corresponding to smaller regions being quantized to samples with lesser numbers of bits than region codes corresponding to larger regions.

33. The digital video encoder set forth in claim 32 wherein the means for quantizing includes means for truncating bits of said region codes.

34. A method of compressing a frame of video data comprising:

hierarchically determining fill data including absolute fill data, DPCM fill data and corresponding region descriptive parameters for said frame;

independently examining, on a frame basis, each of the types of fill data, and the region descriptive parameters, for determining respective optimum variable length code sets for encoding the respective types of data;

variable length encoding the respective types of fill data, and the region descriptive parameters according to the optimum variable length code sets determined.

35. Apparatus for compressing a frame of video data, comprising:

means for applying said frame of video data;

means, including means coupled to said means for applying said frame, for hierarchically determining fill data including relative fill data, DPCM fill data, DYAD fill data and corresponding region descriptive parameters;

means for independently examining each of the types of fill data on an entire frame basis, and the region descriptive parameters for the entire frame, to determine respective optimum variable length code sets for each type of data, from a table of variable length code sets, and encoding the respective types of fill and region data according to the optimum variable length code determined for the respective type of data.

36. A method for compressing frames of video data represented by arrays of pixel values arranged in rows and columns wherein each array is successively split into regions by dividing said array and said regions substantially in half, either vertically or horizontally between said rows and columns respectively, until a region is found for which pixel values therein can be described, within predetermined tolerances, by a region specific code, the direction, horizontal or vertical in which a region is split being determined by examining the pixel values in a respective region to ascertain the distribution of relative pixel differences within said region and dividing the region in the direction which tends to isolate the majority of pixels exhibiting relative differences on one side of the split.

37. The method set forth in claim 36 wherein the step of ascertaining the distribution of relative pixel differences includes:

subtracting each pixel value in a region from each of its immediate adjacent pixel values to generate respective differences;

comparing said differences to a threshold value;

counting the number of differences between pixel values in adjacent rows which exceed said threshold value, to generate a first number;

counting the number of differences between pixel values in adjacent columns which exceed said threshold value, to generate a second number;

comparing said first number with said second number; and

wherein said region is split horizontally if said first number exceeds said second number and vertically if said second number exceeds said first number.

38. The method set forth in claim 36 wherein the step of ascertaining the distribution of relative pixel differences includes:

detecting edges in the region to be split;

determining the distribution of edges in each quadrant of the region to be split;

comparing the edge distributions in said quadrants; and

determining a split direction, depending on said comparison, which confines the two quadrants having the largest edge distributions to one side of the split.

39. The method set forth in claim 38 further including:

determining a split direction which tends to divide the region to be split into subregions having a predetermined preferred height/width aspect ratio if the quadrant edge distributions preclude confining the quadrants having the largest edge distributions to one side of a split.

40. A method for compressing frames of video data represented by arrays of pixel values arranged in rows and columns wherein each array is successively split into by dividing said array and said regions either horizontally or vertically between said rows and columns respectively until a region is found for which pixel values therein can be described, within predetermined tolerances, by a region specific code, the direction, horizontal or vertical, in which a region is split being determined by

(A) generating a region specific code for a respective region;

(B) generating pixel values for said region using said region specific code;

(C) determining values representing errors between the generated pixel values and corresponding region pixel values;

(D) determining an aggregate vertical error value from said errors;

(E) determining an aggregate horizontal error value from said errors;

(F) comparing said vertical and horizontal aggregate error values and splitting the region horizontally or vertically in accordance with the result of said comparison.