# Patent

## Title
Method and apparatus for parallel speculative rendering of synthetic images

## Abstract

A method, apparatus and computer program product for parallel speculative rendering of synthetic images in an image rendering system are presented. The operations include obtaining measurements regarding scene characteristics. The measurements are provided to predictors, each predicting a future state for a measurement. The future states are provided to a renderer that renders graphical entities, each rendering resulting from a different predicted future state. Subsequently, a new set of measurements is obtained regarding the scene characteristics. Then each measurement of the new set of measurements is compared with a corresponding one of the predicted future states produced by the predictors. The predicted future state that most closely matches with the new measurements is then selected. Then, the graphical entities associated with the predicted future state that most closely match with the new measurements are selected. The selected graphical entities displayed on a display device.

## Background
BACKGROUND OF THE INVENTION
(1) Technical Field
The present invention relates to techniques for registering components in computer-generated scenes. More specifically, the present invention relates to a technique for registering synthetic images of components by generating parallel predictions and selecting the most accurate prediction for display to a user.
(2) Discussion
In graphics systems that are required to produce images derived from changing data, in which the images must be produced as quickly as possible, current technologies suffer from registration accuracy-related drawbacks. One such example is that of head-tracked display systems that create images specific to a particular eye position, orientation, and field of view. Usually these parameters are supplied by sensors that measure an operator's head or gaze position and orientation. As the operator's head moves, the sensors feed updated parameters to the system so that new images can be created consistent with the new parameters. Since the image is usually synthetic, or contains synthetic elements, it takes time to construct. By the time the image reaches its ultimate display surface, there is some difference between the current sensor outputs and the parameters used to construct the image. Visually, the result is incorrect registration of synthetic components, which can result in confusion, nausea, and other undesirable physical and psychological effects.
Current systems for generating synthetic or augmented computer graphic scenes use a sequence of steps to produce an output image at the display device, as depicted in FIG. 1, which shows a typical sequence. In a sensing step 100, one or more sensors feed data, for example a viewer's eyepoint and gaze direction into a prediction module. Typical sensors used include magnetic, video, and inertial sensors. Next, in a predicting step 102, a predicting module attempts to predict a future value of the sensor data, such as what the eyepoint and gaze directions will be at the time the image is finally displayed. Typical predicting modules include, for example, Kalman filters as well as other behavioral and physical models. After the predicting step 102 has finished, a rendering step 104 is performed by a render module that creates an image in memory based on inputs from the predicting step 102. At the conclusion of rendering, in a warping step 106, new sensor inputs may be used to warp the image to adjust for small changes to the viewing parameters. The warping step 106 is typically performed by interpolating the image to match current information from the sensors. After the image has been sufficiently warped, a displaying step 108 is performed to produce an image on an output device. Most existing systems do not perform the predicting step 102 or the warping step 106, and simply attempt to keep up with the sensors as well as possible.
The technique depicted in FIG. 1 can work well if the prediction and warping modules produce good results, i.e., the correct future parameter values are predicted and the warping does not introduce noticeable visual artifacts and can be accomplished quickly. Unfortunately, these conditions are often not met, resulting in serious visual artifacts.
Accordingly, there exists a need in the art for a fast and reliable system for properly registering synthetic images of components at their proper locations in computer-generated scenes. Such a system would provide final images that closely match the current state of the sensors, thereby eliminating the undesirable physical and psychological side effects described above.
SUMMARY OF THE INVENTION
The present invention provides a method, apparatus, and computer product for parallel speculative rendering of synthetic images in an image rendering system. In the method aspect, steps are performed, including first obtaining measurements regarding scene characteristics. Next, a step is performed for providing the measurements to a plurality of predictors, for predicting, at each of the predictors, a future state for each of the measurements. Next, the future states are provided to a plurality of renderers. Each renderer renders graphical entities such that each rendering results from a different predicted future state. Next, a new set of measurements regarding the scene characteristics is obtained. At a comparator, each one of the new set of measurements is compared with a corresponding one of the predicted future states produced by the predictors. The predicted future state most closely matching with the new measurements is determined, and its associated graphical entities are selected. The graphical entities are then output for display on a display device.
In another aspect of the present invention, multiple predicting, providing, and rendering steps are performed, with each sequence of predicting, providing, and rendering steps performed substantially in parallel with respect to the others.
In still another aspect of the present invention, the parallel sequences of predicting, providing, and rendering steps are performed asynchronously with respect to each other.
In yet another aspect of present invention, the measurements are obtained from at least two sensors with each sensor selected from a group consisting of magnetic sensors, video sensors, position sensors, inertial sensors, databases, and computer networks.
In a further aspect of the present invention, each step of predicting is performed by predictors having a configuration selected from a group consisting of Kalman filters, sudden-stop and sudden-start models, and behavioral and physical models.
In another aspect present invention, the predictors predict values at a common future time.
In yet another aspect of the present invention, at least two predictors have the same configuration, and wherein the predictors produce output based on differing assumptions.
In a yet further aspect of the present invention, the predictors provide output having the same form as the measurements regarding the scene characteristics.
In another aspect of the present invention, in the step of rendering, for each renderer, there is an average of at least one predictor.
In still another aspect of the present invention, the step of comparing is performed by a simple weighted summing of value differences between the predicted future state and the new set of measurements.
In another aspect of the present invention, each predictor includes multiple prediction models along with a model that models the likelihood of each of the other models being accurate, where the method further comprises a step of selecting the model having the greatest likelihood of being accurate, and wherein the predicting step is performed using the model having the greatest likelihood of being accurate.
In a still further aspect of the present invention, in the step of comparing, a comparator is biased based on a combination of at least one biasing parameter selected from a group consisting of user-specified preferences, system-derived preferences, and a belief network in a predictor.
In another aspect the present invention, the step of selecting is performed by a switch configured to select a plurality of images for display in an environment selected from multi-image display environments and multi-user environments with multiple displays.
In yet another aspect of the present invention, the step of comparing, the step of rendering, and the step of switching are performed competitively as steps in a self-optimizing process subject to the following constraint:

