Determining feature vectors for video volumes

• US 9,177,208 B2
• Filed: 10/01/2012
• Issued: 11/03/2015
• Est. Priority Date: 11/04/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Sukthankar, Rahul, Yagnik, Jay
• Primary Examiner(s): Tran, Thai
• Assistant Examiner(s): BRANIFF, CHRISTOPHER
• Application Number:
  US13/633,062
• Publication Number:
  US 20130113877A1
• Time in Patent Office: 1,128 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/7837 using objects detected or recognised in the video content
• CPC Class Codes: G06F 16/7867 using information manually generated, e.g. tags, keywords, comments, title and artist information, manually generated time, location and usage information, user ratings
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: G06V 20/41 Higher-level, semantic clustering, classification or understanding of video scenes, e.g. detection, labelling or Markovian modelling of sport events or news items segmenting video sequences G06V20/49
• CPC Class Codes: G06V 20/46 Extracting features or characteristics from the video content, e.g. video fingerprints, representative shots or key frames

Abstract

A volume identification system identifies a set of unlabeled spatio-temporal volumes within each of a set of videos, each volume representing a distinct object or action. The volume identification system further determines, for each of the videos, a set of volume-level features characterizing the volume as a whole. In one embodiment, the features are based on a codebook and describe the temporal and spatial relationships of different codebook entries of the volume. The volume identification system uses the volume-level features, in conjunction with existing labels assigned to the videos as a whole, to label with high confidence some subset of the identified volumes, e.g., by employing consistency learning or training and application of weak volume classifiers. The labeled volumes may be used for a number of applications, such as training strong volume classifiers, improving video search (including locating individual volumes), and creating composite videos based on identified volumes.

Claims

1. A computer-implemented method comprising:

accessing a feature codebook comprising a set of representative feature vectors representing at least visual properties of digital videos;

identifying, in a plurality of digital videos, a plurality of candidate volumes representing spatio-temporal portions of the digital videos, wherein each of the candidate volumes corresponds to a contiguous sequence of spatial portions of video frames having a starting time and an ending time;

associating features with each candidate volume of a plurality of the identified candidate volumes, the associating comprising;

identifying a plurality of temporal segments of the candidate volume;

for each of the identified temporal segments;

determining a feature vector from at least visual properties of the temporal segment, and

associating with the temporal segment a representative feature vector from the feature codebook that is most similar to the feature vector;

determining features for the candidate volume, the features comprising temporal relationship features comprising, for each of a plurality of the representative feature vectors of the feature codebook, quantifications of occurrences of the representative feature vector within the candidate volume with respect to occurrences of other ones of the representative feature vectors within the candidate volume, the occurrences quantified according to a temporal operator;

assigning a label to the candidate volume using the determined temporal relationship features, the label indicating a particular object or action represented by the candidate volume; and

storing the label in association with the candidate volume.

2. The computer-implemented method of claim 1, wherein the temporal operator takes as input a first feature vector and a second feature vector and produces as output an indication of how often the first feature vector occurs before the second feature vector in the candidate volume.

3. The computer-implemented method of claim 1, the determined features for the candidate volume additionally comprising spatial relationship features, wherein the spatial relationship features comprise, for each of a plurality of the representative feature vectors of the feature codebook, quantifications of occurrences of the representative feature vector within the candidate volume with respect to occurrences of other ones of the representative feature vectors within the candidate volume, the occurrences quantified according to a spatial operator.

4. The computer-implemented method of claim 3, wherein the spatial operator takes as input a first feature vector and a second feature vector and produces as output an indication of how often the first feature vector occurs in a given spatial direction with respect to the second feature vector in the candidate volume, the given spatial direction comprising one of the group consisting of:

to the left,

to the right,

above,

below, and

centered on.

5. The computer-implemented method of claim 1, wherein the feature codebook is constructed by clustering feature vectors derived from a plurality of volumes from a plurality of digital videos, thereby obtaining representative feature vectors that constitute the feature codebook.

6. A computer-implemented method comprising:

identifying, in a digital video, a volume representing a spatio-temporal portion of the digital video, the volume corresponding to a contiguous sequence of spatial portions of frames of the video having a starting time and an ending time;

identifying a set of temporal segments of the volume, each segment associated with a time within the video and with a spatial portion of a frame of the video that corresponds to the associated time;

accessing a feature codebook comprising a set of representative feature vectors representing at least visual properties of digital videos;

for each of a plurality of the temporal segments;

deriving a feature vector from at least visual content of the temporal segment;

associating, with the temporal segment, a feature vector from the feature codebook that is most similar to the feature vector derived from the visual content;

for the volume, and for at least a first one of the representative feature vectors and a second one of the representative feature vectors;

determining temporal relationship features comprising quantifications of occurrences of the first one of the representative feature vectors within the candidate volume with respect to occurrences of the second one of the representative feature vectors within the candidate volume, the occurrences quantified according to a temporal operator; and

