# US 2024/0203123 A1 · Automated Video Segmentation

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

- Number: US 2024/0203123 A1
- Document ID: US20240203123A1
- Status: Published application
- Kind: A1
- Application number: 18/591,305
- Filed: 2024-02-29
- Published: 2024-06-20
- Earliest claimed: 2021-09-02
- Assignees: Gracenote, Inc.
- Applicants: Gracenote, Inc.
- Inventors: Konstantinos Antonio Dimitriou; Amanmeet Garg
- Web page: https://patentgrep.com/patent/US20240203123A1

## CPC

- G06V 20/49: {Segmenting video sequences, i.e. computational techniques such as parsing or cutting the sequence, low-level clustering or determining units such as shots or scenes}
- G06F 18/2148: {characterised by the process organisation or structure, e.g. boosting cascade}
- G06F 18/22: Matching criteria, e.g. proximity measures
- G06N 3/045: Combinations of networks
- G06N 3/084: Backpropagation, e.g. using gradient descent
- G06N 3/09: Supervised learning
- G06V 10/426: Graphical representations
- G06V 10/454: {Integrating the filters into a hierarchical structure, e.g. convolutional neural networks [CNN]}
- G06V 10/761: {Proximity, similarity or dissimilarity measures}
- G06V 10/763: {Non-hierarchical techniques, e.g. based on statistics of modelling distributions}
- G06V 10/774: Generating sets of training patterns; Bootstrap methods, e.g. bagging or boosting
- G06V 10/82: using neural networks
- G06V 10/84: using probabilistic graphical models from image or video features, e.g. Markov models or Bayesian networks
- 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/46: {Extracting features or characteristics from the video content, e.g. video fingerprints, representative shots or key frames}
- H04N 21/8456: {by decomposing the content in the time domain, e.g. in time segments}
- H04N 21/23418: {involving operations for analysing video streams, e.g. detecting features or characteristics (television picture signal circuitry for scene change detection H04N5/147; filtering for image enhancement G06T5/00; methods or arrangements for recognising scenes G06V20/00; arrangements characterised by components specially adapted for monitoring, identification or recognition of video in broadcast systems H04H60/59)}
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

Methods and systems for automated video segmentation are disclosed. A sequence of video frames having video segments of contextually-related sub-sequences may be received. Each frame may be labeled according to segment and segment class. A video graph may be constructed in which each node corresponds to a different frame, and each edge connects a different pair of nodes, and is associated with a time between video frames and a similarity metric of the connected frames. An artificial neural network (ANN) may be trained to predict both labels for the nodes and clusters of the nodes corresponding to predicted membership among the segments, using the video graph as input to the ANN, and ground-truth clusters of ground-truth labeled nodes. The ANN may be further trained to predict segment classes of the predicted clusters, using the segment classes as ground truths. The trained ANN may be configured for application runtime video sequences.

## Claims

### Claim 1

A system for automated video segmentation, the system comprising:
one or more processors; and
memory storing instructions that, when executed by the one or more processors, cause the system to carry out operations including:
receiving a training sequence of training media frames comprising a plurality of respective training media segments, wherein the respective training media segments comprise non-overlapping respective sub-sequences of the training media frames, each of the respective sub-sequences being associated with respective contextually-related subject content, and wherein each training media frame is associated with a respective label identifying both which particular training media segment it belongs to, and a segment class associated with the particular training media segment;
analytically constructing a training media graph from the training sequence of training media frames, the training media graph comprising nodes connected by edges, wherein each node corresponds to a different one of the respective training media frames, and each edge connects a different particular pair of nodes, and is associated with both a temporal distance between the respective training media frames corresponding to the particular pair of nodes, and a respective similarity metric quantifying similarity between respective features of the respective training media frames corresponding to the particular pair of nodes;
training an artificial neural network (ANN) to compute both (i) a predicted training label for each node of the training media graph, and (ii) predicted clusters of the nodes corresponding to predicted membership among the respective training media segments of the corresponding training media frames, using the training media graph as input to the ANN, and ground-truth clusters of ground truth labeled nodes, wherein the ground truth labeled nodes correspond to the training media frames and their associated respective labels, and the ground-truth clusters correspond to the respective training media segments;
further training the ANN to compute a predicted segment class for each of the predicted clusters, using as ground truths the segment classes of the respective training media segments; and
configuring the trained ANN for application to one or more unseen runtime media sequences.

### Claim 2 (depends on 1)