Δtd+Δtp+Δtr+Δtc+Δts=Tp, where:

    
    
        Tp=total prediction time;
        Δtd=average time between data updates;
        Δtp=average time to perform one prediction;
        Δtr=average time to render one scene;
        Δtc=average time to compare all predicted states with the current state; and
        Δts=average time to switch between one candidate image and another.
    
    


In another aspect of the present invention, the predictors are configured to predict all possible future states and wherein the renderers are configured to render all possible future states.
In a further aspect of the present invention, the predictors are configured with a variety of prediction models, having a variety of processing speeds and a variety of qualities, so that a variety of predicted future states is available; whereby different models may be used depending on the speed and quality of prediction necessary.
In a still further aspect of the present invention, for each predictor, there is an average of more than one renderer.
In another aspect of the present invention, the predictors predict values at different future times.
In a yet further aspect of the present invention, the parallel sequences of predicting, providing, and rendering steps are performed synchronously with respect to each other.
It will be appreciated that the operations described above can be incorporated into a computer system or placed onto a computer readable medium as a computer program product without departing from the scope of what is taught. These aspects are considered within the scope of the present invention, as will be explained in greater detail in the detailed description below and in the accompanying claims.



BRIEF DESCRIPTION OF THE DRAWINGS
The objects, features and advantages of the present invention will be apparent from the following detailed descriptions of the preferred aspect of the invention in conjunction with reference to the following drawings.
FIG. 1 is a block diagram depicting steps in a “traditional” prior art method of scene generation;
FIG. 2 is a block diagram of a computer system used in conjunction with the present invention;
FIG. 3 is an example of a computer program product aspect of the present invention, in the form of a computer-readable medium;
FIG. 4 is a block diagram depicting an aspect of the present invention with multiple parallel rendering processes; and
FIG. 5 is a block diagram depicting functional steps or modules of an aspect of the invention in greater detail.



