Differential order video encoding system

• US 5,739,861 A
• Filed: 05/06/1996
• Issued: 04/14/1998
• Est. Priority Date: 05/06/1996
• Status: Expired due to Term

• Current Assignee: Music John D
• Original Assignee: Music John D
• Inventors: Music, John D.
• Primary Examiner(s): Chin, Tommy P.
• Assistant Examiner(s): DIN, LUANNE PAN
• Application Number:
  US08/642,900
• Time in Patent Office: 708 Days
• Field of Search: 348/420, 348/421, 348/660, 348/409, 348/391, 345/153, 382/238, 382/251
• US Class Current: 375/240.01
• CPC Class Codes: H04N 19/10 using adaptive coding
• 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/186 the unit being a colour or a chrominance component
• 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

Abstract

A television communications method and system particularly suitable for high definition, with narrow-band applications as for specialized broadcasting systems and video links using a block coding procedure to produce a system not wasteful of bandwidth caused by transmitting redundancies from multiple sources which do not contribute to picture quality. A differential order video encoding method (DOVE) provides a video coding scheme based on the need for true high-quality video with real-time TV encoding and delivery in fifty per cent of the bandwidth of the 4.5 MHZ vestigial sideband suppressed television system in universal use. Efficient coding algorithms, based on the finding and eliminating multiple source redundancies, characterizes the redundancies and creates, in real-time, an efficient set of codes for encoding only the information that is different, eliminating the need for full 4.5 MHZ bandwidth.

Claims

1. In a digitally coded, data compressed television system, the improvement for high definition with narrow bandwidth, comprising:

means for calculating adjacent pixel Y luminosity differential,

means for generating nonlinear quantization of the adjacent pixel Y luminosity differential,

means for variable bit length encoding of said nonlinear quantized pixel Y luminosity, and

means for quantizing and encoding YO differentials, using YO of previous block where first YO in each row is absolute YO wherein small blocks are characterized as blocks where the quantized differential Y for all 9 pixels is within +/-1 with respect to quantized YO, medium small blocks have quantized differentials within the range of +/-5, and medium large blocks have all 9 quantized differentials within the range of +/-26, while large blocks have all 9 quantized differentials in the full range.

2. In a digitally coded, data compressed television system, the improvement for high definition with narrow bandwidth, comprising:

means for calculating adjacent pixel Y luminosity differential,

means for generating nonlinear quantization of the adjacent pixel Y luminosity differential,

means for variable bit length encoding of said nonlinear quantized pixel Y luminosity,

means for transmitting the encoded signal for remote reception, and

means for receiving and decoding the transmitted signal using an integer arithmetic algorithm where

space="preserve" listing-type="equation">red=Y+(178*(V-64)/128)

space="preserve" listing-type="equation">grn=Y+(89*(V-64)/128)-(43*(U-64)/128)

space="preserve" listing-type="equation">blu=Y+(222*(U-64)/128).

3. A high definition, low bandwidth, real-time digitally coded, data compressed television system, comprising:

means for converting an RGB analog television signal to digital YUV coordinates by converting x-bit RGB values to x-bit YUV values in accordance with an integer arithmetic algorithm based on world standard RGB ratios including an analog to digital,

means for differential quantizing and encoding U and V values based on a major 6×

6 block and four minor 3×

3 blocks,

means for luminosity differential quantizing for encoding Y information using a 3×

3 block and Y components encoding using one of the following techniques;

(a) averaging Y in 3×

3 block (YO), (b) quantizing differential Y for all 9 pixels within +/-1 with respect to quantized YO, (c) quantizing luminosity differentials within the range of +/-5, (d) quantizing all 9 quantized luminosity differentials within the range of +/-26, (e) quantizing luminosity differentials having all 9 pixels in the full range, and (f) mapping Y1, Y2based on allowable error,

means for subtracting the luminosity of adjacent pixels where dY=(Yn-1), resulting in doubling the number of bits needed to represent dY compared to Y,

means for finding YOs as the sum of all Ys in 3×

3 blocks divided by 9 approximated with integer arithmetic using 1/16+1/32+1/64,

means for quantizing and encoding YO differentials, using YO of previous block where first YO in each row is absolute YO wherein small blocks are characterized as blocks where the quantized differential Y for all 9 pixels is within +/-1 with respect to quantized YO, medium small blocks have quantized differentials within the range of +/-5, and medium large blocks have all 9 quantized differentials within the range of +/-26, while large blocks have all 9 quantized differentials in the full range,

