CN116385702A - Method and device for dividing bottom surface of three-dimensional point cloud, electronic equipment and storage medium - Google Patents
Method and device for dividing bottom surface of three-dimensional point cloud, electronic equipment and storage medium Download PDFInfo
- Publication number
- CN116385702A CN116385702A CN202211566698.4A CN202211566698A CN116385702A CN 116385702 A CN116385702 A CN 116385702A CN 202211566698 A CN202211566698 A CN 202211566698A CN 116385702 A CN116385702 A CN 116385702A
- Authority
- CN
- China
- Prior art keywords
- point cloud
- dimensional point
- grid
- target direction
- preset
- 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
- 238000000034 method Methods 0.000 title claims abstract description 54
- 238000001914 filtration Methods 0.000 claims abstract description 76
- 238000012545 processing Methods 0.000 claims abstract description 45
- 230000011218 segmentation Effects 0.000 claims abstract description 33
- 238000004891 communication Methods 0.000 claims description 14
- 238000004590 computer program Methods 0.000 claims description 8
- 238000000638 solvent extraction Methods 0.000 claims description 4
- 238000002372 labelling Methods 0.000 claims description 2
- 238000000605 extraction Methods 0.000 description 12
- 238000010586 diagram Methods 0.000 description 6
- 238000004364 calculation method Methods 0.000 description 2
- 230000002146 bilateral effect Effects 0.000 description 1
- 238000011161 development Methods 0.000 description 1
- 230000018109 developmental process Effects 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 238000010845 search algorithm Methods 0.000 description 1
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T19/00—Manipulating 3D models or images for computer graphics
- G06T19/20—Editing of 3D images, e.g. changing shapes or colours, aligning objects or positioning parts
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T7/00—Image analysis
- G06T7/10—Segmentation; Edge detection
-
- 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)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Architecture (AREA)
- Computer Graphics (AREA)
- Computer Hardware Design (AREA)
- General Engineering & Computer Science (AREA)
- Software Systems (AREA)
- Computer Vision & Pattern Recognition (AREA)
- Image Processing (AREA)
- Length Measuring Devices With Unspecified Measuring Means (AREA)
Abstract
The application relates to a bottom surface segmentation method and device of a three-dimensional point cloud, electronic equipment and a storage medium, wherein the method comprises the following steps: acquiring a three-dimensional point cloud corresponding to a target space; filtering the three-dimensional point cloud; performing grid division on the three-dimensional point cloud subjected to the filtering treatment to obtain a grid set; extracting all points meeting preset conditions in each grid according to the three-dimensional coordinates of the points in each grid in the grid set, and determining the bottom surface of the three-dimensional point cloud according to the extracted points; and dividing the bottom surface of the three-dimensional point cloud. Therefore, the three-dimensional point cloud after the filtering processing can be subjected to network division, and then the points meeting the preset conditions are extracted according to the three-dimensional coordinates of the points in each grid to serve as the bottom surface of the three-dimensional point cloud, so that even if the bottom surface of the three-dimensional point cloud is uneven, the bottom surface corresponding to each grid can be accurately extracted to serve as the bottom surface of the three-dimensional point cloud, and the accuracy of the three-dimensional point cloud bottom surface segmentation is improved.
Description
Technical Field
The application relates to the technical field of laser radars, in particular to a method and a device for dividing the bottom surface of a three-dimensional point cloud, electronic equipment and a storage medium.
Background
With the continuous development of laser radar technology, three-dimensional point clouds have been widely used in various fields, such as smart cities, autopilot, and the like. The bottom surface segmentation of the three-dimensional point cloud is an important ring in the three-dimensional point cloud data processing link, and the accuracy of the result has great influence on calculation accuracy of bounding box calculation, plane fitting and the like of the follow-up three-dimensional point cloud data.
However, the traditional bottom surface segmentation mode of the three-dimensional point cloud is to extract and segment by utilizing a coordinate range, namely, utilizing a distance judgment criterion of a Euclidean distance clustering method, for a point P in a space, finding k points closest to the point P by a KD-Tree neighbor search algorithm, clustering the points with the distances smaller than a set threshold value into a set Q, and ending the whole clustering process if the number of elements in the set Q is not increased; otherwise, other points than the p point are selected from the set Q, and the process is repeated until the number of elements in the set Q is not increased any more. Therefore, by adopting the traditional bottom surface segmentation mode of the three-dimensional point cloud, the accuracy of the segmentation result is lower, and especially when the bottom surface is uneven, incomplete or excessive extraction of the bottom surface can be caused, so that the deviation between the segmentation result and the actual result is larger.
Therefore, how to effectively divide the bottom surface of the three-dimensional point is a technical problem to be solved.
Disclosure of Invention
The application provides a bottom surface segmentation method, device, electronic equipment and storage medium of a three-dimensional point cloud, and aims to solve the problem that the accuracy of segmentation results is low in a traditional bottom surface segmentation mode of the three-dimensional point cloud.
In a first aspect, an embodiment of the present application provides a method for segmenting a bottom surface of a three-dimensional point cloud, where the method includes:
acquiring a three-dimensional point cloud corresponding to a target space;
filtering the three-dimensional point cloud;
performing grid division on the three-dimensional point cloud subjected to the filtering treatment to obtain a grid set;
extracting all points meeting preset conditions in each grid according to three-dimensional coordinates of the points in each grid in a preset coordinate system, and determining the bottom surface of the three-dimensional point cloud according to the extracted points, wherein the preset conditions are that the value range of the points in a target direction is larger than or equal to the minimum coordinate value in the target direction and smaller than or equal to the sum of the minimum coordinate value in the target direction and a preset bottom surface thickness threshold value, and the target direction is any direction in the directions of a plurality of coordinate axes of the preset coordinate system;
and dividing the bottom surface of the three-dimensional point cloud.
Optionally, the performing mesh division on the three-dimensional point cloud after the filtering processing to obtain a mesh set includes:
acquiring coordinate distribution ranges of the three-dimensional point cloud subjected to filtering treatment in two directions perpendicular to the target direction;
according to the coordinate distribution range in two directions perpendicular to the target direction and the grid granularity preset in the two directions perpendicular to the target direction, carrying out grid division on the three-dimensional point cloud after filtering processing to obtain a grid set of the three-dimensional point cloud in the target direction, wherein the target direction is any one direction of a plurality of directions of a preset coordinate system, and the grid granularity is used for representing the number of grids of the three-dimensional point cloud to be divided in the corresponding direction.
Optionally, the acquiring the coordinate distribution range of the three-dimensional point cloud after the filtering processing in two directions perpendicular to the target direction includes:
obtaining maximum coordinate values and minimum coordinate values of each point in the three-dimensional point cloud after filtering in two directions perpendicular to the target direction;
and determining coordinate distribution ranges in two directions perpendicular to the target direction according to the obtained maximum coordinate value and the obtained minimum coordinate value.
Optionally, the mesh dividing of the three-dimensional point cloud after the filtering processing is performed according to a coordinate distribution range in two directions perpendicular to the target direction and a mesh granularity preset in two directions perpendicular to the target direction, so as to obtain a mesh set of the three-dimensional point cloud in the target direction, which includes:
acquiring grid granularity preset in two directions perpendicular to the target direction;
and carrying out grid division on the three-dimensional point cloud subjected to the filtering treatment according to a preset grid division rule to obtain a grid set of the three-dimensional point cloud in the target direction, wherein the preset grid division rule is to equally divide coordinate distribution ranges in two directions perpendicular to the target direction according to grid granularity respectively corresponding to the coordinate distribution ranges.
Optionally, extracting all points meeting a preset condition in each grid according to the three-dimensional coordinates of the points in each grid in the grid set, and determining the bottom surface of the three-dimensional point cloud according to the extracted points, including:
determining the minimum coordinate value of the points in each grid in the grid set in the target direction according to the three-dimensional coordinates of the points in each grid in the grid set in a preset coordinate system;
extracting all points meeting the preset conditions in each grid respectively, and taking all extracted points as the bottom surfaces corresponding to each grid;
and combining the bottom surfaces corresponding to the grids to obtain the bottom surface of the three-dimensional point cloud.
Optionally, the filtering the three-dimensional point cloud includes:
obtaining a marking result of each point in the three-dimensional point cloud by adopting a minimum radius method;
and carrying out filtering processing on the three-dimensional point cloud according to the marking result.
Optionally, the formula for obtaining the labeling result is as follows:
wherein Num (R) represents the number of points in a spherical region with a target point as a center and R as a radius, N std And for a preset threshold value, the flag represents a mark result of the target point, wherein the target point is any point in the three-dimensional point cloud.
In a second aspect, an embodiment of the present application further provides a device for dividing a bottom surface of a three-dimensional point cloud, where the device includes:
the acquisition module is used for acquiring the three-dimensional point cloud corresponding to the target space;
the filtering processing module is used for carrying out filtering processing on the three-dimensional point cloud;
the grid dividing module is used for dividing the three-dimensional point cloud after the filtering processing into grids to obtain a grid set;
the determining module is used for extracting all points meeting preset conditions in each grid according to the three-dimensional coordinates of the points in each grid in a preset coordinate system, and determining the bottom surface of the three-dimensional point cloud according to the extracted points, wherein the preset conditions are that the value range of the points in a target direction is larger than or equal to the minimum coordinate value in the target direction and smaller than or equal to the sum of the minimum coordinate value in the target direction and a preset bottom surface thickness threshold value, and the target direction is any direction in the directions of a plurality of coordinate axes of the preset coordinate system;
and the segmentation module is used for segmenting the bottom surface of the three-dimensional point cloud.
In a third aspect, an embodiment of the present application further provides an electronic device, including a processor, a communication interface, a memory, and a communication bus, where the processor, the communication interface, and the memory complete communication with each other through the communication bus;
a memory for storing a computer program;
and the processor is used for realizing the steps of the bottom surface segmentation method of the three-dimensional point cloud according to any one of the embodiments of the first aspect when executing the program stored in the memory.
In a fourth aspect, embodiments of the present application further provide a computer readable storage medium, on which a computer program is stored, the computer program implementing the steps of the method for bottom surface segmentation of a three-dimensional point cloud according to any of the embodiments of the first aspect when being executed by a processor.
In the embodiment of the application, the three-dimensional point cloud corresponding to the target space is obtained; filtering the three-dimensional point cloud; performing grid division on the three-dimensional point cloud subjected to the filtering treatment to obtain a grid set; extracting all points meeting preset conditions in each grid according to three-dimensional coordinates of the points in each grid in a preset coordinate system, and determining the bottom surface of the three-dimensional point cloud according to the extracted points, wherein the preset conditions are that the value range of the points in a target direction is larger than or equal to the minimum coordinate value in the target direction and smaller than or equal to the sum of the minimum coordinate value in the target direction and a preset bottom surface thickness threshold value, and the target direction is any direction in the directions of a plurality of coordinate axes of the preset coordinate system; and dividing the bottom surface of the three-dimensional point cloud. By the method, the points meeting the preset conditions in each grid in the grid set can be extracted by taking the grids as units, that is, all points, in each grid, of which the coordinate value in the target direction is greater than or equal to the bottom surface thickness threshold value than the minimum coordinate value in the target direction can be extracted, so that the bottom surfaces corresponding to the grids can be accurately obtained, and the bottom surfaces of the three-dimensional point clouds can be determined. Therefore, even when the bottom surface of the three-dimensional point cloud is uneven, the bottom surfaces of different positions can be accurately extracted based on the minimum coordinate values and the bottom surface thickness threshold values in the target directions corresponding to the grids of the different positions, incomplete extraction or excessive extraction of the bottom surfaces of the three-dimensional point cloud are avoided, and therefore accuracy of three-dimensional point cloud bottom surface segmentation is improved.
Drawings
The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate embodiments consistent with the invention and together with the description, serve to explain the principles of the invention.
In order to more clearly illustrate the embodiments of the invention or the technical solutions of the prior art, the drawings which are used in the description of the embodiments or the prior art will be briefly described, and it will be obvious to a person skilled in the art that other drawings can be obtained from these drawings without inventive effort.
Fig. 1 is a flow chart of a bottom surface segmentation method of a three-dimensional point cloud according to an embodiment of the present application;
fig. 2 is a schematic view of laser radar scanning according to an embodiment of the present application;
fig. 3 is a detailed flowchart of a step of performing mesh division on a three-dimensional point cloud after filtering processing to obtain a mesh set according to an embodiment of the present application;
fig. 4 is a schematic diagram of a grid set Gx divided in the X direction according to an embodiment of the present application;
fig. 5 is a schematic diagram of a grid set Gy divided in the Y direction according to an embodiment of the present application;
FIG. 6 is a schematic diagram of a grid set Gz divided in the Z direction according to an embodiment of the present application;
fig. 7 is a detailed flowchart of a step of extracting all points satisfying a preset condition in each grid according to three-dimensional coordinates of points in each grid in the grid set and determining a bottom surface of a three-dimensional point cloud according to the extracted points provided in the embodiment of the present application;
fig. 8 is a schematic structural diagram of a bottom surface segmentation apparatus for a three-dimensional point cloud according to an embodiment of the present application;
fig. 9 is a schematic structural diagram of an electronic device according to an embodiment of the present application.
Detailed Description
For the purposes of making the objects, technical solutions and advantages of the embodiments of the present application more clear, the technical solutions of the embodiments of the present application will be clearly and completely described below with reference to the drawings in the embodiments of the present application, and it is apparent that the described embodiments are some embodiments of the present application, but not all embodiments. All other embodiments, which can be made by one of ordinary skill in the art without undue burden from the present disclosure, are within the scope of the present application based on the embodiments herein.
Example 1
Referring to fig. 1, fig. 1 is a flow chart of a bottom surface segmentation method of a three-dimensional point cloud according to an embodiment of the present application. As shown in fig. 1, the bottom surface segmentation method of the three-dimensional point cloud specifically includes the following steps:
and 101, acquiring a three-dimensional point cloud corresponding to the target space.
Specifically, the target space may be any three-dimensional space, and the embodiment of the present application is not specifically limited.
The method for acquiring the three-dimensional point cloud corresponding to the target space can be realized by a laser radar. As shown in fig. 2, a three-dimensional point cloud can be obtained by scanning a building and the ground in a certain area through a laser radar, and because the two buildings are respectively positioned on the low ground and the high ground, when the two buildings are segmented, the point cloud corresponding to the ground needs to be extracted and segmented, and when the two buildings are segmented, the point clouds of the two buildings are segmented, so that the accuracy of three-dimensional point cloud segmentation is improved.
And 102, performing filtering processing on the three-dimensional point cloud.
In the step, the three-dimensional point cloud can be subjected to filtering treatment by adopting methods such as direct filtering, statistical filtering, radius filtering, improved bilateral filtering, voxel grid filtering and the like, so that outliers in the three-dimensional point cloud are filtered, and effective points are reserved, so that the accuracy of data processing is improved.
And 103, performing grid division on the three-dimensional point cloud subjected to the filtering treatment to obtain a grid set.
In the step, the three-dimensional point cloud after filtering treatment can be divided according to one or more directions according to actual needs, one or more grid sets formed by a plurality of grids are obtained, and the subsequent extraction of the bottom surface based on each grid in each grid set is facilitated, so that the bottom surface of the whole three-dimensional point cloud is obtained. For example, in the target space shown in fig. 2, the ground is a bottom surface to be acquired, and since the ground has a high ground and a low ground, which are not on a horizontal plane, when the point cloud corresponding to the ground shown in fig. 2 is extracted and divided, the plane on which the ground is located needs to be grid-divided, so as to obtain a plurality of rectangular grids, and then the subsequent processing operation is performed. Of course, when the target space is other three-dimensional space, such as a room or a vehicle, the three-dimensional point cloud of the target space may have multiple floors, and then the three-dimensional point cloud of the target space needs to be meshed according to multiple directions to achieve extraction and segmentation of the multiple floors.
And 104, extracting all points meeting preset conditions in each grid according to the three-dimensional coordinates of the points in each grid in the preset coordinate system, and determining the bottom surface of the three-dimensional point cloud according to the extracted points, wherein the preset conditions are that the value range of the points in the target direction is larger than or equal to the minimum coordinate value in the target direction and smaller than or equal to the sum of the minimum coordinate value in the target direction and the preset bottom surface thickness threshold value, and the target direction is any direction in the directions of a plurality of coordinate axes of the preset coordinate system.
Specifically, the preset condition refers to a condition set according to a minimum coordinate value in a certain direction in a preset coordinate system and a preset bottom surface thickness threshold value, and if a point in a certain grid meets the preset condition, the point is indicated to be a point in the bottom surface; if a point in a grid does not meet the preset condition, it indicates that the point is not available as a point in the bottom surface. In this way, all the points meeting the preset conditions in each grid can be extracted according to the three-dimensional coordinates of the points in each grid in the grid set, and the bottom surface of the three-dimensional point cloud is determined according to the extracted points.
And 105, dividing the bottom surface of the three-dimensional point cloud.
After determining the bottom surface of the three-dimensional point cloud, the bottom surface of the three-dimensional point cloud may be segmented for use in a subsequent data processing flow.
In this embodiment, the points satisfying the preset condition in each grid in the grid set may be extracted by using the grid as a unit, that is, all points in each grid whose coordinate value in the target direction is greater than or equal to the bottom thickness threshold than the minimum coordinate value in the target direction may be extracted, so as to accurately obtain the bottom corresponding to each grid, thereby determining the bottom of the three-dimensional point cloud. Therefore, even when the bottom surface of the three-dimensional point cloud is uneven, the bottom surfaces of different positions can be accurately extracted based on the minimum coordinate values and the bottom surface thickness threshold values in the target directions corresponding to the grids of the different positions, incomplete extraction or excessive extraction of the bottom surfaces of the three-dimensional point cloud are avoided, and therefore accuracy of three-dimensional point cloud bottom surface segmentation is improved.
Example two
In an embodiment, the three-dimensional point cloud after the filtering processing can be subjected to grid division to obtain a grid set, so that the bottom surfaces of the grids can be conveniently extracted to obtain the bottom surfaces of the three-dimensional point cloud. Specifically, referring to fig. 3, fig. 3 is a detailed flowchart of a step of performing mesh division on a three-dimensional point cloud after filtering processing to obtain a mesh set according to an embodiment of the present application. As shown in fig. 3, in step 103, mesh division is performed on the three-dimensional point cloud after the filtering process to obtain a mesh set, which may specifically include:
In this step, when the three-dimensional point cloud needs to be divided according to the target direction, first, a coordinate distribution range of the three-dimensional point cloud after the filtering processing in two directions perpendicular to the target direction, that is, a minimum distribution point and a maximum distribution point of the three-dimensional point cloud in two directions perpendicular to the target direction needs to be obtained. Specifically, the step 301 of obtaining the coordinate distribution range of the three-dimensional point cloud after the filtering process in two directions perpendicular to the target direction may include:
obtaining maximum coordinate values and minimum coordinate values of each point in the three-dimensional point cloud after filtering in two directions perpendicular to the target direction;
and determining coordinate distribution ranges in two directions perpendicular to the target direction according to the obtained maximum coordinate value and the obtained minimum coordinate value.
In this way, according to the three-dimensional coordinates of each point in the three-dimensional point cloud after the filtering processing, sorting is performed according to X, Y, Z three different directions in a preset coordinate system, and the maximum coordinate value and the minimum coordinate value in each direction are determined, so that the maximum coordinate value in the X direction is obtained and is recorded as Xmax; the minimum coordinate value in the X direction is recorded as Xmin; the maximum coordinate value in the Y direction is denoted as Ymax; the minimum coordinate value in the Y direction is denoted as Ymin; the maximum coordinate value in the Z direction is denoted as Zmax; the minimum coordinate value in the Z direction is denoted as Zmin. Therefore, when the coordinate distribution ranges of the three-dimensional point cloud after the filtering processing in the two directions perpendicular to the target direction are acquired, the maximum coordinate value and the minimum coordinate value of each point in the three-dimensional point cloud after the filtering processing in the two directions perpendicular to the target direction can be acquired first, and then the coordinate distribution ranges in the two directions perpendicular to the target direction can be determined according to the acquired maximum coordinate value and minimum coordinate value. Thus, the three-dimensional point cloud after the filtering processing can be accurately subjected to grid division according to the target direction, so that the accuracy of grid division is improved.
It should be noted that the grid granularity in different directions may be the same or different, and may be specifically set according to actual needs, which is not specifically limited in the embodiments of the present application. The larger the grid granularity is, the more the number of grids to be divided is, and the higher the bottom surface extraction precision is; the smaller the grid granularity, the smaller the number of grids to be divided, and the lower the accuracy of bottom surface extraction.
Specifically, in the step 302, according to the coordinate distribution range in two directions perpendicular to the target direction and the grid granularity preset in two directions perpendicular to the target direction, the three-dimensional point cloud after the filtering process is grid-divided to obtain a grid set of the three-dimensional point cloud in the target direction, which includes:
acquiring grid granularity preset in two directions perpendicular to the target direction;
and carrying out grid division on the three-dimensional point cloud subjected to the filtering treatment according to a preset grid division rule to obtain a grid set of the three-dimensional point cloud in the target direction, wherein the preset grid division rule is to equally divide coordinate distribution ranges in two directions perpendicular to the target direction according to grid granularity respectively corresponding to the coordinate distribution ranges.
In this way, the grid granularity preset in two directions perpendicular to the target direction can be obtained first, then the coordinate distribution ranges in the two directions perpendicular to the target direction are divided equally according to the grid granularity corresponding to each coordinate distribution range, and therefore the three-dimensional point cloud after filtering processing is subjected to grid division, and the grid set of the three-dimensional point cloud in the target direction is obtained. For example, assuming that the X direction in the preset coordinate system is taken as the target direction, the coordinate distribution ranges in the two directions Y, Z perpendicular to the X direction are (Ymax-Ymin) and (Zmax-Zmin), respectively, and the mesh granularity in the two directions Y, Z is M1, the mesh set Gx with the total number M1X M1 in the X direction is obtained by dividing the mesh with the width (Ymax-Ymin)/M1 and the height (Zmax-Zmin)/M1 according to the mesh length (Xmax-Xmin) of each.
Assuming that the Y direction in the preset coordinate system is taken as the target direction, the coordinate distribution ranges in the two directions X, Z perpendicular to the Y direction are (Xmax-Xmin) and (Zmax-Zmin) respectively, and the mesh granularity in the two directions X, Z is M2, the mesh can be divided according to the length of each mesh being (Xmax-Xmin)/M2, the width being (Ymax-Ymin) and the height being (Zmax-Zmin)/M2, so as to obtain a mesh set Gy with the total number of M2 x M2 in the Y direction, as shown in fig. 5.
Assuming that the Z direction in the preset coordinate system is taken as the target direction, the coordinate distribution ranges in the two directions X, Y perpendicular to the Z direction are (Xmax-Xmin) and (Ymax-Ymin) respectively, and the mesh granularity in the two directions X, Y is M3, the mesh can be divided according to the length of each mesh being (Xmax-Xmin)/M3, the width being (Ymax-Ymin)/M3, and the height being (Zmax-Zmin), so as to obtain a mesh set Gz with the total number of M3 x M3 in the Z direction, as shown in fig. 6.
Here, M1, M2, and M3 are mesh granularity in three directions of X, Y and Z, respectively, and the smaller the value, the lower the accuracy, and the larger the value, the higher the accuracy. As an alternative embodiment, M1, M2 and M3 are generally in the range of 10 to 20.
In the implementation, the grid granularity can be flexibly set according to actual conditions so as to divide the grids into different numbers; and grid division can be performed on a plurality of different directions of the three-dimensional point cloud to obtain a grid set in the plurality of different directions, so that extraction and segmentation are conveniently performed on the bottom surfaces of the three-dimensional point cloud in the plurality of different directions.
Example III
In an embodiment, according to the three-dimensional coordinates of the points in each grid in the grid set, all the points meeting the preset conditions in each grid can be extracted, and the bottom surface of the three-dimensional point cloud is determined according to the extracted points, so that the follow-up segmentation of the bottom surface of the three-dimensional point cloud is facilitated. Specifically, referring to fig. 7, fig. 7 is a detailed flowchart of the steps of extracting all the points satisfying the preset condition in each grid according to the three-dimensional coordinates of the points in each grid in the grid set, and determining the bottom surface of the three-dimensional point cloud according to the extracted points provided in the embodiment of the present application. As shown in fig. 7, the step 104 of extracting all the points meeting the preset condition in each grid according to the three-dimensional coordinates of the points in each grid in the grid set, and determining the bottom surface of the three-dimensional point cloud according to the extracted points may specifically include:
and 701, determining the minimum coordinate value of the point in each grid in the grid set in the target direction according to the three-dimensional coordinates of the point in each grid in the grid set in the preset coordinate system.
And step 703, merging the bottom surfaces corresponding to the grids to obtain the bottom surface of the three-dimensional point cloud.
In an embodiment, the minimum coordinate values of the points in each grid in the grid set in the target direction can be obtained first, then all the points meeting the preset conditions in each grid are extracted according to the minimum coordinate values to serve as the bottom surfaces corresponding to each grid, and finally the bottom surfaces corresponding to each grid are combined, so that the bottom surfaces of the three-dimensional point cloud are obtained.
For example, for the grid set G shown in FIG. 4 x A certain grid G of (1) x (i, j) the minimum coordinate value G in the X direction of all points in the grid can be obtained x (i,j) min Then the grid is internally provided with[G x (i,j) min ，G x (i,j) min +C x ]Points within the range are extracted as the bottom surface of the grid. Sequentially extracting the grid set G according to the rule x And then combining the bottom surfaces of the grids to obtain the bottom surface Bx after the X-direction segmentation.
For the grid set G shown in FIG. 5 y A certain grid G of (1) y (i, j) the minimum coordinate value G in the Y direction of all points in the grid can be obtained y (i,j) min Then the grid is internally provided with [ G ] in the Y direction y (i,j) min ，G y (i,j) min +C y ]Points within the range are extracted as the bottom surface of the grid. Sequentially extracting the grid set G according to the rule y The bottom surface of each grid is then combined to obtain a bottom surface B after being divided in the Y direction y 。
For grid set G shown in FIG. 6 z A certain grid G of (1) z (i, j) the minimum coordinate value G in the Z direction of all points in the grid can be obtained z (i,j) min Then the grid is built up to [ G ] in the Z direction z (i,j) min ，G z (i,j) min +C z ]Points within the range are extracted as the bottom surface of the grid. Sequentially extracting the grid set G according to the rule z The bottom surface of each grid is then combined to obtain a bottom surface B after Z-direction segmentation z 。
Here, i and j represent the number of rows and columns, respectively, of the grid set grid, C x 、C y And C z The bottom thickness thresholds in the three directions X, Y and Z are shown, respectively. As an alternative embodiment, C x 、C y And C z The value can be 0.5-2 meters.
In this embodiment, the points satisfying the preset conditions in each grid can be extracted by taking the grid as a unit, so that the bottom surface corresponding to each grid is accurately obtained, and the bottom surface corresponding to each grid is used as the bottom surface of the three-dimensional point cloud.
Example IV
In one embodiment, the three-dimensional point cloud may be filtered prior to meshing the three-dimensional point cloud. Specifically, the filtering processing of the three-dimensional point cloud in the step 102 may specifically include:
obtaining a marking result of each point in the three-dimensional point cloud by adopting a minimum radius method;
and carrying out filtering processing on the three-dimensional point cloud according to the marking result.
In this way, after the three-dimensional point cloud corresponding to the target space is obtained, the three-dimensional point cloud corresponding to the target space can be subjected to filtering processing. Specifically, a minimum radius method is adopted to obtain a marking result of each point in the three-dimensional point cloud, and then filtering processing is carried out on the three-dimensional point cloud according to the marking result to remove outliers in the three-dimensional point cloud.
Specifically, the minimum radius method can be expressed by the following formula:
wherein Num (R) represents the number of points in a spherical region with the target point as the center and R as the radius, N std For a preset threshold, the flag represents a marking result of a target point, and the target point is any point in the three-dimensional point cloud.
Thus, the number of points in the spherical region with the radius of R can be calculated according to the formula, the marking result of any point in the three-dimensional point cloud is further determined, if the calculated marking result is 1, the point is reserved, and if the calculated marking result is 0, the point is discarded, so that the purpose of filtering outliers is achieved.
When the grid is divided, the grid division precision is not high because the grid is divided according to the maximum coordinate value and the minimum coordinate value in two directions which are mutually perpendicular to the target direction, and if outliers are not filtered; meanwhile, when the bottom surface of each grid is extracted, as the minimum coordinate value of the points in each grid in the target direction is required to be extracted, if outlier points are not filtered, the problem of incomplete bottom surface extraction is caused, and therefore, the three-dimensional point cloud is required to be subjected to filtering processing, the precision of the grid dividing link and the bottom surface extracting link of the three-dimensional point cloud is ensured, and the accuracy of the bottom surface dividing of the three-dimensional point cloud is improved.
Example five
Referring to fig. 8, fig. 8 is a schematic structural diagram of a bottom surface segmentation apparatus for a three-dimensional point cloud according to an embodiment of the present application. The bottom surface segmentation apparatus 800 of the three-dimensional point cloud may include:
an obtaining module 801, configured to obtain a three-dimensional point cloud corresponding to a target space;
the filtering processing module 802 is configured to perform filtering processing on the three-dimensional point cloud;
the grid dividing module 803 is configured to divide the three-dimensional point cloud after the filtering process into grids to obtain a grid set;
a determining module 804, configured to extract all points meeting a preset condition in each grid according to three-dimensional coordinates of points in each grid in a preset coordinate system in the grid set, and determine a bottom surface of the three-dimensional point cloud according to the extracted points, where the preset condition is that a value range of the points in a target direction is greater than or equal to a minimum coordinate value in the target direction and less than or equal to a sum of the minimum coordinate value in the target direction and a preset bottom surface thickness threshold, and the target direction is any direction in a direction of multiple coordinate axes of the preset coordinate system;
the segmentation module 805 is configured to segment a bottom surface of the three-dimensional point cloud.
Further, the meshing module 803 includes:
the first acquisition submodule is used for acquiring coordinate distribution ranges of the three-dimensional point cloud subjected to filtering processing in two directions perpendicular to the target direction;
the grid dividing sub-module is used for dividing the three-dimensional point cloud after the filtering processing into grids according to the coordinate distribution range in two directions perpendicular to the target direction and the grid granularity preset in the two directions perpendicular to the target direction to obtain a grid set of the three-dimensional point cloud in the target direction, wherein the target direction is any one direction of a plurality of directions of a preset coordinate system, and the grid granularity is used for representing the grid quantity of the three-dimensional point cloud to be divided in the corresponding direction.
Further, the first acquisition submodule includes:
the first acquisition unit is used for acquiring the maximum coordinate value and the minimum coordinate value of each point in the three-dimensional point cloud after the filtering processing in two directions perpendicular to the target direction;
and the determining unit is used for determining the coordinate distribution range in two directions perpendicular to the target direction according to the acquired maximum coordinate value and minimum coordinate value.
Further, the grid dividing sub-module includes:
a second acquisition unit configured to acquire grid granularity preset in two directions perpendicular to the target direction;
the grid dividing unit is used for carrying out grid division on the three-dimensional point cloud after the filtering processing according to a preset grid dividing rule to obtain a grid set of the three-dimensional point cloud in the target direction, wherein the preset grid dividing rule is used for equally dividing coordinate distribution ranges in two directions perpendicular to the target direction according to grid granularity respectively corresponding to the coordinate distribution ranges.
Further, the determining module 804 includes:
the determining submodule is used for determining the minimum coordinate value of the point in each grid in the grid set in the target direction according to the three-dimensional coordinate of the point in each grid in the grid set in the preset coordinate system;
the extraction submodule is used for respectively extracting all points meeting preset conditions in each grid, and taking all extracted points as the bottom surfaces corresponding to each grid;
and the merging sub-module is used for merging the bottom surfaces corresponding to the grids to obtain the bottom surface of the three-dimensional point cloud.
Further, the filtering processing module 802 includes:
the second acquisition submodule is used for acquiring marking results of each point in the three-dimensional point cloud by adopting a minimum radius method;
and the filtering processing sub-module is used for carrying out filtering processing on the three-dimensional point cloud according to the marking result.
Further, the formula for obtaining the marking result is as follows:
wherein Num (R) represents the number of points in a spherical region with the target point as the center and R as the radius, N std For a preset threshold, the flag represents a marking result of a target point, and the target point is any point in the three-dimensional point cloud.
It should be noted that, the bottom surface segmentation apparatus 800 of the three-dimensional point cloud may implement the steps of the bottom surface segmentation method of the three-dimensional point cloud provided in any one of the foregoing method embodiments, and may achieve the same technical effects, which are not described herein in detail.
Example six
As shown in fig. 9, the embodiment of the present application further provides an electronic device, which includes a processor 911, a communication interface 912, a memory 913, and a communication bus 914, wherein the processor 911, the communication interface 912, and the memory 913 perform communication with each other through the communication bus 914,
a memory 913 for storing a computer program;
in one embodiment of the present application, the processor 911 is configured to implement the method for partitioning the bottom surface of the three-dimensional point cloud provided in any one of the foregoing method embodiments when executing the program stored on the memory 913, where the method includes:
acquiring a three-dimensional point cloud corresponding to a target space;
filtering the three-dimensional point cloud;
performing grid division on the three-dimensional point cloud subjected to the filtering treatment to obtain a grid set;
extracting all points meeting preset conditions in each grid according to three-dimensional coordinates of points in each grid in a preset coordinate system, and determining the bottom surface of the three-dimensional point cloud according to the extracted points, wherein the preset conditions are that the value range of the points in a target direction is larger than or equal to the minimum coordinate value in the target direction and smaller than or equal to the sum of the minimum coordinate value in the target direction and a preset bottom surface thickness threshold value, and the target direction is any direction in the directions of a plurality of coordinate axes of the preset coordinate system;
and dividing the bottom surface of the three-dimensional point cloud.
Example seven
The embodiment of the application further provides a computer readable storage medium, on which a computer program is stored, which when executed by a processor, implements the steps of the method for partitioning the bottom surface of the three-dimensional point cloud provided in any one of the method embodiments described above.
It should be noted that in this document, relational terms such as "first" and "second" and the like are 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. Moreover, 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 one … …" does not exclude the presence of other like elements in a process, method, article, or apparatus that comprises the element.
The foregoing is only a specific embodiment of the invention to enable those skilled in the art to understand or practice the 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.
Claims (10)
1. A method for partitioning a bottom surface of a three-dimensional point cloud, the method comprising:
acquiring a three-dimensional point cloud corresponding to a target space;
filtering the three-dimensional point cloud;
performing grid division on the three-dimensional point cloud subjected to the filtering treatment to obtain a grid set;
extracting all points meeting preset conditions in each grid according to three-dimensional coordinates of the points in each grid in a preset coordinate system, and determining the bottom surface of the three-dimensional point cloud according to the extracted points, wherein the preset conditions are that the value range of the points in a target direction is larger than or equal to the minimum coordinate value in the target direction and smaller than or equal to the sum of the minimum coordinate value in the target direction and a preset bottom surface thickness threshold value, and the target direction is any direction in the directions of a plurality of coordinate axes of the preset coordinate system;
and dividing the bottom surface of the three-dimensional point cloud.
2. The method of claim 1, wherein meshing the three-dimensional point cloud after the filtering process to obtain a mesh set comprises:
acquiring coordinate distribution ranges of the three-dimensional point cloud subjected to filtering treatment in two directions perpendicular to the target direction;
according to the coordinate distribution range in two directions perpendicular to the target direction and the grid granularity preset in the two directions perpendicular to the target direction, carrying out grid division on the three-dimensional point cloud after filtering processing to obtain a grid set of the three-dimensional point cloud in the target direction, wherein the target direction is any one direction of a plurality of directions of a preset coordinate system, and the grid granularity is used for representing the number of grids of the three-dimensional point cloud to be divided in the corresponding direction.
3. The method according to claim 2, wherein the obtaining the coordinate distribution range of the three-dimensional point cloud after the filtering processing in two directions perpendicular to the target direction includes:
obtaining maximum coordinate values and minimum coordinate values of each point in the three-dimensional point cloud after filtering in two directions perpendicular to the target direction;
and determining coordinate distribution ranges in two directions perpendicular to the target direction according to the obtained maximum coordinate value and the obtained minimum coordinate value.
4. The method according to claim 2, wherein the step of meshing the three-dimensional point cloud after the filtering process according to a coordinate distribution range in two directions perpendicular to the target direction and a mesh granularity preset in two directions perpendicular to the target direction to obtain a mesh set of the three-dimensional point cloud in the target direction includes:
acquiring grid granularity preset in two directions perpendicular to the target direction;
and carrying out grid division on the three-dimensional point cloud subjected to the filtering treatment according to a preset grid division rule to obtain a grid set of the three-dimensional point cloud in the target direction, wherein the preset grid division rule is to equally divide coordinate distribution ranges in two directions perpendicular to the target direction according to grid granularity respectively corresponding to the coordinate distribution ranges.
5. The method according to claim 1, wherein the extracting all the points satisfying the preset condition in each grid according to the three-dimensional coordinates of the points in each grid in the grid set in the preset coordinate system, and determining the bottom surface of the three-dimensional point cloud according to the extracted points, comprises:
determining the minimum coordinate value of the points in each grid in the grid set in the target direction according to the three-dimensional coordinates of the points in each grid in the grid set in a preset coordinate system;
extracting all points meeting the preset conditions in each grid respectively, and taking all extracted points as the bottom surfaces corresponding to each grid;
and combining the bottom surfaces corresponding to the grids to obtain the bottom surface of the three-dimensional point cloud.
6. The method of claim 1, wherein the filtering the three-dimensional point cloud comprises:
obtaining a marking result of each point in the three-dimensional point cloud by adopting a minimum radius method;
and carrying out filtering processing on the three-dimensional point cloud according to the marking result.
7. The method of claim 6, wherein the equation for obtaining the labeling result is as follows:
wherein Num (R) represents the number of points in a spherical region with a target point as a center and R as a radius, N std And for a preset threshold value, the flag represents a mark result of the target point, wherein the target point is any point in the three-dimensional point cloud.
8. A device for partitioning a bottom surface of a three-dimensional point cloud, the device comprising:
the acquisition module is used for acquiring the three-dimensional point cloud corresponding to the target space;
the filtering processing module is used for carrying out filtering processing on the three-dimensional point cloud;
the grid dividing module is used for dividing the three-dimensional point cloud after the filtering processing into grids to obtain a grid set;
the determining module is used for extracting all points meeting preset conditions in each grid according to the three-dimensional coordinates of the points in each grid in a preset coordinate system, and determining the bottom surface of the three-dimensional point cloud according to the extracted points, wherein the preset conditions are that the value range of the points in a target direction is larger than or equal to the minimum coordinate value in the target direction and smaller than or equal to the sum of the minimum coordinate value in the target direction and a preset bottom surface thickness threshold value, and the target direction is any direction in the directions of a plurality of coordinate axes of the preset coordinate system;
and the segmentation module is used for segmenting the bottom surface of the three-dimensional point cloud.
9. The electronic equipment is characterized by comprising a processor, a communication interface, a memory and a communication bus, wherein the processor, the communication interface and the memory are communicated with each other through the communication bus;
a memory for storing a computer program;
a processor for implementing the steps of the method for bottom surface segmentation of a three-dimensional point cloud according to any one of claims 1 to 7 when executing a program stored on a memory.
10. A computer readable storage medium, on which a computer program is stored, characterized in that the computer program, when being executed by a processor, implements the steps of the method for floor segmentation of a three-dimensional point cloud according to any of claims 1-7.
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202211566698.4A CN116385702A (en) | 2022-12-07 | 2022-12-07 | Method and device for dividing bottom surface of three-dimensional point cloud, electronic equipment and storage medium |
| PCT/CN2023/136778 WO2024120437A1 (en) | 2022-12-07 | 2023-12-06 | Bottom surface segmentation method and apparatus for three-dimensional point cloud, and electronic device and storage medium |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202211566698.4A CN116385702A (en) | 2022-12-07 | 2022-12-07 | Method and device for dividing bottom surface of three-dimensional point cloud, electronic equipment and storage medium |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN116385702A true CN116385702A (en) | 2023-07-04 |
Family
ID=86971786
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202211566698.4A Pending CN116385702A (en) | 2022-12-07 | 2022-12-07 | Method and device for dividing bottom surface of three-dimensional point cloud, electronic equipment and storage medium |
Country Status (2)
| Country | Link |
|---|---|
| CN (1) | CN116385702A (en) |
| WO (1) | WO2024120437A1 (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2024120437A1 (en) * | 2022-12-07 | 2024-06-13 | 北京东土科技股份有限公司 | Bottom surface segmentation method and apparatus for three-dimensional point cloud, and electronic device and storage medium |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN118334278B (en) * | 2024-06-17 | 2024-08-27 | 之江实验室 | Point cloud data processing method, device, storage medium and equipment |
Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN108596860A (en) * | 2018-05-10 | 2018-09-28 | 芜湖航飞科技股份有限公司 | A kind of ground point cloud dividing method based on three-dimensional laser radar |
| CN112070870A (en) * | 2020-07-31 | 2020-12-11 | 广州景骐科技有限公司 | Point cloud map evaluation method and device, computer equipment and storage medium |
| CN112432647A (en) * | 2020-11-09 | 2021-03-02 | 深圳市汇川技术股份有限公司 | Positioning method, device and system of carriage and computer readable storage medium |
| WO2021097618A1 (en) * | 2019-11-18 | 2021-05-27 | 深圳市大疆创新科技有限公司 | Point cloud segmentation method and system, and computer storage medium |
| WO2022099511A1 (en) * | 2020-11-11 | 2022-05-19 | 深圳元戎启行科技有限公司 | Method and apparatus for ground segmentation based on point cloud data, and computer device |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2000172879A (en) * | 1998-12-11 | 2000-06-23 | Hitachi Ltd | Method and device for dividing shape, storage medium storing shape dividing program, and manufacture of the device |
| CN111928811B (en) * | 2020-09-22 | 2021-01-08 | 上海钛米机器人股份有限公司 | Ground detection method, device, equipment and storage medium |
| CN116385702A (en) * | 2022-12-07 | 2023-07-04 | 北京东土科技股份有限公司 | Method and device for dividing bottom surface of three-dimensional point cloud, electronic equipment and storage medium |
-
2022
- 2022-12-07 CN CN202211566698.4A patent/CN116385702A/en active Pending
-
2023
- 2023-12-06 WO PCT/CN2023/136778 patent/WO2024120437A1/en unknown
Patent Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN108596860A (en) * | 2018-05-10 | 2018-09-28 | 芜湖航飞科技股份有限公司 | A kind of ground point cloud dividing method based on three-dimensional laser radar |
| WO2021097618A1 (en) * | 2019-11-18 | 2021-05-27 | 深圳市大疆创新科技有限公司 | Point cloud segmentation method and system, and computer storage medium |
| CN112070870A (en) * | 2020-07-31 | 2020-12-11 | 广州景骐科技有限公司 | Point cloud map evaluation method and device, computer equipment and storage medium |
| CN112432647A (en) * | 2020-11-09 | 2021-03-02 | 深圳市汇川技术股份有限公司 | Positioning method, device and system of carriage and computer readable storage medium |
| WO2022099511A1 (en) * | 2020-11-11 | 2022-05-19 | 深圳元戎启行科技有限公司 | Method and apparatus for ground segmentation based on point cloud data, and computer device |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2024120437A1 (en) * | 2022-12-07 | 2024-06-13 | 北京东土科技股份有限公司 | Bottom surface segmentation method and apparatus for three-dimensional point cloud, and electronic device and storage medium |
Also Published As
| Publication number | Publication date |
|---|---|
| WO2024120437A1 (en) | 2024-06-13 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN106970375B (en) | Method for automatically extracting building information from airborne laser radar point cloud | |
| CN116385702A (en) | Method and device for dividing bottom surface of three-dimensional point cloud, electronic equipment and storage medium | |
| CN107610061B (en) | Edge-preserving point cloud hole repairing method based on two-dimensional projection | |
| CN115564926B (en) | Three-dimensional patch model construction method based on image building structure learning | |
| CN105139379B (en) | Based on the progressive extracting method of classified and layered airborne Lidar points cloud building top surface | |
| CN111598780B (en) | Terrain adaptive interpolation filtering method suitable for airborne LiDAR point cloud | |
| CN112164145B (en) | Method for rapidly extracting indoor three-dimensional line segment structure based on point cloud data | |
| CN115222625A (en) | Laser radar point cloud denoising method based on multi-scale noise | |
| CN108830933B (en) | Method, system, medium and equipment for rebuilding tower body of electric tower | |
| KR100857529B1 (en) | Method of automatic extraction of building boundary from lidar data | |
| CN115239887A (en) | Method and system for reconstructing Manhattan building axis with high precision by utilizing indoor and outdoor point clouds | |
| CN116721228B (en) | Building elevation extraction method and system based on low-density point cloud | |
| CN112687005A (en) | Coal pile volume measurement method based on three-dimensional reconstruction | |
| CN102222357A (en) | Foot-shaped three-dimensional surface reconstruction method based on image segmentation and grid subdivision | |
| CN113409332B (en) | Building plane segmentation method based on three-dimensional point cloud | |
| CN114119902A (en) | Building extraction method based on unmanned aerial vehicle inclined three-dimensional model | |
| CN115049925A (en) | Method for extracting field ridge, electronic device and storage medium | |
| CN115965712A (en) | Building two-dimensional vector diagram construction method, system, equipment and storage medium | |
| CN109344750B (en) | Complex structure three-dimensional object identification method based on structure descriptor | |
| CN113838069B (en) | Point cloud segmentation method and system based on flatness constraint | |
| CN113781649B (en) | Building plan generating method based on three-dimensional scanning point cloud | |
| CN114548277A (en) | Method and system for fitting ground points and extracting crop height based on point cloud data | |
| CN116266365A (en) | Point cloud data extraction method and device, electronic equipment and storage medium | |
| CN117132737B (en) | Three-dimensional building model construction method, system and equipment | |
| CN116186864B (en) | Deep foundation pit model rapid modeling method and system based on BIM technology |
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 |