Method, system and apparatus for tracking objects of a scene

Patent metadata

Field	Value
Publication number	US-9846810-B2
Application number	US-201414264668-A
Country	US
Kind code	B2
Filing date	Apr 29, 2014
Priority date	Apr 30, 2013
Publication date	Dec 19, 2017
Grant date	Dec 19, 2017

Abstract

A method of tracking objects of a scene is disclosed. The method determines two or more tracks which have merged. Each track is associated with at least one of the objects and having a corresponding graph structure. Each graph structure comprising at least one node representing the corresponding track. A new node representing the merged tracks is created. The graph structures are added as children nodes of the new node to create a merged graph structure. A split between the objects associated with one of the tracks represented by the nodes of the merged graph structure is determined. Similarity between one or more of the nodes in the merged graph structure and foreground areas corresponding to split objects is determined. One of the nodes in the merged graph structure is selected based on the determined similarity. A new graph structure for tracking the objects is created, the new graph structure having the selected node at the root of the new graph structure.

First claim

The claim(s) defining the invention are as follows:

1. A method of tracking objects of a scene, the method comprising:
determining two or more tracks which have merged, each track being associated with at least one of the objects and having a corresponding graph structure, each graph structure comprising at least one node representing the corresponding track;
creating a new node representing the merged tracks;
adding the graph structures as children nodes of the new node to create a merged graph structure;
detecting a split between the objects associated with one of the tracks represented by the nodes of the merged graph structure;
determining similarity between one or more of the nodes in the merged graph structure and foreground areas corresponding to split objects;
selecting one of the one or more nodes in the merged graph structure based on the determined similarity; and
dividing the merged graph structure and creating a new graph structure for tracking the objects in response to the detection of the split, the new graph structure being created from the merged graph structure based on the determined similarity, wherein the new graph structure has the selected node at the root of the new graph structure such that the selected node is distinct or separate from any preceding or prior node,
wherein the creation of the new graph structure removes and/or does not have a requirement or condition on having a 1:1 correlation between merged tracks and split tracks, and
wherein the new graph structure is monitored, maintained and/or updated by an object tracker, a video object tracker or a processor to track the objects of the scene or the objects in a sequence of images of the scene.

2. The method according to claim 1 , wherein hierarchy of the nodes under the selected node is maintained in the new graph structure.

3. The method according to claim 1 , further comprising merging graph structures corresponding to the tracks associated with the split.

4. The method according to claim 1 , further comprising creating further new graph structures for tracks that do not correspond to one of the at least one node or to any node.

5. The method according to claim 1 , wherein the selected node has a highest or best similarity score as compared with a similarity score of one or more unselected nodes.

6. The method according to claim 1 , wherein the selected node is removed from the merged graph structure along with a hierarchy underneath, or descendant node(s) of, the selected node.

7. The method according to claim 6 , wherein one or more ancestors of the selected node are marked for deletion and can no longer be selected.

8. The method according to claim 7 , wherein the nodes divide iteratively until no nodes are left or until the nodes are marked for deletion.

9. The method according to claim 1 , wherein the determined similarity is measured with at least one of:
(i) a gating distance used by at least one of: an Alpha Beta Filter based video object tracker, a Kalman Filter based video object tracker, a multi-state Alpha Beta Filter based video object tracker which approximates a Kalman filter with a predetermined number of states before reaching a Cramer-Rao lower bound;
(ii) a fraction representing an area of overlap divided by a total area occupied by an extended spatial representation of the foreground areas and a spatial prediction of a selected graph structure or track representation; and
(iii) a sum of discrepancies of edge positions for edges of the merged graph structure.

10. The method according to claim 9 , wherein the determining of the similarity step further comprises applying one or more bonuses or one or more penalties to determine the similarity, wherein the one or more bonuses encourage association hypotheses.

11. The method according to claim 1 , further comprising comparing the determined similarity to a threshold value; and
if the determined similarity is less than the threshold value, creating an additional association hypothesis, representing a hypothesis that a combination of selected foreground areas match a selected graph structure or track representation, and adding the additional association hypothesis to a list of one or more association hypotheses, or
if the determined similarity is more than or equal to the threshold value, determining whether all combinations of the foreground areas are processed.

12. The method according to claim 11 , further comprising using the list of one or more association hypotheses to reduce the list to a non-contradictory set of association hypotheses.

13. The method according to claim 12 , further comprising:
when an unprocessed association hypothesis remains, selecting an unprocessed association hypothesis from the list, associating track(s) and foreground area(s) in the selected association hypothesis and marking the association hypothesis as processed; and
when no unprocessed association hypothesis remains, updating each track that has not been matched to one or more of the foreground areas and creating a new graph structure for each foreground area that has not been matched to a track.

14. The method according to claim 1 , wherein at least one of:
(i) the creation of the new graph structure does not require, or does not have, a number, m, of merged tracks being split into the number, m, of split tracks, and
(ii) the removal and/or lack of the requirement or condition on having a 1:1 correlation between the merged tracks and the split tracks allows for at least one of: one or more real-time decisions to be made when one or more splits are detected, and one or more complex interactions to be accepted by a video object tracker without needing to either label the tracks as fragments, objects or groups or without making assumptions on how many real-world objects are present in an interaction.

15. The method according to claim 1 , wherein at least one of:
(i) the new graph structure is used to update or track the scene;
(ii) the new graph structure is displayed in a graph;
(iii) the graph of the new graph structure is maintained or updated by the object tracker, the video object tracker or the processor to track the objects; and
(iv) the new graph structure is stored in a memory.

16. A system for tracking objects of a scene, the system comprising:
a memory for storing data and a computer program;
a processor coupled to the memory for executing the computer program, the computer program comprising instructions for:
determining two or more tracks which have merged, each track being associated with at least one of the objects and having a corresponding graph structure, each graph structure comprising at least one node representing the corresponding track;
creating a new node representing the merged tracks;
adding the graph structures as children nodes of the new node to create a merged graph structure;
detecting a split between the objects associated with one of the tracks represented by the nodes of the merged graph structure;
determining similarity between one or more of the nodes in the merged graph structure and foreground areas corresponding to split objects;
selecting one of the nodes in the merged graph structure based on the determined similarity; and
dividing the merged graph structure and creating a new graph structure for tracking the objects in response to the detection of the split, the new graph structure being created from the merged graph structure based on the determined similarity, wherein the new graph structure has the selected node at the root of the new graph structure such that the selected node is dist

Assignees

• Canon Kk

Inventors

• Partis Ashley John

Classifications

• G06T7/20 Primary

  Analysis of motion (motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51) · CPC title

• G06V10/84

  using probabilistic graphical models from image or video features, e.g. Markov models or Bayesian networks · CPC title

• G06V20/52

  Surveillance or monitoring of activities, e.g. for recognising suspicious objects (recognising microscopic objects G06V20/69) · CPC title

• G06F18/29

  Graphical models, e.g. Bayesian networks · CPC title

• G06T2207/20072

  Graph-based image processing · CPC title