DETAILED DESCRIPTION OF PREFERRED ASPECTS
The present invention relates to techniques for registering components in computer-generated scenes. More specifically, the present invention relates to a technique for properly registering synthetic images of components by generating parallel predictions and selecting the most accurate prediction for display to a user. The following description, taken in conjunction with the referenced drawings, is presented to enable one of ordinary skill in the art to make and use the invention and to incorporate it in the context of particular applications. Various modifications, as well as a variety of uses in different applications, will be readily apparent to those skilled in the art, and the general principles defined herein, may be applied to a wide range of aspects. Thus, the present invention is not intended to be limited to the aspects presented, but is to be accorded the widest scope consistent with the principles and novel features disclosed herein. Furthermore it should be noted that unless explicitly stated otherwise, the figures included herein are illustrated diagrammatically and without any specific scale, as they are provided as qualitative illustrations of the concept of the present invention.
In order to provide a working frame of reference, first a glossary of terms used in the description and claims is given as a central resource for the reader. Next, a discussion of various physical aspects of the present invention is provided. Finally, a discussion is provided to give an understanding of the specific details.
(1) Glossary
Before describing the specific details of the present invention, a centralized location is provided in which various terms used herein and in the claims are defined. The glossary provided is intended to provide the reader with a feel for the intended meaning of the terms, but is not intended to convey the entire scope of each term. Rather, the glossary is intended to supplement the rest of the specification in more accurately explaining the terms used.
Graphics Component—As used herein, the phrase “graphics component” identifies information that directly or indirectly determines the appearance of all or part of a rendered image. Non-limiting examples include geometric models of physical objects, global and local lighting information, material properties, graphical representations of information (e.g., data used to populate a graph or diagram).
Means—In one context, the term “means” as used with respect to this invention generally indicates a set of operations to be performed on a computer, and may represent pieces of a whole program or individual, separable, software modules. Non-limiting examples of “means” include computer program code (source or object code) and “hard-coded” electronics (i.e. computer operations coded into a computer chip). The “means” may be stored in the memory of a computer or on a computer readable medium. In another context, the term “means” is used with hardware components to indicate a device that produces the function of the “means.”
Scene Characteristics—As used herein, the phrase “scene characteristics” specifies the set of values that define a synthetic image, non-limiting examples of which include viewpoint, position, and orientation information, graphical entity position and orientation, spatial relationships among graphical entities, the representation of entities in the rendered image (e.g. in one measurement, a hand may be represented as a hand, while in another, it may be represented as another object such as a stick), and scene and entity color and lighting characteristics.
(2) Physical Aspects
The present invention has three principal “physical” aspects. The first is a system for properly rendering synthetic components in computer-generated images, typically in the form of a combination of a computer system operating software (possibly in the form of a “hard-coded” instruction set) and a dedicated graphical processor 206 such as a graphics card. This system may be incorporated into various devices, non-limiting examples including augmented reality systems, video games, and simulators, and may be coupled with a variety of sensors that provide information regarding the system state. The second physical aspect is a method, typically in the form of software, operated using a data processing system (computer). The third principal physical aspect is a computer program product. The computer program product generally represents computer readable code stored on a computer readable medium such as an optical storage device, e.g., a compact disc (CD) or digital versatile disc (DVD), or a magnetic storage device such as a floppy disk or magnetic tape. Other, non-limiting examples of computer readable media include hard disks, read only memory (ROM), and flash-type memories. These aspects will be described in more detail below.
A block diagram depicting the components of a computer system used in the present invention is provided in FIG. 2. The data processing system 200 comprises an input 202 for receiving information from at least one sensor for use in registering synthetic components. Note that the input 202 may include multiple ports. Typically, input is received from sensors such as CMOS and CCD vision sensors, magnetic sensors, inertial sensors, databases, and networks. The output 204 is connected with the processor 206 for providing information to other systems, such as a display (not shown) to display a scene with a properly registered synthetic component. Output may also be provided to other devices or other programs, e.g. to other software modules, for use therein. The input 202 and the output 204 are both coupled with a processor 206, which may be a general-purpose computer processor or a specialized processor designed specifically for use with the present invention. The processor 206 is coupled with a memory 208 to permit storage of data and software to be manipulated by commands to the processor. Depending on the requirements of a particular application, it is important to note that a plurality of computing devices may be used in combination. The specific configuration is understood to be adapted to a particular application, as will be readily understood by one of skill in the art.
An illustrative diagram of a computer program product embodying the present invention is depicted in FIG. 3. The computer program product 300 is depicted as an optical disk such as a CD or DVD. However, as mentioned previously, the computer program product generally represents computer readable code stored on any compatible computer readable medium.
(3) Introduction
The present invention replaces the “traditional” single sequence shown in FIG. 1 with multiple parallel sequences as shown in FIG. 4. Using multiple prediction models having differing parameters, multiple possible scenes are rendered in parallel on separate hardware platforms. When at least some renderers have finished rendering, current sensor values are compared with those implied by each prediction to determine the closest fit. The rendering that most closely matches current conditions is then selected. An electronically controlled switch then sends the single rendered image to the display.
Specifically, with regard to FIG. 4, a sensing step 400 is performed using at least one sensor. Non-limiting, but typical, sensor choices include magnetic sensors, such as compasses, video sensors such as CCD cameras, inertial sensors such as gyroscopes, and other sensors as appropriate for a particular application. After the sensing step has been performed, prediction steps 402 are performed in parallel based on the sensor information. The prediction steps 402 typically use different prediction models and/or different model parameters. Non-limiting, but typical, prediction model choices include Kalman filters and other behavioral and physical models. After at least some of the prediction steps 402 are complete, rendering steps 404 are performed to render scene for a user. In each rendering step 404, pixels of a rendered image are stored in a display buffer. The individual predicting steps 402 and the rendering steps 404 are performed substantially in parallel. However, the specific individual steps may vary in their particular execution time. Furthermore, the number of predicting step 402 and rendering step 404 pairs can be selected as desired for a particular apparatus, and may be variable even within the same apparatus by user command or by some other automatic selection process. After the rendering steps 404 have been completed, a second sensing step 406 is performed, and the results of the second sensing step 406 are compared with the results of the predicting steps 402 to determine which image resulted from the best prediction. A switching step 408 is then performed to gate this image for displaying 410 on a display device. It is also important to note that prediction may also involve parameters that affect the temporal use of rendered scene. In this case, the prediction and rendering may occur asynchronously and be available for display at variable rates depending on the needs of an application.
Furthermore, it is also worth noting that the present invention is not limited to the example described above, which may be used, for example, in head-tracking devices. Rather, the present invention can be used in any system that renders a sequence of images based on unpredictable dynamic inputs. The unpredictability may derive from sensors, as above, or for example, from changes in the simulated or real positions of components in a scene.
Thus, the present invention permits improved visual response to changes in information affecting graphic components. Also, it helps to make head-tracked displays more comfortable and accurate with less negative physical and psychological effects. The present invention will benefit any device that includes a gaze directed display. Examples may include future combat systems (FCS), airborne operator interfaces, and Augmented Reality (AR) and Virtual Reality (VR) displays. It will also benefit programs that attempt to visualize unpredictable dynamic situations, such as rapidly-changing battlespace visualizations, air traffic control (ATC) displays, immersive training, computer-guided assembly processes, and real-time military simulations. It can be used in the computer gaming industry to create images that more correctly correspond to player's commands. Also, for example, in automotive heads-up displays, it can increase the fidelity of the heads-up display to the current vehicle/driver situation. These examples represent only a few of the potential applications of the present invention that will be appreciated by those of skill in the art.
A block diagram showing a more detailed aspect of the present invention is shown in FIG. 5. This block diagram depicts functional steps or modules of the present invention and is intended to provide the reader with a better understanding of its operations. First, data sources 500 provide information that affects graphical components, such as information about the physical environment. The data sources 500 typically include sensors as discussed previously. Note that the data sources 500 could include other types of “sensors” in the context of a videogame or simulator. The information may be provided, for example, by magnetic 6-degree of freedom (DOF) trackers, Global Positioning System (GPS) receivers, earth magnetic field sensors, or vision systems. The data sources 500 provide output to populate a data structure that represents the most up-to-date input values 502. These values are generally updated as quickly as the data sources 500 can provide them. The predictors 504, of which there are generally at least two for the invention to function properly, compute new sets of predicted input values 506 that represent hypothetical future values of the data sources 500. The predictors 504 generally operate in parallel, and possibly asynchronously, with each other. The predictors 504 can use a variety of methods to determine the hypothetical future values, non-limiting examples of which include Kalman filters, sudden-stop and sudden-start models, as well as knowledge of physical constraints on the data sources. All predictors 504 may provide predicted input values 506 at a common future time, or each may predict a different future time's values.
The predicted input values 506 result from predictors predicting future values of the input values based on different methods and assumptions. In some cases, there may be more predicted input values 506 than predictors (if predictors 504 act asynchronously and some take longer than others to produce output). In form, each set of predicted input values 506 is generally identical to the latest input values 502; they differ only in content. Although this qualification is not necessary, it makes the role of the comparator (discussed below) easier.
The renderers 508, of which there are generally at least two for the invention to function properly, compute new sets of candidate image values 510 that represent hypothetical future scenes. The renderers 508 generally operate in parallel, and possibly asynchronously with each other. Each renderer 508 can use the output from one predictor 504, or, depending on relative speeds, there may be M predictors 504 and N renderers 508, where M>1 and N>1 but M and N may have any relationship. As an example, in one manifestation of the invention, each renderer 508 might be a separate PC graphics card.
Each of the candidate images 510 produced by the renderers 508 is a single synthetic image of a scene rendered to the specifications of one prediction of future data source values. These are speculative images; that is, they correspond to possible future states, but only one will be selected for display. A premise of the present invention is the assumption that one candidate image 510 will be very close to the desired image (i.e., the image and all components in the image are properly registered), and expends some cost (risk) to increase the chances for success. Without this speculative rendering, the system would be forced to display an image derived from a single prediction of future input data sources values, and its success would depend wholly on the (single) predictor. Each candidate image 510 resides in an area of memory from which it can be read rapidly; if, for example, each renderer 508 is a separate PC graphics card, each candidate image 510 is made available at a card's output port.
At some time after the candidate images 510 have been created, of which there are generally at least two for the invention to function properly, a comparator 512 compares the (then or current) latest input values 502(c) with the values produced by the predictors 504 associated with each candidate image 510. A determination is made regarding which predicted values 506 are “closest” to the latest input values 502(c). This comparison may be a single weighted summing of value differences, or may be more complex method. Many such methods are available, as will readily be recognized by one of skill in the art. Note that element 502 is used to represent the latest input values from which the predictions are derived and that element 502(c) is used to represent the latest (or current) input values that are obtained for use in the comparator 512 to check against the predicted values 506 derived from the original latest input values 502.
When the comparator 512 has determined the best candidate image 510, based on predicted input values 506 that are closest to the actual latest input values 502(c), it activates a switch 514 to select that candidate image 510, which is then (for convenience) the selected image 516.
After the switch 514 has been activated, the selected image 516 is read from the candidate image storage. The selected image 516 is then displayed on a display medium 518, non-limiting examples of which include display monitors such as televisions, projectors, or other computer monitors and head-mounted displays.
In another aspect, the present invention can utilize more “intelligence” for the predictors 504, the comparator 512, and the switch 514. For example, the predicted input values 506 produced by the predictors 504 can be the result of a variety of models, including belief networks that model the likelihood of different outputs (and if desired, also prioritizing them), a rule-based system that models heuristic knowledge about behavior, or a model that tries to determine the theoretical or practical limit of possible viewpoints and gaze directions for one or more users (the latter is a brute-force approach that generate all possible scenes).
The predictors 504 might also be arranged in a hierarchical fashion, in which higher-level nodes predict using more primitive but faster methods than leaf-level predictors.
A more “intelligent” comparator 512 could, for example, be based on user specified preferences, system derived preferences, and/or a belief network from a predictor 504.
A “smart” switch 514 could, for example, select a set of images for display in a variety of conditions: a multi-image display environment like an immersive stereoscopic multi-screen or a multi-user environment with multiple display devices.
In yet another aspect, the predictors 504, the comparator 512, the renderers 508, and the switch 514 may be considered as competing components of a self-optimizing system. In this case, the number, sophistication, and time allotted to each component type would be controlled by an encompassing constraint function. This aspect is better understood with reference to the following example.
Let:

    
    
        Ts=total speculating/rendering time;
        Δtd=average time between data updates;
        Δtp=average time to perform one prediction;
        Δtr=average time to render one scene;
        Δtc=average time to compare all predicted states with the current state; and
        Δts=average time to switch between one candidate image and another.
    
    


