US6295367B1 — System and method for tracking movement of object…

Claim 1

Independent Claim 183 words

A method for tracking movement of objects in a scene from a stream of video frames comprising image information for the scene, the objects represented by region clusters which are hypotheses of objects to be tracked, comprising steps of: (a) forming a first correspondence graph comprising a plurality of object nodes representing the region clusters, and a plurality of tracks, each track comprising an ordered sequence of object nodes in consecutive video frames that represents a candidate track segment of an object in the scene, wherein the first correspondence graph includes multiple tracks representing multiple candidate track segments for the same object; (b) forming a second correspondence graph from tracks in the first correspondence graph, the second correspondence graph comprising a plurality of nodes and a plurality of tracks, each node in the second correspondence graph representing at least one track in the first correspondence graph, each track in the second correspondence graph comprising an ordered sequence of nodes representing a path of an object through the scene; and (c) accumulating track information for objects based on information in the second correspondence graph.

Claim 2

Independent Claim 183 words

A method for tracking movement of objects in a scene from a stream of video frames comprising image information for the scene, the objects represented by region clusters which are hypotheses of objects to be tracked, comprising steps of: (a) forming a first correspondence graph comprising a plurality of object nodes representing the region clusters, and a plurality of tracks, each track comprising an ordered sequence of object nodes in consecutive video frames that represents a candidate track segment of an object in the scene, wherein the first correspondence graph includes multiple tracks representing multiple candidate track segments for the same object; (b) forming a second correspondence graph from tracks in the first correspondence graph, the second correspondence graph comprising a plurality of nodes and a plurality of tracks, each node in the second correspondence graph representing at least one track in the first correspondence graph, each track in the second correspondence graph comprising an ordered sequence of nodes representing a path of an object through the scene; and (c) accumulating track information for objects based on information in the second correspondence graph.

Claim 3

Dependent Claim 37 words

The method of claim 1 , wherein the step of forming the first correspondence graph comprises the step of evaluating each region cluster for a video frame to determine whether it represents an object to be tracked.

Claim 4

Dependent Claim 43 words

The method of claim 2 , wherein the step of evaluating comprises comparing each region cluster with object model information and generating a first confidence value for the region cluster representing a likelihood that the region cluster represents an object to be tracked.

Claim 5

Dependent Claim 44 words

The method of claim 3 , wherein the step of evaluating further comprises determining a correspondence between each region cluster and a region cluster of a prior video frame that represents an object currently being tracked, and generating a second confidence value based thereon.

Claim 6

Dependent Claim 67 words

The method of claim 4 , and further comprising the step of inserting an object node in the first correspondence graph for each region cluster having a total confidence value greater than all region clusters that share mass with the region cluster, wherein the total confidence value is a combination of the first and second confidence values, and having a first confidence value greater than a threshold.

Claim 7

Dependent Claim 89 words

The method of claim 1 , wherein the step of forming the first correspondence graph comprises steps of: (1) comparing image information for a first object node in a current video frame with image information for a second object node in a prior video frame and generating a correspondence score representing a measure of correspondence between the first and second object nodes; and (2) linking the first object node in the current video frame to the second object node in the prior video frame based on the correspondence score.

Claim 8

Dependent Claim 111 words

The method of claim 6 , wherein the step of linking an object node comprises steps of: (i) comparing the correspondence score between the first object node and the second object node with a correspondence score between the first object node and every other object node in the prior video frame; and (ii) linking the first object node to the second object node if the correspondence score between the first object node and the second object node is greater than a predetermined minimum threshold, or if no other object node in the current video frame has a significantly higher correspondence score to the second object node in the prior video frame.

Claim 9

Dependent Claim 50 words

The method of claim 7 , wherein the step of forming the first correspondence graph comprises the step of creating a new track in the first correspondence graph when the first object node for the current video frame does not link to any existing track in the first correspondence graph.

Claim 10

Dependent Claim 52 words

The method of claim 7 , wherein the step of forming the first correspondence graph comprises the step of updating a track in the first correspondence graph when the first object node for the current video frame links to another object node contained in an existing track in the first correspondence graph.

Claim 11

Dependent Claim 36 words

The method of claim 8 , wherein the step of creating a new track in the first correspondence graph comprises assigning a track confidence value based on the first confidence value of the first object node.

Claim 12

Dependent Claim 58 words

The method of claim 9 , wherein the step of updating a track in the first correspondence graph comprises the step of updating a track confidence value based on the first confidence value of the first object node, a track confidence value at the prior video frame and the correspondence score between the first and second object nodes.

Claim 13

Dependent Claim 41 words

The method of claim 7 , wherein the step of forming the first correspondence graph comprises linking the first object node to a second object node based upon an orthogonal feature set tuned to resolve splitting and merging of object nodes.

Claim 14

Dependent Claim 31 words

The method of claim 12 , wherein the step of forming the first correspondence graph comprises linking object nodes on a broken track to object nodes in a current video frame.

