# US 11,443,453 B2 · Method and device for detecting planes and/or quadtrees for use as a virtual substrate > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,443,453 B2 - Document ID: US11443453B2 - Status: Granted - Kind: B2 - Application number: 16/983,722 - Filed: 2020-08-03 - Published: 2020-11-19 - Granted: 2022-09-13 - Earliest claimed: 2017-06-02 - Assignees: Apple Inc. - Applicants: Apple Inc. - Inventors: Giancarlo Yerkes; Aitor Aldoma Buchaca; Na Wong; Oliver Montague Dunkley - Web page: https://patentgrep.com/patent/US11443453B2 ## CPC - G06T 7/73: using feature-based methods - G06F 3/04845: for image manipulation, e.g. dragging, rotation, expansion or change of colour - G06T 11/40: Filling planar surfaces by adding surface attributes, e.g. adding colours or textures - G06T 19/006: {Mixed reality (object pose determination, tracking or camera calibration for mixed reality G06T7/00)} - G06T 19/20: Editing of three-dimensional [3D] images, e.g. changing shapes or colours, aligning objects or positioning parts - G06T 2200/24: involving graphical user interfaces [GUIs] - G06T 2207/10028: Range image; Depth image; 3D point clouds - G06T 2219/2016: Rotation, translation, scaling - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract An electronic device: obtains a plurality of sets of images; synthesizes a three-dimensional point cloud for each of the plurality of sets of images; constructs planes using the respective three-dimensional point clouds; and generates a merged set of quadtrees characterizing a merged set of planes across the three-dimensional point clouds. ## Claims ### Claim 1 A method comprising: at an electronic device with one or more processors and non-transitory memory: obtaining a plurality of sets of images associated with different capture times; synthesizing a three-dimensional point cloud for each of the plurality of sets of images; generating a plurality of sets of quadtrees based on the respective three-dimensional point clouds; and generating a merged set of quadtrees based on the plurality of sets of quadtrees, wherein the merged set of quadtrees characterize a merged set of planes across the three-dimensional point clouds. ### Claim 2 (depends on 1) The method of claim 1, further comprising: constructing a set of one or more planes for each of the three-dimensional point clouds, wherein the plurality of sets of quadtrees are generated from the sets of one or more planes, and wherein the merged set of planes corresponds to a correlation between the sets of one or more planes across a temporal dimension. ### Claim 3 (depends on 2) The method of claim 2, wherein the correlation between the sets of one or more planes across the temporal dimension includes at least one of: enlarging planes, merging planes, or correcting planes. ### Claim 4 (depends on 1) The method of claim 1, wherein generating the merged set of quadtrees includes generating the merged set of merged quadtrees by correlating the plurality of sets of quadtrees across a temporal dimension. ### Claim 5 (depends on 4) The method of claim 4, wherein correlating the plurality of sets of quadtrees includes at least one of: enlarging portions of quadtrees, merging quadtrees, or correcting portions of quadtrees. ### Claim 6 (depends on 2) The method of claim 2, wherein constructing the sets of one or more planes includes fitting planes to clusters of points in the three-dimension point clouds to obtain the merged set of planes; and wherein generating the merged set of quadtrees includes: triangulating points across the three-dimensional point clouds; removing triangles having points that are not in the merged set of planes to obtain constrained triangulated regions; projecting the constrained triangulated regions onto the merged set of planes; and quadratizing the constrained triangulated regions to obtain the merged set of quadtrees. ### Claim 7 (depends on 1) The method of claim 1, further comprising: displaying, on a display of the electronic device, a media capture preview of objects in a field of view of an image sensor of the electronic device, wherein the media capture preview changes as the objects in the field of view of the image sensor change; and in response to generating the merged set of quadtrees, displaying, on the display, planes associated with the set of merged quadtrees overlaid on the media capture preview, wherein a perimeter of the planes correspond to bounds of the set of merged quadtrees. ### Claim 8 (depends on 7) The method of claim 7, further comprising: while displaying the planes overlaid on the media capture preview, detecting, via one or more inputs devices of the electronic device, a user input that corresponds to selecting an augmented or virtual reality object from an object selection interface; and in response to detecting the user input, displaying, on the display, the selected augmented or virtual reality object overlaid on the media capture preview relative to one of the planes. ### Claim 9 (depends on 1) The method of claim 1, wherein a first set of images in plurality of sets of images corresponds to a first reference point, and wherein a second set of images in plurality of sets of images corresponds to a second reference point. ### Claim 10 (depends on 1) The method of claim 1, wherein each quadtree in the merged set of quadtrees provides an indication of one of: a substantially horizontal plane, a substantially vertical plane, or a plane angled according one or more of three degrees of freedom. ### Claim 11 An electronic device, comprising: one or more processors; non-transitory memory; and one or more programs, wherein the one or more programs are stored in the non-transitory memory and configured to be executed by the one or more processors, the one or more programs including instructions for: obtaining a plurality of sets of images associated with different capture times; synthesizing a three-dimensional point cloud for each of the plurality of sets of images; generating a plurality of sets of quadtrees based on the respective three-dimensional point clouds; and generating a merged set of quadtrees based on the plurality of sets of quadtrees, wherein the merged set of quadtrees characterize a merged set of planes across the three-dimensional point clouds. ### Claim 12 (depends on 11) The electronic device of claim 11, wherein the one or more programs further include instructions for: constructing a set of one or more planes for each of the three-dimensional point clouds, wherein the plurality of sets of quadtrees are generated from the sets of one or more planes, and wherein the merged set of planes corresponds to a correlation between the sets of one or more planes across a temporal dimension. ### Claim 13 (depends on 12) The electronic device of claim 12, wherein the correlation between the sets of one or more planes across the temporal dimension includes at least one of: enlarging planes, merging planes, or correcting planes. ### Claim 14 (depends on 11) The electronic device of claim 11, wherein generating the merged set of quadtrees includes generating the merged set of merged quadtrees by correlating the plurality of sets of quadtrees across a temporal dimension. ### Claim 15 (depends on 14) The electronic device of claim 14, wherein correlating the plurality of sets of quadtrees includes at least one of: enlarging portions of quadtrees, merging quadtrees, or correcting portions of quadtrees. ### Claim 16 (depends on 12) The electronic device of claim 12, wherein constructing the sets of one or more planes includes fitting planes to clusters of points in the three-dimension point clouds to obtain the merged set of planes; and wherein generating the merged set of quadtrees includes: triangulating points across the three-dimensional point clouds; removing triangles having points that are not in the merged set of planes to obtain constrained triangulated regions; projecting the constrained triangulated regions onto the merged set of planes; and quadratizing the constrained triangulated regions to obtain the merged set of quadtrees. ### Claim 17 A non-transitory computer readable storage medium storing one or more programs, the one or more programs comprising instructions, which, when executed by an electronic device, cause the electronic device to: obtain a plurality of sets of images associated with different capture times; synthesize a three-dimensional point cloud for each of the plurality of sets of images; generate a plurality of sets of quadtrees based on the respective three-dimensional point clouds; and generate a merged set of quadtrees based on the plurality of sets of quadtrees, wherein the merged set of quadtrees characterize a merged set of planes across the three-dimensional point clouds. ### Claim 18 (depends on 17) The non-transitory computer readable storage medium of claim 17, wherein the instructions further cause the electronic device to: construct a set of one or more planes includes constructing a plurality of sets of planes for each of the three-dimensional point clouds, wherein the plurality of sets of quadtrees are generated from the sets of one or more planes, and wherein the merged set of planes corresponds to a correlation between the sets of one or more planes across a temporal dimension. ### Claim 19 (depends on 18) The non-transitory computer readable storage medium of claim 18, wherein the correlation between the sets of one or more planes across the temporal dimension includes at least one of: enlarging planes, merging planes, or correcting planes. ### Claim 20 (depends on 17) The non-transitory computer readable storage medium of claim 17, wherein generating the merged set of quadtrees includes generating the merged set of merged quadtrees by correlating the plurality of sets of quadtrees across a temporal dimension. ### Claim 21 (depends on 20) The non-transitory computer readable storage medium of claim 20, wherein correlating the plurality of sets of quadtrees includes at least one of: enlarging portions of quadtrees, merging quadtrees, or correcting portions of quadtrees. ### Claim 22 (depends on 18) The non-transitory computer readable storage medium of claim 18, wherein constructing the sets of one or more planes includes fitting planes to clusters of points in the three-dimension point clouds to obtain the merged set of planes; and wherein generating the merged set of quadtrees includes: triangulating points across the three-dimensional point clouds; removing triangles having points that are not in the merged set of planes to obtain constrained triangulated regions; projecting the constrained triangulated regions onto the merged set of planes; and quadratizing the constrained triangulated regions to obtain the merged set of quadtrees.