Using the “traditional” approach shown previously in FIG. 1, the average time to produce an image at the output following a change in input values is approximately Δtd+Δtp+Δtr=Ts.
On the other hand, using the technique shown in FIG. 5, the time is approximately Δtd+Δtp+Δtr+Δtc+Δts=Tp. The difference between Ts and Tp is minimized when Δtc+Δts is minimized. Even if this quantity cannot be made very small (Δts is limited by the refresh rate of the output display), the result of the new method is an output image that is generally much closer to the current data than the image produced by the “traditional” method of FIG. 1. This result also suggests that the predictors 504 should be configured to predict to a time Ts in the future.
The overall performance of the system of the present invention may involve a trade-off between system utilization and accuracy. If predictions take a relatively long time, there will be fewer, generally more accurate, predictions and less overall parallelism leading to fewer candidate images 510. If, on the other hand, predictions are fast, the system may produce more predictions per unit time, enabling different predictions and prediction times (generally a greater amount of prediction time results in a greater degree of prediction accuracy or quality), resulting in more candidate images 510 from which to choose the best one.

## Claims

1. A method for parallel speculative rendering of synthetic images in an image rendering system comprising steps of:
obtaining measurements regarding scene characteristics;
providing the measurements to a plurality of predictors;
predicting, at each of the predictors, a future state for each of the measurements;
providing the future states to a plurality of renderers;
rendering, at each renderer, graphical entities such that each rendering results from a different predicted future state;
obtaining a new set of measurements regarding the scene characteristics;
comparing, at a comparator, each one of the new set of measurements with a corresponding one of the predicted future states produced by the predictors;
determining which predicted future state most closely matches with the new measurements;
selecting, at a switch, graphical entities associated with the predicted future state that most closely matches with the new measurements; and
displaying the selected graphical entities on a display device;
wherein providing the measurements to a plurality of predictors, the predictors are arranged in a hierarchical fashion having higher-level predictors and leaf-level predictors, and wherein predicting, the higher-level predictors predict at a faster rate than the leaf-level predictors.

