CN117607829B - Ordered reconstruction method of laser radar point cloud and computer readable storage medium - Google Patents

Abstract

A method for orderly reconstructing laser radar point cloud and a computer readable storage medium convert the problem of ordering the laser radar point cloud into the problem of ordering a set of horizontal azimuth angles and vertical pitch angles of laser beams corresponding to the laser radar point cloud, preset a laser radar pixel matrix, calculate the specific positioning of the point cloud on the laser radar pixel matrix according to the horizontal azimuth angles and the vertical pitch angles of the laser beams corresponding to the point cloud based on the imaging principle of various types of laser radars, realize the ordered arrangement of the three-dimensional point cloud under the two-dimensional angle distribution, and finish the ordered transformation of the original point cloud. After the ordered reconstruction method is adopted to order the original point cloud set, dynamic inquiry of any point in three-dimensional distribution or ordered two-dimensional distribution can be realized by means of the laser radar pixel matrix, and the time complexity of the inquiry or indexing process of any point or the adjacent point on the pixel matrix is only O (1).

Description

Orderly reconstruction method of laser radar point cloud and computer readable storage medium

Technical Field

The present invention relates to the field of computer three-dimensional vision, and in particular to an ordered reconstruction method of a laser radar point cloud and a computer-readable storage medium.

Background Art

For the current industrialized lidar equipment, especially in the field of autonomous driving, the output data of the equipment generally only contains the spatial distribution coordinates (x, y, z) describing the point cloud and the reflection intensity or multiple echo information, etc., and lacks the description of the order of point cloud generation, the adjacency relationship between point clouds, etc. This further limits the research on the structured expression of large outdoor sparse point clouds.

The existing target detection tasks based on point clouds often require mining the feature information of objects based on the relationship between point cloud sets in spatial and geometric dimensions. When LiDAR collects point clouds, i.e. receives laser signals reflected by objects, it often lacks the underlying original information of the sensor, such as the order and timing of received signals, the number and orientation of the laser receiving component to which the received signals belong, etc. The lack of such original information of discrete point clouds means that additional calculation and storage costs are required in the process of realizing the above functions. Therefore, it is necessary to sort the LiDAR point clouds.

Summary of the invention

The main technical problem solved by the present invention is how to achieve orderly expression of lidar point cloud.

According to the first aspect, an embodiment provides a method for orderly reconstruction of a laser radar point cloud, comprising:

Get the original point cloud set collected by the laser radar;

If the laser radar is a solid-state laser radar, the horizontal azimuth and vertical pitch angle of the laser beam corresponding to each point cloud are calculated according to the three-dimensional coordinates of each point cloud in the original point cloud set, and the coordinates ( u _{i ,} vi ) of each point cloud on the preset laser radar pixel matrix are calculated according to the horizontal azimuth and vertical pitch angle of the laser beam corresponding to each point cloud, where ( u _i , _vi ) represents the coordinates of the i -th point cloud on the laser radar pixel matrix;

If the laser radar is a mechanical laser radar or a semi-solid laser radar, the horizontal azimuth and vertical pitch angle of the laser beam corresponding to each point cloud are calculated according to the three-dimensional coordinates of each point cloud in the original point cloud set, the actual number of lines and the actual horizontal cumulative number of steps of the laser beam corresponding to each point cloud are calculated according to the horizontal azimuth and vertical pitch angle of the laser beam corresponding to each point cloud, and the coordinates ( u _i , vi _i ) of each point cloud on the laser radar pixel matrix are calculated according to the actual number of lines and the actual horizontal cumulative number of steps of the laser beam corresponding to each point cloud;

If the laser radar is a dual-prism semi-solid laser radar, then according to the laser radar Centrifugal inclination function and The laser deflection angle function calculates the horizontal azimuth and vertical pitch angle of the laser beam corresponding to each point cloud, and the actual number of lines and the actual horizontal cumulative number of steps of the laser beam corresponding to each point cloud are calculated according to the horizontal azimuth and vertical pitch angle of the laser beam corresponding to each point cloud. The coordinates ( u _i , vi) of each point cloud on the laser radar pixel matrix are calculated according to the actual number of lines and the actual horizontal cumulative number of steps of the laser beam _{corresponding} to each point cloud.

If the laser radar is a pure solid-state laser radar, and the target size of the laser radar pixel matrix is W × H , where W and H are positive integers, then in one embodiment, the coordinates of each point cloud on the preset laser radar pixel matrix are calculated based on the horizontal azimuth angle and vertical pitch angle of the laser beam corresponding to each point cloud, including:

The coordinates of each point cloud on the laser radar pixel matrix are calculated according to the following formula:

,

_Wherein θi represents the horizontal azimuth angle of the _laser beam corresponding to the i- th point cloud, γi represents the vertical pitch angle of the laser beam corresponding to the i - th point cloud, Ang _Horizontal is the horizontal azimuth angle of the laser radar, and Ang _Vertical is the vertical pitch angle of the laser radar.

If the laser radar is a mechanical laser radar or a semi-solid laser radar or a dual-prism semi-solid laser radar, and the target size of the laser radar pixel matrix is W × H , where W and H are positive integers, then in one embodiment, the coordinates of each point cloud on the laser radar pixel matrix are calculated based on the actual number of lines and the actual horizontal cumulative number of steps of the laser beam corresponding to each point cloud, including:

The coordinates of each point cloud on the laser radar pixel matrix are calculated according to the following formula:

,

Wherein o _i represents the actual horizontal cumulative number of steps of the laser beam corresponding to the i - th point cloud, qi _represents the actual number of lines of the laser beam corresponding to the i - th point cloud, O is the total number of horizontal rotation or vibration steps of the laser radar, and Q is the total number of laser beam lines of the laser radar.

In one embodiment, the actual number of lines and the actual number of horizontal accumulated steps of the laser beam corresponding to the point cloud are determined by the following formula:

,

Among them, θi represents the horizontal azimuth angle of the laser beam corresponding to the i - th point cloud, _γi represents the vertical pitch angle of _the laser beam corresponding to the i - th point cloud, It means that when θ = θ _i, the function The value of It means that when γ = γ _i, the function The value of represents the inverse function of the distribution function In ( o ) _of the horizontal azimuth angle of the laser beam of the laser radar, Represents the inverse function of the distribution function L _m ( q ) of the vertical pitch angle of the laser beam of the laser radar.

