Live video analytics at scale

• US 10,223,604 B2
• Filed: 12/08/2016
• Issued: 03/05/2019
• Est. Priority Date: 11/06/2016
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Bahl, Paramvir, Bodik, Peter, Philipose, Matthai, Ananthanarayanan, Ganesh, Zhang, Haoyu
• Primary Examiner(s): Johns, Andrew W
• Application Number:
  US15/373,301
• Publication Number:
  US 20180129892A1
• Time in Patent Office: 817 Days
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: G06V 10/95 structured as a network, e.g. client-server architectures
• CPC Class Codes: G06V 10/96 Management of image or video recognition tasks
• CPC Class Codes: G06V 20/40 in video content extracting overlay text G06V20/62; video retrieval G06F16/70; processing of video elementary streams in video servers H04N21/234; processing of video elementary streams in video clients H04N21/44
• CPC Class Codes: G06V 20/44 Event detection
• CPC Class Codes: G06V 20/52 Surveillance or monitoring of activities, e.g. for recognising suspicious objects recognising microscopic objects G06V20/69
• CPC Class Codes: G06V 20/54 of traffic, e.g. cars on the road, trains or boats
• CPC Class Codes: G06V 40/178 estimating age from face image; using age information for improving recognition
• CPC Class Codes: H04N 21/23418 involving operations for analysing video streams, e.g. detecting features or characteristics television picture signal circuitry for scene change detection H04N5/147; filtering for image enhancement G06T5/00; methods or arrangements for recognising scenes G06V20/00; arrangements characterised by components specially adapted for monitoring, identification or recognition of video in broadcast systems H04H60/59
• CPC Class Codes: H04N 7/181 for receiving images from a plurality of remote sources

Abstract

Various technologies described herein pertain to performing video analytics. The approaches set forth herein support live video analytics at scale with approximate and delay-tolerant processing. Video streams can be captured by multiple cameras and continuously streamed to a video analytics computing system; the video streams can be received at the video analytics computing system. Multiple video analytics queries can be executed on the video streams. The multiple video analytics queries can be concurrently executed by the video analytics computing system on the video streams as the video streams are continuously streamed to the video analytics computing system. The multiple video analytics queries can be executed utilizing resources of the video analytics computing system allocated between the multiple video analytics queries. Execution of the multiple video analytics queries can return respective results for the multiple video analytics queries. The results for the multiple video analytics queries can be outputted.

Claims

1. A method of performing video analytics, comprising:

receiving video streams at a video analytics computing system, the video streams being captured by multiple cameras and continuously streamed to the video analytics computing system;

scheduling multiple video analytics queries, wherein scheduling the multiple video analytics queries further comprises;

allocating resources of the video analytics computing system between the multiple video analytics queries for the execution of each of the multiple video analytics queries; and

selecting multi-dimensional configurations for each of the multiple video analytics queries based on the resources as allocated;

executing the multiple video analytics queries on the video streams, the multiple video analytics queries concurrently being executed by the video analytics computing system on the video streams as the video streams are continuously streamed to the video analytics computing system, the multiple video analytics queries being executed utilizing the resources of the video analytics computing system allocated between the multiple video analytics queries, and execution of the multiple video analytics queries returns respective results for the multiple video analytics queries; and

outputting the results for the multiple video analytics queries.

2. The method of claim 1, wherein scheduling the multiple video analytics queries further comprises:

placing the multiple video analytics queries on worker computing devices of the video analytics computing system for the execution of the multiple video analytics queries.

3. The method of claim 1, wherein the multiple video analytics queries are scheduled jointly based on resource-quality profiles of the multiple video analytics queries and lag tolerances of the multiple video analytics queries.

4. The method of claim 3, further comprising:

generating a resource-quality profile of a particular video analytics query, the resource-quality profile specifies resource demands and result qualities corresponding to candidate multi-dimensional configurations of the particular video analytics query.

5. The method of claim 4, wherein generating the resource-quality profile of the particular video analytics query further comprises:

identifying the candidate multi-dimensional configurations utilizing a greedy local search in a resource-quality space, the candidate multi-dimensional configurations being a subset of potential multi-dimensional configurations, and the candidate multi-dimensional configurations being on a Pareto boundary.

6. The method of claim 4, further comprising:

