# US 9,870,514 B2 · Hypotheses line mapping and verification for 3D maps > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,870,514 B2 - Document ID: US9870514B2 - Status: Granted - Kind: B2 - Application number: 14/791,205 - Filed: 2015-07-02 - Published: 2017-01-05 - Granted: 2018-01-16 - Earliest claimed: 2015-07-02 - Assignees: QUALCOMM Incorporated - Applicants: QUALCOMM Incorporated - Inventors: Kiyoung Kim; Youngmin Park - Web page: https://patentgrep.com/patent/US9870514B2 ## CPC - G06T 7/543: from line drawings - G06T 7/55: from multiple images - G06T 7/73: using feature-based methods - 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 2207/10016: Video; Image sequence - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## Abstract Disclosed are a device, apparatus, and method for performing line mapping. A three-dimensional (3D) map that includes at least a first and a second 3D line corresponding to an aspect of a real world environment may be obtained. One or more images of the aspect may also be obtained and hypotheses 3D lines may be determined. The hypothesis 3D lines may be verified with the one or more images and the 3D map may be updated. The determination and verification of the hypothesis 3D lines may include creating a plane in 3D space and using co-planarity or orthogonality assumptions. ## Claims ### Claim 1 A computer-implemented method of line mapping, the method comprising: obtaining a three-dimensional (3D) map that includes at least a first and a second 3D line corresponding to one or more aspects of a real world environment; obtaining a first one or more images that include at least a portion of the one or more aspects; generating one or more hypotheses 3D lines according to a combination of the 3D map and the first one or more images; obtaining a second one or more images that include at least a portion of the one or more aspects, wherein the second one or more images captured from a different position than the first one or more images; and verifying, from second one or more images, at least one of the one or more hypotheses 3D lines correspond to the one or more aspects, wherein verifying the one or more hypotheses 3D lines correspond to the aspect comprises applying an edge filter to the second one or more images to obtain a magnitude of the one or more hypotheses 3D lines. ### Claim 2 (depends on 1) The method of claim 1, further comprising: updating, in response to a successful verification of the one or more hypotheses 3D lines, the 3D map to include the one or more hypotheses 3D lines. ### Claim 3 (depends on 1) The method of claim 1, wherein generating one or more hypotheses 3D lines comprises: defining a plane in 3D space based on the first 3D line and the second 3D line; identifying one or more 3D lines orthogonal to the plane; and selecting one or more of the 3D lines orthogonal to the plane as the one or more hypotheses 3D lines. ### Claim 4 (depends on 1) The method of claim 1, wherein applying the edge filter includes applying a Sobel edge filter. ### Claim 5 (depends on 1) The method of claim 1, wherein generating the one or more hypotheses 3D lines includes extracting one or more lines from the first one or more images, and wherein the hypotheses 3D lines are based on the extracted one or more lines. ### Claim 6 (depends on 5) The method of claim 5, wherein verifying that the one or more hypotheses 3D lines correspond to the aspect includes: defining a plane in 3D space based on the first 3D line and the second 3D line; and determining whether the one or more hypotheses 3D lines are co-planar with the plane. ### Claim 7 A machine readable non-transitory storage medium having stored line mapping program instructions executable by a processor to: obtain a three-dimensional (3D) map that includes at least a first and a second 3D line corresponding to one or more aspects of a real world environment; obtain a first one or more images that include at least a portion of the one or more aspects; generate one or more hypotheses 3D lines according to a combination of the 3D map and the first one or more images; obtain a second one or more images that include at least a portion of the one or more aspects, wherein the second one or more images captured from a different position than the first one or more images; and verify, from second one or more images, at least one of the one or more hypotheses 3D lines correspond to the one or more aspects, wherein the instructions to verify the one or more hypotheses 3D lines correspond to the aspect comprises instructions to apply an edge filter to the one or more images to obtain a magnitude of the one or more hypotheses 3D lines. ### Claim 8 (depends on 7) The medium of claim 7, further comprising instructions to: update, in response to a successful verification of the one or more hypotheses 3D lines, the 3D map to include the one or more hypotheses 3D lines. ### Claim 9 (depends on 7) The medium of claim 7, wherein the instructions to generate one or more hypotheses 3D lines includes instructions to: define a plane in 3D space based on the first 3D line and the second 3D line; identify one or more 3D lines orthogonal to the plane; and select one or more of the 3D lines orthogonal to the plane as the one or more hypotheses 3D lines. ### Claim 10 (depends on 7) The medium of claim 7, wherein the instructions to apply the edge filter includes instructions to apply a Sobel edge filter. ### Claim 11 (depends on 7) The medium of claim 7, wherein the instructions to generate the one or more hypotheses 3D lines includes instructions to extract one or more lines from the one or more images, and wherein the hypotheses 3D lines are based on the extracted one or more lines. ### Claim 12 (depends on 11) The medium of claim 11, wherein the instructions to verify that the one or more hypotheses 3D lines correspond to the aspect includes instructions to: define a plane in 3D space based on the first 3D line and the second 3D line; and determine whether the one or more hypotheses 3D lines are co-planar with the plane. ### Claim 13 A device for line mapping, comprising: memory; a processor coupled to the memory and configured to: obtain a three-dimensional (3D) map that includes at least a first and a second 3D line corresponding to one or more aspects of a real world environment; obtain a first one or more images that include at least a portion of the one or more aspects; generate one or more hypotheses 3D lines according to a combination of the 3D map and the first one or more images; obtain a second one or more images that include at least a portion of the one or more aspects, wherein the second one or more images captured from a different position than the first one or more images; and verify, from second one or more images, at least one of the one or more hypotheses 3D lines correspond to the one or more aspects, wherein the instructions to verify the one or more hypotheses 3D lines correspond to the aspect comprises instructions to apply an edge filter to the one or more images to obtain a magnitude of the one or more hypotheses 3D lines. ### Claim 14 (depends on 13) The device of claim 13, further comprising instructions to: update, in response to a successful verification of the one or more hypotheses 3D lines, the 3D map to include the one or more hypotheses 3D lines. ### Claim 15 (depends on 13) The device of claim 13, wherein the instructions to process the first 3D line and the second 3D line comprises instructions to: define a plane in 3D space based on the first 3D line and the second 3D line; identify one or more 3D lines orthogonal to the plane; and select one or more of the 3D lines orthogonal to the plane as the one or more hypotheses 3D lines. ### Claim 16 (depends on 13) The device of claim 13, wherein the instructions to apply the edge filter includes instructions to apply a Sobel edge filter. ### Claim 17 (depends on 13) The device of claim 13, wherein the instructions to determine the one or more hypotheses 3D lines includes instructions to extract one or more lines from the one or more images, and wherein the hypotheses 3D lines are based on the extracted one or more lines. ### Claim 18 (depends on 17) The device of claim 17, wherein the instructions to verify that the one or more hypotheses 3D lines correspond to the aspect includes instructions to: define a plane in 3D space based on the first 3D line and the second 3D line; and determine whether the one or more hypotheses 3D lines are co-planar with the plane. ### Claim 19 An apparatus for performing line mapping, the apparatus comprising: means for obtaining a three-dimensional (3D) map that includes at least a first and a second 3D line corresponding to one or more aspects of a real world environment; means for obtaining a first one or more images that include at least a portion of the one or more aspects; means for generating one or more hypotheses 3D lines according to a combination of the 3D map and the first one or more images; means for obtaining a second one or more images that include at least a portion of the one or more aspects, wherein the second one or more images captured from a different position than the first one or more images; and means for verifying, from second one or more images, at least one of the one or more hypotheses 3D lines correspond to the one or more aspects, wherein the means for verifying the one or more hypotheses 3D lines correspond to the aspect comprises means for applying an edge filter to the one or more images to obtain a magnitude of the one or more hypotheses 3D lines. ### Claim 20 (depends on 19) The apparatus of claim 19, further comprising: means for updating, in response to a successful verification of the one or more hypotheses 3D lines, the 3D map to include the one or more hypotheses 3D lines. ### Claim 21 (depends on 19) The apparatus of claim 19, wherein the means for generating the one or more hypotheses 3D lines comprises: means for defining a plane in 3D space based on the first 3D line and the second 3D line; means for identifying one or more 3D lines orthogonal to the plane; and means for selecting one or more of the 3D lines orthogonal to the plane as the one or more hypotheses 3D lines. ### Claim 22 (depends on 19) The apparatus of claim 19, wherein the means for applying the edge filter includes means for applying a Sobel edge filter. ### Claim 23 (depends on 19) The apparatus of claim 19, wherein the means for generating the one or more hypotheses 3D lines includes means for extracting one or more lines from the one or more images, and wherein the hypotheses 3D lines are based on the extracted one or more lines. ### Claim 24 (depends on 23) The apparatus of claim 23, wherein verifying that the one or more hypotheses 3D lines correspond to the aspect includes: means for defining a plane in 3D space based on the first 3D line and the second 3D line; and means for determining whether the one or more hypotheses 3D lines are co-planar with the plane.