United States Patent 19
`Kalra et al.
`
`USOO595.3506A
`Patent Number:
`11
`(45) Date of Patent:
`
`5,953,506
`Sep. 14, 1999
`
`54 METHOD AND APPARATUS THAT
`PROVIDES ASCALABLE MEDIA DELIVERY
`SYSTEM
`
`WO 96/14711 5/1996 WIPO.
`WO 96/23280 8/1996 WIPO.
`WO 97/15149 4/1997 WIPO.
`
`75 Inventors: Devendra Kalra, Fremont;
`Karnamadakala Krishnamohan, San
`Jose; Venkatasubbarao Ramamoorthy
`Ple asainton; Jeyendran Balakrishnan s
`Sunnyvale; Timothy J. Burr, San Jose;
`Kowsik Guruswamy, Mountain View,
`all of Calif.
`
`OTHER PUBLICATIONS
`Moura et al. “Retrieving quality Video acroSS heterogeneous
`networks”, IEEE Personal Communications, Feb. 1996, pp.
`44-54.
`IBM Technical Disclosure Bulletin “Multi-Rate Video
`Transmission Scheme', vol. 38 No. 12, Dec. 1995. pp.
`59-62.
`Doenges, P.K. et al., “Audio/video and Synthetic graphics/
`audio for mixed media,” Signal Processing: Image Commu
`nication, vol. 9, No. 4, May 1997.
`Arikawa, M. et al., “Dynamic LoD for QoS Management in
`the Next Generation VRML,” Proceedings of the Intl. Conf.
`On Multimedia Computing and Systems, Jun. 17, 1996.
`(List continued on next page.)
`
`56)
`
`(73) Assignee: Adaptive Media Technologies,
`Sunnyvale, Calif.
`21 Appl. No.: 08/768,114
`21 Appl. No.:
`9
`22 Filed:
`Dec. 17, 1996
`G06F 15/16; HO4L 7/30
`51 Int. CI.
`52 U.S. Cl. ...................... 395/200.61; 345/428; 348/420
`58 Field of Search ....................... 395/200.61; 370/431,
`Primary Examiner Dung C. Dinh
`370/437; 345/302, 428; 348/17, 18, 19,
`Attorney, Agent, or Firm- Pillsbury Madison & Sutro LLP
`20, 384, 387, 390, 420
`57
`ABSTRACT
`References Cited
`The present invention provides an apparatus and method for
`U.S. PATENT DOCUMENTS
`encoding, Storing, transmitting and decoding multimedia
`348/441
`4,672,444 6/1987 Bergen et al
`information in the form of Scalable, Streamed digital data. A
`... 348/412
`5,068,726 11/1991 Kondo et al. .
`base Stream containing basic informational content and
`... 348/419
`5,196,933 3/1993 Henot ............
`Subsequent Streams containing additive informational con
`... 370/410
`5,574,724 11/1996 Bales et al. ...
`- - - i. tent are initially created from Standard digital multimedia
`526, SE Star".
`... 34.5/502
`data by a transcoder. Client computers, each of which may
`5.675.721 10/1997 Freedman et al.
`5,699,361 12/1997 Ding et al. .............................. 370/431
`have different configurations and capabilities are capable of
`5,737.495 4/1998 Adams et al. ..................... 395/200.49
`accessing a stream Server that contains the Scalable Streamed
`FOREIGN PATENT DOCUMENTS
`digital data. Each different client computer, therefore, may
`access different Stream combinations according to a profile
`asSociated with each different client computer. Thus, the
`Streams accessed from the Server are tailored to match the
`profile of each client computer So that the best combination
`of Streams can be provided to maximize the resolution of the
`3D, audio and Video components.
`
`0577327 A1 1/1994 European Pat. Off..
`s
`.
`A. 4/1994 European Pat. Off..
`O 661885 A1 2. E. s s
`O 687 112 A2 3.1995 EVEN E. Of
`0 739 140A2 10/1996 European Pat. Off..
`0 751 685 A1 1/1997 European Pat. Off..
`WO 94/11993 5/1994 WIPO.
`
`80 Claims, 39 Drawing Sheets
`
`
`
`Adaptive Digital
`Streams Format
`
`14Ab
`
`14A1
`
`Base Stream
`1st
`Additive Stream
`2
`Additive Stream
`3rd
`Additive Stream
`
`Stream
`Management
`Module
`
`Multimedia
`Devices
`
`Nth
`Additive Stream
`
`
`
`6---
`
`1
`
`DISH 1005
`
`

`

