# US 12,002,266 B2 · Graph-based video instance segmentation > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,002,266 B2 - Document ID: US12002266B2 - Status: Granted - Kind: B2 - Application number: 17/502,447 - Filed: 2021-10-15 - Published: 2023-04-20 - Granted: 2024-06-04 - Earliest claimed: 2021-10-15 - Assignees: Adobe Inc. - Applicants: Adobe Inc. - Inventors: Ning Xu - Web page: https://patentgrep.com/patent/US12002266B2 ## 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/253: {of extracted features} - G06N 3/045: Combinations of networks - G06N 3/08: Learning methods - G06T 7/11: Region-based segmentation - G06T 7/162: involving graph-based methods - G06V 10/44: Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components - G06V 10/82: using neural networks - G06V 20/46: {Extracting features or characteristics from the video content, e.g. video fingerprints, representative shots or key frames} - G06T 2207/10016: Video; Image sequence - 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 - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## Abstract Certain aspects and features of this disclosure relate to graph-based video instance segmentation. In one example, a reference instance of an object in a reference frame and features in a target frame are identified and used to produce a graph of nodes and edges. Each node represents a feature in the target frame or the reference instance of the object in the reference frame. Each edge of the graph represents a spatiotemporal relationship between the feature in the target frame and the reference instance of the object. Embeddings of the nodes and edges of the graph are iteratively updated based on the spatiotemporal relationship between a feature in the target frame and the reference instance of the object in the reference frame, resulting in a fused node embedding that can be used for detecting the target instance of the object. ## Claims ### Claim 1 A computer-implemented method in which one or more computing systems perform operations comprising: identifying, by a backbone neural network module, a reference instance of an object in a feature domain of a reference frame of a media clip including a plurality of consecutive video frames; identifying, by the backbone neural network module, features in a target frame of the media clip in the feature domain; producing, by a graphing module, a graph of nodes and edges based on the reference instance of the object in the reference frame and the features in the target frame, wherein each node of the graph represents a feature in the target frame or the reference instance of the object in the reference frame and each edge of the graph represents a spatiotemporal relationship between the feature in the target frame and the reference instance of the object in the reference frame; iteratively updating, by a modeling and graph feature fusion module, embeddings of the nodes and edges of the graph based on the spatiotemporal relationship to produce fused node embeddings and updated edge embeddings, wherein the embeddings of the nodes and edges are generated based on the reference instance of the features in the target frame; detecting, by a detection module, a target instance of the object in the target frame based on the fused node embeddings; and displaying, by a presentation device, the target instance of the object as visually segmented from the target frame. ### Claim 2 (depends on 1) The method of claim 1, wherein detecting the target instance of the object further comprises: segmenting the target instance of the object in the target frame of the media clip; and generating a segmentation mask for the detected target instance based on the fused node embeddings and historical mask information for frames preceding the target frame in the media clip. ### Claim 3 (depends on 2) The method of claim 2, wherein generating the segmentation mask further comprises warping the historical mask information to the target frame in the media clip. ### Claim 4 (depends on 1) The method of claim 1, wherein displaying the target instance of the object comprises displaying at least one of a segmentation mask or a bounding box for the target instance of the object. ### Claim 5 (depends on 1) The method of claim 1, further comprising selectively and repeatedly using the target frame and the target instance of the object to provide a subsequent reference frame for identifying the object in a subsequent target frame of the media clip. ### Claim 6 (depends on 1) The method of claim 1, further comprising: pruning the edges based on the detected target instance by removing edges connecting features of the target frame outside the detected target instance and combining edges connecting features of the target frame inside the detected target instance; and classifying the pruned edges based on the updated edge embeddings to determine an association between the detected target instance of the object in the target frame and the reference instance of the object in the reference frame. ### Claim 7 (depends on 1) The method of claim 1, further comprising training or retraining, using a cost function, one or more models used for detecting the target instance of the object. ### Claim 8 A system comprising: a processor; and a memory device configured to store a media clip including a plurality of consecutive video frames and a graph of nodes and edges based on a reference instance of an object in the media clip, the memory device further storing a media editing application executable by the processor for performing operations comprising; identifying the reference instance of the object in a reference frame of the media clip; identifying features in a target frame of the media clip; producing the graph of nodes and edges based on the reference instance of the object in the reference frame and the features in the target frame, wherein each node of the graph represents a feature in the target frame or the reference instance of the object in the reference frame and each edge of the graph represents a spatiotemporal relationship between the feature in the target frame and the reference instance of the object in the reference frame; iteratively updating embeddings of the nodes and edges of the graph based on the spatiotemporal relationship to produce fused node embeddings and updated edge embeddings; and detecting a target instance of the object in the target frame based on the fused node embeddings. ### Claim 9 (depends on 8) The system of claim 8, wherein the operation of detecting the target instance of the object further comprises: segmenting the target instance of the object in the target frame of the media clip; and generating a segmentation mask for the detected target instance based on the fused node embeddings and historical mask information for frames preceding the target frame in the media clip. ### Claim 10 (depends on 9) The system of claim 9, wherein the operation of generating the segmentation mask further comprises warping the historical mask information to the target frame in the media clip. ### Claim 11 (depends on 8) The system of claim 8, wherein the operation of displaying the target instance of the object comprises displaying at least one of a segmentation mask or a bounding box for the target instance of the object. ### Claim 12 (depends on 8) The system of claim 8, wherein the media editing application is further executable by the processor for performing an operation comprising selectively and repeatedly using the target frame and the target instance of the object to provide a subsequent reference frame for identifying the object in a subsequent target frame of the media clip. ### Claim 13 (depends on 8) The system of claim 8, wherein the media editing application is further executable by the processor for performing operations comprising: pruning the edges based on the detected target instance by removing edges connecting features of the target frame outside the detected target instance and combining edges connecting features of the target frame inside the detected target instance; and classifying the pruned edges based on the updated edge embeddings to determine an association between the detected target instance of the object in the target frame and the reference instance of the object in the reference frame. ### Claim 14 (depends on 8) The system of claim 8, wherein the media editing application is further executable by the processor for performing an operation comprising training or retraining, using a cost function, one or more models used for detecting the target instance of the object. ### Claim 15 A non-transitory computer-readable medium storing program code executable by a processor to perform operations, the operations comprising: identifying a reference instance of an object in a reference frame of a media clip including a plurality of consecutive video frames; identifying features in a target frame of the media clip in the feature domain; a step for producing a graph of nodes and edges based on the reference instance of the object in the reference frame and the features in the target frame; a step for iteratively updating embeddings of the nodes and edges of the graph based on a spatiotemporal relationship between a feature in the target frame and the reference instance of the object in the reference frame to produce fused node embeddings and updated edge embeddings; a step for identifying a target instance of the object in the target frame based on the fused node embeddings; and displaying the target instance of the object as visually segmented from the target frame. ### Claim 16 (depends on 15) The non-transitory computer-readable medium of claim 15, wherein the step for identifying the target instance of the object further comprises warping the historical mask information to the target frame in the media clip. ### Claim 17 (depends on 15) The non-transitory computer-readable medium of claim 15, wherein the operation of displaying the target instance of the object further comprises displaying at least one of a segmentation mask or a bounding box for the target instance of the object. ### Claim 18 (depends on 15) The non-transitory computer-readable medium of claim 15, wherein the program code is further executable by the processor to perform an operation comprising selectively and repeatedly using the target frame and the target instance of the object to provide a subsequent reference frame for identifying the object in a subsequent target frame of the media clip. ### Claim 19 (depends on 15) The non-transitory computer-readable medium of claim 15, wherein the program code is further executable by the processor to perform operations comprising: pruning the edges based on the identified target instance by removing edges connecting features of the target frame outside the identified target instance and combining edges connecting features of the target frame inside the identified target instance; and classifying the pruned edges based on the updated edge embeddings to determine an association between the identified target instance of the object in the target frame and the reference instance of the object in the reference frame. ### Claim 20 (depends on 15) The non-transitory computer-readable medium of claim 15, wherein the program code is further executable by the processor to perform an operation comprising training or retraining, using a cost function, one or more models used for detecting the target instance of the object.