METHOD FOR CLUSTERING MULTI-MODAL DATA THAT CONTAIN HARD AND SOFT CROSS-MODE CONSTRAINTS

• US 20120051589A1
• Filed: 08/24/2010
• Published: 03/01/2012
• Est. Priority Date: 08/24/2010
• Status: Abandoned Application

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Schloegel, Kirk A., Guralnik, Valerie
• Application Number:
  US12/862,289
• Publication Number:
  US 20120051589A1
• Time in Patent Office: Days
• US Class Current: 382/103
• CPC Class Codes: G06T 2207/30232 Surveillance
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51

Abstract

A program product for clustering multi-modal data including hard and soft cross-mode constraints is provided. The program-product includes a non-transitory processor-readable medium on which program instructions are embodied. The program instructions are operable, when executed by at least one processor, to: color nodes in a graph having a plurality of objective edges and a plurality of constraint edges; partition the nodes by color; map the partitions back to the graph to form a color-partitioned graph having at least two sub-domains; and cross-associate all data that are part of a cluster. At least two colors are used to color the nodes. The plurality of constraint edges connects a respective plurality of node pairs, the two nodes in the node pairs being different colors. The partitioned nodes of the same color are independent of constraint edges.

Claims

1. A program product for clustering multi-modal data including hard and soft cross-mode constraints, the program-product comprising a non-transitory processor-readable medium on which program instructions are embodied, wherein the program instructions are operable, when executed by at least one processor, to:

color nodes in a graph having a plurality of objective edges and a plurality of constraint edges, wherein at least two colors are used to color the nodes, and wherein the plurality of constraint edges connects a respective plurality of node pairs, the two nodes in the node pairs being different colors;

partition the nodes by color, wherein the partitioned nodes of the same color are independent of constraint edges;

map the partitions back to the graph to form a color-partitioned graph having at least two sub-domains; and

cross-associate all data that are part of a cluster.

2. The program product of claim 1, wherein the program instructions are further operable, when executed by the at least one processor, to optimize the partitioning with respect to an optimization function while ensuring that all constraint edges are cut by the partitioning by performing at least one of:

swap border nodes bordering on two sub-domains;

merge at least two sub-domains; and

split at least one sub-domain.

3. The program product of claim 1, wherein the program instructions are further operable, when executed by the at least one processor, to:

provide objective-edge weights for respective associated objective edges; and

minimize a function of the objective-edge weights cut by the sub-domains.

4. The program product of claim 1, wherein the program instructions are further operable, when executed by the at least one processor, to color the nodes in the graph by using a Modified Welsh-Powell algorithm.

5. The program product of claim 1, wherein the program instructions are further operable, when executed by the at least one processor, to partition the nodes by color using a multi-objective graph partitioner.

6. The program product of claim 1, wherein the program instructions are further operable, when executed by the at least one processor, to optimize data received from a plurality of cameras.

7. The program product of claim 6, wherein the program instructions to optimize the data received from the plurality of cameras are further operable, when executed by the at least one processor, to:

optimize generation of the plurality of objective edges based on a similarity quantification of the data;

optimize generation of the plurality of objective edges and generation of the plurality of constraint edges based on at least one of spatial location of the plurality of cameras, and a position of an object within a field-of-view of at least one of the plurality of cameras; and

optimize generation of the plurality of constraint edges based on temporal gaps in track lifespans.

8. The program product of claim 1, wherein the program instructions are further operable, when executed by the at least one processor, to generate the plurality of objective edges for the nodes in the graph, the plurality of objective edges being based on a quantified similarity of the data;

a spatial location and position within a field-of-view of at least one of the plurality of cameras;

temporal gaps in the cluster; and

social network data.

9. The program product of claim 1, wherein the program instructions are further operable, when executed by the at least one processor, to generate the plurality of constraint edges for the nodes in the graph, the plurality of constraint edges being based on at least one of:

