Method and apparatus for multi-dimensional content search and video identification
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.
1. A computer-implemented method comprising:
obtaining, by a processor, a query index that is derived from features of a frame of a query video;
determining, by the processor, that a distance measure between the query index and a candidate database index of a reference database satisfies a threshold condition, wherein the candidate database index corresponds to a frame of an original video;
based on the distance measure satisfying the threshold condition, determining, by the processor, a first time correlation score based on a comparison of signatures of a sequence of frames of the query video with respective signatures of a first sequence of frames of the original video, the first sequence of frames starting at a first start frame position;
determining, by the processor, a second time correlation score based on a comparison of the signatures of the sequence of frames of the query video with respective signatures of a second sequence of frames of the original video, the second sequence of frames starting at a second start frame position that is offset from the first start frame position; and
based at least on the second time correlation score, providing, by the processor, a results list that includes a name of the original video.
2. The computer-implemented method of claim 1 , wherein the query index corresponds to a multi-dimensional query signature of the frame of the query video, wherein the candidate database index corresponds to a multi-dimensional database signature of the frame of the original video, and wherein the distance measure is a sum of differences in dimensions between the multi-dimensional query signature and the multi-dimensional database signature.
3. The computer-implemented method of claim 1 , further comprising:
determining that the second time correlation score is greater than the first time correlation score; and
based on the second time correlation score being greater than the first time correlation score, selecting the second start frame position as an identified start frame position, wherein the results list further includes the identified start frame position.
4. The computer-implemented method of claim 1 , wherein the name of the original video is stored at a leaf node corresponding to the candidate database index, and wherein the leaf node is addressable by the candidate database index.
5. The computer-implemented method of claim 1 , wherein the query index corresponds to a global signature of a region of interest of the frame of the query video, wherein the region of interest comprises multiple sectors, and wherein the global signature represents features of respective sectors of the multiple sectors.
6. The computer-implemented method of claim 5 , wherein the region of interest is a rectangular grid.
7. The computer-implemented method of claim 1 , wherein the query index corresponds to local features of an area around a keypoint of the frame of the query video.
8. The computer-implemented method of claim 1 , further comprising using the query index as a traversal index so as to identify candidate database indexes of the reference database that are within a range of the query index, wherein the candidate database index is one of the candidate database indexes.
9. The computer-implemented method of claim 1 , further comprising determining the second start frame position based on the first start frame position.
10. A multi-dimensional content search system comprising:
one or more processors; and
a computer-readable medium having stored therein instructions that are executable by the one or more computers to cause the multi-dimensional content search system to perform functions comprising:
obtaining a query index that is derived from features of a frame of a query video,
determining that a distance measure between the query index and a candidate database index of a reference database satisfies a threshold condition, wherein the candidate database index corresponds to a frame of an original video,
based on the distance measure satisfying the threshold condition, determining a first time correlation score based on a comparison of signatures of a sequence of frames of the query video with respective signatures of a first sequence of frames of the original video, the first sequence of frames starting at a first start frame position,
determining a second time correlation score based on a comparison of the signatures of the sequence of frames of the query video with respective signatures of a second sequence of frames of the original video, the second sequence of frames starting at a second start frame position that is offset from the first start frame position, and
based at least on the second time correlation score, providing a results list that includes a name of the original video.
11. The multi-dimensional content search system of claim 10 , wherein the query index corresponds to a multi-dimensional query signature of the frame of the query video, wherein the candidate database index corresponds to a multi-dimensional database signature of the frame of the original video, and wherein the distance measure is a sum of differences in dimensions between the multi-dimensional query signature and the multi-dimensional database signature.
12. The multi-dimensional content search system of claim 10 , wherein the functions further comprise:
determining that the second time correlation score is greater than the first time correlation score; and
based on the second time correlation score being greater than the first time correlation score, selecting the second start frame position as an identified start frame position, wherein the results list further includes the identified start frame position.
13. The multi-dimensional content search system of claim 10 , wherein the name of the original video is stored at a leaf node corresponding to the candidate database index, and wherein the leaf node is addressable by the candidate database index.
14. The multi-dimensional content search system of claim 10 , wherein the query index corresponds to a global signature of a region of interest of the frame of the query video, wherein the region of interest comprises multiple sectors, and wherein the global signature represents features of respective sectors of the multiple sectors.
15. The multi-dimensional content search system of claim 14 , wherein the region of interest is a rectangular grid.
16. The multi-dimensional content search system of claim 10 , wherein the query index corresponds to local features of an area around a keypoint of the frame of the query video.
17. A non-transitory computer-readable medium having stored therein instructions that are executable by one or more processors to cause a computing device to perform functions comprising:
obtaining a query index that is derived from features of a frame of a query video;
determining that a distance measure between the query index and a candidate database index of a reference database satisfies a threshold condition, wherein the candidate database index corresponds to a frame of an original video;
based on the distance measure satisfying the threshold condition, determining a first time correlation score based on a comparison of signatures of a sequence of frames of the query video with respective signatures of a first sequence of frames of the original video, the first sequence of frames starting at a first start frame position;
determining a second time correlation score based on a comparison of the signatures of the sequence of frames of the query video with respective signatures of a second sequence of frames of the original video, the second sequence of frames starting at a second start frame position that is offset from the first start frame position; and
based at least on the second time correlation score, providing a results list that includes a name of the original video.
18. The non-transitory computer-readable medium of claim 17 , wherein the query index corresponds to a multi-dimensional query signature of the frame of the query video, wherein the candidate database index corresponds to a multi-dimensional database signature of the frame of the original video, and wherein the distance measure is a sum of differences in dimensions between the multi-dimensional query signature and the multi-dimensional database signature.
19. The non-transitory computer-readable medium of claim 17 , wherein the functions further comprise:
determining that the second time correlation score is greater than the first time correlation score; and
based on the second time correlation score being greater than the first time correlation score, selecting the second start frame position as an identified start frame position, wherein the results list further includes the identified start frame position.
20. The non-transitory computer-readable medium of claim 17 , wherein the name of the original video is stored at a leaf node corresponding to the candidate database index, and wherein the leaf node is addressable by the candidate database index.