In one embodiment, the laser beam of the laser radar is evenly distributed in M segments in the vertical viewing angle and evenly distributed in N segments in the horizontal viewing angle, where M and N are both positive integers; the expression of the distribution function I _n ( o ) of the horizontal azimuth angle of the laser beam of the laser radar is:

,

_Wherein θn represents the horizontal azimuth angle of the nth laser beam in the horizontal viewing angle, o represents the horizontal cumulative number of steps of the laser beam, o _{n -1} represents the starting horizontal cumulative number of steps of the nth laser beam in the horizontal viewing angle, o _n represents the ending horizontal cumulative number of steps of the nth laser beam in the horizontal viewing angle, a _n , b _n and c _n represent the quadratic term coefficient, linear term coefficient and constant term of the quadratic fitting curve of the horizontal azimuth angle of the nth laser beam in the horizontal viewing angle, respectively;

The distribution function L _m ( q ) of the vertical pitch angle of the laser beam of the laser radar is expressed as:

,

Wherein, γ _m represents the vertical pitch angle of the mth laser beam within the vertical viewing angle, q represents the number of laser beam lines, q _{m -1} represents the starting line number of the mth laser beam within the vertical viewing angle, q _m represents the ending line number of the mth laser beam within the vertical viewing angle, K _m and B _m respectively represent the slope and intercept of the linear fitting curve of the vertical pitch angle of the mth laser beam within the vertical viewing angle.

If the laser radar is a dual-prism semi-solid laser radar, in one embodiment, the horizontal azimuth angle and vertical pitch angle of the laser beam corresponding to the point cloud are determined by the following formula:

,

in Indicates the laser radar Centrifugal inclination function, Indicates the laser radar Laser deflection _angle function, β1 and β2 are the refraction angles of the double prisms of the laser radar, ω1 and ω2 are the rotation _angular velocities of _the double prisms of the laser radar, and t _is the rotation time of the double prisms of the laser radar.

In one embodiment, W is greater than a theoretical value of the width of a pixel plane of the laser radar, and H is greater than a theoretical value of the height of a pixel plane of the laser radar.

In one embodiment, the ordered reconstruction method further comprises:

Obtain an index matrix P2T of the original point cloud set converted to a sensor pixel coordinate set T {( u , v )} of the original point cloud set, wherein the sensor pixel coordinate set T {( u , v )} of the original point cloud set is composed of the coordinates ( ui , vi ) of each point cloud in the original point cloud set on the _laser radar pixel matrix _;

Obtain an inverse index matrix X2P of the original point cloud set converted to a target expression form X, wherein the target expression form X includes but is not limited to voxelization of the point cloud and projection compression of the point cloud in a bird's-eye view or a front view;

The original point cloud set in the target expression form X is transformed according to the inverse index matrix X2P, and then transformed according to the index matrix P2T to obtain the sensor pixel coordinate set T' {( u , v )} of the original point cloud set in the target expression form X.

In one embodiment, the ordered reconstruction method further comprises:

According to the sensor pixel coordinate set T {( u , v )} of the original point cloud set, for any non-empty pixel ( ui , vi ), obtain its corresponding point cloud pi _{, and} obtain the point cloud set corresponding to the non-empty pixels in the neighbor area bounding box with the non-empty pixel ( ui _, vi ) as the center _and with a preset target size _as the neighbor _point set PNi ₌ { pk , k =1,2..., Np } of the point cloud pi , where _pk represents the point _cloud corresponding to the kth non- _empty pixel in the neighbor area bounding box, _Np represents the total number of non-empty pixels in the neighbor area bounding box , and the sensor pixel coordinate set T {( u , v )} of the original point cloud set is composed of the coordinates ( ui _, vi ) of each point cloud in the original point cloud set on the laser radar pixel matrix _;

The directed edges from each point cloud in the neighbor point set PN _i to the point _cloud pi constitute a directed edge set ;

With point cloud p _i and its neighbor point set PN _i as vertices and directed edge set E _i as edges, a local directed graph with point cloud p _i as key point is obtained. ;

The sensor pixel coordinate set T {( u , v )} of the original point cloud set is traversed to obtain a local directed graph with the point cloud corresponding to each non-empty pixel as a key point, thereby realizing the transformation from the original point cloud set to the directed graph expression.

According to the second aspect, an embodiment provides a computer-readable storage medium, on which a program is stored, and the program can be executed by a processor to implement the ordered reconstruction method of any of the above embodiments.

According to the ordered reconstruction method of the laser radar point cloud of the above embodiment, the ordering problem of the laser radar point cloud is converted into the ordering problem of the horizontal azimuth and vertical pitch angle set { θ , γ } of the laser beam corresponding to the laser radar point cloud (where θ is the horizontal azimuth and γ is the vertical pitch angle), and the laser radar pixel matrix is preset. For various types of laser radars, based on their imaging principles, according to the horizontal azimuth and vertical pitch angle of the laser beam corresponding to the point cloud, the specific location of the point cloud on the laser radar pixel matrix, i.e., the pixel coordinates ( u , v ), is calculated, and the ordered arrangement of the three-dimensional point cloud under the two-dimensional angle distribution is realized, and the ordered transformation of the original point cloud set is completed. After the original point cloud set is ordered by the ordered reconstruction method of the present invention, the index matrix from the original point cloud set to the pixel coordinate set can be used to realize the dynamic query of any point in the three-dimensional distribution or the ordered two-dimensional distribution, and the time complexity of the query or index process for any point or its neighboring points on the pixel matrix is only O(1).

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a schematic diagram showing the relationship between the three-dimensional coordinates of a point cloud and the horizontal azimuth and vertical pitch angle of a laser beam corresponding to the point cloud;

FIG2 is a schematic diagram of a laser radar pixel matrix according to an embodiment;

FIG3 is a flow chart of a method for orderly reconstruction of a laser radar point cloud in an embodiment;

FIG4 is a schematic diagram of the horizontal azimuth and vertical pitch angle distribution characteristics of a purely mechanical or semi-solid laser radar;

FIG5 is a schematic diagram of the basic imaging principle of a dual-prism semi-solid laser radar;

FIG6 is a flow chart of a method for orderly reconstruction of a laser radar point cloud in another embodiment;

FIG7 is a schematic diagram of finding a neighbor point set of a point cloud and establishing a directed edge set;

FIG8 is a flow chart of a method for orderly reconstruction of a lidar point cloud in yet another embodiment.

