United States Patent [19l
`Keith et al.
`
`[11] Patent Number:
`[45] Date of Patent:
`
`4,785,349
`Nov. 15, 1988
`
`[54] DIGITAL VIDEO DECOMPRESSION
`SYSTEM
`
`mar Conf. On Circuits, Sys. and Computers, Ca. 11182
`IEEE.
`
`[75]
`
`Inventors: John M. Keith, Washington
`Crossing, Pa.; Stuart J. Golin, East
`Windsor, N.J.; Allen H. Simon, Belle
`Mead, N.J.; Brian Astle, Cranbury,
`N.J.
`
`[73] Assignee: Technology Inc. 64, Princeton, N.J.
`[21] Appl. No.: 104,131
`[22] Filed:
`Oct. 5, 1987
`[51]
`Int. Cl.4 ............................................... H04N 7/13
`[52] U.S. CI. ...................................... 358/136; 358/11;
`358/13; 358/133; 358/135
`[58] Field of Search ............... 358/133, 136, 135, 105,
`358/13, 11; 375/27, 122
`References Cited
`U.S. PATENT DOCUMENTS
`4,225,885 9/1980 Lux et al. ......................... 340/146.3
`4,334,246 6/1982 Saran .............................. : .... 358/261
`4,386,366 5/1983 Mori .................................... 358/135
`4,430,670 2/1984 Netrravali ........................... 358/135
`4,468,708 8/1984 Coleman ............................. 358/310
`4,520,401 5/1985 Takahashi et al. .................. 358/310
`4,546,342 10/1985 Weaver et al. ...................... 340/347
`4,667,233 5/1987 Furukawa ........................... 358/136
`4,691,329 9/1987 Juri ...................................... 358/136
`
`[56]
`
`OTHER PUBLICATIONS
`Leonardi & Kunt, "Adaptive Split and Merge for Image
`Analysis and Coding", Image Coding, Cannes, France,
`Dec. 1985 vol. 594 pp. 2-9, 1986.
`Leonardi & Kunt, "Adaptive Split for Image Coding",
`International Symposium On Applied Signal Proc. and
`Digital Filtering, Paris 1985.
`Milford et a!., "Quad Encoded Display", IEEE Pro(cid:173)
`ceedings, val. 131, Pt. E, No. 3, May 1984, pp. 70-75.
`Baker & Gray "Image Compression Using Non-Adap(cid:173)
`tive Spatial Vector Quantization",
`IEEE Cat.
`#CH1809-3183/0000/0055 Conf. Paper in 16th Asilo-
`
`Primary Examiner-Howard W. Britton
`Attorney, Agent, or Firm-Paul J. Rasmussen; Eric P.
`Herrmann; Kenneth N. Nigon
`
`ABSTRACT
`[57]
`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 de(cid:173)
`scriptive 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 accord(cid:173)
`ing 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 de(cid:173)
`coder 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 re(cid:173)
`gion 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 fo.r subsequent display.
`
`15 Claims, 32 Drawing Sheets
`
`Vedanti Systems Limited - Ex. 2015
`Page 1
`
`

`
`U.S. Patent Nov.15, 1988
`
`Sheet 1 of 32
`
`4,785,349
`
`10
`
`S1
`
`53
`
`RECORDING SYSTEM 6
`
`54 BIT-STREAM
`~1.23 X 10' BITS/SEC.
`
`FIG.1
`
`18
`
`PLAYBACK SYSTEM
`8
`
`~516
`
`517-.
`
`DISPLAY
`
`520
`
`32
`
`2
`
`3.
`
`VIDEO
`PROCESSOR
`(FIGS. 48-63)
`
`Vedanti Systems Limited - Ex. 2015
`Page 2
`
`

`
`U.S. Patent Nov. IS, 1988
`
`Sheet 2 of32
`
`4,785,349
`
`22f
`PRE -COMPRESSION
`PROCESSJR ~---- OPERA10R
`CONTROL
`(FIGS. 14-15)
`22c(..__,__,___...,..._.J
`I
`y
`
`206-9
`AUX. DATA
`IN
`
`S3
`
`MODE
`SWI'Tt:H
`
`~AUDIO IN
`
`202 S1
`~
`
`CHAN.
`SELECT ~208
`AND
`A/D
`CO NV.
`
`;-9 VIDEO IN
`204 S2
`
`'
`
`S5
`
`10
`
`1lt
`
`/
`
`AUDIO
`COMP.
`(FIG.25)
`
`56
`
`.• 1'2
`
`BUFFER
`STORE
`
`Q
`
`I
`
`SUBFRAMEf\2;
`SELECT
`
`DIGITAL VIDEO
`COMPRESSOR
`(FIGS. 16- 47)
`
`,,
`
`-
`
`S9 r
`
`232 --..._. BUFFER
`S10RE
`
`THRESHOLD
`CONTROL
`A
`
`BYTE
`r* COUNT
`MONITOR
`
`2~
`rECODE
`i~ TIME
`MONITOR
`
`I
`I
`I
`I
`_j
`I
`I
`I
`I
`I
`I
`I
`-1
`I
`I
`I
`I
`I
`I
`
`57
`
`SIO
`
`53
`
`ENCODER
`16
`
`'
`
`f
`FORMATTER
`
`250-
`
`(FIGS. 8-13)
`
`I
`---------------·
`I
`S4 BITSTREAM OUT
`f-o
`10 CD-ROM
`RECORDER 18
`
`FIG. 2
`
`Vedanti Systems Limited - Ex. 2015
`Page 3
`
`

`
`U.S. Patent
`
`Nov. 15, 1988
`
`FIG.3
`
`I~
`
`I
`
`ONE FRAME
`
`FIELD I
`
`4,785,349
`
`Sheet 3 of32
`,..!
`I NTSC
`
`RELO 2
`
`S2 COMPOSITE
`VIDEO
`
`FIG.4
`
`I~ 512X24Q
`
`R
`G
`B
`737, 28:> BYTES
`
`DECODED
`AND
`DIGITIZED
`
`F/G.5
`
`y
`
`256
`
`X 240
`
`I164:J ~64~J ~g·SAMPLED
`Q I COMPRESSED
`
`69, 120 BYTES
`
`y
`
`I
`I
`I
`I
`>4500 BYTES
`
`FRAME, REGION
`COOED
`
`FIG.6
`
`FIG.7
`
`IH
`
`y
`
`VIDEO 11STREAM11
`I H I
`I
`<4500 BYTES
`
`I Hi Q I VAR. LENG
`
`QUANTI~
`COCED
`S9 WITH HEADERS
`AD CEO
`
`FIG.B
`
`I
`I
`I
`I
`FORMATTED
`FRAME 1 OOMPRESSED1 CIGIT.IIL 1 S3 1
`I AUDIO 1 ALO< 1 Fll,L,ER DATA FRAME
`HEADER 1 DIGITAL
`I II VIDEO II I 13)1134 I DATA I DATA 5124""5128 BYiES
`1 BYTES I
`I
`I STREAM
`
`~FRAM~
`FIG.9 :1~1!51~ .· ... 1!51241 !51281 B~A~~61THERED
`29.97 Ff5, 5125.12 BYTES AVERAGE
`
`Vedanti Systems Limited - Ex. 2015
`Page 4
`
`

`
`U.S. Patent Nov. 15, 1988
`
`Sheet 4 of 32
`
`4,785,349
`
`FRAME F1 FRAME F2 FRAME F3(CM:RSIZE)
`FIG. 10 I 3000 I 4000 I . 6000
`I
`
`FIG.//
`
`: PAD
`VIDEO
`3000 !2000
`
`1 PAD
`VIDEO
`4000 11000
`
`VIDEO
`5000
`
`COMPRESS~
`INCREASED
`
`VIDEO
`6000
`~
`
`11 BORROWED11 FROM
`PREVIOUS FRAME
`
`AUX. OOA
`FROM
`
`53
`
`1370 AUX. DATA PADDING
`SELECT
`
`206 ~l mQrERO
`
`VIDEO IN
`
`SIO
`
`O
`
`B~~~o ~3~
`
`HEADER
`DATA
`1361
`
`FIG. 13
`
`VIDEO
`DITHER,
`PADDING
`INSERT
`
`BIT-STREAM
`OUT TO
`CO-ROM
`RECORDER
`18
`
`Vedanti Systems Limited - Ex. 2015
`Page 5
`
`

`
`U.S. Patent Nov. 15, 1988
`
`Sheet 5 of32
`
`4,785,349
`
`PROCESSOR
`220
`
`204
`
`:> S2 FROM SOURCE 12
`
`140~ ,.
`
`R
`
`140 -~ ,.
`
`LPF
`(2 MHz)
`
`RGB
`DECODER
`
`140;
`
`G
`If
`I
`
`LPF
`(2 MHz)
`
`8
`
`14~8 ,,
`
`LPF
`(2 MHz)
`
`,It
`f
`~
`PROGRAMMABLE t--1410
`GRAPHICS
`WORK STATION
`(FIG.I5)
`
`I-_
`
`-
`
`~2·
`OPERA lOR
`TERMINAL
`
`y
`
`I Q
`
`~· , If
`
`DISK
`SlORE
`7
`1412
`
`y -.
`I -: OUT TO SUB-FRAME
`SELECTOR 224
`Q -:
`_.
`
`FIG. I~
`
`Vedanti Systems Limited - Ex. 2015
`Page 6
`
`

`
`U.s.· Patent
`
`Nov.15, 1988
`
`Sheet 6 of32
`
`4,785,349
`
`IN FROM OPERAlOR
`TERMINAL 222'
`
`IN FROM LP FILTERS 1404·1408
`R
`G
`8
`LP FILTERED
`ANALOG RGB
`
`1506
`
`DIGITIZE
`~12 X 480 PIXELS/F~AME
`
`SKIP AlTERNATE
`FIELDS
`
`SKIP ALTERNATE
`PIXELS
`
`1516
`
`500KHZ
`
`60 UNES/PICTURE
`HEIGHT
`
`SKIP 3 CE 4 UNES
`
`SKIP 3 OF 4 PIXELS
`
`I,Q: 64 X 60 each
`Y: 256 X 240
`
`MATRIX
`
`y
`
`I
`
`Q
`
`OUT TO
`SWITCH 224
`YIQ
`
`DISC
`STORE
`
`FIG. 15
`
`Vedanti Systems Limited - Ex. 2015
`Page 7
`
`

`
`U.S. Patent Nov. 15, 1988
`
`Sheet 7 of32
`
`4,785,349
`
`IN FROM YIQ
`SELECTOR SWITCH 224
`
`1602
`sa
`
`MODE
`SWITCH
`24d
`
`IN FROM THRESHOLD
`CCM"ROL238
`
`1610
`
`INTRA-FRAME
`REGION SPECIFIC
`COOER
`(FIGS. 17-38)
`
`1604
`
`Sll
`
`I t-ITER- FRAME
`REGION SPECIAC
`CODER
`Sl~ ( AGS. 39-43,61,62)
`
`AREA DEPENDENT
`ADAPTIVE QUANllZER
`CFIGS. 44, 45)
`
`Sl4
`
`STREAM SEGMENTED
`VM. LENGTH CODER
`(FIGS. 46, 47)
`
`1630
`
`1640
`
`S9
`
`OUT TO
`BUFFER
`232
`
`DIGITAL VIDEO COMPRESSOR 230
`
`FIG. /6
`
`Vedanti Systems Limited - Ex. 2015
`Page 8
`
`

`
`U.S. Patent Nov. 15, 1988
`
`Sheet 8 of 32
`
`4,785,349
`
`DETERMINE
`BI-LINEAR FILl
`Axi-By-t C
`
`MEASURE
`BOUNDARY AND
`MEANSQERR
`1711
`
`FIG./7
`
`Vedanti Systems Limited - Ex. 2015
`Page 9
`
`

`
`U.S. Patent
`
`Nov. 15, 1988
`
`Sheet 9 of32
`
`4,785,349
`
`COLUMN
`"3
`2
`I
`4
`,------------------,
`
`I 8 0 @ G ~REGION
`
`v
`
`1802
`
`I
`I
`I
`
`FIG. /8
`
`1904
`
`191
`
`HORIZ.
`EDGE
`COUNTER
`
`lOSPUT
`LOGIC
`FIG.33
`
`VERT. EDGE
`
`F/G./9
`
`NO EDGES
`IN REGION
`"FILL"
`
`Vedanti Systems Limited - Ex. 2015
`Page 10
`
`

`
`U.S. Patent Nov.15, 1988
`
`Sheet 10 of 32
`
`4, 785,349
`
`2~02
`
`®®® NO 1SLOPE" OR GRADIENT
`FIG.20 ®®®
`®®®
`
`FILL= Ax+ By+ C
`A=O
`B=O
`C=5
`CODE: ASS 005
`
`2J02
`
`0®® UNIFORM HOR. Sl.DPE
`FIG. 21 0®®
`@®®
`
`FILL= Ax+ By+ C
`A= I
`8=0
`C=4
`CODE: ABS I 0 4
`
`2~02
`
`®®®
`FIG. 22 ®®®
`@@~
`
`UNIFORM VERT. Sl.DPE
`FILL;: Ax+ By+C
`A=O
`B= -1
`C=6
`CODE: ABS 0-1 6
`
`23~2
`®®~ VERT. AND HOR. SLOPE
`F/6.23 ~®®
`®~®
`
`FILL=Ax+By+C
`A= I
`B=-1
`C=5
`CODE:ABS 1-1 5
`
`Vedanti Systems Limited - Ex. 2015
`Page 11
`
`