The system of claim 1, wherein the operations further include:
receiving a runtime sequence of runtime media frames, the runtime media frames being unlabeled with respect to both any media segment of the runtime sequence and any segment class;
analytically constructing a runtime media graph from the runtime sequence of runtime media frames, the runtime media graph comprising runtime nodes connected by runtime edges, wherein each runtime node corresponds to a different one of the respective runtime media frames, and each runtime edge connects a different particular pair of runtime nodes, and is associated with both a temporal distance between the respective runtime media frames corresponding to the particular pair of runtime nodes, and a respective runtime similarity metric quantifying similarity between respective features of the respective runtime media frames corresponding to the particular pair of runtime nodes;
applying the trained ANN to the runtime media graph to compute both (i) a predicted runtime label for each runtime node of the runtime media graph and (ii) predicted runtime clusters of the runtime nodes;
further applying the trained ANN to respectively determine both a predicted runtime media segment associated with each predicted runtime cluster, and a predicted runtime segment class of each predicted runtime media segment; and
recording in memory and/or displaying segmentation information, the segmentation information being based on the predicted runtime labels, the predicted runtime media segments, and the predicted runtime segment classes, and including (i) an identification of the predicted runtime media segments, (ii) an association of each respective runtime media frame with one of the predicted runtime media segments, and (iii) for each respective predicted runtime segment class, an identification of all predicted runtime media segments belonging to the respective runtime segment class.

### Claim 3 (depends on 2)

The system of claim 2, wherein the training media frames are at least one of training video frames or training audio frames,
wherein training media segments are at least one of training video segments or training audio segments,
wherein the runtime media frames are at least one of runtime video frames or runtime audio frames,
and wherein runtime media segments are at least one of runtime video segments or runtime audio segments.

### Claim 4 (depends on 1)

The system of claim 1, wherein the ANN comprises a graph neural network (GNN) and a clustering ANN,
wherein analytically constructing the training media graph from the training sequence of training media frames comprises:
extracting from each respective training media frame the respective label, timing information indicating temporal position in the training sequence, and a respective training feature vector characterizing media data of the respective training media frame;
creating a respective training node associated with each respective training media frame and its respective training feature vector and timing information, and labeled with the respective label of the associated training media frame; and
for every respective pair of created training nodes, determining a connecting edge having a length corresponding to a temporal distance between the pair of training media frames associated with respective pair of training nodes, and a weight corresponding to a similarity metric of the respective training feature vectors of the pair of training media frames associated with the respective pair of training nodes,
and wherein training the ANN to compute both (i) the predicted training labels for each node of the training media graph and (ii) the predicted clusters of the nodes corresponding to predicted membership among the respective training media segments of the corresponding training media frames comprises:
training the GNN to predict a respective embedding training vector for each respective node of the training media graph, the respective embedding training vector comprising a reduced-dimension mapping of the respective training feature vector associated with the respective node; and
using the respective embedding training vectors as input, training the clustering ANN to predict clusters of the nodes corresponding to the ground-truth clusters, and to predict node labels corresponding to the respective labels of the training media frames.

### Claim 5 (depends on 4)

The system of claim 4, wherein the operations further include:
receiving a runtime sequence of runtime media frames, the runtime media frames being unlabeled with respect to both any media segment of the runtime sequence and any segment class;
analytically constructing a runtime media graph from the runtime sequence of runtime media frames, the runtime media graph comprising runtime nodes connected by runtime edges, wherein each runtime node corresponds to a different one of the respective runtime media frames, and each runtime edge connects a different particular pair of runtime nodes, and is associated with both a temporal distance between the respective runtime media frames corresponding to the particular pair of runtime nodes, and a respective runtime similarity metric quantifying similarity between respective features of the respective runtime media frames corresponding to the particular pair of runtime nodes;
applying the trained ANN to the runtime media graph to compute both (i) a predicted runtime label for each runtime node of the runtime media graph and (ii) predicted runtime clusters of the runtime nodes;
further applying the trained ANN to respectively determine both a predicted runtime media segment associated with each predicted runtime cluster, and a predicted runtime segment class of each predicted runtime media segment; and
recording in memory and/or displaying segmentation information, the segmentation information being based on the predicted runtime labels, the predicted runtime media segments, and the predicted runtime segment classes, and including (i) an identification of the predicted runtime media segments, (ii) an association of each respective runtime media frame with one of the predicted runtime media segments, and (iii) for each respective predicted runtime segment class, an identification of all predicted runtime media segments belonging to the respective runtime segment class.

### Claim 6 (depends on 5)

