Multiple object tracking in a video stream

[0001] This patent application relates generally to computer vision, and more specifically to the tracking of objects within video data.

[0002] Identifying objects in a video stream is often a straightforward task for humans. To a computer system, however, a video stream is a sequence of images, and identifying portions of successive video frames within the video stream that correspond to the same physical object can be a difficult task. Multiple Object Tracking (MOT) procedures are used to analyze a video stream to identify and track objects and events of interest.

[0003] The tracking of objects of interest using unsupervised smart cameras or systems is of paramount importance for a range of applications, such as object in-painting to remove an object from a video stream. However, MOT procedures are often a limiting factor in video stream analysis because tracking is difficult and prone to error in complex situations. Errors occurring during the tracking phase can negatively impact subsequent operations related to video analytics, video modification, and video insight generation. Accordingly, improved techniques for multiple object tracking are desired.

[0004] Techniques and methods described herein provide for embodiments of systems, devices, methods, and non-transitory computer readable media having instructions stored thereon for video stream analysis and processing. In some implementations, a bounding box around an object within a designated frame of a plurality of frames within a video stream may be determined. Two or more object tracks for the object may be determined from a plurality of object tracks by applying two or more object tracking models to the video stream, each of the two or more object tracks identifying a correspondence between bounding boxes for the object across different ones of the plurality of frames. A plurality of raw performance metrics may be determined based at least in part on one or more visual features within the designated frame, each of the raw performance metrics corresponding to a respective one of the two or more object tracking models. A designated object track of the two or more object tracks may be selected for the object based at least in part on the plurality of raw performance metrics. The designated object track may be stored on a storage device.

[0005] According to various embodiments, a determination may be made as to whether the two or more object tracks are different. The raw performance metrics may be determined when it is determined that the two or more object tracks are different.

[0006] In some embodiments, a plurality of normalized performance metrics may be determined based on the raw performance metrics. The normalized performance metrics may be located on a designated performance metric scale.

[0007] In some implementations, a plurality of raw cost matrices may be determined for the designated frame. The raw cost matrices corresponding to a respective one of the object tracking models. A designated one of the raw cost matrices may include a plurality of values. Each of the values may correspond with a respective one of the plurality of object tracks and a respective bounding box within the designated frame. A plurality of weighted cost matrices may be determined for the designated frame. Each of the weighted cost matrices may correspond with a respective raw cost matrix and may be weighted based on a respective weighting factor. The weighting factors may be determined based on the plurality of raw performance metrics.

[0008] In some embodiments, an object identifier for the bounding box may be determined by applying an object recognition algorithm to all or a portion of the designated frame. The two or more object tracking models may include an appearance-based model. The two or more object tracking models may include a motion-based model. A designated one of the performance metrics may be determined for an individual frame. Alternatively, or additionally, a designated one of the performance metrics is determined for a group of temporally proximate frames.

[0009] These and other embodiments are described further below with reference to the figures.

[0016] Techniques and mechanisms described herein provide for the tracking of one or more objects across multiple video frames. In some embodiments, two or more different models may be separately applied to track an object across multiple video frames. A model may be dynamically evaluated for a frame or group of frames by determining a performance metric for the model, for instance on the level of a frame or group of frames. Then, two or more models may be fused together using a weighting scheme based at least in part on performance metrics for the different models.

[0017] Different models may be more or less suitable for tracking different types of objects and/or tracking objects in different situations. Accordingly, many conventional MOT techniques involve stacking or fusing different models. However, fusing is typically performed in a static fashion by using averages and other fixed combination techniques. The performance of static fusing methods is very poor in complex situations that involve challenges such as occlusions, variable scene illumination, nonlinear motion, frequent entries and exits of objects. The poor performance of these models is reflected by issues such as frequent object ID switching and lost tracks.

[0018] In contrast to conventional techniques, techniques and mechanisms described herein provide for a dynamic fusing approach in which the use of models is tailored depending on the context. Such techniques and mechanisms allow the use of two or more models for tracks construction by matching the detected objects in the current frame to their corresponding tracks (i.e. the set of positions of the detected object in the previous frames).

[0019] In some implementations, the use or not of a given model as well as the determination of the importance of a given model among the set of used models may be dynamically determined (e.g., at each frame), for instance by evaluating how appropriate the model's performance is to the matching task for the current frame. The appropriateness of a given model may be determined at least in part using information about the situations where the model tends to perform well or poorly. Such information may be coded as a metric that is used to dynamically compute (e.g., at each frame) the weight of the model attached to it.