`
`U.S. Patent
`
`Nov. IS, 1988
`
`Sheet 11 of 32
`
`4,785,349
`
`ACTUAL REGION PIXEL VALUES
`
`VALUES AS DECODED FROM
`POLYNOMIAL FILL Ax+By+C
`
`FIG. 24
`
`Vedanti Systems Limited - Ex. 2015
`Page 12
`
`

`
`U.S. Patent Nov. 15, 1988
`211
`l
`DPCM R
`
`55
`IN
`
`Sheet 12 of 32
`
`214
`·;
`
`-
`
`4,785,349
`218
`)
`
`BYTE LIMIT
`11256 11
`
`)
`
`(
`
`~ CODER - COMP
`t
`- BYTE
`.. COUNl'ER
`
`,...
`56 ou
`T
`
`ALOO
`1-----216 COMPRESSOR
`210
`
`FIG.25
`
`FIG. 26
`
`2604
`
`2605
`
`QUAD-TREE
`REGIONALIZATION
`
`70
`
`70
`
`70
`
`70
`
`I
`I
`I
`I
`I
`_____ L ___ _
`I
`I
`46 146 1
`-----1
`32: 32 I
`I
`
`57
`
`I
`46146
`I -----
`32 : 32
`I
`
`608
`
`57
`
`Vedanti Systems Limited - Ex. 2015
`Page 13
`
`

`
`U.S. Patent Nov.15, 1988
`2702
`
`2
`
`Sheet 13 of 32
`
`4,785,349
`
`FILL
`
`SPUT1
`
`2706 FIG:27
`
`SPLIT 3 SPLIT 2
`
`TREE CODING
`USING NODE VALUES
`
`TREE CODING
`USING NODE DIFFERENCES
`SPLIT 1(122-128:::-6)
`
`FILL 112
`
`FILL 90
`FILL 98
`RG.28
`
`FILL
`
`FIG. 29
`
`RG.30
`SPLJT I FILL
`~EE CODE
`HF 141 VHF90 F 98 F 112
`H: HORIZONTAL SPLIT ACTION
`V: VERTICAL SPLIT ACTION
`F: FILL ACTION
`
`F/6.31
`SPLIT/FILL
`TREE CODE
`A. -6H -38 FVI8 H8 FFF
`B. 12H76 FV36 H 16 FFF
`C. 12S 76 FS36 S 16 FFF
`S-Simple SPLIT )
`A-Alternate SPUT
`
`(
`
`Vedanti Systems Limited - Ex. 2015
`Page 14
`
`