The system of claim 5, wherein analytically constructing the runtime media graph from the runtime sequence of runtime media frames comprises:
extracting from each respective runtime media frame timing information indicating temporal position in the runtime sequence, and a respective runtime feature vector characterizing media data of the respective runtime media frame;
creating a respective runtime node associated with each respective runtime media frame and its respective runtime feature vector and timing information; and
for every respective pair of created runtime nodes, determining a connecting edge having a length corresponding to a temporal distance between the pair of runtime media frames associated with respective pair of runtime nodes, and a weight corresponding to a similarity metric of the respective runtime feature vectors of the pair of runtime media frames associated with the respective pair of runtime nodes,
and wherein applying the trained ANN to the runtime media graph to compute both (i) the predicted runtime label for each runtime node of the runtime media graph and (ii) the predicted runtime clusters of the runtime nodes comprises:
applying the trained GNN to the runtime media graph to predict a respective embedding runtime vector for each respective runtime node of the runtime media graph; and
applying the trained clustering ANN to the respective embedding runtime vectors to predict clusters of the runtime nodes, and to predict node labels corresponding to the respective runtime labels of the runtime media frames,
and wherein further applying the trained ANN to respectively determine both the predicted runtime media segment associated with each predicted runtime cluster, and the predicted runtime segment class of each predicted runtime media segment comprises:
applying the trained clustering ANN to both the predicted clusters of the runtime nodes and the predicted node labels in order to predict the runtime media segment associated with each predicted runtime cluster, and to predict the runtime segment class of each predicted runtime media segment.

### Claim 7 (depends on 1)

The system of claim 1, wherein the training sequence further comprises one or more program-sequences, each corresponding to a respective content program, and each comprising a respective sub-plurality of the plurality of training media segments,
wherein the respective contextually-related subject content comprises a media content category, the media content category being at least one of regular program content, advertising content, program scene content, or thematic program content,
wherein analytically constructing the training media graph comprises constructing a respective program-content media graph for each of the one or more program-sequences,
wherein training the ANN comprises respectively training the ANN for each respective program-content media graph,
and wherein further training the ANN comprises further training the ANN for each respective program-content media graph.

### Claim 8

A non-transitory computer-readable medium storing instructions thereon that, when executed by one or more processors of a system, cause the system to carry out operations including:
receiving a training sequence of training media frames comprising a plurality of respective training media segments, wherein the respective training media segments comprise non-overlapping respective sub-sequences of the training media frames, each of the respective sub-sequences being associated with respective contextually-related subject content, and wherein each training media frame is associated with a respective label identifying both which particular training media segment it belongs to, and a segment class associated with the particular training media segment;
analytically constructing a training media graph from the training sequence of training media frames, the training media graph comprising nodes connected by edges, wherein each node corresponds to a different one of the respective training media frames, and each edge connects a different particular pair of nodes, and is associated with both a temporal distance between the respective training media frames corresponding to the particular pair of nodes, and a respective similarity metric quantifying similarity between respective features of the respective training media frames corresponding to the particular pair of nodes;
training an artificial neural network (ANN) to compute both (i) a predicted training label for each node of the training media graph, and (ii) predicted clusters of the nodes corresponding to predicted membership among the respective training media segments of the corresponding training media frames, using the training media graph as input to the ANN, and ground-truth clusters of ground truth labeled nodes, wherein the ground truth labeled nodes correspond to the training media frames and their associated respective labels, and the ground-truth clusters correspond to the respective training media segments;
further training the ANN to compute a predicted segment class for each of the predicted clusters, using as ground truths the segment classes of the respective training media segments; and
configuring the trained ANN for application to one or more unseen runtime media sequences.

### Claim 9 (depends on 8)

The non-transitory computer-readable medium of claim 8, wherein the operations further include:
receiving a runtime sequence of runtime media frames, the runtime media frames being unlabeled with respect to both any media segment of the runtime sequence and any segment class;
analytically constructing a runtime media graph from the runtime sequence of runtime media frames, the runtime media graph comprising runtime nodes connected by runtime edges, wherein each runtime node corresponds to a different one of the respective runtime media frames, and each runtime edge connects a different particular pair of runtime nodes, and is associated with both a temporal distance between the respective runtime media frames corresponding to the particular pair of runtime nodes, and a respective runtime similarity metric quantifying similarity between respective features of the respective runtime media frames corresponding to the particular pair of runtime nodes;
applying the trained ANN to the runtime media graph to compute both (i) a predicted runtime label for each runtime node of the runtime media graph and (ii) predicted runtime clusters of the runtime nodes;
further applying the trained ANN to respectively determine both a predicted runtime media segment associated with each predicted runtime cluster, and a predicted runtime segment class of each predicted runtime media segment; and
recording in memory and/or displaying segmentation information, the segmentation information being based on the predicted runtime labels, the predicted runtime media segments, and the predicted runtime segment classes, and including (i) an identification of the predicted runtime media segments, (ii) an association of each respective runtime media frame with one of the predicted runtime media segments, and (iii) for each respective predicted runtime segment class, an identification of all predicted runtime media segments belonging to the respective runtime segment class.

