CN100444201C - Marker point matching method for point cloud stitching in 3D scanning system - Google Patents

Abstract

A method that can quickly match the landmark points during point cloud stitching: firstly, the first set of point cloud landmark points starting from the successive scans are dynamically divided into layers according to the spatial coordinates and distance values to form layer nesting; The first point cloud at the beginning of the scan is used as the reference, and when the first point cloud at the beginning of the successive scans is matched with the second point cloud at the beginning of the successive scans, the data area that conforms to the actual motion law is pre-estimated before the search and recognition , adopt the method of regional data matching, add the processing result data to the corresponding data layer after matching, recognition and alignment, and carry out the next step of prediction and estimation, and at the same time dynamically correct the data layer, and constantly memorize and optimize it; look for the first image scanned successively When the point cloud matches the marker points of the i-th point cloud scanned successively, and so on.

Description

Marker point matching method for point cloud stitching in 3D scanning system

technical field

Reverse engineering technology (attached Figure 1) is an advanced manufacturing technology that uses 3D digital measuring instruments to digitize products (physical models or prototypes), collects three-dimensional coordinate points of the model, uses CAD software to model, and finally manufactures products, which generally includes Four basic links: 3D shape detection and conversion (acquisition of physical data), data preprocessing (point cloud processing, recognition, multi-view splicing), CAD model establishment (surface reconstruction), and CAM part molding. The present invention mainly relates to a marker point matching method when splicing multi-view point clouds obtained by a three-dimensional scanning system (accompanying drawing 2) on the same object using a multi-view label positioning method in the data preprocessing process of reverse engineering . In engineering practice, point cloud measurement data is generally used in the three-dimensional display of objects or the three-dimensional reconstruction of digital models, so the actual measurement data must be coordinate normalized and complete. In the process of measuring the shape of the product, the geometric data of the product cannot be measured at one time in the same coordinate system, so the coordinates must be normalized. This process is called the relocation of the measured data, that is, the three-dimensional data splicing. In the multi-view label location mosaic algorithm, the quality of splicing can be guaranteed only by finding the correct matching of the marker points. The present invention designs a correct matching method of marker points based on the dynamic layering of spatial data.

Background technique

The multi-view mosaic method is an effective means to expand the range of 3D measurement. According to the difference between the relative motion of the measuring head and the object to be scanned and the image processing method, the splicing methods include: correlation splicing method, rotary splicing method, fringe image splicing method, multi-view label positioning splicing method, etc. In the present invention, the multi-view tag positioning point cloud splicing technology is adopted, and the feature mark points are artificially set up to ensure the complete topological structure of the three-dimensional object. . Space search and recognition of feature marker points is a key issue in the process of 3D point cloud stitching, which directly affects the quality of stitching.

In recent years, the splicing algorithm of 3D point cloud has made great progress both at home and abroad, and a considerable amount of literature has been published, and the correct matching of feature marker points has always been the key and difficult problem.

The ICP algorithm proposed in the literature "A method for registration of 3-D shapes" (P.Besl, and D.McKay.PatternAnal.Mach.Intell., 14(2), 239-256, 1992.) is used for multiple Point cloud splicing based on label positioning is to use an iterative method to minimize the distance between two given point cloud feature mark point sets, and to realize the splicing method, it is necessary to establish a point-to-point mapping relationship. In practical applications, in the absence of a clear corresponding relationship It is difficult to find the point-to-point matching relationship of each feature mark in the point set, and the calculation speed is also very slow, which cannot really solve the practical application problem. The ICL and ICT algorithms proposed in the document "Iterative closest geometric objects registration" (LiQingde, Griffiths J G. Computers and Mathematics with Applications, 40, 2000, Page(s): 1171～1188.) directly perform two given point clouds The points in the data point set are connected and triangulated, and the corresponding line segments or corresponding triangles in the two views are approximately found according to certain criteria, and an objective equation is established to solve it. However, this method cannot accurately locate, lacks an effective criterion for finding a corresponding relationship, and cannot guarantee to obtain a correct matching relationship.

