System and method for object clustering and identification in video

• US 8,150,169 B2
• Filed: 09/16/2008
• Issued: 04/03/2012
• Est. Priority Date: 09/16/2008
• Status: Active Grant

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.), Viewdle, Inc.
• Original Assignee: Viewdle, Inc.
• Inventors: Kovtun, Ivan, Musatenko, Yuriy, Schlesinger, Mykhailo
• Primary Examiner(s): Seth, Manav
• Application Number:
  US12/211,493
• Publication Number:
  US 20100067745A1
• Time in Patent Office: 1,295 Days
• Field of Search: 382162-181, 382224-228
• US Class Current: 382/225
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 18/24147 Distances to closest patterns, e.g. nearest neighbour classification
• CPC Class Codes: G06V 10/761 Proximity, similarity or dissimilarity measures
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 20/40 in video content extracting overlay text G06V20/62; video retrieval G06F16/70; processing of video elementary streams in video servers H04N21/234; processing of video elementary streams in video clients H04N21/44
• CPC Class Codes: G06V 2201/10 Recognition assisted with metadata

Abstract

Embodiments of computer implemented methods and systems for object clustering and identification are described. One example embodiment includes receiving an unclustered video object, determining a first distance between the unclustered video object and an arbitrary representative video object, the arbitrary representative video object being selected from representative video objects, estimating distances between the unclustered video object and the representative video objects based on the first distance and precalculated distances between the arbitrary representative video object and the representative video objects, and, based on the estimated distances, selectively associating the unclustered video object with a video cluster, thereby producing a clustered video object.

Claims

1. A computer-implemented method comprising:

receiving an unclustered video object;

determining a first distance between the unclustered video object and an arbitrary representative video object, the arbitrary representative video object being selected from video objects representative of clusters comprising one or more clustered video objects;

determining estimate distances between the unclustered video object and the representative video objects based on the first distance and precalculated distances between the arbitrary representative video object and the representative video objects; and

based on the estimated distances, associating the unclustered video object with a cluster as a clustered video object.

2. The computer-implemented method of claim 1, wherein the estimated distances are determined based on a triangle inequality.

3. The computer-implemented method of claim 1, further comprising:

selecting one or more distances from the estimated distances within a predetermined threshold;

selecting one or more objects from the representative video objects associated with the estimated distances;

calculating distances between the unclustered video object and the representative video objects; and

associating the unclustered video object with a cluster based on the distances.

4. The computer-implemented method of claim 3, wherein the unclustered video object is associated with the cluster corresponding to a representative video object closest to the unclustered video object.

5. The computer-implemented method of claim 3, further comprising:

determining that no estimated distances are within the predetermined threshold;

creating a new cluster, based on the determination; and

associating the unclustered video object with the new cluster.

21. The computer-implemented method of claim 3, wherein associating the unclustered video object with the cluster based on the distances further comprises:

determining whether the distance between the unclustered video object and the representative video object closest to the unclustered video object is above a second threshold and below the first threshold; and

responsive to the unclustered video object being above the second threshold and below the first threshold, associating the unclustered video object with the cluster as a new representative object of the cluster.

22. The computer-implemented method of claim 3, wherein associating the unclustered video object with the cluster based on the distances further comprises:

determining whether the distance between the unclustered video object and the representative video object closest to the unclustered video object is below a second threshold, the second threshold below the first threshold; and

responsive to the unclustered video object being below the second threshold, increasing a presence rate of the representative video object.

23. The computer-implemented method of claim 22, further comprising:

analyzing presence rates for a plurality of representative objects in the cluster; and

filtering the plurality of representative objects based on their respective presence rates to determine a set of representative objects having the highest presence rates to represent the cluster.

6. A computer-implemented method comprising:

receiving an unidentified representative video object of a cluster for identification;

determining a first distance between the unidentified representative video object of the cluster and an arbitrary reference video object, the arbitrary reference video object being selected from reference video objects having associated identities;

determining estimate distances between the unidentified representative video object and the reference video objects based on the first distance and precalculated distances between the arbitrary reference video object and the reference video objects;

determining an identity of the unidentified representative video object based on the estimated distances, the identity of the unidentified representative video object being the identity of a reference video object; and

associating the identity of the reference video object with the unidentified representative video object and video objects associated with the cluster represented by the unidentified representative video object.

7. The computer-implemented method of claim 6, further comprising:

selecting the estimated distances within a predetermined threshold;

selecting further reference video objects associated with the estimated distances within the predetermined threshold;

calculating distances between the unidentified representative video object and the further reference video objects; and

associating the identity of a further reference video object with the unidentified representative video object and video objects associated with the cluster represented by the unidentified representative video object based on the distances.

8. The computer-implemented method of claim 6, wherein associating the identity of the reference video object with the unidentified representative video object and objects associated with the cluster represented by the unidentified representative video object further comprises associating metadata describing the identity of the reference video object with the cluster, the reference video object determined as being the closest reference video object to the unidentified representative video object.

