# US 9,519,061 B2 · Geometric fingerprinting for localization of a device > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,519,061 B2 - Document ID: US9519061B2 - Status: Granted - Kind: B2 - Application number: 14/583,375 - Filed: 2014-12-26 - Published: 2016-06-30 - Granted: 2016-12-13 - Earliest claimed: 2014-12-26 - Assignees: HERE Global B.V. - Applicants: HERE Global B.V. - Inventors: Leo Modica; Leon Stenneth; James Lynch - Web page: https://patentgrep.com/patent/US9519061B2 ## CPC - H04W 4/02: Services making use of location information - G01C 21/005: {with correlation of navigation data from several sources, e.g. map or contour matching (G01C21/30 takes precedence)} - G01S 5/16: using electromagnetic waves other than radio waves - G01S 7/4808: {Evaluating distance, position or velocity data} - G01S 13/08: Systems for measuring distance only (indirect measurement G01S13/46) - G01S 15/08: Systems for measuring distance only (indirect measurement G01S15/46) - G01S 17/06: Systems determining position data of a target - G01S 17/08: for measuring distance only (indirect measurement G01S17/46; active triangulation systems G01S17/48) - G05D 1/0274: {using mapping information stored in a memory device (navigation using map-matching G01C21/30)} - G06T 7/11: Region-based segmentation - G06T 7/62: of area, perimeter, diameter or volume - G06T 7/73: using feature-based methods - G06T 7/74: {involving reference images or patches} - G06T 2207/10028: Range image; Depth image; 3D point clouds - G06T 2207/20021: Dividing image into blocks, subimages or windows - G06T 2207/30248: Vehicle exterior or interior - H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72) - G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S) - G01S: RADIO DIRECTION-FINDING; RADIO NAVIGATION; DETERMINING DISTANCE OR VELOCITY BY USE OF RADIO WAVES; LOCATING OR PRESENCE-DETECTING BY USE OF THE REFLECTION OR RERADIATION OF RADIO WAVES; ANALOGOUS ARRANGEMENTS USING OTHER WAVES - G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## Abstract Systems, apparatuses, and methods are provided for developing a fingerprint database for and determining the geographic location of an end-user device (e.g., vehicle, mobile phone, smart watch, etc.) with the database. A fingerprint database may be developed by receiving a depth map for a location in a path network, and then identifying physical structures within the depth map. The depth map may be divided, at each physical structure, into one or more horizontal planes at one or more elevations from a road level. Two-dimensional feature geometries may be extracted from the horizontal planes. At least a portion of the extracted feature geometries may be encoded into the fingerprint database. ## Claims ### Claim 1 A method comprising: receiving a three-dimensional depth map for a location in a path network using a depth sensing device; identifying, using a processor, data indicative of physical structures within the depth map; dividing the depth map, at each physical structure, into one or more horizontal slices corresponding to one or more elevations from a road level, each horizontal slice having a thickness range associated with the respective elevation and including data from the depth map in the thickness range above and below the respective elevation; identifying data points of the one or more horizontal slices representing feature geometries of the physical structures; extracting two-dimensional feature geometries from the identified data points; encoding portions of the extracted feature geometries into a database; and providing the encoded portions of the extracted feature geometries for determination of a current geographic location of a vehicle. ### Claim 2 (depends on 1) The method of claim 1, wherein the depth sensing device is selected from the group consisting of: a LIDAR camera, a RADAR device, an ultrasound device, a structure light camera, and a moving mono-camera. ### Claim 3 (depends on 1) The method of claim 1, wherein the one or more horizontal slices have a thickness of 0.1-2 meters. ### Claim 4 (depends on 1) The method of claim 1, wherein the two-dimensional feature geometries comprise lines, arcs, or splines. ### Claim 5 (depends on 1) The method of claim 1, further comprising: ranking the extracted feature geometries to provide a ranking value for each extracted feature geometry, wherein the ranking is based on one or more of the following factors: (1) shape of the feature geometries, (2) a size of the feature geometries, (3) an elevation of the feature geometries, or (4) variance of the feature geometries; and sorting the ranked feature geometries from highest to lowest ranked feature geometries, wherein the portion of extracted feature geometries encoded in the database correlate with the highest ranked feature geometries. ### Claim 6 (depends on 1) The method of claim 1, wherein the encoding of the portion of the feature geometries comprises storing geographic attributes of selected control points of the feature geometries, wherein the geographic attributes comprise, for each selected control point, a latitude, a longitude, and an elevation above the road level. ### Claim 7 A method comprising: collecting a three-dimensional depth map at a location in a path network using a depth sensing camera attached to an end-user device; dividing, using a processor, the depth map into one or more horizontal slices, each horizontal slice at a defined elevation from a road level and having a thickness in a range above and below the defined elevation, wherein each horizontal slice includes data from the depth map within a range above and below each respective elevation; extracting two-dimensional feature geometries comprising one or more sets of connected lines from the one or more horizontal slices; determining a geographic location of the end-user device through a comparison of at least a portion of the extracted feature geometries and a database of feature geometries for the path network; and providing the geographic location to the end-user device. ### Claim 8 (depends on 7) The method in claim 7, further comprising: ascertaining a geographic orientation of the end-user device through a comparison of the extracted feature geometries and the database of feature geometries. ### Claim 9 (depends on 7) The method of claim 7, wherein the end-user device is a vehicle, and wherein the depth sensing camera is selected from the group consisting of: a LIDAR camera, a RADAR device, an ultrasound device, a structure light camera, and a moving mono-camera. ### Claim 10 (depends on 7) The method of claim 7, further comprising: ranking the extracted feature geometries to provide a ranking value for each extracted feature geometry, wherein the ranking is based on one or more of the following factors: (1) shape of the feature geometries, (2) a size of the feature geometries, (3) an elevation of the feature geometries, or (4) variance of the feature geometries; and sorting the ranked feature geometries from highest to lowest ranked feature geometries, wherein the portion of extracted feature geometries used in the comparison with the database comprise the highest ranked feature geometries. ### Claim 11 (depends on 7) The method of claim 7, wherein the two-dimensional feature geometries comprise lines, arcs, or splines. ### Claim 12 (depends on 7) The method of claim 7, wherein the geographic location of the device is determined using (1) geographic attributes of selected control points of the feature geometries in the database and (2) a determined distance of the device from each selected control point of the feature geometries, wherein the geographic attributes comprise, for each selected control point, a latitude, a longitude, and an elevation above the road level. ### Claim 13 An apparatus comprising: at least one processor; and at least one memory including computer program code for one or more programs; the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to at least perform: receive a three-dimensional depth map for a location in a path network from a depth sensing device; identify physical structures within the depth map at the location; divide the depth map into one or more horizontal slices, each of the one or more horizontal slices at a defined elevation from a road level and having a thickness in a range above and below the defined elevation, wherein each horizontal slice includes data from the depth map at the defined elevation and includes data from the depth map in the range above and below the defined elevation, until at least one feature geometry of a physical structure is identified; extract at least one two-dimensional feature geometry from the one or more horizontal slices; and encode at least a portion of the extracted at least one feature geometry into a database. ### Claim 14 (depends on 13) The apparatus of claim 13, wherein the depth sensing device is selected from the group consisting of: a LIDAR camera, a RADAR device, an ultrasound device, a structure light camera, and a moving mono-camera. ### Claim 15 (depends on 13) The apparatus of claim 13, wherein the at least one memory and the computer program code are configured to cause the apparatus to further perform: rank extracted feature geometries to provide a ranking value for each extracted feature geometry, wherein the ranking is based on one or more of the following factors: (1) shape of the feature geometries, (2) a size of the feature geometries, (3) an elevation of the feature geometries, or (4) variance of the feature geometries; and sort the ranked feature geometries from highest to lowest ranked feature geometries, wherein the portion of extracted feature geometries encoded in the database correlate with the highest ranked feature geometries. ### Claim 16 (depends on 13) The apparatus of claim 13, wherein the encoding of the portion of the at least one feature geometry comprises storing geographic attributes of selected control points of the at least one feature geometry, wherein the geographic attributes comprise, for each selected control point, a latitude, a longitude, and an elevation above the road level. ### Claim 17 An apparatus comprising: at least one processor; and at least one memory including computer program code for one or more programs; the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to at least perform: collect a three-dimensional depth map at a location in a path network using a depth sensing camera attached to an end-user device; identify physical structures within the depth map at the location; divide the depth map, at each physical structure, into one or more horizontal slices, each of the one or more horizontal slices at a defined elevation from a road level and having a thickness in a range above and below the defined elevation, wherein the one or more horizontal slices include data from the depth map at the defined elevation and include data from the depth map in the range above and below the defined elevation; extract two-dimensional feature geometries comprising one or more sets of connected lines from the ones or more horizontal slices; determine a geographic location of the end-user device through a comparison of at least a portion of the extracted feature geometries and a database of feature geometries for the path network; and provide the geographic location of the end-user device to the end-user device. ### Claim 18 (depends on 17) The apparatus of claim 17, wherein the at least one memory and the computer program code are configured to cause the apparatus to further perform: ascertain a geographic orientation of the end-user device through a comparison of the extracted feature geometries and the database of feature geometries. ### Claim 19 (depends on 17) The apparatus of claim 17, wherein the at least one memory and the computer program code are configured to cause the apparatus to further perform: rank the extracted feature geometries to provide a ranking value for each extracted feature geometry, wherein the ranking is based on one or more of the following factors: (1) shape of the feature geometries, (2) a size of the feature geometries, (3) an elevation of the feature geometries, or (4) variance of the feature geometries; and sort the ranked feature geometries from highest to lowest ranked feature geometries, wherein the portion of extracted feature geometries used in the comparison with the database comprise the highest ranked feature geometries. ### Claim 20 (depends on 17) The apparatus of claim 17, wherein the geographic location of the end-user device is determined using (1) geographic attributes of selected control points of the feature geometries in the database and (2) a determined distance of the end-user device from each selected control point of the feature geometries, wherein the geographic attributes comprise, for each selected control point, a latitude, a longitude, and an elevation above the road level.