Method and Apparatus for Multi-Dimensional Content Search and Video Identification

Patent metadata

Field	Value
Publication number	US-2017192980-A1
Application number	US-201615290364-A
Country	US
Kind code	A1
Filing date	Oct 11, 2016
Priority date	Jun 18, 2007
Publication date	Jul 6, 2017
Grant date	—

Abstract

A multi-dimensional database and indexes and operations on the multi-dimensional database are described which include video search applications or other similar sequence or structure searches. Traversal indexes utilize highly discriminative information about images and video sequences or about object shapes. Global and local signatures around keypoints are used for compact and robust retrieval and discriminative information content of images or video sequences of interest. For other objects or structures relevant signature of pattern or structure are used for traversal indexes. Traversal indexes are stored in leaf nodes along with distance measures and occurrence of similar images in the database. During a sequence query, correlation scores are calculated for single frame, for frame sequence, and video clips, or for other objects or structures.

First claim

1 .- 20 . (canceled)

21 . A method of generating a likelihood score of a query video sequence matching an original video sequence, the method comprising:
generating a similarity measure between frames of a query video sequence and an original video sequence based on frame similarity scores that exceed a threshold, wherein the original video is an entry in a video database; generating a time correlation between features extracted from frames having different frame numbers in the query video sequence and in the original video sequence; and generating a correlation score between the original video sequence and the query video sequence by using a combination of the similarity measure and the time correlation to identify the likelihood score of the query video sequence matching the original video sequence.

22 . The method of claim 21 , wherein signature pairs selected from the original video and the query video that match determine a starting frame for the original video sequence.

23 . The method of claim 21 , wherein the video database is stored on a portable device.

24 . The method of claim 21 further comprising:
determining the threshold based on the length of a matching original video sequence.

25 . The method of claim 21 further comprising:
determining the threshold from information extracted from the original video sequence that matches the query video sequence.

26 . The method of claim 21 further comprising:
determining the threshold experimentally for a sequence window length of a matching original video sequence.

27 . The method of claim 21 , wherein frames of the query video sequence are processed to generate signatures and for each of the signatures generate a traversal index to provide a direct hash address to a leaf node storing information regarding a region of interest in a frame of the query video sequence.

28 . The method of claim 21 , wherein the query video sequence comprises a sequence of signatures and traversal indexes used to search for likely matching frames of the original video sequence.

29 . The method of claim 21 , wherein the query video sequence comprises a sequence of signatures with an associated traversal index, the traversal index is generated from a combination of two subsequent signatures selected from two subsequent frames.

30 . A method of generating a likelihood score for matching frames of a query video and an original video, the method comprising:
generating a similarity measure between a query video and an original video selected from a video database, the generated similarity measure based on individual frame similarity scores that exceed a first threshold, wherein the original video is an entry in a video database; generating a time correlation using different starting frame numbers for the query video sequence and the original video sequence to find a starting frame and an original video sequence with highest correlation to the query video sequence; generating a correlation score between the original video sequence and the query video sequence by using a combination of the similarity measure and the time correlation to identify the likelihood score of the query video sequence matching the original video sequence.

31 . The method of claim 30 further comprising:
performing, for a selected query video signature, a search in a video database to identify a candidate list of nearest video frames from video sequences stored in the video database; and
selecting from the candidate list the starting frame and the original video sequence that exceeds a second threshold.

32 . The method of claim 30 , wherein frames of the query video sequence are processed to generate signatures and for each of the signatures generate a traversal index to provide a direct hash address to a leaf node storing information regarding a region of interest in a frame of the query video sequence.

33 . The method of claim 30 further comprising:
determining the threshold from information extracted from the original video sequence that matches the query video sequence.

34 . The method of claim 30 , wherein the video database is stored on a portable device.

35 . The method of claim 30 , wherein the correlation score is generated by a portable device.

36 . A processing system for generating a likelihood score of a query video sequence matching an original video sequence, the processing system comprising:
a video database located on a portable device that stores a plurality of original videos; and a processor configured to generate a similarity measure between frames of a query video sequence and an original video sequence, selected from the video database, based on frame similarity scores that exceed a threshold, to generate a time correlation between features extracted from frames having different frame numbers in the query video sequence and in the original video sequence, and to generate a correlation score between the original video sequence and the query video sequence by using a combination of the similarity measure and the time correlation to identify the likelihood score of the query video sequence matching the original video sequence.

37 . The processing system of claim 36 , wherein the processor is further configured to determine the threshold from information extracted from the original video sequence that matches the query video sequence.

38 . The processing system of claim 36 , wherein the processor is further configured to process frames of the query video sequence to generate signatures, and
to generate a traversal index from each of the generated signatures to provide a direct hash address to a leaf node storing information regarding a region of interest in a frame of the query video sequence.

39 . The processing system of claim 36 , wherein the processor is further configured to search for likely matching frames of a video sequence stored in the video database using a sequence of signatures and traversal indexes generated from frames of the query video sequence, and wherein the query video sequence comprises a sequence of signatures and traversal indexes used to search for likely matching frames of the original video sequence.

40 . The processing system of claim 36 , wherein the processor is further configured to provide video fingerprinting and search operations on video sequences selected from the video database.

Assignees

• Gracenote Inc

Inventors

• Pereira Jose Pio
• Stojancic Mihailo M
• Merchant Shashank

Classifications

• G06F16/7837 Primary

  using objects detected or recognised in the video content · CPC title

• G06T7/10

  Segmentation; Edge detection (motion-based segmentation G06T7/215) · CPC title

• G06F16/7854

  using shape (G06F16/7837 takes precedence) · CPC title

• G06T7/12

  Edge-based segmentation · CPC title

• G06F16/7847

  using low-level visual features of the video content · CPC title