2. A method as set forth in claim 1, wherein a plurality of predicting, providing, and rendering steps are performed, with each sequence of predicting, providing, and rendering steps performed substantially in parallel with respect to the others.

3. A method as set forth in claim 2, wherein the parallel sequences of predicting, providing, and rendering steps are performed asynchronously with respect to each other.

4. A method as set forth in claim 3, wherein the measurements are obtained from at least two sensors with each sensor selected from a group consisting of magnetic sensors, video sensors, position sensors, inertial sensors, databases, and computer networks.

5. A method as set forth in claim 4, wherein each step of predicting is performed by predictors having a configuration selected from a group consisting of Kalman filters, sudden-stop and sudden-start models, and behavioral and physical models.

6. A method as set forth in claim 5, wherein the predictors predict values at a common future time.

7. A method as set forth in claim 6, wherein at least two predictors have the same configuration, and wherein the predictors produce output based on differing assumptions.

8. A method as set forth in claim 7, wherein the predictors provide output having the same form as the measurements regarding the scene characteristics.

9. A method as set forth in claim 8, wherein in the step of rendering, for each renderer, there is an average of at least one predictor.

10. A method as set forth in claim 9, wherein the step of comparing is performed by a simple weighted summing of value differences between the predicted future state and the new set of measurements.

11. A method as set forth in claim 10, wherein in the step of predicting each predictor includes multiple prediction models along with a model that models a likelihood of each of the other models being accurate, and where the method further comprises a step of selecting the model having a greatest likelihood of being accurate, and wherein the predicting step is performed using the model having the greatest likelihood of being accurate.

12. A method as set forth in claim 11, wherein in the step of comparing, a comparator is biased based on a combination of at least one biasing parameter selected from a group consisting of user-specified preferences, system-derived preferences, and a belief network in a predictor.

13. A method as set forth in claim 12, wherein the step of selecting is performed by a switch configured to select a plurality of images for display in an environment selected from multi-image display environments and multi-user environments with multiple displays.

14. A method as set forth in claim 13, wherein the step of predicting, the step of comparing, the step of rendering, and the step of switching are performed competitively as steps in a self-optimizing process subject to the following constraint:


Δtd+Δtp+Δtr+Δtc+Δts=Tp, where:

Tp=total prediction time;
Δtd=average time between data updates;
Δtp=average time to perform one prediction;
Δtr=average time to render one scene;
Δtc=average time to compare all predicted states with the current state; and
Δts=average time to switch between one candidate image and another.

15. A method as set forth in claim 10, wherein the predictors are configured to predict all possible future states and wherein the renderers are configured to render all possible future states.

16. A method as set forth in claim 10, wherein the predictors are configured with a variety of prediction models, having a variety of processing speeds and a variety of qualities, so that a variety of predicted future states is available; whereby different models may be used depending on the speed and quality of prediction necessary.

17. A method as set forth in claim 8, wherein for each predictor, there is an average of more than one renderer.

18. A method as set forth in claim 5, wherein the predictors predict values at different future times.

19. A method as set forth in claim 2, wherein the parallel sequences of predicting, providing, and rendering steps are performed synchronously with respect to each other.

20. A method as set forth in claim 1, wherein the measurements are obtained from at least two sensors with each sensor selected from a group consisting of magnetic sensors, video sensors, position sensors, inertial sensors, databases, and computer networks.

21. A method as set forth in claim 1, wherein each step of predicting is performed by predictors having a configuration selected from a group consisting of Kalman filters, sudden-stop and sudden-start models, and behavioral and physical models.

22. A method as set forth in claim 21, wherein the predictors predict values at a common future time.

23. A method as set forth in claim 22, wherein at least two predictors have the same configuration, and wherein the predictors produce output based on differing assumptions.

24. A method as set forth in claim 23, wherein the predictors provide output having the same form as the measurements regarding the scene characteristics.

25. A method as set forth in claim 24, wherein in the step of rendering, for each renderer, there is an average of at least one predictor.

26. A method as set forth in claim 25, wherein for each predictor, there is an average of more than one renderer.

27. A method as set forth in claim 21, wherein the predictors predict values at different future times.