`
`U.S. Patent
`
`Nov. 15, 1988
`
`Sheet 14 of 32
`
`4, 785,349
`
`3202
`
`2
`I
`FIG.32A
`---1---
`3 ~ 4
`
`RG.32B
`
`RG.32C
`
`FIG.32D
`
`32041
`c:::J I
`c::::::~ I
`------
`I
`c:::> I
`c:::> I
`I
`
`320
`:o~o
`:o~ o
`
`___ I ___
`
`320
`
`0 : 0 0
`-0 u-n·
`~
`
`I
`32101
`
`c:::::l
`
`I 0
`FIG.32E 0 0 :~ I
`
`I c:::>
`W >H
`
`32121
`I
`I 2
`I
`I
`'t=::) - c:::>
`3 : 4
`
`32141
`
`FIG.32F
`
`~ ~ : ~ ~
`--_I_- FIG. 32G
`
`I
`
`32161
`
`-~:-~- FIG. 32H
`
`c:::::::J I C==>
`c::::::::> I c::::::::>
`I
`
`3218
`
`<==::)
`
`I
`-~--
`
`c:::::ll <==::) FIG.32I
`c:::>F
`
`I c::::::::>
`
`322q
`
`-----
`
`c::::::::> 0 0 H>W
`FIG.32J
`~~
`
`Vedanti Systems Limited - Ex. 2015
`Page 15
`
`

