United States Patent [19J
`Widergren et al.
`
`[11]
`
`[45]
`
`4,302,775
`Nov. 24, 1981
`
`[75]
`
`[54] DIGITAL VIDEO COMPRESSION SYSTEM
`AND METHODS UTILIZING SCENE
`ADAPTIVE CODING WITH RATE BUFFER
`FEEDBACK
`Inventors: Robert D. Widergren, Saratoga;
`Wen-Hsiung Chen, Sunnyvale;
`Stanley C. Fralick, Saratoga; Andrew
`G. Tescher, Claremont, all of Calif.
`[73] Assignee: Compression Labs, Inc., San Jose,
`Calif.
`[21] Appl. No.: 969,991
`[22] Filed:
`Dec. 15, 1978
`[51]
`Int. CJ.3 ........................ H04N 7/12; H04N 9/32;
`G06F 15/20; G08C 9/00
`[52] U.S. Cl ....................................... 358/136; 358/13;
`340/347 DD; 364/514; 364/515; 364/582
`[58] Field of Search ............... 364/514, 515, 576, 582;
`358/12, 13, 133, 138, 260, 261; 340/347 DD
`References Cited
`U.S. PATENT DOCUMENTS
`3,795,763 3/1974 Golding eta!. ................. 358/135 X
`3,984,626 10/1976 Mounts eta!. ...................... 358/135
`4,005,411 1/1977 Morris ......................... 340/347 DD
`4,047,221 9/1977 Yasuda eta!. ...................... 358/136
`4,051,530 9/1977 Kuroda eta!. ...................... 358/136
`4,054,909 10/1977 Kojima eta! ......................... 358/13
`4,060,797 11/1977 Maxwell eta! ................. 325/419 X
`4,125,861 11/1978 Mounts et a!. ...................... 358/133
`4,168,513 9/1979 Hains eta!. ......................... 358/261
`4,179,710 12/1979 Ishiguro eta!. .................. 358/13 X
`
`[56]
`
`OTHER PUBLICATIONS
`Image Data Compression by Predictive Coding II: En(cid:173)
`coding Algorithms Bah! & Kobayashi: IBM J. Res.
`Develop., Mar. 1974, pp. 172-179.
`Frame-to-Frame Coding of Television Pictures Using
`Two-Dimensional Fourier Transforms: Haskell: IEEE
`Transactions on Info. Theory: vol. IT-20, No. I, pp.
`119-120: Jan. 74.
`Spahal Transform Coding of Color Images: Pratt:
`IEEE Transactions on Comm. Technology, vol. Co(cid:173)
`m-19, No. 6, Dec. 71, pp. 980-992.
`Goertzel et al., Two-Dimensional Data Compression &
`Decompression System; Aug. 7, 1979.
`Application of Fourier-Hadamard Transformation to
`
`Bandwidth Compression-Pratt & Andrews Proc. Poly(cid:173)
`technic Institute of Brooklyn, 1969, pp. 56-68.
`Hadamard Transform Image Coding, Pratt, Kane, An(cid:173)
`drews, Proc. IEEE, vol. 57, No. 1, Jan. 69, pp. 58-68.
`Television Bandwidth Reduction by Encoding Spatial
`Frequencies, Andrews & Pratt, Journal SMPTE, vol.
`77, No. 12, Dec. 1968, pp. 1279-1281.
`Television Bandwidth Reduction by Fourier Image
`Coding; Andrews & Pratt, Paper Delivered to 103rd
`Technical Conference SMPTE, May 5-10, 1968.
`Transform Image Coding, Andrews & Pratt: Proc.
`Symposium on Computer Processing in Communica(cid:173)
`tions, Polytechnic Institute of Brooklyn, Apr. 8-10,
`1969, pp. 63-84.
`Primary Examiner-James W. Moffitt
`Assistant Examiner-Aristotelis M. Psitos
`Attorney, Agent, or Firm-David B. Harrison.
`
`ABSTRACT
`[57]
`A digital video compression system and its methods for
`compressing digitalized video signals in real time at
`rates up to NTSC color broadcast rates are disclosed.
`The system compressor receives digitalized video
`frames divided into subframes, performs in a single pass
`a spatial domain to transform domain transformation in
`two dimensions of the picture elements of each sub(cid:173)
`frame, normalizes the resultant coefficients by a normal(cid:173)
`ization factor having a predetermined compression ratio
`component and an adaptive rate buffer capacity control
`feedback component, to provide compression, encodes
`the coefficients and stores them in a first rate buffer
`memory asynchronously at a high data transfer rate
`from which they are put out at a slower, synchronous
`rate. The compressor adaptively determines the rate
`buffer capacity control feedback component in relation
`to instantaneous data content of the rate buffer memory
`in relation to its capacity, and it controls the absolute
`quantity of data resulting from the normalization step so
`that the buffer memory is never completely emptied and
`never completely filled. In expansion, the system essen(cid:173)
`tially mirrors the steps performed during compression.
`An efficient, high speed decoder forms an important
`aspect of the present invention. The compression sys(cid:173)
`tem forms an important element of a disclosed color
`broadcast compression system.
`
`7 Claims, 30 Drawing Figures
`
`1
`
`SAMSUNG 1012
`
`

`
`30
`
`DECODER
`VITERBI
`
`-0
`
`N
`N
` ........
`
`-\
`
`00 -
`
`0
`
`I
`I
`MEDIUM
`BANDWIDTH I
`I
`LIMITED
`I
`I
`
`L_
`I
`I
`I
`14--+
`
`CONVOLUTIONAL
`
`CODER
`
`DECODER
`ADAPTIVE
`
`SCENE
`
`34
`
`CODED AUDIO
`
`CONVERTER
`
`FILTER
`
`a
`D/A
`
`EXPANDER J2
`
`42
`
`20
`
`COMPRESSOR 10
`
`18
`
`y
`
`VIDEO
`NTSC
`
`INTERFACE
`
`AUDIO
`
`AUDIO
`
`44
`
`16
`
`FIG. I
`
`CODED LUMINANCE
`
`ADAPTIVE
`
`CODER
`
`SCENE
`
`TRANSFORM
`
`COSINE
`2-D
`
`y
`
`22
`
`CODED AUDIO
`
`ENCODER
`
`PCM
`
`SEPARATOR
`
`INTERFACE
`
`VIDEO
`
`a
`
`VIDEO
`
`AUDIO
`
`/
`
`2
`
`

`
`Ul
`-......)
`-......)
`..N
`0
`~ --w
`
`N
`N
`0 ........
`N
`n .....
`n
`::r
`Vl
`
`00 -
`
`-\
`
`0
`
`\ 60, 64.
`
`94,98.
`
`114
`
`CONfROL
`
`74188
`16 X 128
`PROM
`
`127
`
`4
`
`COUNTER
`
`4-BIT
`
`RESET
`
`CLOCK
`
`DATA OUT
`
`~6
`
`f(j. k)
`
`TRANSFORM
`
`COSINE
`INVERSE
`
`F(u, v)
`
`SHUFFLE
`
`29
`ADD
`a
`
`MULT.
`
`58;
`
`34
`
`y
`
`56.)
`
`NORMALIZA-
`INVERSE
`
`TION
`
`•
`
`FN(u,v)
`
`DECODING
`
`OUT
`RATE
`ABLE
`VARI-
`
`54.)
`
`BUFFER
`RATE
`
`I
`
`~~ IN
`RATE
`FIXED
`
`___. CHANNEL
`
`9
`
`SHUFFLE
`
`ADD
`a
`
`8
`
`14
`
`DATA IN
`FIG. 5
`F
`IG. 2
`
`~
`
`!----ou
`FIXED R ATE
`
`T
`
`52)
`
`L5o
`
`48J
`
`20
`
`46J
`
`'\
`
`BUFFER
`
`RATE
`I
`
`RATE
`ABLE
`VARI-
`
`IN
`
`CODING
`
`FN(u,v)
`
`NORMALIZATION ~ QUANTIZATION
`
`FN(u,v)
`
`F(u,vt
`
`f_
`
`i's
`TRANSFORM
`
`~ COSINE
`
`3
`
`

`
`N
`N
`0 ......,
`w
`.......
`{i)
`{I)
`::r
`(I'J
`
`.....
`00
`\0
`~ .....
`z 0 :::
`::s
`(1)
`f"'1'-
`~
`~
`
`f""''o.
`
`N
`
`Vl
`~
`
`SYNC
`CLOCK
`
`DATA
`
`SYNC
`CLOCK
`
`DATA
`
`84
`
`B. LUMINANCE DECODER
`
`\ 36
`
`100
`
`FIG. 3
`
`BLOCK SYNC-------L~~=~
`
`LINE SYNC..:rJ-------1
`
`CLOCKE-------~~~~~
`
`A. LUMINANCE
`
`I
`I
`I
`I
`I
`I
`I
`' I
`I
`
`SAMPLES
`
`VIDEO
`
`18
`
`'
`
`68
`
`BLOCK
`FRAME
`CLOCK
`
`4
`
`

`
`’U.S. Patent
`
`Nov. 24, 1981
`
`:104‘ul-eeLuS
`
`27.
`
`4,302,775
`
`IHmH.$»ara.V‘.\54.H|Vl.VlIxfl..‘\l,HM.“
`hH«N_nn2.§..fi.n.I_V
`%i«....>I4...H.w}o»Hv:w>M
`Ln.VIx|l..A.V
`“...o./fi\Nu1fir/IE.
`
`2.m\hf/§ba I.:
`
`
`A..aVNl.§I//._.iiE..a$..N$luW§MAI¥D7HM.“.
`
`
`‘“JQ‘._‘ON&
`
`
`>9....,%..rO>.m.
`
`Mum
`
`5
`
`

`
`U.S. Patent Nov. 24, 1981
`
`Sheet 5 of 22
`
`4,302,775
`
`DATA IN
`
`A ADDRESS
`B ADDRESS
`--~=-~~ ~W=E----~
`OEA
`OEB
`
`INPUT a
`SHUFFLE
`CONTROL
`
`116
`
`16 x n
`DUAL PORT
`RAM
`
`16 x n
`DUAL PORT
`RAM
`
`118
`
`ADD/SUBTRACT
`
`120
`
`FIG. 6
`
`FIG.8
`
`r--
`
`r-
`
`RAM
`r--...140
`4Kx8
`(8x 2147) 1-
`
`ALU (n -BIT)
`
`_tn+l
`
`DATA OUT
`
`124
`
`\
`
`102.104,
`108.
`
`- RAM
`
`4K X 8
`(8x 2147)
`
`'--.142
`
`'1
`h
`
`I
`
`(VERTICAL)
`DATA OUT
`
`1521
`
`M
`
`X
`
`VERT ~ CONT.
`LOGIC
`CTR
`
`u ~ ADD. --(!l>
`
`(HORIZONTAL) I
`DATA IN
`8
`
`HOR
`A DR.
`CTR
`
`~
`~8
`
`M
`u
`X
`
`I~
`',
`I
`13
`
`~0
`
`CLOCK
`
`BANK
`WRITE
`SELECT
`
`' ,(s
`
`62,96.
`
`f-
`
`RAM
`4Kx8 ~
`~ (8x 2147}
`
`)4
`
`144
`
`f-
`
`'-
`
`RAM
`4Kx 8
`{8 X 2147) 1'-146
`
`~
`
`)
`
`158
`
`• 1a
`
`CONTROL
`CHIP SEL
`a WRITE ENABLE
`TO EACH BANK
`
`CLOCK
`
`6
`
`

`
`U.S. Patent Nov. 24, 1981
`
`Sheet 6 of 22
`
`4,302,775
`
`FIG. 7
`
`DATA IN
`
`II A ADDRESS
`B ADDRESS
`_,__-L-+-< .!!W.=.E __ -l
`
`_
`
`OEB
`
`INPUT a
`SHUFFLE
`CONTROL
`
`126
`
`16x n
`DUAL
`PORT
`RAM
`
`130
`
`16x 11
`DUAL
`PORT
`RAM
`
`128
`
`132
`
`MULTIPLIER
`I 142 B
`1---1 I
`
`•1 MULT~PLIER- ·.~
`MULT A 1
`3
`-+-....,...-~ 512x8
`I
`M U L T B ,
`A
`SELECT 13 , - - - - - -
`1140 PROM
`I
`COEFF.
`
`I
`
`. I
`134'+
`
`1
`
`I
`
`r l36
`8
`,.+--~.--....,.-~ I
`I I
`L---__,..----.....J I [n/4] 'LSZ83
`I
`I I
`I
`L ___ _:_·-"-_j - - -
`-~
`~
`
`/
`
`106, 110
`
`ADD I SUBTRACT
`
`~-BIT
`ALU
`
`138
`
`f/+"1
`
`DATA OUT
`
`7
`
`

`
`U.S. Patent Nov. 24, 1981
`
`Sheet 7 of 22
`
`4,302,775
`
`DATA IN - - · - - - - - - - - - .
`
`,_.. DATA OUT
`H-.--+.8
`172
`
`170
`
`ADDRESS
`MAP
`
`164
`
`CLOCK
`FIG. 9
`
`CONTROL
`CONTROL
`CONTROL
`(WR ITE ENABLE S
`OUTPUT ENABLE)
`
`CLOCK
`
`FIG.IO
`
`TRANSFORM PIXEL ROW
`
`TRAN.SFORM PIXEL COLUMNS
`
`8
`
`

