SYSTEM AND METHOD FOR OBJECT CLUSTERING AND IDENTIFICATION IN VIDEO

• US 20100067745A1
• Filed: 09/16/2008
• Published: 03/18/2010
• Est. Priority Date: 09/16/2008
• Status: Active Grant

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.), Viewdle, Inc.
• Original Assignee: Viewdle, Inc.
• Inventors: Musatenko, Yuriy, Schlesinger, Mykhailo, Kovtun, Ivan
• Granted Patent: US 8,150,169 B2
• Time in Patent Office: Days
• US Class Current: 382/106
• 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 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 as a clustered video object.

2. The computer-implemented method of claim 1, wherein the estimating distances between the unclustered video object and the representative video objects are further based on a triangle inequality theorem.

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

selectively 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 the 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 determining; and

associating the unclustered video object with the new cluster.

6. A computer-implemented method comprising:

receiving an unidentified representative video object;

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

estimating 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;

identifying the unidentified representative video object, based on the estimated distances, as an identified representative video object; and

selectively associating metadata of the identified representative video object with every video object associated with a cluster represented by the identified 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;

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

selectively associating metadata, based on the distances, with every object of the cluster represented by the identified representative video object.

8. The computer-implemented method of claim 7, further comprising associating metadata of the reference video object with every object in the cluster represented by the identified representative video object, the reference video object being closest to the identified representative video object.

9. A system comprising:

a receiving module to receive an unclustered video object;

a triangle inequality module to determine 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;

a distance estimating module to 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

an associating module to selectively associate the unclustered video object with a video cluster based on the estimated distances as a clustered video object.

10. The system of claim 9, further comprising:

a selecting module to select one or more distances from the estimated distances within a predetermined threshold and to select one or more video objects from the representative video objects associated with the estimated distances;

the distance calculating module to calculate distances between the unclustered video object and the representative video objects; and

the associating module to selectively associate the unclustered video object with a cluster based on the distances.

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

12. The system of claim 9, further comprising:

a new cluster creating module to create a new cluster; and

the associating module to associate the object with the new cluster when no estimated distances are within the predetermined threshold.

13. A system comprising:

a receiving module to receive an unidentified representative video object;

a distance calculating module to determine a first distance between the unidentified representative video object and an arbitrary reference video object, the arbitrary reference video object being selected from reference video objects;

a triangle inequality module to 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;

an identifying module to identify the unidentified representative video object based on the estimated distances to produce an identified representative video object; and

an associating module to selectively associate metadata of the identified representative video object with every video object associated with a cluster represented by the identified representative video object.

14. The computer-implemented method of claim 13, further comprising:

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

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

the associating module to selectively associate metadata with every object of a cluster represented by the unidentified representative video object based on the distances.

15. The computer-implemented method of claim 13, wherein the associating module is to associate metadata of the reference video object with every object in a cluster represented by the unidentified representative video object, the reference video object being closest to the unidentified object.

16. The computer-implemented method of claim 13, further comprising:

a user interface to permit manual identification of the unidentified representative video object; and

the associating module to further associate every object in a cluster represented by the unidentified representative video object with metadata based on the identifying the unidentified representative video object when no estimated distances are within the predetermined threshold.

17. A computer-readable medium comprising instructions, which when executed by one or more processors, perform the following operations:

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 representative video objects;

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

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

18. An apparatus for suggesting items to a target user, the computer-implemented 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 representative video objects;

means for 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

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

19. A computer-readable medium comprising instructions, which when executed by one or more processors, perform the following operations:

receive an unidentified representative video object;

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

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;

identify the unidentified representative video object, based on the estimated distances, as an identified representative video object; and

selectively associate metadata of the identified representative video object with every video object associated with a cluster represented by the identified representative video object.

20. An apparatus for suggesting items to a target user, the computer-implemented apparatus comprising:

means for receiving an unidentified representative video object;

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

means for estimating 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 identifying the unidentified representative video object, based on the estimated distances, as an identified representative video object; and

means for selectively associating metadata of the identified representative video object with every video object associated with a cluster represented by the identified representative video object.