`
`U.S. Patent
`
`Nov.15, 1988
`
`Sheet 15 of 32
`
`4,785,349
`
`DETECT EDGES
`IN QUADRANTS
`CF REGION
`
`3316
`
`FIG. 33A
`
`3306
`
`GENERATE
`Vl3, V24,
`Hl2, H34
`
`3300
`\
`
`MULTIPLY
`VF= H ·VI3 · V24
`HF=W ·H12 · H34
`
`YES
`
`SPLIT
`VERTICAL
`
`3312
`3314
`
`SPliT
`HORIZ.
`
`LEFT
`HALF
`(VI3)
`
`RIGHT
`HALF
`(V24)
`
`TOP
`HALF
`(HI2)
`
`BOTTOM
`HALF
`(H34)
`
`(H3-H4) 2
`2
`
`+(V3-V4)
`+V02 +V3
`
`(V1-V3) 2
`2
`
`+(H1-H3)
`+ H02 +H1
`+ H3 +1
`
`(V2-V4) 2
`2
`
`+(H2-H4)
`2
`+H0
`
`+H2
`
`(H1- H2) 2
`2
`
`+(vt-V2)
`
`+V02+vt
`
`+H4+ 1
`
`+V2+1
`
`+V4 + 1
`
`FIG. 338
`
`Vedanti Systems Limited - Ex. 2015
`Page 16
`
`

`
`U.S. Patent Nov.15, 1988
`
`Sheet 16 of 32
`
`4,785,349
`
`''SIMPLE" SPLITS
`
`W >H
`SPLIT
`VERTICAL
`
`H>W
`SPLIT
`HORIZ.
`
`FIG. 34A
`
`FIG.348
`
`'~LTERNATE" SPLITS
`
`3406 3408--m
`
`H~-~-~--~ w
`
`W>H
`SPLIT
`HORIZ.
`
`H>W
`SPLIT
`VERTICAL
`
`Vedanti Systems Limited - Ex. 2015
`Page 17
`
`

`
`U.S. Patent
`
`Nov. 15, 1988
`
`Sheet 17 of 32
`
`4,785,349
`
`PIXEL AND
`ITS NEAR
`NEIGHBORS
`®@®
`@
`
`@@G)
`FIG.35A
`
`3502
`
`3503
`
`FILTER
`WEIGHTS
`
`MEDIAN
`FILTERED
`PIXEL
`
`CD®CD f-.--'3504 0 00
`®0® 350
`CD® CD
`F/G.358
`
`00 0
`FIG.35C
`
`~3 { 1 i i 1 r I T':':":::Nw-:-:::;=r:-:::HTE=o:--M:-:-::E::=-DI:-:-:f:-:------...1r
`3so4{> 2 1 2
`1
`I A I A I
`11 ~1~3 1~ 1~
`~MEDIAN (FILTER OUTPUT)
`
`ORDERED VA LUES
`
`2
`
`2
`
`5
`
`1
`
`3508{ 1 5 5 9 10 10
`
`WEIGHTED ORDERED VALUES
`F/G.36D
`
`3510 """----
`
`F/6.35£
`0 ®
`®
`EXEMPLARY
`WEIGHTS FOR
`0. @ G) AVERAGE
`SCENE
`® G) ®
`
`Vedanti Systems Limited - Ex. 2015
`Page 18
`
`

`
`U.S. Patent Nov. 15, 1988
`
`Sheet 18 of 32
`
`4,785,349
`
`FIG.368
`
`1- • • • -F=====----1-------I---+--========-.... .•• ----!
`-255 -100
`-50
`0
`50
`100
`255
`DIFFERENCE SIGNAL
`
`0
`
`0
`
`. ---~-·- -
`
`OINPUT
`
`eOUTPUT
`
`3640
`
`/
`
`/
`
`/
`
`1 ~3642
`
`I
`
`/
`
`/
`
`/
`
`/ •
`
`0
`
`FIG. 36C
`
`Vedanti Systems Limited - Ex. 2015
`Page 19
`
`

`
`U.S. Patent
`
`Nov. 15, 1988
`VERT. FIT
`
`Sheet 19 of 32
`
`4,785,349
`
`~--)~702
`REGION
`WITHOUT
`EDGES
`
`~HORIZ.
`
`YH
`
`I
`
`1 FIT
`
`I
`I
`
`1
`
`F/6.37
`
`I
`
`I
`
`Ax+C
`
`1
`
`I
`
`F/6.38
`
`MEASURE HORIZ.
`FIT OF Ax+C
`TO YH DATA
`
`3802
`
`MEASURE VERT
`FIT OF B~+C
`TO Yv DATA
`
`3804
`
`3810
`
`YES
`
`3808
`
`SFLJT
`HORIZ.
`
`Vedanti Systems Limited - Ex. 2015
`Page 20
`
`

`
`U.S. Patent Nov. 15, 1988
`
`Sheet 20 of 32
`
`4,785,349
`
`3902
`
`SELECT
`REGION
`
`3980
`
`ENCOCE
`DYADS
`
`SPUT
`
`A,B,C
`
`FIG. 39
`
`Vedanti Systems Limited - Ex. 2015
`Page 21
`
`

`
`U.S. Patent
`
`Nov. 15, 1988
`
`Sheet 21 of 32
`
`4,785,349
`
`1_ __ r-~~l~ _ MOVEMENT
`
`1
`
`Yo
`1
`rt~ A" l - -
`r- CORRESPONDING
`rtt3. -rv T
`I
`REGION OF
`PREVIOOS FRAME C
`---
`'
`40 ~.._,____
`REGION OF ----lxo ~
`
`CURRENT FRAME
`( TARGET,T)
`
`LU
`
`U
`
`RU
`
`RD
`
`BEST
`DIR.
`
`NEXT(cid:173)
`STEP
`
`F/6.42
`
`TEST UPT08
`DIRECTIONS
`FOR BEST DIR.
`
`4230
`4240
`
`SET
`RESOI...=I/8
`
`SET
`RESOL=I
`
`4220
`LOW FASS
`FILTER
`
`STEP IN BEST
`DIRECTION
`UNTIL NO
`IMPROVEMENT
`
`TO 3922
`
`Vedanti Systems Limited - Ex. 2015
`Page 22
`
`