Claim 15

Dependent Claim 50 words

The method of claim 13 , wherein the step of linking object nodes on a broken track to object nodes in a current video frame is based upon color information and overlap of mass with respect to object nodes in the current video frame, and/or trajectory of the broken track.

Claim 16

Dependent Claim 39 words

The method of claim 7 , wherein the step of forming the first correspondence graph comprises detecting a split or merge of a track based upon shared regions of object nodes in tracks over a plurality of video frames.

Claim 17

Dependent Claim 50 words

The method of claim 1 , wherein the step of forming the second correspondence graph comprises creating a node in the second correspondence graph for a track in the first correspondence graph when a length of the track in the first correspondence graph is greater than a predetermined minimum length.

Claim 18

Dependent Claim 43 words

The method of claim 16 , wherein the step of forming the second correspondence graph comprises the step of linking all merged tracks in the first correspondence graph to a node in the second correspondence graph representing the track of the merged tracks.

Claim 19

Dependent Claim 38 words

The method of claim 17 , wherein the step of forming the second correspondence graph comprises the step of detecting that a track in the second correspondence graph has split into at least two or more object tracks.

Claim 20

Dependent Claim 133 words

The method of claim 18 , wherein the step of resolving that two or more tracks have merged and then split comprises steps of: (i) generating directional color features of a most recent object node of the track prior to the merge that is not itself a result of a merge of two or more prior tracks and of the first object node of at least one subsequent track after the split; and (ii) comparing the directional color features of the most recent object node of the track prior to the merge and the first object node of the tracks after the split and generating a directional color correspondence score; and (iii) matching the track prior to the merge with the at least one subsequent track based upon the directional color correspondence score.

Claim 21

Dependent Claim 178 words

The method of claim 18 , wherein the step of resolving that two or more tracks have merged and then split comprises steps of: (i) resegmenting the set of object nodes of the track prior to the merge that is not itself a result of a merge of two or more prior tracks to generate a set of connected components and extracting features about the connected components; and (ii) resegmenting the object nodes of the track after the merge and at subsequent video frames up to and including the split to generate connected components of the object node and extracting features about the connected components of the resegmented object node; and (iii) comparing the extracted features of the set of connected components of the resegmented object nodes between consecutive video frames and matching connected components of the object nodes from consecutive video frames based upon a feature correspondence score; and (iv) matching the track prior to the merge with the at least one subsequent track after the split by the propagation of feature correspondence results from consecutive frames.

Claim 22

Independent Claim 212 words

A system for tracking movement of objects in a scene, comprising: (a) a video camera for monitoring the scene; (b) frame grabber means coupled to the video camera for generating a stream of video frames representing image information in the scene; (c) processor means coupled to the frame grabber means, the processor means being programmed to: (1) form a first correspondence graph comprising a plurality of object nodes representing region clusters which are hypotheses of objects to be tracked, and a plurality of tracks, each track comprising an ordered sequence of object nodes in consecutive video frames that represents a candidate track segment of an object in the scene, wherein the first correspondence graph includes multiple tracks representing multiple candidate track segments for the same object; (2) form a second correspondence graph from tracks in the first correspondence graph, the second correspondence graph comprising a plurality of nodes and a plurality of tracks, each node in the second correspondence graph representing at least one track in the first correspondence graph, each track in the second correspondence graph comprising an ordered sequence of nodes in the second correspondence graph representing a track of an object through the scene; and (3) accumulate track information for objects based on information in the second correspondence graph.

Claim 23

Independent Claim 212 words

A system for tracking movement of objects in a scene, comprising: (a) a video camera for monitoring the scene; (b) frame grabber means coupled to the video camera for generating a stream of video frames representing image information in the scene; (c) processor means coupled to the frame grabber means, the processor means being programmed to: (1) form a first correspondence graph comprising a plurality of object nodes representing region clusters which are hypotheses of objects to be tracked, and a plurality of tracks, each track comprising an ordered sequence of object nodes in consecutive video frames that represents a candidate track segment of an object in the scene, wherein the first correspondence graph includes multiple tracks representing multiple candidate track segments for the same object; (2) form a second correspondence graph from tracks in the first correspondence graph, the second correspondence graph comprising a plurality of nodes and a plurality of tracks, each node in the second correspondence graph representing at least one track in the first correspondence graph, each track in the second correspondence graph comprising an ordered sequence of nodes in the second correspondence graph representing a track of an object through the scene; and (3) accumulate track information for objects based on information in the second correspondence graph.

Claim 24

Dependent Claim 34 words

The system of claim 21 , wherein the processor means forms the first correspondence graph by evaluating each region cluster for a video frame to determine whether it represents an object to be tracked.

Claim 25

Dependent Claim 44 words

The system of claim 22 , wherein the processor means evaluates each region cluster by comparing it with object model information, and generating a first confidence value for the region cluster representing a likelihood that the region cluster represents an object to be tracked.

Claim 26