28. A method as set forth in claim 1, wherein the step of comparing is performed by a simple weighted summing of value differences between the predicted future state and the new set of measurements.

29. A method as set forth in claim 28, wherein the predictors are configured with a variety of prediction models, having a variety of processing speeds and a variety of qualities, so that a variety of predicted future states is available; whereby different models may be used depending on the speed and quality of prediction necessary.

30. A method as set forth in claim 28, wherein the predictors are configured to predict all possible future states and wherein the renderers are configured to render all possible future states.

31. A method as set forth in claim 1, wherein in the step of predicting each predictor includes multiple prediction models along with a model that models a likelihood of each of the other models being accurate, and where the method further comprises a step of selecting the model having a greatest likelihood of being accurate, and wherein the predicting step is performed using the model having the greatest likelihood of being accurate.

32. A method as set forth in claim 1, wherein in the step of comparing, a comparator is biased based on a combination of at least one biasing parameter selected from a group consisting of user-specified preferences, system-derived preferences, and a belief network in a predictor.

33. A method as set forth in claim 1, wherein the step of selecting is performed by a switch configured to select a plurality of images for display in an environment selected from multi-image display environments and multi-user environments with multiple displays.

34. A method as set forth in claim 1, wherein the step of predicting, the step of comparing, the step of rendering, and the step of switching are performed competitively as steps in a self-optimizing process subject to the following constraint:


Δtd+Δtp+Δtr+Δtc+Δts=Tp, where:

Tp=total prediction time;
Δtd=average time between data updates;
Δtp=average time to perform one prediction;
Δtr=average time to render one scene;
Δtc=average time to compare all predicted states with the current state; and
Δts=average time to switch between one candidate image and another.

35. An apparatus for parallel speculative rendering of synthetic images in an image rendering system, the apparatus comprising at least one computer, the computer comprising an input, a processor connected with the input, a memory connected with the processor, and an output connected with the processor, the computer further comprising means for performing operations of:
obtaining measurements regarding scene characteristics;
providing the measurements to a plurality of predictors;
predicting, at each of the predictors, a future state for each of the measurements;
providing the future states to a plurality of renderers;
rendering, at each renderer, graphical entities such that each rendering results from a different predicted future state;
obtaining a new set of measurements regarding the scene characteristics;
comparing, at a comparator, each one of the new set of measurements with a corresponding one of the predicted future states produced by the predictors;
determining which predicted future state most closely matches with the new measurements;
selecting, at a switch, graphical entities associated with the predicted future state that most closely matches with the new measurements; and
outputting the selected graphical entities;
wherein providing the measurements to a plurality of predictors, the predictors are arranged in a hierarchical fashion having higher-level predictors and leaf-level predictors, and wherein predicting, the higher-level predictors predict at a faster rate than the leaf-level predictors.

36. An apparatus as set forth in claim 35, wherein a plurality of predicting, providing, and rendering means are provided so that each sequence of predicting, providing, and rendering operations is performed substantially in parallel with respect to the others.

37. An apparatus as set forth in claim 36, wherein the parallel sequences of predicting, providing, and rendering operations are performed asynchronously with respect to each other.

38. An apparatus as set forth in claim 37, wherein the measurements are obtained from at least two sensors with each sensor selected from a group consisting of magnetic sensors, video sensors, position sensors, inertial sensors, databases, and computer networks.

39. An apparatus as set forth in claim 38, wherein each operation of predicting is performed by predictors having a configuration selected from a group consisting of Kalman filters, sudden-stop and sudden-start models, and behavioral and physical models.

40. An apparatus as set forth in claim 39, wherein the predictors predict values at a common future time.

41. An apparatus as set forth in claim 40, wherein at least two predictors have the same configuration, and wherein the predictors produce output based on differing assumptions.

42. An apparatus as set forth in claim 41, wherein the predictors provide output having the same form as the measurements regarding the scene characteristics.

43. An apparatus as set forth in claim 42, wherein in the operation of rendering, for each renderer, there is an average of at least one predictor.

44. An apparatus as set forth in claim 43, wherein the operation of comparing is performed by a simple weighted summing of value differences between the predicted future state and the new set of measurements.

45. An apparatus as set forth in claim 44, wherein in the operation of predicting each predictor includes multiple prediction models along with a model that models a likelihood of each of the other models being accurate, and where the apparatus further comprises a operation of selecting the model having a greatest likelihood of being accurate, and wherein the predicting operation is performed using the model having the greatest likelihood of being accurate.

46. An apparatus as set forth in claim 45, wherein in the operation of comparing, a comparator is biased based on a combination of at least one biasing parameter selected from a group consisting of user-specified preferences, system-derived preferences, and a belief network in a predictor.

47. An apparatus as set forth in claim 46, wherein the operation of selecting is performed by a switch configured to select a plurality of images for display in an environment selected from multi-image display environments and multi-user environments with multiple displays.

48. An apparatus as set forth in claim 47, wherein the means for predicting, the means for comparing, the means for rendering, and the means for switching are run competitively as operations in a self-optimizing process subject to the following constraint:


Δtd+Δtp+Δtr+Δtc+Δts=Tp, where:

Tp=total prediction time;
Δtd=average time between data updates;
Δtp=average time to perform one prediction;
Δtr=average time to render one scene;
Δtc=average time to compare all predicted states with the current state; and
Δts=average time to switch between one candidate image and another.

