Exhibit 2012
`Bradium Technologies LLC - patent owner
`Microsoft Corporation - petitioner
`IPR2016-01897
`1
`
`
`Bradium Technologies LLC - patent owner
`Microsoft Corporation - petitioner
`IPR2016-01897
`1
`
`
`
`MULTIPLE PARALLEL LAYERS OF TARGET IMAGE
`
`DATA STREAMED OVER LIMITED AND
`
`NARROWBAND COMMUNICATIONS CHANNELS
`
`Inventors:
`
`Isaac Levanon
`
`Yoni Lavi
`
`Background of the Invention
`
`The present invention is generally related to the delivery of high—resolution
`
`highly featured graphic images over limited and narrowband communications
`
`channels.
`
`Summary of the Invention
`
`The objective is to display a two-dimensional pixel map, al 6-Bit RGB color
`
`image in the preferred embodiments, of very large dimensions and permitting the
`
`viewing of the image from a dynamic three-dimensional viewpoint. Multiple such
`
`images are remotely hosted for on-demand selection and transfer to a client
`
`system for viewing.
`
`Images, as stored by the server, may individually range from gigabytes to
`
`multiple terabyte in total size. A correspondingly large server storage and
`
`Attorney Docket No.: FLVT3003
`gbr/tlvt/3003.000.provisional.wpd
`
`‘I2/26/2000
`
`\OCI)‘\lO\U1->(.aOf\)—*
`
`
`
`2
`
`
`
`
`
`-2-
`
`processing system is contemplated. Conversely, client systems are contemplated
`
`to be conventional personal computer systems and, in particular, mobile, cellular,
`
`embedded, and handheld computer systems, such as personal digital assistants
`
`(PDAs) and internet-capable digital phones, with relatively limited to highly
`
`constrained network communications capabilities. For most wireless applications,
`
`conventional narrowband communications links have a bandwidth of less than
`
`approximately three kilobytes of data per second. Consequently, transmittal of
`
`entire images to a client system in reasonable time is infeasible as a practical
`
`matter.
`
`Overview:
`
`Description of the Invention
`
`For purposes of the present invention, each image (Figure l) is at least
`
`logically defined in terms of multiple grids of image parcels with various levels of
`
`resolutions (Figure 2) that are created through composition of information from
`
`all level of resolutions, and stored by the server to provide an image for transfer
`
`to a client system (Figure 3). Composed and separate static and dynamically
`
`created layers are transferred to client system in parcels in a program selectable
`
`order to optimize for fast quality build-up of the image presented to a user of the
`
`client system, particularly when the parcels are streamed over a narrowbandl
`
`communication link.
`
`The multiple layers of an image allow the selectivity to incorporate
`
`topographical, geographical, orientational, and other terrain and mapping
`
`related information into the image delivered. Other layers, such as geographic
`
`grids, graphical text overlays, and hyperlink selection areas, separately provided
`
`Attorney Docket No.: FLVT3003
`gbr/flvt/3003.000.provisionol.wpd
`
`l 2/2 6/2000
`
`3
`
`
`
`:I
`
`O\OOO\lO\U'1-boolxj
`
`-3-
`
`or composed, aid in the useful presentation and navigation of the image as
`
`presented by the client system and viewed by the user.
`
`Compositing of layers on the server enables the data transfer burden to be
`
`reduced, particularly in analysis of the requirements and capabilities of the client
`
`system and the connecting communications link. Separate transfer of layers to the
`
`client system allows the client system selectivity in managing and presentation of
`
`the data to the user.
`
`The system and methods of the present invention are designed to, on
`
`demand, select, process and immediately transfer data parcels to the client
`
`system, which immediately processes and displays a low-detail representation of
`
`the image requested by the client system. The system and methods immediately
`
`continue to select, process and sequentially transfer data parcels that, in turn, are
`
`processed and displayed by the client system to augment the presented image
`
`and thereby provide a continuously improving image to the user.
`
`Selection of the sequentially transferred data is, in part, dependent on the
`
`progressive translation of the three-dimensional viewpoint as dynamically
`
`modified on the client system during the transfer process. This achieves the
`
`above-stated objective while concurrently achieving a good rendering quality for
`
`continuous fly-over of the image as fast as possible, yet continuously building the
`
`image quality to the highest resolution of the image as stored by the server.
`
`To optimize image quality build-up over
`
`limited and narrowband
`
`communication links, the target image, as requested by the client system,
`
`is
`
`represented by multiple grids of 64x64 image pixels (Figure 4) with each grid
`
`having some corresponding level of detail. That is, each grid is treated as a
`
`sparse data array that can be progressively revised to increase the resolution of
`
`Attorney Docket No.: FLVT3003
`gbr/flvt/3003.000.provisional.wpd
`
`l2/26/2000
`
`
`
`4
`
`
`
`-4-
`
`C)©CX3\IO\U1-F-C.0l\)-—*
`
`the grid and thereby the level of detail presented by the grid. The reason for
`
`choosing the 64x64 pixel dimension is that, using current image compression
`
`algorithms, a 16-bit 64x64 pixel array image can be presented as a 2KByte data
`
`parcel.
`
`In turn, this 2KByte parcel is the optimal size, subject to conventional
`
`protocol and overhead requirements, to be transmitted through a 3KByte per
`
`second narrowband transmission channel. Using a smaller image array, such as
`
`32x32, would create a O.5KByte parcel, hence causing inefficiencies due to packet
`
`transmission overhead, given the nature of current wireless communications
`
`protocols.
`
`Image array dimensions are preferably powers of two so that they can be
`
`used in texture mapping efficiently. Each parcel, as received by the client system,
`
`is preferably immediately processed and incorporated into the presented image.
`
`To do so efficiently, according to the present invention, each data parcel
`
`is
`
`independently processable by the client system, which is enabled by the selection
`
`and server-side processing used to prepare a parcel for tra nsmission. In addition,
`
`each data parcel is sized appropriate to fit within the level-1 cache, or equivalent,
`
`of the client system processor, thereby enable the data processing intensive
`
`operations needed to process the data parcel to be performed without extended
`
`memory access delays.
`
`In the preferred embodiment of the present invention,
`
`data parcels are also processed for texture mapping and other image features,
`
`such as topographical detailing.
`
`Currently, with regard to conventional client systems, a larger image array,
`
`such as 128x128, is too large to be fully placed within the level-1 cache of many
`
`of the smaller conventional current processors, such as used by personal digital
`
`
`
`Attorney Docket No.: FLVT3003
`gbr/flvt/3003.000.provisional.wpd
`
`‘I2/26/2000
`
`5
`
`
`
`(ID\lO\U'I-J>-0.)l\7—-I
`
`-5-
`
`assistants (PDAs) and cellular phones.
`
`Since access to cache memory is
`
`substantially faster than to RAM this will likely result in lower frame rate.
`
`Different and larger data parcel sizes may be optimal as transmission
`
`protocols and micro-architectures of the client computers change. For purposes
`
`above, the data content was a pixel array representing image data. Where the
`
`data parcel content is vector, text or other data that may subject to different client
`
`system design factors, other parcel sizes may be used.
`
`In the process implemented by the present invention, data parcels maybe
`
`selected for sequential transmission based on a prioritization of the importance
`
`of the data contained. The criteria of importance maybe defined as suitable for
`
`particular applications and may directly relate to the presentation of image
`
`quality, provision of a textual overlay of a low-quality image to quickly provide a
`
`navigational orientation, or the addition of topography information at a rate or
`
`timing different from the rate of image quality improvement. Thus, image data
`
`layers reflecting navigational cues,
`
`text overlays, and topography can be
`
`composed into data packets for transmission subject to prioritizations set by the
`
`server alone, based on the nature and type of the client system, and interactively
`
`influenced by the actions and commands provided by the user of the client system
`
`(Figure 5).
`
`Progressive transmission of image parcels is performed in an iterative
`
`process involving selection of an image data grid within the target image of the
`
`client system, which is a portion of a potentially multi-layered source image stored
`
`by the server. The selection parameters are preferably dependent on the client
`
`navigation viewpoint, effective velocity, and height, and the effective level of detail
`
`currently presented in each grid. Once a grid is selected, the server selects the
`
`Attorney Docket No.: FLVT3003
`gbr/flvt/3003.000.provisional.wpd
`
`12/26/2000
`
`
`
`6
`
`
`
`
`
`-5-
`
`OO\lO\U1-h(.OI\)—-I
`
`source data to be logically composed into the selected grid to complement the
`
`effective resolution of that grid, processing the grid data to produce the optimally
`
`sized size grid data parcels, and sequentially transmitting the parcels to the client
`
`system. Preferably, the detail of a grid array is sequentially enhanced by division
`
`of the grid into sub-grids related by a power of two (Figure 6). Thus, a given grid
`
`is preferably updated using four data parcels having twice the data resolution of
`
`the existing grid. Whatever number of parcels are used, each data parcel is
`
`rendered by the client system into the target image. Additional client system
`image data processing to provide texturing and three-dimensional representation
`
`of the data may be performed as part of the parcel rendering and integration into
`
`the target image.
`
`Image Parcel Download Seguence:
`
`The server of the present invention supports the download of parcel data
`
`to a client system by providing data parcels in response to network requests
`
`originated by client systems. Each requested data parcel is identified within a grid
`
`coordinate system relative to an image stored by the server.
`
`A client system implementing the process of the present invention is
`
`responsible for identifying and requesting parcel data, then rendering the parcel
`
`data into the target image at the correct location. The client system is also
`
`responsible for managing navigational and other interaction with the user.
`
`In
`
`identifying the parcel data to be requested, the client system operates to select
`
`grids within the coordinate system, corresponding to portions of the target image,
`
`for which to request a corresponding data parcel. The requests are issued over
`
`the network to the server and rendering performed asynchronously as data
`
`Attorney Docket No.: FLVT3003
`gbr/flvt/3003.000.provisional.wpd
`
`‘I2/26/2000
`
`7
`
`
`
`-'©\0CD\lO\U‘l-B0Ol\J—'
`
`:I—J
`
`_.I NJ
`
`._a 00
`
`_a J}-
`
`_| U‘!
`
`-—-I O‘
`
`._I \l
`
`._a 00
`
`_a ‘O
`
`l\) C
`
`l\3 .—I
`
`IO N)
`
`Ix) CO
`
`I\) A
`
`sIx) U1
`
`-7-
`
`parcels are received. The order of data parcel requests is defined as a sequence
`
`that will provide for the optimal build-up of the target image as presented to the
`
`user. The rate of optimal build up of the target image is dependent on the nature
`
`of the target image requested, such as the supported parcel size and depth of the
`
`target image that can be rendered by the client system.
`
`The client identifies and requests the download of data parcels in the
`
`process as follows. Denote the target image as lo and its size in pixels as (X, Y).
`
`Let N be the smallest power of 2 that is equal or greater than max {X,Y}.
`
`Construct the grid of 64x64 pixel grid-images loin that together compose the
`
`target image I0. The rectangle [64i,64i + 64] x [64j,64 i + 64] of I0 is mapped
`
`to IOM.
`
`In order to view a large portion of the image, the target image, without
`
`downloading the substantial bulk of the target image, mip-maps of lo are created,
`
`representing a collection of images to be used as surface textures when rendering
`
`a two-dimensional representation of a three-dimensional scene, and which are
`
`defined recursively as:
`
`lk+‘| (i,[) = avg(|k (2i,2i), lk(2i + l,2i), lk(2i,2i + l), lk(2i + 1,2] + 1))
`
`Such mip-maps are created up to |M,M = log2 (N) - 6. At this point, IM is
`
`a 64x64 image containing the entire area of the original image, hence no further
`
`mip-mapping is required.
`
`The methods of the present invention then proceed by constructing the
`
`respective grids or cells (lm) for each mip-map. Each nonempty image cell Im
`
`now may be downloaded. Larger values of k cover more area within the original
`
`Attorney Docket No.: FLVT3003
`gbr/flvt/3003.0OO.provisIonal.wpd
`
`T2/26/2000
`
`
`
`8
`
`
`
`-3-
`
`image but provide lower detail on that area. The task at hand is now to
`
`determine, given the viewing trustum and the list of previously downloaded image
`
`cells lklm, downloading which grids will improve the quality of the display as fast
`
`as possible, considering the download rate as fixed. The scheme used to
`
`implemented the downloading sequence of these cells is by constructing a tree,
`
`starting from lN_6Io,O and expanding a quadtree towards the lower mip—map levels.
`
`(Quadtrees are data structures in which each node can have up to tour child
`
`nodes. As each 64x64 pixel image in the grid lk has exactly tour matching 64x64
`
`pixel images on the grid 1,0, covering the same area, the data structure is built
`
`accordingly.)
`
`For every frame that is rendered , begin with the cell that covers the area
`
`of the entire original image, lN_6’o’0. For each cell under consideration, compute
`
`the principle mip—map level that should be used to draw it.
`
`If it is lower than the
`
`mip—map level of the cell, subdivide the cell
`
`to tour smaller cells and use
`
`recursion.
`
`If this operation attempts to draw over areas that do not yet have
`
`image cells at a low enough mip—map level to use with them, the recursion stops.
`
`If the principle mip—map level is equal or higher than the level of the cell,
`
`then the cell is rendered using the cell of the principle mip—map level, which is the
`
`parent of that cell in the Quad-tree, at the appropriate level. Then download the
`
`cells in which the difference between the principle mip—map level to the mip—map
`
`level of the image cell actually used is the highest. Downloading is asynchronous;
`
`the renderer maintains a priority queue of download requests, and separate
`
`threads are downloading images. Whenever a download is complete, another
`
`download is initiated immediately, based on the currently highest-priority request.
`
`Attorney Docket No.: FLVT3003
`gbr/llvt/3003.000.provislanal .wpd
`
`1 2/2 6/2000
`
`
`
`9
`
`
`
`O\OOO\lO\U‘I-hCa)f\>——'
`
`__,l
`
`——I
`
`._|
`
`...a K)
`
`....I
`
`(A)
`
`._I -IA
`
`——I U‘!
`
`.._I O‘
`
`—| \l
`
`_.I 00
`
`_| \O
`
`I\) 0
`
`N3 _..t
`
`ix) ND
`
`ix) O0
`
`Ix) -k
`
`I0 ()1
`
`
`
`‘:5
`
`-9-
`
`The principle mip-map level of an image cell is determined by the screen
`
`resolution, FOV (field of view) angle,the angle formed between the image's plane
`
`normal and the line connecting between the camera and the position within the
`
`cell that is closest to the camera, and a few other factors. The equation, which
`
`uses the above information, approximates the general mip-mapping level
`
`equafion:
`
`l = max[O, log, (T/5))
`
`in which 5 is the surface of the cell as displayed on the screen during rendering
`
`(in pixels), and T is the surface of the cell within the texture being mapped (in
`
`pixels).
`
`When rendering a cell of the grid lk,
`
`T = N22“
`
`and
`
`S = xycos(a)ctg2(O.5FOV)t2 T / 22
`
`where x is the disp|ay's x-resolution, y is the display's y-resolution, FOV is the field-
`
`of-view angle, a is the angle between the image's plane normal and the line
`
`connecting the viewpoint and the point in the cell of shortest distance to it, t is the
`
`length of the square each pixel in the original image is assigned to in 3D, and 2
`
`is the height of the camera over the image's plane.
`
`This arrives at the equation:
`
`I = log, (22 /(xycos(a)ctg2(O.5FOV)t2))
`
`Attorney Docket No.: FLVT3003
`gbr/flvt/3003.000.provisional .wpd
`
`T 2/2 6/2 000
`
`10
`
`10
`
`
`
`OO\lO~U'I-l>OOl\)—-I
`
`
`
`-10-
`
`l = max(O, min(l, M))
`
`For example, using a 64x64 target grid display to render the image from a view
`
`of height N with FOV angle of 90 degrees, with the length of each pixel in space
`
`being one, the entire target image can be fitted precisely to the display as
`
`demonstrated by:
`
`l= log4(N2/(642 '1 'l '12)) = M
`
`Image Data Parcel Transfer for Multiple Target Image Layers:
`
`The ordered download process of the present invention can be extended
`
`to support the concurrent download of multiple target image layers for separate
`
`or composited rendering by the client system. For example, one such layer may
`
`be a geographic map and a second layer may be a graphic-based image overlay
`
`providing textual and graphical navigational cues. Both will be viewed by the user
`
`from the so me effective viewpoint and reflect navigational translations ofthe point
`
`of view over the map. Provided that both layers share the same coordinate
`
`system, data parcels representing the corresponding grid portions of each layer
`
`can be requested concurrently by the client system in execution of the process
`
`described above. That is, each layer image will be composed at each cell layer
`
`of corresponding mip-maps. The client system process of receiving and rendering
`
`data parcels is extended to distinguish between the data parcels as received for
`
`the different
`
`layers and, as appropriate, provides for the joint or separate
`
`rendering of the parcel data.
`
`Attorney Docket No.: FLVT3003
`gbr/flvt/3003.000.provisional.wpd
`
`12/2 6/2000
`
`11
`
`11
`
`
`
`
`
`:8;50%._@>fi__wu_.._QE0
`
`mEm_..._m_manE5on
`
`5..U....
`
`
`
`55.,Semx:__§_§§§
`
`5.
`.m§§.%
`
`am.m..._o.o___mo...Ǥ
`
`.3
`.A»,.afi.¥
`
`
`
`
`
`£9..
`
`m>:omn_m._om
`
`in5:5on
`
`.6wmo._mm_u
`
`:._OU¢m.€
`
`¢_5os_EON
`
`m_m:_E._¢._.
`
`b\\
`
`oEaEmom0
`
`U20
`
`12
`
`12
`
`
`
`
`
`
`N65
`
`13
`
`13
`
`
`
`
`64
`
`64
`
`64
`
`64
`
`64
`
`64
`
`64
`
`FIG. 4
`
`14
`
`14
`
`
`
`E1“mi:m
`
`15
`
`15
`
`
`
`64
`
`16
`
`16
Accessing this document will incur an additional charge of $.
After purchase, you can access this document again without charge.
Accept $ Charge
Still Working On It
This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.
Give it another minute or two to complete, and then try the refresh button.
A few More Minutes ... Still Working
It can take up to 5 minutes for us to download a document if the court servers are running slowly.
Thank you for your continued patience.
This document could not be displayed.
We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.
Your account does not support viewing this document.
You need a Paid Account to view this document. Click here to change your account type.
Your account does not support viewing this document.
Set your membership
status to view this document.
With a Docket Alarm membership, you'll
get a whole lot more, including:
- Up-to-date information for this case.
- Email alerts whenever there is an update.
- Full text search for other cases.
- Get email alerts whenever a new case matches your search.
One Moment Please
The filing “” is large (MB) and is being downloaded.
Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.
Your document is on its way!
If you do not receive the document in five minutes, contact support at support@docketalarm.com.
Sealed Document
We are unable to display this document, it may be under a court ordered seal.
If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.
Access Government Site
