# US 12,223,985 B2 · Grounding flow graphs in signals

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,223,985 B2
- Document ID: US12223985B2
- Status: Granted
- Kind: B2
- Application number: 18/103,101
- Filed: 2023-01-30
- Published: 2023-09-07
- Granted: 2025-02-11
- Earliest claimed: 2022-03-07
- Assignees: Samsung Electronics Co., Ltd.
- Applicants: Samsung Electronics Co., Ltd.
- Inventors: Mikita Dvornik; Isma Hadji; Allan Douglas Jepson
- Web page: https://patentgrep.com/patent/US12223985B2

## CPC

- G06F 16/783: using metadata automatically derived from the content
- G11B 27/34: Indicating arrangements {(indicating means incorporated in magazine or cassette G11B23/046 and G11B23/0875; indicating measured values in general G01D)}
- G06F 16/7328: {Query by example, e.g. a complete video frame or video sequence (graphical querying G06F16/7335)}
- G06V 10/86: using syntactic or structural representations of the image or video pattern, e.g. symbolic string recognition; using graph matching
- G06V 20/41: {Higher-level, semantic clustering, classification or understanding of video scenes, e.g. detection, labelling or Markovian modelling of sport events or news items (segmenting video sequences G06V20/49)}
- G06V 20/44: {Event detection}
- G11B 27/102: {Programmed access in sequence to addressed parts of tracks of operating record carriers (access by moving the head G11B3/08, G11B5/54, G11B7/085, G11B21/022; by moving the record carrier G11B15/005, G11B17/005, by driving of both record carrier and head G11B15/1816)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G11B: INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER (recording measured values in a way that does not require playback through a transducer G01D9/00; recording or playback apparatus using mechanically marked tape, e.g. punched paper tape, or using unit records, e.g. punched or magnetically marked cards G06K; transferring data from one type of record carrier to another G06K1/18; circuits for coupling output of reproducer to radio receiver H04B1/20; gramophone pick-ups or like acoustic electromechanical transducers or circuits therefor H04R)
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

A first graph which is a flow graph is converted into a second graph using a first algorithm. The second graph, combined with a second algorithm using a dynamic programming recursion, is compared with a video and a best matching thread, with respect to the video, is found through the second graph. The best matching thread may then be used for a user-assistance function. The dynamic programming recursion reduces computational effort needed by the computer performing the matching.

## Claims

### Claim 1

An apparatus comprising:
one or more processors; and
one or more memories storing instructions, wherein an execution by the one or more processors of the instructions is configured to cause the apparatus to:
obtain a second graph, wherein the second graph is formed from a first graph, wherein the first graph is a flow graph and the second graph encodes topological sorts of the first graph;
align the second graph to a video, wherein the aligning obtains a start time and an end time of an event in the video; and
perform a user-assistance function based on the start time and the end time of the event.

### Claim 2 (depends on 1)

The apparatus of claim 1, wherein the user-assistance function is a providing of content addressability to a user, wherein the execution by the one or more processors of the instructions is further configured to cause the apparatus to:
receive, from the user, a query as to the event in the video;
cue, based on the query and the second graph, the video to the start time of the event in the video; and
display the video to the user beginning at the start time of the event.

### Claim 3 (depends on 2)

The apparatus of claim 2, wherein the execution by the one or more processors of the instructions is further configured to cause the apparatus to:
obtain the video from a video database; and
obtain the second graph from a graph database.

### Claim 4 (depends on 1)

The apparatus of claim 1, wherein the user-assistance function is an on-line personal assistant, and wherein the execution by the one or more processors of the instructions is further configured to cause the apparatus to:
observe one or more recent operations of a user;
receive a query from the user as to candidate next steps; and
communicate, based on the query, the second graph and the one or more recent operations of the user, one or more candidate next steps to the user.

### Claim 5 (depends on 1)

The apparatus of claim 1, wherein the execution by the one or more processors of the instructions is further configured to cause the apparatus to form the first graph from a set of text instructions.

### Claim 6 (depends on 1)

The apparatus of claim 1, wherein the execution by the one or more processors of the instructions is further configured to cause the apparatus to form the second graph by defining nodes in the second graph as a two tuple (v,P), wherein v is a node in the second graph currently being processed and P is a set of nodes that has already been processed.

### Claim 7 (depends on 6)

The apparatus of claim 6, wherein the execution by the one or more processors of the instructions is further configured to cause the apparatus to form the second graph by defining edges in the second graph as satisfying (v,P) to (w,P′) is an edge in the second graph if and only if P′=PU{v}, ancestors of w are in P, and w is not already in P, wherein P and P′ are nodes in the second graph, v is a step that has been completed, w is not in P and “U” is a set operator indicating union.

### Claim 8 (depends on 1)

The apparatus of claim 1, wherein the execution by the one or more processors of the instructions is further configured to cause the apparatus to align the second graph to the video by inferring an ordering of steps in the video by applying a dynamic programming recursion.

### Claim 9 (depends on 8)

The apparatus of claim 8, wherein the dynamic programming recursion comprises:
determining a plurality of costs associated with a plurality of two-tuples, a first two-tuple of the plurality of two-tuples corresponding to a pairing of a step encoding with a clip from the video; and
tracing back among the plurality of two-tuples to find a minimum cost path.

### Claim 10

A non-transitory computer readable medium storing instructions for execution by a computer, wherein the execution by the computer of the instructions is configured to cause the computer to:
obtain a second graph, wherein the second graph is formed from a first graph, wherein the first graph is a flow graph and the second graph encodes topological sorts of the first graph;
align the second graph to a video, wherein the aligning obtains a start time and an end time of an event in the video; and
perform a user-assistance function based on the start time and the end time of the event.

### Claim 11 (depends on 10)

The non-transitory computer readable medium of claim 10, wherein the user-assistance function is a providing of content addressability to a user, wherein the execution by the computer of the instructions is further configured to cause the computer to:
receive, from the user, a query as to the event in the video;
cue, based on the query and the second graph, the video to the start time of the event in the video; and
display the video to the user beginning at the start time of the event.

### Claim 12 (depends on 11)

The non-transitory computer readable medium of claim 11, wherein the execution by the computer of the instructions is further configured to cause the computer to:
obtain the video from a video database; and
obtain the second graph from a graph database.

### Claim 13 (depends on 10)

The non-transitory computer readable medium of claim 10, wherein the user-assistance function is an on-line personal assistant, and wherein the execution by the computer of the instructions is further configured to cause the computer to:
observe one or more recent operations of a user;
receive a query from the user as to candidate next steps; and
communicate, based on the query, the second graph and the one or more recent operations of the user, one or more candidate next steps to the user.

### Claim 14 (depends on 10)

The non-transitory computer readable medium of claim 10, wherein the execution by the computer of the instructions is further configured to cause the computer to form the first graph from a set of text instructions.

### Claim 15 (depends on 10)

The non-transitory computer readable medium of claim 10, wherein the execution by the computer of the instructions is further configured to cause the computer to form the second graph by defining nodes in the second graph as a two tuple (v,P), wherein v is a node in the second graph currently being processed and P is a set of nodes that has already been processed.

### Claim 16 (depends on 15)

The non-transitory computer readable medium of claim 15, wherein the execution by the computer of the instructions is further configured to cause the computer to form the second graph by defining edges in the second graph as satisfying (v,P) to (w,P′) is an edge in the second graph if and only if P′=PU{v}, ancestors of w are in P, and w is not already in P, wherein P and P′ are nodes in the second graph, v is a step that has been completed, w is not in P and “U” is a set operator indicating union.

### Claim 17 (depends on 10)

The non-transitory computer readable medium of claim 10, wherein the execution by the computer of the instructions is further configured to cause the computer to align the second graph to the video by inferring an ordering of steps in the video by applying a dynamic programming recursion.

### Claim 18 (depends on 17)

The non-transitory computer readable medium of claim 17, wherein the dynamic programming recursion comprises:
determining a plurality of costs associated with a plurality of two-tuples, a first two-tuple of the plurality of two-tuples corresponding to a pairing of a step encoding with a clip from the video; and
tracing back among the plurality of two-tuples to find a minimum cost path.