49. An apparatus as set forth in claim 44, wherein the predictors are configured to predict all possible future states and wherein the renderers are configured to render all possible future states.

50. An apparatus as set forth in claim 44, wherein the predictors are configured with a variety of prediction models, having a variety of processing speeds and a variety of qualities, so that a variety of predicted future states is available; whereby different models may be used depending on the speed and
quality of prediction necessary.

51. An apparatus as set forth in claim 42, wherein for each predictor, there is an average of more than one renderer.

52. An apparatus as set forth in claim 39, wherein the predictors predict values at different future times.

53. An apparatus as set forth in claim 36, wherein the parallel sequences of predicting, providing, and rendering operations are performed synchronously with respect to each other.

54. An apparatus as set forth in claim 35, wherein the measurements are obtained from at least two sensors with each sensor selected from a group consisting of magnetic sensors, video sensors, position sensors, inertial sensors, databases, and computer networks.

55. An apparatus as set forth in claim 35, wherein each operation of predicting is performed by predictors having a configuration selected from a group consisting of Kalman filters, sudden-stop and sudden-start models, and behavioral and physical models.

56. An apparatus as set forth in claim 55, wherein the predictors predict values at a common future time.

57. An apparatus as set forth in claim 56, wherein at least two predictors have the same configuration, and wherein the predictors produce output based on differing assumptions.

58. An apparatus as set forth in claim 57, wherein the predictors provide output having the same form as the measurements regarding the scene characteristics.

59. An apparatus as set forth in claim 58, wherein in the operation of rendering, for each renderer, there is an average of at least one predictor.

60. An apparatus as set forth in claim 58, wherein for each predictor, there is an average of more than one renderer.

61. An apparatus as set forth in claim 55, wherein the means for comparing operates by performing a simple weighted summing of value differences between the predicted future state and the new set of measurements.

62. An apparatus as set forth in claim 35, wherein the operation of comparing is performed by a simple weighted summing of value differences between the predicted future state and the new set of measurements.

63. An apparatus as set forth in claim 62, wherein the predictors are configured with a variety of prediction models, having a variety of processing speeds and a variety of qualities, so that a variety of predicted future states is available; whereby different models may be used depending on the speed and quality of prediction necessary.

64. An apparatus as set forth in claim 62, wherein the predictors are configured to predict all possible future states and wherein the renderers are configured to render all possible future states.

65. An apparatus as set forth in claim 35, wherein in the operation of predicting each predictor includes multiple prediction models along with a model that models a likelihood of each of the other models being accurate, and where the apparatus further comprises a means for selecting the model having a greatest likelihood of being accurate, and wherein the means for predicting uses the model having the greatest likelihood of being accurate.

66. An apparatus as set forth in claim 35, wherein in the operation of comparing, a comparator is biased based on a combination of at least one biasing parameter selected from a group consisting of user-specified preferences, system-derived preferences, and a belief network in a predictor.

67. An apparatus as set forth in claim 35, wherein the operation of selecting is performed by a switch configured to select a plurality of images for display in an environment selected from multi-image display environments and multi-user environments with multiple displays.

68. An apparatus as set forth in claim 35, wherein the operation of predicting, the operation of comparing, the operation of rendering, and the operation of switching are performed competitively as operations in a self-optimizing process subject to the following constraint:


Δtd+Δtp+Δtr+Δtc+Δts=Tp, where:

Tp=total prediction time;
Δtd=average time between data updates;
Δtp=average time to perform one prediction;
Δtr=average time to render one scene;
Δtc=average time to compare all predicted states with the current state; and
Δts=average time to switch between one candidate image and another.

69. A computer program product for parallel speculative rendering of synthetic images in an image rendering system having stored on a computer-readable medium, means for performing operations of:
obtaining measurements regarding scene characteristics;
providing the measurements to a plurality of predictors;
predicting, at each of the predictors, a future state for each of the measurements;
providing the future states to a plurality of renderers;
rendering, at each renderer, graphical entities such that each rendering results from a different predicted future state;
obtaining a new set of measurements regarding the scene characteristics;
comparing, at a comparator, each one of the new set of measurements with a corresponding one of the predicted future states produced by the predictors;
determining which predicted future state most closely matches with the new measurements;
selecting, at a switch, graphical entities associated with the predicted future state that most closely matches with the new measurements; and
displaying the selected graphical entities on a display device;
wherein providing the measurements to a plurality of predictors, the predictors are arranged in a hierarchical fashion having higher-level predictors and leaf-level predictors, and wherein predicting, the higher-level predictors predict at a faster rate than the leaf-level predictors.

70. A computer program product as set forth in claim 69, wherein a plurality of predicting, providing, and rendering operations are performed by a plurality of means for predicting, providing, and rendering, with each sequence of predicting, providing, and rendering operations performed substantially in parallel with respect to the others.

71. A computer program product as set forth in claim 70, wherein the parallel sequences of predicting, providing, and rendering operations are performed asynchronously with respect to each other.

72. A computer program product as set forth in claim 71, wherein the measurements are obtained from at least two sensors with each sensor selected from a group consisting of magnetic sensors, video sensors, position sensors, inertial sensors, databases, and computer networks.

73. A computer program product as set forth in claim 72, wherein each operation of predicting is performed by predictors having a configuration selected from a group consisting of Kalman filters, sudden-stop and sudden-start models, and behavioral and physical models.

74. A computer program product as set forth in claim 73, wherein the predictors predict values at a common future time.