DETAILED DESCRIPTION

The present invention is further described in detail below by specific embodiments in conjunction with the accompanying drawings. Wherein similar elements in different embodiments adopt associated similar element numbers. In the following embodiments, many detailed descriptions are for making the present application better understood. However, those skilled in the art can easily recognize that some features can be omitted in different situations, or can be replaced by other elements, materials, methods. In some cases, some operations related to the present application are not shown or described in the specification, this is to avoid the core part of the present application being overwhelmed by too much description, and for those skilled in the art, it is not necessary to describe these related operations in detail, and they can fully understand the related operations according to the description in the specification and the general technical knowledge in the art.

In addition, the features, operations or characteristics described in the specification can be combined in any appropriate manner to form various implementations. At the same time, the steps or actions in the method description can also be interchanged or adjusted in a manner that is obvious to those skilled in the art. Therefore, the various sequences in the specification and the drawings are only for the purpose of clearly describing a certain embodiment and are not meant to be a required sequence, unless otherwise specified that a certain sequence must be followed.

The serial numbers assigned to the components in this document, such as "first", "second", etc., are only used to distinguish the objects described and do not have any order or technical meaning. The "connection" and "connection" mentioned in this application, unless otherwise specified, include direct and indirect connections (connections). The "lidar" and "lidar sensor" in this document refer to the same thing.

The technical solution of the present invention is mainly applied to the post-processing process of sensor radar output data and the pre-processing process of point cloud-based target detection and other functions. The present invention provides a general, reliable and computationally cost-limited ordered reconstruction method for lidar point clouds. In addition, on this basis, it can be extended to the ordered expression of other expression types of point clouds. At the same time, an embodiment of the present invention provides a calculation method based on directed edges between ordered point clouds on the basis of ordered expression, thereby realizing the graph expression of point clouds.

In order to better understand the technical solution of the present invention, some prior arts are briefly introduced below.

In the prior art, the ordering methods for discrete point clouds generally include:

1. The default input point cloud sequence is used as the ordered point cloud, and the initial sequence is used as the basis for subsequent processing. When this method is applied to deep learning, it violates the permutation invariance principle of the deep learning network for the input data;

2. Order the point cloud based on data structures such as KD-Tree and Oc-Tree, and use the point cloud coordinates or area information as the basis for establishing the tree structure.

The key to the graphical representation of discrete point clouds is to determine the neighboring points of spatial points. The existing methods for obtaining the Euclidean distance neighbors of a point in three-dimensional space include:

1. Directly use the target point as the center of the sphere and search for existing point clouds within a sphere of a certain radius as neighboring points of the target point. This process does not require additional data storage, but requires a calculation process with a time complexity of O(n ² ). To speed up the above process, the original point cloud can be downsampled more evenly through rasterization or farthest point sampling, and then the point cloud near the target point is searched with a sphere of a certain size. This process also requires an operation with a time complexity of O(n ² ). It only speeds up the process by reducing the scale of the point cloud.

2. Algorithms based on tree structures such as KD-Tree and Oc-Tree. This type of method requires preprocessing of point cloud data for tree building. Under the tree structure, layer-by-layer judgment is made based on coordinate data or hyperplanes, and the neighbor information of the target point in the tree structure is returned. The disadvantage of this type of method is that the tree building process consumes time and memory and requires additional data structures. The advantage is that it can achieve neighbor indexing with a time complexity of O(n);

3. Point cloud depth map based on spherical projection. This method uses the sensor as the origin and projects the point cloud into a two-dimensional plane according to its horizontal and vertical angle distribution to realize the projection of the 3D point cloud onto the 2D image. This method explicitly assigns one or more point cloud information to each 2D image pixel, and the neighboring relationship between pixels can be considered as the neighbor relationship of the 3D point cloud. The advantage of this method is that it has high computational efficiency and can achieve a time complexity of O(1) for indexing any point. The disadvantage is that this method assumes that the angular distribution of the spatial point cloud is uniformly distributed by default. For some sensors with uneven point cloud distribution, the description of the real 3D information in the projected 2D image is distorted, and thus the representation of the point cloud ordering and neighbor relationship is also distorted.

The point cloud data generated by the LiDAR describes the surface information of objects in the scanning area. The LiDAR projects laser light onto the surface of the object, and the surface of the object reflects the laser light to the LiDAR sensor to form an image, generating point cloud data. Unlike point cloud data of models or indoor scenes in the field of 3D modeling, point cloud data in scenarios such as autonomous driving has a sparse distance correlation, that is, the farther the distance, the sparser the point cloud distribution. This has led to the fact that previous point cloud processing methods are no longer applicable to the current research stage due to high computational costs and lack of real-time performance.

The inventor of the present invention realizes that since the current laser radar equipment must rely on reciprocating (mechanical or semi-solid laser radar) or array (solid-state laser radar) to emit laser beams when implementing the above process, it can be considered that the reflection points of the laser beam of the object to a certain extent not only describe the surface structure distribution of the object, but also that the adjacent reflection points have a certain proximity relationship in the laser radar sensor. Therefore, the present invention proposes an ordered reconstruction method suitable for the original point cloud data of any type of laser radar sensor (mechanical, semi-solid, solid) or other expressions of point clouds (such as voxelization, rasterization, etc. of point clouds), aiming to reconstruct the sensor coordinates of the three-dimensional point cloud based only on the laser radar imaging principle and the spatial coordinate data of the point cloud, under the premise of the lack of the original measurement sequence information and distribution information of the laser radar sensor, and accurately obtain the absolute position of the point cloud in the sensor coordinate system, so as to realize the ordering of the original point cloud.

After the absolute position coordinates of each spatial point are determined, the neighboring point clouds of each point cloud in the sensor coordinate system can be found according to the coordinate information. At the same time, the directed edges between point clouds can be defined to transform the discrete point cloud set into graph data. At this point, the conversion process from discrete spatial points to ordered points and then to the graph expression of point clouds is completed. The following is an overview of the basis of the technical solution of the present invention.

Given an original point cloud set, denoted as , where N is the number of point clouds in the point cloud set, (3+ C+L ) represents the information dimension of each point cloud, 3 represents the ( x , y , z ) coordinates, C represents the characteristic information such as the reflection intensity of the point cloud, and L represents the label information of the point cloud. In general, the reflection intensity information expressed by C is the intensity signal value in the interval [0,1], and other possible characteristic information is also attribute information expressed by some numerical value. The label L is generally an integer value. In practical applications, it can be mapped by an integer value greater than 0 to represent information such as "trees" and "buildings" according to different application scenarios.