[0020] According to various embodiments, two or more models for object tracking may be combined based on their expected performance. For example, object tracking may involve the application of both an appearance model and a motion model. For each frame or group of frames, the expected performance of the appearance model and the motion model may each be determined. An appropriate performance metric for the appearance model may depend on the degree of similarity between the objects of the same frame, using for instance the cosine similarity between the vectors encoding the appearance of the objects. An appropriate metric for the motion model may depend on the degree of crowdedness of the scene, using for instance the distance between the centroids of the bounding boxes.

[0021] In some embodiments, a model weight may be determined based on the performance metric. For example, a performance metric may measure a negative impact, in which case a model weight may be inversely proportional to the metric. That is, the higher the metric, the lower the weight. In the example discussed in the previous paragraph, increased similarity between objects of the same frame may lower the weight of the appearance model, while increased crowdedness may lower the weight of the motion model.

[0022] According to various embodiments, techniques and mechanisms described herein may allow for any suitable number of models to be aggregated into a single procedure in which models receive higher weights when they positively impact object tracking precision and lower weights when they do not. Further, the system may support various types and combinations of metrics for different models.

[0023] Object tracking is a fundamental aspect of many video processing systems, such as surveillance systems. Accordingly, embodiments of techniques and mechanisms described herein may improve the functioning of such systems by providing for increased object tracking precision. Such improvements may manifest as a lower error rate when tracking objects across frames in a video stream.

[0024] FIG. 1 illustrates an overview method 100 for multiple object tracking, performed in accordance with one or more embodiments. According to various embodiments, the method 100 may be performed at any suitable computing device. For example, the method 100 may be performed at a surveillance system configured to control one or more cameras. As another example, the method 100 may be performed at a smart camera, or at a computing device that receives data from a camera.

[0025] A bounding box for an object within a frame of a video stream is determined at 102. The term “bounding box” refers to a region of an image that defines a location of an object. In some embodiments, the bounding box may be rectangular. Alternatively, or additionally, non-rectangular bounding boxes may be used.

[0026] According to various embodiments, a bounding box may be determined by applying one or more of a variety of suitable image processing procedures to the frame. For example, an object detection algorithm may be applied to the frame. The object detection algorithm may identify a region of an image that corresponds to a particular object. Object detection may rely, for instance, on identifying lines, corners, shapes, and/or other low-level features. Alternatively, or additionally, object detection may rely on pattern recognition algorithms that identify objects such as human beings, animals, or vehicles based on characteristics common to these types of objects.

[0027] Object tracks for the bounding box are determined at 104 by applying two or more object tracking models to the video stream. According to various embodiments, various types of tracking models may be used. For instance, an appearance tracking model may track objects based on their visual characteristics, while a motion tracking model may track objects based on their location within the frame.

[0028] A respective performance metric for each of the two or more object tracking models is determined at 106. According to various embodiments, an object tracking model may be associated with a performance metric that indicates a predicted performance level for the object tracking model under a particular set of conditions. For example, a performance metric may depend on characteristics such as the crowdedness of a frame.

[0029] A designated object track is selected for the bounding box at 108 from the two or more object tracks. According to various embodiments, the designated object track may be selected based at least in part on the performance metrics determined at 106. For example, the designated object track may be selected by weighting the tracks based on the performance metrics associated with the object models that produced the tracks, and then selecting the object tracking having the highest weight.

[0030] For expositional clarity, the method 100 shown in FIG. 1 is described as being applied to track a single object across different frames in a video stream. However, the method 100 may be applied to track any number of objects across different frames in a video stream.

[0031] FIG. 2 illustrates a method 200 for multiple object tracking, performed in accordance with one or more embodiments. According to various embodiments, the method 200 may be performed on a computing device such as the device 500 shown in FIG. 5.

[0032] A request to perform multiple object tracking for a frame of a video stream is received at 202. In some embodiments, the request may be generated manually, for instance based on user input. Alternatively, the request may be generated automatically and/or dynamically. For instance, the request may be generated as part of a larger video analysis methodology, such as a video in-painting process in which objects are removed from a video stream.

[0033] In particular embodiments, the method 200 may be performed for each successive frame in a video stream. Alternatively, the method 200 may be performed periodically. For example, the method 200 may be performed for key frames within a video stream. As another example, the method 200 may be performed at a given rate, such as once per every five frames.

[0034] One or more bounding boxes for the frame are determined at 204. According to various embodiments, bounding boxes for a frame may be determined via any of a variety of suitable methods. For instance, bounding boxes may be determined via logistic regression, histogram of oriented gradient (HOG), convolutional neural network (CNN), region-based convolutional neural networks (R-CNN), single-shot detector, You Only Look Once (YOLO), or any suitable bounding box detection procedure.

