# US 12,112,519 B1 · Scripted interactive scenarios based on scene graph matching > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,112,519 B1 - Document ID: US12112519B1 - Status: Granted - Kind: B1 - Application number: 17/678,090 - Filed: 2022-02-23 - Granted: 2024-10-08 - Earliest claimed: 2021-02-24 - Assignees: Apple Inc. - Applicants: Apple Inc. - Inventors: Alexander S. Polichroniadis; Angela Blechschmidt; Daniel Ulbricht - Web page: https://patentgrep.com/patent/US12112519B1 ## CPC - G06V 10/761: {Proximity, similarity or dissimilarity measures} - G06T 17/00: Three-dimensional [3D] modelling for computer graphics - G06V 10/7635: {based on graphs, e.g. graph cuts or spectral clustering} - G06V 10/80: Fusion, i.e. combining data from various sources at the sensor level, preprocessing level, feature extraction level or classification level (multimodal speaker identification or verification G10L17/10) - G06V 20/20: in augmented reality scenes - G06V 20/70: Labelling scene content, e.g. deriving syntactic or semantic representations - G06T 2210/61: Scene description - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## Abstract An exemplary process obtains sensor data for a physical environment, generates a local scene graph for the physical environment based on the sensor data, wherein the local scene graph represents a set of objects and relationships between the objects, matches the local scene graph with a principal scene graph of a set of principal scene graphs, and executes one or more scripted actions involving the objects based on a narrative associated with the matched principal scene graph. In some implementations, the set of principal scene graphs is generated by generating local scene graphs for a plurality of environments, and generating individual scene graphs each representative of local scene graphs. ## Claims ### Claim 1 A method comprising: at an electronic device having a processor: obtaining sensor data for a physical environment; generating a local scene graph for the physical environment based on the sensor data, wherein the local scene graph represents a set of objects and relationships between the objects; identifying a principal scene graph from a set of previously obtained principal scene graphs based on matching characteristics and relationships between the set of objects associated with the local scene graph to one or more characteristics and relationships between a set of objects associated with each principal scene graph; and executing one or more scripted actions involving the objects based on a narrative associated with the identified principal scene graph. ### Claim 2 (depends on 1) The method of claim 1, wherein each principal scene graph of the set of principal scene graphs comprises a different respective combination of objects and relationships. ### Claim 3 (depends on 1) The method of claim 1, wherein each principal scene graph of the set of principal scene graphs represents a respective set of local scene graphs. ### Claim 4 (depends on 1) The method of claim 1, wherein the set of principal scene graphs is generated by: generating local scene graphs for a plurality of environments; and generating individual scene graphs each representative of local scene graphs. ### Claim 5 (depends on 4) The method of claim 4, wherein the set of principal scene graphs is generated using a machine learning method that inputs a representation of the local scene graphs and generates the individual scene graphs based on a clustering algorithm. ### Claim 6 (depends on 5) The method of claim 5, wherein the clustering algorithm is based on similarity distance measurements between objects within each of the local scene graphs. ### Claim 7 (depends on 1) The method of claim 1, wherein the narrative is a first narrative of a plurality of narratives and each principal scene graph of the set of principal scene graphs is associated with a different narrative of the plurality of narratives. ### Claim 8 (depends on 1) The method of claim 1, wherein the narrative is a first narrative of a plurality of narratives and each narrative is associated with a different action of the one or more scripted actions involving the objects. ### Claim 9 (depends on 1) The method of claim 1, wherein matching the local scene graph with the principal scene graph is based on determining similarity scores between the local scene graph and each principal scene graph of the set of principal scene graphs. ### Claim 10 (depends on 1) The method of claim 1, further comprising: generating, based on the local scene graph, a view of a three-dimensional (3D) environment comprising the physical environment. ### Claim 11 (depends on 10) The method of claim 10, wherein executing the one or more scripted actions comprising presenting the objects within the view of the 3D environment. ### Claim 12 (depends on 11) The method of claim 11, wherein matching the local scene graph with a principal scene graph comprises: determining whether to generate a virtual object within the view of the 3D environment to match the local scene graph with a principal scene graph; and in accordance with determining to generate the virtual object to match the local scene graph with the principal scene graph, generating the virtual object to be presented within the view of the 3D environment. ### Claim 13 (depends on 1) The method of claim 1, wherein the set of principal scene graphs comprises a first principal scene graph and a second principal scene graph, and matching the local scene graph with a principal scene graph comprises: determining that the first principal scene graph matches a first portion of an attribute of the local scene graph; determining that the second principal scene graph matches a second portion of the attribute of the local scene graph; and merging the first principal scene graph and the second principal scene graph to generate a matched principal scene graph. ### Claim 14 (depends on 1) The method of claim 1, wherein the electronic device is a head-mounted device (HMD). ### Claim 15 A device comprising: a non-transitory computer-readable storage medium; and one or more processors coupled to the non-transitory computer-readable storage medium, wherein the non-transitory computer-readable storage medium comprises program instructions that, when executed on the one or more processors, cause the one or more processors to perform operations comprising: obtaining sensor data for a physical environment; generating a local scene graph for the physical environment based on the sensor data, wherein the local scene graph represents a set of objects and relationships between the objects; identifying a principal scene graph from a set of previously obtained principal scene graphs based on matching characteristics and relationships between the set of objects associated with the local scene graph to one or more characteristics and relationships between a set of objects associated with each principal scene graph; and executing one or more scripted actions involving the objects based on a narrative associated with the identified principal scene graph. ### Claim 16 (depends on 15) The device of claim 15, wherein each principal scene graph of the set of principal scene graphs comprises a different respective combination of objects and relationships. ### Claim 17 (depends on 15) The device of claim 15, wherein each principal scene graph of the set of principal scene graphs represents a respective set of local scene graphs. ### Claim 18 (depends on 15) The device of claim 15, wherein the set of principal scene graphs is generated by: generating local scene graphs for a plurality of environments; and generating individual scene graphs each representative of local scene graphs. ### Claim 19 (depends on 18) The device of claim 18, wherein the set of principal scene graphs is generated using a machine learning method that inputs a representation of the local scene graphs and generates the individual scene graphs based on a clustering algorithm. ### Claim 20 A non-transitory computer-readable storage medium, storing program instructions executable by one or more processors of an electronic device to perform operations comprising: obtaining sensor data for a physical environment; generating a local scene graph for the physical environment based on the sensor data, wherein the local scene graph represents a set of objects and relationships between the objects; identifying a principal scene graph from a set of previously obtained principal scene graphs based on matching characteristics and relationships between the set of objects associated with the local scene graph to one or more characteristics and relationships between a set of objects associated with each principal scene graph; and executing one or more scripted actions involving the objects based on a narrative associated with the identified principal scene graph.