According to the laser radar measurement principle, the spatial three-dimensional coordinates ( x , y , z ) of any normal imaging point are determined by the distance d calculated from the flight time of the reflected laser beam and the horizontal rotation angle (i.e. horizontal azimuth angle) θ and vertical angle (i.e. vertical pitch angle) γ of the corresponding laser beam, as shown in the following formula (1):

. (1)

Under ideal measurement conditions, each three-dimensional space measurement point should correspond to a unique laser beam at the same time. Therefore, for the point cloud set P , please refer to Figure 1. The horizontal azimuth angle θ _i and the vertical pitch angle γ _i of the laser beam corresponding to any point pi can be reversely _calculated based on its three-dimensional coordinates, as shown in formula (2). The ordering problem of the point cloud set P can be transformed into the ordering problem of the horizontal azimuth angle and vertical pitch angle set { θ , γ } of the laser beam corresponding to the point cloud.

. (2)

The present invention proposes an ordered arrangement method according to the properties of the laser radar sensor for the problem of ordering the horizontal azimuth and vertical pitch angle set { θ , γ } of the laser beam, that is, according to the horizontal azimuth and vertical pitch angle distribution of the laser beam corresponding to the point cloud, the specific location of the point cloud in the laser radar field of view is calculated. Referring to the principle of visual imaging, the present invention defines the laser radar field of view as a two-dimensional matrix with a target size of W × H , called the laser radar pixel matrix, which represents the pixel plane of the laser radar imaging, and forms the sensor pixel coordinate system Ouv (that is, the laser radar field of view coordinate system) based on this, as shown in Figure 2, where W and H are positive integers. In the laser radar field of view coordinate system, the point cloud is located to the pixel coordinate ( u , v ) through the horizontal azimuth and vertical pitch angle information, where u is the horizontal coordinate and v is the vertical coordinate. The above process reconstructs the coordinates of the three-dimensional point cloud in the two-dimensional pixel matrix, and realizes the ordered arrangement of the three-dimensional point cloud under the two-dimensional angle distribution. The process definition is shown in formula (3).

. (3)

Here, F _rebuild refers to the process of ordered reconstruction.

It should also be noted that the inventors have noticed that for multi-beam laser radars, the complex imaging process often cannot ensure that the laser receiving component receives the specified laser beam according to the ideal setting, which often results in the horizontal azimuth angle θ and the vertical pitch angle γ obtained by reverse calculation according to formula (2) exceeding the laser radar field of view angle range under theoretical conditions. Therefore, the target sizes W and H of the laser radar pixel matrix are preferably such that W is greater than the theoretical value of the width of the laser radar pixel plane, and H is greater than the theoretical value of the height of the laser radar pixel plane.

According to the above description, please refer to FIG. 3 , a method for orderly reconstruction of a lidar point cloud in an embodiment of the present invention includes steps 100 to 400 , which are introduced below.

Step 100: Obtain the original point cloud set collected by the laser radar.

The ordered reconstruction method of the present invention is applicable to any type of laser radar sensor (mechanical, semi-solid, solid), where the laser radar can be a solid-state laser radar, a mechanical laser radar or a semi-solid laser radar, etc.

Step 200: If the laser radar is a solid-state laser radar, the horizontal azimuth and vertical pitch angle of the laser beam corresponding to each point cloud are calculated according to the three-dimensional coordinates of each point cloud in the original point cloud set, and _the coordinates ( ui , vi ) of each point cloud on the preset laser radar pixel matrix are calculated according to the horizontal azimuth and vertical pitch angle of the laser beam corresponding to each point cloud, where (ui _{, vi )} represents the _coordinates of the i -th point cloud pi on the laser radar pixel matrix.

The solid-state laser radar here refers to a pure solid-state laser radar. The horizontal azimuth and vertical pitch angle of the laser beam corresponding to each point cloud can be calculated based on the three-dimensional coordinates of each point cloud in the original point cloud set. See formula (2). For a pure solid-state laser radar, since its imaging principle is similar to classical visual imaging, the pixel coordinates ( u _i , vi ) of any point cloud p _i can be calculated by referring to the classical visual imaging _principle .

The laser radar pixel matrix is preset before orderly reconstruction, wherein W and H can be set according to actual needs, and the selection of W and H determines the accuracy of the orderly reconstruction method of the present invention.

Step 300: If the laser radar is a mechanical laser radar or a semi-solid laser radar, the horizontal azimuth and vertical pitch angle of the laser beam corresponding to each point cloud are calculated according to the three-dimensional coordinates of each point cloud in the original point cloud set, and the actual number of lines and the actual horizontal cumulative number of steps of the laser beam corresponding to each point cloud are calculated according to the horizontal azimuth and vertical pitch angle of the laser beam corresponding to each point cloud. The coordinates ( u _{i ,} vi ) of each point cloud on the laser radar pixel matrix are calculated according to the actual number of lines and the actual horizontal cumulative number of steps of the laser beam corresponding to each point cloud.

Similarly, the horizontal azimuth and vertical pitch angle of the laser beam corresponding to each point cloud can be calculated based on the three-dimensional coordinates of each point cloud in the original point cloud set, as shown in formula (2). The actual number of lines of the laser beam corresponding to the point cloud refers to the number of laser beams, while pure mechanical or semi-solid laser radars need to use microelectronic galvanometers or mechanical rotation to achieve array or surround laser scanning. The actual horizontal cumulative number of steps of the laser beam refers to the total number of steps of horizontal rotation or vibration of the laser radar when emitting the laser beam.

Step 400: If the laser radar is a dual-prism semi-solid laser radar, Centrifugal inclination function and The laser deflection angle function calculates the horizontal azimuth and vertical pitch angle of the laser beam corresponding to each point cloud. The actual number of lines and the actual horizontal cumulative steps of the laser beam corresponding to each point cloud are calculated according to the horizontal azimuth and vertical pitch angle of the laser beam corresponding to each point cloud. The coordinates ( u _i , vi ) of each point cloud on the lidar pixel matrix are calculated according to the actual number of lines and the actual horizontal cumulative steps of the laser beam corresponding to each _point cloud.

