Method and systems for progressive asynchronous transmission of multimedia data

<img img-format="tif" img-content="drawing" file="IL125643AD00021.tif" id="idf0001" />

πποηΛη» &gt;jwu b\y οηπρη» Nb omwb jvd*wi nw

METHOD AND SYSTEMS FOR PROGRESSIVE ASYNCHRONOUSTRANSMISSION OF MULTIMEDIA DATA OLiVR CORPORATION LTD.

D»i,a ]U&gt;»*n£nip *wbiN 0:31574

METHOD AND SYSTEMS FOR PROGRESSIVE ASYNCHRONOUS

TRANSMISSION OF MULTIMEDIA DATA

FIELD OF THE INVENTION

The present invention relates to methods and systems for encoding digitalmultimedia data for transmission over a network.

BACKGROUND OF THE INVENTION

The following U.S. Patents have been found in a U.S. Patent Search and arebelieved to be generally relevant to the field of the invention: 4,897,367 1/90 Foster et al. 5,119,188 6/92 McCalley et al. 5,122,873 6/92 Golin 5,195,092 3/93 Wilson et al. 5,220,420 6/93 Hoartv et al. 5,236.199 8/93 Thompson, Jr. 5,251,209 10/93 Jurkevich et al. 5,265,248 11/93 Mouiios et al. 5,283,819 1/94 Glick et al. 5,325,423 6/94 Lewis 5,351,276 9/94 Doll, Jr. et al. 5,363,482 11/94 Victor et ai. 5,420,572 5/95 Doiin, Jr. et al. 5,420,801 5/95 Dockter et al. 5,438,658 8/95 Fitzpatrick et al 5,487,167 1/96 Dinailo et ai. 5,495,576 2/96 Ritchey 5,508,940 4/96 Rossmere et ai. 5,519.435 5/96 Anderson 5,553,221 9/96 Reimer et ai. 1

<img img-format="tif" img-content="drawing" file="IL125643AD00022.tif" id="idf0002" />

5,553,222 5,557,538 5,561,791 5,564,001 5,577,180 5,577,258 5,581,783 9/96 9/96 10/96 10/96 11/96 11/96 12/96

Milne et al.Retter et ai.Mendelson et al.LewisReed

Cruz et al.Ohashi

When using various media such as video, audio, text and images, a user generallyretrieves the media from a storage device or "server" connected via a network to manycomputers or users. The server downloads the media to the network and transmits it tothe user at the user's request.

There are two basic limitations involved in such data retrieval: delay between thetime that a user requests the data and the time when the server downloads it to thenetwork, and bandwidth limitations on data throughput and rate of data transmission.The present invention relates to the second limitation.

One example of such a system includes a CD ROM drive and personal computerwhich may be located at the same site. Another example includes a network connectingInternet servers and users’ personal computers. Such networks are installed in order tofacilitate convenient data transmission between users and data distribution from theserver to the users' computers.

When a user retrieves the media from a storage device or server, typicallyconnected via a network, the aforesaid bandwidth limitations affect the amount of timerequired to transmit a video frame from the server to the user, and thus limit the videoframe rate. Moreover, when dealing with object movies and panoramas the files beingtransmitted are extremely large, so that overcoming bandwidth limitations is a criticalenabling factor, even for high bandwidth networks.

Currently, two methods are employed to overcome bandwidth limitations: The firstis to compress the video frame sequence, thereby speeding up transmission time at thecost of additional downstream processing to decompress the frames prior to display.The second is to copy the entire sequence to an intermediate storage device, such as auser's hard disk, to which the user has higher bandwidth access, at the cost of delayingthe viewing of the video until the entire sequence has been delivered. 2

Known network applications involve streaming data from a server to a clientcomputer (hereinafter also referred to as "client"). "Streaming" refers to serial or paralleltransmission of digital data between two computers, by transmitting sequences of bitpackets. For example, installation executables on a network server stream files to aclient computer performing the installation. Servers with large amounts of memory areused to archive digital movies, which are streamed to a client computer for viewing upondemand. Digital video is broadcast from cable stations to subscribers using streaming.Internet browsers, such as Netscape and Microsoft Explorer, are used to stream datafrom a server on the web to a client. Internet web sites can contain enormous databases,such as phone directories for all of the cities in the U.S., photographs from art galleriesand museums around the world, voluminous encyclopedias, and even copies of allpatents ever issued by the U.S. Patent &amp;amp; Trademark Office. Clients using the Internetcan search these databases and then request the server to download specific information.This request initiates a streaming event.

In view of the multitude of bandwidths present in complex client/server systemstoday and the large amounts of data necessary to produce compelling audio, video andimaging presentations, there is a pressing demand for scalable data representation ofmultimedia data, so that it can be delivered for on-line interactive playback in such aform that the transmission rate can accommodate the client bandwidth. The Internet isan example of a complex system where clients with many different bandwidth constraintsdemand multimedia data from server sites. There are several low bandwidth rates formodem transmission over phone lines, higher rates for frame relay lines, higher rates forISDN lines, even higher rates for Tl lines, etc. j

SUMMARY OF THE INVENTION

The present invention seeks to provide an improved method and system for transmitting digital data representing the original over plural transmission links at least some of which have limited bandwidth.

The present invention relates to scalable encoding, which enables two or moreclients, connected to a server by lines having differing bandwidth, to begin playing themultimedia data on-line, and both at the same time, almost immediately after the start ofstreaming, but the lower bandwidth client receives lower quality media than the higherbandwidth client at first. As the media is replayed in the foreground and the bandwidth isfreed, more data streams in via background, and the quality of the media is enhanced.

Without scalable encoding, a client of an Internet application must wait until therequested data arrives, at whatever rate its network line provides. A client with a 14.4Kbs modem line, for example, would have to wait twice as long as a client with a 28.8Kbs modem line. Moreover, if the data was encoded for 28.8 Kbs on-line playback, the14.4 Kbs client would never be able to achieve live playback, since there would be anever-increasing lag in the data stream. Conversely, if the data were encoded for 14.4Kbs on-line playback, the 28.8 Kbs client would receive unnecessarily poor qualitymedia.

On account of the progressive nature of the data representation in accordance withthe present invention, the additional data block arriving in a 14.4 Kbs stream combineswith the previous data block which arrived in a 14.4 Kbs stream, to produce a 28.8 Kbsstreamed version; all that is being sent is the incremental data necessary for the upgrade.The progressive form of the encoding itself provides the ability to achieve scalability.

Another shortcoming of ποη-scaiable encoding as in the prior art is the inability topreview a video sequence. Often a client would like to play a quick preview of a videoclip, before deciding whether or not to download it. The scalable representation of thepresent invention can be used to deliver the video in a preview mode, as the first datablocks. If the client continues to download the video after previewing, the first data 4 block already transmitted is progressively integrated with additional data blocks to create the full viewing video.

The present invention can also be applied to enhance delivery of large still imagesfor multi-resolution gazing. Current technology transmits such images as large files, andcarries out extensive computations for sub-sampiing to lower resolution and zooming into areas of interest for gazing. This makes it very time consuming to interact with largeimages, and as a result it is currently impractical to produce high resolution images forInternet browsing. When deaiing with large images, producers simply sub-sample themto fit entirely within a computer monitor screen, and store the resulting low resolutionimages on web servers. Using the technology of the present invention, producers candeliver high resolution images over the Internet for rapid interactive gazing.

The present invention seeks to provide a scalable representation of multimediadata, enabling the data to be (a) progressively streamed, (b) transmitted asynchronouslyto clients at different bandwidths and (c) played back interactively on-line. Therepresentation is two-dimensional, with one dimension (block number) beingcharacterized by progressiveness in quality, and the second dimension (frame number)being characterized by interactivity.

The representation comprises data blocks which are integrated with one another toproduce successively higher bandwidth versions of the media, the data blocks comprisingencoded frames. The first data block corresponds to the lowest bandwidth, and enablesthe client with this bandwidth to play back the media on-line at the lowest quality. Thesecond data block, when integrated with the first block, corresponds to the next higherbandwidth, and enables the client with this bandwidth to play back the media on-line atthe next highest quality, and similarly for each successive data block.

Moreover, a client with the lowest bandwidth who played the media at the lowquality and freed the bandwidth can continue in background to receive successive datablocks and integrate them with previously received data blocks, resulting in successivelyhigher quality media each time it is replayed. The modular form of the datarepresentation thus makes it possible to both accommodate different bandwidths andprogressively update media quality. A production tool makes it possible for a producerto control modularity and quality settings. 5

<img img-format="tif" img-content="drawing" file="IL125643AD00023.tif" id="idf0003" />

In accordance with the present invention there is provided a method for providingon-line virtual reality movies, comprising inputting a cyclic movie sequence into anencoder, determining the number of portions that each frame of said movie is dividedinto, and forming partial frames, specifying hot-spots and independent objects forinteraction within a partial frame, transmitting the partial frames part by part to a user'sasynchronous database, and displaying said frames on a user's interface.

There is also provided in accordance with a preferred embodiment of the presentinvention a system for producing virtual reality (VR) movies comprising an encoder forpreparing the VR movie for transmission, and a server including a repository for the VRmovie and a transceiver for transmitting the movie, part by part to a user, upon request.

An essential feature of the present invention is the use of a two-dimensionalinteractive progressive database to represent multimedia data, and the storage of thisdatabase in three different forms: for streaming, processing and playback purposes. Thedatabase is calibrated in data blocks of roughly equal size, to deliver the media for on-line playback at a selected range of bandwidths, and in such a way that the higherbandwidth versions are built by integrating data blocks with the lower bandwidthversions. Thus, rather than discard the lower bandwidth data, it is saved and useddirectly to upgrade from low to high bandwidth quality.

The data blocks themseives are comprised of frames which can be randomlyaccessed, thus giving a second dimension (namely, frames) to the progressive database.Thus it is possible to selectively build higher quality versions of some frames and notothers. The mechanism determining which frames to send within each block may becontrolled interactively by the user.

To best appreciate the achievement of the present invention, one should consider itin the broader perspective of streaming technology. There are known two modes ofaccessing streamed data: random access and sequential access. In a random access mode,the client can request the server to transmit data from any position within the stream. Ina sequential access mode, the server can only send a serial stream.

Current Internet streaming technology does not provide random access. Rather,the stream is sent serially in packets. The present invention operates by creating threecopies of the progressive database. A first copy is stored on the server serially. A second copy, which mirrors the server database, is built on the client, with randomaccessibility. These first two copies are in encoded form. The frames in the data blocksfrom the second copy are decoded and stored in the third copy. The third copy isdynamically updated and contains the frames to be displayed in either raw bitmap form,or in intermediate compressed form whereby the decompression is fast enough to keepup with real time interactive display in response to user commands. A by-product of the present invention, when applied to video clips, is the ability todeliver a preview of the video using the first data blocks. This enables the client to playthe preview almost immediately after the transmission begins, and then to quickly decidewhether or not to proceed with the download. Moreover, if the client does continuewith the download, then the first data block already transmitted is integrated withadditional data blocks being downloaded, to form the full view version of the video.Thus, rather than discard the data transmitted for the preview, it is saved and used tocreate the full view frame sequence.

