`
`9‘11 ”i? Q
`
`m PW
`
`» x
`
`iI,
`
`is
`
`IN THE UNITED STATES PATENT AND TRADEMARK OFFICE
`
`REQUEST FOR FILING A PROVISIONAL APPLICATION FOR PATENT
`
`UNDER 37 CFR §1 .53 (C)
`
`
`|NVENTOR(S)
`
`
`
`
`Levanon
`I Lavi
`
`3 Nachal Besor St‘, Ramat Hasharn, Israel
`21 Bar llan St., Raanana, Israel
`
`TITLE OF THE INVENTION
`
`OPTIMIZATION T-JUNCTION CRACKING-PROBLEM OF IMAGE
`PARCELS BEING PACKET STREAMED BY UTILIZING QUADTREE
`SCHEME
`
`X
`
`Direct all correspondence to Customer Number 23488.
`
`Gerald B. Rosenberg, Esq.
`: N ewTec h Law
`
`(Reg No.: 30,320)
`
`Telephone:
`Facsimile:
`
`650.325.2100
`650.325.2107
`
`‘ 285 Hamilton Avenue, Suite 520
`; Palo Alto, California 94301
`
`IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
`23488
`PATENT TRADEMARK OFFICE
`
`o E
`F E
`“in 5
`Jo go
`"2% 23
`i =3 Ea
`- 3.32:?
`..
`tam E
`h ’.
`
`EL 661 534 274 US
`
`ENCLOSED APPLICATION PARTS (check all that apply)
`11
`
`Specification
`
`No. of pages:
`
`Small Entity Statement
`
`D rawi ngs
`
`Declaration
`
`No. of sheets:
`
`5
`
`Power of Attorney
`
`Assignment and Cover Sheet
`
`Other: Return-Receipt Post Card
`
`METHOD OF PAYMENT OF FILING FEES FOR THIS PROVISIONAL APPLICATION FOR PATENT
`
`
`' Provisional Basic Filing Fee: $ 150.00 (Small Entity: $75.00)
`
`Filing Fee Amount: $ 150.00
`
`X
`
`A check is enclosed to cover the Filing Fees.
`
`The Commissioner is hereby authorized charge Filing Fees or credit any
`overpayment to: Deposit Account Number: 50-0890.
`
`This invention was n_ot made by or under contract with a US Government agency.
`
`US Government agency and Contract:
`
`Signature:
`
`Date: December 26 2000
`
`Gerald B. Rosenberg
`Reg. No.: 30320
`
`pplication Docket No:
`
`FLVT3002
`
`Express Mail Label No.:
`
`- Address To:
`
`Box Provisional A- olication Assistant Commissioner for Patents Washin-ton DC 20231
`
`gbr/flvt/S002.002.prov:xmittal wpd
`
`Page 1 of 95
`
`Unified Patents Exhibit 1019
`
`OU/Lz/ZTIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIOldem8969!;
`
`
`
`Page 1 of 95
`
`Unified Patents Exhibit 1019
`
`
`
`EFFICIENT CORRECTION OF T-JUNCTION
`
`CRACKING-PROBLEM OF IMAGE PARCELS BEING
`
`PACKET STREAMED BY UTILIZING QUADTREE
`
`SCHEME
`
`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.
`
`Summafl of the Invention
`
`The obiective is to display a two-dimensional pixel map, a16-Bit RGB color
`
`image in the preferred embodiments, of very large dimensions and permitting the
`
`viewing of the imagefrom 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.: FLVT3002
`gbr/flvt/3002.000.provisional.wpd
`
`12/26/2000
`
`Page 2 of 95
`
`Unified Patents Exhibit 1019
`
`1
`
`2
`
`3
`
`4
`
`5 6 7 8
`
`9
`
`10
`
`I I
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`1‘9
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`26
`
`
`
`=
`
`Page 2 of 95
`
`Unified Patents Exhibit 1019
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`9
`
`10
`
`1 1
`
`12
`
`13
`14
`
`15
`
`16
`17
`18
`19
`
`20
`
`21
`
`22
`23
`24
`25
`
`
`
`-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 1) 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 narrowband
`
`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 providedl
`
`Attorney Docket No.: FLVT3002
`gbr/flvt/3002.000.provisional.wpd
`
`12/26/2000
`
`Page 3 of 95
`
`Unified Patents Exhibit 1019
`
`Page 3 of 95
`
`Unified Patents Exhibit 1019
`
`
`
`-3-
`
`v
`
`._|
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`l l
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`l8
`
`1‘?
`
`20
`
`21'
`
`22
`
`23
`
`24
`
`25
`
`
`
`
`~
`
`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.: FLVT3002
`gbr/flvt/3002.000.provisional.wpd
`
`12/26/2000
`
`Page 4 of 95
`
`Unified Patents Exhibit 1019
`
`Page 4 of 95
`
`Unified Patents Exhibit 1019
`
`
`
`-4-
`
`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 ds
`
`32x32, would create a 0.5KByte parcel, hence ca using 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 transmission. 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
`
`1
`
`2 3 4 5
`
`6 7
`
`8
`
`9
`
`10
`
`1 1
`
`12
`
`13
`
`14'
`
`15
`
`16
`
`1 7
`
`18
`
`'19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`
`
`
`Attorney Docket No.: FLVT3002
`gbr/flvt/3002.000.provisiona|.wpd
`
`12/26/2000
`
`Page 5 of 95
`
`Unified Patents Exhibit 1019
`
`Page 5 of 95
`
`Unified Patents Exhibit 1019
`
`
`
`u—I
`
`assistants (PDAs) and cellular phones.
`
`Since access to cache memory is
`
`-5-
`
`O\OOO\IO\U‘IJAOON2
` l3
`
`
`12
`
`it
`
`19
`
`20
`
`2]
`
`22
`
`23
`
`24
`
`25
`
`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 subiect 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 subiect 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.2 FLVT3002
`gbr/flvt/3002 .000.provisional.wpd
`
`l 2/26/2000
`
`Page 6 of 95
`
`Unified Patents Exhibit 1019
`
`Page 6 of 95
`
`Unified Patents Exhibit 1019
`
`
`
`1
`
`2
`3
`
`4
`
`5
`6
`
`7
`8
`9
`
`10
`
`1 l
`
`1 2
`
`13
`
`T4
`
`15
`16
`1 7
`
`18
`
`19
`20
`
`21
`
`22
`
`23
`24
`
`25
`
`
`
`-6—
`
`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.: FLVT3002
`gbr/flvt/3002.000.provisional.wpd
`
`12/26/2000
`
`Page 7 of 95
`
`Unified Patents Exhibit 1019
`
`Page 7 of 95
`
`Unified Patents Exhibit 1019
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`10
`
`1 1
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`19
`
`20
`21
`
`22
`
`23
`24
`25
`
`
`
`—
`
`-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 10 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 l0,i,i that together compose the
`target image IO. The rectangle [64i,64i + 64] x [641,64 1 + 64] of '0 is mapped
`
`to lOM‘
`
`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 10 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:
`
`1k+1 (1,1) = avg(lk (21,21), 1,421 + 1,2)), 1421,21 + 1), lk(2i + 1,2) + 1))
`
`Such mip-maps are created up to IM,M = log2 (N) - 6. At this point, lM 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 UK“) for each mip-map. Each nonempty image cell lk,i,1
`now may be downloaded. Larger values of k cover more area within the original
`
`Attorney Docket No.: FLVT3002
`gbr/flvt/3002.000.provisional.wpd
`
`12/26/2000
`
`Page 8 of 95
`
`Unified Patents Exhibit 1019
`
`Page 8 of 95
`
`Unified Patents Exhibit 1019
`
`
`
`-8-
`
`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 lkmr 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 at these cells is by constructing a tree,
`
`starting trom INJSIOI0 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 1k has exactly tour matching 64x64
`
`pixel images on the grid 1“ covering the same area, the data structure is built
`
`O\OOO\IO\U‘i-J>-OOI\J—'
`
`accordingly.)
`
`For every frame that is rendered , begin with the cell that covers the area
`
`
` It the principle mip-map level is equal or higher than the level of the cell,
`
`1 1
`
`12
`
`13
`
`of the entire original image, lN-6,0,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 four 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.
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`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 otthe image cell actually used is the highest. Downloading is asynchronous;
`
`the tenderer 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.: FLVT3002
`gbr/flvt/SOOZ.000.provisional.wpd
`
`l 2/26/2000
`
`Page 9 of 95
`
`Unified Patents Exhibit 1019
`
`Page 9 of 95
`
`Unified Patents Exhibit 1019
`
`
`
`-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
`
`equation:
`
`l = max(0, log4 (T/S))
`
`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‘l‘
`
`and
`
`S = xycosla)ctgz(0.5FOV)t2 T / 22
`
`where x is the display'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 z
`
`is the height of the camera over the image‘s plane.
`
`This arrives at the equation:
`
`Attorney Docket No.: FLVT3002
`gbr/flvt/3002.000.provisional.wpd
`
`12/26/2000
`
`l
`
`2 3 4 5
`
`6
`
`7 8
`
`
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`Page 10 of 95
`
`Unified Patents Exhibit 1019
`
`Page 10 of 95
`
`Unified Patents Exhibit 1019
`
`
`
`-10-
`
`I = log4 (22 /(xyc05(0)ct92(0-5FOVW
`
`l = maxlO, min(l, Ml)
`
`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:
`
`I: log4(N2/(642 -i -1 ~12» = M
`
`Image Quality Management at T-Junctions:
`
`Note that the geometry (polygons) generated by quadtree scheme is non—
`
`manifold, dueto a problem shared among all adaptively subdivision triangulation
`
`schemes, known as the T-iunction cracking problem, where an image parcel is
`
`adiacent to two smaller image parcels.
`
`In the case of the present invention, all
`
`parcels are 64x64 pixel arrays, where the parcels for smaller dimensioned grids
`
`represent a correspondingly higher resolution. The spatial discontinuity created
`
`by the difference in resolutions, specifically between one grid and the sub-grids
`
`of an adjacent grid, results in undesirable display artifacts.
`
`The present invention provides a solution to this problem by converting the
`
`polygon, or in the present instance, grid mesh into a Manifold surface by adding
`
`vertices along edges connecting grids of different cell levels. The addition of new
`
`vertices, where necessary, is done efficiently, involving only constant time per
`
`vertex added.
`
`Attorney Docket No.: FLVT3002
`gbr/flvt/3002.000.provisional.wpd
`
`12/26/2000
`
`l 2 3 4 5 6 7 8
`
`
`
`
`T9
`
`20
`
`21
`
`22
`
`23
`
`24
`
`Page 11 of 95
`
`'
`
`'
`
`Unified Patents Exhibit 1019
`
`Page 11 of 95
`
`Unified Patents Exhibit 1019
`
`
`
`-11-
`
`The algorithm of the present invention works as follows: an 8-bit square
`
`map is created, in which the edge length is 2 + N/64. Where the target image
`
`size in pixels is (X, Y), N is the smallest power of 2 that is equal or greater than
`
`max {X,Y}. For each frame rendered, the contents of this map are reset to zero.
`
`Each cell that is rendered, is also drawn as a square on the map, corresponding
`
`to the area it occupies, using the number M - l as a color, where l is the level of
`
`the grid the polygon is upon, where M is M = log2 (N) - 6.
`
`The boundaries of the map remain set to zero while the cells are drawn.
`
`When each of the polygons is rendered, its boundaries on the map are checked.
`
`Pixels on the map are evaluated to check if any vertices should be added.
`
`Locations that can be predicted mathematically are not read from the map and
`
`are skipped. Consequently, the process implemented by the present invention is
`
`efficient and, in particular, more efficient than searching within traditional data
`
`structures such as the Quad-tree as an approach to preventing the occurrence of
`
`T-iunction based artifacts.
`
`—J
`
`OOCDNOUT-h-OOM
`
`1 1
`
`12
`
`13
`
`14
`
`15
`
`
`
`Attorney Docket No.: FLVT3002
`gbr/flvt/3002 .000.provisional.wpd
`
`12/26/2000
`
`Page '12 of 95
`
`Unified Patents Exhibit 1019
`
`Page 12 of 95
`
`Unified Patents Exhibit 1019
`
`
`
`wEmEmEantam.ON
`
`
`
`:3“LE8%.305%..w
`
`.25.mp5.9:85
`
`,fiwfi.
`
`Q.
`9m.)
`S”g4%
`
`Eff“
`
`5HI...
`
`m5—63722::
`
`598?:
`
`fig
`
`lama“
`
` 28%.SEE:
`
`Acnmhmoow
`
`U20
`
`x_m53>0....
`
`9532mg
`
`Ecumen—
`
`2:09.29".
`
`O
`
`mEgo—>—5ON
`
`mfiEEE...
`
`Page 13 of 95
`
`Unified Patents Exhibit 1019
`
`Page 13 of 95
`
`Unified Patents Exhibit 1019
`
`
`
`
`
`QUE
`
`a
`
`Page 14 0f 95
`
`Unified Patents Exhi
`
`it 1019
`
`Page 14 of 95
`
`Unified Patents Exhibit 1019
`
`
`
`
`
`
`Page 15 of 95
`
`Unified Patents Exhibit 1019
`
`Page 15 of 95
`
`Unified Patents Exhibit 1019
`
`
`
`
`
`FIGS
`
`
`
`Page 16 of 95
`
`Unified Patents Exhibit 1019
`
`Page 16 of 95
`
`Unified Patents Exhibit 1019
`
`
`
`64
`
`64
`
`
`
`64
`
`Page 17 of 95
`
`Unified Patents Exhibit 1019
`
`Page 17 of 95
`
`Unified Patents Exhibit 1019
`
`
`
`is weer-ee
`
`1‘9 [Pf-10"]
`
`IN THE UNITED STATES PATENT AND TRADEMARK OFFICE
`REQUEST FOR FILING A PROVISIONAL APPLICATION FOR PATENT
`UNDER 37 CFR §I .53 (c)
`
`‘A
`
`INVENTOR(S)
`
`Levanon
`‘ Lavi
`
`
`
`l 3 Nachal Besor St., Ramat Hasham, Israel
`
`21 Bar llan St., Raanana, Israel
`
`TITLE OF THE INVENTION
`
`OPTIMIZATION OF RENDERING MEMORY USAGE IN FAST QUALITY
`BUILD-UP TARGET IMAGE TRANSFER OVER LIMITED AND
`NARROWBAND COMMUNICATION NETWORKS
`
`mmmmwI
`.5.25346
`14U60/
`
`/O
`
`11111<
`
`lllIIllllllllllllllonem2969!:
`
` :1 Signature:
`
`en eeeeeeeee ee Cusemer Number ”48—8
`
`llllllllIlllllllllllllllll
`
`Gerald B. Rosenberg, Esq.
`NewTechLaw
`. 285 Hamilton Avenue, Suite 520
`Palo Alto, California 94301
`
`(Reg No.: 30,320)
`
`Telephone:
`Facsimile:
`
`650.325.2100
`650.3252 I O7
`
`2 4
`PATENTTSDEgRSKOFFKZE
`
`ENCLOSED APPLICATION PARTS (check all that apply)
`
`Specification
`
`No. of pages:
`
`Drawings
`
`No. of sheets:
`
`11
`
`5
`
`_ Small Entity Statement
`
`_ Power of Attorney
`
`Declaration
`
`__ Assignment and Cover Sheet
`
`Other: Return-Receigt Post Card.
`
`METHOD OF PAYMENT OF FILING FEES FOR THIS PROVISIONAL APPLICATION FOR PATENT
`
`: Provisional Basic Filing Fee: $ 150.00 (Small Entity: $75.00)
`
`Filing Fee Amount: $ 150.00
`
`A check is enclosed to cover the Filing Fees.
`
`The Commissioner is hereby authorized charge Filing Fees or credit any
`overpayment to: Deposit Account Number: 50—0890.
`
`This invention was r_1_o__t made by or under contract with a US Government agency.
`
`US Government agency and Contract:
`
`Gerald B. Rosenberg
`Reg. No.: 30.320
`
`Date: December 26. 2000
`
`Application Docket No:
`
`FLVT3004
`
`Express Mail Label No.2
`
`EL 661 534 291 US
`
`; Address To:
`
`Box Provisional A- olication Assistant Commissioner for Patents Washinoton DC 20231
`
`gbr/flvb’3004.002 prov xmittal wpd
`
`Page 18 of 95
`
`Unified Patents Exhibit 1019
`
`Page 18 of 95
`
`Unified Patents Exhibit 1019
`
`
`
`OPTIMIZATION OF RENDERING MEMORY USAGE IN
`
`FAST QUALITY BUILD-UP TARGET IMAGE TRANSFER
`OVER LIMITED AND NARROWBAND
`
`COMMUNICATION NETWORKS
`
`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 obiective is to display a two-dimensional pixel map, aI 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.
`
`Attorney Docket No.: FLVT3004
`gbr/tlvt/3004.000.provnsional.wpd
`
`12/26/2000
`
`Page 19 of 95
`
`Unified Patents Exhibit 1019
`
`I
`
`2
`3
`
`4
`
`5 6 7 8 9
`
`IO
`
`I I_
`I2
`
`I3
`
`I4
`
`I5
`
`16
`
`I7
`
`I8
`
`I9
`
`20
`
`2I
`
`22
`
`23
`
`24
`
`25
`
`
`
`‘
`
`Page 19 of 95
`
`Unified Patents Exhibit 1019
`
`
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`1 1
`
`12
`
`13 1
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`25
`
`-2-
`
`Images, as stored by the server, may individually range from gigabytes to
`
`multiple terabyte in total size. A correspondingly large server storage and
`
`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 1) 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 narrowband
`
`communication link.
`
`The multiple layers of an image allow the selectivity to incorporate
`
`topographical, geographical, orientational, and other terrain and mapping
`
`Attorney Docket No.: FLVT3004
`gbr/flvt/3004.000.provisional.wpd
`
`12/26/2000
`
`Page 20 of 95
`
`Unified Patents Exhibit 1019
`
`Page 20 of 95
`
`Unified Patents Exhibit 1019
`
`
`
`-3-
`
`related information into the image delivered. Other layers, such as geographic
`grids, graphical text overlays, and hyperlink selection areas, separately provided
`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
`
`1
`2
`3
`4
`
`5
`
`6
`
`M
`
`7
`8
`9
`10
`11
`12
`13
`14
`" 15
`
`
`
` 16
`
`=3
`
`1 7
`18
`19
`20
`21
`22
`23
`
`24
`25
`
`is
`communication links, the target image, as requested by the client system,
`represented by multiple grids of 64x64 image pixels (Figure 4) with each grid
`
`Attorney Docket No.: FLVT3004
`gbr/flvt/3004.000.provi5|onal.wpd
`
`/
`
`12/26/2000
`
`Page 21 of 95
`
`Unified Patents Exhibit 1019
`
`Page 21 of 95
`
`Unified Patents Exhibit 1019
`
`
`
`-4_
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`.9
`10
`
`1 1
`
`12
`
`.13
`
`i4
`15
`16
`1 7
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24 '
`
`25
`
`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
`
`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, 0 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 0.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 fortransmission.
`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 la rger image array,
`
`such as 128x128, is too large to be fully placed within the level-1 cache of many
`
`
`
`é
`
`
`
`_
`
`
`Attorney Docket No.: FLVT3004
`gbr/flvt/3004.000.provisional.wpd
`
`12/26/2000
`
`Page 22 of 95
`
`Unified Patents Exhibit 1019
`
`Page 22 of 95
`
`Unified Patents Exhibit 1019
`
`
`
`l
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`1 l
`
`T2
`
`13
`
`14
`
`.15
`
`16
`
`l7
`18
`l9
`
`20
`
`21
`
`22
`
`23
`
`24
`'25
`
`
`
`3
`r
`
`-5-
`
`of the smaller conventional current processors, such as used by personal digital
`
`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 subiect to different client
`
`system design factors, other parcel sizes may be used.
`
`ln 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