The dual prism semi-solid laser radar here refers to a semi-solid laser radar based on a rotating dual prism. Due to its unique laser deflection method, the horizontal azimuth angle and vertical pitch angle of the laser beam refracted by the rotating dual prism depend on the rotation angular velocity ω ₁ and ω ₂ of the dual prism, the rotation time t of the dual prism, and the refraction angles β ₁ and β ₂ of the dual prism. Therefore, the present invention proposes a method based on the dual prism semi-solid laser radar. Centrifugal inclination function and The laser deflection angle function is used to calculate the horizontal azimuth and vertical pitch angle of the laser beam corresponding to the point cloud, and then the coordinates ( u _{i ,} vi ) of each point cloud on the laser radar pixel matrix are calculated by referring to the semi-solid laser radar method.

For different types of lidar, there are some differences in the calculation methods from the horizontal azimuth angle θ and the vertical pitch angle γ to the pixel coordinates ( u , v ). The following details the ordered calculation method for the three types of lidar measurement principles described in the above steps.

For the pure solid-state laser radar in step 200, in one embodiment, the coordinates ( u _{i ,} vi ) of each point cloud on the laser radar pixel matrix are calculated according to the following formula:

, (4)

_Wherein θi represents the horizontal azimuth angle of the laser beam corresponding to the ith point cloud, γi represents the vertical pitch angle of the laser beam corresponding to the ith point _cloud , Ang _Horizontal is the horizontal azimuth angle of the laser radar, and Ang _Vertical is the vertical pitch angle of the laser radar.

Ang _Horizontal and Ang _Vertical express the horizontal and vertical viewing angles, respectively. The values of Ang _Horizontal and Ang _Vertical can be selected based on the theoretical value of the sensor performance or calculated according to the actual value distribution of the point cloud set. The theoretical values are generally clearly annotated in the manual of the lidar equipment, such as "horizontal 360°" or "horizontal 90°" or "vertical viewing angle +2°~-24°", etc. The values of different devices are generally different. Calculation based on the actual value distribution means: for a given point cloud set P , the horizontal azimuth and vertical pitch angle corresponding to all points under the point cloud set P can be obtained. According to the definition of viewing angle, the absolute value of the maximum value minus the minimum value in the horizontal azimuth or vertical pitch angle can be considered as the viewing angle range expressed by the point cloud set P , that is, Ang _Horizontal or Ang _Vertical .

For the pure mechanical laser radar or semi-solid laser radar in step 300, the coordinates of each point cloud on the laser radar pixel matrix are calculated according to the actual number of lines of the laser beam corresponding to each point cloud and the actual horizontal cumulative number of steps. According to the principle of visual imaging, in one embodiment, the coordinates of each point cloud on the laser radar pixel matrix are calculated specifically according to the following formula:

, (5)

Where o _i represents the actual horizontal cumulative steps of the laser beam corresponding to the i - th point cloud, qi represents the actual line _number of the laser beam corresponding to the i - th point cloud, O is the total number of horizontal rotation or vibration steps of the laser radar, and Q is the total number of laser beam lines of the laser radar. and are the scaling factors of the horizontal and vertical fields of view, respectively, which are used to adjust the overlap loss of the pixel coordinates ( u _{i ,} vi ) of the point cloud p _i in practical applications.

In one embodiment, the actual number of lines and the actual number of horizontal accumulated steps of the laser beam corresponding to the point cloud are determined by the following formula:

, (6)

in, It means that when θ = θ _i, the function The value of It means that when γ = γ _i, the function The value of represents the inverse function of the distribution function In ( o ) _of the horizontal azimuth angle of the laser beam of the laser radar, Represents the inverse function of the vertical pitch angle distribution function L _m ( q ) of the laser radar laser beam.

Those skilled in the art can understand that, based on the technical manual, mechanical structure and optical characteristics of the laser radar, and in combination with actual needs, the horizontal azimuth angle distribution function In ( o ) and the vertical pitch angle distribution function Lm ( q ) of the _laser beam can be summarized or _designed .

For pure mechanical laser radar or semi-solid laser radar, their imaging requires the use of microelectronic galvanometers or mechanical rotation to achieve area array or surround laser scanning. This type of sensor also achieves a specific number of laser lines or measurement point density by stacking multiple sets of laser emission/reception or rotation/oscillation mirrors. The inventors realize that this means that the laser beam of this type of sensor generally has a segmented uniformly distributed dot matrix in the horizontal or vertical viewing angle. Therefore, the present invention proposes a general method of ordered reconstruction based on the imaging principle for this type of laser radar sensor and its principle.

A pure mechanical or semi-solid laser radar with M -segment uniform distribution in the vertical viewing angle, N- segment uniform distribution in the horizontal viewing angle, Q laser lines, and O total number of horizontal rotation or vibration steps, has horizontal azimuth angle and vertical pitch angle distribution characteristics as shown in FIG4. In one embodiment, due to the laser module distribution characteristics, for a laser radar sensor with a total number of laser lines Q , the vertical pitch angle of the q -th laser beam follows the M- segment piecewise linear function L _m ( q ) shown in formula (7), that is, the expression of the distribution function L _m ( q ) of the vertical pitch angle of the laser beam is as shown in formula (7).

. (7)

The vertical pitch angle of each laser beam segment is fitted by a linear fitting curve, γ _m represents the vertical pitch angle of the mth laser beam segment within the vertical viewing angle, q represents the number of laser beam lines, q _{m -1} represents the number of starting lines of the mth laser beam segment within the vertical viewing angle, q _m represents the number of ending lines of the mth laser beam segment within the vertical viewing angle, and q _M = Q. K _m and B _m represent the slope and intercept of the linear fitting curve of the vertical pitch angle of the mth laser beam segment within the vertical viewing angle, respectively.

Those skilled in the art will appreciate that the value of the laser line number q segment can be _determined in combination with the equipment design manual and the laser radar structure. Generally, the values of Km and Bm are determined by the ideal or actual vertical pitch angle distribution. The specific _values can be estimated by linear fitting method based on the ideal or actual measured vertical pitch angle distribution. The distribution of the vertical resolution of some laser radars has a clear proportionality coefficient, which can be determined. ,in As a known parameter, combined with the ideal or actual vertical pitch angle Ang _Vertical , K _m can be calculated according to formula (8), where unit_k is the slope proportional factor.

. (8)

