Methods and apparatuses for interactive similarity searching, retrieval and browsing of video

• US 7,246,314 B2
• Filed: 06/03/2004
• Issued: 07/17/2007
• Est. Priority Date: 03/11/1999
• Status: Expired due to Fees

• Current Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.), Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.), Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Girgensohn, Andreas, Foote, Jonathan T., Wilcox, Lynn
• Primary Examiner(s): Nguyen; Cao (Kevin)
• Application Number:
  US10/859,832
• Publication Number:
  US 20040221237A1
• Time in Patent Office: 1,139 Days
• Field of Search: 715/700, 715/716, 715/723, 715/762, 715/765, 715/744, 715/835, 715/848, 715/953
• US Class Current: 715/700
• CPC Class Codes: G06F 16/7328 Query by example, e.g. a complete video frame or video sequence graphical querying G06F16/7335
• CPC Class Codes: G06F 16/738 Presentation of query results
• CPC Class Codes: G06F 16/7864 using domain-transform features, e.g. DCT or wavelet transform coefficients
• CPC Class Codes: G06V 20/48 Matching video sequences

Abstract

Methods for interactive selecting video queries consisting of training images from a video for a video similarity search and for displaying the results of the similarity search are disclosed. The user selects a time interval in the video as a query definition of training images for training an image class statistical model. Time intervals can be as short as one frame or consist of disjoint segments or shots. A statistical model of the image class defined by the training images is calculated on-the-fly from feature vectors extracted from transforms of the training images. For each frame in the video, a feature vector is extracted from the transform of the frame, and a similarity measure is calculated using the feature vector and the image class statistical model. The similarity measure is derived from the likelihood of a Gaussian model producing the frame. The similarity is then presented graphically, which allows the time structure of the video to be visualized and browsed. Similarity can be rapidly calculated for other video files as well, which enables content-based retrieval by example. A content-aware video browser featuring interactive similarity measurement is presented. A method for selecting training segments involves mouse click-and-drag operations over a time bar representing the duration of the video; similarity results are displayed as shades in the time bar. Another method involves selecting periodic frames of the video as endpoints for the training segment.

Claims

1. A method of performing a similarity search of a video, the method comprising the steps of

interactively defining by a user on a video browser a training video segment from the video, the training video segment comprising one or more video segments;

obtaining a reduced feature vectors for each video frames of the video;

training a statistical model using reduced feature vectors from the training video segment;

computing a similarity score for each video frame using the frame'"'"'s reduced feature vector and the statistical model; and

displaying one or more similarity scores and one or more frames of the video to the video browser.

2. A method as in claim 1, further comprising:

segmenting the video into similar and non-similar segments based upon the similarity scores.

3. A method as in claim 2,

wherein segmenting the video into similar and non-similar segments based upon the similarity scores comprises comparing the similarity scores to an interactively defined similarity threshold.

4. A method as in claim 1,

wherein obtaining a reduced feature vectors for each video frames comprises retrieving each of the reduced feature vectors from a precomputed feature vector database corresponding to the video.

5. A method as in claim 4,

wherein training a statistical model comprises retrieving each of the reduced feature vectors from a pretrained statistical model using the training video segment'"'"'s reduced feature vectors retrieved from the precomputed feature vector database.

6. A method as in claim 1,

wherein obtaining a reduced feature vectors for each video frames comprises transforming frames of the video using one of a Discrete Cosine Transform and a Hadamard transform.

7. A method as in claim 1,

wherein obtaining a reduced feature vector for each video frame includes obtaining features representing chromatic components of the frame and features representing luminance components of the frame.

8. A method as in claim 7,

wherein obtaining a reduced feature vector for each video frame includes obtaining fewer features representing chromatic components than features representing luminance components.

9. A method as in claim 1,

wherein obtaining a reduced feature vector for each video frame includes obtaining features representing red components of the frame, features representing green components of the frame, and features representing blue components of the frame.

10. A method as in claim 1,

wherein training a statistical model comprises training a Gaussian model. vectors retrieved from the precomputed feature vector database.

11. A method as in claim 1,

wherein displaying comprises displaying a timeline bar of similarity scores, the similarity scores depicted as bars within the timeline bar such that the darker the similarity score bar, the more similar the corresponding video frame is to the training video segment.

12. A method as in claim 1,

wherein displaying comprises providing interactive indexing to allow the user to jump to similar video frames in the video by skipping nonsimilar video frames in the video.

13. A method as in claim 1,

wherein obtaining a reduced feature vector for each video frame comprises reducing a number of less significant coefficients in each feature vector by using one of truncation, principal component analysis, and linear discriminant analysis.

14. A machine readable medium having instructions stored thereon that when executed by a processor are configured to cause the processor to perform the steps of:

interactively defining by a user on a video browser a training video segment from the video, the training video segment comprising one or more video segments;

obtaining reduced feature vectors for each video frames of the video;

training a statistical model using reduced feature vectors from the training video segment;

computing a similarity score for each video frame using the frame'"'"'s reduced feature vector and the statistical model; and