The matching method of the point cloud marker points based on the dynamic layering of spatial data proposed in the present invention, the method of comparison and reasoning and the method based on view recognition and search, according to the three-dimensional geometric topological relationship and spatial distance relationship of the feature marker point set, through searching Excellent, effectively solves the problem of searching and matching recognition between feature mark point groups during point cloud splicing, does not require multiple measurements or complex graphic logic operations, and improves matching speed and accuracy.

Contents of the invention

The invention provides a method capable of quickly matching marker points during point cloud splicing, and the invention has the advantage of low algorithm complexity.

The present invention adopts following technical scheme:

A Marker Point Matching Method for Point Cloud Stitching in a 3D Scanning System

Step 1: Dynamically divide the spatial data set {M _i } (i=0, 1,...n) according to the spatial coordinates and distance values of the first point cloud marker point set at the beginning of successive scans to form a layer-by-layer embedding set, the division criterion is: set the center layer M ₀ , set the side length of its cube to L, take the center layer data as the reference coordinate system, and then dynamically add layers, the side length of the second layer cube is 3L, and the third layer The side length of the cube is 5L, and so on, the side length of the i-th cube is 2i+1, forming layer nesting;

The second step: a) set the first point cloud at the beginning of the successive scans as the benchmark, and point the current data layer _Ma to the data layer where the overlapping area of the first point cloud of the successive scans and the second point cloud of the successive scans is located, In the current data layer M _a and its adjacent inner and outer layers, it is enough to find the first point cloud of successive scans and the marker points of the second point cloud of successive scans to match. The marker point data of the second point cloud is added to the corresponding data layer of the first point cloud at the beginning of the successive scanning, and the data layer of the first point cloud at the beginning of the successive scanning increases dynamically accordingly, and the range expands. When the first point cloud of the successive scanning When the point cloud and the second point cloud of successive scans have no marker points in the current data layer M _a and its adjacent inner and outer layers, an automatic recursive search method is used to start from the outermost layer of the first point cloud of successive scans Search from outside to inside until you find a data area that matches the marker points of the second piece of point cloud scanned successively. Similarly, after the matching is successful, the marker point data layer of the first piece of point cloud that starts from scan successively is also dynamically increased. expanded range,

b) When looking for the first point cloud of successive scans to match the marker points of the third point cloud of successive scans, point the current data layer M _a to the first point cloud of successive scans and the point cloud of successive scans according to the above method. The data layer where the third point cloud overlap area is located, it is enough to find the first point cloud of successive scans in the current data layer _Ma and its adjacent inner and outer layers to match the marker points of the second point cloud of successive scans, After the matching and splicing is successful, the data of the third point cloud at the beginning of each scan is added to the corresponding data layer of the first point cloud at the beginning of each scan, and the data layer of the first point cloud at the beginning of each scan is dynamically increased accordingly. To expand, when the first point cloud of successive scans and the third point cloud of successive scans have no marker points in the current data layer M _a and its adjacent inner and outer layers, the method of automatic recursive search is adopted from the successive scans The outermost layer of the first point cloud starts to search from outside to inside until it finds the data area that matches the marked points of the third point cloud scanned successively. The point data layer is also dynamically increased, and the scope is expanded. When looking for the first point cloud of successive scans to match the marker points of the i-th point cloud of successive scans, and so on;

The matching method of the above marker points is:

Find all the triangles in the current data layer M _a of the first point cloud scanned successively, its adjacent inner and outer layers, and the spliced point cloud with any three marker points as vertices, and record the side lengths of these triangles , area, perimeter, in all the triangles of the current data layer M _a of the first point cloud scanned successively and its adjacent inner and outer layers, find the triangles of the spliced point cloud with the same side length, area, and perimeter The triangles, the vertices of these triangles are the matching marker points;

