Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

K nearest neighbor search method for point cloud simplification

A search method and K-nearest neighbor technology, applied in the field of point cloud simplified K-nearest neighbor search, which can solve the problems of huge amount of point cloud data and unacceptable computational complexity.

Inactive Publication Date: 2013-06-05
CHANGSHU RES INSTITUE OF NANJING UNIV OF SCI & TECH
View PDF1 Cites 18 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0004] The amount of point cloud data obtained through 3D scanning is extremely large. If you directly calculate the distance from one point to all other points, and then sort the top K according to the distance, the computational complexity is obviously unacceptable.

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • K nearest neighbor search method for point cloud simplification
  • K nearest neighbor search method for point cloud simplification
  • K nearest neighbor search method for point cloud simplification

Examples

Experimental program
Comparison scheme
Effect test

experiment example 1

[0053] Experimental example 1: Test method effect

[0054] The parameter N in the above method is a very important parameter, and its influence on the effect of the method will be analyzed below.

[0055] The octree is a hierarchical structure, which is manifested in the Morton code, that is, the Morton codes at the same level have the same length, and the deeper the Morton code is, the longer it is. This feature brings difficulties to the K-nearest neighbor search.

[0056] The numerical proximity of Mortoon codes means that the points are relatively close in space, and it also means that these points are at the same level of the octree. However, it is very likely that some neighbors are located in different layers of the octree from the center point, resulting in a large difference between their Morton code value and the Morton value of the center point, which will cause this part of the neighbors to be missed during the search, making the search accuracy worse. reduce. Th...

experiment example 2

[0058] Experimental Example 2: Test Time Performance

[0059] The larger N is, the more points are obtained, the greater the calculation amount when determining the neighbors, and this calculation amount increases linearly with the increase of N value, and the main time is spent on the calculation of the spatial distance.

[0060] Table 1 and Table 2 reflect the running time of this method from different aspects. However, the smaller N is, the more severe the Riemannian block is, and the more inaccurate K-nearest neighbor search results are. Accuracy is efficiency is a contradiction in this method.

[0061] The search time is very short when N is small, which makes it suitable for point cloud simplification. Use a relatively small N value to perform K-nearest neighbor search first, and after quickly obtaining K-nearest neighbors, point cloud simplification can be performed to improve the efficiency of simplification. Although the K-nearest neighbor search of some points is ...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention discloses a K nearest neighbor search method for point cloud simplification. The K nearest neighbor search method for the point cloud simplification comprises the following steps: enlarging original data and horizontally moving the original data to map the original data to positive integer space, obtaining Morton codes of any point in the positive integer space through a displacement calculation method, ranking the Morton codes from small to big, respectively obtaining N*K points from the front and the back of the center point, calculating three-dimensional distances between the 2*N*K points and the center point, and selecting advanced K points as the K nearest neighbor.

Description

technical field [0001] The invention relates to the fields of pattern recognition and image processing, in particular to a technique for simplifying point cloud data obtained by three-dimensional scanning, in particular to a K-nearest neighbor search method for point cloud simplification. Background technique [0002] Three-dimensional scanning can directly obtain the sampling point information on the surface of the object, that is, point cloud data, and any surface can be reconstructed by using the point cloud data. In point cloud data processing, point cloud gridding and point cloud simplification all require K-nearest neighbor information. Since K-nearest neighbors reflect important local topological relationships of scattered point clouds, and K-nearest neighbors are searched before surface reconstruction, the efficiency and accuracy of K-nearest neighbors searches are directly related to the efficiency and accuracy of point cloud modeling. [0003] The K nearest neighb...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
IPC IPC(8): G06K9/62
Inventor 王建宇康其桔袁夏
Owner CHANGSHU RES INSTITUE OF NANJING UNIV OF SCI & TECH
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com