The horizontal azimuth distribution of a mechanical or semi-solid laser radar is generally determined by a mechanical rotation or microelectronic galvanometer system. In one embodiment, the expression of the horizontal azimuth distribution function I _n ( o ) of the laser beam of this type of laser radar is as shown in formula (9). . (9)

The horizontal azimuth angle of each laser beam segment is fitted by a quadratic fitting curve, θn represents the horizontal azimuth angle of the nth laser beam segment within the horizontal viewing angle, _o represents the horizontal cumulative number of steps of the laser beam, o _{n -1} represents the starting horizontal cumulative number of steps of the nth laser beam segment within the horizontal viewing angle, o _n represents the ending horizontal cumulative number of steps of the nth laser beam segment within the horizontal viewing angle, and o _N = O. a _n , b _n and c _n represent the quadratic term coefficient, the linear term coefficient and the constant term of the quadratic fitting curve of the horizontal azimuth angle of the nth laser beam segment within the horizontal viewing angle, respectively.

Those skilled in the art will appreciate that the value of the horizontal cumulative step number o segment can be determined by the rotation or vibration motion characteristics of the laser radar. The values of a _n , b _n and c _n are determined by the ideal or actual horizontal azimuth distribution. The specific values can be estimated by quadratic function fitting based on the ideal or actual measured horizontal azimuth distribution. Generally, for a purely mechanical laser radar that rotates 360° at a constant speed, the distribution function of the horizontal azimuth is At this time, the parameters a _n and c _n degenerate to constant 0, and b _n degenerates to constant resolution .

According to equations (7) and (9), we can further get the inverse function and , combined with formula (6), the actual number of lines and the actual horizontal cumulative number of steps of the laser beam that generates the point cloud can be inferred from the horizontal azimuth and vertical pitch angle of the point cloud, and finally the coordinates of the point cloud on the laser radar pixel matrix can be obtained according to formula (5). So far, this embodiment combines the basic technical properties of mechanical or semi-solid laser radars, and inversely infers the two-dimensional positioning of the point cloud in the laser radar receptive field according to the horizontal azimuth and vertical pitch angle of the point cloud.

For the dual-prism semi-solid laser radar in step 400, an embodiment of the present invention provides a formula for determining the horizontal azimuth angle and the vertical pitch angle as shown in formula (10) based on its basic imaging principle (as shown in FIG. 5 ):

, (10)

in Represents the laser radar Centrifugal inclination function, Represents the laser radar Laser deflection angle function, β ₁ and β ₂ are the refraction angles of the laser radar dual prism, ω ₁ and ω ₂ are the rotation angular velocities of the laser radar dual prism, and t is the rotation time of the dual prism. Combining equation (6) and equation (5), the coordinates ( u _i , vi ) of the point cloud on the laser radar pixel matrix are finally obtained, _and its general expression is shown in equation (11):

. (11)

At this point, the present invention obtains the coordinates ( ui , vi ) of each point cloud in the original point cloud set P on the laser radar pixel matrix, thereby forming the sensor pixel coordinate set T {( u , v )} of the _original point cloud set P , _and completing the ordered transformation of the original point cloud set P. According to the above-mentioned ordered reconstruction process, in some embodiments, the index matrix P2T and the inverse index matrix T2P of the original point cloud set P converted to the sensor pixel coordinate set T can be obtained at the same time, thereby realizing the dynamic query of any point in a three-dimensional distribution or an ordered two-dimensional distribution, and the time complexity of the query or index process of any point or its neighboring points on the pixel matrix is O(1).

Based on the ordering of the original point cloud, the present invention can be extended to the ordering of other expressions of point clouds. Other expressions of point clouds include but are not limited to voxelization of point clouds, projection compression of point clouds in bird's-eye views or front views, etc. For any point cloud expression form X, the index matrix P2X and the inverse index matrix X2P of the original point cloud set P converted to the point cloud sequence under the expression form X can be obtained. Furthermore, in order to obtain the sensor pixel coordinate set T ' under the point cloud expression form X, the original point cloud set can be used as a medium, and multiple indexing (i.e., X2P first and then P2T) can be performed to achieve the ordering of the expression form X. This indexing process can be combined into an index matrix X2P2T'. Specifically, as shown in FIG6, the ordered reconstruction method in some embodiments of the present invention, after completing the ordered reconstruction of the original point cloud set, that is, after step 200, step 300 or step 400, further includes the following steps:

Step 511, obtaining an index matrix P2T of the sensor pixel coordinate set T {( u , v )} converted from the original point cloud set;

Step 512: Obtain an inverse index matrix X2P of the original point cloud set converted to a target expression form X, where the target expression form X is a point cloud expression form that needs to be orderly reconstructed, including but not limited to voxelization of the point cloud, projection compression of the point cloud in a bird's-eye view or a front view, etc.;

Step 513: transform the original point cloud set in the target expression form X according to the inverse index matrix X2P, and then transform it according to the index matrix P2T to obtain the sensor pixel coordinate set T' {( u , v )} of the original point cloud set in the target expression form X.

