Methods and systems for tracking objects in videos and images using a cost matrix

• US 10,445,885 B1
• Filed: 06/11/2016
• Issued: 10/15/2019
• Est. Priority Date: 10/01/2015
• Status: Active Grant

• Current Assignee: IntelliVision Technologies Corp. (Melrose Industries Plc)
• Original Assignee: IntelliVision Technologies Corp. (Melrose Industries Plc)
• Inventors: Nathan, Vaidhi, Sokolov, Maxim, Afraimovich, Lev, Gope, Chandan
• Primary Examiner(s): Bali, Vikkram
• Application Number:
  US15/179,972
• Time in Patent Office: 1,221 Days
• Field of Search: None
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 18/2431 Multiple classes
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30232 Surveillance
• CPC Class Codes: G06T 7/248 involving reference images or patches
• CPC Class Codes: G06T 7/74 involving reference images or patches
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 10/467 Encoded features or binary features, e.g. local binary patterns [LBP]
• CPC Class Codes: G06V 10/50 by performing operations within image blocks; by using histograms, e.g. histogram of oriented gradients [HoG]; by summing image-intensity values; Projection analysis
• CPC Class Codes: G06V 10/56 relating to colour
• CPC Class Codes: G06V 10/761 Proximity, similarity or dissimilarity measures
• CPC Class Codes: G06V 20/41 Higher-level, semantic clustering, classification or understanding of video scenes, e.g. detection, labelling or Markovian modelling of sport events or news items segmenting video sequences G06V20/49
• CPC Class Codes: G06V 20/52 Surveillance or monitoring of activities, e.g. for recognising suspicious objects recognising microscopic objects G06V20/69

Abstract

The present invention discloses methods, systems, and computer programmable products for tracking objects across a first frame and a second frame of a video. An object tracking system computes a cost function between each object in the first frame and each object in the second frame. Further, a pair of objects is selected from the first frame and the second frame based on a pre-defined criteria which is based on the computed cost function. Thereafter, the object tracking system established a correspondence between the selected pair of objects.

Claims

1. An optimizer-reduced cost matrix for object tracking across consecutive video frames for optimal object assignment, said system comprising of:

an optimizer;

encoded instructions stored in a non-transitory storage element, wherein the encoded instructions when implemented by a processor, configure the system to;

obtain pixel values of captured feature points across at least a first video frame and a second video frame;

detect at least one object in the first video frame and at least one candidate object in the second video frame and store pixel values corresponding to the at least one detected object in the first video frame and the at least one detected candidate object in the second video frame;

compute a cost function value between at least one detected object in the first video frame and at least one detected candidate object in the second video frame based on;

a visual dissimilarity between the object and the candidate object based on the stored pixel values;

a physical distance between the object and the candidate object based on the stored pixel values; and

a difference between an expected location of the object in the second video frame and the candidate object based on the stored pixel values and storing the computed cost functions in a cost matrix;

reduce a size of the cost matrix via the optimizer by checking the cost function values in each column to identify the value that is significantly smaller than others, and then values in the corresponding row are then compared to the values of all other objects to identify the smallest value for marking, repeating for all columns and rows of the cost matrix that have one or more marked elements are removed; and

apply the reduced cost matrix via the optimizer to execute optimal object assignment for the tracked objects across consecutive video frames.

2. The system of claim 1, wherein the visual dissimilarity between the object and the candidate object is determined based on at least one of a color based similarity, gradient based similarity and texture based similarity.

3. The system of claim 1, wherein the physical distance between the object and the candidate object is determined based on number of pixels between the object and the candidate object, and wherein perspective geometry information is available.

4. The system of claim 1, wherein the expected location of the object in the second frame is determined based on at least one of location of the object in the first frame, speed of the object and direction of motion of the object.

5. The system of claim 1, wherein the pre-determined criteria is to select a pair of objects comprising an object of the one or more objects and a candidate object of the one or more candidate objects when value corresponding to the cost function computed between the object and the candidate object is lower than values corresponding to cost functions computed between the object and each of the remaining candidate objects of the one or more candidate objects.

6. The system of claim 1, further comprising of a tracking unit, wherein the tracking unit is configured to apply a Hungarian method to select the one or more pairs of objects.

7. The system of claim 1, further comprising an optimizer configured to optimize size of the two-dimensional array.