The present invention is mainly used for matching feature mark points when splicing multi-view cloud in a three-dimensional scanning system. This method mainly has the following advantages:

(1) In the present invention, the multi-view label positioning point cloud splicing technology is adopted, and the mark points adopt artificial prior setting to ensure the complete topological structure of the three-dimensional object. Complicated operations.

(2) According to the method of hierarchy and dynamic division, the marker point data is pre-layered at the center, and the layers are gradually expanded. According to the spatial distance, the dynamic division is carried out in sequence, and the spatial structure is clarified, corresponding to the overall topological relationship. The dynamic layering is based on the actual splicing The law of motion is a reasonable data arrangement. Without dynamic layering processing, not only is it impossible to predict, but also for recognition, the data needs to be fully calculated. The calculation is too large, the efficiency is very low, and errors are prone to occur, even when the three-dimensional object is relatively large. case cannot be achieved.

(3) The matching method of point cloud marker points based on spatial data dynamic layering in the present invention, the method of comparative reasoning and the method based on view recognition search, according to the three-dimensional geometric topological relationship of the marker point set, the spatial distance relationship, through Optimizing effectively solves the problem of searching and matching recognition between feature mark point groups during point cloud splicing, without the need for multiple measurements or complex graphic logic operations, which improves the matching speed and accuracy.

(4) The use of the dynamic layered data structure can make recognition, matching, splicing, etc., including some special algorithms, possible, and has obvious computational efficiency. Unfolding, the spatial relationship is clear, the operation is convenient, the space can be estimated in advance, the calculation is optimized, the information between layers is recorded and modified in real time, the area and quantity dynamically grow according to the splicing of the physical objects, and it has a certain degree of intelligence.

(5) Pre-estimate the data area that conforms to the actual movement law before searching and identifying, adopt the method of area data matching, dynamically layer data processing, and add the processing result data to the corresponding data layer after matching, identification and alignment, and perform the next step of prediction Estimates, and at the same time dynamically correct the data layer, and continuously memorize and optimize it, reducing the calculation time.

(6) Using dynamic hierarchical processing and estimation processing, the amount of calculation is greatly reduced, and the spatial relationship is relatively clear. At the same time, the implementation method of the marker point data adopts a linear linked list, and at the same time, an array is used to store the necessary information, which has obvious computational efficiency.

Description of drawings

Figure 1 is a flow chart of reverse engineering.

Figure 2 is a composition diagram of the raster type three-dimensional scanning system.

Figure 3(a) is a point cloud model diagram of the car door in the first coordinate system.

Figure 3(b) is a point cloud model diagram of the car door in the second coordinate system.

Figure 3(c) is a point cloud model diagram of the car door in the third coordinate system.

Figure 3(d) is a point cloud model diagram of the car door in the fourth coordinate system.

Fig. 4 is a block diagram of a data structure linked list.

Figure 5 is a dynamic layered expansion diagram of data.

Fig. 6 is a flowchart of setting the current layer.

Fig. 7 is a flow chart of dynamic hierarchical splicing.

Figure 8 is a diagram of the overall point cloud model of the car door.

Detailed ways

A Marker Point Matching Method for Point Cloud Stitching in a 3D Scanning System

Step 1: Dynamically divide the spatial data set {M _i } (i=0, 1,...n) according to the spatial coordinates and distance values of the first point cloud marker point set at the beginning of successive scans to form a layer-by-layer embedding set, the division criterion is: set the center layer M ₀ , set the side length of its cube to L, take the center layer data as the reference coordinate system, and then dynamically add layers, the side length of the second layer cube is 3L, and the third layer The side length of the cube is 5L, and so on, the side length of the i-th cube is 2i+1, forming layer nesting;