The present invention can also be applied to efficiently deliver large still images atmultiple resolutions for interactive gazing. Each block of the progressive database storesvarious tiles of the image at different resolutions. Smaller tiles are stored at higherresolution. Hot spots are used to link tiles at lower resolution to smaller tiles containedwithin them at higher resolution. When a viewer clicks on a hot spot to gaze, the displayquickly brings up the tile linked to by the hot spot, giving the effect of an instant zoomin. The totality of multi-resolution tiles may comprise the "frames" in this application,and these frames form the interactivity dimension of the database.

The first tile consists of the lowest resolution version of the full image, with hotspots encoded within it. As soon as the first tile is delivered and decoded, the user can atonce begin gazing at the higher resolution tiles, even though the image is of low quality.While the user is viewing the tiles, additional data blocks are being delivered anddecoded in background, and the quality of the tiles is being upgraded as time progresses.In other words, the zoomed in portion of the image being gazed at gets displayed almostimmediately after the streaming begins, but at low quality. The quality improves withtime.

<img img-format="tif" img-content="drawing" file="IL125643AD00024.tif" id="idf0004" />

Die higher resolution tiles correspond to hierarchical "areas of interest" in theimage. Die choice of which areas to mark with hot spots as areas of interest is in thehands of the producer. Dus use of the invention is particularly efficient in the case wherethere is a relatively small number of areas of interest in the full image, so that relativelyfew tiles are encoded at the higher resolutions. Without the present invention, the clientwould have to wait to receive the full image at higher resolution before viewing any partof it at this resolution, even though only small parts of it are of interest. Moreover, eachzoom in and out would be both processor and memory demanding. Viewer interactivitywould be painfully slow.

Diere is thus provided in accordance with a preferred embodiment of the presentinvention a system for transmitting digital data representing the original over pluraltransmission links at least some of which have limited bandwidth including: a digital data source storing digital data representing an original;a digital data receiver receiving the digital data representing an original via one of the plural transmission links having limited bandwidth; and a digital data transmitter operative to transmit the digital data representing an original to the receiver over a transmission link having a limited bandwidth in pluralblocks which are sequentially transmitted at a rate determined by the limited bandwidth,each block being an incomplete collection of data which includes parts of multipleframes, each frame being viewable in a selectable order by the receiver even when lessthan all of the plural blocks have been received, receipt of subsequent blocks by thereceiver being used to cumulatively improve the quality of the digital data viewed by thereceiver.

There is additionally provided in accordance with a preferred embodiment of thepresent invention a digital data transmitter actuator comprising: an organizer operative, when actuated, to access digital data representing anoriginal which is organized in plural blocks for subsequent transmission, each block beingan incomplete collection of data which includes parts of multiple frames, each framebeing viewable in a selectable order by the a receiver even when less than all of the pluralblocks have been received; and

<img img-format="tif" img-content="drawing" file="IL125643AD00025.tif" id="idf0005" />

a receiver instruction interface responsive to interactive inputs from a receiver for actuating the organizer to seiect a given block and at least one given partial frame within the given block for transmission.

There is also provided in accordance with a preferred embodiment of the present invention a digital data receiver including: a data receipt interface receiving digital data representing an original in a pluralityof sequential blocks, each block being an incomplete collection of data which includesparts of multiple frames; a block accumulator for combining plural blocks as they are received for viewingby the recipient; and a viewer including a recipient interface which permits each frame to be viewed inan order selected by the recipient, even when less than all of the plural blocks have beenreceived, combining of plural blocks by the block accumulator being used to improve thequality of the digital data viewed by the recipient.

There is additionally provided in accordance with a preferred embodiment of thepresent invention a method for transmitting digital data representing an original overpiural transmission links at least some of which have limited bandwidth including thesteps of: storing digital data representing an original; receiving at a receiver the digital data representing an original via one of the pluraltransmission links having limited bandwidth; and transmitting the digital data representing an original to the receiver over atransmission link having a limited bandwidth in plural blocks which are sequentiallytransmitted at a rate determined by the limited bandwidth, each block being anincomplete collection of data which includes parts of multiple frames, each frame beingviewable in a selectable order by the receiver even when less than all of the plural blockshave been received, receipt of subsequent blocks by the receiver being used tocumulatively improve the quality of the digital data viewed by the receiver.

There is also provided in accordance with a preferred embodiment of the presentinvention a method for digital data transmission including: 9

<img img-format="tif" img-content="drawing" file="IL125643AD00026.tif" id="idf0006" />

organizing digital data representing an original into plural blocks for subsequent transmission, each block being an incomplete collection of data which includes pans of multiple frames, each frame being viewable in a selectable order by the a receiver even when less than all of the plural blocks have been received; responsive to interactive inputs from a receiver for actuating the organizer,selecting a given block and at least one given partial frame within the given block fortransmission; and transmitting the selected given block and at least one given partial frame to a user.

In accordance with a preferred embodiment of the present invention, the blockaccumulator is operative to combine plural blocks which are distinguished from eachother by their respective frequency bands.

Preferably, the digital data receiver includes a fractal decompression engine.

In accordance with a preferred embodiment of the present invention, the datareceipt interface is operative to initially receive a first plurality of blocks containingrelatively low frequency data and thereafter receive a second plurality of blockscontaining relatively high frequency data and the block accumulator is operative toreconstitute the digital data representing an original from the blocks representingrelatively high frequency and relatively low frequency data.

Preferably, the block accumulator is operative to combine plural blocks havingdifferent sampling.

In accordance with a preferred embodiment of the present invention, the samplingrate of a combined plurality of blocks is equal to the sum of the sampling rates ofindividual ones of the plurality of blocks.

Preferably, the digital data receiver includes a wavelet decoder.

In accordance with a preferred embodiment of the present invention, the blockaccumulator includes a dequantizer which combines blocks each of which containquantized data of a different order, such that accumulation of multiple blocks providescombined data of greater precision than that contained in any single block.

There is additionally provided in accordance with a preferred embodiment of thepresent invention a digital data transmitter actuator including: 10

<img img-format="tif" img-content="drawing" file="IL125643AD00027.tif" id="idf0007" />

an organizer operative, when actuated, to access digital data representing an original which is organized in plural blocks for subsequent transmission, each block being an incomplete collection of data which includes parts of multiple frames, each frame being viewable in a selectable order by the a receiver even when less than all of the plural blocks have been received; and a receiver instruction interface responsive to interactive inputs from a receiver foractuating the organizer to select a given block and at least one given partial frame withinthe given block for transmission.

In accordance with a preferred embodiment of the present invention a first one ofthe plural blocks contains digital data which represents a first approximation to theoriginal.

Preferably, additional ones of the plural blocks, when combined with the first oneof the plural blocks provide additionally accurate approximations to the original.

In accordance with a preferred embodiment of the present invention each of themultiple frames includes a portion of data which can be independently and interactivelymanipulated.

Preferably, the system also includes a block generator operative to receive digitaldata representing the original and to provide the plural blocks.

There is also provided in accordance with a preferred embodiment of the presentinvention a block generator including. a producer interface; and a digital data compressor, operative in response to producer control parametersreceived via the producer interface for receiving digital data representing an original andproviding plural blocks, each block being an incomplete collection of data which includesparts of multiple frames.

In accordance with a preferred embodiment of the present invention the blockgenerator is operative to provide plural blocks which are distinguished from each otherby their respective frequency bands.

Preferably, the block generator includes a fractal compression engine.

In accordance with a preferred embodiment of the present invention, the blockgenerator is operative to decompose the digital data representing an original in relatively 11 high frequency and relatively low frequency digital data portions, and wherein a first plurality of blocks containing the relatively low frequency portion is transmitted by the data transmitter prior to transmission of a second plurality of blocks containing the relatively high frequency portion.

Preferably, the block generator is operative to provide plural blocks by samplingthe received digital data.

In accordance with a preferred embodiment of the present invention the samplingrate of a plurality of blocks is equal to the sum of the sampling rates of individual ones ofthe plurality of blocks.

Preferably, the block generator includes a wavelet encoder.

In accordance with a preferred embodiment of the present invention, the blockgenerator includes a quantizer which produces blocks each of which contain quantizeddata of a different order, such that accumulation of multiple blocks provides combineddata of greater precision than that contained in any single block.

There is also provided in accordance with another preferred embodiment of thepresent invention, a method for encoding original digital video data to be stored on aserver computer for on-line delivery to client computers, including the steps of: encoding the digital video into a database including a series of encoded datablocks, each block including a sequence of encoded frames, with the property thatsuccessive blocks when decoded and integrated together provide successively higherbandwidth versions of the video for on-line playback; storing the database on a server computer; processing a request by a client computer for on-line delivery of the video in orderto determine which data blocks to transmit, so as to accommodate the client bandwidth; transmitting the necessary data blocks to the client;decoding the data blocks on the client computer; integrating the data blocks together on the client computer to reconstruct anappropriate version of the original digital video; and playing the reconstructed video on the client computer. 12

Further in accordance with a preferred embodiment of the present invention, the step of encoding includes a bit-rate control device enabling the producer to pre-select the sequence of bandwidths or quality levels for the database.

Still further in accordance with a preferred embodiment of the present invention,the step of encoding is performed in such a way that the first blocks of the databasecorrespond to previews of the video.

Additionally in accordance with a preferred embodiment of the present invention,the steps of transmitting, decoding, integrating and playing are repeated in succession anumber of times in order to transmit additional data blocks to the client, therebyupgrading the quality of the video while it is replayed.

There is also provided in accordance with another preferred embodiment of thepresent invention a method for encoding original digital audio data to be stored on aserver computer for on-line delivery to client computers, including the steps of: encoding the digital audio into a database including a series of encoded datablocks, each block including a sequence of encoded frames, with the property thatsuccessive blocks when decoded and integrated together provide successively higherbandwidth versions of the audio for on-line playback; storing the database on a server computer; processing a request by a client computer for on-line delivery of the audio in orderto determine which data blocks to transmit, so as to accommodate the ciient bandwidth; transmitting the necessary data blocks to the client;decoding the data blocks on the ciient computer; integrating the data blocks together on the client computer to reconstruct anappropriate version of the original digital audio; and playing the reconstructed audio on the ciient computer.

Further in accordance with a preferred embodiment of the present invention, thestep of encoding includes a bit-rate control device enabling the producer to pre-select thesequence of bandwidths or quality levels for the database.

Still further in accordance with a prefeaed embodiment of the present invention,the steps of transmitting, decoding, integrating and playing are repeated in succession a 13 number of times in order to transmit additional data blocks to the client, thereby upgrading the quality of the audio while it is replayed.

There is also provided in accordance with another preferred embodiment of the present invention, a method for encoding original digital object movie data to be stored on a server computer for on-line delivery to client including, comprising the steps of: encoding the digital object movie into a database including a series of encoded datablocks, each block including a sequence of encoded frames, with the property thatsuccessive blocks when decoded and integrated together provide successively higherbandwidth versions of the object movie for on-line playback; storing the database on a server computer; processing a request by a client computer for on-line delivery of the object moviein order to determine which data blocks to transmit, so as to accommodate the clientbandwidth; transmitting the necessary data blocks to the ciient;decoding the data blocks on the ciient computer; integrating the data blocks together on the ciient computer to reconstruct anappropriate version of the original digital object movie; and playing the reconstructed object movie on the client computer.

Further in accordance with a preferred embodiment of the present invention, thestep of encoding includes a bit-rate control device enabling the producer to pre-select thesequence of bandwidths or quality levels for the database.

Still further in accordance with a preferred embodiment of the present invention,the steps of transmitting, decoding, integrating and playing are repeated in succession anumber of times in order to transmit additional data blocks to the client, therebyupgrading the quality of the object movie while it is replayed.

