Adaptive voting experts for incremental segmentation of sequences with prediction in a video surveillance system
View Patent ↗A sequence layer in a machine-learning engine configured to learn from the observations of a computer vision engine. In one embodiment, the machine-learning engine uses the voting experts to segment adaptive resonance theory (ART) network label sequences for different objects observed in a scene. The sequence layer may be configured to observe the ART label sequences and incrementally build, update, and trim, and reorganize an ngram trie for those label sequences. The sequence layer computes the entropies for the nodes in the ngram trie and determines a sliding window length and vote count parameters. Once determined, the sequence layer may segment newly observed sequences to estimate the primitive events observed in the scene as well as issue alerts for inter-sequence and intra-sequence anomalies.
1. A computer-implemented method for analyzing a scene depicted in an input stream of video frames captured by a video camera, the method comprising:
receiving a plurality of sequences, wherein each sequence stores an ordered string of labels assigned to clusters in an adaptive resonance theory (ART) network, wherein the ART network clusters nodes of a self-organizing map (SOM), and wherein the SOM is generated by mapping, to nodes of the SOM, kinematic data vectors generated for foreground objects detected in the input stream of video frames;
generating, from the plurality sequences, an ngram trie to a specified depth, wherein the ngram trie includes a node for each subsequence present in the plurality of sequences, up to the specified depth;
determining, for each node in the ngram trie, an entropy measure based on a count of how many times the subsequence represented by the node appears in the plurality of sequences;
receiving a first sequence; and
determining, in the first sequence, one or more segments, based on the determined entropies.
2. The computer-implemented method of claim 1 , further comprising, prior to generating the ngram trie, deleting any repeated subsequences in the ordered string of labels in each of the plurality of sequences, up to a specified length.
3. The computer-implemented method of claim 1 , wherein determining, in the first sequence, one or more segments, comprises:
evaluating subsequences in a sliding window of length (L), wherein an internal entropy expert and a boundary entropy expert each vote a position in each sliding window subsequence at which to split the sliding window sequence; and
inducing a segment boundary at each position in the first sequence that receives at least a number of votes satisfying a vote count threshold (V).
4. The computer-implemented method of claim 3 , wherein:
the internal entropy expert votes to minimize internal entropy by selecting a position which minimizes internal entropy in each respective sliding window sequence, based on the determined entropies; and
the boundary entropy expert votes by selecting a position in each respective sliding window that maximizes entropy between segments in the sliding window subsequence.
5. The computer-implemented method of claim 3 , further comprising, determining the sliding window length (L) as
L
=
⌈
arg
max
(
H
^
I
)
+
arg
max
(
H
^
B
)
2
⌉
,
wherein Ĥ I and Ĥ B , represent a standardized entropy value for the entropy measure determined for each node in the ngram trie and argmax( ) returns a level of the node in the trie with the greatest entropy values for Ĥ I and Ĥ B .
6. The computer-implemented method of claim 3 , wherein the vote count threshold (v) is determined as follows
V
=
⌈
∑
i
=
1
n
arg
max
(
H
^
I
)
i
+
arg
max
(
H
^
B
)
i
2
n
⌉
,
wherein Ĥ I and Ĥ B , represent a standardized entropy value for the entropy measure determined for each node in the ngram trie, wherein n represents a total number of branches in the ngram trie and argmax( ) returns a level of the node in the trie with the greatest entropy values for Ĥ I and Ĥ B .
7. The computer-implemented method of claim 1 , further comprising:
receiving an partial sequence of ART network labels generated from a set of kinematic vectors derived for a foreground object being tracked from frame-to-frame in the input stream of video frames, wherein the set of kinematic vectors are mapped to nodes of the SOM and clustered by the ART network; and
predicting a next element of the second sequence based on the determined entropies in the ngram trie.
8. The computer-implemented method of claim 1 , further comprising:
accumulating a threshold number of segments from observations of one or more foreground objects tracked from frame-to-frame in the input stream of video frames;
updating the ngram trie using the accumulated segments;
determining, for each node in the ngram trie, an updated entropy measure.
9. The computer-implemented method of claim 1 , further comprising:
upon determining the ngram trie exceeds a specified number of nodes, trimming one or more nodes from the ngram trie, based on the counts,
determining, for each node remaining in the ngram trie, an updated entropy measure.
10. The computer-implemented method of claim 1 , further comprising:
combining a first label of the ordered string of labels and a second label of the ordered string of labels to provide;
reorganizing the ngram trie to replace each instance of the first label and the second label with a label representing the combined first and second labels; and
determining, for each node in the ngram trie, an updated entropy measure.
11. The computer-implemented method of claim 1 , wherein the plurality of kinematic data vectors generated for foreground objects are generated for one or more foreground objects classified as depicting a common object type.
12. The computer-implemented method of claim 11 , wherein the one or more foreground objects are classified based on a plurality of micro features derived from observations of the foreground objects in the input stream of video frames.
13. A computer-readable storage medium containing a program, which when executed on a processor, performs an operation for analyzing a scene depicted in an input stream of video frames captured by a video camera, the operation comprising:
receiving a plurality of sequences, wherein each sequence stores an ordered string of labels assigned to clusters in an adaptive resonance theory (ART) network, wherein the ART network clusters nodes of a self-organizing map (SOM), and wherein the SOM is generated by mapping, to nodes of the SOM, kinematic data vectors generated for foreground objects detected in the input stream of video frames;
generating, from the plurality sequences, an ngram trie to a specified depth, wherein the ngram trie includes a node for each subsequence present in the plurality of sequences, up to the specified depth;
determining, for each node in the ngram trie, an entropy measure based on a count of how many times the subsequence represented by the node appears in the plurality of sequences;
receiving a first sequence; and
determining, in the first sequence, one or more segments, based on the determined entropies.
14. The computer-readable storage medium of claim 13 , wherein the operation further comprises, prior to generating the ngram trie, deleting any repeated subsequences in the ordered string of labels in each of the plurality of sequences, up to a specified length.
15. The computer-readable storage medium of claim 13 , wherein determining, in the first sequence, one or more segments, comprises:
evaluating subsequences of the first sequence using a sliding window of length (L), wherein an internal entropy expert and a boundary entropy expert each vote a position in each sliding window subsequence at which to split the sliding window sequence; and
inducing a segment boundary at each position in the first sequence that receives at least a number of votes satisfying a vote count threshold (V).
16. The computer-readable storage medium of claim 15 , wherein the operation further comprises, determining the sliding window length (L) as
L
=
⌈
arg
max
(
H
^
I
)
+
arg
max
(
H
^
B
)
2
⌉
,
wherein Ĥ I and Ĥ B , represent a standardized entropy value for the entropy measure determined for each node in the ngram trie and argmax( ) returns a level of the node in the trie with the greatest entropy values for Ĥ I and Ĥ B .
17. The computer-readable storage medium of claim 15 , wherein the vote count threshold (v) is determined as follows
V
=
⌈
∑
i
=
1
n
arg
max
(
H
^
I
)
i
+
arg
max
(
H
^
B
)
i
2
n
⌉
,
wherein Ĥ I and Ĥ B , represent a standardized entropy value for the entropy measure determined for each node in the ngram trie, wherein n represents a total number of branches in the ngram trie and argmax( ) returns a level of the node in the trie with the greatest entropy values for Ĥ I and Ĥ B .
18. The computer-readable storage medium of claim 13 , wherein the operation further comprises:
receiving an partial sequence of ART network labels generated from a set of kinematic vectors derived for a foreground object being tracked from frame-to-frame in the input stream of video frames, wherein the set of kinematic vectors are mapped to nodes of the SOM and clustered by the ART network; and
predicting a next element of the partial sequence based on the determined entropies in the ngram trie.
19. The computer-readable storage medium of claim 13 , wherein the operation further comprises:
accumulating a threshold number of segments from observations of one or more foreground objects tracked from frame-to-frame in the input stream of video frames;
updating the ngram trie using the accumulated segments;
determining, for each node in the ngram trie, an updated entropy measure.
20. The computer-readable storage medium of claim 13 , wherein the operation further comprises:
upon determining the ngram trie exceeds a specified number of nodes, trimming one or more nodes from the ngram trie; and
determining, for each node remaining in the ngram trie, an updated entropy measure.
21. A system, comprising:
a video input source configured to provide an input stream of video frames captured by a video camera, each depicting a scene;
a processor; and
a memory containing a program, which, when executed on the processor is configured to perform an operation for analyzing the scene depicted in the input stream of video frames, the operation comprising:
receiving a plurality of sequences, wherein each sequence stores an ordered string of labels assigned to clusters in an adaptive resonance theory (ART) network, wherein the ART network clusters nodes of a self-organizing map (SOM), and wherein the SOM is generated by mapping, to nodes of the SOM, kinematic data vectors generated for foreground objects detected in the input stream of video frames,
generating, from the plurality sequences, an ngram trie to a specified depth, wherein the ngram trie includes a node for each subsequence present in the plurality of sequences, up to the specified depth,
determining, for each node in the ngram trie, an entropy measure based on a count of how many times the subsequence represented by the node appears in the plurality of sequences,
receiving a first sequence, and
determining, in the first sequence, one or more segments, based on the determined entropies.
22. The system of claim 21 , wherein determining, in the first sequence, one or more segments, comprises:
evaluating subsequences of the first sequence using a sliding window of length (L), wherein an internal entropy expert and a boundary entropy expert each vote a position in each sliding window subsequence at which to split the sliding window sequence; and
inducing a segment boundary at each position in the first sequence that receives at least a number of votes satisfying a vote count threshold (V).
23. The system of claim 22 , wherein the operation further comprises, determining the sliding window length (L) as
L
=
⌈
arg
max
(
H
^
I
)
+
arg
max
(
H
^
B
)
2
⌉
,
wherein Ĥ I and Ĥ B , represent a standardized entropy value for the entropy measure determined for each node in the ngram trie and argmax returns and argmax( ) returns a level of the node in the trie with the greatest entropy values for Ĥ I and Ĥ B .
24. The system of claim 22 , wherein the vote count threshold (v) is determined as follows
V
=
⌈
∑
i
=
1
n
arg
max
(
H
^
I
)
i
+
arg
max
(
H
^
B
)
i
2
n
⌉
,
wherein Ĥ I and Ĥ B , represent a standardized entropy value for the entropy measure determined for each node in the ngram trie, wherein n represents a total number of branches in the ngram trie and argmax( ) returns a level of the node in the trie with the greatest entropy values for Ĥ I and Ĥ B .
25. The system of claim 21 , wherein the operation further comprises:
receiving an partial sequence of ART network labels generated from a set of kinematic vectors derived for a foreground object being tracked from frame-to-frame in the input stream of video frames, wherein the set of kinematic vectors are mapped to nodes of the SOM and clustered by the ART network; and
predicting a next element of the partial sequence based on the determined entropies in the ngram trie.