Decision-theoretic regulation for allocating computational resources among components of multimedia content to improve fidelity

• US 6,232,974 B1
• Filed: 07/30/1997
• Issued: 05/15/2001
• Est. Priority Date: 07/30/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Horvitz, Eric, Lengyel, Jerome E.
• Primary Examiner(s): Hong, Stephen S.
• Assistant Examiner(s): Bashore, William L.
• Application Number:
  US08/904,966
• Time in Patent Office: 1,385 Days
• Field of Search: 345/302, 345/419, 345/433, 345/420, 345/502, 345/428, 345/473, 345/522, 358/1.2, 358/456, 382/229, 382/167
• US Class Current: 345/419
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06T 15/00 3D [Three Dimensional] image rendering

Abstract

A decision-theoretic regulator employs a method for allocating computational resources to components of media content to create the highest quality output for a budget of rendering resources. The components of the content represent parts of the content that have independent quality parameters that the regulator can vary to trade-off quality for computational savings. For example, in multimedia content, the components might be objects in a 3D graphics scene. The method allocates computational resources by attempting to minimize the total expected cost of a rendering task. The method computes the raw error for a rendering action on a component and then maps the raw error to a perceived error based on empirical evidence of how users perceive errors in rendered output. The expected cost is computed from the perceived error or raw error by applying a model of attention that gives the probability that a user is focusing his or her attention on a component. The method minimizes the total expected cost by selecting a rendering action for each component that yields the lowest expected cost for a given rendering budget.

Claims

1. A method for regulating computational resources needed to present renderable content, where the renderable content is divided into a plurality of components, and a computational rendering budget is designated for rendering the renderable content, the method comprising:

computing perceived cost of a rendering action and assessing computational cost of the rendering action for each of the plurality of components, wherein the perceived cost reflects perceived quality due to performing the rendering action for the component, and the computational cost reflects computing resources required to perform the rendering action for the component;

designating an expected perceptual cost for the rendering actions by applying a model of a user'"'"'s attention to the perceived cost reflecting perceived quality due to performing the rendering action for the component, wherein the model of attention specifies a probability that a component has a degree of a user'"'"'s attention;

based on the computational rendering budget, selecting a rendering action from at least two possible rendering actions for each of the plurality of components to minimize total expected perceptual cost of rendered output representing the plurality of components and to fit total computational cost of the selected rendering actions within the computational rendering budget, wherein the total expected perceptual cost is determined by combining the expected perceptual costs for the selected actions, and the total computational cost of the selected rendering actions is determined by combining the computational costs of the selected actions; and

transferring the selected rendering actions to a rendering system to render the plurality of the components by performing the selected rendering actions.

2. The method of claim 1 wherein computing the perceived cost comprises:

computing the raw error of a rendering action on the component that degrades fidelity of the component in exchange for saving computational resources; and

mapping the raw error to the perceived cost using a mapping function that maps raw error values to perceived cost values based on empirical evidence of how users perceive errors in output images associated with the rendering actions on the components.

3. The method of claim 2 wherein each component is a portion of object geometry of a scene that is rendered into an image layer, and

the raw error is a geometric error associated with warping the image layer to approximate motion of object geometry represented in the image layer.

4. The method of claim 1 wherein the renderable content comprises an animation sequence and the perceived cost of a component for a current frame in the animation sequence is a function of the raw error of the component as computed for a plurality of frames in the animation sequence.

5. The method of claim 1 wherein the perceived cost of a component is measured as the raw error of the component caused by degrading spatial resolution or temporal resolution of the component, where the temporal resolution is defined as a rate at which the object geometry of the component is re-rendered, and where the spatial resolution is the spatial resolution of a 2D image rendering of the component.

6. The method of claim 1 wherein each component is a portion of an object geometry of a scene that is rendered into an image layer;

and wherein the selecting includes dynamically changing the temporal or spatial resolution of the image layer to trade-off fidelity of the image layer for computational cost of the image layer.

7. The method of claim 1 wherein each component is a portion of an object geometry of a scene that is rendered into an image layer;

and wherein the model of attention gives a probability that a user is attending to the portion of the object geometry of the scene that is rendered to the image layer.