`
`E ~ ...
`
`w
`
`RDRLS s ...
`
`RDFS RD
`
`TO ENCODER CONTROLLER 34
`
`ROC LENGTH
`
`2t0
`
`SEL SIGN
`
`"s
`
`RDRL
`
`JTZ
`
`·'
`z
`
`Ul
`-.)
`-.)
`
`1f194
`198
`
`.. ...
`
`(BUFFER)
`
`LENGTH
`
`RLS
`
`FRAME SYNC E f..-
`
`(BUFFER)
`
`LENGTH
`
`C
`FRAME SYNC E f-
`
`CODE
`
`~/
`
`~
`
`... -
`
`EN 1-
`
`REGISTER
`
`L--L
`
`\
`~ 5-BIT
`
`186
`
`188
`
`COUNTER [\_,
`
`8-BIT
`
`ZERO
`
`256 x32 1-
`
`CODE PROM
`BUN LENGTH
`
`178) f
`
`FIG. II
`
`Fe
`
`I
`
`74
`
`218
`
`Q 1-
`
`I!IB
`
`f--c
`
`Lo
`
`r--
`
`EN
`PIS REGC
`
`21-BIT
`
`~ L
`
`121
`
`I
`
`184J rl82
`
`EN f--
`
`~ r--. REGISTER
`
`00
`\0
`.......
`
`Et--
`
`RLS CODE
`
`lf192
`~196
`E
`
`(BUFFER}
`
`LENGTH
`
`EOB
`
`c
`
`c
`
`... -
`
`~190
`
`REGISTER E
`TRI STATE
`
`c EOB CODE
`
`BUFFER MEMORY
`_ SERIAL DATA TO
`
`I
`
`Q
`Q~204
`
`EN
`
`.---c
`202-._
`
`D
`
`17\
`
`v206
`
`I
`
`180
`
`5-BIT
`
`~ L
`
`~6
`
`PIS REGc f--
`21-BIT
`
`ENh
`
`~ L
`
`121 ~
`
`I
`
`CODE PROM !-
`COEFFICIENT
`
`256x32
`
`~-<r--
`
`f
`s140x~o --13
`~
`
`FIFO
`
`COEFFICIENT
`
`EFFICIENT
`
`LOAD CO
`
`'9
`
`DATA
`
`9
`
`

`
`.....
`00
`\0
`.....
`~~
`N
`~
`
`z 0
`
`..,
`en .
`~
`
`=::s
`~
`f""''-
`~
`
`(""~-
`
`SERIAL DATA
`
`LATCH
`6-BIT
`
`8
`
`8
`
`32x 6 FIFO
`
`352
`
`l
`BUFFER FIFO I
`
`FIFO
`LOAD
`
`FIFO
`SHIFT
`
`SR
`LOAD
`
`82
`
`FIFO READY FULL
`
`Sl L
`REGISTER
`
`PIS
`
`08
`FIG.I2
`FIG. 22
`CLOCK
`BIT
`_N_E_X __ T-,.-1 C
`
`xxxx
`
`XXXXXX COD E N+l
`
`X COEFFICIE NT NH
`
`I
`
`I
`
`LATCH
`
`ADDRESS
`
`COEFFICIENT N-2 = 0, COEFFICIENT N-1 = 0, COEFFICIENT N = 0
`
`_ILJLilJl_Jl_ flJLJl_
`I
`
`<r-
`
`I
`
`SEL SIGN
`
`SEL SIGN
`
`CODE N
`
`XXX
`
`XXX CODE N-1
`
`PIS REG OUT
`
`Fe {N-1}
`
`CODE N
`
`.. ;>
`
`PROM OUT CODE N-1 xxxxxxxxxx
`j---TAA--1
`COEFFICIENT N
`
`PROM ADDR
`
`X
`
`10
`
`

`
`~ -0
`
`::r
`Vl
`
`('D
`
`......
`00
`\0
`......
`~
`N
`~
`
`z 0
`
`::s
`(I)
`t-1-
`~
`~
`
`t-1-
`
`V)
`
`C! .
`
`5
`
`LENGTH
`
`NC= 0s
`RD FS
`RD EOB
`RD RL
`RD RLS
`RD C
`0z
`
`FIG. 13
`
`0s
`
`6
`
`12
`
`U't
`........)
`........)
`,..
`N
`0
`~ --w
`
`MEMORY
`TO BUFFER
`
`CLOCK
`SHIFT
`DONE
`WORD
`
`TO ENCODER
`
`SIGN
`SELECT
`
`N
`N
`0 ......,
`
`CONTROLLER
`FROM MEMORY
`
`WAIT
`
`c
`
`D
`
`238
`
`232
`
`226
`
`{"'60 MHz)
`
`CLOCK
`SHIFT
`
`224
`
`222
`
`ENCODER .-1--------JL., 01
`
`02
`
`11
`
`

`
`U.S. Patent Nov. 24, 1981
`
`Sheet 11 of 22
`
`4,302,775
`
`FIG.I4
`
`FIG.I5
`
`STATE (Q)
`
`N. STATE
`(D)
`
`CONTROL
`(C)
`
`xxxx
`
`FLAGS (F) _,A.x a..X xOJ.xl..,._ ______ _
`
`T = = DELAY THRU STATE
`LOGIC
`T2 = DURATION OF
`ACTION CHANGE
`T3 = ADDITIONAL WAIT
`FOR ACTION
`T4 = DURATION OF
`LATCH CLOSING
`
`TOTAL = 30 TO 40 ns
`
`12
`
`

`
`U.S. Patent Nov. 24, 1981
`
`Sheet 12 of 22
`
`4,302,775
`
`STATE
`01 02 03
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`FLAG
`Fe Fs Fs
`
`0
`
`0 X
`
`0 X
`I X
`0 X
`I X
`
`X
`
`0
`
`0
`
`NEXT
`STATE
`Dl D2 03
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`fiiF
`
`fils
`
`CONTROL
`0z cs Ro Nc
`
`0
`
`0
`
`0
`
`0
`
`0
`
`RST
`
`0
`
`0
`
`I
`
`0
`
`Rc
`Rc
`Rc
`0
`
`0
`
`0
`
`RST 0
`
`0
`
`0
`
`I X X
`X X X
`X X X
`I X 0
`0 X 0
`X X
`I X X
`0 X X
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`I
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`0
`0
`I RLS 0
`RL
`
`0
`
`I RST RST
`
`I
`
`0
`
`0
`RST
`RST
`
`0
`
`I
`
`I
`
`0
`
`0
`
`RE
`RE
`RE
`RF
`RF
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`FIG. 16
`
`13
`
`

`
`FROM BUFFER CONTROLLER
`ALL OTHER SIGNALS
`
`SELECT
`
`DATA
`
`256
`
`REG.
`P/S
`8-BIT
`
`Q
`
`6
`
`0
`
`-\
`
`00 -
`
`....__---+-+--SERIAL DATA
`
`242
`
`0s ----.-----+
`CONTROLLER)
`
`(ENCODER
`
`Q
`REG.
`P/S
`8-BIT
`
`8
`
`244
`
`FIFO
`32 X 8
`
`SD
`
`Sl
`
`8
`
`8-BIT
`REG.
`S/P
`
`.-------------------wE
`
`.-------------------------~cs
`
`.---------------------------~ADDRESS
`
`ROY
`DATA
`
`FULL FIFO
`FIFO SHIFT
`
`FIFO
`INPUT
`LOAD
`
`DATA
`SERIAL-"----.
`
`FIG.I7
`
`(ENCODER CONTROLLER)
`
`I
`FLIP FLOP
`SYNC BIT
`
`WORD DONE
`
`14
`
`

`
`Ul
`-.)
`-.)
`...
`N
`0
`w
`... ~
`
`N
`N
`0 ......,
`,J::.
`......
`....
`::r
`Vl
`
`('1)
`('1)
`
`N
`~
`~
`
`00 -
`}~ -\0
`
`=:s
`(D
`t-1'
`~
`~
`
`t-1'
`
`Vl .
`~
`
`296
`
`R/W ADDRESS
`
`292
`
`294
`
`WE
`
`cs
`
`Q~~-------~---_.
`Q
`
`5-BIT 851--1--1--1 D
`
`R CTR
`
`SYNC F/F
`
`011NSERT
`
`I 80
`
`WAIT Clll---(
`
`280
`
`SHIFT CLOCK
`
`CONTROLLER)
`(ENCODER 272
`
`READY F/F
`INPUT
`
`TION
`RESOLU(cid:173)
`
`RATE
`FRAME
`
`COMPRESSION
`
`MEMORY
`TO BUFFER
`
`LOAD OUT
`
`DATA CLOCK
`
`302
`
`DATA-RATE t--..:....1 --~
`
`0
`
`2-PHASE
`
`282
`
`CLOCK
`
`FIFO
`INPUT
`. LOAD
`
`276
`
`FULL ROY
`FIFO DATA
`
`FIG. IS
`
`15
`
`

`
`U.S. Patent Nov. 24, 1981
`FIG. 19
`
`Sheet 15 of 22
`
`4,302,775
`
`OUTPUT READ CYCLE
`
`8 £12 __ __,
`
`SEL
`DATA
`
`SYNC INSERTION SEQUENCE
`
`¢3 s -L__
`
`WAIT _ IL_
`LOAD~
`FIFO
`LOAD INPUT FIFO SEQUENCE
`
`ROY
`
`84
`
`WE/CS
`
`SHIFT
`OUT
`
`INPUT WRITE CYCLE
`
`16
`
`

`
`FIG. 20
`
`!--'<
`
`r--
`
`LOOK-AHEAD
`
`2902
`CARRY
`
`.....
`00
`\0
`.....
`
`320
`
`~
`
`---
`
`336")
`
`2903
`
`DA
`14
`
`11 I
`
`-
`
`-318
`
`2903
`
`DA
`{4
`
`ll r y 11 r
`
`r--
`i"'-316
`
`J
`I
`
`2903
`
`DA
`i4
`
`;----
`
`1'-314
`
`TO NORMALIZATION MULTI PILER
`
`344
`
`342
`
`18
`
`LATCH
`{a
`ZEN LATCH
`
`IL
`
`COS-TRANSFORM
`FROM
`EOB
`
`V4
`
`4,~
`
`'9
`)O-B
`
`"8
`
`~ l1
`
`REGISTER
`lOE PIPELINE
`
`328)
`
`324)
`
`256X 40
`MICROPROGRAM
`
`MEMORY
`
`4
`
`8
`
`372
`
`1
`
`'
`
`2910
`00-11
`
`~1'o-3
`
`FL
`
`;---OE LATCH
`
`r---OE LATCH
`
`;_10
`A (BIT COUNT) FROM
`
`f's
`
`16 Q z
`
`EXTERNAL R /R
`
`r-
`318
`
`A CONSTANT
`
`~6
`32xl6
`-OE PROM
`
`4
`
`/
`
`INTERRUPT
`
`(32 x8)
`VECTOR
`
`MAP
`
`~30
`
`>\
`326 ! ! ~BLOCK TRANSFORM DONE
`
`1BIT COUNT READY
`
`.-334
`
`-
`
`y
`
`2903
`
`CONTROL
`
`l STATUS
`
`SHIFT
`AND
`
`2904 l
`
`; 13
`
`,
`2_.~
`
`a/ A B
`
`4,
`
`,...--DA
`14
`
`"4 I
`
`DECODE
`
`3~
`
`I 2
`
`17
`
`

`
`U.S. Patent Nov. 24, 1981
`
`Sheet 17 of 22
`
`4,302,775
`
`BIT COUNT
`READY
`
`POWER UP
`RESTART
`
`LOAD
`DEFAULT
`CONSTANT
`
`DONE
`
`CHANGE RATE
`
`LOAD EXTERNAL
`REGISTER:
`INTO R9
`
`DONE
`
`REGISTER
`DEFINITION
`R1=S(k)-S(k-l)
`R2=t.5- S(k-1)
`R3=S(k) SIGN (S(k)""" S(k-1))
`R4=S(k)
`R5 =TEMPORARY STORAGE FOR 0 (k)
`RG=TEMPORARY STORAGE
`R7=D(k)
`R
`=1/D(k)
`8
`R9 = R0 I R I (CONSTANT)
`
`BLOCK TRANSFORM
`DONE
`
`DONE
`
`n
`
`n
`
`FIG. 21
`FIG. 23
`161
`162
`B4
`LATCH ~
`WE
`RAD CLK
`LOAD FIFO
`
`DONE
`
`...n
`
`__J'""""'1.__
`
`READ/WRITE SEQUENCE
`
`NEXT BIT
`CLOCK~}
`B4 ~ LOAD SHIFT REGISTER SEQUENCE
`___r-"1_._
`Q
`
`18
`
`

`
`FIFO
`LOAD
`
`-0
`
`N
`N
`0 .....,
`0
`
`-\
`
`00 -
`
`0
`
`380
`
`376
`
`378
`
`384
`
`~I SYNC. TO D. c.r----t----DATA CLOCK
`
`372
`
`12
`
`COUNTER
`ADDRESS
`
`READ
`12
`
`12
`
`COUNTER
`ADDRESS
`WRITE
`
`370
`
`~I
`
`2-PHASE
`llf2
`
`CLOCK
`
`8{'
`
`356
`
`FIG. 24
`
`en .
`c
`
`368
`
`LATCH
`
`F/F
`WRITE
`
`358
`
`FIFO
`SHIFT
`
`R
`
`CLOCK
`BIT---IC
`NEXT
`
`386
`
`19
`
`

`
`~
`N
`~
`
`z 0
`
`COUNT
`COUNTERQB
`
`JAM
`
`8-BIT
`
`F. S.
`EOB
`
`470
`
`,
`
`ZERO CODE
`
`EFF
`
`8
`
`SELECTOR
`
`v-398
`
`2:1
`
`7
`8,
`
`rl1 OUTPUT ~co
`
`DECODER
`2-BIT
`
`T
`
`3j6
`
`1---l
`1--l
`
`_L 1 .,.... SIGN
`
`S.l. RDV S.O.
`
`64xl2
`FIFO
`
`3\4
`
`LATCH
`10-BIT
`
`1 312
`
`-
`
`2
`10
`LATCH DATA ~
`
`BUFFER~ l
`~
`I
`l
`,,--
`f'o
`8/
`
`Q2 l
`o, :r-402
`Q2 ~
`o, w
`4~~ ~406
`
`-
`
`~ c2
`,-<j c,
`
`.r408
`
`02
`01
`
`NEXT COEFF CLOCK
`
`(-8.7 M h/s}
`
`OVER FLOW
`
`~ EQNS)
`zc
`(SEE
`LOGIC
`~
`
`lr-.....
`
`410....-1
`
`(-20 M h/s}
`
`CLOCK
`LATCH
`
`READY
`FIFO
`
`l
`
`414
`
`l../420
`
`REGISTER
`
`SIP
`
`-CJPR JQ
`
`RATE
`
`FR
`~
`
`I T 4la
`
`OPER SEL
`
`CTR
`
`I
`
`~
`
`, r
`~ DECODER
`
`2Kx 12
`PROM
`
`3\0
`
`10
`
`. 25
`86
`
`FIG
`
`/
`
`-
`
`L-
`
`--
`
`416
`
`BIT C LOCK
`NEXT
`
`CL! OCK
`SY
`
`NC
`
`IM TA
`
`20
`
`

`
`U.S. Patent Nov. 24, 1981
`
`Sheet 20 of 22
`
`4,302,775
`
`FIG. 26
`
`FIG. 27
`NEXT BIT CLK
`
`DATA
`
`LATCH OUTPUT
`
`PROM OUTPUT
`
`LATCH
`
`TERMINAL STATE BIT
`
`1/J/1
`
`\\\\\
`
`SHIFT IN (LOAD FIFO)
`
`FIG. 28
`SHIFT OUT
`
`FIFO OUT
`
`ZERO CODE
`
`NEXT COEFF CODE
`
`JAM COUNTER
`
`COUNT CLOCK
`
`OVER FLOW
`
`\\\\\
`__ l l __ r-L_f-l ..... H.J-~___s---t_
`r-1,_ __ ~.--------
`
`r--t,~
`
`21
`
`

`
`Ul
`-.l
`-.l
`,.
`N
`0
`(.;,.)
`~ ,.
`
`N
`N
`0 ......,
`
`N
`.....
`(!)
`(!)
`:r
`Vl
`
`00
`0
`
`-\
`
`CONTROL
`OUTPUT
`
`Q
`I
`
`ENCODED
`
`OUT
`DATA
`
`CHROM/NANCE DECODER
`
`38
`
`\
`
`CONTROLLER
`
`452
`
`438 ' 22
`
`CHROM/NANCE ENCODER
`
`CONTROLLER
`
`8.26 MHz
`
`SYNC
`
`PIXEL CLOCK
`
`Q
`I
`
`FIG. 29
`
`424
`
`22
`
`

`
`U.S. Patent Nov. 24, 1981
`
`Sheet 22 of 22
`
`4,302,775
`
`v462
`1---
`
`SYNC
`WORD
`
`jo
`
`FIFO
`
`~8 L-
`-
`
`1------;
`
`FIFO
`
`SELECTOR
`
`/
`
`TO CONV.
`CODER
`DATA
`
`CLOCK
`
`J
`
`J
`
`5-BIT
`PROM
`~ ~ FRAME
`32x2
`COUNTER
`
`~
`
`4~
`
`FIFO 1---
`
`\ ~8
`
`28
`
`4 '
`
`SOUND
`
`FIFO
`READY
`
`DATA
`CLOCK
`FIFO
`READY
`
`DATA
`
`CHROM
`
`CLOCK
`FIFO
`READY
`LUM DATA
`
`/
`456
`FIG. 30
`
`MULTIPLEXER
`
`FROM
`VITERBI
`DECODER
`DATA
`
`CLOCK
`'---
`
`5-BIT
`FRAME
`COUNTER
`
`•
`
`PROM
`SELECTOR
`I-- 32x2 fe-
`
`DATA
`
`SOUND CLOCK
`DATA
`READY
`DATA
`CHROM CLOCK
`DATA
`READY
`DATA
`LUM CLOCK
`DATA
`READY
`
`478
`I
`
`FIFO
`
`CLOCK
`;476
`
`l
`
`FIFO
`
`CLOCK
`
`474
`
`CLOCK
`
`FIFO
`
`4{2 ' )e2 4'
`
`32
`
`SYNCHRO-
`NIZER
`
`4701
`
`DEMULTIPLEXER
`
`23
`
`

`
`1
`
`4,302,775
`
`DIGITAL VIDEO COMPRESSION SYSTEM AND
`METHODS UTILIZING SCENE ADAPTIVE
`CODING WITH RATE BUFFER FEEDBACK
`
`BACKGROUND OF THE INVENTION
`The present invention relates to methods and appara(cid:173)
`tus for compression, transfer through a limited band(cid:173)
`width medium, and expansion of digitalized television
`picture signals·,at real time rates up to standard broad(cid:173)
`cast frame rates. ?ylore particularly, the present inven(cid:173)
`tion relates to methods and apparatus for television
`picture single pass scene adaptive compression, transfer
`and expansion with two dimen~ional transformation in
`conjunction with compression coding schemes wherein
`rate buffer feedback is effectively utilized to provide
`optimalized compression normalization factoring in real
`time without undue degradation of restored piCture
`imagery and with minimized hardware implementation
`requirements. ··
`Digital coding techniques are increasingly employed
`in processing television signals for transfer over noisy
`transmission channels. Digital data streams may be
`made essentially free of noise ·degradation, and this
`advantage in the transmission of digitized information
`has been advantageously utilized over long, noisy trans(cid:173)
`mission paths. Thus, it is an increasingly common prac(cid:173)
`tice today to digitalize broadcast television signals for
`transmission and relay through otherwise noisy long
`distance paths, such as stationary earth satellites· many
`thousands of miles away from the earth.
`To digitize a televion signal, a significant number of
`bits, 4, 5, 6 or even more, may be required to provide for
`the proper range of gray scale of each of the hundreds
`of thousands of separate picture elements (pixels). Con- 35
`sequeiitly, data rates for digitalized television signals are
`far in excess of the highest frequency components of
`analog television signals. It is not unusual to find in a
`digitalized television communications link, a required
`video bandwidth of 40 megabits per second. While 40
`digitalized television transmission formats advanta(cid:173)
`geously overcome the signal to noise problems inherent
`in analog transmission over similar path lengths, the
`substantial bandwidths for such digitalized signals often
`occupy the entire bandwidth capability of the commu- 45
`nications link. If the communications link is an earth
`satellite in stationary orbit above the earth, the video
`signal typically occupies the entire transponder band(cid:173)
`width ofthe satellite, with very few channels, if any, left
`over for other uses. Thus, need has arisen for a practical
`yet effective way to reduce the bandwidth of digitalized
`television signals to provide for more channels within a
`communications path such as an earth satellite.
`
`2
`included two-dimensional digital pulse code modulation
`schemes with block adaptive coding or with rate buffer(cid:173)
`ing; hybrid cosine transformation and digital pulse code
`modulation schemes; and, unidimensional, bidimen(cid:173)
`sional and hybrid Haar-Hadamard transformations. Run
`length coding has also been employed.
`Two basic techniques for coding transform domain
`coefficients are known in the prior art, namely zonal
`coding and adaptive coding. Zonal coding essentially
`10 eliminated all high frequency picture transform coeffici(cid:173)
`ents regardless of energy content with a resultant loss of
`picture detail upon reconstitution of the picture. On the
`other hand, adaptive coding schemes, including thresh(cid:173)
`old sampling techniques, were used to identifY, and pre-
`15 serve large amplitude high frequency coefficients, and
`those schemes provided reconstituted pictures having
`less distortion from the compression process at signifi(cid:173)
`cantly higher degrees of compression. In threshold
`sampling when a coefficient exceeded a preset ampli-
`20 tude, it was sent with full precision (normally 6 to 8
`bits), and many times a coefficient was transmitted with
`8 bits when one or two bits would have accurately
`characterized the coefficient.
`25 Adaptive coding techniques followed two basic ap-
`proaches: multiple class energy bit map coding and
`recursive coding with rate buffer feedback. In the multi(cid:173)
`ple class bit map approach, transform sub-frames of the
`picture were sorted into categories related to the level
`30 of image activity present in each sub-frame. Within each
`activity level, AC energy coding bits were allocated to
`individual transform elements in classes according to a
`variance matrix of the transform data with the variance
`matrix being computed for each of the classes and dif-
`ferent bit allocation matrices being created with more
`bits being assigned to areas of high image activity and
`fewer bits to those areas of lower activity. Such classifi(cid:173)
`cations were carried out either with a two-pass statisti(cid:173)
`cal gathering and mapping scheme or with a fixed
`pregenerated statistical model created upon assump(cid:173)
`tions. made for the particular system application.
`In the two-pass approach, the first pass of processing
`generated statistics for sub-block classification maps, set
`up bit assignment matrices and calculated normalization
`factors for compression. The second pass was for multi(cid:173)
`plying the normalization factor to quantize transform
`coefficients, for encoding the resultant data, and for
`adding overhead information. The drawback of the two
`pass approach is the substantial times required for two
`50 pass processing within existing equipment which un(cid:173)
`duly limited the size of pictures to be compressed and
`the number of sub-frame activity classifications that
`could be utilized. Also, the hardware requirements for
`real time implementation were prohibitively complex,
`BRIEF; DESCRIPTION OFPERTINENT PRIOR 55 and hence the two pass approach is presently impracti-
`ART
`cal, particularly at picture broadcast rates.
`.
`The pregenerated statistics modeling approach suf-
`It is known and discussed in the prior art relating to
`fered from the fact that no pregenerated statistics ever
`television image bandwidth compression that two-di(cid:173)
`exactly matched those of a real time picture being com(cid:173)
`mensional cosine transform . techniques have yielded
`pressed. Additionally, several sets of pregenerated sta(cid:173)
`reproduced pictures of superior quality at the same and 60
`tistics were often needed to accommodate multiple
`even higher picture data compression ratios than were
`applications which required multiple passes to preselect
`obtainable with other transforms or techniques. Hereto~
`the most nearly appropriate statistical set to be utilized
`fore, television picture compression techniques have
`for the particular picture.
`been directed to simple implementations with substan•
`In the recursive coding with rate buffer feedback
`tial throughput speeds in real time with concomitant 65.
`scheme, the sub-frame activity was determined by the
`significant degradation of restored picture resolution
`and the introduction of unwanted compression process
`estimated variances of the transform coefficients, the
`artifacts into the restored picture. Such techniques have
`variances being derived by a simple linear predicter.
`
`24
`
`

`
`3
`One significant drawback in the recursive coding ap(cid:173)
`proach was the elimination of high frequency AC coef(cid:173)
`ficients, including those having significant amplitudes.
`Once the linear predicter produced a variance which
`needed a zero bit assignment, the· encoding of that par(cid:173)
`ticular picture subframe was terminated, and all subse(cid:173)
`quent AC terms, including those with significant values,
`· were lost. Such losses unduly degraded high activity
`regions in the reconstituted pictures following inverse
`expansion and reconstruction of the compressed picture 10
`signal. Another drawback of the recursive coding
`scheme was that heretofore there has been no theoreti(cid:173)
`cal analysis which justifies the assumed optimality of a
`linear predicter. One feature of recursive coding which
`has been advantageously incorporated into and signifi- IS
`cantly expanded in the present invention is that of the
`rate buffer technique.
`A major problem with image data compression has
`been the non-stationarity of image statistics. Early cod(cid:173)
`ing schemes such as a single map zonal coder attempted 20
`to ignore the problem by assuming image statistics as a
`stationary process. The Markov model used by investi(cid:173)
`gators was an example of the stationary statistical char(cid:173)
`acterization of image data. Adaptive coding procedures
`have been proposed to take care of the non-stationary
`nature of the image processes and to improve the image
`quality. A well designed adaptive coder generally needs
`a priori non-stationary statistical information. This a
`priori information can either be estimated or computed 30
`on line, or predetermined a priorily. Neither case is
`desirable since it causes complications in hardware im(cid:173)
`plementation on the former and causes statistical mis(cid:173)
`matches on the latter. The undesirable feature can be
`eliminated by introducing the rate buffer concept for JS
`the channel rate equalization in accordance with the
`present invention.
`
`2s
`
`SOME OBJECTS OF THE PRESENT INVENTION
`A general object of the present invention is to pro- 40
`vide a digital video compression system which effec(cid:173)
`tively combines scene adaptive coding with rate buffer
`feedback in methods and apparatus which overcome
`limitations and drawbacks of the prior art.
`Another object of the present invention is to provide 4S
`a digital video compression system which operates ef(cid:173)
`fectively at real time picture frame rates as high as those
`of the NTSC color broadcast standards.
`Another object of the present invention is to combine
`novel circuits and subsystems into a digital video com- so
`pressor and expander which effectively compresses the
`bandwidth of a television picture in accordance with
`novel methods and techniques.
`Another object of the present invention is to provide
`a digital video compression system which effectively ss
`implements a two-dimensional discrete cosine transform
`of blocks of the picture.
`Another object of the present invention is to provide
`a digital video compression system which effectively
`implements a two-dimensional transform in which the 60
`DC term of each transformed picture block may always
`be transmitted in a fixed .number of bits.
`Another object of the present invention is to provide
`a digital video compression system which effectively
`implements a two-dimensional transform of blocks of 65
`the picture in which uniformly quantized AC coeffici(cid:173)
`ents of each block fall into a single Huffman codeable
`statistical set.
`
`4,302,775
`
`4
`Another object of the present invention is to provide
`a digital video compression system which effectively
`implements a two-dimensional transform of blocks of
`the picture in which low order uniformly quantized AC
`coefficients can be efficiently Huffman coded by the
`compressor and decoded by the expander in accordance
`with a predetermined Huffman code table, without
`transmitting the Huffman table or generating a new
`table for each block.
`Another object of the present invention is to provide
`a digital video compression system which implements a
`two-dimensional transform of blocks of the picture in
`which long strings of zero value high order AC coeffici(cid:173)
`ents may be effectively run length encoded and in
`which high amplitude high order AC coefficients will
`be preserved.
`Another object of the present invention is to provide
`a digital video compression system which implements a
`two-dimensional transform of blocks of the picture in
`which variance calculations, bit allocation matrix calcu(cid:173)
`lations, and nonlinear block quantization are eliminated
`and not required in the compression process.
`Another object of the present invention is.to provide
`a single pass digital video compression system which
`implements a two-dimensional transform of blocks of
`the picture which eliminates the requirement of prelimi(cid:173)
`nary statistical matching or preprocessing to determine
`applicable statistics needed by prior two-pass picture
`compression techniques.
`Another object of the present invention is to provide
`a digital video compression system which effectively
`utilizes rate buffer feedback control to provide global
`adaptivity of the system to the picture in real time.
`Another object of the present invention is to provide
`a digital video compression system which requires only
`one two-dimensional block of a fraction of the picture
`for input buffering, but which in practice will buffer at
`input an image strip of blocks of the same number of
`lines as defines the block size and will further provide
`some preformatting of the data.
`Yet another object of the present invention is to pro(cid:173)
`vide a digital video compression system in which the
`output of the compression process yields a white noise
`error image· with no apparent structure.
`A further object ofthe present invention is to provide
`a digital video compression and expansion system in
`which the expander includes an instantaneous decoder
`which operates on each bit as it is received.
`SUMMARY OF THE INVENTION
`An NTSC color broadcast compression and expan(cid:173)
`sion system incorporating the principles of the present
`invention divides the color picture into luminance
`(monochrome) and I and Q chrominance components.
`The luminance signal is compressed and expanded with
`the scene adaptive coding with rate buffer feedback
`techniques of the present invention. The I and Q chro(cid:173)
`minance components are given simple spatial low pass
`filtering followed by spatial subsampling with two-di(cid:173)
`mensional interpolation at the system receiver. The
`audo is filtered and sampled at a predetermined rate,
`with each sample quantized to a predetermined bit reso(cid:173)
`lution. The digitalized and compressed luminance (in(cid:173)
`cluding picture synchronization pulses) chrominance
`and audio components are multiplexed together with bit
`stream synchronization codes and transmitted as a sin(cid:173)
`gle composite bit stream.
`
`25
`
`

`
`25
`
`5
`The scene adaptive coding with rate buffer feedback
`compression system of the present invention receives
`each digitalized video luminance frame divided into a
`predetermined matrix of subframes or blocks. The com(cid:173)
`pressor performs a spatial domain to transform domain
`transformation in both horizontal and vertical dimen(cid:173)
`sions of the picture elements of each subframe to pro(cid:173)
`vide transform coefficients corresponding to each sub(cid:173)
`frame. The compressor normalizes the coefficients by a
`normalization factor having a predetermined compres- 10
`sion ratio component and an adaptive rate buffer capac-
`ity control feedback component to provide· compres(cid:173)
`sion to the transform coefficients and to provide nor(cid:173)
`malized transform coefficients compatible with a prede(cid:173)
`termined data coding scheme. The coefficients are en- 15
`coded in accordance with, e.g., Huffman codes and zero
`coefficient run length codes, and then stored in a first
`rate buffer memory asynchronously at a high data trans-
`fer rate from which they are put out at a slower, syn(cid:173)
`chronous bit stream rate capable of passing through a 20
`limited bandwidth medium. The compressor adaptively
`determines the rate buffer capacity control feedback
`component in relation to the instantaneous data content
`of the rate buffer memory in relation to its capacity to
`control at normalization the absolute quantity of data
`resulting from that process so that the buffer memory is
`never completely emptied and never completely filled.
`In expansion, the system stores the coded coefficients
`in a second, decoder rate buffer memory at the slow 30
`synchronous data transfer rate through the limited me(cid:173)
`dium. The coefficients are then put out from the second
`memory asynchronously at a high data transfer rate.
`The coefficients are decoded in accordance