9. A system comprising:

one or more processors and a non-transitory computer-readable storage medium storing executable computer program instructions that when executed cause the one or more processors to;

receive an unclustered video object;

determine a first distance between the unclustered video object and an arbitrary representative video object, the arbitrary representative video object being selected from video objects representative of clusters comprising one or more clustered video objects;

determine estimate distances between the unclustered video object and the representative video objects based on the first distance and precalculated distances between the arbitrary representative video object and the representative video objects; and

associate the unclustered video object with a video cluster as a clustered video object based on the estimated distances.

10. The system of claim 9, further comprising instructions that when executed cause the processors to:

select one or more distances from the estimated distances within a predetermined threshold;

select one or more video objects from the representative video objects associated with the estimated distances;

calculate distances between the unclustered video object and the representative video objects; and

associate the unclustered video object with a cluster based on the distances.

11. The system of claim 9, wherein the unclustered video object is associated with the cluster corresponding to a representative video object closest to the unclustered video object.

12. The system of claim 10, further comprising instructions that when executed cause the processors to:

determine that no estimated distances are within the predetermined threshold;

create a new cluster, based on the determination; and

associate the object with the new cluster.

13. A system comprising:

one or more processors and a non-transitory computer-readable storage medium storing executable computer program instructions that when executed cause the one or more processors to;

receive an unidentified representative video object of a cluster for identification;

determine a first distance between the unidentified representative video object of the cluster and an arbitrary reference video object, the arbitrary reference video object being selected from reference video objects having associated identities;

determining estimate distances between the unidentified representative video object and the reference video objects based on the first distance and precalculated distances between the arbitrary reference video object and the reference video objects;

determine an identity of the unidentified representative video object based on the estimated distances, the identity of the unidentified representative video object being the identity of a reference video object; and

associate the identity of the reference video object with the unidentified representative video object and video objects associated with the cluster represented by the unidentified representative video object.

14. The system of claim 13, further comprising instructions that when executed cause the processors to:

select the estimated distances within a predetermined threshold and to select the further reference video objects associated with the estimated distances;

calculate distances between the unidentified representative video object and the further reference video objects; and

associate the identity of a further reference video object with the unidentified representative video object and video objects associated with the cluster represented by the unidentified representative video object based on the distances.

15. The system of claim 13, wherein associating the identity of the reference video object with the unidentified representative video object and objects associated with the cluster represented by the unidentified representative video object further comprises associating metadata describing the identity of the reference video object with the cluster, the reference video object determined as being the closest reference video object to the unidentified representative video object.

16. The system of claim 13, further comprising instructions that when executed cause the processors to receive a manual identification of the unidentified representative video object.

17. A non-transitory computer-readable storage medium storing executable computer program instructions performing steps comprising:

receiving an unclustered video object;

determining a first distance between the unclustered video object and an arbitrary representative video object, the arbitrary representative video object being selected from video objects representative of clusters comprising one or more clustered video objects;

determining estimate distances between the unclustered video object and the representative video objects based on the first distance and precalculated distances between the arbitrary representative video object and the representative video objects; and

based on the estimated distances, associating the unclustered video object with a cluster as a clustered video object.

18. An apparatus comprising:

means for receiving an unclustered video object;

means for determining a first distance between the unclustered video object and an arbitrary representative video object, the arbitrary representative video object being selected from video objects representative of clusters comprising one or more clustered video objects;

means for determining estimate distances between the unclustered video object and the representative video objects based on the first distance and precalculated distances between the arbitrary representative video object and the representative video objects; and

means for associating the unclustered video object with a cluster as a clustered video object based on the estimated distances.

19. A non-transitory computer-readable storage medium storing executable computer program instructions performing steps comprising:

receiving an unidentified representative video object of a cluster for identification;

determining a first distance between the unidentified representative video object of the cluster and an arbitrary reference video object, the arbitrary reference video object being selected from reference video objects having associated identities;

determining estimate distances between the unidentified representative video object and the reference video objects based on the first distance and precalculated distances between the arbitrary reference video object and the reference video objects;

determining an identity of the unidentified representative video object based on the estimated distances, the identity of the unidentified representative video object being the identity of a reference video object; and

associating the identity of the reference video object with the unidentified representative video object and video objects associated with the cluster represented by the unidentified representative video object.

20. An apparatus comprising:

means for receiving an unidentified representative video object of a cluster for identification;

means for determining a first distance between the unidentified representative video object of the cluster and an arbitrary reference video object, the arbitrary reference video object being selected from reference video objects having associated identities;

means for determining estimate distances between the unidentified representative video object and the reference video objects based on the first distance and precalculated distances between the arbitrary reference video object and the reference video objects;

means for determining an identity of the unidentified representative video object based on the estimated distances, the identity of the unidentified video object being the identity of a reference video object; and

means for associating the identity of the reference video object with the unidentified representative video object and video objects associated with the cluster represented by the unidentified representative video object.