CN110660053A - Plane detection method and device for point cloud data - Google Patents
Plane detection method and device for point cloud data Download PDFInfo
- Publication number
- CN110660053A CN110660053A CN201910899350.9A CN201910899350A CN110660053A CN 110660053 A CN110660053 A CN 110660053A CN 201910899350 A CN201910899350 A CN 201910899350A CN 110660053 A CN110660053 A CN 110660053A
- Authority
- CN
- China
- Prior art keywords
- point cloud
- node
- plane
- adjacent
- block
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T7/00—Image analysis
- G06T7/0002—Inspection of images, e.g. flaw detection
- G06T7/0004—Industrial image inspection
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T2207/00—Indexing scheme for image analysis or image enhancement
- G06T2207/10—Image acquisition modality
- G06T2207/10028—Range image; Depth image; 3D point clouds
Landscapes
- Engineering & Computer Science (AREA)
- Quality & Reliability (AREA)
- Computer Vision & Pattern Recognition (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Image Analysis (AREA)
Abstract
The invention provides a plane detection method and a plane detection device for point cloud data. And then, constructing a adjacency relation graph for the point cloud blocks capable of being fitted into a plane according to the adjacency relation of the point cloud blocks in the three-dimensional space. And for the point cloud block with the minimum fitting error in the adjacency relation graph, carrying out plane combination on the point cloud block and the adjacent point cloud block to finally obtain all point cloud blocks which belong to the same plane with the point cloud block. And repeating the process of plane combination, and detecting to obtain all planes in the point cloud data.
Description
Technical Field
The invention belongs to the technical field of point cloud data processing, and particularly relates to a plane detection method and device for point cloud data.
Background
Point cloud data refers to the measurement of the surface of an object using a scanning device (e.g., 2D/3D lidar, stereo camera, transit time camera, etc.) and is recorded in the form of points, each point containing three-dimensional coordinates, typically expressed in the form of x, y, z three-dimensional coordinates. The point cloud data may also include color information or reflection intensity information, etc.
The plane refers to a flat surface in actual scene data acquired by a scanning device, for example, a floor, a desktop, a wall surface, and the like in an indoor environment.
The traditional plane detection method comprises the steps of extracting random N points in point cloud data corresponding to a target object (or space), fitting a plane according to the N points, and if errors of the plane fitted by the N points are small enough, determining that the plane is detected; and if the error is large, randomly extracting N points again to perform the next plane fitting process. The plane detection method has the advantages of large calculated amount, high false detection rate, uncontrollable calculation time and great influence of random factors, and basically cannot meet the real-time detection requirement.
Disclosure of Invention
In view of the above, the present invention provides a method and an apparatus for detecting a plane of point cloud data to improve a detection speed and a detection accuracy, and the specific technical solution is as follows:
in a first aspect, the present invention provides a plane detection method for point cloud data, including:
dividing point cloud data of a target to obtain a plurality of point cloud blocks;
performing plane fitting on the point cloud data in the network aiming at each point cloud block to obtain a target point cloud block which can be fitted into a plane;
aiming at any target point cloud block, determining an adjacent network having an adjacent relation with the target point cloud block from all the target point cloud blocks to obtain an adjacent relation graph, wherein each node in the adjacent relation graph is a point cloud block;
and carrying out plane combination on the point cloud block and the adjacent point cloud blocks corresponding to the point cloud block each time aiming at the point cloud block with the minimum fitting error in the adjacent relation graph to obtain all point cloud blocks belonging to the same plane.
In a possible implementation manner, each time, for a point cloud block with the smallest fitting error in the adjacency relation graph, performing plane merging on the point cloud block and an adjacent point cloud block corresponding to the point cloud block to obtain all point cloud blocks belonging to the same plane, includes:
sequencing all the nodes in the adjacency relation graph according to the sequence of fitting errors corresponding to the nodes from small to large to obtain an ordered sequence;
for the node with the minimum fitting error in the ordered sequence, combining the node and an adjacent node which corresponds to the node and can be fitted into a plane into one node in the adjacent relation graph, updating the combined node into the ordered sequence, and repeatedly executing the step until the ordered sequence is empty;
and if the node block does not have an adjacent node which can be fit into a plane, determining that the point cloud data corresponding to the node belongs to the plane, and deleting the node from the ordered sequence.
In one possible implementation manner, for a node in the ordered sequence with the smallest fitting error, merging the node and an adjacent node that corresponds to the node and can be fitted to one plane into one node in the adjacent relationship graph, and updating the merged node into the ordered sequence includes:
for the node with the minimum fitting error in the ordered sequence, finding an adjacent node set corresponding to the node from the adjacent relation graph;
carrying out plane fitting on any adjacent node in the adjacent node set and the node, and combining the adjacent node with fitting error meeting the requirement and the node to obtain a combined node;
and inserting the merged node into the ordered sequence according to the fitting error corresponding to the merged node, and deleting two nodes before merging corresponding to the merged node from the ordered sequence.
In a possible implementation manner, performing plane fitting on any adjacent node in the adjacent node set and the node, and merging an adjacent node with a fitting error meeting a requirement and the node to obtain a merged node, includes:
traversing all adjacent nodes in the adjacent node set, and performing plane fitting on each adjacent node and the node;
and selecting an adjacent node which has the minimum fitting error and is smaller than the error threshold value and performs plane fitting with the node, and combining the adjacent node with the node to obtain a combined node.
In a possible implementation manner, the determining, for all target point clouds, an adjacency network having an adjacency relation with each target point cloud to obtain an adjacency relation graph includes:
for each target point cloud block, determining an adjacent point cloud block which has an adjacent relation with the target point cloud block in a three-dimensional space;
and taking each cloud block as a node, and communicating the nodes with the adjacent relation through edges to obtain the adjacent relation graph.
In a possible implementation manner, for all point cloud blocks in the adjacency relation graph, sorting the point cloud blocks according to a sequence of fitting errors corresponding to the point cloud blocks from small to large to obtain an ordered sequence, including:
and constructing a minimum pile of data according to the sequence of fitting errors corresponding to each point cloud block from small to large, wherein the pile top of the minimum pile of data is the point cloud block with the minimum fitting error.
In a second aspect, the present invention further provides a plane detection apparatus for point cloud data, including:
the dividing module is used for dividing the point cloud data of the target to obtain a plurality of point cloud blocks;
the plane fitting module is used for performing plane fitting on the point cloud data in the network aiming at each point cloud block to obtain a target point cloud block which can be fitted into a plane;
the adjacency relation graph building module is used for determining an adjacency network having adjacency relation with the target point cloud block from all the target point cloud blocks aiming at any target point cloud block to obtain an adjacency relation graph, wherein each node in the adjacency relation graph is a point cloud block;
and the plane merging module is used for performing plane merging on the point cloud block and the adjacent point cloud blocks corresponding to the point cloud block at each time aiming at the point cloud block with the minimum fitting error in the adjacent relation graph to obtain all the point cloud blocks belonging to the same plane.
In a possible implementation manner, the plane merging module is specifically configured to:
sequencing all the nodes in the adjacency relation graph according to the sequence of fitting errors corresponding to the nodes from small to large to obtain an ordered sequence;
for the node with the minimum fitting error in the ordered sequence, combining the node and an adjacent node which corresponds to the node and can be fitted into a plane into one node in the adjacent relation graph, updating the combined node into the ordered sequence, and repeatedly executing the step until the ordered sequence is empty;
and if the node block does not have an adjacent node which can be fit into a plane, determining that the point cloud data corresponding to the node belongs to the plane, and deleting the node from the ordered sequence.
In a third aspect, the present invention further provides an apparatus, including a memory and a processor, where the memory is used to store a program, and the processor executes the program stored in the memory to implement the plane detection method for point cloud data according to any one of the above possible implementation manners.
In a fourth aspect, the present invention further provides a storage medium, where computer-executable instructions are stored, and when the computer-executable instructions are loaded and executed by a processor, the method for detecting a plane of point cloud data according to any one of the above possible implementation manners is implemented.
According to the plane detection method of the point cloud data, after the point cloud data of the target are obtained, the point cloud data are divided into a plurality of different point cloud blocks, and plane fitting is firstly carried out on the point cloud data in each point cloud block. And then, constructing a adjacency relation graph for the point cloud blocks capable of being fitted into a plane according to the adjacency relation of the point cloud blocks in the three-dimensional space. And for the point cloud block with the minimum fitting error in the adjacency relation graph, carrying out plane combination on the point cloud block and the adjacent point cloud block to finally obtain all point cloud blocks which belong to the same plane with the point cloud block. And repeating the process of plane combination, and detecting to obtain all planes in the point cloud data. Firstly, when point cloud blocks are subjected to plane combination, selecting a plane with the minimum fitting error each time to combine with a plane of a cloud block adjacent to the point cloud block, wherein the smaller the fitting error is, the higher the flatness of the plane formed by local point clouds is, and the easier the plane is expanded to the periphery, the closer planes are found to be combined; moreover, the adjacency relation graph is constructed, so that plane merging is performed each time, point cloud blocks with adjacency relations are merged, and the probability that adjacent point cloud blocks belong to the same plane is higher. Therefore, the method can reduce the calculation amount of plane detection, improve the detection speed and improve the accuracy of the detection result.
Drawings
In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the drawings used in the description of the embodiments or the prior art will be briefly introduced below, and it is obvious that the drawings in the following description are some embodiments of the present invention, and for those skilled in the art, other drawings can be obtained according to these drawings without creative efforts.
FIG. 1 is a flow chart of a method for detecting a plane of point cloud data according to the present invention;
FIG. 2 is a schematic diagram of an adjacency under a two-dimensional structure provided by the present invention;
FIG. 3 is a flow chart of a plane merging process performed on point cloud blocks according to the present invention;
fig. 4 is a schematic structural diagram of a plane detection apparatus for point cloud data according to the present invention.
Detailed Description
In order to make the objects, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the drawings in the embodiments of the present invention, and it is obvious that the described embodiments are some, but not all, embodiments of the present invention. All other embodiments, which can be derived by a person skilled in the art from the embodiments given herein without making any creative effort, shall fall within the protection scope of the present invention.
Referring to fig. 1, a flowchart of a plane detection method for point cloud data according to the present invention is shown, where the method is applied to a computer device, and the computer device may be a server, or a PC, or a mobile terminal such as a mobile phone and a tablet computer.
As shown in fig. 1, the method comprises the steps of:
and S110, dividing the point cloud data of the target to obtain a plurality of point cloud blocks.
The method comprises the steps of acquiring point cloud data of a target acquired by scanning equipment, wherein the point cloud data are unordered and can be called unordered point cloud data, and then dividing the unordered point cloud data into different point cloud blocks according to a three-dimensional coordinate.
In one possible implementation, a point cloud block may be divided by a voxel method, and a point cloud space is divided into a plurality of voxel cubes with a side length n (i.e., point cloud blocks), for example, a certain point cloud data P has three-dimensional coordinates (x.p, y.p, z.p), and a point P is divided into voxel cubes with a label [ I, j, k ], where [ I, j, k ] ═ [ x.p/n, y.p/n, z.p/n ], that is, the coordinate of the point P is divided by the side length of the voxel cube to obtain the label corresponding to the voxel cube.
The point cloud block obtained by division may or may not contain at least one point, which is related to the point cloud data distribution of the target. The point cloud block not containing the point indicates that the space corresponding to the point cloud block does not contain any part of the target, so that only the point cloud block containing the point needs to be subjected to subsequent processing. That is, the point cloud blocks hereinafter each contain point cloud data.
And S120, performing plane fitting on the point cloud data in each point cloud block to obtain a target point cloud block capable of being fitted into a plane.
For each point cloud block, performing plane fitting on all points contained in the point cloud block to obtain a plane fitting equation and a fitting error of a fitting plane, and if the fitting error is greater than an error threshold value, determining that the points in the point cloud block do not belong to the same plane; and if the fitting error is smaller than the error threshold value, all the points in the point cloud block are considered to belong to the same plane.
In one possible implementation manner of the present invention, a process of fitting a plane is described by taking a least square method as an example:
for a point cloud set A contained in any point cloud block, assuming that the point cloud set A containsIncluding N points, the gravity center of the N points is calculated according to the formula 1
In formula 1, xi, yi, zi are three-dimensional coordinates of any one of the N points included in the point cloud block.
The fitted plane must pass through the center of gravity, and for each point the center of gravity is removed using equation 2:
using the points after the reconstruction, a least squares function is constructed as shown in equation 3:
and (4) solving the values of the coefficients a, b and c in the formula 3 according to a formula 4 to finally obtain a plane equation.
After the values of a, b and c are obtained, the MSE (mean square error) corresponding to the fitting plane is calculated by formula 3.
Then, setting an error threshold k, comparing the magnitude relation between MSE and k, and determining whether the point in the point cloud block can be fitted into a plane.
And S130, aiming at any target point cloud block, determining an adjacent network having an adjacent relation with the target point cloud block from all the target point cloud blocks to obtain an adjacent relation graph.
For all point cloud blocks with MSE smaller than or equal to an error threshold k, determining the point cloud block with each point cloud block having an adjacent relation, wherein each point cloud block should have 6 neighborhoods in a three-dimensional space, which are respectively as follows: up, down, left, right, front, back. And forming an adjacency graph of the cloud blocks of each point.
In one possible implementation, the adjacency graph is a graph data structure, each cloud block can be used as a node in the graph, and the nodes with the adjacency are communicated with each other by edges. Fig. 2 is a schematic diagram of an adjacent relation diagram under a two-dimensional structure.
And S140, performing plane combination on the point cloud block and the adjacent point cloud blocks corresponding to the point cloud block each time aiming at the point cloud block with the minimum fitting error in the adjacent relation graph to obtain all point cloud blocks belonging to the same plane.
Then, sorting all nodes in the adjacency relation graph from small to large according to RMSE (root mean square error) of each node, then, carrying out plane combination on the nodes with the minimum RMSE each time, namely, carrying out plane fitting on planes obtained by fitting two point cloud blocks again, and if the two planes can be fitted into one plane, combining the two point cloud blocks in the adjacency relation graph into one point cloud block; then, plane merging continues to be performed on the node with the minimum RMSE in the adjacency graph and the nodes with the adjacency until no nodes capable of being merged exist, and a plane is considered to be detected. And if no node capable of being merged exists in all adjacent nodes corresponding to the current node with the minimum RMSE, the current node with the minimum R MSE is regarded as a plane in the space.
The plane detection method for point cloud data provided by this embodiment includes, when point cloud blocks are subjected to plane combination, selecting a plane with the smallest fitting error each time to combine with a plane of a cloud block adjacent to the point cloud block, and first, the smaller the fitting error is, the higher the flatness of a plane formed by local point clouds is, and the easier the plane is expanded to the periphery, the closer planes are found to be combined; moreover, the adjacency relation graph is constructed, so that plane merging is performed each time, point cloud blocks with adjacency relations are merged, and the probability that adjacent point cloud blocks belong to the same plane is higher. Therefore, the method can reduce the calculation amount of plane detection, improve the detection speed and improve the accuracy of the detection result.
Referring to fig. 3, a flowchart of a plane merging process performed on a point cloud block according to the present invention is shown, and as shown in fig. 3, the plane merging process of the point cloud block includes the following steps:
and S210, constructing a minimum pile of data according to the sequence of the fitting errors of all the point cloud blocks in the adjacency relation graph from small to large.
Wherein the top of the minimum heap data is a point cloud block with the minimum fitting error; moreover, the minimal heap of data enables rapid insertion or deletion of data.
In other embodiments of the present invention, other ordered data structures that facilitate quick insertion, deletion, such as ordered arrays, etc., may be used in place of the minimal heap data structure.
And S220, aiming at the point cloud block at the top of the pile in the minimum pile data, merging the point cloud block and an adjacent point cloud block which corresponds to the point cloud block and can be fitted into a plane into one point cloud block, and updating the merged point cloud block into the minimum pile data.
And S230, if the point cloud block does not have an adjacent point cloud block which can be fitted into a plane, determining that the point cloud data in the point cloud block belongs to the plane, and deleting the point cloud block from the ordered sequence.
The top data of the minimum heap data, namely the point cloud block with the minimum fitting error (namely RMSE), and for the point cloud block, an adjacent node set B corresponding to the point cloud block a is obtained from the adjacent relation graph;
and then traversing the nodes in the set B, supposing that the nodes are traversed to an adjacent node B, and performing plane fitting by using the point cloud data in the point cloud data a and the point cloud data in the point cloud data B. If the error (namely MSE) of the fitting plane is larger than the error threshold, the nodes a and b are not considered to belong to the same plane; the merging process described above continues for the next node in set B. And if the MSE of the fitting plane is smaller than the error threshold, the nodes a and b belong to the same plane, at the moment, the nodes a and b in the adjacency relation graph are merged into a node c, and the node c inherits all non-repeated adjacent nodes in the nodes a and b. And simultaneously, c is inserted into the minimum heap data according to the size of the RMSE corresponding to the node c, and meanwhile, the data corresponding to the nodes a and b are deleted from the minimum heap data. And then, re-extracting the heap top data from the updated minimum heap data and traversing the adjacent nodes of the heap top data for plane merging until the minimum heap data has no nodes.
And if the MSE obtained by plane fitting of all adjacent nodes of the node a and the node a does not meet the requirement of the error threshold, the node a is considered as a plane detected in the space, and the heap top node is deleted from the minimum heap data. Then, the next process of extracting the heap top data and traversing the adjacent nodes thereof for plane merging is carried out until the minimum heap data has no nodes.
In another possible implementation manner, when merging a heap top node with its neighboring nodes, the neighboring node with the smallest fitting error (i.e., MSE) is preferentially merged with the heap top node, that is, the neighboring node set of the heap top node is traversed, fitting errors when each neighboring node performs plane fitting with the heap top node are calculated one by one, and the neighboring node with the smallest fitting error and which is smaller than an error threshold is selected to be merged with the heap top node. Since the smaller the fitting error is, the higher the flatness of the plane formed by the local point clouds is, the easier it is to find a similar plane for merging when the plane is expanded to the periphery, and therefore, the plane detection speed can be increased by the method.
The invention also provides an embodiment of a plane detection device of the point cloud data.
Referring to fig. 4, a schematic structural diagram of a plane detection apparatus for point cloud data according to the present invention is shown, where the apparatus may be applied to a computer device, and the computer device may be a server, or a PC, or a mobile terminal such as a mobile phone and a tablet computer.
As shown in fig. 4, the apparatus may include: a partitioning module 110, a plane fitting module 120, an adjacency graph construction module 130, and a plane merging module 140.
The dividing module 110 is configured to divide the point cloud data of the target to obtain a plurality of point cloud blocks.
And a plane fitting module 120, configured to perform plane fitting on the point cloud data in the network for each point cloud block, so as to obtain a target point cloud block that can be fitted into a plane.
An adjacency relation graph building module 130, configured to determine, for any one target point cloud block, an adjacency network having an adjacency relation with the target point cloud block from all the target point cloud blocks, and obtain an adjacency relation graph, where each node in the adjacency relation graph is a point cloud block.
In a possible implementation manner of the present invention, the adjacency relation graph building module 130 is specifically configured to:
for each target point cloud block, determining an adjacent point cloud block which has an adjacent relation with the target point cloud block in a three-dimensional space;
and taking each cloud block as a node, and communicating the nodes with the adjacent relation through edges to obtain the adjacent relation graph.
And the plane merging module 140 is configured to perform plane merging on the point cloud block and the adjacent point cloud block corresponding to the point cloud block each time for the point cloud block with the smallest fitting error in the adjacent relationship graph, so as to obtain all point cloud blocks belonging to the same plane.
In a possible implementation manner, the plane merging module 140 is specifically configured to:
sequencing all nodes in the adjacency relation graph according to the sequence of fitting errors corresponding to all the nodes from small to large to obtain a sequence;
in one embodiment of the invention, the ordered sequence may employ a minimum heap data structure whose heap top is the point cloud block with the least fitting error.
Aiming at the node with the minimum fitting error in the ordered sequence, combining the node and the adjacent node which corresponds to the node and can be fitted into a plane into a node in an adjacent relation graph, updating the combined node into the ordered sequence, and repeatedly executing the step until the ordered sequence is empty;
and if the node block does not have an adjacent node which can be fit into a plane, determining that the point cloud data corresponding to the node belongs to the plane, and deleting the node from the ordered sequence.
In one possible implementation, for a node with the smallest fitting error in the ordered sequence, merging the node and an adjacent node that corresponds to the node and can be fitted to a plane into one node in the adjacent relationship graph, and updating the merged node into the ordered sequence includes:
for the node with the minimum fitting error in the ordered sequence, finding an adjacent node set corresponding to the node from the adjacent relation graph;
carrying out plane fitting on any adjacent node in the adjacent node set and the node, and combining the adjacent node with fitting error meeting the requirement and the node to obtain a combined node;
and inserting the merged node into the ordered sequence according to the fitting error corresponding to the merged node, and deleting two nodes before merging corresponding to the merged node from the ordered sequence.
In a possible implementation manner, performing plane fitting on any adjacent node in the adjacent node set and the node, and merging the adjacent node whose fitting error meets the requirement and the node to obtain a merged node, includes:
traversing all adjacent nodes in the adjacent node set, and performing plane fitting on each adjacent node and the node;
and selecting an adjacent node which has the minimum fitting error and is smaller than the error threshold value and performs plane fitting with the node, and combining the adjacent node with the node to obtain a combined node.
The plane detection device for point cloud data provided by this embodiment selects a plane with the smallest fitting error each time to merge with a plane of a cloud block adjacent to the plane when performing plane merging on the point cloud blocks, and first, the smaller the fitting error is, the higher the flatness of the plane formed by local point clouds is, and the easier it is to find a similar plane to merge by expanding the plane to the periphery; moreover, the adjacency relation graph is constructed, so that plane merging is performed each time, point cloud blocks with adjacency relations are merged, and the probability that adjacent point cloud blocks belong to the same plane is higher. Therefore, the method can reduce the calculation amount of plane detection, improve the detection speed and improve the accuracy of the detection result.
In another aspect, the present invention further provides an apparatus, which includes a processor and a memory, where the memory stores a program, and the processor executes the program stored in the memory to implement the plane detection method for point cloud data provided in any one of the above embodiments.
The processor herein may be a CPU of the terminal, or an MCU integrated within the terminal, or a combination of the CPU and the MCU. The processor includes kernel, which calls corresponding program from memory, and the kernel may be set in one or more than one.
The memory may include volatile memory in a computer readable medium, Random Access Memory (RAM) and/or nonvolatile memory such as Read Only Memory (ROM) or flash memory (flash RAM), and the memory includes at least one memory chip.
The device herein may be a server, PC, PAD, mobile phone, etc.
In still another aspect, the present invention further provides a storage medium executable by a computing device, where the storage medium stores a program, and the program, when executed by the computing device, implements the plane detection method for point cloud data provided in any one of the above embodiments.
While, for purposes of simplicity of explanation, the foregoing method embodiments have been described as a series of acts or combination of acts, it will be appreciated by those skilled in the art that the present invention is not limited by the illustrated ordering of acts, as some steps may occur in other orders or concurrently with other steps in accordance with the invention. Further, those skilled in the art should also appreciate that the embodiments described in the specification are preferred embodiments and that the acts and modules referred to are not necessarily required by the invention.
It should be noted that, in the present specification, the embodiments are all described in a progressive manner, each embodiment focuses on differences from other embodiments, and the same and similar parts among the embodiments may be referred to each other. For the device-like embodiment, since it is basically similar to the method embodiment, the description is simple, and for the relevant points, reference may be made to the partial description of the method embodiment.
The steps in the method of the embodiments of the present application may be sequentially adjusted, combined, and deleted according to actual needs.
The device and the modules and sub-modules in the terminal in the embodiments of the present application can be combined, divided and deleted according to actual needs.
In the several embodiments provided in the present application, it should be understood that the disclosed terminal, apparatus and method may be implemented in other manners. For example, the above-described terminal embodiments are merely illustrative, and for example, the division of a module or a sub-module is only one logical division, and there may be other divisions when the terminal is actually implemented, for example, a plurality of sub-modules or modules may be combined or integrated into another module, or some features may be omitted or not executed. In addition, the shown or discussed mutual coupling or direct coupling or communication connection may be an indirect coupling or communication connection through some interfaces, devices or modules, and may be in an electrical, mechanical or other form.
The modules or sub-modules described as separate parts may or may not be physically separate, and parts that are modules or sub-modules may or may not be physical modules or sub-modules, may be located in one place, or may be distributed over a plurality of network modules or sub-modules. Some or all of the modules or sub-modules can be selected according to actual needs to achieve the purpose of the solution of the present embodiment.
In addition, each functional module or sub-module in the embodiments of the present application may be integrated into one processing module, or each module or sub-module may exist alone physically, or two or more modules or sub-modules may be integrated into one module. The integrated modules or sub-modules may be implemented in the form of hardware, or may be implemented in the form of software functional modules or sub-modules.
Finally, it should also be noted that, herein, relational terms such as first and second, and the like may be used solely to distinguish one entity or action from another entity or action without necessarily requiring or implying any actual such relationship or order between such entities or actions. Also, the terms "comprises," "comprising," or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. Without further limitation, an element defined by the phrase "comprising an … …" does not exclude the presence of other identical elements in a process, method, article, or apparatus that comprises the element.
The previous description of the disclosed embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without departing from the spirit or scope of the invention. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.
The foregoing is only a preferred embodiment of the present invention, and it should be noted that, for those skilled in the art, various modifications and decorations can be made without departing from the principle of the present invention, and these modifications and decorations should also be regarded as the protection scope of the present invention.
Claims (10)
1. A plane detection method of point cloud data is characterized by comprising the following steps:
dividing point cloud data of a target to obtain a plurality of point cloud blocks;
performing plane fitting on the point cloud data in the network aiming at each point cloud block to obtain a target point cloud block which can be fitted into a plane;
aiming at any target point cloud block, determining an adjacent network having an adjacent relation with the target point cloud block from all the target point cloud blocks to obtain an adjacent relation graph, wherein each node in the adjacent relation graph is a point cloud block;
and carrying out plane combination on the point cloud block and the adjacent point cloud blocks corresponding to the point cloud block each time aiming at the point cloud block with the minimum fitting error in the adjacent relation graph to obtain all point cloud blocks belonging to the same plane.
2. The method of claim 1, wherein performing plane merging on the point cloud block and an adjacent point cloud block corresponding to the point cloud block each time for a point cloud block with a smallest fitting error in the adjacency graph to obtain all point cloud blocks belonging to a same plane comprises:
sequencing all the nodes in the adjacency relation graph according to the sequence of fitting errors corresponding to the nodes from small to large to obtain an ordered sequence;
for the node with the minimum fitting error in the ordered sequence, combining the node and an adjacent node which corresponds to the node and can be fitted into a plane into one node in the adjacent relation graph, updating the combined node into the ordered sequence, and repeatedly executing the step until the ordered sequence is empty;
and if the node block does not have an adjacent node which can be fit into a plane, determining that the point cloud data corresponding to the node belongs to the plane, and deleting the node from the ordered sequence.
3. The method of claim 2, wherein for a node in the ordered sequence having the smallest fitting error, merging the node and an adjacent node corresponding to the node and capable of fitting into a plane into one node in the adjacency graph, and updating the merged node into the ordered sequence comprises:
for the node with the minimum fitting error in the ordered sequence, finding an adjacent node set corresponding to the node from the adjacent relation graph;
carrying out plane fitting on any adjacent node in the adjacent node set and the node, and combining the adjacent node with fitting error meeting the requirement and the node to obtain a combined node;
and inserting the merged node into the ordered sequence according to the fitting error corresponding to the merged node, and deleting two nodes before merging corresponding to the merged node from the ordered sequence.
4. The method of claim 3, wherein performing a plane fitting on any one neighboring node in the set of neighboring nodes and the node, and combining the neighboring node with a fitting error meeting a requirement and the node to obtain a combined node comprises:
traversing all adjacent nodes in the adjacent node set, and performing plane fitting on each adjacent node and the node;
and selecting an adjacent node which has the minimum fitting error and is smaller than the error threshold value and performs plane fitting with the node, and combining the adjacent node with the node to obtain a combined node.
5. The method of claim 1, wherein determining, for all target point clouds, an adjacency network having an adjacency relationship with each target point cloud, resulting in an adjacency graph, comprises:
for each target point cloud block, determining an adjacent point cloud block which has an adjacent relation with the target point cloud block in a three-dimensional space;
and taking each cloud block as a node, and communicating the nodes with the adjacent relation through edges to obtain the adjacent relation graph.
6. The method of claim 2, wherein the step of ordering all the point cloud blocks in the adjacency graph according to the fitting errors corresponding to the point cloud blocks from small to large to obtain an ordered sequence comprises:
and constructing a minimum pile of data according to the sequence of fitting errors corresponding to each point cloud block from small to large, wherein the pile top of the minimum pile of data is the point cloud block with the minimum fitting error.
7. A plane detection device for point cloud data, comprising:
the dividing module is used for dividing the point cloud data of the target to obtain a plurality of point cloud blocks;
the plane fitting module is used for performing plane fitting on the point cloud data in the network aiming at each point cloud block to obtain a target point cloud block which can be fitted into a plane;
the adjacency relation graph building module is used for determining an adjacency network having adjacency relation with the target point cloud block from all the target point cloud blocks aiming at any target point cloud block to obtain an adjacency relation graph, wherein each node in the adjacency relation graph is a point cloud block;
and the plane merging module is used for performing plane merging on the point cloud block and the adjacent point cloud blocks corresponding to the point cloud block at each time aiming at the point cloud block with the minimum fitting error in the adjacent relation graph to obtain all the point cloud blocks belonging to the same plane.
8. The apparatus of claim 7, wherein the plane merging module is specifically configured to:
sequencing all the nodes in the adjacency relation graph according to the sequence of fitting errors corresponding to the nodes from small to large to obtain an ordered sequence;
for the node with the minimum fitting error in the ordered sequence, combining the node and an adjacent node which corresponds to the node and can be fitted into a plane into one node in the adjacent relation graph, updating the combined node into the ordered sequence, and repeatedly executing the step until the ordered sequence is empty;
and if the node block does not have an adjacent node which can be fit into a plane, determining that the point cloud data corresponding to the node belongs to the plane, and deleting the node from the ordered sequence.
9. An apparatus comprising a memory for storing a program and a processor for executing the program stored in the memory to implement the plane detection method of point cloud data of any one of the above claims 1 to 6.
10. A storage medium having stored thereon computer-executable instructions which, when loaded and executed by a processor, carry out a method of plane detection of point cloud data as claimed in any one of claims 1 to 6.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910899350.9A CN110660053A (en) | 2019-09-23 | 2019-09-23 | Plane detection method and device for point cloud data |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910899350.9A CN110660053A (en) | 2019-09-23 | 2019-09-23 | Plane detection method and device for point cloud data |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN110660053A true CN110660053A (en) | 2020-01-07 |
Family
ID=69038866
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201910899350.9A Pending CN110660053A (en) | 2019-09-23 | 2019-09-23 | Plane detection method and device for point cloud data |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN110660053A (en) |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20150154467A1 (en) * | 2013-12-04 | 2015-06-04 | Mitsubishi Electric Research Laboratories, Inc. | Method for Extracting Planes from 3D Point Cloud Sensor Data |
| CN107341804A (en) * | 2016-04-29 | 2017-11-10 | 成都理想境界科技有限公司 | Determination method and device, image superimposing method and the equipment of cloud data midplane |
-
2019
- 2019-09-23 CN CN201910899350.9A patent/CN110660053A/en active Pending
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20150154467A1 (en) * | 2013-12-04 | 2015-06-04 | Mitsubishi Electric Research Laboratories, Inc. | Method for Extracting Planes from 3D Point Cloud Sensor Data |
| CN107341804A (en) * | 2016-04-29 | 2017-11-10 | 成都理想境界科技有限公司 | Determination method and device, image superimposing method and the equipment of cloud data midplane |
Non-Patent Citations (1)
| Title |
|---|
| CHEN FENG等: "Fast plane extraction in organized point clouds using agglomerative hierarchical clustering", 《2014 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS & AUTOMATION（ICRA）》 * |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US10510148B2 (en) | Systems and methods for block based edgel detection with false edge elimination | |
| CN109242855B (en) | Roof segmentation method, system and equipment based on multi-resolution 3D statistical information | |
| CN107657659A (en) | The Manhattan construction method for automatic modeling of scanning three-dimensional point cloud is fitted based on cuboid | |
| CN113837202B (en) | Feature point extraction method, image reconstruction method and device | |
| Han et al. | Development of a hashing-based data structure for the fast retrieval of 3D terrestrial laser scanned data | |
| CN105957068B (en) | Method and system for constructing a surface of a three-dimensional reconstructed model | |
| US11281935B2 (en) | 3D object detection from calibrated 2D images | |
| WO2021092771A1 (en) | Target detection method and apparatus, and device and storage medium | |
| CN114359204A (en) | Method, device and electronic device for detecting void in point cloud | |
| CN108564604B (en) | Binocular vision stereo matching method and device based on plane constraint and triangulation | |
| US11475629B2 (en) | Method for 3D reconstruction of an object | |
| CN117058022A (en) | Depth image denoising method and device, computer equipment and storage medium | |
| US20170140549A1 (en) | Method of perceiving 3d structure from a pair of images | |
| CN116266365A (en) | Point cloud data extraction method and device, electronic equipment and storage medium | |
| CN113487634A (en) | Method and device for correlating height and area of building | |
| CN114723883A (en) | Three-dimensional scene reconstruction method, device, equipment and storage medium | |
| CN112634366B (en) | Method for generating position information, related device and computer program product | |
| CN110660053A (en) | Plane detection method and device for point cloud data | |
| CN113838069A (en) | Point cloud segmentation method and system based on flatness constraint | |
| CN117455936B (en) | Point cloud data processing method and device and electronic equipment | |
| CN112002007A (en) | Model obtaining method and device based on air-ground image, equipment and storage medium | |
| US11360744B2 (en) | Two-dimensional data matching method, device and logic circuit | |
| CN118247321A (en) | Plane detection method, device, electronic device and storage medium in point cloud data | |
| CN111898654B (en) | Three-dimensional object feature acquisition method, device, computer equipment and storage medium | |
| Tushev et al. | Effective graph-based point matching algorithms |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| RJ01 | Rejection of invention patent application after publication | ||
| RJ01 | Rejection of invention patent application after publication |
Application publication date: 20200107 |