assigning a label to the volume using the determined temporal relationship features, the label indicating a particular object or action represented by the volume; and

storing a degree of the temporal relationship as a feature representing the volume.

7. The computer-implemented method of claim 6, further comprising computing a number of times that the first representative feature vector occurs before the second representative feature vector in the segments associated with the object, the computing comprising:

determining a first count corresponding to a number of times that the first representative feature vector is associated with one of the temporal segments before the second representative feature vector is associated with any of the temporal segments;

determining a second count corresponding to a number of times that the second representative feature vector is associated with one of the temporal segments after a last occurrence of the first representative feature vector in the temporal segments; and

computing a product of the first count and the second count.

8. The computer-implemented method of claim 6, the determined features for the candidate volume additionally comprising spatial relationship features comprising quantifications of a spatial relationship between the first one of the representative feature vectors within the candidate volume with respect to the second one of the representative feature vectors within the candidate volume, the spatial relationship quantifying a number of times that the first representative feature vector is associated with a spatial frame location that is of a given spatial direction with respect to a spatial frame location associated with the second representative feature vector.

9. The computer-implemented method of claim 8, wherein the given spatial direction represents whether the frame location associated with the first representative feature vector occurs in the given spatial direction with respect to the frame location associated with the second representative feature vector, the given spatial direction comprising one of the group consisting of:

to the left,

to the right,

above,

below, and

centered on.

10. The computer-implemented method of claim 8, further comprising computing the number of times that the first representative feature vector occurs in the given spatial direction with respect to the second representative feature vector in the segments associated with the object, the computing comprising:

for each of a plurality of the temporal segments associated with the object, identifying a centroid of the temporal segment; and

comparing locations of the identified centroids of the segments.

11. The computer-implemented method of claim 8, further comprising computing the number of times that the first representative feature vector is associated with a spatial frame location that is of the given spatial direction with respect to the spatial frame location associated with the second representative feature vector, the computing comprising:

for each of a first point and a second point within a frame of one of the temporal segments associated with the volume, associating one of the representative feature vectors with the point based on visual properties of the point; and

determining whether the first point has the given spatial direction with respect to the second point.

12. A non-transitory computer-readable storage medium storing executable computer program instructions comprising:

instructions for identifying, in a plurality of digital videos, a plurality of candidate volumes representing spatio-temporal segments of the digital videos, wherein each of the candidate volumes corresponds to a contiguous sequence of spatial portions of video frames having a starting time and an ending time, and potentially represents a discrete object or action within the video frames;

instructions for forming a feature codebook based on the identified plurality of candidate volumes, the forming comprising;

dividing each of a plurality of the candidate volume into temporal segments;

for each segment of the determined temporal segments, determining a segment feature vector representing at least visual properties of the segment; and

forming the feature codebook by clustering the segment feature vectors into a set of representative feature vectors;

instructions for associating features with each candidate volume of a plurality of the identified candidate volumes, the associating comprising;

dividing the candidate volume into temporal segments;

for each temporal segment;

determining a feature vector from at least visual properties of the temporal segment;

associating with the temporal segment a representative feature vector from the feature codebook that is most similar to the feature vector;

determining features for the candidate volume, the features comprising temporal relationship features determined by comparing the times of occurrence within the candidate volume of the representative feature vectors associated with the temporal segments, the time of occurrence of a representative feature vector being the time of occurrence of the temporal segment with which it is associated, wherein the temporal relationship features comprise, for each a plurality of the representative feature vectors of the feature codebook, quantifications of occurrences of the representative feature vector within the candidate volume with respect to occurrences of other ones of the representative feature vectors within the candidate volume, the occurrences quantified according to a temporal operator;

assigning a label to the candidate volume using the determined temporal relationship features, the label indicating a particular object or action represented by the candidate volume to which the label is assigned; and

storing the determined features in association with the candidate volume.

13. The non-transitory computer-readable storage medium of claim 12, wherein the temporal operator takes as input a first feature vector and a second feature vector and produces as output an indication of how often the first feature vector occurs before the second feature vector in the candidate volume.

14. The non-transitory computer-readable storage medium of claim 12, wherein the determined features for the candidate volume additionally comprise spatial relationship features determined by comparing spatial locations of occurrence, within the temporal segments of the candidate volume, of the representative feature vectors associated with the temporal segments, wherein the spatial relationship features comprise, for each of a plurality of the representative feature vectors of the feature codebook, quantifications of occurrences of the representative feature vector within the candidate volume with respect to occurrences of other ones of the representative feature vectors within the candidate volume, the occurrences quantified according to a spatial operator.

15. The non-transitory computer-readable storage medium of claim 14, wherein the spatial operator takes as input a first feature vector and a second feature vector and produces as output an indication of how often the first feature vector occurs in a given spatial direction with respect to the second feature vector in the candidate volume, the given spatial direction comprising one of the group consisting of:

to the left,

to the right,

above,

below, and

centered on.