Geometric Work Scheduling with Dynamic and Probabilistic Work Trimming

• US 20170287185A1
• Filed: 06/24/2016
• Published: 10/05/2017
• Est. Priority Date: 03/31/2016
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Kumar, Tushar, Jia, Wenhao, Raman, Arun, Chao, Hui, Ruan, Wenjia
• Granted Patent: US 10,325,390 B2
• Time in Patent Office: Days
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 19/006 Mixed reality object pose determination, tracking or camera calibration for mixed reality G06T7/00
• CPC Class Codes: G06T 3/4038 Image mosaicing, e.g. composing plane images from plane sub-images
• CPC Class Codes: G06T 7/33 using feature-based methods
• CPC Class Codes: H04N 23/64 Computer-aided capture of images, e.g. transfer from script file into camera, check of taken image quality, advice or proposal for image composition or decision on when to take image
• CPC Class Codes: H04N 23/698 for achieving an enlarged field of view, e.g. panoramic image capture

Abstract

Various embodiments may include methods executed by processors of computing devices for geometry based work execution prioritization. The processor may receive events, such as images. The processor may overlay a boundary shape on the event to identify discard regions of the event lying outside the boundary shape. The processor may identify work regions of the events lying within the working boundary shape. The devices may determine a cancellation likelihood for each of the identified work regions of the events. The processor may assign a trimming weight to each of the identified work regions based on the determined cancellation likelihoods. The processor may then add each of the identified work regions as a work item to an execution work list in an order based on the assigned trimming weights. The work items may be processed in order of trimming weight priority.

Claims

1. A method for geometry based work execution prioritization on a computing device, comprising:

obtaining, by a processor of the computing device, a first image;

overlaying, by the processor, a default boundary shape on the first image to initialize a working boundary shape and identify a discard region lying outside the working boundary shape;

identifying, by the processor, work regions lying within the working boundary shape;

determining, by the processor, a cancellation likelihood for each of the identified work regions;

determining, by the processor, a trimming weight for each of the identified work regions using the cancellation likelihoods; and

adding, by the processor, work items associated with each of the identified work regions to an execution work list in an order based, at least in part, on the determined trimming weights.

2. The method of claim 1, further comprising:

obtaining, by the processor, a second image;

updating, by the processor, a position of the working boundary shape;

overlaying, by the processor, the updated working boundary shape on the second image to identify updates to the discard region lying outside the updated working boundary shape;

determining, by the processor, whether any work items are associated with work regions that overlap the discard region;

cancelling, by the processor, a work item in response to determining that the work item overlaps the discard region;

updating, by the processor, the work regions lying within the updated working boundary shape;

determining, by the processor, a cancellation likelihood for each of the updated work regions;

determining, by the processor, a trimming weight to each of the identified work regions based, at least in part, on the cancellation likelihoods; and

adding, by the processor, work items associated with each of the identified work regions to the execution work list in an order based, at least in part, on the determined trimming weights.

3. The method of claim 2, wherein determining the cancellation likelihood for each of the updated work regions comprises:

determining, by the processor, a direction in which a focus of the obtained images is moving; and

determining, by the processor, the cancellation likelihood based, at least in part, on the determined direction of motion.

4. The method of claim 3, wherein cancellation likelihoods are determined such that a likelihood of cancellation for the work regions lying closest to a direction of motion is less than the cancellation likelihood for the work regions lying furthest from the direction of motion.

5. The method of claim 2, further comprising:

generating, by the processor, a composite image from portions of each obtained image that lie within a final updated working boundary shape.

6. The method of claim 5, wherein the composite image is a panorama.

7. The method of claim 5, wherein the composite image is a virtual reality rendering.

8. The method of claim 1, further comprising:

redetermining, by the processor, the cancellation likelihood of each of the work regions based, at least in part, on a comparison of a position of an overlay of the updated working boundary shape on the first image to the position of the overlay of the working boundary shape;

determining, by the processor, updated trimming weights for the work regions based, at least in part, on the cancellation likelihoods; and

adjusting, by the processor, an order of the work items in the execution work list based, at least in part, on the updated trimming weights determined for the work items in the execution work list.

9. The method of claim 1, further comprising:

determining, by the processor, a work score for each work item in the execution work list; and

determining, by the processor, a work item to execute on a second processor based on the work score,

wherein the work score is determined based, at least in part, on one or more of the determined trimming weight of the work item, a size of the work item, a shape of the work item, and commonality of processing elements with other work items.

10. The method of claim 9, further comprising determining, by the processor, a work score for each work item in the execution work list, for every processor of the computing device, such that each work item has multiple work scores indicating processing suitability with regard to each processing unit.

11. The method of claim 9, wherein determining a work score for each work item, in the execution work list is further based, at least in part, on at least one member selected from the group consisting of a launch overhead for the work item;

a battery exhaustion associated with processing the work item, ease of cancelling the work item, and utilization of the processor.

12. The method of claim 1, wherein the cancellation likelihood is based, at least in part, on a distance of a work region from a center of an image.

13. The method of claim 1, wherein determining the cancellation likelihood for each of the identified work regions comprises:

determining, by the processor, a timeout duration; and

determining, by the processor, a likelihood that a subsequent image will not lie within a work region for a period exceeding the timeout duration.

14. The method of claim 13, wherein determining, by the processor, the likelihood that a subsequent image will not lie within the work region for a period exceeding the timeout duration comprises executing one or more Kalman filters, to predict a position of the subsequent image.