means for transmitting the coded signal for remote reception, and

means for receiving and decoding the transmitted signal using an integer arithmetic algorithm where

space="preserve" listing-type="equation">red=Y+(178*(V-64)/128)

space="preserve" listing-type="equation">grn=Y±

(89*(V-64)/128)-(43*(U-64)/128)

space="preserve" listing-type="equation">blu=Y+(222*(U-64)/128).

4.

4. A high definition system according to claim 3, wherein:

said means for converting with an integer arithmetic algorithm comprises an analog to digital converter.

5. A coding method for high definition, narrow bandwidth video, comprising the steps of:

converting a color video signal to digital Y U V values,

non-linear differential quantizing to arrange individual pixels in major blocks, with each said block further arranged into minor blocks, whereby U and V values for both the major block and minor blocks are the sum of all U'"'"'s and V'"'"'s in a minor block divided by the number of pixels in the minor block to provide values of U and V subsampled with respect to Y,

quantizing the U and V values according to dx where dx means either dY or dV, and

space="preserve" listing-type="tabular">______________________________________ if abs(dx) >

0 and abs(dx) <

2 then dx <

--- 1 * (sgn(dx)) if abs(dx) >

1 and abs(dx) <

5 then dx <

--- 3 * (sgn(dx)) if abs(dx) >

4 and abs(dx) <

10 then dx <

--- 7 * (sgn(dx)) if abs(dx) >

9 and abs(dx) <

17 then dx <

--- 13 * (sgn(dx)) if abs(dx) >

16 and abs(dx) <

32 then dx <

--- 24 * (sgn(dx)) if abs(dx) >

31 and abs(dx) <

47 then dx <

--- 39 * (sgn(dx)) if abs(dx) >

46 then dx <

--- 54 * (sgn(dx)), ______________________________________

testing for overflow and underflow from the quantizing whereby if dx+previous dx>

127 or <

0 then dx<

next lower quantize value, then testing again,

differencing the major block UVs from the preceding quantizing and differencing the minor blocks from the large block and quantizing, and if the difference of any one of the minor blocks exceeds a threshold, encoding that minor block encoded together with the major block,

assigning a single bit associated with a major block to indicate if the encoding is for a single large block or if the encoding is for the large block plus one or more small blocks,

encoding quantized U and V differentials encoded both for the major blocks and for any minor blocks whose values are different from the major blocks by an adjustable error (UV(err)),

luminosity differential quantizing for encoding Y information using a minor block and the Y components,

encoding using one of the following different techniques;

(a) averaging Y in 3×

3 block (YO), (b) quantizing differential Y for all 9 pixels within +/-1 with respect to quantized YO, (c) quantizing luminosity differentials within the range of +/-5, (d) quantizing all 9 quantized luminosity differentials within the range of +/-26, (e) quantizing luminosity differentials having all 9 pixels in the full range, and (f) mapping Y1, Y2 based on allowable error,

subtracting the luminosity of adjacent pixels where dY=(Yn-Yn-1) resulting in doubling the number of bits needed to represent dY compared to Y,

finding YOs as the sum of all Ys in minor blocks divided by the number of pixels therein,

quantizing and encoding YO differentials using YO of previous block where first YO in each row is absolute YO wherein small blocks are characterized as blocks where the quantized differential Y for all pixels is within +/-1 with respect to quantized YO, and medium small blocks have quantized differentials within the range of +/-5, and medium large blocks have all quantized differentials with the range of +/-26, while large blocks have all quantized differentials in the full range, and

formatting encoded data by bit packing and organizing the coded data to accommodate video signal format.

6. A coding method according to claim 5, and further including:

run length coding the U and V block characterization bits to eliminate redundant zeros.

7. A coding method according to claim 5, wherein said major blocks are 6×

6 blocks and said minor blocks are 3×

3 blocks.

8. A coding method according to claim 5, wherein said major blocks are 8×

8 blocks and said minor blocks are 4×

4 blocks.

9. A method according to claim 5, and further comprising:

bit mapping blocks based on allowable error to provide an additional level of compression of Y information, by luminance partitioning the minor block into two values of luminosity Y1 and Y2, Y1 being the sum of all pixels in the block whose value is greater than YO, divided by the quantity of such pixels, and Y2 is the sum of all pixels in the block whose value is equal to or less than YO divided by the quantity of such pixels, the divisor in both cases always being an integer in the range of 1 to 8 according to the following logic;