8. The system of claim 1, wherein the video is at least one of a live video, an archived video stored in a data storage, or a recorded video.

9. The system of claim 1, wherein the system is a part of at least one of a surveillance system, a security system, a retail system, a monitoring system, a business intelligence-based system.

10. The system of claim 1, further comprising a classifier unit configured to classify an object of the one or more objects in one or more categories.

11. The system of claim 10, wherein the classifier unit classifies the object based on at least one feature of the object, and wherein the feature is at least one of a size, aspect ratio, location, color, Histogram of Oriented Gradient (HOG), Scale-invariant feature transform (SIFT), HAAR like features and Local Binary Pattern (LBP) of the object.

12. A method for executing optimal object assignment across consecutive video frames based on a optimizer-reduced cost matrix, said method comprising the steps of:

obtaining pixel values of captured feature points across at least a first video frame and a second video frame by means of a video capture;

detecting at least one object in the first video frame and at least one candidate object in the second video frame and store pixel values corresponding to the at least one detected object in the first video frame and the at least one detected candidate object in the second video frame;

computing a cost function between at least one detected object in the first video frame and at least one detected candidate object in the second video frame based on;

a visual dissimilarity between the object and the candidate object based on the stored pixel values, a physical distance between the object and the candidate object based on the stored pixel values, and a difference between an expected location of the object in the second video frame and the candidate object based on the stored pixel values and storing the cost functions computed;

reducing a size of the cost matrix via an optimizer by checking the cost function values in each column to identify the value that is significantly smaller than others, and then values in the corresponding row are then compared to the values of all other objects to identify the smallest value for marking, repeating for all columns and rows of the cost matrix that have one or more marked elements are removed; and

applying the reduced cost matrix via the optimizer to execute optimal object assignment for the tracked objects across consecutive video frames, whereby object assignment is optimized by at least one of decreasing an amount of computation, reducing power consumption, or increasing assignment speed and accuracy.

13. The method of claim 12, wherein the visual dissimilarity between the object and the candidate object is determined based on at least one of the group comprising color based similarity, gradient based similarity and texture based similarity.

14. The method of claim 12, wherein the physical distance between the object and the candidate object is determined based on number of pixels between the object and the candidate object, and wherein perspective geometry information is available.

15. The method of claim 12, wherein the expected location of the object in the second frame is determined based on at least one of location of the object in the first frame, speed of the object and direction of motion of the object.

16. The method of claim 12, wherein the pre-determined criteria is to select a pair of objects comprising an object of the one or more objects and a candidate object of the one or more candidate objects when value corresponding to the cost function computed between the object and the candidate object is lower than values corresponding to cost functions computed between the object and each of the remaining candidate objects of the one or more candidate objects.

17. The method of claim 12, further comprising a tracking unit, wherein the tracking unit is configured to apply a Hungarian method to select the one or more pairs of objects.

18. The method of claim 12, further comprising an optimizer, wherein the optimizer is configured to optimize the size of the two-dimensional array.

19. The method of claim 12, further comprising a classifying unit, wherein the classifier is configured to classify an object of the one or more objects in one or more categories.

20. An optimized system executing efficient object assignment from a reduced cost matrix, said system comprising of:

an optimizer;

encoded instructions stored in a non-transitory storage element, wherein the encoded instructions when implemented by a processor, configure the system to;

obtain pixel values of captured feature points across at least a first video frame and a second video frame;

generate a cost function between a plurality of detected objects and a candidate objects by evaluating pixel values of captured feature points in the first video frame and the second video frame based on;

a visual dissimilarity between the object and the candidate object, a physical distance between the object and the candidate object, and a difference between an expected location of the object in the second video frame and the candidate object and storing the cost functions computed in a form of a two-dimensional cost matrix;

reduce a size of the cost matrix via the optimizer by checking the cost function values in each column to identify the value that is significantly smaller than others, and then values in the corresponding row are then compared to the values of all other objects to identify the smallest value for marking, repeating for all columns and rows of the cost matrix that have one or more marked elements are removed; and

apply the reduced cost matrix to select one or more pairs of objects from the stored values based on a pre-determined criteria, wherein the object and the candidate object belong to a pair of the one or more pairs of objects, and thereby, executing efficient object tracking by at least one of decreasing the time required to select the one or more pairs of objects from the optimizer-reduced cost matrix, decreasing an amount of computation, reducing power consumption, or increasing assignment speed and accuracy.