displaying one or more similarity scores and one or more frames of the video to the video browser.

15. A machine readable medium as in claim 14, further comprising instructions that when executed by the processor cause the processor to perform the step of:

segmenting the video into similar and non-similar segments based upon the similarity scores.

16. A machine readable medium as in claim 15,

wherein segmenting the video into similar and non-similar segments based upon the similarity scores comprises comparing the similarity scores to an interactively defined similarity threshold.

17. A machine readable medium as in claim 14,

wherein obtaining a reduced feature vectors for each video frames comprises retrieving each of the reduced feature vectors comprises retrieving each of the reduced feature vectors from a precomputed feature vector database corresponding to the video.

18. A machine readable medium as in claim 17,

wherein training a statistical model comprises retrieving each of the reduced feature vectors from a pretrained statistical model using the training video segment'"'"'s reduced feature vectors retrieved from the precomputed feature vector database.

19. A machine readable medium as in claim 14,

wherein obtaining a reduced feature vectors for each video frames comprises transforming frames of the video using one of a Discrete Cosine Transform and a Hadamard transform.

20. A machine readable medium as in claim 14,

wherein obtaining a reduced feature vector for each video frame includes obtaining features representing chromatic components of the frame and features representing luminance components of the frame.

21. A machine readable medium as in claim 20,

wherein obtaining a reduced feature vector for each video frame includes obtaining fewer features representing chromatic components than features representing luminance components.

22. A machine readable medium as in claim 14,

wherein obtaining a reduced feature vector for each video frame includes obtaining features representing red components of the frame, features representing green components of the frame, and features representing blue components of the frame.

23. A machine readable medium as in claim 14,

wherein training a statistical model comprises training a Gaussian model.

24. A machine readable medium as in claim 14,

wherein displaying comprises displaying a timeline bar of similarity scores, the similarity scores depicted as bars within the timeline bar such that the darker the similarity score bar, the more similar the corresponding video frame is to the training video segment.

25. A machine readable medium as in claim 14,

wherein displaying comprises providing interactive indexing to allow the user to jump to similar video frames in the video by skipping non-similar video frames in the video.

26. A machine readable medium as in claim 14,

wherein obtaining a reduced feature vector for each video frame comprises reducing a number of less significant coefficients in each feature vector by using one of truncation, principal component analysis, and linear discriminant analysis.

27. A system for performing a similarity search of a video, the system comprising:

a video browser that enables a user to interactively define a query video training segment from the video, the training video segment comprising one or more video segments; and

a model generation component configured to;

obtain a reduced feature vectors from each video frames of the video; and

train a statistical model using reduced feature vectors from the query video training segment; and

a score computation component configured to;

compute a similarity score for each video frame using the frame'"'"'s reduced feature vector and the statistical model; and

display the similarity scores and one or more frames of the video to the video browser.

28. A system as in claim 27, wherein the score computation component is further configured to:

segment the video into similar and non-similar segments based upon the similarity scores.

29. A system as in claim 28, wherein, when the video is segmented into similar and non-similar segments based upon the similarity scores, a comparison is performed of the similarity scores to an interactively defined similarity threshold.

30. A system as in claim 27, wherein the model generation component is further configured to:

retrieves each of the reduced feature vectors from a precomputed feature vector database corresponding to the video, in order to obtain reduced feature vectors.

31. A system as in claim 30,

wherein the trained statistical model comprises a retrieval of each of the reduced feature vectors from a pretrained statistical model using the training video segment'"'"'s reduced feature vectors retrieved from the precomputed feature vector database.

32. A system as in claim 27, wherein the model generation component is further configured to:

transforms frames of the video using one of a Discrete Cosine Transform and a Hadamard transform, in order to obtain reduced feature vectors.

33. A system as in claim 27, wherein the model generation component is further configured to:

obtain features representing chromatic components of the frame and features representing luminance components of the frame, in order to obtain reduced feature vectors.

34. A system as in claim 33, wherein the model generation component is further configured to:

obtain fewer features representing chromatic components than features representing luminance components, in order to obtain reduced feature vectors.

35. A system as in claim 27, wherein the model generation component is further configured to:

obtain features representing red components of the frame, features representing green components of the frame, and features representing blue components of the frame, in order to obtain reduced feature vectors.

36. A system as in claim 27,

wherein a trained statistical model comprises a trained Gaussian model.

37. A system as in claim 27,

wherein the display of similarity scores comprises displaying a timeline bar of similarity scores, the similarity scores depicted as bars within the timeline bar such that die darker the similarity score bar, the more similar the corresponding video frame is to the training video segment.

38. A system as in claim 27,

wherein the display of similarity scores comprises providing interactive indexing to allow the user to jump to similar video frames in the video by skipping non-similar video frames in the video.

39. A system as in claim 27,

wherein an obtained reduced feature vector for each video flame comprises a reduction of a number of less significant coefficients in each feature vector by using one of truncation, principal component analysis, and linear discriminant analysis.