75. A computer program product as set forth in claim 74, wherein at least two predictors have the same configuration, and wherein the predictors produce output based on differing assumptions.

76. A computer program product as set forth in claim 75, wherein the predictors provide output having the same form as the measurements regarding the scene characteristics.

77. A computer program product as set forth in claim 76, wherein in the operation of rendering, for each renderer, there is an average of at least one predictor.

78. A computer program product as set forth in claim 77, wherein the operation of comparing is performed by a simple weighted summing of value differences between the predicted future state and the new set of measurements.

79. A computer program product as set forth in claim 78, wherein in the operation of predicting each predictor includes multiple prediction models along with a model that models a likelihood of each of the other models being accurate, and where the computer product further comprises a operation of selecting the model having a greatest likelihood of being accurate, and wherein the predicting operation is performed using the model having the greatest likelihood of being accurate.

80. A computer program product as set forth in claim 79, wherein in the operation of comparing, a comparator is biased based on a combination of at least one biasing parameter selected from a group consisting of user-specified preferences, system-derived preferences, and a belief network in a predictor.

81. A computer program product as set forth in claim 80, wherein the operation of selecting is performed by a switch configured to select a plurality of images for display in an environment selected from multi-image display environments and multi-user environments with multiple displays.

82. A computer program product as set forth in claim 81, wherein the operation of predicting, the operation of comparing, the operation of rendering, and the operation of switching are performed competitively as operations in a self-optimizing process subject to the following constraint:


Δtd+Δtp+Δtr+Δtc+Δts=Tp, where:

Tp=total prediction time;
Δtd=average time between data updates;
Δtp=average time to perform one prediction;
Δtr=average time to render one scene;
Δtc=average time to compare all predicted states with the current state; and
Δts=average time to switch between one candidate image and another.

83. A computer program product as set forth in claim 78, wherein the predictors are configured to predict all possible future states and wherein the renderers are configured to render all possible future states.

84. A computer program product as set forth in claim 78, wherein the predictors are configured with a variety of prediction models, having a variety of processing speeds and a variety of qualities, so that a variety of predicted future states is available; whereby different models may be used
depending on the speed and quality of prediction necessary.

85. A computer program product as set forth in claim 76, wherein for each predictor, there is an average of more than one renderer.

86. A computer program product as set forth in claim 73, wherein the predictors predict values at different future times.

87. A computer program product as set forth in claim 70, wherein the parallel sequences of predicting, providing, and rendering operations are performed synchronously with respect to each other.

88. A computer program product as set forth in claim 69, wherein the measurements are obtained from at least two sensors with each sensor selected from a group consisting of magnetic sensors, video sensors, position sensors, inertial sensors, databases, and computer networks.

89. A computer program product as set forth in claim 69, wherein each operation of predicting is performed by predictors having a configuration selected from a group consisting of Kalman filters, sudden-stop and sudden-start models, and behavioral and physical models

90. A computer program product as set forth in claim 89, wherein the predictors predict values at a common future time.

91. A computer program product as set forth in claim 90, wherein at least two predictors have the same configuration, and wherein the predictors produce output based on differing assumptions.

92. A computer program product as set forth in claim 91, wherein the predictors provide output having the same form as the measurements regarding the scene characteristics.

93. A computer program product as set forth in claim 92, wherein in the operation of rendering, for each renderer, there is an average of at least one predictor.

94. A computer program product as set forth in claim 92, wherein for each predictor, there is an average of more than one renderer.

95. A computer program product as set forth in claim 89, wherein the operation of comparing is performed by a simple weighted summing of value differences between the predicted future state and the new set of measurements.

96. A computer program product as set forth in claim 69, wherein the operation of comparing is performed by a simple weighted summing of value differences between the predicted future state and the new set of measurements.

97. A computer program product as set forth in claim 96, wherein the predictors are configured with a variety of prediction models, having a variety of processing speeds and a variety of qualities, so that a variety of predicted future states is available; whereby different models may be used depending on the speed and quality of prediction necessary.

98. A computer program product as set forth in claim 96, wherein the predictors are configured to predict all possible future states and wherein the renderers are configured to render all possible future states.

99. A computer program product as set forth in claim 69, wherein in the operation of predicting each predictor includes multiple prediction models along with a model that models a likelihood of each of the other models being accurate, and where the computer program product further comprises a operation of selecting the model having a greatest likelihood of being accurate, and wherein the predicting operation is performed using the model having the greatest likelihood of being accurate.

100. A computer program product as set forth in claim 69, wherein in the operation of comparing, a comparator is biased based on a combination of at least one biasing parameter selected from a group consisting of user-specified preferences, system-derived preferences, and a belief network in a predictor.

101. A computer program product as set forth in claim 69, wherein the operation of selecting is performed by a switch configured to select a plurality of images for display in an environment selected from multi-image display environments and multi-user environments with multiple displays.

102. A computer program product as set forth in claim 69, wherein the operation of predicting, the operation of comparing, the operation of rendering, and the operation of switching are performed competitively as operations in a self-optimizing process subject to the following constraint:


Δtd+Δtp+Δtr+Δtc+Δts=Tp, where:

Tp=total prediction time;
Δtd=average time between data updates;
Δtp=average time to perform one prediction;
Δtr=average time to render one scene;
Δtc=average time to compare all predicted states with the current state; and
Δts=average time to switch between one candidate image and another.