8. The method of claim 7 wherein the model of attention classifies objects in a scene into different categories, each with an associated probability that a user is attending to an object of a particular category.

9. The method of claim 7 wherein each component is a portion of the object geometry of the scene that is rendered into an image layer, and wherein selecting a rendering action comprises:

sorting the components in the scene based on a cost-benefit ratio of each component, where the cost-benefit ratio represents the ratio of a marginal expected perceptual cost designated by applying a model of a user'"'"'s attention and due to an image warp approximation of a component to the computation cost associated with the image warp approximation, where the computational cost associated with the image warp approximation approximates cost savings of the image warp approximation; and

scheduling components for re-rendering in the order of the cost benefit ratio such that the image layers with the largest impact on perceived quality are re-rendered within the budget and other image layers are warped to approximate the position of object geometry in a current frame.

10. The method of claim 9 wherein scheduling components includes refining the order of the cost-benefit ratio by adjusting spatial resolution of one or more components to save computational resources so that one or more components can be re-rendered within the budget.

11. The method of claim 1 wherein the model of attention includes performing a Bayesian analysis to determine probability that a user is attending to each of the components in the scene.

12. The method of claim 1 wherein the selecting includes performing an optimization on k rendering actions for each component to find a rendering action for each component such that total perceptual cost is minimized for the budget of computational resources available for a current frame.

13. A computer readable medium on which is stored instructions for performing the method of claim 1.

27. The method of claim 1 wherein the two possible rendering actions are re-rendering a component and warping a previous rendering of a component.

28. The method of claim 1 wherein the computational budget is variable between successive renderings of the renderable content.

29. The method of claim 1 wherein the model of attention specifies a probability that a component has an entire amount of the user'"'"'s attention.

30. The method of claim 1 wherein the model of attention specifies a random variable representing an amount of user'"'"'s attention for a component.

31. The method of claim 30 wherein the probabilities are numerical ratings.

14. A method for regulating the use of resources for rendering media content based on a computational budget, the method comprising:

dividing the media content into components, where each of the components has at least two possible rendering actions, each with different computational costs, that will convert the component into a format suitable for presentation;

computing a raw error for performing each rendering action for each component for a current frame of the media content;

determining the probability that a user is attending to each of the components of the current frame;

determining the expected cost of rendering a component using each of the rendering actions, where the expected cost is a function of the raw error of the rendering action and the probability that the user is attending to the component representing part of the current frame; and

based on the computational budget, regulating use of rendering resources by selecting rendering actions for each of the components such that expected cost is minimized and total computational cost of rendering the frame is within the computational budget.

15. The method of claim 14 wherein the expected cost of each component is a function of a perceived cost and the probability that a user is attending to the component;

and further including;

computing the perceived cost for each component by mapping the raw error to a perceived cost based on a perceived cost map that gives a perceived cost value for a raw error value based on empirical data representing the extent to which users perceive the raw error of an associated rendering action.

16. A computer readable medium on which is stored instructions for performing the method of claim 14.

17. A method for regulating the use of resources for rendering media content, the method comprising:

dividing the media content into components, where each of the components has at least two rendering actions, each with different computational costs, that will convert the component into a format suitable for presentation;

computing a raw error of each rendering action for each component for a current frame;

computing the perceived cost for each component by mapping the raw error to a perceived cost based on a perceived cost map that gives a perceived cost value for a raw error value based on empirical data representing the extent to which users perceive the raw error;

combining the perceived costs into a total perceived cost based on the empirical data and reflecting the extent to which users perceive the raw errors; and

regulating use of rendering resources by selecting rendering actions for each of the components such that total perceived cost based on the empirical data and reflecting the extent to which users perceive the raw errors is minimized and total computational cost of rendering the frame is within a budget.

18. A computer readable medium on which is stored instructions for performing the method of claim 17.

32. The method of claim 17 wherein the frame is an animation frame and the components represent objects displayed in the animation.

19. In a pre-processor for a layered graphics rendering pipeline, a method for allocating computational resources to components of a frame of animation in an animation sequence, where each component is a portion of object geometry of a scene that is rendered into an image layer, the method comprising:

computing the raw error of a rendering action on the component that degrades fidelity of the image layer of the component in exchange for saving computational resources;