space="preserve" listing-type="equation">if locnt>

0 then Y2=Y2/locnt

space="preserve" listing-type="equation">if hicnt>

0 then Y1=Y1/hicnt

space="preserve" listing-type="equation">if hicnt=0 or locnt=0 then Y1=cpt;

Y2=cpt,

using simplified integer arithmetic to obtain values for Y1, the average Y for all pixels exceeding YO, and Y2, and

generating a 9 bit map in which a 1 means the pixel will be represented by Y1 and 0 means the pixel will be represented by Y2.

11. A method according to claim 9, and further including:

remapping in a process step using a lookup table to convert the bit maps into variable bit length codes based on expected probability of occurrence, and the remap process is based on the assumption of allowable error in disallowing certain bit maps that are (1) low probability, and (2) not likely to cause discernable error, said maps being of the form ##STR2## wherein either of these maps is generated only for low amplitude blocks, with an illogical map bit pattern most likely caused by noise, the lookup table for remap comprising 9 bits in 512 possible maps, and outputs of variable bit length codes representing 84 possible maps.

10. Coding means for high definition, narrow bandwidth video transmission, comprising:

means for converting a color video signal to digital Y U V values,

means for non-linear differential quantizing to arrange individual pixels in major blocks, with each said block further arranged into minor blocks, whereby U and V values for both the major block and minor blocks are the sum of all U'"'"'s and V'"'"'s in a minor block divided by the number of pixels in the minor block to provide values of U and V subsampled with respect to Y,

means for quantizing the U and V values according to dx where dx means either dU or dV, and

space="preserve" listing-type="tabular">______________________________________ if abs(dx) >

0 and abs(dx) <

2 then dx <

--- 1 * (sgn(dx)) if abs(dx) >

1 and abs(dx) <

5 then dx <

--- 3 * (sgn(dx)) if abs(dx) >

4 and abs(dx) <

10 then dx <

--- 7 * (sgn(dx)) if abs(dx) >

9 and abs(dx) <

17 then dx <

--- 13 * (sgn(dx)) if abs(dx) >

16 and abs(dx) <

32 then dx <

--- 24 * (sgn(dx)) if abs(dx) >

31 and abs(dx) <

47 then dx <

--- 39 * (sgn(dx)) if abs(dx) >

46 and dx <

--- 54 * (sgn(dx)), ______________________________________

means for testing for overflow and underflow from the quantizer, whereby if dx+previous x>

127 or <

0 then dx<

next lower quantize value, then testing again,

means for differencing the major block UVs from the preceding quantizing and differencing the minor blocks from the large block and quantizing, and if the difference of any one of the minor blocks exceeds a threshold, encoding that minor block encoded together with the major block,

means for assigning a single bit associated with a major block to indicate if the encoding is for a single large block or if the encoding is for the large block plus one or more small blocks,

means for encoding quantized U and V differentials encoded both for the major blocks and for any minor blocks whose values are different from the major blocks by an adjustable error (UV(err)),

means for luminosity differential quantizing for encoding Y information using a minor block and the Y components,

means for encoding using one of the following different techniques;

(a) averaging Y in 3×

3 block (YO), (b) quantizing differential Y for all 9 pixels within +/-1 with respect to quantized YO, (c) quantizing luminosity differentials within the range of +/-5, (d) quantizing all 9 quantized luminosity differentials within the range of +/-26, (e) quantizing luminosity differentials having all 9 pixels in the full range, and (f) mapping Y1, Y2 based on allowable error,

means for subtracting the luminosity of adjacent pixels where dY=(Yn-Yn-1) resulting in doubling the number of bits needed to represent dY compared to Y,

means for finding YOs as the sum of all Ys in minor blocks divided by the number of pixels therein,

means for quantizing and encoding YO differentials using YO of previous block where first YO in each row is absolute YO wherein small blocks are characterized as blocks where the quantized differential Y for all pixels is within +/-1 with respect to quantized YO, and medium, small blocks have quantized differentials within the range of +/-5, and medium large blocks have all quantized differentials with the range of +/-26, while large blocks have all quantized differentials in the full range, and

means for formatting encoded data by bit packing and organizing the coded data to accommodate the video signal format.