temporal overlap within a camera;

temporal overlap across cameras having across non-overlapping field-of-views;

temporal locality constraints;

temporal constraints on dynamic tracks;

spatial constraints;

constraints derived from social network data;

constraints derived from financial data; and

constraints derived from other modes of data.

10. A method to extend the lifespan of a track of a moving object to overcome spatial non-locality and temporal non-locality by:

obtaining quantified similarity data based on data received from a plurality of cameras;

transforming the quantified similarity data to form a graph having a plurality of objective edges and a plurality of constraint edges;

coloring nodes in the graph, wherein at least two colors are used to color the nodes, and wherein the plurality of constraint edges connect a respective plurality of node pairs, the two nodes in the node pairs being different colors;

partitioning the nodes by color, wherein the partitioned nodes of the same color are independent of the plurality of constraint edges; and

mapping the partitions back to the graph to form a color-partitioned graph having at least two sub-domains.

11. The method of claim 10, further comprising coloring the nodes in the graph by using a Modified Welsh-Powell algorithm.

12. The method of claim 11, further comprising optimizing a clustering of the color-partitioned graph by with respect to an optimization function while ensuring that the plurality of constraint edges are cut by the partitioning by at least one of:

swapping border nodes bordering on two of the at least two sub-domains;

merging at least two of the at least two sub-domains; and

splitting at least one of the at least two sub-domain.

13. The method of claim 10, further comprising:

providing objective-edge weights for respective associated objective edges; and

minimizing a function of the objective-edge weights cut by the sub-domains.

14. The method of claim 10, further comprising partitioning nodes by color using a multi-objective graph partitioner.

15. The method of claim 10, further comprising:

creating an initial partitioning with one color; and

greedily growing the partition by adding nodes of the other colors.

16. The method of claim 10, wherein for two nodes in the graph connected by at least one of the plurality of objective edges and at least one of the plurality of constraint edges the method further comprises removing the at least one of the plurality of objective edges connecting the two nodes.

17. The method of claim 16, further comprising computing disconnected sub-domains within the graph based on the plurality of objective edges.

18. The method of claim 17, wherein for the computed disconnected sub-domains the method further comprises:

constructing a graph with a subset of nodes in the disconnected sub-domain that only has constraint edges and that has no objective edges to form a constraint-edge graph;

computing a coloring of the graph to form an initial partitioning of the sub-domain;

mapping the initial partitioning of the at least two colors together to form a color-partitioned graph; and

optimizing a clustering of the color-partitioned graph by a greedy algorithm.

19. The method of claim 18, further comprising growing the partitioning from the initial partitioning in a greedy manner based on the objective edges.

20. A program product for clustering multi-modal data including hard and soft cross-mode constraints, the program-product comprising a non-transitory processor-readable medium on which program instructions are embodied, wherein the program instructions are operable, when executed by at least one processor, to:

color nodes in a graph formed from quantified similarity data based on data received from a plurality of cameras, the colored nodes being connected by a plurality of objective edges and a plurality of constraint edges, wherein at least two colors are used to color the nodes, wherein the plurality of constraint edges connect a respective plurality of node pairs, and wherein the two nodes in the node pairs are different colors;

determine if at least one pair of nodes in the graph is connected by at least one objective edge and at least one constraint edge;

remove the at least one objective edge connecting the pair of nodes determined to be connected by at least one objective edge and at least one constraint edge;

compute all disconnected sub-domains within the graph based on the objective edges;

for the computed sub-domains, construct a graph from a subset of the nodes, wherein the subset of nodes includes nodes that only have constraint edges and that have no objective edges, wherein the constructed graph forms a constraint-edge graph;

compute a coloring of the graph to form an initial partitioning of the sub-domain;

map the initial partitionings together to form a color-partitioned graph in which edge-cuts of the objective edges are minimized; and

minimize a function of the objective-edge weights cut by the sub-domains.