# US 12,602,430 B2 · Method for constructing positioning DB using clustering of local features and apparatus for constructing positioning DB > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,602,430 B2 - Document ID: US12602430B2 - Status: Granted - Kind: B2 - Application number: 17/852,037 - Filed: 2022-06-28 - Published: 2022-12-29 - Granted: 2026-04-14 - Earliest claimed: 2021-06-28 - Assignees: SK Telecom Co., Ltd. - Applicants: SK Telecom Co., Ltd. - Inventors: Taekyeong Lee - Web page: https://patentgrep.com/patent/US12602430B2 ## CPC - G06F 16/75: Clustering; Classification - G06F 16/7328: {Query by example, e.g. a complete video frame or video sequence (graphical querying G06F16/7335)} - G06T 19/003: {Navigation within 3D models or images} - 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/762: using clustering, e.g. of similar faces in social networks - G06V 20/46: {Extracting features or characteristics from the video content, e.g. video fingerprints, representative shots or key frames} - G06V 20/647: {by matching two-dimensional images to three-dimensional objects} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING ## Abstract A method of constructing a positioning DB performed by an apparatus for constructing the positioning DB, may comprise: extracting a plurality of local features from a plurality of keyframes capturing a predetermined region; determining an individual 3D keypoint including information on a 3-dimensional position of each of the plurality of local features; clustering the plurality of local features into a plurality of clusters based on the individual 3D keypoint; determining a representative position information representatively indicating a position of each of the plurality of clusters by using the individual 3D keypoint of the local feature included in each of the plurality of clusters; and storing, for each of the plurality of keyframes, an cluster identification for identifying each of the plurality of clusters and the representative position information of each of the plurality of clusters in the positioning DB. ## Claims ### Claim 1 A computer-implemented method for constructing a positioning database (DB) performed by an apparatus for constructing the positioning DB, the method comprising: extracting a plurality of local features from a plurality of keyframes capturing a predetermined region by executing a neural network on one or more processors, the plurality of keyframes captured using a light detection and ranging (LiDAR) sensor and a camera; determining, by the one or more processors, an individual 3D keypoint including information on a 3-dimensional position of each of the plurality of local features; clustering the plurality of local features into a plurality of clusters to reduce a size of the positioning DB for storing in a memory by at least: determining a 2D keypoint indicating a position of each of the plurality of local features, determining the individual 3D keypoint of each of the plurality of local features and a covariance of the individual 3D keypoint using the 2D keypoint of each of the plurality of local features, and clustering the plurality of local features into the plurality of clusters using the covariance of the individual 3D keypoint of each of the plurality of local features; determining a representative position information representatively indicating a position of each of the plurality of clusters by using the individual 3D keypoint of the local feature included in each of the plurality of clusters; and storing, for each of the plurality of keyframes, cluster identification for identifying each of the plurality of clusters and the representative position information of each of the plurality of clusters in the positioning DB, wherein each of the local features included in each of the plurality of keyframes corresponds to one of the plurality of clusters. ### Claim 2 (depends on 1) The method of claim 1, wherein the clustering of the plurality of local features into the plurality of clusters comprises: clustering local features indicating a same point on a three-dimensional space within the predetermined region among the plurality of local features, based on the individual 3D keypoint of each of the plurality of local features. ### Claim 3 (depends on 1) The method of claim 1, further comprises: determining an individual descriptor of each of the plurality of local features, which includes information for distinguishing the plurality of local features. ### Claim 4 (depends on 1) The method of claim 1, wherein the representative position information comprises: a representative 3D keypoint including a 3-dimensional keypoint on each of the plurality of clusters based on the individual 3D keypoint of local features, and a representative descriptor including a descriptor on each of the plurality of clusters based on the individual descriptor of local features. ### Claim 5 (depends on 1) The method of claim 1, wherein the clustering of the plurality of local features into the plurality of clusters comprises: if a first cluster among one or more previously generated clusters satisfies a preset clustering condition with respect to a first local feature among the plurality of local features, including a first local feature in the first cluster feature for the first local feature among the plurality of local features, and wherein the preset clustering condition comprises at least one of a distance between an individual 3D keypoint of the first local feature and a representative keypoint of the first cluster, a parallax angle between keyframes corresponding to each of the local features included in the first cluster and a keyframe including the first local feature, and an epipolar distance between local features in the first cluster and the first local feature. ### Claim 6 (depends on 5) The method of claim 5, wherein the clustering of the plurality of local features into the plurality of clusters further comprises: if there is no cluster satisfying the preset clustering condition among the one or more previously generated clusters, generating a second cluster including a second local feature for the second local feature among the plurality of local features. ### Claim 7 (depends on 4) The method of claim 4, wherein the clustering of the plurality of local features into the plurality of clusters comprises: clustering the plurality of local features into at least one cluster based on the individual 3D keypoint of each of the plurality of local features; and re-clustering the at least one cluster into the plurality of clusters based on the individual descriptor of each of the plurality of local features. ### Claim 8 (depends on 7) The method of claim 7, wherein the re-clustering of the plurality of local features into the plurality of clusters further comprises: re-clustering the at least one cluster into the plurality of clusters based on a result of applying the individual descriptor of each of the plurality of local features to a preset clustering condition, and wherein the preset clustering condition comprises at least one of a distance between a descriptor of each of the plurality of local features and the representative descriptor of the at least one cluster, and the number of local features included in the at least one cluster. ### Claim 9 (depends on 8) The method of claim 8, wherein the re-clustering of the plurality of local features into the plurality of clusters further comprises: generating a list for the at least one cluster; re-clustering the local features included in a first cluster into the plurality of clusters if the local features included in the first cluster among the at least one cluster satisfy the preset clustering condition; and removing the first cluster from the list and adding the plurality of re-clustered clusters into the list. ### Claim 10 (depends on 4) The method of claim 4, wherein the positioning DB comprises a keyframe DB and a cluster DB, a global feature of each of the plurality of keyframes and an ID of a cluster corresponding to each of local features included in each of the plurality of keyframes are stored in the keyframe DB, and the representative 3D keypoint and the representative descriptor of each of the plurality of clusters are stored in the cluster DB. ### Claim 11 An apparatus for constructing a positioning database (DB), the apparatus comprising: a memory in which a positioning DB constructing program for generating data to be constructed in the positioning DB is stored; and a processor configured to load the positioning DB constructing program from the memory, wherein the processor is configured to execute the positioning DB constructing program to: extract a plurality of local features from a plurality of keyframes capturing a predetermined region by executing a neural network, the plurality of keyframes captured using a light detection and ranging (LiDAR) sensor and a camera; determine an individual 3D keypoint including information on a 3-dimensional position of each of the plurality of local features; cluster the plurality of local features into a plurality of clusters to reduce a size of the positioning DB for storing in a memory by at least: determining a 2D keypoint indicating a position of each of the plurality of local features, determining the individual 3D keypoint of each of the plurality of local features and a covariance of the individual 3D keypoint using the 2D keypoint of each of the plurality of local features, and clustering the plurality of local features into the plurality of clusters using the covariance of the individual 3D keypoint of each of the plurality of local features; determine a representative position information representatively indicating a position of each of the plurality of clusters by using the individual 3D keypoint of the local feature included in each of the plurality of clusters; and store, for each of the plurality of keyframes, cluster identification for identifying each of the plurality of clusters and the representative position information of each of the plurality of clusters in the positioning DB, wherein each of the local features included in each of the plurality of keyframes corresponds to one of the plurality of clusters. ### Claim 12 (depends on 11) The apparatus of claim 11, wherein the processor is configured to cluster local features indicating a same point on a three-dimensional space within the predetermined region among the plurality of local features, based on the individual 3D keypoint of each of the plurality of local features. ### Claim 13 (depends on 11) The apparatus of claim 11, wherein the processor is configured to determine an individual descriptor of each of the plurality of local features, which includes information for distinguishing the plurality of local features. ### Claim 14 (depends on 13) The apparatus of claim 13, wherein the representative position information comprises: a representative 3D keypoint including a 3-dimensional keypoint on each of the plurality of clusters based on the individual 3D keypoint of local features, and a representative descriptor including a descriptor on each of the plurality of clusters based on the individual descriptor of local features. ### Claim 15 (depends on 14) The apparatus of claim 14, wherein the processor is configured to: cluster the plurality of local features into at least one cluster based on the individual 3D keypoint of each of the plurality of local features; and re-cluster the at least one cluster into the plurality of clusters based on the individual descriptor of each of the plurality of local features. ### Claim 16 (depends on 15) The apparatus of claim 15, wherein the processor is configured to re-cluster the at least one cluster into the plurality of clusters based on a result of applying the individual descriptor of each of the plurality of local features to a preset clustering condition, and wherein the preset clustering condition comprises at least one of a distance between a descriptor of each of the plurality of local features and the representative descriptor of the at least one cluster, and the number of local features included in the at least one cluster. ### Claim 17 (depends on 16) The apparatus of claim 16, wherein the processor is configured to: generate a list for the at least one cluster; re-cluster the local features included in a first cluster into the plurality of clusters if the local features included in the first cluster among the at least one cluster satisfy the preset clustering condition; and remove the first cluster from the list and add the plurality of re-clustered clusters into the list. ### Claim 18 (depends on 14) The apparatus of claim 14, wherein the positioning DB comprises a keyframe DB and a cluster DB, a global feature of each of the plurality of keyframes and an ID of a cluster corresponding to each of local features included in each of the plurality of keyframes are stored in the keyframe DB, and the representative 3D keypoint and the representative descriptor of each of the plurality of clusters are stored in the cluster DB.