There is also provided in accordance with another preferred embodiment of thepresent invention a method for encoding an original digital panorama to be stored on aserver computer for on-line delivery to client computers, including the steps of: encoding the digital panorama into a database including a series of encoded datablocks, each block including a sequence of encoded frames, with the property that 14

<img img-format="tif" img-content="drawing" file="IL125643AD00028.tif" id="idf0008" />

successive blocks when decoded and integrated together provide successively higher bandwidth versions of the panorama for on-line playback; storing the database on a server computer; processing a request by a client computer for on-line delivery of the panorama inorder to determine which data blocks to transmit, so as to accommodate the clientbandwidth; transmitting the necessary data blocks to the client;decoding the data blocks on the client computer; integrating the data blocks together on the client computer to reconstruct anappropriate version of the original digital panorama; and playing the reconstructed panorama on the client computer.

Further in accordance with a preferred embodiment of the present invention thestep of encoding includes a bit-rate control device enabling the producer to pre-seiect thesequence of bandwidths or quality levels for the database.

Still further in accordance with a preferred embodiment of the present inventionthe steps of transmitting, decoding, integrating and playing are repeated in succession anumber of times in order to transmit additional data blocks to the client, therebyupgrading the quality of the panorama while it is replayed.

There is also provided in accordance with another preferred embodiment of thepresent invention a method for encoding original digital large still image data to be storedon a server computer for on-line delivery to ciient computers, including the steps of: encoding the large digital image into a database including a series of encoded datablocks, each block including a sequence of encoded multi-resolution tiles of the image,with the property that successive blocks when decoded and integrated together providesuccessively higher quality versions of the tiles for display; storing the database on a server computer; processing a request by a client computer for on-line delivery of the image in orderto determine which data blocks to transmit; transmitting the necessary data blocks to the client;decoding the data blocks on the client computer; 15

<img img-format="tif" img-content="drawing" file="IL125643AD00029.tif" id="idf0009" />

integrating the data blocks together on the client computer to reconstruct an appropriate version of the original multi-resolution image tiles; and interactively displaying the reconstructed tiles on the client computer.

Still further in accordance with a preferred embodiment of the present inventionthe step of encoding includes a compression control device enabling the producer to pre-select the sequence of quality levels for the database.

Additionally in accordance with a preferred embodiment of the present inventionthe step of encoding operates on a plurality of images forming an animation, and eachencoded data block is comprised of multi-resolution tiles from the plurality of images.

There is also provided in accordance with another preferred embodiment of thepresent invention a video processing system operative on digital video data for encodingthe digital video, storing it on a server computer and delivering it to client computers on-line upon request including; an encoder for compressing the digital video into a database inciuding a series ofencoded data blocks, each block inciuding a sequence of encoded frames, with theproperty that successive blocks when decoded and integrated together providesuccessively higher bandwidth versions of the video for on-line playback; a storage device for archiving the database on a server computer;a processing unit for accepting a request by a client computer for on-line delivery of the video and determining which data blocks to transmit, so as to accommodate theciient bandwidth; a transmitter for delivering the necessary data blocks to the client;a decoder for decompressing the data blocks back into video data on the ciient computer; an accumulator for integrating the data blocks together on the client computer toreconstruct an appropriate version of the original digital video; and a player on the client computer for playing the reconstructed digital video.

Additionally in accordance with a preferred embodiment of the present inventionthe encoder includes a bit-rate controller enabling the user to pre-select the sequence ofbandwidths or quality levels for the database. 16

<img img-format="tif" img-content="drawing" file="IL125643AD000210.tif" id="idf0010" />

Moreover in accordance with a preferred embodiment of the present invention the encoder compresses the digital video in such a way that the first blocks of the database correspond to previews of the video.

Further in accordance with a preferred embodiment of the present invention thetransmitter, decoder, accumulator and player repeatedly operate in succession a numberof times in order to transmit additional data blocks to the client, thereby upgrading thequality of the video while it is being replayed.

There is also provided in accordance with another preferred embodiment of thepresent invention an audio processing system operative on digital audio data forencoding the digital audio, storing it on a server computer and delivering it to clientcomputers on-line upon request including: an encoder for compressing the digital audio into a database including a series ofencoded data blocks, each block including a sequence of encoded frames, with theproperty that successive blocks when decoded and integrated together providesuccessively higher bandwidth versions of the audio for on-line playback; a storage device for archiving the database on a server computer;a processing unit for accepting a request by a client computer for on-line delivery of the audio and determining which data blocks to transmit, so as to accommodate theclient bandwidth; a transmitter for delivering the necessary data blocks to the client;a decoder for decompressing the data blocks back into audio data on the client computer; an accumulator for integrating the data blocks together on the client computer toreconstruct an appropriate version of the original digital audio; and a player on the client computer for playing the reconstructed digital audio.

Further in accordance with a preferred embodiment of the present invention theencoder includes a bit-rate controller enabling the user to pre-select the sequence ofbandwidths or quality levels for the database.

Still further in accordance with a preferred embodiment of the present inventionthe transmitter, decoder, accumulator and player repeatedly operate in succession a 17

<img img-format="tif" img-content="drawing" file="IL125643AD000211.tif" id="idf0011" />

number of times in order to transmit additional data blocks to the client, thereby upgrading the quality of the audio while it is being replayed.

There is also provided in accordance with another preferred embodiment of thepresent invention an object movie processing system operative on digital object moviedata for encoding the digital object movie, storing it on a server computer and deliveringit to client computers on-line upon request including: an encoder for compressing the digital object movie into a database including aseries of encoded data blocks, each block comprising a sequence of encoded frames, withthe property that successive blocks when decoded and integrated together providesuccessively higher bandwidth versions of the object movie for on-line playback; a storage device for archiving the database on a server computer;a processing unit for accepting a request by a client computer for on-line delivery of the object movie and determining which data blocks to transmit, so as toaccommodate the client bandwidth; a transmitter for delivering the necessary data blocks to the client;a decoder for decompressing the data blocks back into object movie data on the client computer; an accumulator for integrating the data blocks together on the client computer toreconstruct an appropriate version of the original digital object movie; and a player on the client computer for playing the reconstructed digital object movie.

Further in accordance with a preferred embodiment of the present invention theencoder includes a bit-rate controller enabling the user to pre-select the sequence ofbandwidths or quality levels for the database.

Still further in accordance with another preferred embodiment of the presentinvention the transmitter, decoder, accumulator and player repeatedly operate insuccession a number of times in order to transmit additional data blocks to the client,thereby upgrading the quality of the object movie while it is being replayed.

There is also provided in accordance with another preferred embodiment of thepresent invention a panorama processing system operative on digital panorama data forencoding the digital panorama, storing it on a server computer and delivering it to clientcomputers on-line upon request including: 18

<img img-format="tif" img-content="drawing" file="IL125643AD000212.tif" id="idf0012" />

an encoder for compressing the digital panorama into a database including a series of encoded data blocks, each block including a sequence of encoded frames, with the property that successive blocks when decoded and integrated together provide successively higher bandwidth versions of the panorama for on-line playback; a storage device for archiving the database on a server computer,a processing unit for accepting a request by a client computer for on-line delivery of the panorama and determining which data blocks to transmit, so as to accommodatethe client bandwidth; a transmitter for delivering the necessary data blocks to the client;a decoder for decompressing the data blocks back into panorama data on the client computer; an accumulator for integrating the data blocks together on the client computer toreconstruct an appropriate version of the original digital panorama; and a player on the client computer for playing the reconstructed digital panorama.

Further in accordance with a preferred embodiment of the present invention theencoder includes a bit-rate controller enabling the user to pre-select the sequence ofbandwidths or quality levels for the database.

Still further in accordance with a preferred embodiment of the present inventionthe transmitter, decoder, accumulator and player repeatedly operate in succession anumber of times in order to transmit additional data blocks to the client, therebyupgrading the quality of the panorama while it is being replayed.

There is also provided in accordance with another preferred embodiment of thepresent invention an image processing system operative on large digital image data forencoding the digital image, storing it on a server computer and delivering it to clientcomputers on-line upon request including: an encoder for compressing the large digital image into a database including aseries of encoded data blocks, each block including a sequence of encoded multi-resolution tiles of the image, with the property that successive blocks when decoded andintegrated together provide successively higher quality versions of the image tiles; a storage device for archiving the database on a server computer; 19

<img img-format="tif" img-content="drawing" file="IL125643AD000213.tif" id="idf0013" />

a processing unit for accepting a request by a client computer for on-line delivery of the image and determining which data blocks to transmit; a transmitter for delivering the necessaiy data blocks to the client; a decoder for decompressing the data blocks back into image tile data on the client computer, an accumulator for integrating the data blocks together on the client computer toreconstruct an appropriate version of the original multi-resolution image tiles; and an interactive viewer on the client computer for displaying the reconstructed image tiles.

Additionally in accordance with a preferred embodiment of the present inventionthe encoder includes a compression controller enabling the user to pre-select thesequence of quality levels for the database.

Moreover in accordance with a preferred embodiment the encoder operates on aplurality of images forming an animation, and each encoded data block is comprised ofmulti-resolution tiles from the plurality of images.

There is aiso provided in accordance with another preferred embodiment of thepresent invention a method for caching of data which gets transmitted from servers toclients on a central hub within a network, including the steps of: encoding digital multimedia data into databases including a series of encoded datablocks, each block including a sequence of encoded frames, with the property thatsuccessive blocks when decoded and integrated together provide successively higherbandwidth versions of the media for on-line playback; storing the databases on a multitude of server computers; managing within the hub requests by client computers for on-line delivery of media stored on server computers in order to determine which data blocks to transmit, so as toaccommodate the client bandwidth; transmitting the necessary data blocks from the server and from the hub to the client; storing the data blocks delivered by the server in the cache residing in the central hub; processing within the hub the data blocks it receives; 20

<img img-format="tif" img-content="drawing" file="IL125643AD000214.tif" id="idf0014" />

decoding the data blocks on the client computer; integrating the data blocks together on the client computer to reconstruct an appropriate version of the original digital media; and playing the reconstructed media on the client computer.

Further in accordance with a preferred embodiment of the present invention thestep of managing is performed by: setting inventory flags to indicate which data blocks are currently stored in the hub.

Still further in accordance with a preferred embodiment of the present inventionthe step of managing further including the steps of: communicating with the servers to monitor which media data is outdated;removing from cache the blocks corresponding to the media data which is outdated; and resetting the inventory flags to indicate that the above blocks are no longer storedin the cache.

Still further in accordance with a preferred embodiment of the present inventionthe step of processing comprising the steps of: decoding the data blocks received; integrating the data blocks together to reconstruct appropriate versions of theoriginal digital media; and encoding the reconstructed media versions into an intermediate database for futuretransmission to the clients.

There is also provided in accordance with another preferred embodiment of thepresent invention a proxy system operative on a server/client network for caching of datawhich gets transmitted from servers to clients on a central hub, including: an encoder for compressing digital multimedia data into databases including aseries of encoded data blocks, each block including a sequence of encoded frames, withthe property that successive blocks when decoded and integrated together providesuccessively higher bandwidth versions of the media for on-line playback; server communication iines from the servers to the hub for sending data blocks;client communication lines from the hub to the clients for sending digital data;storage devices for archiving the databases on a multitude of server computers; 21