The second step: a) set the first point cloud at the beginning of the successive scans as the benchmark, and point the current data layer _Ma to the data layer where the overlapping area of the first point cloud of the successive scans and the second point cloud of the successive scans is located, In the current data layer M _a and its adjacent inner and outer layers, it is enough to find the first point cloud of successive scans and the marker points of the second point cloud of successive scans to match. The marker point data of the second point cloud is added to the corresponding data layer of the first point cloud at the beginning of the successive scanning, and the data layer of the first point cloud at the beginning of the successive scanning increases dynamically accordingly, and the range expands. When the first point cloud of the successive scanning When the point cloud and the second point cloud of successive scans have no marker points in the current data layer M _a and its adjacent inner and outer layers, an automatic recursive search method is used to start from the outermost layer of the first point cloud of successive scans Search from outside to inside until you find a data area that matches the marker points of the second piece of point cloud scanned successively. Similarly, after the matching is successful, the marker point data layer of the first piece of point cloud that starts from scan successively is also dynamically increased. expanded range,

b) When looking for the first point cloud of successive scans to match the marker points of the third point cloud of successive scans, point the current data layer M _a to the first point cloud of successive scans and the point cloud of successive scans according to the above method. The data layer where the third point cloud overlap area is located, it is enough to find the first point cloud of successive scans in the current data layer _Ma and its adjacent inner and outer layers to match the marker points of the second point cloud of successive scans, After the matching and splicing is successful, the data of the third point cloud at the beginning of each scan is added to the corresponding data layer of the first point cloud at the beginning of each scan, and the data layer of the first point cloud at the beginning of each scan is dynamically increased accordingly. To expand, when the first point cloud of successive scans and the third point cloud of successive scans have no marker points in the current data layer M _a and its adjacent inner and outer layers, the method of automatic recursive search is adopted from the successive scans The outermost layer of the first point cloud starts to search from outside to inside until it finds the data area that matches the marked points of the third point cloud scanned successively. The point data layer is also dynamically increased, and the scope is expanded. When looking for the first point cloud of successive scans to match the marker points of the i-th point cloud of successive scans, and so on;

The matching method of the above marker points is:

Find all the triangles in the current data layer M _a of the first point cloud scanned successively, its adjacent inner and outer layers, and the spliced point cloud with any three marker points as vertices, and record the side lengths of these triangles , area, perimeter, in all the triangles of the current data layer M _a of the first point cloud scanned successively and its adjacent inner and outer layers, find the triangles of the spliced point cloud with the same side length, area, and perimeter The triangles, the vertices of these triangles are the matching marker points;

In this embodiment, during dynamic layering, the data in each layer does not include its internal cube data. When the overlapping area is in a certain data layer of the first point cloud scanned successively, point the current data layer _Ma to the data layer, and when the overlapping area is in the two-layer data area of the first point cloud scanned successively, according to the calculation The size of the space area occupied by the overlapping area in each layer determines the data layer with a relatively large area, and points the current data layer _Ma to this layer.

Below with reference to accompanying drawing, the present invention is described in detail:

Using multi-view tag positioning point cloud stitching technology to obtain accurate 3D data of feature marker points is the prerequisite for 3D point cloud stitching. Paste special mark points on the surface of the object, high-precision circles with black background and white surface, no reflection, the number of mark points should be three points or more, and the situation of multi-point collinearity should not appear. According to the shape of the three-dimensional object, paste more points in places with relatively high curvature to ensure that the feature point area fully expresses the three-dimensional topological characteristics of the object. Due to the characteristics of splicing, only overlapping areas can be effectively spliced, and the recognition alignment mainly depends on the marker point data in the overlapping areas. The scanning movement starts from scanning the first image, overlapping, shooting, splicing, and completing multiple point cloud splicing through two-phase splicing. It is a process that gradually expands from the local to the global. It is impossible to break away from the local and directly expand. Therefore, according to the characteristics of the movement, after obtaining the feature point data in the three-dimensional space, according to the consistency of the three-dimensional rigid body posture and geometric invariance, the set of feature marker points is set according to the spatial coordinates and distance values, from the inside to the outside, according to the largest possible area of a scan, Dynamically divide the spatial data set to form layer-by-layer nesting, and ensure correct marker point matching during splicing.

