Graph-based video indexing to support querying with implicit relations

Patent metadata

Field	Value
Publication number	US-12346374-B2
Application number	US-202218067294-A
Country	US
Kind code	B2
Filing date	Dec 16, 2022
Priority date	Dec 16, 2022
Publication date	Jul 1, 2025
Grant date	Jul 1, 2025

Abstract

A video indexing system generates descriptive metadata for a video including identifiers for each of multiple detections that each correspond to a select one of multiple subjects that appear in the video. These detections are used to create relational graph data for the video, where the relational graph data includes nodes corresponding to each of the multiple subjects that appear in the video. A knowledge graph is queried with unique identifiers corresponding to the multiple subjects of the video to retrieve implicit relational data for each of the multiple subjects, and a merged relational graph is created by merging the implicit relational data retrieved from the knowledge graph with the relational graph data created for the video. A search engine uses the merged relational graph to identify video content relevant to a user query that is based on an implicit relation. Search results identifying the relevant content are presented on a user device.

First claim

What is claimed is:

1. A method comprising:
creating a merged relational graph by:
obtaining relational graph data created for a video, the relational graph data including a video node identifying video subject nodes that identify multiple subjects of the video;
retrieving implicit relational data for each of the multiple subjects identified in the relational graph data by querying a knowledge graph with unique identifiers corresponding to the multiple subjects; and
merging the implicit relational data retrieved from the knowledge graph with the relational graph data created for the video;

indexing the merged relational graph in a video-based database by combining the merged relational graph with other graphs of common format previously created for other videos;
receiving a video search query via a search interface, the video search query specifying an implicit relation identifying a fact satisfied by video content that is not evident from viewing the video content without access to an external data source;
identifying, based on the merged relational graph, the video content that is characterized by the implicit relation; and
providing, responsive to the query via the search interface, search results that identify the video content.

2. The method of claim 1 , further comprising:
generating descriptive metadata for the video, the descriptive metadata including detections corresponding to each of the multiple subjects that appear in the video; and
generating the relational graph data for the video.

3. The method of claim 1 , wherein the relational graph data for the video and the knowledge graph implement a common graph model and utilize a common identifier scheme.

4. The method of claim 3 , further comprising:
determining, from the merged relational graph, that the video features an instance of a select subject of interest referenced in the video search query, the instance being characterized by the implicit relation; and
including the video in the search results.

5. The method of claim 1 , wherein the video search query specifies a temporal relation between two instances of a subject of interest and the video content presented in the search results includes a select video with two instances of the subject of interest, in different frames, satisfying the temporal relation.

6. The method of claim 4 , wherein the merged relational graph is created dynamically in response to receipt of the video search query by performing a joint query on multiple data sources.

7. The method of claim 4 , wherein the search results identify a location within the video featuring the instance of the select subject of interest.

8. A system comprising:
memory;
a processing system;
a relational graph generator stored in the memory and executable by the processing system to:
create a merged relational graph by:
generating relational graph data for a video, the relational graph data including a video node identifying video subject nodes that identify to multiple subjects of the video;
retrieving implicit relational data for each of the multiple subjects identified in the relational graph data by querying a knowledge graph with unique identifiers corresponding to the multiple subjects; and
merging the implicit relational data retrieved from the knowledge graph with the relational graph data created for the video; and

index the merged relational graph in a video-based database by combining the merged relational graph with other graphs of common format previously created for other videos;

a search engine stored in memory and executable by the processing system to:
receive a video search query via a search interface, the video search query specifying an implicit relation identifying a fact satisfied by video content that is not evident from viewing the video content without access to an external data source;
identify, based on the merged relational graph, the video content that is characterized by the implicit relation; and
provide, responsive to the video search query via the search interface, search results that identify the video content.

9. The system of claim 8 , further comprising:
a descriptive metadata generator stored in the memory and executable by the processing system to generate descriptive metadata for the video, the descriptive metadata including detections corresponding to each of the multiple subjects that appear in the video.

10. The system of claim 8 , wherein the relational graph data for the video and the knowledge graph implement a common graph model and utilize a common identifier scheme.

11. The system of claim 8 , wherein the search engine is further executable to:
determine, from the merged relational graph, that the video features an instance of a select subject of interest referenced in the video search query, the instance being characterized by the implicit relation; and
include the video in the search results.

12. The system of claim 8 , wherein the relational graph generator creates the merged relational graph in response to receipt of the video search query.

13. The system of claim 11 , wherein the search results identify a location within the video featuring the instance of the select subject of interest.

14. A tangible computer-readable storage media storing processor-executable instructions for executing a computer process, the computer process comprising:
generating descriptive metadata for a video, the descriptive metadata including detections corresponding to each of multiple subjects that appear in the video;
receiving a query via a search interface, the query specifying an implicit relation identifying a fact satisfied by video content that is not evident from viewing the video content without access to an external data source;
identifying, based on a merged relational graph, the video content that is characterized by the implicit relation, the merged relational graph including relational graph data including nodes corresponding to the multiple subjects that appear in the video and implicit relational data from a knowledge graph that pertains to each of the multiple subjects identified in the relational graph data; and
providing, responsive to the query via the search interface, search results that identify the video content.

15. The tangible computer-readable storage media of claim 14 , wherein the relational graph data for the video and the knowledge graph implement a common graph model and utilize a common identifier scheme.

16. The tangible computer-readable storage media of claim 14 , wherein the computer process further comprises:
determining, from the merged relational graph, that the video features an instance of a select subject of interest referenced in the query, the instance being characterized by the implicit relation; and
including the video in the search results.

17. The tangible computer-readable storage media of claim 14 , wherein the creating of the merged relational graph occurs in response to receiving of the query.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Nir Oron
• Bar-Menachem Ika
• Sagiv Inbal

Classifications

• G06F16/738

  Presentation of query results · CPC title

• G06F16/71 Primary

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F16/784

  the detected or recognised objects being people · CPC title

• G06F16/783

  using metadata automatically derived from the content · CPC title

• G06F16/735 Primary

  Filtering based on additional data, e.g. user or group profiles · CPC title