`5,953,506
`Page 2
`
`OTHER PUBLICATIONS
`Kudumakis, P.E. et al., “Wavelet packet Based Scalable
`Audio Coding,” 1996 IEEE Intl. Symposium on Circuits and
`Systems (ISCAS) Circuits and Systems Connecting the
`World, Atlanta, May 12–15, 1996; vol. 2, May 1996, InSt. of
`Electrical and Electronics Engineers, pp. 41-44.
`“Transmission of non-telephone Signals, information tech
`nology-generic coding of moving pictures and associated
`audio information: video” ITU-T Telecommunication Stan
`dardization Sector of ITU, Jul. 1995.
`Riegel, T., "Coding of combined natural and computer
`rendered image sequences.” Proc. of SPIE vol. 2451, 1995,
`pp. 207-211.
`Broll, W., et al.; “VRML. Today and Tomorrow,” Computers
`& Graphics vol. 20, No. 3, May 1996, pp. 427-434.
`
`Funkhouser, T.A. and Sequin, C.H., “Adaptive Display
`Algorithm for Interactive Frame Rates during Visualization
`of Complex Virtual Environments,” Computer Graphics
`Proceedings, Annual Conf. Series 1993, pp. 247-254.
`Hoppe, H., Progressive Meshes, Computer Graphics Pro
`ceedings, Annual Conference Series, 1996, pp. 99-108.
`Popovic, J.; and Hoppe, H., Progressive Simplicial Com
`plexes, Computer Graphics (SIGGRAPH '97 Proceedings),
`pp. 217-224.
`Clarke, R.J., Standards for Image Sequence Coding from
`Digital Compression of Still Images and Video, 1995, pp.
`285-299.
`Kuan Hui Tan/Mohammad Ohanbari, Layered Image Cod
`ing Using the DCT Pyramid from IEEE Transactions On
`Image Processing, Apr. 1995, pp. 512-516.
`
`2
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 1 of 39
`
`5,953,506
`
`fig. 1
`
`12
`
`14
`
`Standard Digital
`Multimedia Data
`
`Transcoder
`
`Adaptive Digital
`Streams Format
`
`
`
`Adaptive Digital
`Streams Format
`
`
`
`14Ab
`
`4A1
`
`
`
`1st
`Additive Stream
`2nd
`Additive Stream
`3rd
`Additive Stream
`
`
`
`
`
`
`
`Nth
`Additive Stream
`
`Stream
`Margrent
`
`22
`
`
`
`Multimedia
`Devices
`
`3
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 2 of 39
`
`5,953,506
`
`Jig. 2B
`
`Visual
`Elements
`
`Animation
`3D & Video
`
`
`
`
`
`Audio
`Classical
`Rock & Roll
`Easy Listening
`English
`French
`German
`
`Stream
`Management
`Module
`
`Multimedia
`Device
`
`
`
`German
`
`2O
`
`Dynamic Computational
`& User Profiles
`
`Adaptive
`Streams
`
`Netscape
`MicroSoft
`
`Application
`
`APDU (Telnet)
`
`Presentation
`
`PPDU
`
`Session
`
`SPDU (HTTP/RTP)
`
`Network
`
`Packet (IP)
`
`E.E
`
`Data Link
`
`Frame (LLC)
`
`Physical
`
`Bit (Ethernet)
`
`4
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 3 of 39
`
`5,953,506
`
`Tig. 4
`
`24
`
`H- Video Sequence -
`
`
`
`
`
`28-1
`28-2
`28-3
`28-4
`28-N
`
`
`
`
`
`Partition
`Picture
`into Slices
`
`Macroblock Macroblock Macroblock Macroblock Macroblock
`
`30-3
`
`
`
`Block
`
`32
`32-3
`32-5
`
`32-2
`32-4
`32-6
`
`32, 8 x 8 Array of Data
`
`5
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 4 of 39
`
`5,953,506
`
`5Fig. 5
`
`4.
`
`MPEG Coded Video Stream (Input Stream)
`
`Transcode
`
`e
`
`X (3)
`
`X (4)
`
`X(5)
`
`(1)
`
`(2)
`
`X (O)
`
`X ( O) Stream
`
`
`
`
`
`
`
`X(1) Stream
`
`X (2) Stream
`
`X (3) Stream
`
`X (4) Stream
`
`( )
`X(5) Stream
`
`X (6) Stream
`
`X(7) Stream
`
`
`
`
`
`
`
`
`
`
`
`
`
`Tig. 64
`o14|9||19||5||9||19
`325||10|7|2750
`a 7 || ||2||9||
`is 141312||19||2892
`22822, 2008
`3534.3333305
`III || ||
`ECIPIEEE Ed
`
`,
`
`11 1827 3851
`
`HIHL
`
`6
`
`

`

`U.S. Patent
`
`5,953,506
`
`Sep. 14, 1999
`
`Sheet 5 of 39
`
`Fig. 6TB
`1. 6
`1-1/2
`-7
`(15/19/13/1)
`al12/19/1/11
`11%1/1/11
`1114 14
`
`
`
`
`
`
`
`
`
`7
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 6 of 39
`
`5,953,506
`
`T14. 72
`42
`
`50
`Sequence End
`
`Picture Start
`
`
`
`
`
`Picture Start
`
`Drop Frame Code
`
`
`
`58, Picture
`Header
`
`8 4
`
`
`
`54, Group
`Code
`Picture Numbers
`Temporal Reference
`
`
`
`Next Picture Pointer
`
`|| ||
`||
`/ Correction Start Code
`
`N/
`
`|| ||st) stream
`
`
`
`
`
`X (2) Stream
`
`40
`Sequence Start
`
`
`
`Picture Start
`
`
`
`
`
`6 4.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`8
`
`

`