<img img-format="tif" img-content="drawing" file="IL125643AD000215.tif" id="idf0015" />

a management unit within the huh to process requests by client computers for on- line delivery of media stored on server computers in order to determine which data blocks to transmit, so as to accommodate the client bandwidth; a transmitter for delivering the necessary data blocks on the server communicationlines from the server to the hub, and on the client communication lines from the hub tothe client; a storage device for saving the data blocks delivered by the server communicationlines in the cache residing in the central hub; a processing unit within the hub for processing the data blocks which the hubreceives; a decoder for decompressing the data blocks on the client computer;an accumulator for integrating the data blocks together on the client computer to reconstruct an appropriate version of the original digital media; and a player for playing the reconstructed media on the client computer.

Further in accordance with a preferred embodiment of the present invention the management unit operates by setting inventory flags to indicate which data blocks arecurrently stored in the hub.

Still further in accordance with a preferred embodiment of the present inventionthe management unit operates by monitoring from the servers which media data isoutdated, removing from cache the blocks corresponding to the media data which isoutdated, and resetting the inventory flags to indicate that the above blocks are no longerstored in the cache.

Additionally in accordance with a preferred embodiment of the present inventionthe processing unit comprising: a decoder for decompressing the data blocks received; an accumulator for integrating the data blocks together to reconstruct appropriateversions of the original digital media; and an encoder for compressing the reconstructed media versions into an intermediatedatabase for future transmission to the clients.

<img img-format="tif" img-content="drawing" file="IL125643AD000216.tif" id="idf0016" />

There is also provided in accordance with another preferred embodiment of the present invention a multi-casting unit (MCU) system operative on a broadcasting network for caching of data which gets transmitted from stations to viewers, including: an encoder for compressing digital multimedia data into databases including aseries of encoded data blocks, each block including a sequence of encoded frames, withthe property that successive blocks when decoded and integrated together providesuccessively higher bandwidth versions of the media for on-line playback; station communication lines from the stations to the MCU for sending data blocks;viewer communication lines from the MCU to the viewers for sending data;viewer receiver units for receiving the data sent by the MCU; storage devices for archiving the databases on a multitude of station computers; a management unit within the MCU to process requests by viewers for on-line delivery of media stored on station computers in order to determine which data blocks totransmit, so as to accommodate the viewer bandwidth; a transmitter for delivering the necessary data blocks on the station communicationlines from the station to the MCU, and on the viewer communication lines from theMCU to the viewer receiver units; a storage device for saving the data blocks delivered by the station communicationlines in the cache residing in the MCU; a processing unit within the MCU for processing the data blocks which the MCUreceives; a decoder for decompressing the data blocks on the viewer receiver;an accumulator for integrating the data blocks together on the viewer receiver unit to reconstruct an appropriate version of the original digital media; and a player for playing the reconstructed media from the viewer receiver unit.

Further in accordance with a preferred embodiment of the present invention the management unit operates by setting inventory flags to indicate which data blocks arecurrently stored in the MCU.

Still further in accordance with a preferred embodiment of the present inventionthe management unit operates by monitoring from the stations which media data isoutdated, removing from cache the blocks corresponding to the media data which is 23

<img img-format="tif" img-content="drawing" file="IL125643AD000217.tif" id="idf0017" />

outdated, and resetting the inventory flags to indicate that the above blocks are no longer stored in the cache.

Additionally in accordance with a preferred embodiment of the present invention the processing unit within the MCU including: a decoder for decompressing the data blocks received; an accumulator for integrating the data blocks together to reconstruct appropriateversions of the original digital media; and an encoder for compressing the reconstructed media versions into an intermediatedatabase for future transmission to the viewers.

There is also provided in accordance with another preferred embodiment of thepresent invention a method for streaming multimedia data over a network, including thesteps of: encoding the media into a progressive database indexed according to frame andprogressive block numbers; serializing the encoded database; storing the serialized database on a server; streaming the serialized database to a client upon request; creating a mirror copy of the encoded database on the client computer from thedata which streams in: and decoding the encoded database on the client computer into a sequence of framesfor real time display.

There is also provided in accordance with another preferred embodiment of thepresent invention a multimedia network streaming system, including: an encoder for compressing the media into a progressive database indexedaccording to frame and progressive block numbers; a sequencer for serializing the encoded database;a storage device for archiving the serialized database on a server;a transmitter for streaming the serialized database to a client upon request:a processor for creating a mirror copy of the encoded database on the client computer from the data which streams in; and 24 a decoder for decompressing the encoded database on the client computer into a sequence of frames for real time display.

There is also provided in accordance with another preferred embodiment of thepresent invention a system for transmitting model based data representations of threedimensional images over plural transmission links having limited bandwidth, said systemincluding: a digital data source storing model based data representations of three dimensionalimages; an image processor for rendering views of said model based data representationsinto raster bitmap format; a digital data receiver receiving said digital data in said raster bitmap format over aone of the plural transmission links having limited bandwidth; and a digital data transmitter operative to transmit the digital data in said raster bitmapformat to said receiver over a transmission link having a limited bandwidth in pluralblocks which are sequentially transmitted at a rate determined by the limited bandwidth,each block being an incomplete collection of data which includes parts of multipleframes, each frame being viewable in a selectable order by said receiver even when lessthan all of the plural blocks have been received, receipt of subsequent blocks by thereceiver being used to cumulatively improve the quality of the digital data viewed by thereceiver.

Further in accordance with a preferred embodiment of the present invention themodel based data representations comprise VRML representations.

Still further in accordance with a preferred embodiment of the present inventionthe model based data representations comprise CAD-CAM representations.

Additionally in accordance with a preferred embodiment of the present inventionthe image processor is operative to render only views which are selected by a user.

There is also provided in accordance with another preferred embodiment of thepresent invention a method for transmitting model based data representations of threedimensional images over plural transmission links having limited bandwidth, said systemincluding: storing model based data representations of three dimensional images; 25

<img img-format="tif" img-content="drawing" file="IL125643AD000218.tif" id="idf0018" />

rendering views of the model based data representations into raster bitmap format; receiving the digital data in said raster bitmap format over a one of said plural transmission links having limited bandwidth; and transmit the digital data in said raster bitmap format to the receiver over a transmission link having a limited bandwidth in plural blocks which are sequentiallytransmitted at a rate determined by the limited bandwidth, each block being anincomplete collection of data which includes parts of multiple frames, each frame beingviewable in a selectable order by the receiver even when less than all of the plural blockshave been received, receipt of subsequent blocks by the receiver being used tocumulatively improve the quality of the digital data viewed by the receiver.

Further in accordance with a preferred embodiment of the present invention themodel based data representations comprise VRML representations, and CAD-CAMrepresentations.

Still further in accordance with a preferred embodiment of the present inventionthe image processor is operative to render only views which are selected by a user.

The following definitions are employed throughout the specification and claims: RESOLUTION—The relationship between the number of digital samples per unitof an original and the number of digital samples per unit in a rendered version thereof.Specifically, when dealing with images, resolution refers to the relationship between thenumber of pixels per unit area of an original image or scene and the number of pixels perunit area in a displayed image. Specifically, when dealing with audio, resolution refers tothe relationship between the number of samples per unit time of an original sound and thenumber of samples per unit time in a played sound. QUALITY—The degree to which a rendered version of an original is faithful to theoriginal. Specifically, when dealing with images, quality refers to the degree to which thedisplayed image is faithful to the original image or scene. Normally this is expressed asthe degree to which the approximation of pixei values in the displayed image approachesthe correct pixei values in the original image or scene. Specifically, when dealing withaudio, quality refers to the degree to which a piaved sound is faithful to the originalsound. 26

<img img-format="tif" img-content="drawing" file="IL125643AD000219.tif" id="idf0019" />

FRAME—A portion of an original which can be independently and interactively manipulated. Specifically, when dealing with images, frame refers to a portion of an image or of a collection of images which can be independently and interactively manipulated. Specifically, when dealing with audio, frame refers to a portion of a sound which is delimited in time and can be independently and interactively manipulated. BLOCK—A sequentially transmitted collection of partial data which is used tobuild multiple frames. The frames are built up of one or more sequentially transmittedblocks, whose contents are accumulated. Specifically, when dealing with images, theblock contains image data. Specifically when dealing with audio, the block containsaudio data. PARTIAL FRAME—The part of a frame which is contained in a given block. TILE—A window sized pixel array of a predetermined given size forming part of animage. For example, tiles partition an image into a plurality of arrays, each of whichcontains an identical number of pixels. 27

BRIEF DESCRIPTION OF THE DRAWINGS * " The present invention will be understood and appreciated more fully from thefollowing detailed description, taken in conjunction with the drawings in which:

Fig. 1 and Fig. 2 are simplified block diagrams illustrating a system for scalablerepresentation of multimedia data for progressive asynchronous transmission,constructed and operative in accordance with a preferred embodiment of the presentinvention;

Fig. 3 A is a simplified schematic diagram of the database structure of the presentinvention which includes three databases, embodied within the client-server system ofthe present invention;

Fig. 3B is a simplified diagram of a database structure particularly useful in theciient database of Fig. 3 A, illustrating its two-dimensional nature;

Fig. 4 is an illustration of the operation of a preferred embodiment of the presentinvention;

Fig. 5 is a simplified schematic diagram of a production tool for converting adigital multimedia file into a progressive scalable database representation for storage on aserver computer in accordance with a preferred embodiment of the present invention;

Fig. 6 is a simplified schematic diagram of the structure of a block within the serverdatabase, partitioned into frames which can be accessed randomly in accordance with apreferred embodiment of the present invention;

Fig. 7 is a simplified schematic diagram of a decoder for receiving and integratingdata blocks from a scalable database, to form a version of a digital multimedia object forplayback in accordance with a preferred embodiment of the present invention;

Fig. 8 is a simplified schematic diagram of a scalable progressive database for avideo clip in which the first data blocks are used for previewing the video in accordancewith a preferred embodiment of the present invention;

Fig. 9 and Fig. 10 are simplified schematic diagrams of a system for incorporating ascalable progressive database into a time-based video sequence of frames indexed by twotime scales: a macro and micro scale, in accordance with a preferred embodiment of thepresent invention; 28

<img img-format="tif" img-content="drawing" file="IL125643AD000220.tif" id="idf0020" />

Fig. 11 is a simplified block diagram of a proxy system used to cache in a central hub multimedia data which is transmitted from servers to clients in accordance with a preferred embodiment of the present invention;

Fig. 12 is a simplified block diagram of a system for generating a scalable databasefrom digital media data, by running a compressor in a feedback loop in accordance with apreferred embodiment of the present invention;

Fig. 13 is a simplified block diagram of a decoder for the database generated by thesystem of Fig. 12 in accordance with a preferred embodiment of the present invention;

Fig. 14 is a simplified diagram illustrating a scalable progressive database useful fora large still image in accordance with a preferred embodiment of the present invention;

Fig. 15 is a simplified diagram illustrating a virtual reality system constructed andoperative in accordance with a preferred embodiment of the present invention;

Fig. 16 is a simplified flowchart illustrating operation of the system of Fig. 15; and

Fig. 17 is an illustration of the operation of a preferred embodiment of the presentinvention illustrated in Figs. 15 and 16, permission to reproduce Fig. 17 was granted byTecnomatix, Ltd. 29

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

<img img-format="tif" img-content="drawing" file="IL125643AD000221.tif" id="idf0021" />