mapping the raw error to a perceived cost using a mapping function that maps raw error values to perceived cost values based on empirical evidence of how users perceive errors in output images associated with the rendering actions on the components;

determining the expected cost of rendering each component by applying a model of a user'"'"'s attention to the perceived cost of each component, where the model of attention gives a probability that a user is attending to a component;

evaluating a total expected perceptual cost of an output image incorporating perceived cost values based on empirical evidence of how users perceive errors and the model of a user'"'"'s attention giving a probability that a user is attending to a component;

based on a rendering budget, selecting a rendering action between at least two rendering actions for each component to minimize the total expected perceptual cost of an output image incorporating perceived cost values based on empirical evidence of how users perceive errors and the model of a user'"'"'s attention giving a probability that a user is attending to a component, such that total computational cost of the selected rendering actions its within the rendering budget;

transferring the selected rendering actions to a rendering system to render the scene into an output image; and

repeating the above to select the rendering actions for subsequent output images in a sequence of animation.

20. A computer-implemented method for regulating computing resources applied to rendering a frame of a multimedia presentation, wherein the frame of the multimedia presentation comprises a plurality of components to be rendered for presentation to a user, wherein a computational budget is provided for rendering the frame of the multimedia presentation, the method comprising:

for the components to be rendered, determining a probability that the component to be rendered has an amount of the user'"'"'s attention;

for the components to be rendered, designating computational costs for at least two possible actions that will render the component for presentation and calculating a raw error of the possible actions;

for the frame, designating a quality-based rating incorporating a combination of the components'"'"' probability that an amount of the user'"'"'s attention is had by the components and the components'"'"' raw errors; and

based on the computational budget, selecting actions for each of the components to optimize the frame'"'"'s quality-based rating incorporating the combination of the components'"'"' probability that an amount of the user'"'"'s attention is had by the components and the components'"'"' raw errors, while keeping total computational costs for the components of the frame within the computational budget.

21. The method of claim 20 wherein the at least two actions comprise re-rendering a component and re-using a previous rendering of a component.

22. The method of claim 20 wherein the at least two actions comprise re-rendering a component and warping a previous rendering of a component.

23. The method of claim 20 wherein the probability indicates a likelihood that a component has an entire amount of the user'"'"'s attention.

24. The method of claim 20 wherein the probability is a random variable representing, an amount of user'"'"'s attention for a component.

25. A computer-implemented method for regulating computing resources applied to rendering a frame of a multimedia presentation, wherein the frame of the multimedia presentation comprises a plurality of components to be rendered for presentation to a user, wherein a computational budget is provided for rendering the frame of the multimedia presentation, the method comprising:

for the components to be rendered, designating a probability distribution indicating probabilities of a plurality of states for one or more random variables associated with the user'"'"'s perception of the component;

for the components to be rendered, designating computational costs for at least two possible actions that will render the component for presentation and calculating a raw error of the possible actions;

for the frame, designating a quality-based rating incorporating a combination of the components'"'"' raw errors and calculated probability-based expectations of states of the one or more random variables associated with the user'"'"'s perception of quality of a rendered version of the component; and

based on the computational budget, selecting actions for each of the components to optimize the frame'"'"'s quality-based rating incorporating the combination of the components'"'"' raw errors and calculated probability-based expectations of states of the one or more random variable associated with the user'"'"'s perception of quality of a rendered version of the component, while keeping total computational costs for the components of the frame within the computational budget.

26. A computer-implemented method for regulating computing resources applied to rendering a frame of a multimedia presentation, wherein the frame of the multimedia presentation comprises a plurality of components to be rendered for presentation to a user, wherein a computational budget is provided for rendering the frame of the multimedia presentation, the method comprising:

for the components to be rendered, designating a probability distribution indicating probabilities of a plurality of states for one or more random variables associated with the user'"'"'s perception of the component;

for the components to be rendered, designating computational costs for at least two possible actions that will render the component for presentation and calculating a raw perceptual error of the possible actions;

for the frame, designating a quality-based expected perceptual cost by considering, for each random variable, a summation of the product of the raw perceptual errors with the probability of each state of the random variable; and

based on the computational budget, selecting actions for each of the components to optimize the frame'"'"'s quality-based expected perceptual cost, while keeping total computational costs for the components of the frame within the computational budget.