[0035] A bounding box is selected for tracking at 206. A model for track prediction is selected at 208. According to various embodiments, bounding boxes and models may be selected for analysis in any suitable order. For example, bounding boxes and models may be selected for analysis in a pre-defined sequence, in parallel, or according to another ordering.

[0036] A predicted object track is determined for the bounding box at 210 based on the model. According to various embodiments, any of a variety of object tracking models may be employed. For example, multiple object tracking may involve motion models, appearance models, other models, or some combination thereof. Examples of such models may include, but are not limited to: Generic Object Tracking Using Regression Networks (GOTURN), Recurrent You Only Look Once (ROLO), Simple Online Real-Time Tracker (SORT), DeepSORT, SiamMask, Joint Detection and Embedding (JDE), and Tracktor++. Techniques and mechanisms described herein are consistent with the group of different models identified above, other models, and/or different instances of the same model trained or parameterized in different ways.

[0037] A determination is made at 212 as to whether to select an additional model. If an additional model is not selected, then at 214 a determination is made as to whether to select an additional bounding box for tracking. According to various embodiments, the process many continue until all bounding boxes selected at 206 and models used for track prediction have been identified.

[0038] A determination is made at 216 as to whether there is consensus among the models as to the predicted object tracks. According to various embodiments, the determination may involve identifying a correspondence between bounding boxes and object tracks for each model, and then determining whether those correspondences are the same across each models.

[0039] In some implementations, a determination may be made as to whether a partial consensus exists. In a partial correspondence, all models may agree on a correspondence between bounding box and track for one or more of the bounding boxes, while also disagreeing on a correspondence between bounding box and track for a different one or more of the bounding boxes. In such a configuration, the agreed upon tracks may be employed for the bounding box or boxes where a consensus exists, and a composite model may be used to determine predicted object tracks for bounding boxes where no such consensus exists.

[0040] If consensus does not exist, then at 218 predicted object tracks are determined based on a composite model. Additional details related to the determination of predicted object tracks are discussed with respect to the method 300 shown in FIG. 3.

[0041] The predicted object tracks are stored at 220. Additional details related to the storage of predicted object tracks are discussed with respect to the method 400 shown in FIG. 4.

[0042] According to various embodiments, the operations shown in FIG. 200 may be performed in an order different than that shown. For example, operations 206 and 208 may performed in the reverse order, as well as operations 212 and 214.

[0043] FIG. 3 illustrates a method 300 for determining a composite model, performed in accordance with one or more embodiments. According to various embodiments, the method 200 may be performed on a computing device such as the device 500 shown in FIG. 5.

[0044] A request to determine a composite model for a frame of a video stream is received at 302. According to various embodiments, the request may be generated as part of a multiple object tracking procedure. For instance, the request may be generated as discussed with respect to the operation 208 shown in FIG. 2, when different models disagree as to the object track for one or more bounding boxes.

[0045] A model is selected for multiple object tracking at 304. According to various embodiments, any and all methods employed during the performance of the method 200 shown in FIG. 2 may be selected. For instance, models may be selected where there was at least some disagreement as to the object track for at least one bounding box. Models may be selected in any suitable order. For instance, models may be selected in sequence, in parallel, or in accordance with a pre-determined ordering.

[0046] A raw cost matrix for the frame is determined at 306 using the selected model. According to various embodiments, a raw cost matrix may identify a distance between one or more bounding boxes included in a current frame and one or more bounding boxes of existing tracks. That is, a value corresponding with row i and column j of a raw cost matrix may identify a distance between bounding box i in the current frame and a bounding box in existing track j, for a particular model.

[0047] According to various embodiments, any of various approaches may be used to calculate the distance values. For example, a distance value may be calculated using a cosine similarity measure as applied to a vector representation of the bounding boxes. As another example, a distance measure may be calculated as an intersection over union that identifies the area of overlap between the two bounding boxes as a portion of the union of the two bounding boxes. A similarity measure may be determined as, for instance, a distance value subtracted from one.

[0048] An existing track may be associated with more than one bounding box, for instance corresponding with different frames of a track. Accordingly, a similarity value between an existing track and a bounding box of the current frame may be determined in any of various ways. For example, the similarity value may be determined based on the maximum similarity of the bounding box of the current frame with any bounding box associated with the existing track. For instance, such an approach may be appropriate when employing an appearance model. As another example, the similarity value may be determined based on the similarity between the bounding box associated with the current frame and the bounding box for an existing track associated with an immediately preceding frame. For instance, such an approach may be appropriate when employing a motion model.