The preferred embodiments of the present invention may be better understoodgiven the following technical and theoretical explanation.

The present invention provides a novel method for representing multimedia data.The invention provides a scalable representation, so that the data can be asynchronouslytransmitted to clients having different bandwidth connections, played on-line almostimmediately after the transmission begins, interactively controlled, and also progressivelyupgraded as it is replayed.

Although the present invention is described hereinbelow with particular referenceto image data, it is to be appreciated that it is applicable also to non-image data, such asaudio data.

When addressing bandwidth limitations, it is natural to think in terms of data rates,or velocities. Video players, for example, play at standard rates such as thirty frames persecond (fps), and require the images for display to be available at this rate. If the imagesare already stored on a local hard disk, then all that is necessary is disk access, which isvery fast. On the other hand, if the images are streamed in from a server, then in orderfor on-line playback to be possible before a full download is finished, the rate oftransmission must be great enough to supply the frames at thirty fps. This does not meanthat the network link has to transmit the data equivalent to thirty full frames everysecond. Due to compression, it suffices if the network transmits thirty compressedframes every second.

For example, if the compression achieved is 10:1, then it suffices to transmit at arate of three fps, provided that the client CPU can decompress thirty compressed framesinto full frames every second. In fact, compression is the mediator between the videoplayer and the bandwidth. The piaver does not siow down when bandwidth is low;rather, the compression ratio has to be greater. Should a bottleneck arise, and a frame isnot available when the piaver needs it, then the piaver simply skips that frame, butcontinues to expect frames at the thirty fps rate. The video can be preset at the outsetfor lower rates than thirty fps. but not much lower, since siow video playback breaks thecontinuity between frames, and thus loses the effect of motion. 30

<img img-format="tif" img-content="drawing" file="IL125643AD000222.tif" id="idf0022" />

Thus, realizing that higher compression means lower quality, it can be appreciatedthat users having high bandwidth connections can receive high quality video for on-lineplayback, and users having low bandwidth connections receive low quality video. In anon-scalable setting, it is thus necessary to prepare different compressed media files foreach playback rate and bandwidth combination. For example, four different versions ofthe media could exist for (a) 24 fps playback, 14.4 Kbs bandwidth, (b) 24 fps playback,28.8 Kbs bandwidth, (c) 30 fps playback, 14.4 Kbs bandwidth, (d) 30 fps, 28.8 Kbsbandwidth. As described below, using the present invention a single media file can beused to accommodate all four of these combinations.

In the present invention, the media data is comprised of m frames F\, F2, ..., F„. Aframe can be, for example, an individual frame of a movie sequence, a piece of apanoramic view, an individual segment of an audio signal, or even a sub-sampled versionof a large still image. It can also be a group of such frames, such as for example, a groupof inter-frames between key frames in a video segment, in a case where an H.263 codecis being used. In broad terms, frames are units of interactivity. For example, in objectmovies where interactivity means frame advance, a frame unit is an individual still image,whereas in gazing applications where interactivity means zooming in and out, the frameunits are multi-resolution tiles.

The representation encodes the media data into n data blocks Bt, B2, .... B„preferably of roughly equal size. Each encoded data block B. contains m compressed frame units F{, Fi.....Ff. Thus it is appreciated that the database is arranged in two dimensions, corresponding to blocks and frames. The dimension used for blocks is forachieving progressiveness, and the dimension used for frames is for achievinginteractivity. The frame data can be transmitted in a selective order, but the blocks mustbe transmitted in sequence, since they build cumulatively. This is an essential feature ofthe subject invention.

Data block Bi is used to deliver the media at the lowest bandwidth, say/ Kbs; datablocks Bi and B2 when integrated together, are used to deliver the media at bandwidth/ = 2/ Kbs; and in general, for 1 &lt; k &lt; n, data blocks Bt, B2, Bm when integratedtogether, are used to deliver the media at bandwidth / = k/ Kbs. Each higher bandwidthversion delivers a higher quality rendition of the media. In this way, the representation 31

<img img-format="tif" img-content="drawing" file="IL125643AD000223.tif" id="idf0023" />

can accommodate multiple clients connecting to the network with different bandwidths.

Moreover, a client connecting with bandwidth ft who has downloaded data block Bt and played the media, can continue downloading block Bi in background, since the bandwidth has been freed, and thereby achieve the same quality as bandwidth f&gt; the next time the media is replayed.

Within each block the frames can be accessed randomly and delivered selectively,so that the user can vary the quality level among the frames. For example, a viewer whowants to gaze at frame #3 may instruct the database to send frame #3 data from the firstten blocks, but only one block of data for all of the other frames. The viewer selection iscarried out interactively, through the use of keyboard presses and mouse clicks, as themedia is being played. Whereas for some applications it may be most natural to transmitthe entire blocks in sequence, for other applications it may be more effective to firstdeliver as much data as possible for specific frames at the expense of lowering the qualityof other frames. The two dimensionality of the database, together with its interactiveaccessibility, gives the user complete control over the transmission sequence.

The scalable representation that is the subject of the present invention is embodiedin a production tool which enables the producer to control the bandwidth parameters fk,or equivalently, the qualities of the media versions obtained by integrating blocks £/, ..., Bk- In general, it is not necessary that the blocks be of equal size, nor that thefrequencies be given by k//, although this is the preferred embodiment. Theproduction tool also enables the producer to control the final quality of the highestbandwidth version, or equivalently, the total number, n, of data blocks in therepresentation.

In contrast, if the media data representation is not scalable, but is encoded insteadfor a specific bandwidth / then only clients with bandwidth f or greater can play themedia on-line as it is being downloaded. A ciient with a lower bandwidth than f wouldhave to download the entire data stream to memory in order to begin playback, whichcan take a great deal of time on account of the large file sizes typically used inmultimedia production. A client with a higher bandwidth connection than f would not beable to take advantage of it to receive higher quality media. Moreover, there would beno means of upgrading media quality, even for clients with high bandwidth connections. j-

<img img-format="tif" img-content="drawing" file="IL125643AD000224.tif" id="idf0024" />

other than to transmit an entirely new data stream from the server side, and discard the previously downloaded data.

Applications of the invention include, inter alia, scalable audio and videotransmission, video previewing, progressively rendered object movies and panoramas,large still images, efficient proxy or multi-casting unit (MCU) management for web andother hubs, and VRML transmission, as described hereinafter in greater detail.

Scaleable audio transmission: Digital audio data can be progressively encoded intoa scalable database for asynchronous transmission at different bandwidths. A clientconnected with a low bandwidth line can receive a low quality version of the audio,which can be played back on-line at the low bandwidth as the data streams in. After theaudio is played, additional data blocks can continue to be received and integrated withthe previous blocks, so that the audio is upgraded to higher quality for replay.

Scaleable video transmission: Similar to the description above for the audiotransmission, digital video data can be encoded into a scalable database for asynchronousdelivery and progressive quality upgrade.

For certain time-based video systems, there is disclosed a novel way to incorporatethe scalable database so that progressiveness and immediate playback can be achieved,even in a single-play mode. Specifically, this applies to video systems with two timescales, such as is present in the Apple QUICKTIME* movie player. The first time scale(hereinafter referred to as the “major scale”) is used to advance from one frame to thenext, based on major units of time. The second time scale (hereinafter referred to as the“minor scale”) is a sub-division of the major scale into smaller time units, and is used toincorporate small changes or fluctuations into the frame being displayed. For example,

B the major scale can be advancing through a movie of a bird flying and the minor scale canbe adding fluttering to the bird’s wings. The advantage of such a two-scale player is thatthe decoder, which does the intensive processing to supply the frames, need only run atthe slower rate, e.g. 3 frames per second (fps), governed by the major scale, whereas theviewer, doing the less intensive processing, is playing at the faster rate, e.g. 30 fps,governed by the minor scale.

The subject invention can be incorporated into a system having two time scales asdescribed hereinabove by using the minor scale in a way different from the way that was jj

<img img-format="tif" img-content="drawing" file="IL125643AD000225.tif" id="idf0025" />

originally intended. Instead of being used to introduce fluctuations, it is used to displayprogressively rendered versions of a frame. At each minor time unit, the player displaysthe latest version available of the frame indexed by the major scale. For example,suppose there are ten minor time units within the major time unit during which frame #4is to be displayed. At the first minor time unit, the player initially displays the version offrame #4 which it has available from the first data blocks already processed. Asadditional blocks of data are accumulated and higher quality versions of frame #4become available, the piayer displays those frames at successive minor time units. Thiscontinues for ten minor time units, until the next major time unit, at which time frame #5is to be displayed. The cycle then repeats, and the version of frame #5 which is alreadyavailable is initially displayed at the first minor time unit. Thus it can be seen thatprogressiveness can be achieved by interjecting into the minor scale, the versions of theframes obtained by accumulating successive blocks.

For the user to be able to view the video immediately, without waiting for theentire file to download, the production tool must store the encoded video in the order ofsuccessive blocks. Each partial frame must be handled as if it were an entire frame. Thatis, the production tool must treat the movie as if there were a total of m n distinctframes being encoded. On the other hand, each frame is sent only once to the codec forencoding, and is returned as a series of encoded partial frames. Thus it is necessary topost-process the encoded data file, to rearrange the data items from a frame dominatedorder to a block dominated order. This rearrangement process is referred to as“flattening” in the an.

The player in tum, however, must know that although it is receiving what appearsto be’m · n data items, there are really only a total of m frames. It must decode andaccumulate every successive sequence of m data items with the previous ones, to updatethe frames. The combined effect of the flattening on the production side and the player'sinterpretation on the client side enables seamless integration of the scalable progressivedatabase within a non-progressive video interface. That is, the incorporation ofprogressive blocks does not require any modifications to the existing interface.

Video previewing: When encoding digital video data into a scalable database, thefirst data blocks can be used to generate a preview of the video, restricted to selected

A J-+

<img img-format="tif" img-content="drawing" file="IL125643AD000226.tif" id="idf0026" />

frames. The preview can be played back by the client almost immediately after the streaming begins. Moreover, additional data blocks received are integrated with the data blocks from the preview, to form full view versions of the video.

Object movies: Advertising agencies are using object movies to produceinteractive 3-D virtual reality presentations of merchandise on the Internet. The user canrotate and zoom the 3-D object, and examine it from different viewing angles. Using themethodology of the current invention, object movies can be progressively encoded sothat the viewer can download and begin playing them almost immediately after thestreaming begins. Initially the movie will scale to a quality commensurate with thebandwidth of the user’s network connection, but as the data blocks are received and theuser interacts with the movie, additional data blocks are delivered and integrated with theprevious blocks, resulting in a higher and higher quality movie. An important feature ofthe invention is that, regardless of bandwidth, the user can begin playback and interactionalmost immediately, and does not need to wait for the complete download, as the firstversion of the movie delivered scales itself to the native bandwidth. As playbackcontinues additional data streams in the background and the movie version is upgradedto higher and higher quality.

Panoramas: Panoramas are very large images which the user cannot view in theirentirety, but rather sees within a restricted viewing window. By panning in variousdirections, and zooming in and out. the user navigates through the panorama. Thecontinuous change in viewing window gives the effect of movement within a scene.Similar to the description above for object movies, panoramas can be progressivelyencoded so that the viewer can download and begin navigating through them almostimmediately after the streaming begins. Initially the panorama scales to the clientbandwidth, and after the first data blocks are received, additional data blocks arestreamed in background while the panorama is playing, to provide higher and higherimage quality.

Large still images: Although large high quality still images are not composed offrames in the conventional sense, the large sizes of the image data files makes the presentinvention an effective means for interactive on-line viewing. The frames can be smallimage tiles within the full image at different resolutions, the smaller tiles having higher 35

<img img-format="tif" img-content="drawing" file="IL125643AD000227.tif" id="idf0027" />

resolution than the larger ones. The locations of the tiles can be marked as hot spots.

When the viewer clicks on a hot spot within a specific tile, the database delivers that tile at a higher resolution, giving the effect of a zoom in. Within the higher resolution tile there can be more hot spots, and the zooming can continue through the database.

As a simple example, the first frame within a data block may contain the full imagesub-sampled by 4:1, for example, in each dimension. The next set of frames within thedata block may contain (some subset of) the four quadrants of the full image sub-sampled by 2:1 in each dimension. The next set of frames within the data block maycontain (some subset of) the sixteen quadrants within the above four quadrants at theoriginal resolution. A viewer could see the 4:1 reduction of the original image (the firstblock), click on one of the quadrants and then see that quadrant at a 2:1 reduction (aframe from the second set), and click further on one of its quadrants and then see it atfull scale (a frame from the third set).

Efficient proxv/MCU management: Proxies are large storage devices, located ashubs within networks, used as large caches for data being delivered from servers toclients. Similarly MCUs are large storage devices used as caches for data being deliveredfrom broadcasting stations to viewers, such as cable TV. As data is streamed fromservers to clients or from broadcasting stations to viewers upon request, the proxy orMCU stores the data in a central hub so that it is available for delivery at a highbandwidth if requested again by any of the clients connected to the hub. It plays a similarrole to paging files on a local computer disk, but on a much larger scale and for a muchlarger clientele.

The scalable representation of the subject invention is particularly well suited forproxies and MCUs which operate in asynchronous environments. Server/clientconnections and broadcast transmissions can be of many different bandwidths, and so theproxy or MCU can be accumulating versions of the same multimedia data correspondingto different qualities. Without scalability these versions are all independent of oneanother, and cannot be combined to achieve quality levels other than those originallypreset or combined to save space. Using the scalable representation of the subjectinvention, the proxy or MCU can be optimized to cache the various progressivebuilding blocks. This affords great flexibility in being able to create versions of different 36

<img img-format="tif" img-content="drawing" file="IL125643AD000228.tif" id="idf0028" />

quality levels, and reduces the space requirements.

As a simple example, a first user with a low bandwidth connection f, to the server, who demands a multimedia file, downloads data block Bi, which is then alsosaved to cache on the proxy, and the user receives a low quality version (quality level 1)of the media. A second user with a higher bandwidth connection f to the server, whodemands the same multimedia file, can download data blocks B2 and Bs from the server,and can access block Bt directly from the proxy. The three data blocks are integratedand the second user receives a very high quality version (quality level 3) of the media.Data blocks Bi and B} would then also be stored on the proxy. A third user with a directconnection to the proxy of bandwidth /2 who now demands the same multimedia file, canreceive the high quality version (quality level 2) comprising of blocks B, and B? directlyfrom the proxy. Without a scalable representation it would not be possible for thesecond user, with a bandwidth connection of f2, to receive a quality level 3 versioncorresponding to the higher bandwidth /3, nor for the proxy to deliver to the third user aversion at a quality level different from those directly available in its cache. Moreover,without a scalable representation the proxy memory required to cache the /, /? and fsversions would equal the size of six data blocks, rather than three. It can thus be seenthat the proxy or MCU inherits the scalability from the servers, giving it a great dealmore flexibility in its media delivery to the clients than would be possible in a non-scalable environment. VRML transmission: Virtual reality modeling language (VRML) is a descriptivelanguage for representing and rendering three-dimensional objects. The objects aremodeled as collections of polygonal elements, the description of which forms a VRMLdatabase. Depending on the viewing parameters, the individual elements are processedand the desired view of the object is rendered into a raster bitmap for display. TheVRML representation is rich enough to encapsulate all possible views of the object. Infact, there is an infinity of possible variations in viewing parameters. A user interactswith the VRML object by adjusting viewing parameters, through mouse clicks andkeyboard presses. VRML was first popularized by Silicon Graphics. Their top Irisworkstations, for example, can render on the order of a million polygonal elements persecond. VRML images are characterized by their sharp photo-realistic attributes. 37