On the basis of the ordering of the original point cloud, the present invention also proposes a transformation method expressed by the original point cloud set to a graph. _First , according to the sensor pixel coordinate set T {( u , v )} of the original point cloud set, for the point cloud p _i corresponding to any non-empty pixel ( ui , vi ₎ , find its neighbor point set PN _i and establish a directed edge set, and the establishment method is shown in Figure 7. Centered on the sensor pixel coordinate ( ui , vi ₎ corresponding to point p _i , a neighbor area bounding box with a target size of box_w × box_h is given, and the point cloud set corresponding to the non-empty pixels in the neighbor area bounding box _is returned as the neighbor point set PN _i ={ p _k , k =1,2……, N _p } of point p _i , where p _k represents the point cloud corresponding to the kth non-empty pixel in the neighbor area bounding box, and N _p represents the total number of non-empty pixels in the neighbor area bounding box. At the same time, a directed edge set pointing from the neighbor point set PN _i to the target point p _i can be obtained. According to the definition of the graph, with the target point p _i and its neighbor point set PN _i as vertices and the directed edge set E _i as the directed edge structure, we can get the local directed graph structure with p _i as the key point By traversing the sensor pixel coordinate set T {( u , v )} of the original point cloud set, the original point cloud set can be transformed into a directed graph expression. Specifically, as shown in FIG8 , the ordered reconstruction method in some embodiments of the present invention, after completing the ordered reconstruction of the original point cloud set, that is, after step 200, step 300 or step 400, further includes the following steps:

Step 521: According to the sensor pixel coordinate set T {( u _, v )} of the _original point cloud set, for any non-empty pixel ( ui , vi ), obtain its corresponding point cloud pi _, and obtain the point cloud set corresponding to the non-empty pixel in the neighboring area bounding box with the non-empty _pixel ( ui , vi ) as the center and with a preset target size _as the neighbor _point set PNi ₌ { pk _, k =1,2..., Np } of the point cloud pi _;

Step 522: The directed edges from each point cloud in the neighbor point set PN _i to the point _cloud pi form a directed edge set ;

Step 523: Take the point cloud pi _and each _point cloud in its neighbor point set PN _i as vertices and the directed edge set E _i as edges to form a local directed graph with the point cloud pi as the key point. ;

Step 524, traverse the sensor pixel coordinate set T {( u , v )} of the original point cloud set to obtain a local directed graph with the point cloud corresponding to each non-empty pixel as the key point, thus achieving the transformation from the original point cloud set to the directed graph expression.

On the basis of the above-mentioned graph expression method, the graph expressions of other expression forms of point cloud can be obtained by using the sensor pixel coordinate set T ' of other expression forms of point cloud.

According to the ordered reconstruction method of the laser radar point cloud of the above embodiment, the ordering problem of the laser radar point cloud is converted into the ordering problem of the horizontal azimuth and vertical pitch angle set { θ , γ } of the laser beam corresponding to the laser radar point cloud. For various types of laser radars, based on their imaging principles, according to the horizontal azimuth and vertical pitch angle of the laser beam corresponding to the point cloud, the pixel coordinates ( u , v ) of the point cloud on the laser radar pixel matrix are calculated, and the ordered arrangement of the three-dimensional point cloud under the two-dimensional angle distribution is realized, and the ordered point cloud is obtained. The ordered reconstruction method of the embodiment of the present invention has the following beneficial effects:

(1) It provides a point cloud ordering and point cloud image expression method for non-object models and non-indoor dense point cloud scenes, filling the technical gap;

(2) The ordered reconstruction method of the embodiment of the present invention can be executed in the preprocessing stage of the point cloud, and one processing is always applicable to each frame of the point cloud;

(3) The present invention provides a method for orderly reconstruction of point clouds based on the measurement principle of a laser radar sensor, and provides a method for fast querying point cloud neighbors with customizable performance. In addition, in some embodiments, a method for constructing directed edges and graph expressions based on ordered point clouds is also provided;

(4) After the original point cloud set is ordered by the ordered reconstruction method of the present invention, the index matrix from the original point cloud set to the pixel coordinate set can be used to dynamically query any point in a three-dimensional distribution or an ordered two-dimensional distribution, and the time complexity of the query or indexing process for any point or its neighboring points on the pixel matrix is only O(1). For the frequent switching of expression methods or the indexing of point cloud neighbors in some target detection models, the present invention can always provide a fast index with a time complexity of O(1).

(5) The present invention reconstructs based on the laser radar measurement principle, avoiding the geometric deformation caused by different point cloud density distribution to the spherical projection method. Compared with tree construction methods such as KDTree, it avoids the computational cost of the tree structure and reduces the index or query cost.

Those skilled in the art will appreciate that all or part of the functions of the various methods in the above-mentioned embodiments can be implemented by hardware or by computer programs. When all or part of the functions in the above-mentioned embodiments are implemented by computer programs, the program can be stored in a computer-readable storage medium, and the storage medium can include: read-only memory, random access memory, disk, optical disk, hard disk, etc., and the program is executed by a computer to implement the above-mentioned functions. For example, the program is stored in the memory of the device, and when the program in the memory is executed by the processor, all or part of the above-mentioned functions can be implemented. In addition, when all or part of the functions in the above-mentioned embodiments are implemented by computer programs, the program can also be stored in a storage medium such as a server, another computer, disk, optical disk, flash disk or mobile hard disk, and can be downloaded or copied and saved in the memory of the local device, or the system of the local device is updated, and when the program in the memory is executed by the processor, all or part of the functions in the above-mentioned embodiments can be implemented.

The above specific examples are used to illustrate the present invention, which is only used to help understand the present invention and is not intended to limit the present invention. For those skilled in the art, according to the idea of the present invention, some simple deductions, modifications or substitutions can be made.

Claims (8)

1. A method for orderly reconstruction of laser radar point cloud, characterized by comprising: Get the original point cloud set collected by the laser radar; If the laser radar is a solid-state laser radar, the horizontal azimuth and vertical pitch angle of the laser beam corresponding to each point cloud are calculated according to the three-dimensional coordinates of each point cloud in the original point cloud set, and the coordinates ( u _{i ,} vi ) of each point cloud on the preset laser radar pixel matrix are calculated according to the horizontal azimuth and vertical pitch angle of the laser beam corresponding to each point cloud, where ( u _i , _vi ) represents the coordinates of the i -th point cloud on the laser radar pixel matrix; If the laser radar is a mechanical laser radar or a semi-solid laser radar, the horizontal azimuth and vertical pitch angle of the laser beam corresponding to each point cloud are calculated according to the three-dimensional coordinates of each point cloud in the original point cloud set, the actual number of lines and the actual horizontal cumulative number of steps of the laser beam corresponding to each point cloud are calculated according to the horizontal azimuth and vertical pitch angle of the laser beam corresponding to each point cloud, and the coordinates ( u _i , vi _i ) of each point cloud on the laser radar pixel matrix are calculated according to the actual number of lines and the actual horizontal cumulative number of steps of the laser beam corresponding to each point cloud; If the laser radar is a dual-prism semi-solid laser radar, then according to the laser radar Centrifugal inclination function and The laser deflection angle function calculates the horizontal azimuth and vertical pitch angle of the laser beam corresponding to each point cloud, and calculates the actual number of lines and the actual horizontal cumulative number of steps of the laser beam corresponding to each point cloud according to the horizontal azimuth and vertical pitch angle of the laser beam corresponding to each point cloud. The coordinates ( u _i , vi i ) of each point cloud on the laser radar pixel matrix are calculated according to the actual number of lines and the actual horizontal cumulative number of steps of the laser beam corresponding to each point cloud _; Wherein, the target size of the laser radar pixel matrix is W × H , where W and H are positive integers; if the laser radar is a solid-state laser radar, the coordinates of each point cloud on the preset laser radar pixel matrix are calculated based on the horizontal azimuth angle and vertical pitch angle of the laser beam corresponding to each point cloud, including: calculating the coordinates of each point cloud on the laser radar pixel matrix according to the following formula: , Wherein θ _i represents the horizontal azimuth angle of the laser beam corresponding to the i - th point cloud, γ _i represents the vertical pitch angle of the laser beam corresponding to the i - th point cloud, Ang _Horizontal is the horizontal azimuth angle of the laser radar, and Ang _Vertical is the vertical pitch angle of the laser radar; If the laser radar is a mechanical laser radar or a semi-solid laser radar or a dual-prism semi-solid laser radar, the coordinates of each point cloud on the laser radar pixel matrix are calculated based on the actual number of lines of the laser beam corresponding to each point cloud and the actual horizontal cumulative number of steps, including: calculating the coordinates of each point cloud on the laser radar pixel matrix according to the following formula: , Wherein o _i represents the actual horizontal cumulative number of steps of the laser beam corresponding to the i - th point cloud, qi _represents the actual number of lines of the laser beam corresponding to the i - th point cloud, O is the total number of horizontal rotation or vibration steps of the laser radar, and Q is the total number of laser beam lines of the laser radar. 2. The ordered reconstruction method according to claim 1, wherein the actual number of lines and the actual horizontal cumulative number of steps of the laser beam corresponding to the point cloud are determined by the following formula: , Among them, θi represents the horizontal azimuth angle of the laser beam corresponding to the i - th point cloud, _γi represents the vertical pitch angle of _the laser beam corresponding to the i - th point cloud, It means that when θ = θ _i, the function The value of It means that when γ = γ _i, the function The value of represents the inverse function of the distribution function In ( o ) _of the horizontal azimuth angle of the laser beam of the laser radar, Represents the inverse function of the distribution function L _m ( q ) of the vertical pitch angle of the laser beam of the laser radar. 3. The ordered reconstruction method according to claim 2 is characterized in that the laser beam of the laser radar is uniformly distributed in M segments in the vertical viewing angle and uniformly distributed in N segments in the horizontal viewing angle, wherein M and N are both positive integers; the distribution function In ( o ₎ of the horizontal azimuth angle of the laser beam of the laser radar is expressed as: , _Wherein θn represents the horizontal azimuth angle of the nth laser beam in the horizontal viewing angle, o represents the horizontal cumulative number of steps of the laser beam, o _{n -1} represents the starting horizontal cumulative number of steps of the nth laser beam in the horizontal viewing angle, o _n represents the ending horizontal cumulative number of steps of the nth laser beam in the horizontal viewing angle, a _n , b _n and c _n represent the quadratic term coefficient, linear term coefficient and constant term of the quadratic fitting curve of the horizontal azimuth angle of the nth laser beam in the horizontal viewing angle, respectively; The distribution function L _m ( q ) of the vertical pitch angle of the laser beam of the laser radar is expressed as: , Wherein, γ _m represents the vertical pitch angle of the mth laser beam within the vertical viewing angle, q represents the number of laser beam lines, q _{m -1} represents the starting line number of the mth laser beam within the vertical viewing angle, q _m represents the ending line number of the mth laser beam within the vertical viewing angle, K _m and B _m respectively represent the slope and intercept of the linear fitting curve of the vertical pitch angle of the mth laser beam within the vertical viewing angle. 4. The ordered reconstruction method according to claim 2 or 3, characterized in that if the laser radar is a dual-prism semi-solid laser radar, the horizontal azimuth angle and vertical pitch angle of the laser beam corresponding to the point cloud are determined by the following formula: , in Indicates the laser radar Centrifugal inclination function, Indicates the laser radar Laser deflection _angle function, β1 and β2 are the refraction angles of the double prisms of the laser radar, ω1 and ω2 are the rotation _angular velocities of _the double prisms of the laser radar, and t _is the rotation time of the double prisms of the laser radar. 5. The ordered reconstruction method as described in claim 1 is characterized in that W is greater than the theoretical value of the width of the pixel plane of the laser radar, and H is greater than the theoretical value of the height of the pixel plane of the laser radar. 6. The ordered reconstruction method according to claim 1, further comprising: Obtain an index matrix P2T of the original point cloud set converted to a sensor pixel coordinate set T {( u , v )} of the original point cloud set, wherein the sensor pixel coordinate set T {( u , v )} of the original point cloud set is composed of the coordinates ( ui , vi ) of each point cloud in the original point cloud set on the _laser radar pixel matrix _; Obtain an inverse index matrix X2P of the original point cloud set converted to a target expression form X, wherein the target expression form X includes but is not limited to voxelization of the point cloud and projection compression of the point cloud in a bird's-eye view or a front view; The original point cloud set in the target expression form X is transformed according to the inverse index matrix X2P, and then transformed according to the index matrix P2T to obtain the sensor pixel coordinate set T' {( u , v )} of the original point cloud set in the target expression form X. 7. The ordered reconstruction method according to claim 1, further comprising: According to the sensor pixel coordinate set T {( u , v )} of the original point cloud set, for any non-empty pixel ( ui , vi ), obtain its corresponding point cloud pi _{, and} obtain the point cloud set corresponding to the non-empty pixels in the neighbor area bounding box with the non-empty pixel ( ui _, vi ) as the center _and with a preset target size _as the neighbor _point set PNi ₌ { pk , k =1,2..., Np } of the point cloud pi , where _pk represents the point _cloud corresponding to the kth non- _empty pixel in the neighbor area bounding box, _Np represents the total number of non-empty pixels in the neighbor area bounding box , and the sensor pixel coordinate set T {( u , v )} of the original point cloud set is composed of the coordinates ( ui _, vi ) of each point cloud in the original point cloud set on the laser radar pixel matrix _; The directed edges from each point cloud in the neighbor point set PN _i to the point _cloud pi constitute a directed edge set ; With point cloud p _i and its neighbor point set PN _i as vertices and directed edge set E _i as edges, a local directed graph with point cloud p _i as key point is obtained. ; The sensor pixel coordinate set T {( u , v )} of the original point cloud set is traversed to obtain a local directed graph with the point cloud corresponding to each non-empty pixel as a key point, thereby realizing the transformation from the original point cloud set to the directed graph expression. 8. A computer-readable storage medium, characterized in that a program is stored on the medium, and the program can be executed by a processor to implement the ordered reconstruction method according to any one of claims 1 to 7.