[0049] One or more raw model fitness coefficient values are determined at 308 based on the frame. In some embodiments, a raw model fitness coefficient value may indicate a quality or fitness of a particular model when applied to the current frame, as estimated or predicted based at least in part on one or more characteristics of the current frame.

[0050] According to various embodiments, a raw model fitness coefficient value may be determined based on the cost matrix. The raw model fitness coefficient value may be determined in a model-specific way. For example, the raw model coefficient value may be based on appearance similarity for an appearance model. As another example, the raw model coefficient value may be based on crowdedness for a motion frame. For instance, crowdedness may be determined based on, for instance, factors such as the number, size, and proximity of bounding boxes within the frame.

[0051] In particular embodiments, a raw model fitness coefficient value and/or a raw cost matrix may be determined for a set of temporally proximate frames rather than for an individual frame. In this way, temporal changes in a video stream may be smoothed across multiple frames.

[0052] A determination is made at 310 as to whether to select an additional model for multiple object tracking. According to various embodiments, as discussed with respect to operation 304, models may be analyzed in any suitable order, in sequence or in parallel.

[0053] Normalized model fitness coefficient values are determined at 312 based on the raw model fitness coefficient values. According to various embodiments, the normalized model fitness coefficient values may be determined by scaling the raw model fitness coefficient values determined at 308 to a common scale. For example, the raw model fitness coefficient values may each be scaled to a value between zero and one.

[0054] Weighted cost matrices are determined at 314 based on the normalized model fitness coefficient values. In some embodiments, a weighted cost matrix may be determined by multiplying the values within a raw cost matrix for a model by the normalized model fitness coefficient value for that model.

[0055] A composite cost matrix is determined at 316 based on the weighted cost matrices. According to various embodiments, the composite cost matrix may be determined by combining the weighted cost matrices according to a combination function. For instance, the weighted cost matrices may be added together. In this way, each value of the composite cost matrix may represent a distance between a bounding box in the current frame and an existing track that reflects the input of all models, weighted based on the quality of each model for the frame as determined based on the model fitness coefficient values.

[0056] Predicted object tracks are determined at 318 based on the composite cost matrix. In some embodiments, a predicted object track for a bounding box may be determined based on which existing track is associated with the lowest cost in the composite cost matrix. Alternatively, or additionally, one or more other selection criteria may be used. For example, a restriction that different bounding boxes may not be associated with the same existing track may be imposed. As another example, the composite cost matrix may be analyzed to identify a one-to-one correspondence between bounding boxes and tracks, for instance the correspondence having the small total cost.

[0057] FIG. 4 illustrates a method 400 for storing one or more object tracks, performed in accordance with one or more embodiments. According to various embodiments, the method 400 may be performed to store an object track in association with a bounding box, after such an association is determined as discussed with respect to the methods 200 and 300 shown in FIGS. 2 and 3. The method 200 may be performed on a computing device such as the device 500 shown in FIG. 5.

[0058] A request to store one or more object tracks for a frame in a video stream is received at 402. In some implementations, the request may be generated as discussed with respect to the operation 220 shown in FIG. 2.

[0059] A bounding box and associated track for the frame are selected at 404. According to various embodiments, the track for a bounding box in a frame may be determined as discussed with respect to the methods 200 and 300 as shown in FIGS. 2 and 3.

[0060] A determination is made at 406 as to whether to update an object identifier for the track. According to various embodiments, each track may be associated with one or more identifiers that identify an object associated with the track. An identifier may identify any suitable information that may be associate with a track. For example, an identifier may indicate that the track corresponds to a person, an animal, or another type of object. As another example, an identifier may indicate that a track corresponds to a particular person, a particular animal, or a particular object. As yet another example, an identifier may indicate that a track corresponds to a particular type of person or object. For instance, a type of person in a video stream associated with a video surveillance application may be a home occupant, an intruder, or an unidentified individual.

[0061] According to various embodiments, any of various criteria may be used to determine whether to update an object identifier for a track. For example, an object identifier for a track may be determined if the track is not yet associate with an object identifier. As another example, object identification may be performed on a track periodically, such as every 30 frames. As yet another example, object identification may be performed on a track if a confidence value associated with object identification for the track is below a designated threshold. The particular criteria for use in determining whether to update an object identifier may be strategically determined based on the application.

[0062] Object recognition is applied to the bounding box at 408. According to various embodiments, one or more of any suitable object recognition algorithm may be applied to the bounding box and/or to the frame to recognize the object. For example, a person recognition algorithm may be applied to distinguish humans from other moving objects. As another example, a face recognition algorithm may be applied, for instance to distinguish occupants of a home from other individuals.