<img img-format="tif" img-content="drawing" file="IL125643AD000229.tif" id="idf0029" />

The present invention can be applied to efficiently deliver VRML imagery over aserver/client network, for on-line interaction. Within the VRML environment itself, twoproblems arise when transmitting VRML databases over a network for on-lineinteraction. First, there is the bandwidth limitation, which inhibits the rate oftransmission. Second, there is the intense processing on the client side, necessary torender the many polygonal elements into a bitmap for viewing. It would be preferable tohave the server (typically a more powerful computer) do the rendering, but then it wouldbe necessary to store rendered bitmaps of every possible set of viewing conditions - afeat that would require on the order of terabytes of disk space.

The present invention can be used to mitigate the problem by allowing therendering to be done on the server computer without requiring enormous memory, andyet enable the client to freely interact with the VRML object in an on-line interactivesetting. This is one of many examples involving real-time encoding. The inventionoperates by receiving the viewing parameters from the user, rendering the correspondingimage on the server into a raster bitmap image, encoding the bitmap into progressivepartial frames and inserting them into a two-dimensional server database. The encodeddata within the server database is continually streamed from server to client, enabling theclient to begin viewing a low quality image as soon as the first partial frame data arrives.As the user navigates through the VRML, additional bitmaps are rendered, encoded andinserted into the server database. Whenever the user re-traces steps, so that the viewingparameters are the same as those selected at some previous stage, the server does notneed to render the same bitmaps again. Rather, the streaming simply continues inbackground, and the quality of the image on the client side is enhanced as additionalpartial frames are integrated. Similarly, if the user stays focused on a single view, thenthe bitmap being displayed is enhanced as additional partial frames stream in. Once all ofthe partial frames are integrated, the image has the same sharp photo-realistic quality asis characteristic of VRML images. On the other hand, the user does not have to wait forall of the data to arrive in order to interact with the object, nor does the client computerhave to do the intensive processing to render the VRML database into bitmaps.

Reference is now made to Fig. 1 which shows a block diagram of a system forproviding on-line virtual reality (VR) movies. The system includes a production 38

<img img-format="tif" img-content="drawing" file="IL125643AD000230.tif" id="idf0030" />

workstation 3 for receiving input images and processing same, as will be describedhereinafter. Such input images may be constituted by photographs which are scannedinto the workstation. The output from production workstation 3, being a raw VR movie,is fed into an encoder 5 for preparing the movie for transmission and in turn, applied to aserver 7 essentially used for storage and transmission of the movie to clients, namely,subscribers or user units 9.

Reference is now made to Fig. 2, which shows user unit 9 of Fig. 1 in greaterdetail. Seen is a transceiver 34, an asynchronous memory/database 35, a decoder 36 anda user’s workstation 40.

Typical operation of a preferred embodiment of the present invention is nowdescribed with reference to Figs. 1 and 2. Selected images are introduced in productionworkstation 3 in which the VR movie is produced in accordance with a certain script.The producer at the workstation determines the number and size (for example, in bytes)of the partial frames and also defines the various available interactions between theframes by defining hot spots and objects at 21, using auxiliary standard devices forproducing movies, such as a keyboard, a mouse, speakers and a CPU all designated by23. The product obtained is a raw VR movie, which is a complete VR movie that hasnot been reformatted for transmission. The preparation of the movie for transmission iseffected in encoder 5 where partial frames are generated through an iterative process.

The partial frames are generated by encoder 5 as controlled by the controller 25, asfollows A partial resolution frame or a partial resolution slice of each frame of the VRmovie sequence is generated. One example of such a partial resolution frame is sub-sampled scan lines, e.g., the removal of every IO14 line of a 150 line frame or acompression encoded frame, which partial resolution results in a blurry display. Thepartial resolution frame is then subtracted from the original frame by a partial framesubtractor 27, yielding a residual frame or a remainder frame. This process can berepeated on the residual frame, generating a second partial resolution frame. Theprocedure is also repeated time and time again, until the number (which is determined bythe producer) of partial resolution frames is generated. The net resuit is a set of partialresolution frames that can be recombined into the original full resolution frame.

When this process is completed on each frame of the sequence, the partial 39

<img img-format="tif" img-content="drawing" file="IL125643AD000231.tif" id="idf0031" />

resolution frames are transmitted. The order of transmission follows the script given bythe producer, and commonly, the first partial resolution frame of each frame istransmitted, followed by the second partial resolution frame, and so on. This sequenceof transmission allows for the whole sequence to be viewed in a partial resolution formatthat progressively comes into focus.

Partial resolution frames may be optionally compression encoded, possibly takinginto account similarities between various frames. This is effected in the compressor 29.

Encoded and compressed VR movie parts are passed to a server 7 where themovie parts are stored in a database 31 and transmitted to a user’s unit 9 part by pan, bymeans of a transceiver 33.

As seen in Fig. 2, a user’s transceiver 34 receives movie parts and transmitsrequests for additional information. A user’s database 35 is progressively updated withrequested images or, alternatively, may be progressively updated by the server 7. User’sdatabase 35 functions asynchronously, supplying the frames to the user via a decoder 36by request independent of data transmission. Upon receiving the frames, the decoderinitially decompresses the frames as indicated at 37 (if compression took place) and thendecodes and recombines them by means of a partial frame integrator 38. Following this,the partial frames are stored in the user’s database where the frames may be stored in acompressed format, effected by a compressor 39. A user’s workstation 40 enables theuser to view and interact with the VR movie. The user utilizes the workstation forsending requests for images to the decoder which retrieves (and decompresses, ifnecessary), the images from the user’s database and sends requests for particular imageswhich may not yet have been transmitted to the server database. Furthermore, the user’sworkstation actuates any script produced in the production workstation 3. Hence theuser’s workstation also inciudes the standard devices included in the workstation 3 anddesignated by the number 23 (Fig. 1).

As a preface to the explanation of the remaining figures, it is important tounderstand that the progressive scalable database which is a subject of the currentinvention preferably is stored in three databases within the server/client system.

Reference is now made to Fig. 3 A which shows a preferred database structure inaccordance with a preferred embodiment of the present invention. It is a particular 40

<img img-format="tif" img-content="drawing" file="IL125643AD000232.tif" id="idf0032" />

feature of the present invention that three databases are employed, a server database 41,which is arranged in a serial form, containing multiple data blocks, each includingmultiple partial frame data, a client database 42 which is arranged in a two dimensionalstructure, conceptually illustrated in Fig. 3B and an interactive database 43 whichcontains a single data block including multiple frames, which is dynamically updated fromthe client database 42. In an alternative embodiment of the invention, wherein extremelyhigh processing speeds are available at the client, the client database could be eliminated.

It is a particular feature of the present invention that interactive data streaming isprovided. The use of three databases as described above enables interactive datastreaming to be achieved in an efficient and cost effective manner. The use of databaseshaving a two-dimensional structure greatly simplifies the data processing.

Server database 41, which is archived on a server constitutes a first database of theprogressive scalable database. The server database 41 includes a plurality of data blocksin encoded form. As seen particularly in Fig. 3B, the progressive scalable database istwo-dimensional in nature. It has a progressive dimension indexed by block number, andan interactive dimension indexed by frame number but it is serialized for streaming andcan only be accessed sequentially. Server database 41 is streamed from server to clientvia the transmission and buffering protocol of the Internet browser.