`
`U.S. Patent Nov. 15,1988
`
`Sheet 22 of 32
`
`4, 785,349
`
`FIG. 43
`
`Xo
`
`X,Y
`
`4302
`
`liT II
`TARGET
`IMAGE Yo
`\ . r - - - - - - - - i
`
`®®0
`@G)@
`CV®®
`
`PR~~us
`FRAME
`1 - - - - - - - l
`I@@)@) I
`I
`I
`1®®®1
`:®®®I
`L - - - _r_j
`
`I
`
`I
`
`4304
`
`' - -
`-~ DIFFERENCE
`I@) CD@
`IMAGE
`I=T-C
`I
`4308lCD ®@I
`11®@@1
`
`____ :_j
`
`RELATIVE FILL CQOE: A + 8 + C + JIO+ Yo
`
`EXAMPLE:
`
`I,
`
`-I,
`
`0,
`
`Xo, Yo
`
`Vedanti Systems Limited - Ex. 2015
`Page 23
`
`

`
`U.S. Patent Nov.15, 1988
`
`Sheet 23 of 32
`
`4,785,349
`
`FIG. 44
`
`REGION
`AREA
`(PIXELS)
`I
`2-3
`4-7
`S-15
`16-31
`32-N
`
`QUANTIZATION
`(BITS)
`3
`4
`5
`6
`7
`8
`
`4506
`
`COMPUTE
`REG JON
`AREA, A
`
`4520
`
`F/6.45
`
`4502
`
`GET
`REGION
`~TA
`(8 BITS)
`
`SlORE
`lll\TA
`
`4510
`
`Vedanti Systems Limited - Ex. 2015
`Page 24
`
`

`
`U.S. Patent Nov. 15, 1988
`
`Sheet 24 of 32
`
`4,785,349
`
`FIG. 46
`
`Sl4 IN FROM
`QUANllZER 1630
`,-L--L----,
`DYAD FILL
`
`VAR . LENGTH CODER 1640
`
`1650
`
`DPCM FILL
`
`ABSa..UTE
`FILL
`RELATIVE
`FILL
`--TREE--(cid:173)
`DESCRIPTION
`
`OODE
`STATISTICS
`STORE
`(6 TAB.ES)
`
`59 OUTPUT TO
`BUFFER 232
`
`FIG. 47
`FIXED LENGTH COlE)
`VAR. LENGTH COIED WITH-IMPLICIT TABLE
`VAR. LENG1H COIEDA WITH COL. 2 TABLES
`
`{,.
`
`HEADER
`
`CODE
`TABLES
`
`TYPE
`(Y, I orQ)
`
`SIZE
`CHECK-
`SUM
`DPCM
`TABLE
`
`DYAD
`TABLE
`
`TREE
`I. .IICTION~
`2. XoYo
`AND C
`
`3. COEF.
`A, B,C
`4.ABS.
`SLOPES
`A,B
`5. IFCM
`6. DYADS
`
`TREE
`DESCR.
`
`RELATIVE ABSOL.lm
`DATA
`DATA
`
`DPCM
`DATA
`
`DYAD
`DATA
`
`SPLIT
`FILL
`
`SHI)lg
`VALU
`XoYo
`
`ABSCL
`CONSr
`.. c ..
`
`POLY
`CCEF.
`A
`B
`c
`
`ABS.
`COEF.
`A
`B
`
`DPCM
`DYAD
`VAWES VALUES
`
`ONE
`PER
`PIXEL
`
`ONE
`PER
`TWO
`PIXELS
`
`STREAM FORMAT F~ EACH OF Y,I AND Q
`SUBFRAMES
`
`Vedanti Systems Limited - Ex. 2015
`Page 25
`
`

`
`U.S. Patent Nov. 15, 1988
`
`Sheet 25 of 32
`
`4,785,349
`
`Sl7
`
`F/6.48
`- I
`VIDEO RAM 4820..--r - - - - -
`COMPRESSED
`Y I Q
`STORE
`
`:
`
`I
`I
`
`REGION
`LOCATION
`TABLE
`
`4824
`
`4826
`
`BIT MAP
`QJRRENT
`FRAME
`
`I
`I
`\ I /
`
`BIT MAP
`PREV.
`FRAME
`4828
`I
`I I
`I
`
`\
`
`DISPLAY
`Bu=FER
`~I
`
`' - - - - - - _...l
`
`S20 OUT TO
`DISPLAY 36
`4ro4
`y
`I
`Q
`
`D/A
`AND
`MATRIX
`
`4860
`
`Vedanti Systems Limited - Ex. 2015
`Page 26
`
`