[0063] In particular embodiments, an object recognition algorithm may receive as input not only a particular frame and/or bounding box within a frame, but also other information. For instance, the algorithm may receive as input one or more other images of the object, such as image data from previous frames in the video stream.

[0064] A determination is made at 410 as to whether object recognition was successful. The determination may be made based at least in part on the output from the object recognition algorithm or algorithms applied at operation 408.

[0065] In some implementations, the determination made at operation 410 may be non-binary. For instance, the output of an object recognition algorithm may identify not a single object, but rather one or more objects that are each associated with a respective confidence value. As another example, different object recognition algorithms may identify different objects. In such a situation, an object track may be associated with more than object identifier. Alternatively, or additionally, an object identifier may be associated with metadata such as a confidence value.

[0066] The track is associated with the object identifier at 412. An association between the bounding box and the track is stored at 414. According to various embodiments, such associations may be stored in transient memory, in a non-transitory storage medium, in a network-accessible storage location, or in any other suitable way.

[0067] A determination is made at 416 as to whether to select an additional bounding box for the frame. According to various embodiments, additional bounding boxes may be selected until all bounding boxes in the frame have been processed. As discussed with respect to the operation 404, bounding boxes may be analyzed in parallel or in sequence, and in any suitable order.

[0068] FIG. 5 illustrates one example of a computing device 500, configured in accordance with one or more embodiments. According to various embodiments, a system 500 suitable for implementing embodiments described herein includes a processor 501, a memory module 503, a storage device 505, an interface 511, and a bus 515 (e.g., a PCI bus or other interconnection fabric.) System 500 may operate as variety of devices such as an application server, a database server, or any other device or service described herein. Although a particular configuration is described, a variety of alternative configurations are possible. The processor 501 may perform operations such as those described herein. Instructions for performing such operations may be embodied in the memory 503, on one or more non-transitory computer readable media, or on some other storage device. Various specially configured devices can also be used in place of or in addition to the processor 501. The interface 511 may be configured to send and receive data packets over a network. Examples of supported interfaces include, but are not limited to: Ethernet, fast Ethernet, Gigabit Ethernet, frame relay, cable, digital subscriber line (DSL), token ring, Asynchronous Transfer Mode (ATM), High-Speed Serial Interface (HSSI), and Fiber Distributed Data Interface (FDDI). These interfaces may include ports appropriate for communication with the appropriate media. They may also include an independent processor and/or volatile RAM. A computer system or computing device may include or communicate with a monitor, printer, or other suitable display for providing any of the results mentioned herein to a user.

[0069] Any of the disclosed implementations may be embodied in various types of hardware, software, firmware, computer readable media, and combinations thereof. For example, some techniques disclosed herein may be implemented, at least in part, by computer-readable media that include program instructions, state information, etc., for configuring a computing system to perform various services and operations described herein. Examples of program instructions include both machine code, such as produced by a compiler, and higher-level code that may be executed via an interpreter. Instructions may be embodied in any suitable language such as, for example, Java, Python, C++, C, HTML, any other markup language, JavaScript, ActiveX, VBScript, or Perl. Examples of computer-readable media include, but are not limited to: magnetic media such as hard disks and magnetic tape; optical media such as flash memory, compact disk (CD) or digital versatile disk (DVD); magneto-optical media; and other hardware devices such as read-only memory (“ROM”) devices and random-access memory (“RAM”) devices. A computer-readable medium may be any combination of such storage devices.

[0070] In the foregoing specification, various techniques and mechanisms may have been described in singular form for clarity. However, it should be noted that some embodiments include multiple iterations of a technique or multiple instantiations of a mechanism unless otherwise noted. For example, a system uses a processor in a variety of contexts but can use multiple processors while remaining within the scope of the present disclosure unless otherwise noted. Similarly, various techniques and mechanisms may have been described as including a connection between two entities. However, a connection does not necessarily mean a direct, unimpeded connection, as a variety of other entities (e.g., bridges, controllers, gateways, etc.) may reside between the two entities.

[0071] In the foregoing specification, reference was made in detail to specific embodiments including one or more of the best modes contemplated by the inventor. While various implementations have been described herein, it should be understood that they have been presented by way of example only, and not limitation. For example, some techniques and mechanisms are described herein in the context of tracking multiple objects within video streams. However, the techniques of the present invention apply to a wide variety of computer vision applications, such as tracking objects within sequences of still images. Particular embodiments may be implemented without some or all of the specific details described herein. In other instances, well known process operations have not been described in detail in order not to unnecessarily obscure the present invention. Accordingly, the breadth and scope of the present application should not be limited by any of the implementations described herein, but should be defined only in accordance with the claims and their equivalents.