Client database 42, the second database, is built up on the client side as theinformation streams in. to mirror the server database 41. Client database 42 is truly two-dimensional, with random access capability within the data blocks. The data blockswithin it are also in encoded form.

Interactive database 43, the third database, is created by decoding the data fromthe client database 42. This interactive database 43 is one-dimensional, and containsonly one sequence of frames, but it is dynamically updated. As additional block data isintegrated, these frames are updated, with the previous versions over-written.

When a frame has been updated, the encoded frame used to update it is deletedfrom client database 42. Thus while interactive database 43 is being created andupdated, client database 42 is being deleted. Since the updating of the frames isasynchronous, however, client database 42 typically contains frames from many differentblocks simultaneously at any point in time. In essence, then, the progressive dimension 41

<img img-format="tif" img-content="drawing" file="IL125643AD000233.tif" id="idf0033" />

of the database is being realized through a time dimension in interactive database 43.

Interactive database 43 is controlled by the user interface through keyboard pressesand mouse clicks. The creation and update of interactive database 43 from ciientdatabase 42 is done in background time slices, while the client CPU is idle. Interactivedatabase 43 may store the frames in either raw bitmap form or in an intermediatecompressed form, as long as the intermediate compression is such that the frames can bedecompressed in real time for display. An advantage of using an intermediatecompression is to confine interactive database 43 to internal RAM, which has fast accesstime, rather than swap to hard disk memory, which has slow access time. The swappingin itself is a drain on processing speed.

When the user requests a frame to be displayed, interactive database 43 displaysthat frame immediately, if it is available. In case the frame is not available, interactivedatabase 43 passes a message back to client database 42 requesting that frame. Clientdatabase 42 accesses the specific frame requested from its first encoded data block, if itis available, and sends it to the decoder for decompression and integration, andsubsequent incorporation into interactive database 43. Once a frame is incorporated,interactive database 43 displays the frame at once. If client database 42 has not yetreceived the requested frame from the server stream, then it must wait until the encodedframe arrives, since the streaming is sequential. If the streaming were instead randomaccess, client database 42 would be able to directly request the specific frame it needsfrom server database 41.

