Color clustering for scene change detection and object tracking in video sequences
First Claim
1. A method for clustering input vectors of a current set of input vectors in a sequence of sets of input vectors, in which the current set of input vectors corresponds to a current image frame being processed and the sequence of sets of input vectors corresponds to a sequence of image frames, the method comprising the steps of:
- identifying a set of prototype vectors for use in allocating the input vectors of the current set of input vectors into a plurality of clusters, wherein there is a one to one correspondence between the set of prototype vectors and the plurality of clusters;
allocating the input vectors of the current set of input vectors into a plurality of clusters of input vectors, wherein during the step of allocating, the set of prototype vectors changes dynamically resulting in a modified set of prototype vectors after all input vectors of the current set of input vectors are allocated among the plurality of clusters, each cluster among the plurality of clusters having a number of allocated input vectors; and
after the step of allocating, discarding any prototype vector among the modified set of prototype vectors for which a corresponding cluster among the plurality of clusters has less than a specific number of allocated input vectors.
1 Assignment
0 Petitions
Accused Products
Abstract
Pixel data forming an image is clustered into groups of data of similar color. Pixels of approximately the same color form one cluster. A vigilance parameter determines how many clusters are derived and how wide a range of colors are included in a cluster. The process for allocating input vectors into clusters is based upon a minimum distance measure to multiple prototype vectors. A given image frame is allocated into clusters in an iterative process. A subset of clusters from an initial image frame are treated as featured clusters. The featured clusters correspond object(s). To track the object, input vectors in subsequent frames are tested to determine whether they correspond to a featured cluster. A scene change is detected when more than a prescribed number of prototype vectors have changed by more than a predetermined amount.
49 Citations
24 Claims
-
1. A method for clustering input vectors of a current set of input vectors in a sequence of sets of input vectors, in which the current set of input vectors corresponds to a current image frame being processed and the sequence of sets of input vectors corresponds to a sequence of image frames, the method comprising the steps of:
-
identifying a set of prototype vectors for use in allocating the input vectors of the current set of input vectors into a plurality of clusters, wherein there is a one to one correspondence between the set of prototype vectors and the plurality of clusters;
allocating the input vectors of the current set of input vectors into a plurality of clusters of input vectors, wherein during the step of allocating, the set of prototype vectors changes dynamically resulting in a modified set of prototype vectors after all input vectors of the current set of input vectors are allocated among the plurality of clusters, each cluster among the plurality of clusters having a number of allocated input vectors; and
after the step of allocating, discarding any prototype vector among the modified set of prototype vectors for which a corresponding cluster among the plurality of clusters has less than a specific number of allocated input vectors. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
iteratively repeating the steps of identifying, allocating and discarding for one of either of a maximum number of iterations or until the respective number of allocated input vectors for each cluster among the plurality of clusters stabilizes from a prior iteration to a current iteration, which ever occurs first.
-
-
3. The method of claim 1, further comprising the step of:
iteratively repeating the steps of identifying, allocating and discarding until the respective number of allocated input vectors for each cluster among the plurality of clusters stabilizes from a prior iteration to a current iteration.
-
4. The method of claim 3, in which during a first iteration for clustering input vectors of a first image frame among a sequence of image frames, there are no initial prototype vectors, and wherein for a first input vector of the first image frame, the first input vector is allocated to a new cluster, the prototype vector for the new cluster being set to the first input vector.
-
5. The method of claim 3, in which the modified set of prototype vectors after the step of discarding during one iteration is the set of prototype vectors identified in the identifying step of a subsequent iteration.
-
6. The method of claim 1, further comprising the step of:
iteratively repeating the steps of identifying, allocating and discarding for a prescribed number of iterations.
-
7. The method of claim 1, in which the step of allocating, comprises the step of changing the prototype vector for a given cluster of the plurality of clusters when an input vector is allocated to said given cluster by determining a statistical centroid of input vectors allocated to the given cluster.
-
8. The method of claim 1, in which the step of allocating, comprises the steps of:
-
deriving a vector distance magnitude between a current input vector of the current set of input vectors and each prototype vector of the set of prototype vectors;
identifying a minimum vector distance magnitude among the derived vector distance magnitudes;
identifying the prototype vector corresponding to the minimum vector distance magnitude;
when the minimum vector distance magnitude is less than a vigilance value, allocating the current input vector to a cluster corresponding to the identified prototype vector, and altering the identified prototype vector as a function of the current input vector;
when the minimum vector distance exceeds the vigilance value, allocating the current input vector to a new cluster, using the current input vector as a prototype vector for such new cluster, and including the prototype vector for said new cluster within the set of initial prototype vectors.
-
-
9. The method of claim 8, in which the method is repeated for subsequent image frames among the set of image frames, and further comprising the step of:
increasing the vigilance value after clustering input vectors of a first image frame among the sequence of image frames prior to clustering input vectors of a subsequent image frame among the sequence of image frames.
-
10. The method of claim 1, in which the method is repeated for subsequent image frames among the set of image frames, and further comprising the step of:
detecting a scene change among the sequence of image frames.
-
11. The method of claim 10, in which the step of detecting a scene change comprises the step of:
tracking a clustering change ratio for each image frame among the sequence of image frames.
-
12. The method of claim 1, in which the method is repeated for subsequent image frames among the set of image frames, and further comprising the step of:
-
identifying a feature cluster among the plurality of clusters achieved during allocating a current set of input vectors, wherein the feature cluster includes an indicator of presence of an object in the current image frame;
tracking the object through subsequent image frames among the sequence of image frames by monitoring said indicator while the method is repeated for subsequent image frames among the set of image frames.
-
-
13. The method of claim 12, in which a first value is used during the initial frame for the vigilance value, and in which the vigilance value is increased after clustering input vectors of the initial image frame during a common scene.
-
14. The method of claim 1, in which the method is repeated for subsequent image frames among the set of image frames, and further comprising the step of:
-
detecting a scene change among the sequence of image frames;
in response to a scene change detection, processing the current image frame as an initial image frame to reset the set of prototype vectors and reset the corresponding clusters.
-
-
15. A method for clustering input vectors of a current set of input vectors in a sequence of sets of input vectors, in which the current set of input vectors corresponds to a current image frame being processed and the sequence of sets of input vectors corresponds to a sequence of image frames, the method comprising the steps of:
-
identifying a set of prototype vectors for use in allocating the input vectors of the current set of input vectors into a plurality of clusters, wherein there is a one to one correspondence between the set of prototype vectors and the plurality of clusters;
allocating the input vectors of the current set of input vectors into a plurality of clusters of input vectors, wherein during the step of allocating, the set of prototype vectors changes dynamically resulting in a modified set of prototype vectors after all input vectors of the current set of input vectors are allocated among the plurality of clusters, each cluster among the plurality of clusters having a number of allocated input vectors;
after the step of allocating, discarding any prototype vector among the modified set of prototype vectors for which a corresponding cluster among the plurality of clusters has less than a specific number of allocated input vectors; and
iteratively repeating the steps of identifying, allocating and discarding until the respective number of allocated input vectors for each cluster among the plurality of clusters stabilizes from a prior iteration to a current iteration. - View Dependent Claims (16, 17, 18, 19, 20, 21)
deriving a vector distance magnitude between a current input vector of the current set of input vectors and each prototype vector of the set of prototype vectors;
identifying a minimum vector distance magnitude among the derived vector distance magnitudes;
identifying the prototype vector corresponding to the minimum vector distance magnitude;
when the minimum vector distance magnitude is less than a vigilance value, allocating the current input vector to a cluster corresponding to the identified prototype vector, and altering the identified prototype vector as a function of the current input vector;
when the minimum vector distance exceeds the vigilance value, allocating the current input vector to a new cluster, using the current input vector as a prototype vector for such new cluster, and including the prototype vector for said new cluster within the set of initial prototype vectors.
-
-
18. The method of claim 17, in which the method is repeated for subsequent image frames among the set of image frames, and further comprising the step of:
increasing the vigilance value after clustering input vectors of a first image frame among the sequence of image frames prior to clustering input vectors of a subsequent image frame among the sequence of image frames.
-
19. The method of claim 15, in which the method is repeated for subsequent image frames among the set of image frames, and further comprising the step of:
detecting a scene change among the sequence of image frames.
-
20. The method of claim 19, in which the step of detecting a scene change comprises the step of:
tracking a clustering change ratio for each image frame among the sequence of image frames.
-
21. The method of claim 15, in which the method is repeated for subsequent image frames among the set of image frames, and further comprising the step of:
-
identifying a feature cluster among the plurality of clusters achieved during allocating a current set of input vectors, wherein the feature cluster includes an indicator of presence of an object in the current image frame;
tracking the object through subsequent image frames among the sequence of image frames by monitoring said indicator while the method is repeated for subsequent image frames among the set of image frames.
-
-
22. A method for clustering color input vectors of a current set of color input vectors in a sequence of sets of color input vectors, in which the current set of color input vectors corresponds to color values of pixels within a current image frame being processed and the sequence of sets of color input vectors corresponds to color values of pixels within each one image frame of a sequence of image frames, the method comprising the steps of:
-
identifying a set of prototype vectors for use in allocating the color input vectors of the current set of color input vectors into a plurality of clusters, wherein there is a one to one correspondence between the set of prototype vectors and the plurality of clusters;
allocating the color input vectors of the current set of color input vectors into a plurality of clusters of color input vectors, wherein during the step of allocating the set of prototype vectors changes dynamically resulting in a modified set of prototype vectors after all color input vectors of the current set of color input vectors are allocated among the plurality of clusters, each cluster among the plurality of clusters having a number of allocated input vectors; and
after the step of allocating, discarding any prototype vector among the modified set of prototype vectors for which a corresponding cluster among the plurality of clusters has less than a specific number of allocated color input vectors. - View Dependent Claims (23, 24)
detecting a scene change among the sequence of image frames;
in response to a scene change detection, processing the current image frame as an initial image frame to reset the set of prototype vectors and reset the corresponding clusters.
-
-
24. The method of claim 23, in which the method is repeated for subsequent image frames among the set of image frames, and further comprising the step of:
-
identifying a feature cluster among the plurality of clusters achieved during allocating a current set of input vectors, wherein the feature cluster includes an indicator of presence of an object in the current image frame;
tracking the object through subsequent image frames among the sequence of image frames by monitoring said indicator while the method is repeated for subsequent image frames among the set of image frames;
in which a first value is used during the initial frame for the vigilance value, and in which the vigilance value is increased after clustering input vectors of the initial image frame during a common scene.
-
Specification