Figure 3 is the point cloud model of the car door in different coordinate systems. Since the measurement data of the car door cannot be obtained at one time, all the measurements are obtained through four measurements. The feature point data adopts a dynamic hierarchical data structure and stores and implements it with a linked list. . The implementation method of feature point data adopts linear linked list. At the same time, in order to realize the algorithm, several sets of linked list management are added: estimated linked list, layer linked list, etc., see Figure 4.

The present invention mainly relates to the following three aspects:

1) Dynamic layering of feature marker point data

Read in the two 3D point cloud data of the car door, and set the first image as the reference image, also known as the target image. The subsequent splicing operations are all under the same coordinate system of this picture, and the first set of point cloud marker points used for splicing is dynamically divided according to the spatial coordinates and distance values. The spatial data set {M _i } (i=0, 1,...n), forming layers of nesting. The division criteria are as follows: set the center layer M ₀ , set the side length of its cube to L, take the center layer data as the reference coordinate system, and then add layers dynamically, the side length of the cube on the second layer is 3L, and the cube on the third layer The side length is 5L, and so on, the side length of the cube in the i-th layer is 2i+1, forming layer nesting. When dynamic layering, the data in each layer does not include its internal cube data. See Figure 5.

2) Prediction and estimation of feature marker points and setting the current data layer

Set the first point cloud at the beginning of the successive scans as the benchmark, point the current data layer _Ma to the data layer where the first point cloud of the successive scans overlaps with the second point cloud of the successive scans, then when looking for the point cloud of the successive scans When the first point cloud matches the marker points of the second point cloud scanned successively, it is only necessary to search in the current data layer _Ma and its adjacent inner and outer layers to find the first point cloud scanned successively. The data layer M _a and its adjacent inner and outer layers neutralize all triangles formed with any three marker points in the second piece of point cloud scanned successively, and record the side lengths, areas, and perimeters of these triangles. The current data layer M _a of the first point cloud scanned successively finds the triangles with the same side length, area and perimeter among all the triangles of the adjacent inner and outer layers, and the vertices of these triangles In order to match the marker points, after the matching and splicing is successful, add the data of the second point cloud at the beginning of each scan to the corresponding data layer of the first point cloud at the beginning of each scan, and the marker points of the first point cloud at the beginning of each scan The data layer is dynamically increased accordingly, and the scope is expanded. The current data layer _Ma and its adjacent inner and outer layers are the estimated area. When there is no marker point matching in the area, the automatic recursive search method is used to search from the outermost layer of the first point cloud of the successive scans from the outside to the inner until the data area matching the marker points of the second point cloud of the successive scans is found , similarly, after the matching is successful, the first point cloud marker point data layer at the beginning of each scan is also dynamically increased, and the range is expanded. When the overlapping area is in a certain data layer of the first point cloud scanned successively, point the current data layer _Ma to the data layer, and when the overlapping area is in the two-layer data area of the first point cloud scanned successively, according to the calculation The size of the space area occupied by the overlapping area in each layer determines the data layer with a relatively large area, and points the current data layer _Ma to this layer. See Figure 6.

3) Mark point matching for point cloud stitching

After the processing of dynamic layering and estimation of landmark points, each pairwise matching can directly take the estimated data and the dataset of landmark points to be matched for landmark matching, and find the current data layer M of the first point cloud scanned successively. _a) All triangles in the adjacent inner and outer layers and in the spliced point cloud with any three marker points as vertices, and record the side length, area, and perimeter of these triangles, in the first frame of successive scans In all the triangles of the current data layer M _a of the point cloud and its adjacent inner and outer layers, find the triangles with the same side length, area and perimeter in the triangles of the point cloud spliced with it, and the vertices of these triangles are matching marker points, When there is no landmark match, turn to recursive search to perform landmark matching. After each match, dynamically adjust the current data layer of the marker points, and estimate the data again to prepare for the next match. The overall flow chart is shown in Figure 7, and finally the overall point cloud model of the car door is obtained, as shown in Figure 8.