In summary, the server database is two-dimensional but serialized for sequentialstreaming; the ciient database is two-dimensionai with random access within blocks; andthe interactive database is one-dimensional but dynamically updated. In the interactivedatabase, the progressive database dimension is actually being represented as time ratherthan space. This “three database strategy,” using three different databases: (/) two-dimensional serialized, (//) two-dimensional, (///) one space and one time dimension, is akey to the present invention, and to the discussion of the figures in detail which follow.

For each of these three databases, the progressive dimension manifests itself in adifferent way. Within the server database, progressiveness means quality. The encoderbuilds the blocks of the database based on achieving the best quaiity at given bit rates. 42

<img img-format="tif" img-content="drawing" file="IL125643AD000234.tif" id="idf0034" />

Within the client database, progressiveness means cumulative integration.Progressiveness within the ciient database is a computational property. The accumulatoron the client computer integrates frames from successive blocks with those fromprevious blocks. Finally, within the interactive database, progressiveness means time.As time progresses, the frames are dynamically updated as more blocks have beenaccumulated. The transmission from the server database to the ciient database isstreamed serially, and this is where the progressive dimension is effectively convertedfrom “space” to “time.”

The progressiveness manifests itself in bandwidth during the streaming. Thetransmission from the client database to the interactive database is asynchronous. Theciient database is being created in the background while the interactive database is beingplayed, and the former acts as a buffer for the latter. Moreover, the client can interactwith the media almost immediately after the streaming begins, and does not have to waitfor the client database to be constructed entirely.

The interactive dimension of the database corresponds to whatever functionalitythe user interface allows. For example, it can manifest itself as frame advance for videosand object movies, navigating for panoramas, and gazing for large still images.

Reference is now made to Fig. 4 which illustrates one application of the threedatabase structure described hereinabove in Figs. 3 A and 3B. For simplicity, referringadditionally to Fig. 3B, each image in Fig. 4 is built up of corresponding partial framesin successive data blocks which are cumulatively received. Thus, for simplicity, one mayconsider the five images in a first horizontal row, to correspond to five interactivelyviewable frames in a first block of data, each successive frame typicailv illustrating asuccessive position of an imaged model.

Considering each successive horizontal row in Fig. 4, it can be seen that thequality of the images improves successively from the top row to the bottom row. Thiscorresponds to the quality improvement sensed by a viewer as successive blocks of dataare incorporated in the information made available to the viewer.

It is appreciated that in accordance with a preferred embodiment of the presentinvention, a limited bandwidth user first receives the first row of images and isimmediately able to interact therewith. Over time, depending on the bandwidth available 43

<img img-format="tif" img-content="drawing" file="IL125643AD000235.tif" id="idf0035" />

to that user, successive data blocks are received, each cumulatively enhancing the quality. It is a particular feature of the invention that during receipt of successive blocks of data, the user is able to fully interact with the images.

Reference is now made to Fig. 5 showing a production tool 71 which accepts as aninput a sequence of original digital frame units 72, integrated into a digital multimedia file73. The production tool 71 includes an encoder unit 74 which operates by partitioningand compressing the digital multimedia file 73 into a scalable progressive database 75comprised of data blocks 76. Successive blocks combine together to form higherbandwidth versions a to n of the media. Database 75 is stored on server 77. Theproduction tool 71 enables the producer to control the bandwidth or quality granularitythrough control parameters 78. These parameters are used to calculate the data blocksizes and compression settings within encoder unit 74.

Reference is now made to Fig. 6 showing the structure of data block 76 in scalableprogressive database 75. Where a random access server is available, selective encodedframes 72 from block 76 are accessed at 79 on the server 77 database, based oninteractive requests coming from the client. The encoded frames are transmitted fromserver 77 to a client computer 80 and integrated within client database 81, to mirrorserver database 75. It is appreciated that both sequential and random access servers maybe advantageously employed in the present invention, although random access serversare preferred.

Reference is now made to Fig. 7 showing the decoder on a client computer 80.The client computer 80 receives from server 77 (Fig. 5) into a buffer 82 a series of datablocks 76 from scalable database 75. As the blocks are received, a client database, whichmirrors the server database, is built up. A decoder unit 83 decompresses the blocks andan accumulator unit 84 integrates them to form a suitable low quality version 85 of themultimedia file 73 (Fig. 5), which is stored in a buffer 86, thus building up an interactivedatabase.

The operations of the decoder 83 and accumulator 84 are governed by a CPU 87.They may operate in either order; i.e., the decoding may be carried out before theaccumulation, or the accumulation may be carried out before the decoding. Themultimedia file 73 is played on a player unit 88 in response to interactive user commands. 44

<img img-format="tif" img-content="drawing" file="IL125643AD000236.tif" id="idf0036" />

As the user interactively requests specific frames to be played, the buffer 86 supplies thehighest quality version which it possesses. If the desired frame is not available, the buffer86 sends back a request to buffer 82 to decode and accumulate that frame. If the frameis also not available in buffer 82, then that buffer 82 sends back a request to the serverdatabase 75 to transmit the frame. As playback continues and the bandwidth frees,additional data blocks 76 are received and integrated with the previously received blocksinto higher quality versions 89 of the multimedia file.

The description of Figs. 1 - 7 has been directed towards the overall system andmethod provided by the present invention. The description which follows is directlyprincipally to particular applications of the system and method described hereinabove.

Reference is now made to Fig. 8 showing a progressive database 75 for a digitalvideo file which corresponds to digital multimedia file 73 (Fig. 5). The progressivedatabase 75 comprises data blocks, where the first ones of data blocks 76 are used tocreate a preview 90 of the video, and the second ones of data blocks 76 are accumulatedwith the first blocks to create a full view 91 of the video. The views are stored in theinteractive database buffer 86 and played in player unit 88, in response to interactive usercommands.

Reference is now made to Fig. 9 showing a system for incorporating a progressivescalable database into a time-based video frame sequence with a macro and micro timescale, such as the one used in Apple’s QUICKTIME* movies in accordance with apreferred embodiment of the present invention. Individual frames 72 are arrangedaccording to a macro time scale, denoted by major axis markings 92 in Fig. 9. Eachframe is displayed at the respective macro times indicated by markings 92.

Between successive frames 72, small fluctuations can be introduced. For example,the major time scale can be displaying a bird flying, and the minor time scale can be usedto add fluttering to the bird’s wings. The fluctuations typically involve only a smallportion of the image area, and are displayed in rapid succession, according to minor axismarkings 93 in Fig. 9. Such a time based sequence allows the decoder, which does theintensive processing to supply the frames 72, to run at a slow rate; e.g. 3 fps, whereasthe viewer, doing the less intensive processing, can be playing at a fast rate; e.g. 30 fps.The fluctuations must be simple enough, though, that they can be rendered at the full 30 45 fps rate.

The present invention includes a novel use of such a two-scale time based system,to enable progressive streaming. In order to utilize the progressive database of thepresent invention in viewing such time-based video sequences, the minor time scale 93 isused to display progressive versions of a frame, rather than to display fluctuations, asoriginally conceived in the prior art. At each time corresponding to a minor axismarking, the player displays the latest version of the frame which is available. Forexample, in Fig. 9 the low quality version 94 of frame #4, corresponding to the firstblock 76, is displayed over a duration of three minor axis marks, by which time thesecond block 76 has been accumulated to form the medium quality version 95. Thismedium quality version is then displayed over a duration of two minor axis marks, bywhich time the third block 76 has been accumulated to form the high quality version 96of the media. This high quality version is then displayed for a duration of three furtherminor axis marks, following which the frame advances to frame #5.

The cycle then repeats for progressive display of frame #5. If additional blocksarrive and are accumulated for frame #4, they are displayed when the video sequence isreplayed. Thus it is seen that the progressive dimension of the database can beincorporated within the interactive dimension, through the use of a minor time scale,which is situated within the major time scale used for advancing the frames. The majortime scale is the interactive axis, and the minor time scale becomes the progressive axis.The overall accomplishment is to enable viewing of the video before the full mediastream has been downloaded. Initially, the low quality frames are displayed, and whileadditional blocks are downloaded and accumulated in background, the quality of theframes steadily improves.

In accordance with a preferred embodiment of the present invention, for the user tobe able to view the video immediately, without waiting for the entire file to download, aproduction tool must store the encoded video in the order of successive blocks. Oncethe first block is downloaded, the video can already be viewed. The order of theencoded data items must therefore be:

Frame 1/Block 1, Frame 2/Block 1, ..., Frame m /Block 1,.. .,

Frame 1/Block n, Frame 2/Block n, ..., Frame m /Block n 46

<img img-format="tif" img-content="drawing" file="IL125643AD000237.tif" id="idf0037" />

Each row in this order comprises one entire block. In order to integrate this file formatwithin the two-scale time-based system, each partial frame must be handled as if it werean entire frame. That is, the production tool must treat the movie as if there were a totalof m n distinct frames being encoded. The player in turn, however, must know thatalthough it is receiving what appears to be m · n encoded frames, there are really only atotal of m frames. It must decode and accumulate every successive sequence of m dataitems (i.e., each row of the above sequence) with the previous ones, to update theframes.

On the other hand, the natural order in which the production tool produces theencoded data items is:

Frame 1/Block 1, Frame 1 ZB lock 2, ..., Frame 1/Blockn, ...,

Frame m /Block 1, Frame m /Block 2, ..., Frame m /Block n

This is because each frame is sent only once to the codec for encoding, and returned as aseries of encoded partial frames. Thus it is necessary to post-process the encoded datafile, to rearrange the data items from this latter frame dominated order to the formerblock dominated order. This rearrangement process is referred to as “flattening” in theart, and is illustrated in Fig. 10.

As seen in Fig. 10, the frames 72 are supplied in sequence to the production tool,which produces a series of partial blocks 76 for each frame. The partial blocks arereordered, as indicated by the mapping in Fig. 10, into a single file stream 97. Asindicated, the first partial blocks of each frame form the first m data units in the file 97,the second set of partial blocks of each frame form the next m data units, etc.

Reference is now made to Fig. 11 which shows a proxy system 98 for caching in acentral hub 99 multimedia data which streams from servers 77 to clients 80. The servers77 store their multimedia data in the progressive scalable representation described above in the server database 75, with each media encoded into data blocks 76 Βι, B,.....B„.

Multiple servers 77 are connected through the central hub 99 to clients 80 via datacommunication channels. These channels are of various bandwidths. Whenever a ciient80 issues a request for data from a specific server, a proxy computational unit 100 firstdetermines, based on the server bandwidth, which data blocks are to be transmitted tothe ciient. If those data blocks are not already cached in the hub, then the proxy 98 47

<img img-format="tif" img-content="drawing" file="IL125643AD000238.tif" id="idf0038" />

retrieves the required blocks 76 from the server aiong low bandwidth communication channels 101, at the appropriate bandwidth, and delivers them to the client 80 along high bandwidth communication channels 102. The blocks 76 are also cached in the hub 99.

There is provided an inventory flag database 103 on the hub which keeps a recordof which data blocks are available. If some of the required data blocks 76 are alreadycached, then the proxy computational unit 100 computes which data blocks must bedelivered from the server 77 in order to transmit to the client the highest quality versionof the media possible, within the bandwidth constraint. The proxy 98 then retrieves therequired blocks 76 from the server 77 aiong low bandwidth communication channels101, stores them in its cache and delivers them to the client 80 along high bandwidthcommunication channels 102. A decoder unit 83 on the client computer decodes thedata blocks received, and an accumulator unit 84 integrates them. The proxy 98 mayalso have its own decoder unit 83 and accumulator unit 84, which converts the data fromits original compressed form on the server database 77 to an intermediate compressedform on the hub database 104, one which is faster to decompress than that of the clientdatabase. The proxy accumulation unit 84 may perform the necessary data blockaccumulation to store on the hub all possible versions of the multimedia in itsintermediate compressed form, in which case the client accumulator 84 unit isunnecessary.

An update communication line 105 links servers 77 to the proxy 98, through whichservers 77 can notify proxy 98 if any of the multimedia files have been updated. If proxy98 receives such notification, then it clears its cache of any data blocks associated withthose updated files, and resets its inventory flags 103, so that upon future client requestsit will know that it has to retrieve the updated files from the server again.

There are several ways to generate the data biocks Bi, B?, ..., B„ for theprogressive scalable database, so as to satisfy the user-selected constraints that (/) for each 1 &lt; k &lt; n, the first consecutive compressed data blocks Bt, B;.....Bk when integrated together produce a version of the media at a quality level commensuratewith bandwidth fk; (//) the sizes of the compressed data blocks are such that the first consecutivecompressed data blocks Bi, B:, ..., Bk when transmitted at bandwidth fk suffice to enable 48

<img img-format="tif" img-content="drawing" file="IL125643AD000239.tif" id="idf0039" />

on-line playback of the media version.

Reference is now made to Fig. 12 which shows a system for generating aprogressive scalable database from digital media data by cascading compressors intandem. The user selects bit-rate and quality control parameters 106 for the encoding.The original multimedia data file 73 is input to a compressor 107 along with the user-selected control parameters 106, resulting in compressed data 108 adapted to a user-selected bandwidth. The compressed data 108 is transmitted to the scalable database 75as the first data block 76. It is also transmitted to decompressor 109, which reconstructsthe media as it would be generated on the client side.

The reconstructed data 110 is subtracted from the original data 73 to arrive at aresidual 111. The residual 111 is fed back to the compressor 107 in a feedback loop112, and compressed by compressor 107 with bit-rate control so that the compresseddata 108 is adapted to the difference between the first and second user-selectedbandwidths. The compressed data is transmitted to the progressive scalable database 75as the second data block 76, and the loop continues repeatedly until the user-selectedfinal quality is achieved.

It is not necessary for the compressor 107 to use the same compression methodeach time it operates. Rather, it can use a block identifier 113 as a parameter forswitching between methods. For example, with a video encoder, the first block could beencoded using a low quality version of H.263 and successive blocks could be encodedusing spatiai vector quantization and temporal wavelets.

One possible approach to compression is the use of fractal technology, such as thatdescribed and claimed in applicant’s U.S. Patent No. 5,497,435, the disclosure of whichis hereby incorporated by reference.

Another approach to generating a scalable database is through the use ofprogressive JPEG. The progressive JPEG standard allows the encoder to segment thecompression into spectral selection and successive approximation scans. In spectralselection the DCT coefficients are grouped into spectral bands, and in successiveapproximation the bits used to represent them are divided into lower and higher precisioninformation. Progressive JPEG is described by Pennebaker, W. B. and Mitchell, J. L. inJPEG: Still Image Data Compression, Van-Nostrand Reinhold, New York, 1993, the 49

<img img-format="tif" img-content="drawing" file="IL125643AD000240.tif" id="idf0040" />

disclosure of which is hereby incorporated by reference.

Reference is now made to Fig. 13 which shows a decoder for the scalable database75 on the client side, corresponding to the encoder from Fig. 12. Blocks 76 aresuccessively transmitted from the server to the client and are decompressed in decoder83. The decoded data is integrated in an accumulator 84, which converts it into a formcompatible with the player 88, and stores it in the interactive buffer 86. While the playeris showing the media, additional blocks 76 are received in the background, decoded andaccumulated, so that the media quality is upgraded when it is replayed. The player 88requests frames from buffer 86, and if they are not available then buffer 86 requests themfrom database 75. A block identifier 113 provides an input to the decoder as each blockis decoded, so that the decoder can apply the appropriate decompression method for thatdata block, corresponding to the compression method which was performed incompressor 107.

Reference is now made to Fig. 14 which shows a progressive database for a largestill image. The first encoded frame unit of a data block consists of the full image sub-sampled 4:1 in each dimension. The second set of frames consist of four encoded frameunits corresponding to each of the quadrants of the full image, sub-sampled at 2:1.Although this second set of frames appears to be four times the size of the first frame, itcan be stored using only three times as much data since the decoder can also accumulatedata from the previously displayed frame. The third set of frames includes sixteenencoded frame units, each corresponding to a quadrant of a quadrant of the full image,but at the original scale. Again, this third set of frames stores three times as much dataas the second set. These three sets of frames comprise the entire encoded data block,and their sum total is, of course, the same amount of data as the full image at the originalscale. (The effect of the compression is being ignored here.) The frames are all arrangedsequentially in the encoded data block 76. The mapping from multi-resolution imagetiles to sequential frames 72 is shown in Fig. 14.

When the frame #1 is downloaded, decoded and displayed, the viewer sees a lowresolution version of the full image. In the example shown in Fig. 14, the viewer clickson a hot spot in the northwest quadrant and link 114 then transfers over to the northwestframe in the second set of frames, which corresponds to frame #2 in Fig. 14. Displaying 50

<img img-format="tif" img-content="drawing" file="IL125643AD000241.tif" id="idf0041" />

this new frame gives the appearance of having zoomed in on the quadrant. The viewer next clicks on a hot spot in the southeast quadrant of the frame being displayed from the second set, and link 114 then transfers over to the indicated frame in the third set of frames, which corresponds to frame #11 in the Fig. 14, giving the effect of yet another zoom in.

While the viewer is looking at the first frame, the data from the second set offrames is being downloaded in the background. Once received, this data is decoded andstored in the client interactive database. When the hot spot in the northwest quadrant isclicked, the client CPU looks for the desired frame #2 in its interactive database. If theframe is already present, it is delivered to the viewer for immediate display; otherwise theinteractive buffer sends the request back to the progressive database. The progressivedatabase can access and send the specific encoded frame required from the second set offrames, without sending all of the frames. Finally, as successive blocks are integratedinto the interactive database, the quality of the individual frames is enhanced, and thezoomed in tile looks progressively better and better, having cumulatively enhancedquality.

It is evident to those skilled in the art that the above discussion applies toanimations and panoramas of large images which contain areas of interest such as sprites.The frames comprising the interactivity dimension of the database would correspond tomulti-resolution tiles from each of the individual images in the animation or panorama.

Fig. 15 illustrates a system for transmitting VRML images over a server/clientnetwork. A VRML database 121 is stored on a server. A client 80 interactively controlsthe VRML viewing parameters 122 through use of a mouse and keyboard 23. Theviewing parameters 122 are used in conjunction with the VRML database 121 to rendera raster bitmap image 123 of the VRML object on the server computer. If the bitmapimage corresponding to the viewing parameters was already rendered previously, thenthe frame data for the bitmap in the client database 42 is used for display by the player88. The raster bitmap is encoded into partial frames by encoder 74. and the partialframes are inserted into a server two-dimensional database 41. The server database iscontinually streamed to the client, building up the client database 42. The client database42 is used to provide the frames for display. 51

<img img-format="tif" img-content="drawing" file="IL125643AD000242.tif" id="idf0042" />

Fig. 16 depicts a flowchart for the VRML application shown in Fig. 15. At step 131,the user interacts with the mouse and keyboard, and the client computer updates theviewing parameters. At step 132 the client computer checks whether or not thoseviewing parameters have already been processed. Although the viewing parameters canvary continuously, a preferred embodiment of the present invention discretizes them to afinite number of settings; for example, 10° resolution for angles. This makes it likely thatthe user will navigate back to the same settings used earlier.

If the viewing parameters are new, then they are sent to the server computer, whichrenders the VRML database into a raster bitmap corresponding to the specific viewingparameters selected, at step 133. At step 134 the bitmap is encoded into partial frames,and incorporated into the server database. Step 135 is continually operative to transmitadditional encoded data from the server to the client. As data is received on the client,the client database is built up at step 136. At step 137 the client database generates thelatest version of the bitmap on demand, and displays it. This step is also carried outwhenever step 132 results in confirmation that the viewing parameters have already beenprocessed.

It is evident to those skilled in the art that the above discussion applies toCAD/CAM models for three-dimensional objects, as well as VRML models.Specifically, Fig. 17 illustrates a typical two-dimensional array of CAD/CAM images,indexed vertically according to progressive coordinate and horizontally according tointeractive coordinate. It is appreciated that the images in a given horizontal row maybe viewed interactively. Each successive horizontal row of images is built up over timeat a rate determined by bandwidth availability and has increased quality inasmuch as it isbased on an increasing number of data blocks.

It will be appreciated by persons skilled in the art that the present invention is notlimited by what has been particularly shown and described hereinabove but extends alsoto embodiments which would naturally occur to persons reading the above descriptionand to combinations and subcombinations of embodiments described hereinabove. 52