### Claim 10 (depends on 9)

The non-transitory computer-readable medium of claim 9, wherein the training media frames are at least one of training video frames or training audio frames,
wherein training media segments are at least one of training video segments or training audio segments,
wherein the runtime media frames are at least one of runtime video frames or runtime audio frames,
and wherein runtime media segments are at least one of runtime video segments or runtime audio segments.

### Claim 11 (depends on 8)

The non-transitory computer-readable medium of claim 8, wherein the ANN comprises a graph neural network (GNN) and a clustering ANN,
wherein analytically constructing the training media graph from the training sequence of training media frames comprises:
extracting from each respective training media frame the respective label, timing information indicating temporal position in the training sequence, and a respective training feature vector characterizing media data of the respective training media frame;
creating a respective training node associated with each respective training media frame and its respective training feature vector and timing information, and labeled with the respective label of the associated training media frame; and
for every respective pair of created training nodes, determining a connecting edge having a length corresponding to a temporal distance between the pair of training media frames associated with respective pair of training nodes, and a weight corresponding to a similarity metric of the respective training feature vectors of the pair of training media frames associated with the respective pair of training nodes,
and wherein training the ANN to compute both (i) the predicted training labels for each node of the training media graph and (ii) the predicted clusters of the nodes corresponding to predicted membership among the respective training media segments of the corresponding training media frames comprises:
training the GNN to predict a respective embedding training vector for each respective node of the training media graph, the respective embedding training vector comprising a reduced-dimension mapping of the respective training feature vector associated with the respective node; and
using the respective embedding training vectors as input, training the clustering ANN to predict clusters of the nodes corresponding to the ground-truth clusters, and to predict node labels corresponding to the respective labels of the training media frames.

### Claim 12 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein the operations further include:
receiving a runtime sequence of runtime media frames, the runtime media frames being unlabeled with respect to both any media segment of the runtime sequence and any segment class;
analytically constructing a runtime media graph from the runtime sequence of runtime media frames, the runtime media graph comprising runtime nodes connected by runtime edges, wherein each runtime node corresponds to a different one of the respective runtime media frames, and each runtime edge connects a different particular pair of runtime nodes, and is associated with both a temporal distance between the respective runtime media frames corresponding to the particular pair of runtime nodes, and a respective runtime similarity metric quantifying similarity between respective features of the respective runtime media frames corresponding to the particular pair of runtime nodes;
applying the trained ANN to the runtime media graph to compute both (i) a predicted runtime label for each runtime node of the runtime media graph and (ii) predicted runtime clusters of the runtime nodes;
further applying the trained ANN to respectively determine both a predicted runtime media segment associated with each predicted runtime cluster, and a predicted runtime segment class of each predicted runtime media segment; and
recording in memory and/or displaying segmentation information, the segmentation information being based on the predicted runtime labels, the predicted runtime media segments, and the predicted runtime segment classes, and including (i) an identification of the predicted runtime media segments, (ii) an association of each respective runtime media frame with one of the predicted runtime media segments, and (iii) for each respective predicted runtime segment class, an identification of all predicted runtime media segments belonging to the respective runtime segment class.

### Claim 13 (depends on 12)

The non-transitory computer-readable medium of claim 12, wherein analytically constructing the runtime media graph from the runtime sequence of runtime media frames comprises:
extracting from each respective runtime media frame timing information indicating temporal position in the runtime sequence, and a respective runtime feature vector characterizing media data of the respective runtime media frame;
creating a respective runtime node associated with each respective runtime media frame and its respective runtime feature vector and timing information; and
for every respective pair of created runtime nodes, determining a connecting edge having a length corresponding to a temporal distance between the pair of runtime media frames associated with respective pair of runtime nodes, and a weight corresponding to a similarity metric of the respective runtime feature vectors of the pair of runtime media frames associated with the respective pair of runtime nodes, and wherein applying the trained ANN to the runtime media graph to compute both (i) the predicted runtime label for each runtime node of the runtime media graph and (ii) the predicted runtime clusters of the runtime nodes comprises:
applying the trained GNN to the runtime media graph to predict a respective embedding runtime vector for each respective runtime node of the runtime media graph; and
applying the trained clustering ANN to the respective embedding runtime vectors to predict clusters of the runtime nodes, and to predict node labels corresponding to the respective runtime labels of the runtime media frames,
and wherein further applying the trained ANN to respectively determine both the predicted runtime media segment associated with each predicted runtime cluster, and the predicted runtime segment class of each predicted runtime media segment comprises:
applying the trained clustering ANN to both the predicted clusters of the runtime nodes and the predicted node labels in order to predict the runtime media segment associated with each predicted runtime cluster, and to predict the runtime segment class of each predicted runtime media segment.