`
`U.S. Patent Nov.15, 1988
`
`Sheet 26 of 32
`
`4,785,349
`
`REGION
`1YPE
`REGION DIPIE:NSk:N
`ABSOLUTE
`RELATIVE LOCATION
`(HEIGHT,
`DPCMOR (UPPER LEFT
`DYAD
`CORNER) WIDTH)
`.....
`......
`(ONE ENTRY PER REGION) F7G. 49
`
`X y
`
`H W
`
`OTHER VALUES
`
`"C" ( ABS REGIONS)
`Xo Yo ( REL. OR
`DYAD REGIONS)
`
`,..,
`
`..
`
`I..
`
`200
`
`I ABS
`~
`
`(C=90)
`
`REL
`Xo Yo
`=5,7
`REL
`ABS
`D
`(C=75)
`p 6,-3
`DYADIDPCM c 1DYAD
`M 2,2
`4,5
`
`256
`
`FIG. 60
`
`TYPE
`ABS
`REL
`ABS
`DYAD
`DPCM
`DPCM
`REL
`DYAD
`
`H w
`y
`X
`100 128
`0
`0,
`0
`128
`100 128
`100 50 128
`0
`150 50 64
`0
`64 150 50 64
`128 100 100 64
`192 100 50 64
`192 150 50 64
`
`FIG. 51
`OTHER
`90
`5, 7
`75
`4,5
`
`6,-3
`2, 2
`
`Vedanti Systems Limited - Ex. 2015
`Page 27
`
`

`
`U.S. Patent Nov. IS, 1988
`
`Sheet 27 of 32
`
`4,785,349
`
`FIG. 53
`
`P(X, y)=P'(x,y) +AX+ By+ C
`
`AREA>-------. RELATIVE FILL DECOOER ~
`
`RELATIVE
`FILL
`DATA FROM
`MAP4822
`
`5
`
`BIT
`MAP
`4826
`
`BIT
`MAP
`4828
`
`FIG.~4
`
`Vedanti Systems Limited - Ex. 2015
`Page 28
`
`

`
`U.S. Patent Nov.15, 1988
`
`Sheet 28 of 32
`
`4,785,349
`
`5
`
`0000
`ooo
`00
`
`H
`
`w
`P(x~)=Ax + By+ C
`RG.M
`
`ABSOLUTE FILL DECODER 4854
`
`AREA >-------,
`
`SLOPE
`DATA
`FRO~'tAP
`4822r----_.____._,
`DE-QUANT
`5672 PROCESSOR
`
`BIT
`MAP
`4826
`
`.. c ..
`DATA
`
`c
`
`FRC».i
`REGION
`TABLE
`4824
`
`FIG. 56
`
`Vedanti Systems Limited - Ex. 2015
`Page 29
`
`

`
`U.S. Patent Nov. IS, 1988
`
`Sheet 29 of 32
`
`4,785,349
`
`Po= 128 + D
`
`5702
`
`P1=P+D
`x
`p
`~
`!~l 00
`00
`'oooooo
`Q
`00000
`oooooo
`
`F/6.67
`
`a·=a+o
`
`FIG. 58
`DPCM FILL DECODER 4852
`
`DPCM
`DATA
`
`BIT
`MAP
`4826
`
`5802
`
`LATCH
`
`5804
`
`x,y,H,W
`
`AOORESS
`CONTROu.ER
`
`FROM
`REGICJi
`TABLE
`4824
`
`Vedanti Systems Limited - Ex. 2015
`Page 30
`
`

`
`U.S. Patent Nov. 15,1988
`
`Sheet 30 of 32
`
`4,785,349
`
`f£GION
`AREA
`I
`2-3
`4-7
`9-15
`16-31
`>32
`
`QUANT.
`(BITS)
`3
`4
`5
`6
`7
`8
`
`NU~tR
`LEV LS
`8
`16
`32
`64
`128
`256
`FIG. 59
`
`SHIFT
`VAWE
`5
`4
`3
`2
`I
`0
`
`4853 FIG. 60
`i -AREA DtlkrnR -:
`
`6006 1
`
`1
`I
`1
`I
`' - - - - - - - - _j
`
`H,W
`FROM
`REGION
`TABLE
`4824·
`
`6008
`
`AREA
`LOOK-UP
`TAB..E
`
`FILL DATA IN
`
`SHIFT
`VALUES
`
`FILL DATA OUT
`
`Vedanti Systems Limited - Ex. 2015
`Page 31
`
`

`
`U.S. Patent Nov. IS, 1988
`
`Sheet 31 of 32
`
`4.,785.,349
`
`FIG. 61
`
`1/
`
`I
`
`I
`I
`
`c
`)
`
`r---6110
`
`Yo
`
`"
`GGC0@ ......._, 6120
`T) @(9(9@
`"
`T
`0i)~(9@
`6(§)(5)@
`- _j___
`
`TABLE LOOK-UP (CODEi )= R,i, S.i
`A.i = C;, + R.i. B,i = D,i + S.i
`
`FIG. 62
`
`t 20 P(J0,13)
`
`s
`
`~
`"'
`K7
`/
`~··
`0~K6(14,14)
`/
`10
`A
`,
`
`K5(6,6)
`
`-20
`'
`-10
`~ - /
`K3----11
`, / -JO
`~K2
`
`/
`
`Vedanti Systems Limited - Ex. 2015
`Page 32
`
`

`
`U.S. Patent Nov.15, 1988
`
`Sheet 32 of 32
`
`4,785,349
`
`6310
`
`TABLE
`ADDRESS
`GEN
`
`6320
`
`DYAD
`MEMORY
`
`DYAD FILL
`DECODER
`4855
`
`DYAD
`FROM
`4830
`
`X,Y, H, W,Xo,Yo
`FROM REGION
`TABLE4824
`
`LATCH
`
`L....----, Xo)'o
`X;v',H,W
`
`ADDRESS~~
`COUNTERS
`
`6332
`
`FIG. 63
`
`6360
`
`BIT
`MAP
`4826
`
`4858
`
`6340
`
`BIT
`MAP
`4828
`
`NT£GER
`MSB
`
`Vedanti Systems Limited - Ex. 2015
`Page 33
`
`