Dependent Claim 47 words

The system of claim 23 , wherein the processor means evaluates a region cluster by further determining a correspondence between each region cluster and a region cluster of a prior video frame that represents an object currently being tracked, and generating a second confidence value based thereon.

Claim 27

Dependent Claim 65 words

The system of claim 24 , wherein the processor means inserts an object node in the first correspondence graph for each region cluster having a total confidence value greater than all region clusters that share mass with the region cluster, wherein the total confidence value is a combination of the first and second confidence values, and having a first confidence value greater than a threshold.

Claim 28

Dependent Claim 87 words

The system of claim 21 , wherein the processor means forms the first correspondence graph by: (1) comparing image information for a first object node in a current video frame with image information for a second object node in a prior video frame and generating a correspondence score representing a measure of correspondence between the first and second object nodes; and (2) linking the first object node in the current video frame to the second object node in the prior video frame based on the correspondence score.

Claim 29

Dependent Claim 109 words

The system of claim 26 , wherein the processor means links an object node by: (i) comparing the correspondence score between the first object node and the second object node with a correspondence score between the first object node and every other object node in the prior video frame; and (ii) linking the first object node to the second object node if the correspondence score between the first object node and the second object node is greater than a predetermined minimum threshold, or if no other object node in the current video frame has a significantly higher correspondence score to the second object node in the prior video frame.

Claim 30

Dependent Claim 47 words

The system of claim 27 , wherein the processor means forms the first correspondence graph by creating a new track in the first correspondence graph when the first object node for the current video frame does not link to any existing track in the first correspondence graph.

Claim 31

Dependent Claim 49 words

The system of claim 27 , wherein the processor means forms the first correspondence graph by updating a track in the first correspondence graph when the first object node for the current video frame links to another object node contained in an existing track in the first correspondence graph.

Claim 32

Dependent Claim 36 words

The system of claim 28 , wherein the processor means creates a new track in the first correspondence graph and assigns a track confidence value based on the first confidence value of the first object node.

Claim 33

Dependent Claim 55 words

The system of claim 29 , wherein the processor means updates a track in the first correspondence graph by updating a track confidence value based on the first confidence value of the first object node, a track confidence value at the prior video frame and the correspondence score between the first and second object nodes.

Claim 34

Dependent Claim 50 words

The system of claim 21 , wherein the processor means forms the second correspondence graph by creating a node in the second correspondence graph for a track in the first correspondence graph when a length of the track in the first correspondence graph is greater than a predetermined minimum length.

Claim 35

Dependent Claim 41 words

The system of claim 32 , wherein the processor means forms the second correspondence graph by further linking all merged tracks in the first correspondence graph to a node in the second correspondence graph representing the track of the merged tracks.

Claim 36

Dependent Claim 35 words

The system of claim 33 , wherein the processor means forms the second correspondence graph by detecting that a track in the second correspondence graph has split into at least two or more object tracks.

Claim 37

Dependent Claim 131 words

The system of claim 34 , wherein the processor means resolves that two or more tracks have merged and then split by: (i) generating directional color features of a most recent object node of the track prior to the merge that is not itself a result of a merge of two or more prior tracks and of the first object node of at least one subsequent track after the split; and (ii) comparing the directional color features of the most recent object node of the track prior to the merge and the first object node of the tracks after the split and generating a directional color correspondence score; and (iii) matching the track prior to the merge with the at least one subsequent track based upon the directional color correspondence score.

Claim 38

Dependent Claim 176 words

The system of claim 34 , wherein the processor means resolves that two or more tracks have merged and then split by: (i) resegmenting the set of object nodes of the track prior to the merge that is not itself a result of a merge of two or more prior tracks to generate a set of connected components and extracting features about the connected components; and (ii) resegmenting the object nodes of the track after the merge and at subsequent video frames up to and including the split to generate connected components of the object node and extracting features about the connected components of the resegmented object node; and (iii) comparing the extracted features of the set of connected components of the resegmented object nodes between consecutive video frames and matching connected components of the object nodes from consecutive video frames based upon a feature correspondence score; and (iv) matching the track prior to the merge with the at least one subsequent track after the split by the propagation of feature correspondence results from consecutive frames.

Claim 39

Dependent Claim 43 words

The method of claim 1 , wherein the step of forming the first correspondence graph further comprises applying one or more constraints, including shared mass of object nodes and track trajectory information, to reduce the number of tracks in the first correspondence graph.

Claim 40

Dependent Claim 42 words

The method of claim 21 , wherein the processor means forms the first correspondence graph by applying one or more constraints, including shared mass of object nodes and track trajectory information, to reduce the number of tracks in the first correspondence graph.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2004-09-24	2005-03-26	2005-09-25	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2008-09-24	2009-03-26	2009-09-25	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2012-09-24	2013-03-26	2013-09-25	$7700.00	Window Closed / Lapsed

System and method for tracking movement of objects in a scene using correspondence graphs

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag