Method and apparatus for matching slides in video

• US 6,701,014 B1
• Filed: 06/14/2000
• Issued: 03/02/2004
• Est. Priority Date: 06/14/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Syeda-Mahmood, Tanveer Fathima
• Primary Examiner(s): Dastouri, Mehrdad
• Application Number:
  US09/593,205
• Time in Patent Office: 1,357 Days
• Field of Search: 382/163, 382/165, 382/190, 382/195, 382/199, 382/203, 382/209, 382/217, 382/218, 382/224, 345/719, 345/721, 345/723, 707/3, 707/6
• US Class Current: 382/199
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06V 10/757 Matching configurations of points or features
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

The present invention performs a method for matching slides to video comprising, generating keyframes from the video, extracting geometric keyframe features from the keyframes and geometric slide features from the slides, and matching the geometric slide features and the geometric keyframe features.

Claims

1. A method for matching slides to video comprising:

generating keyframes from said video;

extracting geometric keyframe features from said keyframes and geometric slide features from said slides by reducing a structure of said geometric keyframe features and said geometric slide features to a corresponding set of affine coordinates;

placing said affine coordinates in a search tree; and

matching said geometric slide features and said geometric keyframe features by indexing said search tree and making comparisons of said geometric slide features and said geometric keyframe features through any of natural language queries and graphic searching.

2. The method in claim in claim 1, further comprising identifying background matching regions in said keyframes having colors matching colors of backgrounds in said slides.

3. The method in claim 2, wherein said extracting of said geometric keyframe features is performed only in said background matching regions.

4. The method in claim 1, wherein said matching identifies which slide of said slides has a highest number of geometric slide features matching geometric keyframe features in a keyframe of said keyframes.

5. The method in claim 1, wherein said extracting includes:

identifying changes in image intensity as edges;

forming curves connecting said edges;

identifying corners where said curves change direction;

grouping said curves into curve-groups; and

designating a sequence of three consecutive features in each of said curve-groups as basis triples.

6. The method in claim 5, wherein said matching comprises:

computing coordinates of said basic triples; and

identifying which slide of said slides has a highest number of basis triples matching basis triples in a keyframe of said keyframes.

7. The method in claim 1, wherein said generating of said keyframes comprises:

dividing said video into portions based upon scene changes; and

selecting one frame from each portion of said video as a keyframe.

8. A method identifying slides that appear in a video comprising:

generating keyframes from said video;

identifying background matching regions in said keyframes having colors matching colors of backgrounds in said slides;

extracting geometric keyframe features from said background matching regions in said keyframes and geometric slide features from said slides by reducing a structure of said geometric keyframe features and said geometric slide features to a corresponding set of affine coordinates;

placing said affine coordinates in a search tree; and

matching said geometric slide features and said geometric keyframe features by indexing said search tree and making comparisons of said geometric slide features and said geometric keyframe features through any of natural language queries and graphic searching.

9. The method in claim 8, wherein said extracting of said geometric keyframe features is performed only in said background matching regions.

10. The method in claim 8, wherein said matching identifies which slide of said slides has a highest number of geometric slide features matching geometric keyframe features in a keyframe of said keyframes.

11. The method in claim 8, wherein said extracting includes:

identifying changes in image intensity as edges;

forming curves connecting said edges;

identifying corners where said curves change direction;

grouping said curves into curve-groups; and

designating a sequence of three consecutive features in each of said curve-groups as basis triples.

12. The method in claim 11, wherein said matching comprises:

computing coordinates of said basis triples; and

identifying which slide of said slides has a highest number of basis triples matching basis triples in a keyframe of said keyframes.

13. The method in claim 8, wherein said generating of said keyframes comprises:

dividing said video into portions based upon scene changes; and

selecting one frame from each portion of said video as a keyframe.

14. A program storage device readable by machine tangibly embodying a program of instructions executable by the machine to perform a method for matching slides to video, said method comprising:

extracting geometric keyframe features from said keyframes and geometric slide features from said slides by reducing a structure of said geometric keyframe features and said geometric slide features to a corresponding set of affine coordinates;

placing said affine coordinates in a search tree; and

matching said geometric slide features and said geometric keyframe features by indexing said search tree and making comparisons of said geometric slide features and said geometric keyframe features through any of natural language queries and graphic searching.

15. The program storage device in claim 14, further comprising identifying background matching regions in said keyframes having colors matching colors of backgrounds in said slides.

16. The program storage device in claim 15, wherein said extracting of said geometric keyframe features is performed only in said background matching regions.

17. The program storage device in claim 14, wherein said matching identifies which slide of said slides has a highest number of geometric slide features matching geometric keyframe features in a keyframe of said keyframes.

18. The program storage device in claim 14, wherein said extracting includes:

identifying changes in image intensity as edges;

forming curves connecting said edges;

identifying corners where said curves change direction;

grouping said curves into curve-groups; and

designating a sequence of three consecutive features in each of said curve-groups as basis triples.

19. The program storage device in claim 18, wherein said matching comprises:

computing coordinates of said basis triples; and

identifying which slide of said slides has a highest number of basis triples matching basis triples in a keyframe of said keyframes.

20. The program storage device in claim 14, wherein said generating of said keyframes comprises:

dividing said video into portions based upon scene changes; and

selecting one frame from each portion of said video as a keyframe.

21. A method for matching slides to video comprising:

generating keyframes from said video;

extracting geometric keyframe features from said keyframes and geometric slide features from said slides; and

matching said geometric slide features and said geometric keyframe features, wherein said extracting includes;

identifying changes in image intensity as edges;

forming curves connecting said edges;

identifying corners where said curves change direction;

grouping said curves into curve-groups; and

designating a sequence of three consecutive features in each of said curve-groups as basis triples, and wherein said matching comprises;

computing coordinates of said basis triples; and

identifying which slide of said slides has a highest number of basis triples matching basis triples in a keyframe of said keyframes.

22. A method identifying slides that appear in a video comprising:

generating keyframes from said video;

identifying background matching regions in said keyframes having colors matching colors of backgrounds in said slides;

extracting geometric keyframe features from said background matching regions in said keyframes and geometric slide features from said slides; and

matching said geometric slide features and said geometric keyframe features, wherein said extracting includes;

identifying changes in image intensity as edges;

forming curves connecting said edges;

identifying corners where said curves change direction;

grouping said curves into curve-groups; and

designating a sequence of three consecutive features in each of said curve-groups as basis triples, and wherein said matching comprises;

computing coordinates of said basis triples; and

identifying which slide of said slides has a highest number of basis triples matching basis triples in a keyframe of said keyframes.

23. A program storage device readable by machine tangibly embodying a program of instructions executable by the machine to perform a method for matching slides to video, said method comprising:

generating keyframes from said video;

extracting geometric keyframe features from said keyframes said geometric slide features from said slides; and

matching said geometric slide features and said geometric keyframe features, wherein said extracting includes;

identifying changes in image intensity as edges;

forming curves connecting said edges;

identifying corners where said curves change direction;

grouping said curves into curve-groups; and

designating a sequence of three consecutive features in each of said curve-groups as basis triples, and wherein said matching comprises;

computing coordinates of said basis triples; and

identifying which slide of said slides has a highest number of basis triples matching basis triples in a keyframe of said keyframes.