`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
`
`
`
`5,953,506
`5,953,506
`
`
`
`U.S. Patent
`U.S. Patent
`
`Sep. 14, 1999
`Sep. 14, 1999
`
`Sheet 7 of 39
`Sheet 7 of 39
`
`|-
`
`BdIIS
`
`Japeay
`
`|-
`|-
`
`e-80S
`
`|—a0l|§
`
`a0llS
`
`Jepeoy]
`
`aM
`
`Jepeay
`
`
`
`JapesyJapesy
`
`
`
`dnoiygouenbes
`
`a0l|S
`
`ues
`
`aIndid URIS
`
`dnoip
`
`
`
`yeISaauanbas‘Or
`
`
`
`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
`
`
`
`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 21 of 39
`
`5,953,506
`
`sdjgi
`
`sdjol
`
`Sdjg
`
`
`
`[oz|18tS91QMLLZL902912sdjg
`009LIS69hOP2zeLIZO8tzolL—Sd
`009ZIS69bLOPSdjt
`OOb98E16z002EBLSELILOZsdjO|
`OOZLSIGcl8£09L9bcerOGe00dsdjog
`
`096Ord02906hZObOVEOleYStsdjpz
`OZZS6SO8bOlvOBEODEOleOclsdjgt
`096Ov0249O6rsdjpz
`OZZS6SO8rOLYsdjg}
`OOZ:SIGZI@£09L9bCEPsdjoe
`
`8/88/28/9B/SB/bB/EB/eB/LseiSuiely
`8/88/28/9B/SB/B/EB/eB/}S}e1OWI
`GEDst‘fit
`DODST‘Pit
`009ZIG69h10bceceLicO8lCOLsdjgt
`OOZLSLEZLB£09L9bcEbO6200dsdjoe
`096OZ029O6PZOrOSEO22sd
`
`OOZISLEZl8£09L49bcEtbO6e00csdjoe
`
`096OZO49O6PcObO9EOLeOSIsdypz
`
`OzZS6SO8bOlbOBEODEOleOctsdjgh
`OOr98€16200eE8lSrlLILOLsdjot
`€0c18tSOLOLLokGOL29Iesdjg
`
`g/88/28/9B/GBrB/EB/eB/-SyelOUBIG
`8/88/28/9B/SBFB/EB/EB/tSyeiOlUeI
`
`sdjoh
`
`sdjg
`
`UEGST‘Pit
`
`O8€OOFsdjgi
`
`QeGSTAt
`
`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
`U.S. Patent
`
`Sep. 14, 1999
`Sep. 14, 1999
`
`Sheet 28 Of 39
`Sheet 28 of 39
`
`5,953,506
`5,953,506
`
`
`
`
`
`QOL‘wDa4s|DIpIU!
`
`
`
`ZOWIvalsOIUIeUAq
`
`bs
`
`
`
`
`
`4ZOL‘eyep[eqo|sjO1JUaSSa-uON
`
`
`
`
`
`VZOL'SOpOUI|[QISIAUOUJOJBJeposeg
`
`
`
`
`
`ANSUIONH9ZO2'e}ep91N}Xxd|gzoz'eyep
`
`
`
`dZO2'ejep[else
`
`
`
`DO0L'SJea]OSSIQISIAAlf}JopByepaseq
`
`30
`
`
`
`
`
`gooz‘eiepSutuonniedpeneds
`
`
`
`
`
`VOOL‘eyep[eqo|sjo1juassa
`
`30
`
`
`
`Sep. 14, 1999
`
`U.S. Patent
`
`[DSTAb
`
`
`
`spioocaeyei1eqTeqoTDAepeeyeseqeieg
`
`
`
`
`
`
`
`
`
`
`
`SOIN}XOL#STeTISIeWHSOPONFeeT(9S)yderDeusDS#=:
`
`Sheet 29 of 39
`
`
`
`
`
`qJsebzeTutsqzeaJO#BYRSAaTFTOSedS)y4uUTpeubtsun=:
`
`5,953,506
`
`
`
`qUSTTINNA=::UTI
`
`
`
`(8ZT-0):sentea‘e3Aq=::syzUubTT#
`
`
`
`
`
`
`
`quTOdmeT,OFUTuoTIeHtaAeNOFUIPTTOM=::SpATODeYyeedTeqOCTS
`
`
`
`
`#(3U6TT]SQUHTT#=2:eBeqBYOTT
`
`
`
`
`
`qzoyspeubtsun
`
`
`=i:STeTreiene
`
`
`qzoyspeubtsu
`
`=i:seinjyxe#
`
`
`n
`
`qaouspeubtsun=:
`
`
`SeponjeeT9OS#
`
`31
`
`
`
`S]ZTeAQAUSeWXeW
`
`at
`
`
`
`epeeyeseqeieg
`
`eedTeqoT)
`
`SJIeAUSeNxXeW
`
`(qquTyseu
`
`31
`
`
`
`U.S. Patent
`U.S. Patent
`
`Sep. 14, 1999
`Sep. 14, 1999
`
`Sheet 30 of 39
`Sheet 30 of 39
`
`5,953,506
`5,953,506
`
`*SeA=T.“ustpTTYyoSFo#084uQAytToOedsOjSiTqPFYXSeUBy.aAsnN/“ON=Q?_SenTea|asn
`
`
`
`
`9¢zZ03dnAztTosds0}93AqQxOUOYSZTTTIN
`
`
`
`
`cedgueIpTtyDONTTeDdnozy)uezpTtyoa3tidsoLstxy=::ejedqTIED
`
`
`
`
`
`
`
`(Z)S3TqpeazesoysapoNUsIpTTyo#=::coedsuezpTTyuitTT30_-dnozy
`
`
`
`
`
`
`(Z=TT‘A=0T‘X=TO‘“TT®8O0FeeT=00)isenTea_‘s4tqZ=::3TTdsOLstxy
`-SSPONUSIPTTYO#(P)pearessy)|SITqp-sepoNnUSIPTTUF)
`~
`
`
`
`
`
`
`
`
`Butpunogq=z/8907300=[‘807,py=QO):sentTea‘aqhq=::sddAyas
`
`
`__SATQ_UStpTTyo#€=:
`_((s3TqQQg
`
`
`
`ejyeqddSZepeeHdS=::Butpoouq§(qs)buTuotyrqzedtetieds
`
`
`
`USAPTTYO#ZOqO3AQAXONSZTTTIAQ=::soedgTTe9jeeT
`
`
`[eqeqApHotTytoedgedAygs)edk,dg=::zZepeeyas
`
`
`(9edg[Teoyeeq|oadsUsIPTTYO“yatmdnor9
`
`
`
`4Tq[=i:UsIpTtTuo#oqaAqAXONSZTTTIN
`eqeqAPH“otgtoedseddyds(SounTOA_STTSO#x0Og~huTpunog|=::ejegIPH8°27,Pwe1eqIPHeet,py=::
`
`
`
`
`
`
`
`OENTeAATTdS=::oedguezpTtuyONTTe9gdnozy
`[t’"g]‘SATqG=itSNTeAattdstoenTea
`
`
`
`
`CESTPa
`
`
`Trec#[eqed|TT80)=i:eleqser]Py
`
`
`
`ejeq887]pM=::e3eqds
`
`
`
`
`
`jutpoubtsun=::STTeO#
`
`
`
`
`
`:SOnTeaA4ATQ[TT=::usIpTTYyoD
`
`32
`
`
`
`
`
`
`
`sepouou=QOTT99YATMpejzetoossesepou=[TT8°0UTMpajzetToosse
`
`“usapTTyo
`
`32
`
`
`
`U.S. Patent
`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 31 of 39
`
`5,953,506
`5,953,506
`
`
`
`JoyejodiajujUoNneJUsHO
`
`Joyejodsejyu|
`
`didolpny
`
`Oo
`
`Saeed
`
`UOISI||O
`on
`to
`a -
`psfatale|a[H~
`
`jen]s[|e Josuas
`
`
`AyIqisiAPotoseomy|wity6I7Jods il
`ul
`sosueS
`Uolsod (adA}
`
`
`
`
`
`Josuaselayds“osuassapuljAd“osueseueid
`
`
`apouJoelsqe)suoyejodiayzuy
`
`
`(adA}spoujoessqe)
`OSTfit {=
`
`Aljewoaras
`
`
`
`
`(uonejoY‘uolyejsues]‘ayeoSsapnjoul)Wuoysuesy
`
`
`
`(Ajuoysowaseq0}Bulayas)JASeoe4pexepu|
`
`
`
`aiayds“apulyjAyd‘auo0y‘xog
`
`
`(adA}spoujoeljsqe)
`
`
`
`1Yy617peuoHoe1g
`
`yOWUIOd
`
`
`
`OjujUonebHiaeN
`
`JUIOdMASIA
`
`punosByoeg
`
`
`
`Josuag
`
`
`
`
`
`
`
`
`
`AyIWIxold
`
`
`
`QJBUIPIOODeIN|xaL
`
`33
`
`
`
`
`
`
`
`(adAyapouyoessqe)yybIq
`
`)
`
`33
`
`
`
`
`
`
`
`
`
`
`
`
`Sep. 14, 1999
`Sep. 14, 1999
`
`Sheet 32 of 39
`Sheet 32 of 39
`
`5,953,506
`5,953,506
`
`U.S. Patent
`U.S. Patent
`
`
`
`Tig. 19
`
`Fig. 19
`
`34
`
`
`
`
`
`PopECOaUx|TetTzejen|OOS86SPEX|eanqxet=|OttPepottex|Aaj0WoeD{oot|dI
`PCPe
`
`
`IZ
`146
`
`Ajt4Olidl
`
`CG
`
`100[qO
`
`CII
`
`0 £ T O II
`00 T
`
`U.S. Patent
`U.S. Patent
`
`Sep. 14, 1999
`Sep. 14, 1999
`
`Sheet 33 Of 39
`Sheet 33 of 39
`
`5,953,506
`5,953,506
`
`
`
`
`
`
`
`
`
`
`
`
`
`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
`
`
`
`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 36 of 39
`
`5,953,506
`
`
`uoOaTJOI‘re_NIedg
`[eliayeur‘odeys
`
`
`osngiq“ueiquiy
`
`dINXd],SAIIPPV
`‘oINjxe],PPV
`
`[eanpev|
`oytoadsodé[|—————=|smo]
`
`=
`
`
`J9AI9SWOO/]
`|we}Pll
`
`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
`
`
`
`U.S. Patent
`
`Sep. 14, 1999
`
`Sheet 38 of 39
`
`5,953,506
`
`
`
`10j9R]GO']=0sso.nsWw9}sAsJWSUI
`
`disp>p=>VPSpqu+pyadojs|=(po)poy4
`
`“spPp=3UlodMalAWoys90ur\sIC]mvP0dOT=Ysaeseg
`weeeeececeeeeneeeneeeeeeneeeeeeeeeeennnenee0
`
`URISysPpU
`
`doisp<p0
`
`
`
`
`
`HESpodojs-u=julpy/u-=adojs
`
`
`
`
`
`PV
`
`lefit
`
`dol
`
`40
`
`40
`
`
`
`
`U.S. Patent
`U.S. Patent
`
`Sep. 14, 1999
`Sep. 14, 1999
`
`Sheet 39 of 39
`Sheet 39 Of 39
`
`5,953,506
`5,953,506
`
`*o.e..
`
`P
`
`s
`
`Fig.
`
`-
`
`o?*
`
`A1
`
`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
`t