`
`1
`
`4,785,349
`
`DIGITAL VIDEO DECOMPRESSION SYSTEM
`
`FIELD OF THE INVENTION
`This invention relates generally to systems for reduc- 5
`ing the amount of digital data required to represent a
`digital video signal and particularly to systems for de(cid:173)
`coding a compressed digital video signal representative
`of a full motion color video signal.
`
`2
`comprising control means for causing said first decod(cid:173)
`ing means to decode said region descriptive codes prior
`to the decoding of said region fill codes by said second
`·
`decoder means.
`In accordance with a further aspect of the invention,
`said region descriptive and fill codes are conveyed by
`separate segments of said video input signal, said seg(cid:173)
`ments being individually variable length coded in ac(cid:173)
`cordance with their respective statistical distributions
`10 and said decoding apparatus includes a multimode vari(cid:173)
`able length decoder for variable length decoding said
`region descriptive codes in accordance with a first sta(cid:173)
`tistical code and for variable length decoding said re-
`gion fill codes in accordance with a second statistical
`code, said decoding apparatus further including circuit
`means coupled to said input means for deriving said
`statistical codes from data included in a third segment of
`said video input signal.
`
`BACKGROUND OF THE INVENTION
`The need for compression to facilitate recording of a
`digital video signal on relatively narrow-band media,
`such as a compact disc (CD), has been recognized. In a
`system proposed by Takahashi et al. in U.S. Pat. No. 15
`4,520,401, a digital video signal is encoded using differ(cid:173)
`ential pulse code modulation (DPCM) for recording on
`a digital audio disc. In the known system, luminance (Y)
`and chrominance (R- Y, B-Y) components of a video
`frame are separately compressed using DPCM. A cir- 20
`cuit divides the components into picture element data
`groups of a specific number of rows or columns which
`are adjacent on a screen. A header signal is provided
`having a synchronizing signal, a picture mode identifi(cid:173)
`cation signal and a picture information quantity identifi- 25
`cation code. The header signal is added to the beginning
`position of each of the divided picture element data
`groups to produce a digital video output signal having a
`signal format in which the digital luminance, the two
`kinds of digital color difference signal and the header 30
`signal are time sequentially multiplexed and recorded.
`In an example of the Takahashi et al. system still
`frames of digital video are recorded and updated at a
`rate of about four seconds per frame. The division of the
`compressed data into groups of lines with each group 35
`containing complete color information provides a psue(cid:173)
`do-motion effect in that the line groups may be sequen(cid:173)
`tially updated while displaying the previous frame
`thereby providing a partially moving picture.
`
`BRIEF DESCRIPTION OF THE DRAWING
`The foregoing and further features of the invention
`are shown in the accompanying drawing in which like
`elements are denoted by like reference designators and
`in which:
`FIG. 1 is a block diagram of a digital video interac(cid:173)
`tive system embodying the invention providing record(cid:173)
`ing and reproduction of full-motion video, multi-chan(cid:173)
`nel digital audio and auxiliary (e.g., interactive) data
`using a compact disc read-only memory (CD-ROM) as
`the recording media;
`FIG. 2 is a block diagram of a digital video encoder
`used in a recording portion of the system of FIG. 1;
`FIGS. 3-9 are diagrams illustrating digital video
`signal formats at various stages of processing in the
`encoder of FIG. 2;
`FIGS. 10-12 are diagrams illustrating two methods of
`processing "oversized" frames in the encoder of FIG. 2;
`FIG. 13 is a block diagram of a formatter providing
`40 padding and dithering for use in the encoder of FIG. 2;
`FIG. 14 is a block diagram of a pre-compression
`processor used in the encoder of FIG. 2;
`FIG. 15 is a block diagram illustrating details of a
`portion of the processor of FIG. 14;
`FIG. 16 is a block diagram of a digital video compres(cid:173)
`sor used in the encoder of FIG. 2 providing intra-frame
`and inter-frame region-specific coding, quantization by
`region area and frame-segmented variable length cod(cid:173)
`ing;
`FIG. 17 is a flow chart illustrating operation of an
`intra-frame coder used in the compressor of FIG. 16 for
`compressing still video frames and the first frame of a
`motion video sequence;
`FIG. 18 is a region diagram illustrating image edge
`analysis used in the compressor of FIG. 16;
`FIG. 19 is a block diagram of a roughness estimator
`providing split/fill decisions for use in the compressor
`ofFIG. 16;
`FIGS. 20-23 are region diagrams illustrating bi-linear
`absolute fill coding used in the compressor of FIG. 16;
`FIG. 24 is a region diagram illustrating measurement
`of boundary errors;
`FIG. 25 is a block diagram of an audio compressor
`used in the encoder of FIG. 2;
`FIG. 26 is a diagram illustrating quad-tree regional(cid:173)
`ization;
`FIG. 27 is a diagram illustrating binary tree regional(cid:173)
`ization of an image in the compressor of FIG. 16;
`
`65
`
`SUMMARY OF THE INVENTION
`A system for compressing and formatting a full mo(cid:173)
`tion color digital video signal is described herein. The
`present invention is directed to satisfying the need for
`apparatus for decoding a compressed signal of the type 45
`herein described to enable display of full motion video
`images at normal video frame rates.
`Decoding apparatus in accordance with an aspect of
`the invention includes means for providing a com(cid:173)
`pressed digital video signal of a type in which each 50
`frame thereof comprises a plurality of coded regions,
`each region being encoded by a region desrriptive code
`and a region fill code, said region descriptive codes
`conveying data representative of the size and location
`of said regions within said frames, said region ftll codes 55
`conveying pixel amplitude indications for said regions.
`A first decoding means, coupled to said input means,
`decodes said region descriptive code to provide region
`address data. A second decoding means, coupled to said
`input means, decodes said region fill codes to provide 60
`pixel values. A memory means, coupled to said first and
`second decoding means, stores said pixel values for said
`regions at addresses provided by said address data to
`provide a decoded bit map containing one frame of
`pixels.
`In accordance with another aspect of the invention,
`said region descriptive and fill codes are conveyed by
`separate segments of said video input signal and further
`
`Vedanti Systems Limited - Ex. 2015
`Page 34
`
`

`
`4,785,349
`
`3
`4
`FIG. 58 is block diagram of apparatus providing the
`FIGS. 28 and 29 are examples of split/fill coding
`diagrams for the regionalized image of FIG. 27;
`region DPCM decoding of FIG. 57;
`FIG. 59 is a table listing of area dependent adaptive
`FIGS. 30 and 31 are examples of "tree" codes for the
`coding diagrams of FIGS. 28 and 29, respectively;
`quantization values for "dequantizing" pixel data in the
`FIGS. 32A-J are region diagrams illustrating edge 5 decoder of FIG. 48;
`distribution analysis for determining a most favorable
`FIG. 60 is a block diagram of apparatus for providing
`area dependent dequantization in the decoder of FIG.
`region split direction;
`FIG. 33A is a flow chart for computer apparatus for
`48;
`FIGS. 61 and 62 are diagrams illustrating dyad de(cid:173)
`determining a most favorable split direction in the com-
`pressor of FIG. 16 by analysis of the distribution of 10 coding in the decoder of FIG. 48; and
`FIG. 63 is a block diagram of a dyad decoder for use
`horizontal and vertical edges in a region;
`FIG. 33B is a table listing of parameters for the appa-
`in the decoder of FIG. 48.
`ratus of FIG. 33A;
`DETAILED DESCRIPTION
`FIGS. 34A and 34B are diagrams illustrating two
`forms of region splitting in the compressor of FIG. 16; 15
`The digital video interactive system of FIG. 1 com-
`FIGS. 35A-35E are diagrams illustrating weighted
`prises a recording system 6 and a playback system 8.
`filt
`·
`· th
`d.
`of FIG 16·
`The recording system includes sources 10, 12 and 14
`me mn 1 enng m
`e compressor
`.
`,
`d.
`'II
`tr tt'ng non lt'near
`which provide, respectively, a multi-channel sound
`FIGS 36A 36c
`are mgrams 1 us a
`-
`.
`-
`signal S1, a color motion video signal S2 and an auxil-
`low-pass ftltering for use in the encoder of FIG. 16;
`d
`FIG. 37 is a diagram illustrating finding a most favor- 20 iary data signal S3. An encoder 16 encodes an com(cid:173)
`bines signals S1, 52 and 53 to form a digital recording
`able split direction by polynomial fit comparisons;
`signal 54 (hereinafter, "bit-stream") that is recorded on
`FIG. 38 is a flow chart for computer apparatus imple-
`a compact disc read-only memory (CD-ROM) disc 20
`menting the split direction method of FIG. 37;
`by means of a CD-ROM recorder 18. Auxiliary data
`FIG. 39 is a flow chart illustrating operation of an 25 signal 53 may comprise interactive data associated with
`inter-frame coder used in the compressor of FIG. 16 for
`the video or audio signals or some other type of digital
`coding the second frame and all subsequent frames of a
`data which may be independent of the audio or video
`motion video sequence;
`data.
`FIG. 40 is a diagram illustrating region translation in
`The average data rate of the bit-stream S4 is con-
`the inter-frame coder of FIG. 39;
`30 trolled by a selection of encoding parameters to equal
`FIGS. 41 and 42 are vector and flow chart diagrams,
`the standard CD-ROM record/playback bit-rate of
`respectively, illustrating selection of a best region
`about 1.2 mega-bits per second. The parameters are
`search direction in the inter-frame coder of FIG. 39;
`selected, as will be explained, so as to enable recording
`FIG. 43 is a diagram illustrating region translation
`of up to one hour of full-motion digitally encoded color
`and relative coding used in the inter-frame coder of 35 video, multi-channel digital audio and auxiliary data on
`FIG. 39;
`CD-ROM disc 20.
`FIG. 44 is a table illustrating region area dependent
`The encoding of the digital full-motion color video
`adaptive quantization used in the compressor of FIG.
`portion of the recording signal to meet the relatively
`16;
`low channel capacity of the CD-ROM disc player re-
`FIG. 45 is a flow chart illustrating operation of the 40 quires very substantial data reduction. In a specific
`apparatus in FIG. 16 providing area dependent quanti-
`example to be described, this data reduction is on the
`order of about 150:1 for an exemplary video frame rate
`zation of FIG. 44;
`FIG. 46 is a block diagram of a stream segmented
`of 30 FPS (frames per second). To meet this critical
`variable length coder for use in the compressor of FIG.
`requirement, while avoiding visible "artifacts" associ-
`16;
`45 ated with conventional video compression techniques,
`FIG. 47 is a diagram illustrating the format of data
`encoder 16 converts the video signal S2 to a color frame
`"streams" provided by the compressor of FIG. 16;
`sequential component form and separately subjects each
`FIG. 48 is block diagram of a compressed digital
`frame of each component to a number of specially
`video signal decoder used in the playback system 8 of
`adapted processes as will be described. Briefly listed,
`so these include variable sub-sampling, variable inter-
`FIG. 1;
`FIGS. 49, 50 and 51 are examples of table listings of
`frame and intra-frame compression employing what
`data stored in a region location memory of the decoder
`will herein be termed "region-specific" encoding, area
`of FIG. 48 for absolute, relative, dyad and DPCM
`dependent adaptive quantization, "segmented" variable
`coded regions of FIG. 48;
`length coding, reverse frame sequence reformatting,
`FIG. 52 is a block diagram illustrating a memory 55 padding and frame dithering.
`organization for use in the decoder of FIG. 48;
`The selection of the individual processes, the selec-
`FIG. 53 is a diagram illustrating relative region de-
`tion of the share of data reduction provided by each
`coding of an inter-frame coded region by the decoder of
`process and the selection of variable compression pa-
`FIG. 48;
`rameters (e.g., thresholds, operating modes and, partie-
`FIG. 54 is a block diagram of apparatus providing the 60 ularly, when to quit compressing) represents critical
`relative decoding of FIG. 53;
`choices in meeting the objective of encoding full motion
`FIG. 55 is a diagram illustrating absolute region de-
`color video for storage on CD-ROM digital audio tape
`(DA T) or other bandwidth limited media. Such choices
`coding in the decoder of FIG. 48 of an intra-frame
`coded region;
`depend on more than merely the channel capacity of the
`FIG. 56 is block diagram of apparatus providing the 65 CD-ROM media. They depend as well on variables
`absolute decoding of FIG. 55;
`such as the video frame rate, the desired spatial resolu-
`FIG. 57 is a diagram illustrating DPCM decoding of
`tion, certain specific characteristics of the video image
`a region in the decoder of FIG. 48;
`content and on parameters of the decoder that is ulti-
`
`Vedanti Systems Limited - Ex. 2015
`Page 35
`
`

`
`4,785,349
`
`25
`
`6
`One reason for periodically resetting or bypassing
`DPCM encoder 210 is to prevent audio errors, which
`may occur in the CD-ROM transmission system, from
`propagating from frame-to-frame. This feature also
`facilitates subsequent editing of sequences to enable any
`frame to be chosen as an edit point. This feature is im(cid:173)
`plemented as, shown in FIG. 25 by means of a compara(cid:173)
`tor 214 which supplies a reset signal to reset input R of
`audio A DPCM encoder 211 when the byte count of the
`compressed audio signal S6 (produced by a byte
`counter 216) exceeds the byte limit set by a byte limit
`source 218.
`
`5
`mately used for recon