tracking a misestimation of the resource demands specified in the resource-quality profile of the particular video analytics query during execution of the particular video analytics query over time;

wherein the particular video analytics query is further scheduled based on the misestimation.

7. The method of claim 3, further comprising periodically adjusting the scheduling of the multiple video analytics queries over time based on changes in resource demands across the multiple video analytics queries and resource capacity of the video analytics computing system.

8. The method of claim 3, further comprising:

predicting lags of the multiple video analytics queries over a time horizon;

wherein the multiple video analytics queries are further scheduled based on the predicted lags.

9. The method of claim 1, wherein a video analytics query is specified as a graph of transforms applied to at least one of the video streams, and wherein a video frame in the at least one of the video streams is sequentially processed by the transforms such that corresponding outputs of the transforms are passed downstream.

10. The method of claim 9, wherein:

the transforms comprise at least a first transform and a second transform;

the first transform is placed on a first worker computing device of the video analytics computing system for execution; and

the second transform is placed on a second worker computing device of the video analytics computing system for execution.

11. The method of claim 1, wherein the resources of the video analytics computing system are allocated between the multiple video analytics queries for the execution of each of the multiple video analytics queries based on:

utilities of the multiple video analytics queries, wherein the utilities are based on achieved result quality and lag of the multiple video analytics queries; and

a scheduling objective for the video analytics computing system.

12. The method of claim 11, wherein the resources are allocated utilizing a scheduling heuristic for one of maximizing a minimum utility or maximizing a total utility.

13. The method of claim 1, further comprising:

migrating a particular video analytics query between worker computing devices of the video analytics computing system for execution of the particular video analytics query.

14. A video analytics computing system, comprising:

at least one processor; and

memory that comprises computer-executable instructions that, when executed by the at least one processor, cause the at least one processor to perform acts including;

allocating resources of the video analytics computing system between multiple video analytics queries for execution of each of the multiple video analytics queries, the resources of the video analytics computing system are allocated based on resource-quality profiles of the multiple video analytics queries and lag tolerances of the multiple video analytics queries, the multiple video analytics queries concurrently being executed by the video analytics computing system on video streams as the video streams are streamed to the video analytics computing system from multiple camera; and

selecting multi-dimensional configurations for each of the multiple video analytics queries based on the resources as allocated, the multiple video analytics queries being executed utilizing the multi-dimensional configurations.

15. The video analytics computing system of claim 14, the memory further comprising computer-executable instructions that, when executed by the at least one processor, cause the at least one processor to perform acts including:

placing the multiple video analytics queries on worker computing devices of the video analytics computing system for the execution of the multiple video analytics queries.

16. A method of performing video analytics, comprising:

receiving video streams at a video analytics computing system, the video streams being captured by multiple cameras and continuously streamed to the video analytics computing system;

scheduling multiple video analytics queries, wherein the scheduling of the video analytics queries is periodically adjusted over time based on changes in resource demands across the multiple video analytics queries and resource capacity of the video analytics computing system;

executing the multiple video analytics queries on the video streams as scheduled, the multiple video analytics queries concurrently being executed by the video analytics computing system on the video streams as the video streams are continuously streamed to the video analytics computing system, the multiple video analytics queries being executed utilizing resources of the video analytics computing system allocated between the multiple video analytics queries, and execution of the multiple video analytics queries returns respective results for the multiple video analytics queries; and

outputting the results for the multiple video analytics queries.

17. The method of claim 16, wherein scheduling the multiple video analytics queries further comprises:

allocating the resources of the video analytics system between the multiple video analytics queries for the execution of each of the multiple video analytics queries; and

selecting multi-dimensional configurations for each of the multiple video analytics queries based on the resources as allocated.

18. The method of claim 16, wherein the resources of the video analytics computing system are allocated based on resource-quality profiles of the multiple video analytics queries and lag tolerances of the multiple video analytics queries.

19. The method of claim 18, wherein a resource-quality profile of a particular video analytics query specifies resource demands and result qualities corresponding to candidate multi-dimensional configurations of the particular video analytics query.

20. The method of claim 16, further comprising:

predicting lags of the multiple video analytics queries over a time horizon;

wherein the multiple video analytics queries are further scheduled based on the predicted lags.