Claims (3)

1. A marker point matching method for point cloud splicing in a three-dimensional scanning system, characterized in that: Step 1: Dynamically divide the spatial data set {M _i } (i=0, 1,...n) according to the spatial coordinates and distance values of the first point cloud marker point set at the beginning of successive scans to form a layer-by-layer embedding set, the division criterion is: set the center layer M ₀ , set the side length of its cube to L, take the center layer data as the reference coordinate system, and then dynamically add layers, the side length of the second layer cube is 3L, and the third layer The side length of the cube is 5L, and so on, the side length of the i-th cube is 2i+1, forming layer nesting; The second step: a) set the first point cloud at the beginning of the successive scans as the benchmark, and point the current data layer _Ma to the data layer where the overlapping area of the first point cloud of the successive scans and the second point cloud of the successive scans is located, In the current data layer M _a and its adjacent inner and outer layers, it is enough to find the first point cloud of successive scans and the marker points of the second point cloud of successive scans to match. The marker point data of the second point cloud is added to the corresponding data layer of the first point cloud at the beginning of the successive scanning, and the data layer of the first point cloud at the beginning of the successive scanning increases dynamically accordingly, and the range expands. When the first point cloud of the successive scanning When the point cloud and the second point cloud of successive scans have no marker points in the current data layer M _a and its adjacent inner and outer layers, an automatic recursive search method is used to start from the outermost layer of the first point cloud of successive scans Search from outside to inside until you find a data area that matches the marker points of the second piece of point cloud scanned successively. Similarly, after the matching is successful, the marker point data layer of the first piece of point cloud that starts from scan successively is also dynamically increased. expanded range, b) When looking for the first point cloud of successive scans to match the marker points of the third point cloud of successive scans, point the current data layer M _a to the first point cloud of successive scans and the point cloud of successive scans according to the above method. The data layer where the third point cloud overlap area is located, it is enough to find the first point cloud of successive scans in the current data layer _Ma and its adjacent inner and outer layers to match the marker points of the third point cloud of successive scans, After the matching and splicing is successful, the data of the third point cloud at the beginning of each scan is added to the corresponding data layer of the first point cloud at the beginning of each scan, and the data layer of the first point cloud at the beginning of each scan is dynamically increased accordingly. To expand, when the first point cloud of successive scans and the third point cloud of successive scans have no marker points in the current data layer M _a and its adjacent inner and outer layers, the method of automatic recursive search is adopted from the successive scans The outermost layer of the first point cloud starts to search from outside to inside until it finds the data area that matches the marked points of the third point cloud scanned successively. The point data layer is also dynamically increased, and the scope is expanded. When looking for the first point cloud of successive scans to match the marker points of the i-th point cloud of successive scans, and so on; The matching method of the above marker points is: Find all the triangles in the current data layer M _a of the first point cloud scanned successively, its adjacent inner and outer layers, and the spliced point cloud with any three marker points as vertices, and record the side lengths of these triangles , area, perimeter, in all the triangles of the current data layer M _a of the first point cloud scanned successively and its adjacent inner and outer layers, find the triangles of the spliced point cloud with the same side length, area, and perimeter The triangles, the vertices of these triangles are the matching marker points; 2. The marker point matching method for point cloud stitching in a 3D scanning system according to claim 1, wherein during dynamic layering, the data in each layer only includes the data between the current layer and its internal cubes. 3. The point cloud stitching method according to claim 1, characterized in that when the overlapping area is in a certain data layer of the first piece of point cloud scanned successively, the current data layer _Ma points to For this data layer, when the overlapping area is in the two-layer data area of the first point cloud scanned successively, according to the calculated overlapping area in the space area occupied by each layer, determine the data layer with a relatively large area, and convert the current data Layer _Ma points to this layer.

Images