`U.S. Patent
`US. Patent
`
`Sep. 14, 1999
`Sep. 14, 1999
`
`Sheet 7 of 39
`Sheet 7 0f 39
`
`5,953,506
`5,953,506
`
`mIm55w
`
`FImo__m
`
`
`
`|-
`a
`
`mo__m
`
`53mm:
`
`nan
`
`|-
`|-
`
`02%
`
`Sam
`
`E$5
`
`
`
`
`
`mo__w9221$558338
`
`
`
`mo__w932m965
`
`
`
`tfim:Emtflmmocmsumw.ov
`
`Sam
`
`
`
`
`
`89$:$93:$98153me
`
`9
`
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 8 of 39
`
`5,953,506
`
`Tig. 7C
`
`42
`
`Sequence header code
`0x000001B3 (32 bits)
`Horizontal size (12 bits)
`Vertical size (12 bits)
`Pel aspect ratio (4 bits)
`Picture rate
`(4 bits )
`Bit rate
`(8bits
`ME 1( E. 44A
`c
`buffer SIZ
`w
`Constr. par flag (1 bit)
`Load intra qi flag (lbit)
`o
`Load non intra q (1 bit)
`
`Group start code
`0x000001 B8 (32bits)
`ime code (25 bits)
`Close gop
`(1 bit)
`Broken link (1 bit)
`
`46
`
`48
`
`152A
`
`5O
`Picture start code
`0x00000100 (32 bits)
`52A
`Temporal ref (10 bits)
`Next Picture Pointer (16 bits)
`154A
`Drop frame code (8bits)
`Picture cod type (3 bits)
`VBV delay (16 bits)
`Full pel fr vector (1 bit)
`Forward f code (3 bits)
`Full pel bk vector (1 bit)
`Backward f code (3 bits)
`Slice start code
`0x00000101 (32 bits)
`Quantizer scale (5 bits)
`uantizer scale (5 bits)
`
`56
`
`58A
`
`Do all macro blocks
`in the
`Slice
`
`
`
`Sequence end code
`0x000001 B7 (32 bits)
`
`10
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 9 of 39
`
`5,953,506
`
`Tig. 7D
`
`
`
`Sequence start Code
`Ox 000002BX (32 bits)
`
`Picture start code
`Ox 0000020x (32 bits)
`Temporal ref (10 bits)
`Next Picture Pointer (16 bits)
`Drop Frame Code (8bits)
`Slice start code
`Ox 00000101 (32 bits)
`Modified Zig-Zag scan of
`all macroblocks in the Slice
`for the Sigma Stream X(x)
`End of Block Code (2 bits)
`Correction Start Code
`Ox 0000030x (32 bits)
`Correction Stream
`
`Sequence end Code
`Ox 000002Cx (32 bits)
`
`154A
`
`11
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 10 Of 39
`
`5,953,506
`
`s fig. 82.
`
`40
`
`Slice
`
`
`
`E|| || || || ||
`,
`YaYa
`| |
`| Isle III
`
`Macroblocks
`
`
`
`
`
`
`
`
`
`
`
`1514
`
`1312||19|2839 (52
`
`6362 616059 (585756 || 6362 6160|5958 (5756
`
`...6 Total
`Times
`
`12
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 11 of 39
`
`5,953,506
`
`Tig. 94
`
`1 OO
`
`MPEG coded
`video bitstream
`
`Conventional
`MPEG decoder
`
`102
`
`104
`Video sequence {V (n)}
`(pixel domain frames)
`se occuring at frame rate
`of F frames per sec.
`Cr Cb
`(F = 24 fps or 30 fps)
`
`4 : 2 :
`Format
`
`106B
`
`1100 1101
`
`Fu
`temporal
`resolution
`Video
`sequence
`
`Each of
`Y, Cr, Cb
`frames are
`passed
`through
`the E.
`separately
`
`This filter enhances quality
`- - - - - - - - - - - - - - - - -
`Temporal filter
`- 1 N
`Frame store
`1102
`11 On
`
`1
`O6C
`
`Temporal filter
`and
`decimation
`by 4
`Quality
`enhancement
`for F/4 and
`below
`
`|
`
`
`
`Temporal filter
`to enhance
`quality for all
`rates between
`(F, F12)
`
`106A
`
`12OA
`
`{V (n)}
`AM Specific-122A
`MPEG enCOder
`
`Temporally
`subsampled
`output
`video
`sequence at
`frame rate F/2
`frames per sec.
`(1/2)
`
`C Cb
`r
`
`C Cb
`r
`12OC
`
`12OB
`
`Video
`sequence at
`frame rate F/4
`frames per Sec.
`(1/4)
`{V (n)}
`AMT specific
`AMT specific r 122B
`MPEG encoder
`122C-MPEG encoder
`
`Spatial Scaling
`
`
`
`Spatial scaling
`
`124B
`
`Spatial scaling
`
`y (1)
`
`(1/2)
`
`(1/4)
`
`13
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 12 Of 39
`
`5,953,506
`
`5Fig. 9131
`
`XOTranscoder
`Data in is.
`
`sequence start
`Code?
`
`140
`
`
`
`142
`
`144
`
`Write adaptive stream sequence start code
`
`Write MPEG standard sequence
`header type information
`
`146
`
`Write adaptive stream group start code (New I)
`
`148
`
`150
`
`152
`
`154
`
`156
`
`
`
`
`
`
`
`
`
`
`
`Write MPEG standard headers group
`
`Write adaptive stream picture start code
`
`Write MPEG picture headers
`
`Write adaptive stream picture headers
`(see Fig. 9C)
`
`Write adaptive stream slice start code
`
`Write MPEG slice headers
`
`Do & Write all macroblocks in slice
`
`Write Correction Code
`
`Sequence
`end?
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`14
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 13 Of 39
`
`5,953,506
`
`Tig. 9B2
`
`XO-X 7 Transcoder
`
`
`
`
`
`18O
`
`
`
`182
`
`is
`
`sequence start
`Code?
`
`
`
`Find se
`
`Start Code?
`
`184
`
`Write adaptive stream picture start code
`
`
`
`Write adaptive stream slice start code
`
`
`
`188
`
`DO & Write all macroblocks in Slice
`
`190
`
`Write Correction Code
`
`
`
`192
`
`194
`
`sequence?
`
`NO
`
`NO SD- Yes
`
`15
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 14 of 39
`
`5,953,506
`
`Tig. 9C
`
`Update
`pointer for
`next frame
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Ref frame
`previously
`Selected?
`
`
`
`
`
`Are and P
`previously
`Selected?
`
`16
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 15 of 39
`
`5,953,506
`
`
`
`
`
`Jap0000
`
`(/), —{
`
`(99) LOCI
`
`Japo03C]
`
`17
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 16 0f 39
`
`5,953,506
`
`Do all Macro Blocks in the Slice
`
`Tig. 114
`
`faddress escape
`
`yes
`
`Macroblock address escape (ll bits)
`Ob 0000 000 000
`
`NO
`
`
`
`Macroblock address inc (1 - 11 bits)
`
`Macroblock type (1-6 bits)
`
`If macroblock quant
`
`NO
`
`(5 bits)
`
`A.
`uantizer Scale
`
`t
`
`If macroblock motion forward test ( 1 - 11 bits)
`
`If forward f = 1 &&.
`motion hor fr code = 0
`
`
`
`Motion hor fr r ( 1-6 bits)
`
`Motion vert forward r (1-11 bits)
`
`If forward f = 1 &&.
`motion vert fr code = 0
`
`Motion vert fr r (1-6 bits)
`
`C)
`
`18
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 17 of 39
`
`5,953,506
`
`s
`
`(a) Tig. 111B
`
`If macroblock motion backward tles ( 1 - 11 bits)
`
`If backward fl= 1 &&.
`motion hor bk code - 0
`
`Motion hor bk r ( 1-6 bits)
`
`Motion vert backward r (1-11 bits)
`
`mana
`
`If backward fl= 1 &&.
`motion vert bk code = 0
`
`Motion vert bk r (1-6 bits)
`
`If macroblock pattern
`
`Coded block pattern
`(3-9 bits)
`
`
`
`Block Layer
`
`262
`
`
`
`Do all Macroblocks in the slice
`
`19
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 18 of 39
`
`5,953,506
`
`Block Layer
`
`For I = 0 to 5
`
`
`
`
`
`
`
`
`
`
`
`
`
`262
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`if (pattern code(II)
`{
`
`if macroblock intra)
`{
`
`if(I < 4)
`{
`
`dct dc size luminance (2-7 bits)
`if(dc size luminance = 0)
`{
`
`dct dc differential (1-8 bits)
`
`}
`
`}
`
`dct dc size chrominance (2-8 bits)
`if(dc size chrominance = 0)
`{
`
`dct dc differential (1-8 bits)
`
`dct coeff first (2-28 bits)
`
`}
`end of block (2 bits)
`
`
`
`fig, 11C
`
`
`
`Block layer definition for the base Sigma
`Stream X (0)
`
`20
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 19 of 39
`
`5,953,506
`
`s
`
`J 4. 12
`
`
`
`400
`
`Stream Server
`
`
`
`Client Computer
`
`500 1
`
`Client Computer
`#2
`
`500 2
`
`
`
`
`
`Client Computer
`
`5OO 3
`
`Client Computer
`#N
`
`500N
`
`
`
`
`
`
`
`
`
`Adaptive
`Stream
`Server
`
`Adaptive
`Stream
`Client
`
`Adaptive
`Stream
`Server
`
`Adaptive
`Stream
`
`21
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 20 of 39
`
`Tig. 152
`
`5.
`
`s
`
`5,953,506
`
`Receive
`Profile
`
`552
`
`Determine Streams to transmit
`(See Fig. 15B)
`
`554
`
`Transmit (See Fig. 15C)
`
`556
`
`End of
`Session?
`
`558
`
`Yes
`
`Tig. 15B1
`
`Network bandwidth Constraint
`
`
`
`
`
`Video preference
`
`
`
`Select streams
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`552A
`
`552C
`
`22
`
`

`

`US. Patent
`
`”
`
`a
`
`M5
`
`0Lmom:2Eo?8S8%mom2:mm:9:x:2:Ea3%M,8v8m9:9:EE3::cow8m5m08.mm:9:EE3::W08tmm3mmmEN2:NS8:2082m8wawmmmCm2:NB3.9
`
`ownmom09“o;8m8m9mour8::om“mam8*0;8m08ENom,8;:
`
`SEmgmgm8New08£88m;maNSnowno:m?8m8m58
`
`8m9:Em2%08ORof8.6m8mOEEm8vNov08EN9:83
`
`mg3mamm39mmam:22mes“.ma3maQmm;ma9mw:99ween.
`
`mama:Sum«mm:.3
`
`
`.40.gm3mamm3gmQmm:29wee“.emwk3mma?mamaw:2m.33
`gum:3%Qua?Ss
`
`8m0:So8vNov08ORof3E98DEOE8vmowommORof83.m8Em5NS805‘N?8.0.088:88Em5m580new«9comcom35m
`
`aEx:mm:9:PS2:mmaanmom3:m99:5wenoa85w,cow8m5m8m9:3:EE8::8v8m8mm9m:EE8::
`comkmm86.“«mmtmofNS8:308to5vmum5m02m83::
`
`ownmg09‘o;0%08ENom?3::ownmom0?o;8m08ENour8::
`
`23
`
`23
`
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 22 of 39
`
`5,953,506
`
`Tig. 15C
`
`554A
`
`Send adaptive stream I. D. & headers
`
`554B
`
`Send group 2 picture code sequence
`
`554C
`
`554D
`
`Send X 0
`
`Send each of X 1-7
`incrementally as appropriate for
`short code sequence
`
`update? SD
`
`
`
`
`
`Go to review
`profile
`(See Fig. 15A)
`
`Profile
`
`Yes
`
`NO
`
`24
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 23 of 39
`
`5,953,506
`
`Jig. 1641
`
`----------- -
`
`
`
`6O2A
`
`Determine CPU
`8/8
`7/8
`6/8
`
`6O2B
`
`Set video
`preference
`
`See attached
`graph
`(See Fig. 16A2)
`
`604
`
`606
`
`608
`
`610
`
`Establish
`Connection
`
`Send
`profile
`
`Make
`Selection
`
`Data
`
`612
`
`SE) Yes
`
`No
`
`614
`
`End
`
`25
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 24 of 39
`
`5,953,506
`
`Tig. 1642
`
`1.O
`
`
`
`VIDEO ONLY
`BETTER VIDEO
`DEFAULT
`O
`f()
`l --2 BETTER AUDIO
`S.
`PREFA 4
`O.5.
`
`AUDIO ONLY
`
`
`
`28
`
`64
`
`1.28
`
`512
`256
`BWNET
`(kbps)
`
`1024
`
`1536
`
`s fig. 1623
`
`
`
`1.O
`
`CPURA
`
`O5
`
`
`
`Better Audio
`
`>PREFw
`
`Better Video
`
`Default
`
`1.O
`486/66
`
`2.O
`
`4.0
`3.O
`Pentium/166
`
`5.O
`Pentium Pro/200
`
`ADR: Audio decode time
`ratio (LCD platform relative
`to other platforms)
`
`26
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 25 Of 39
`
`5,953,506
`
`Ti
`(B
`ta. 16
`
`62O
`
`Receive stream I.D. & headers
`
`622
`
`Receive group code sequence
`
`626
`
`628
`
`630
`
`632
`
`
`
`
`
`Receive each of X-X7
`(incrementally)
`
`Send data for picture to adaptive
`stream decoder (See Fig. 16C)
`
`Send MPEG result to MPEG
`decoder
`
`
`
`Go to Step 602
`at Fig. 16A1
`and make profile
`
`634
`
`Yes
`
`New profile?
`
`27
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 26 of 39
`
`5,953,506
`
`Tig. 16C
`
`group headers
`
`
`
`
`
`
`
`658
`
`662
`
`
`
`
`
`
`
`reconstruct DCT coefficients
`
`New Slice
`Start Code?
`
`664
`
`666
`
`
`
`668
`
`
`
`Must be new group
`transmit reconstructed BP
`
`28
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 27 of 39
`
`5,953,506
`
`Tig. 17
`
`712A
`
`Compute \
`SG
`Multires
`Encoding
`
`:
`
`- - - - - - - - - - - -
`Bare-bones SG
`
`Remaining SG
`
`
`
`
`
`7 O 712
`
`Read in
`WRML to
`internal
`data
`
`Optimized
`Scene
`Graph
`
`
`
`Compute
`Object
`Multires
`Encodings
`
`Geometric
`Multires
`Encoding
`
`
`
`
`
`
`
`714A
`
`714B
`
`
`
`
`
`Texture
`Multires
`Encoding
`
`Material
`Multires
`Encoding
`
`714C
`
`
`
`
`
`
`
`Texture
`on disk
`
`Material
`On disk
`
`
`
`
`
`Tristrip &
`Compress
`Base
`
`
`
`Compressed Meshes
`
`Global and
`other non
`Adaptive
`data
`
`
`
`
`
`Compress
`Vertex
`Split
`Lists
`
`Base Meshes
`on disk
`
`Compressed Encodings
`
`
`
`VSplit Lists
`On disk
`
`29
`
`

`

`U.S. Patent
`US. Patent
`
`Sep. 14, 1999
`Sep. 14, 1999
`
`Sheet 28 Of 39
`Sheet 28 0f 39
`
`5,953,506
`5,953,506
`
`
`
`09.585.22:
`
`NE.mg
`
`
`
`
`
`moowémwwfisofitmm33%
`
`
`
`<00H8mw132w322396
`
`
`
`mohfimobm28min
`
`
`
`mmofifimw1“an\SEmmwméoZ
`
`
`
`mwowémwb88000
`
`
`
`805.3%“which
`
`
`
`30538:25me
`
`
`
`
`
`59.503:03335:SmEmuommm
`
`ooohflmB0m03%?2:you8%eman—
`
`30
`
`30
`
`

`

`US. Patent
`
`Sep. 14, 1999
`
`Sheet 29 0f 39
`
`5,953,506
`
`
`
`
`
`umwmumaCHmun>mo#maymmHMHoQOvpcflUmcmflmcsnu”muHm>lzmm2lme
`
`
`
`
`
`
`
`
`
`
`
`mmusuxme¢mamflgmpmzwmmUOZImmmqlAwmvcmmuomcmomwnu"Hmvmmmlmmmnmpmo
`
`
`
`
`
`$5$5
`
`
`
`mUuoolimwmmlamnoamHmUmmmlmmempmonu”mumolamnoaw
`
`
`
`
`
`
`
`
`
`unoamlvmcwflmcsnu"mwnsuxmew
`
`
`
`
`
`pgozmlvmcmflmcsHunmamflnmum2¢
`
`
`
`
`
`pHonmIUmcmHmcsnu"mmUOZImmmqlwm#
`
`muum>l£mw2lxmz
`
`31
`
`Amecflnmma
`
`
`
`
`
`pcflomzmfl>omcHGOHum®H>mzowcHUanoznu”mUHoommmpmoHonHw
`
`
`
`
`
`
`
`
`I#wpnmflq_mp30fl4¢nuwmpmmpcwflq
`
`
`
`Ammauov”mmsfim>\mpxnnu"mwnmflq¢
`
`
`
`
`
`
`
`
`
`unoflqqzm>nu”psmflq
`
`31
`
`

`

`U.S. Patent
`US. Patent
`
`Sep. 14, 1999
`Sep.14,1999
`
`Sheet 30 of 39
`Sheet 30 0f 39
`
`5,953,506
`5,953,506
`
`
`
`
`
`
`
`ommmIqmuvHHcoIOZIHHmoImsouwvcmHUHHso“HHQMIoeImeHu..ammoIHHmo
`
`
`
`HHwU#HmpmolHHWUHnu"mumowwneIUM
`mpmommueIUMnu"mumomm
`
`$92.3
`
`
`
`mpmolmmHwUmmmmmnu”mcHUoochAmmvmcHCOHuHuHmmHmHummm
`
`
`
`
`
`
`
`
`
`mcHchonnN~mmHuWOIH~mmquUxnov.mmDHm>~mp>flnu”wQ>eImm
`
`
`
`
`HmpmolMU:IOHMHUQOIwmthmmgwQ>BImmHunHmUmmmImm
`
`
`
`
`
`
`
`
`
`mumolHUmmmueIUMnu”mumoIHUEIUHHHoQOImQ>HImm
`ImHHWo#MomIocHchomIHmwmoHUmImmueUM
`
`chUmcmHchHunmHHWU#
`
`“3mmESHo>
`
`
`
`
`
`
`
`
`
`
`
`
`mmmonQ5>MHoQOoumu>nuxm:mnumNHHHuD.mww
`
`
` H..cwHUHHsUmo¢may>wHqumOpmuHQvpxmcmzpmm:pmSU.02uo”mmSHW>
`
`
`
`
`
`
`pHQHnu”:mHUHHno*momImp>mluxmzmNHHHuD
`
`
`
`
`
`
`
`ImmUozCmHUHH£U#Avaw>Hmwmmv_mpHQHImeozcmHUHH£o#V
`
`IIAAmpHQm
`
`
`
`
`
`cmuvHHSQHIHomImUHqumeImNHHHUDn.mommmIHHmoImmmH
`
`.cmHUHHnU
`
`
`
`
`
`msHm>IUHHQmum”owmmlcwHUHHQUIozHHmoIQSOHU
`
`
`
`
`HH..0_"wde>.WuHQmHunWSHm>IuHHQm
`
`
`
`
`
`
`
`
`
`
`AmvmpHmUm>ummmmmmUozcmHUHHno#HunommmlCmVHUHHSUUHHBIHHmoIIQsonw
`
`IImUHQImnu"cmHWHH£o#
`
`
`
`
`
`
`ANHHH~MHOHKquoHHmoImmmHnoov.mmsHm>I~manNWu”uHHQmI0Bme<
`
`
`
`
`
`AommmIHHmOImmoq_ommmcmgvHHnoanzmsouo
`
`
`.pHQHnu“mmHmHHcoHHmoUUHBUUHMHoommmmmUocIHHHmoUquUmumHoommmwa0:0cMo”mmsHm>
`
`
`
`
`
`
`
`
`
`32
`
`
`
`
`
`
`
`32
`
`

`

`U.S. Patent
`US. Patent
`
`Sep. 14, 1999
`
`Sheet 31 0f 39
`
`5,953,506
`5,953,506
`
`I-flllflflfll
`
`
`
`
`
`$8:muo:“omzwnmvbowcmm
`
`h025m3:555
`
`Em:282695
`
`
`Em:Eon.
`DE.3.& IA
`
`
`
`
`
`
`
`
`
`or:
`
`E6955
`
`vczohmxomm
`
`b_E_x9n_
`
`co_w___oo
`on
`to
`a -
`III-IE
`
` LBEoEmE.
`:3:saw ."l
`
` lewcmwoEF
` howcww
`
`:oEmom $9:
`-----=l--
`
`
`
`Smcmm993mgowcwm83530uomcmmocwE
`cozmmsz
`
`
`060:698an9.220825
`EEEomO!
`
`
`>_cocmmEmmmn29.5298wmom“.umxmuE
`
`
`
`cozfiomcozmficmfi28m3322:2:225;
`
`
`Ear:mnoc695an
`
`coszmto
`
`530825
`
`96o_u=<
`
`
`
`
`
`993m£29230.mcoo.xom
`
`
`
`926.60092me
`
`33
`
`
`
`9::go:#ombmnmvEm]
`
`)
`
`33
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`US. Patent
`
`
`
`Sep. 14, 1999
`Sheet 32 of 39
`Sep. 14,1999
`Sheet 32 0f 39
`Tig. 19
`fig. 19
`
`5,953,506
`5,953,506
`
`
`
`34
`
`34
`
`

`

`U.S. Patent
`US. Patent
`
`Sep. 14, 1999
`Sep. 14, 1999
`
`Sheet 33 Of 39
`Sheet 33 0f 39
`
`5,953,506
`5,953,506
`
`stern.
`
`guys—mommama
`
`mm.@
`
`vomom<x
`
`0mmmvmx
`
`vmmomax
`
`
`
`
`
`
`
`
`
`
`
`IZ
`NN
`146
`La
`
`100[qO
`
`CII
`
`OMH
`QHH
`0 £ T O II
`00 T
`
`OOHB50.30
`
`35
`
`35
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 34 of 39
`
`5,953,506
`
`Tig. 23
`
`Open SSF File to get Server name
`and file name. Call Server with file
`name and profile. Set up the I/O to
`receive data from the server.
`
`Receive global scene data and the
`k-d tree. Set up internal data
`StructureS
`
`75O
`
`752
`
`Draw current frame. While
`drawing, accumulate Visibility
`information and performance
`Statistics
`
`754
`
`
`
`
`
`Communicate the stats to the level
`of detail module to compute new
`information required and old
`information not needed any more
`
`Transmit to server the messages to
`send/stop desired/undesired data
`
`
`
`Merge any data received from
`server into render data
`
`36
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 35 of 39
`
`5,953,506
`
`fig. 24
`
`802
`
`
`
`...
`
`Data
`
`...... -
`
`Insert data into object
`--------------------------------------
`
`Multiplexed
`Streaming
`Data
`
`Current
`.......
`:
`-- Frame Data
`
`804
`
`
`
`
`
`
`
`
`
`
`
`808, Imager
`
`i.l.
`
`- - - - -
`
`
`
`
`
`
`
`814 :
`
`Stream
`Management
`Module
`
`Taverse
`
`
`
`-
`-
`
`- - - - - - - - - - - - - - Data Structure Access
`- Program Flow
`
`37
`
`

`

`US. Patent
`
`Sep. 14, 1999
`
`Sheet 36 0f 39
`
`5,953,506
`
`
`
`omega.EuBE<
`
`
`
`cognac..Ezooam
`
`2&0on09?Alla835%02:2;
`
`
`
`35:2:6%.?
`
`“22x092%a
`
`63Sofie23o
`
`@32662:
`
`252:0583qu
`E!
`
`528Bob0;
`
`38
`
`38
`
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 37 of 39
`
`5,953,506
`
`Tig. 26
`
`
`
`Statistics
`
`LOD Evaluator
`
`-- Add/remove vertices
`+ Change rendering modes
`+ Add remove texture and
`material detail
`+ Increase, decrease Viewport
`size
`+ Change relative priority of
`objects
`+ Suspend / Resume request
`
`Determination of control
`messages for Server
`
`Update of current
`frame data
`
`39
`
`

`

`US. Patent
`
`Sep. 14, 1999
`
`Sheet 38 0f 39
`
`5,953,506
`
`c<
`
`
`
`253323?-cu“Efig:-uego—m
`
`
`
`53$88$88??“EmaQ04na
`
`moatAuo
`
`tSmUVc:
`
`59%uvunv:33E+325:u@325a
`
`mm.@
`
`DOA
`
`40
`
`............................................................o
`
`
`
`
`
`9436uM3895058on8:ng“.8quCOO;u:828mm
`
`40
`
`
`

`

`U.S. Patent
`US. Patent
`
`Sep. 14, 1999
`Sep. 14,1999
`
`Sheet 39 Of 39
`Sheet 39 0f 39
`
`5,953,506
`5,953,506
`
`.vauaga
`
`P
`
`s
`
`.uu
`
`41
`
`41
`
`

`

`1
`METHOD AND APPARATUS THAT
`PROVIDES ASCALABLE MEDIA DELIVERY
`SYSTEM
`
`FIELD OF THE INVENTION
`The present invention relates to apparatus and methods
`for providing a Scalable media delivery System capable of
`encoding, transmitting and decoding multimedia informa
`tion in the form of Streamed digital data.
`
`BACKGROUND OF THE RELATED ART
`Many Standardized formats exist for creating digital Sig
`nals that allow for images and Sounds to be recorded, Stored,
`transmitted and played back. Such formats include the
`MPEG format for digital video, VRML format for 3-D
`graphics and MPEG and WAV formats for digital audio.
`Each of these formats is capable of Storing Sufficient infor
`mation with respect to a particular image or Sound that
`allows for extremely accurate reproduction of the image or
`Sound.
`Despite the fact that these formats allow for conceptually
`distortion free reproduction of images and Sounds, limita
`tions in the computational power of computer Systems and
`network bandwidth limitations prevent reproductions that
`are as accurate as desired while meeting real time con
`Straints. For more compact and distortion free reproduction,
`larger quantities of data and/or faster processing is typically
`required. Accordingly, the digital information that is typi
`cally encoded in a given format provides less than optimum
`resolution So as not to exceed the computational power for
`decoding available in an "average' computer System and the
`network bandwidth limitations. Unfortunately, however,
`computing Systems having computational power and avail
`able bandwidth that is greater than "average' cannot use the
`extra computational power they contain and available band
`width to reproduce images and Sound with even greater
`performance and clarity, Since the originally encoded signal
`contains no further information with which to obtain this
`greater resolution.
`Conversely, if the digital information that is encoded in a
`given format that provides optimum resolution when being
`decoded by a high end computer System, other "average'
`computer Systems are unable to decode all of this additional
`digital information in real time and, therefore, will be unable
`to reproduce any Sound or image at all.
`Accordingly, there is a need to for a method and apparatus
`that allows for the high-end computer Systems to decode as
`much digital information as possible So that they can repro
`duce images or Sounds with optimum resolution for high
`performance computer Systems at the available bandwidth
`and also provide for "average' or low-end computer Systems
`that receive lesser amounts of information corresponding to
`their performance capabilities, as well as taking into con
`sideration bandwidth limitations. Thus, for all of these
`Systems, there is the need to receive digital information that
`is matched to the computational power available.
`Further, there is the need for servers to be able, in real
`time, to determine the amount of digital information to
`transmit and then transmit this digital information while
`minimizing the computational power required to perform
`Such operation.
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`SUMMARY OF THE INVENTION
`It is, therefore, an object of the present invention to
`provide a method and apparatus for reproducing Sounds
`
`65
`
`5,953,506
`
`2
`and/or images with a resolution that is optimized to the
`capabilities of the client computer that is decoding previ
`ously encoded Sounds and/or images.
`It is also an object of the present invention to provide a
`method and apparatus for encoding digital data representing
`Sounds and/or imageS as base Streams and additive Streams
`of digital data.
`It is another object of the present invention to provide a
`method and apparatus for transmitting base Streams and a
`desired number of additive Streams of digital data from a
`Stream Server to a client computer based on a profile
`obtained from the client computer.
`It is a further object of the present invention to provide a
`method and apparatus for decoding base Streams and addi
`tive Streams of digital data to allow for accurate reproduc
`tion of Sounds and images.
`It is a further object of the present invention to provide a
`method and apparatus that allows for variation in resolution
`of different media forms so that the quality of a media form
`Such as Sound can be increased at the expense of the quality
`of another media form, Such as picture image, according to
`the desires of the user.
`It is a further object of the present invention to provide a
`method and apparatus that allows minimal processing by the
`Server to achieve the objects recited above.
`In order to obtain the objects recited above, among others,
`the present invention provides an apparatus and method for
`encoding, Storing, transmitting and decoding multimedia
`information in the form of Scalable, Streamed digital data. A
`base Stream containing basic informational content and
`Subsequent Streams containing additive informational con
`tent are initially created from standard digital multimedia
`data by a transcoder. Client computers, each of which may
`have different configurations and capabilities are capable of
`accessing a stream Server that contains the Scalable Streamed
`digital data. Each different client computer, therefore, may
`access different Stream combinations according to a profile
`asSociated with each different client computer. Thus, the
`Streams accessed from the Server are tailored to match the
`profile of each client computer So that the best combination
`of Streams can be provided to maximize the resolution of the
`3D, audio and Video components. Since different Stream
`combinations can be accessed, this advantageously allows
`for the various combinations of content and resolution that
`are tailored to match that of the Specific client computer. If
`desired, however, the profile can be further adapted to
`increase the resolution of certain characteristics, Such as
`Sound, at the expense of other characteristics, Such as Video.
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIGS. 1 is a block diagram of a transcoder according to
`the present invention for converting Standard digital multi
`media data into digital Streams using a transcoder according
`to the present invention;
`FIG. 2A is a block diagram illustrating a stream manage
`ment module according to the present invention that Selects
`base and additive Streams for use by a multimedia device;
`FIG. 2B an example of digital Streams being used with a
`multimedia device through a network having many client
`devices according to the present invention;
`FIG. 3 illustrates the use of digital Streams according to
`the present invention in application and/or presentation
`layers for media based on the OSI reference transport model;
`FIG. 4 illustrates properties of conventional digital audio/
`video format;
`
`42
`
`

`

`3
`FIG. 5 illustrates a block diagram of an MPEG coded
`Video Stream being transcoded into an adaptive layered
`Stream according to the present invention;
`FIGS. 6A-C illustrates embodiments of adaptive layered
`streams derived from a block of MPEG data;
`FIGS. 7A-D illustrate various adaptive layered streams
`according to a preferred embodiment of the present inven
`tion;
`FIGS. 8A and 8B illustrate the contents of a slice of
`MPEG data and illustrate the preferred embodiments
`method of obtaining adaptive layered Streams for each
`macroblock of MPEG data;
`FIGS. 9A, 9B1A,9B1B, 9B2 and 9C provide a flow chart
`that illustrates a method of creating a base adaptive layered
`stream from a stream of MPEG data according to the present
`invention;
`FIG. 10 provides a flow chart that illustrates a method of
`creating correction codes according to the present invention;
`FIGS. 11A-11C further illustrates step 160 in FIG.9B1B;
`FIG. 12 illustrates an overview of an adaptive stream
`management apparatus including an adaptive Stream Server
`and an adaptive Stream configured computer according to
`the preferred embodiment of the present invention;
`FIGS. 13-14 illustrate a sequence that can be used to
`establish communication between an adaptive Stream Server
`and an adaptive Stream configured computer according to
`the preferred embodiment of the present invention;
`FIG. 14 illustrates a more detailed block diagram of
`components of the adaptive Stream Server according to the
`preferred embodiment of the present invention illustrated in
`FIG. 3;
`FIGS. 15A and 15B1 illustrates block diagrams of a
`Sequence of Steps used at the client computer according to
`the present invention;
`FIG. 15C illustrates a transmit sequence at the server
`according to the present invention;
`FIGS. 16A1-A3, 16B, 16C1-16C2 illustrate sequences of
`operations at the client computer according to the present
`invention;
`FIG. 17 illustrates a flow chart of the 3-D transcoder
`according to the present invention;
`FIGS. 18A-C illustrate types of graphics adaptive data
`according to the present invention;
`FIGS. 19-21 illustrate a scene, bounded Scene and result
`ing K-D tree according to the present invention;
`FIG. 22 illustrates portions of a dictionary according to
`the present invention according to the present invention;
`FIG. 23 illustrates overall operation of the graphics
`Stream processing according to the present invention;
`FIG. 24 illustrates a client computer architecture and
`program flow according to the present invention;
`FIG. 25 illustrates decoder operation according to the
`present invention;
`FIG. 26 illustrates the level of detail evaluation according
`to the present invention;
`FIG. 27 illustrates the level of detail function according to
`the present invention
`FIG. 28 illustrates 3D decoder controlling video
`Sequences and Spatial resolution in dependence upon dis
`tance from the camera according to the present invention.
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`FIG. 1 illustrates a transcoder 10 according to the present
`invention that converts Standard digit