### Claim 14

A non-transitory computer-readable medium storing instructions thereon that, when executed by one or more processors of a system, cause the system to carry out operations including:
analytically constructing a media graph from the sequence of media frames, the media graph comprising nodes connected by edges, wherein each node corresponds to a different one of the respective media frames, and each edge connects a different particular pair of nodes, and is associated with both a temporal distance between the respective media frames corresponding to the particular pair of nodes, and a respective similarity metric quantifying similarity between respective features of the respective media frames corresponding to the particular pair of nodes;
applying an artificial neural network (ANN) to the media graph to compute both (i) predicted labels for the nodes of the media graph corresponding to predicted media-frame labels of the media frames, and (ii) predicted clusters of the nodes corresponding to predicted media segments of the sequence comprising respective sub-sequences of the media frames associated with respective contextually-related subject content, wherein the ANN has previously been trained to compute both predicted training labels for each training node of a training media graph constructed from a training media sequence of training media frames, and predicted training clusters of the training nodes corresponding to predicted membership among respective training media segments of the corresponding training media frames;
further applying the ANN as trained to respectively determine a predicted segment class of each predicted media segment; and
recording in memory and/or displaying information associating each media frame with one of the predicted media segments, and, for each respective predicted segment class, an identification of all predicted media segments belonging to the respective segment class.

### Claim 15 (depends on 14)

The non-transitory computer-readable medium of claim 14, wherein the media frames are at least one of runtime video frames or runtime audio frames,
wherein runtime media segments are at least one of runtime video segments or runtime audio segments,
wherein the training media frames are at least one of training video frames or training audio frames,
and wherein training media segments are at least one of training video segments or training audio segments.

### Claim 16 (depends on 14)

The non-transitory computer-readable medium of claim 14, wherein the sequence comprises media program content,
and wherein the respective contextually-related subject content comprises a media content category, the media content category being at least one of regular program content, advertising content, program scene content, or thematic program content.

### Claim 17 (depends on 14)

The non-transitory computer-readable medium of claim 14, wherein analytically constructing the training media graph from the training sequence of training media frames comprises:
extracting from each respective training media frame the respective label, timing information indicating temporal position in the training sequence, and a respective training feature vector characterizing media data of the respective training media frame;
creating a respective training node associated with each respective training media frame and its respective training feature vector and timing information, and labeled with the respective label of the associated training media frame; and
for every respective pair of created training nodes, determining a connecting edge having a length corresponding to a temporal distance between the pair of training media frames associated with respective pair of training nodes, and a weight corresponding to a similarity metric of the respective training feature vectors of the pair of training media frames associated with the respective pair of training nodes.

### Claim 18 (depends on 17)

The non-transitory computer-readable medium of claim 17, wherein the ANN comprises both a graph neural network (GNN) and a clustering ANN, wherein the GNN is trained to predict a respective embedding training vector for each respective training node of the training media graph, the respective embedding training vector comprising a reduced-dimension mapping of a respective training feature vector associated with the respective training node, and wherein the clustering ANN is trained to predict clusters of the training nodes corresponding to the training media frames of the respective training media segments,
and wherein applying the ANN to the media graph to compute both (i) the predicted labels for the nodes of the media graph, and (ii) the predicted clusters of the nodes corresponding to predicted media segments comprises:
applying the trained GNN to the media graph to predict a respective embedding vector for each respective node of the media graph; and
applying the trained clustering ANN to the respective embedding vectors to predict clusters of the nodes, and to predict node labels corresponding to the respective labels of the media frames.

### Claim 19 (depends on 18)

The non-transitory computer-readable medium of claim 18, wherein applying the ANN as trained to respectively determine the predicted segment class of each predicted media segment comprises:
applying the trained clustering ANN to both the predicted clusters of the nodes and the predicted node labels in order to predict the media segment associated with each predicted cluster, and to predict the segment class of each predicted media segment.

### Claim 20

The non-transitory computer-readable medium of 19, wherein recording in memory and/or displaying the information comprises:
based on the predicted labels, the predicted media segments, and the predicted segment classes, determining (i) all the media frames of each predicted media segment, and (ii) all predicted media segments of each predicted segment class across a temporal span of the media sequence.