15. The method of claim 1, wherein there are multiple working boundary shapes.

16. The method of claim 1, wherein the first image is a viewport of a virtual reality view space.

17. The method of claim 2, wherein updating the work regions lying within the updated working boundary shape comprises:

identifying, by the processor, one or more new work regions lying within the updated working boundary shape; and

changing, by the processor, boundaries of the work regions to fit within the updated working boundary shape.

18. A computing device configured for geometry based work execution prioritization, comprising:

one or more processors configured to;

obtain a first image;

overlay a default boundary shape on the first image to initialize a working boundary shape and identify a discard region lying outside the working boundary shape;

identify work regions lying within the working boundary shape;

determine a cancellation likelihood for each of the identified work regions;

determine a trimming weight for each of the identified work regions using the cancellation likelihoods; and

add work items associated with each of the identified work regions to an execution work list in an order, at least in part, on the determined trimming weights.

19. The computing device of claim 18, wherein the one or more processors are further configured to:

obtain a second image;

update a position of the working boundary shape;

overlay the updated working boundary shape on the second image to identify updates to the discard region lying outside the updated working boundary shape;

determine whether any work items are associated with work regions that overlap the discard region;

cancel a work item in response to determining that the work item overlaps the discard region;

update the work regions lying within the updated working boundary shape;

determine a cancellation likelihood for each of the updated work regions;

determine a trimming weight for each of the identified work regions based, at least in part, on the cancellation likelihoods; and

add work items associated with each of the identified work regions to the execution work list in an order based, at least in part, on the determined trimming weights.

20. The computing device of claim 19, wherein the one or more processors are further configured to determine the cancellation likelihood for each of the updated work regions by:

determining a direction in which a focus of the obtained images is moving; and

determining the cancellation likelihood based, at least in part, on the determined direction of motion.

21. The computing device of claim 20, wherein the one or more processors are further configured to determine the cancellation likelihoods such that a likelihood of cancellation for the work regions lying closest to a direction of motion is less than the cancellation likelihood for the work regions lying furthest from the direction of motion.

22. The computing device of claim 19, wherein the one or more processors are further configured to:

generate a composite image from portions of each obtained image that lie within a final updated working boundary shape.

23. The computing device of claim 18, wherein the one or more processors are further configured to:

redetermine the cancellation likelihood of each of the work regions based, at least in part, on a comparison of a position of an overlay of the updated working boundary shape on the first image to the position of the overlay of the working boundary shape;

determine updated trimming weights for the work regions based, at least in part, on the redetermined cancellation likelihoods; and

adjust an order of the work items in the execution work list based, at least in part, on the updated trimming weights determined for the work items in the execution work list.

24. The computing device of claim 18, wherein the one or more processors are further configured to:

determine a work score for each work item in the execution work list; and

determine a work item to execute on a second processor based, at least in part, on the determined work score,

wherein the work score is determined based, at least in part, on one or more of the determined trimming weight of the work item, a size of the work item, a shape of the work item, and commonality of processing elements with other work items.

25. The computing device of claim 24, wherein the one or more processors are further configured to determine a work score for each work item in the execution work list, for every processor of the computing device, such that each work item has multiple work scores indicating processing suitability with regard to each processing unit.

26. The computing device of claim 18, wherein the one or more processors are further configured to determine the cancellation likelihood for each of the identified work regions by:

determining a timeout duration; and

determining a likelihood that a subsequent image will not lie within a work region for a period exceeding the timeout duration.

27. The computing device of claim 19, wherein the one or more processors are further configured to update the work regions lying within the updated working boundary shape by:

identifying one or more new work regions lying within the updated working boundary shape; and

changing boundaries of the work regions to fit within the updated working boundary shape.

28. A computing device configured for geometry based work execution prioritization on a comprising:

means for obtaining a first image;

means for overlay a default boundary shape on the first image to initialize a working boundary shape and identify a discard region lying outside the working boundary shape;

means for identifying work regions lying within the working boundary shape;

means for determining a cancellation likelihood for each of the identified work regions;

means for determining a trimming weight for each of the identified work regions using the cancellation likelihoods; and

means for adding work items associated with each of the identified work regions to an execution work list in an order based, at least in part, on the determined trimming weights.

29. A non-transitory processor readable medium having stored thereon processor executable instructions causing a processor to perform operations for geometry based work execution prioritization, comprising:

obtaining a first image;

overlaying a default boundary shape on the first image to initialize a working boundary shape and identify a discard region lying outside the working boundary shape;

identifying work regions lying within the working boundary shape;

determining a cancellation likelihood for each of the identified work regions;

determining a trimming weight to each of the identified work regions using the cancellation likelihoods; and

adding work items associated with each of the identified work regions to an execution work list in an order based, at least in part, on the determined trimming weights.

30. The non-transitory processor readable medium of claim 29, having stored thereon processor executable instructions causing the processor to perform operations further comprising:

obtaining a second image;

updating a position of the working boundary shape;

overlaying the updated working boundary shape on the second image to identify updates to the discard region lying outside the updated working boundary shape;

determining whether any work items are associated with work regions that overlap the discard region;

cancelling a work item in response to determining that the work item overlaps the discard region;

updating the work regions lying within the updated working boundary shape;

determining a cancellation likelihood for each of the updated work regions;

determining a trimming weight to each for the identified work regions based, at least in part, on the cancellation likelihoods; and

adding work items associated with each of the identified work regions to the execution work list in an order based, at least in part, on the determined trimming weights.