JP2015118441A - Data processing apparatus, data processing method and data processing program - Google Patents

Abstract

PROBLEM TO BE SOLVED: To reduce dependency upon an initial position by reducing a processing amount for matching directions and positions between objects indicated by two data items, respectively.SOLUTION: A main component calculation part calculates a representative of normal lines in an area where the normal lines are distributed with a higher density than a predetermined density, as a first normal line main component among normal lines on a surface of a first object indicated by first data. A handling part determines a second normal line main component corresponding to the first normal line main component on the basis of a degree of approximation with the first normal line main component from a second normal line main component as a representative of normal lines in an area where the normal lines are distributed with the higher density than the predetermined density, among normal lines on a surface of a second object indicated by second data. A relative direction calculation part calculates a relative direction between a direction of the first normal line main component and a direction of the second normal line main component.

Description

  The present invention relates to a data processing device, a data processing method, and a data processing program.

  A technique for estimating a position in an operating environment (for example, self-position estimation with respect to the environment) and a technique for grasping information about the surrounding environment (for example, construction of a search environment map) have been proposed in the past, and various fields (for example, movement) Application to robot motion control) has been attempted. As a surrounding environment, a three-dimensional ranging distance sensor (3DLRF) that acquires shape data indicating the shape of the surface of various objects located in the surroundings may be used. 3DLRF acquires point cloud data (point cloud information) consisting of sample points obtained by sampling the surface of an object at a predetermined spatial interval (accuracy). For example, there is a high-precision space interval of several mm or less. In self-localization and mapping (mapping), a process for matching the direction and position so that two point groups whose relative positions and postures (relative position and posture) are unknown are overlapped (matching: position) Adjustment) may be required.

  For example, the self-position estimation apparatus described in Patent Document 1 uses an ICP (Iterative Closest Point) method when aligning two point groups. The ICP method is an algorithm for minimizing the distance between two point groups by iterative calculation, and has the versatility that it can be executed even for point groups showing complicated shapes.

JP 2011-8320 A

However, since the ICP method is an iterative solution method, a long time is required for the calculation process. For this reason, it is not practical to apply to applications that require real-time processing, for example, control of the operation of a mobile robot. Even when used for aligning point groups acquired from an object including many surfaces with high flatness, the processing time is not necessarily shortened. Such a point cloud often appears especially in an artificial environment such as a room.
Further, the processing result by the ICP method is highly dependent on the initial position of each sample point constituting the point group, and tends to fall into a local solution. That is, it means that the range of the initial position where the expected alignment result is obtained is narrow. In this regard, it may be possible to adopt a RANSAC (Random Sample Consensus) method to set the initial positions of the respective sample points at random, but the calculation time further increases.

  The present invention has been made in view of the above points, and can reduce the amount of processing for matching the direction and position between the objects indicated by the two data, and can reduce the dependency on the initial position. A data processing apparatus, a data processing method, and a data processing program are provided.

(1) The present invention has been made to solve the above-described problems, and one aspect of the present invention is more than a predetermined density among the normals of the surface of the first object indicated by the first data. Among a normal component calculation unit that calculates a representative of normal lines in a region distributed at high density as a first normal line main component, and a normal line of a surface of the second object indicated by the second data Based on the degree of approximation to the first normal principal component from the second normal principal component that is representative of the normal of the region that is distributed at a higher density than the density, the first normal principal A corresponding part that defines a second normal principal component corresponding to the component, and a relative direction for calculating a relative direction between the direction of the first normal principal component and the direction of the second normal principal component A direction calculation unit and a data processing device provided.

(2) Another aspect of the present invention is the above-described data processing device, wherein the principal component calculation unit is based on first point cloud data including a plurality of points representing the shape of the first object. Of the normals of the surface of the first object, the center of gravity of the normal in a region distributed at a density higher than a predetermined density is calculated as the first normal normal component.

(3) Another aspect of the present invention is the above-described data processing device, wherein the principal component calculation unit calculates a normal between the surfaces of the first object and a normal between the surfaces of the first object. Are grouped into a plurality of normal lines based on the distance of the first normal line, and the first normal principal component is calculated for each normal line belonging to each group.

(4) Another aspect of the present invention is the data processing device described above, wherein the principal component calculation unit is a normal having a depth from the origin to the surface of the first object as a magnitude. Among the first depth normals, a representative of the depth normal distributed at a density higher than a predetermined density is calculated as a first wall surface main component, and the corresponding portion is the second depth. Of the second normal with depth, which is the normal having the depth from the origin to the surface of the object as a magnitude, the normal with depth of the region distributed at a higher density than the predetermined density A second wall surface principal component corresponding to the first wall surface principal component is determined based on a degree of approximation with the first wall surface principal component from the second wall surface principal component that is representative of the first wall surface principal component. The first object based on a difference between a wall surface principal component and a second wall surface principal component corresponding to the first wall surface principal component. And a relative translational position calculating unit for calculating a relative position between said second object.

(5) Another aspect of the present invention is the above-described data processing device, wherein the principal component calculation unit is based on first point cloud data including a plurality of points representing the shape of the first object. Of the normals with depth of the surface of the first object, the center of gravity of the normal with depth in a region distributed at a density higher than a predetermined density is calculated as the first wall surface main component.

(6) Another aspect of the present invention is the above-described data processing device, wherein the principal component calculation unit calculates a normal line with a depth of the surface of the first object on the surface of the first object. Based on the distance between the normals with depth, it classify | categorizes into the group of several normal with depth, and calculates the said 1st wall surface main component for every normal with depth which belongs to each group.

(7) According to another aspect of the present invention, in the data processing method, among the normals of the surface of the first object indicated by the first data, the normals of a region distributed at a higher density than a predetermined density Of the principal component calculation process for calculating the representative of the first normal principal component and the normal of the surface of the second object indicated by the second data at a density higher than a predetermined density The second normal principal component corresponding to the first normal principal component based on the degree of approximation with the first normal principal component from the second normal principal component that is representative of the normal And a relative direction calculation step of calculating a relative direction between the direction of the first normal principal component and the direction of the second normal principal component. is there.

(8) According to another aspect of the present invention, the computer of the data processing apparatus has a region that is distributed at a higher density than a predetermined density among normals of the surface of the first object indicated by the first data. The principal component calculation procedure for calculating the representative of the normal as the first normal principal component, and the normal of the surface of the second object indicated by the second data are distributed at a higher density than the predetermined density. The second normal principal corresponding to the first normal principal component based on the degree of approximation with the first normal principal component from the second normal principal component that is representative of the region normal Data processing for executing a corresponding procedure for determining a component and a relative direction calculation procedure for calculating a relative direction between the direction of the first normal principal component and the direction of the second normal principal component It is a program.

  According to the present invention, it is possible to reduce the amount of processing for matching the direction and position between objects indicated by two data, and it is possible to reduce the dependency on the initial position.

It is a block diagram which shows the structure of the data processor which concerns on the 1st Embodiment of this invention. It is a figure which shows an example of point cloud data. An example of a normal vector is shown. It is a flowchart which shows the data processing which concerns on this embodiment. It is a block diagram which shows the structure of the data processor which concerns on the 2nd Embodiment of this invention. An example of a normal vector with depth information is shown. It is a flowchart which shows the data processing which concerns on this embodiment. It is a figure which shows an example of a model point group. It is a figure which shows the initial position dependence of an error. It is a figure which shows the initial position dependence of processing time. It is a photograph which shows an example of the environment which acquired point cloud data. It is a figure which shows an example of the point cloud data before a process. It is a figure which shows an example of the point cloud data after a process.

(First embodiment)
Hereinafter, embodiments of the present invention will be described with reference to the drawings.
FIG. 1 is a block diagram showing a configuration of a data processing apparatus 1 according to the present embodiment.
The data processing apparatus 1 includes a data input unit 101, a principal component calculation unit 102, a correspondence unit 103, a rotation calculation unit (relative direction calculation unit) 104, a data output unit 105, and a storage unit 11. Each unit is a bus. 12 is connected.

Query point cloud data (first data) is input to the data input unit 101 from the outside of the data processing apparatus 1, for example, 3DLRF. The point group data is data indicating a point group composed of sample points obtained by sampling the shape of a subject (object) included in a predetermined imaging region at a predetermined spatial interval. The point cloud indicated by the input query point cloud data may be referred to as a query point cloud, and the sample points constituting the query point cloud may be referred to as query points. Each sample point indicates the coordinates of one point on the surface of the subject (first object). The data input unit 101 outputs the input query point cloud data to the principal component calculation unit 102. The data input unit 101 is, for example, a data input interface.
The query point cloud data may be point cloud data received from another device, for example, a server device via a communication path such as a LAN (Local Area Network) or the Internet.

The principal component calculation unit 102 sets, for each sample point q _pi constituting the query point cloud data Q input from the data input unit 101, a normal line (normal) indicating a direction perpendicular to the surface of the subject at the sample point. The normal vector q _{ni shown} is calculated. For example, the principal component calculation unit 102 forms a surface that shares a certain target sample point as one of the vertices, and extracts a set of two sample points adjacent to the target sample point.

The principal component calculation unit 102 calculates a normal vector for each surface formed from the set of the sample point of interest and the extracted two sample points, and averages the calculated normal vectors for each surface to obtain the sample of interest. A normal vector q _ni related to the point is calculated. The normal vector q _ni calculated for the sample point of interest in this process is called a vertex normal vector. The calculated normal vector q _ni is a three-dimensional vector. Although the positional information at each sample point q _pi is lost by using the normal vector q _ni , the difference between the rotation and the relative position, which is a relative posture difference (relative posture) between the subject and the model. It is possible to separately handle the translation which is.
The principal component calculation unit 102 normalizes the size of the normal vector q _ni calculated at each sample point q _pi to, for example, 1.

The principal component calculation unit 102 extracts a normal vector q _ni in a portion where the distribution of the normal vector q _ni calculated at each sample point q _pi is distributed at a density higher than a predetermined density.
For example, the principal component calculation unit 102 performs clustering on the distribution of the normal vector q _ni calculated at each sample point q _pi and classifies the distribution into a plurality of clusters (cluster). A representative vector is extracted as a normal component. Thereby, it is possible to extract a normal vector of a portion distributed at a density higher than a predetermined density. When performing the clustering, the principal component calculation unit 102 may use, for example, a group average method that is a method of hierarchical clustering.

  Hierarchical clustering is a method having the following steps (i)-(iv): (i) setting clusters each having one normal vector as a member, (ii) similarity between each cluster Among them, the clusters having the highest similarity are integrated to form one cluster. (Iii) When the number of clusters reaches 1, the process is terminated. Otherwise, the process proceeds to (iv). iv) Calculate the similarity between the cluster formed in (ii) and each of the other clusters, and return to (ii). Hierarchical clustering can be applied even when the number of principal components, that is, the number of clusters is not known, and the similarity between clusters can be calculated regardless of the number of normal vectors belonging to each cluster.

  In the group average method, in this hierarchical clustering, the similarity between normal vectors selected from each of two clusters is calculated for each set of all normal vectors, and the average value of the calculated similarities is calculated as two values. This is a method for determining the similarity between clusters. According to the group average method, a representative (for example, the center of gravity) of each cluster to be finally obtained can be obtained as a normal vector representative. Further, the distribution of normal vectors based on point cloud data indicating artificially constructed subjects such as buildings often forms a clear group concentrated in a specific area in the vector space. Therefore, the distribution of the normal vectors can be modeled by the representative of the normal vectors determined for each region.

The principal component calculation unit 102 excludes clusters in which the number of normal vectors belonging to the cluster is smaller than a predetermined threshold number of normal vectors from the classified clusters. As a result, the normal vector related to the sample point of the outlier, that is, the portion of the sample point showing the shape having a flatness lower than the predetermined flatness is removed, and the normal vector related to the sample point showing the shape having a higher flatness is mainly Extracted into
The principal component calculation unit 102 calculates a representative value for each of a plurality of clusters remaining without being excluded, except for one cluster having the entire normal vector space as its range. The representative value is, for example, the centroid of normal vectors belonging to each cluster. The number of remaining clusters, that is, the number of representative values is represented as N _CQ . In the following description, the center of gravity of the normal vector is referred to as a normal principal component, and calculating the normal principal component for each cluster from the point cloud data may be referred to as normal principal component analysis.

The principal component calculation unit 102 can calculate the similarity s _ab between the two clusters a and b using, for example, Expression (1).

In Equation (1), c _a and c _b indicate the centers of gravity of the clusters a and b, respectively. Each centroid is a three-dimensional vector. || ... || indicates the norm of the vector. Accordingly, the similarity s _ab calculated by the equation (1) indicates a cosine between the centroids c _a and c _b .
The principal component calculation unit 102 can calculate the center of gravity c _ab of one cluster formed by integrating the two clusters a and b using, for example, Expression (2).

In Equation (2), n _a and n _b indicate the numbers of normal vectors belonging to the clusters a and b, respectively. Therefore, the centroid c _ab calculated by the equation (2) is obtained by weighting the centroids c _a and c _b of the clusters a and b by the numbers n _a and n _b of the normal vectors belonging to the clusters a and b, respectively. It is a weighted average.
The principal component calculation unit 102 generates normal principal component point cloud data including the calculated representative vector (for example, centroid) for each cluster as a normal principal component, and the generated normal principal component point cloud data is associated with the corresponding component 103. Output to. Therefore, normal principal component point cloud data is formed from N _CQ three-dimensional vectors. Since the processing target related to the alignment is limited to N _CQ normal principal components, the processing amount is significantly reduced.

Corresponding unit 103 includes normal principal components represented by normal principal component point cloud data (based on query point cloud) input from principal component calculating unit 102 and normals based on model point cloud. Correlation (pairing) with any of the normal principal components indicated by the principal component point cloud data is performed.
The model point group is a point group composed of sample points obtained by sampling the shape of a target (model, second object) to be aligned at a predetermined spatial interval. Data indicating the model point cloud may be referred to as model point cloud data (second point cloud data). The normal principal component point cloud data based on the model point cloud is, for example, data formed from the centroid calculated for each cluster by performing the normal principal component analysis described above on the model point cloud data.

  The normal principal component point cloud data based on the model point cloud may be stored in advance in the storage unit 11 and read from the storage unit 11 or may be input from the principal component calculation unit 102 in advance. Good. The normal principal component point cloud data based on the model point cloud may be generated from model point cloud data indicating the shape of the target generated using CAD (Computer Aided Design) technology.

Based on the degree of approximation with the normal principal component c _mj indicated by the normal principal component point cloud data, the correspondence unit 103 sets the normal principal component c _qi indicated by the normal principal component point cloud data based on the query point cloud. A normal principal component _cmj corresponding to each is determined.
Corresponding unit 103 selects, for example, normal principal component c _mj corresponding to normal principal component c _qi using equation (3).

In Expression (3), f _(i) indicates an index j corresponding to the index i for identifying the normal principal component c _qi . j represents an index for identifying the normal principal component _cmj . That is, f _(i) indicates the correspondence between the normal principal component c _qi and the normal principal component c _mj . A set of each normal principal component c _qi and the corresponding normal principal component c _mj is called a pair. N _CM indicates the number of normal principal components _cmj indicated by the normal principal component point cloud data. arg max ... indicates that j that maximizes... is given. Further, each normal principal component is normalized to 1, and Equation (3) shows that the normal principal component c _mj having the largest inner product with the normal principal component c _qi , that is, the normal principal component c the smallest normal main component _{c mj} is the angle between _qi, normal main component _{c mj} that best approximates the normal main component _{c qi} in other words is selected. Corresponding unit 103 performs this selection for each of N _CQ normal principal components c _qi .
The correspondence unit 103 generates normal principal component correspondence data indicating a correspondence relationship between the normal principal component c _qi and the normal principal component c _mj, and the generated normal principal component correspondence data, model point group, and query point group The normal principal component point cloud data based on each is output to the rotation calculation unit 104.

The rotation calculation unit 104 receives normal principal component correspondence data from the correspondence unit 103, normal principal component data based on the query point group, and the model point group. The rotation calculation unit 104 refers to the normal principal component correspondence data and calculates the rotation matrix R using the normal principal component data based on the query point group and the normal principal component data based on the model point group. The rotation matrix R is a relative direction of the normal principal component c _mj based on the model point group corresponding to the normal principal component c _qi on the basis of the direction indicated by the normal principal component c _qi based on the query point group. (Also referred to as a relative posture or rotation error) is a matrix that indicates rotational transformation in a direction that is integrated between pairs of normal principal components. Therefore, by calculating the rotation matrix R, it is possible to calculate the relative direction of the normal principal component _cmj with respect to the direction of the normal principal component _cqi . The rotation matrix R is used when approximating the relative attitude between the model point group and the direction of the object indicated by the query point group and compensating for the relative attitude.

  The rotation calculation unit 104 uses, for example, a least square method when calculating the rotation matrix R. A method for calculating the rotation matrix R by the least square method is described in, for example, the following document: S. Arun, T .; S. Huang, and S.H. D. Blostein, “Least-Squares Fitting of Two 3D Point Sets”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-9, No. 5, pp. 698-700, SEPMTEMBER 1987.

In the least square method, the rotation calculation unit 104 multiplies the normal principal component c _mj based on the model point cloud and the normal principal component c _qi based on the query point cloud corresponding to the normal principal component by the rotation matrix R. An error function between the normal component Rc _qi after the rotation correction is calculated. The error function is, for example, the Frobenius norm of the difference vector from the normal principal component _cmj to the rotation-corrected normal principal component Rc _qi . The error function is not limited to this, and any function (for example, the Euclidean norm of the difference vector) may be used as long as it indicates the magnitude of the error between the normal principal component _cmj and the rotation-corrected normal principal component Rc _qi. (Euclean norm)).

  Then, the rotation calculation unit 104 calculates, for example, a rotation matrix R that minimizes the error function so as to reduce the calculated error function. The rotation matrix R is a 3 × 3 matrix indicating rotation transformation around the origin. The rotation matrix R may be represented by, for example, an azimuth angle in the horizontal plane in the polar coordinate system and an elevation angle from the horizontal plane, or a rotation angle around each coordinate axis in the orthogonal coordinate system (for example, yaw ( yaw) angle, pitch angle, roll angle). As a result, the relative attitude between the query point group and the model point group is determined by the rotation matrix R.

The rotation calculation unit 104 determines the rotation axis and the rotation amount between the normal principal component c _qi based on the query point group and the normal principal component c _mj based on the model point group corresponding to the normal principal component c _qi. May be calculated by averaging between each pair. The rotation axis is an axis parallel to the outer product of the normal principal component c _qi and the normal principal component c _mj corresponding to the normal principal component c _qi . The rotation amount is an angle formed by the normal principal component c _qi and the normal principal component c _mj around the rotation axis. The rotation matrix R can also be determined by the direction of the rotation axis and the amount of rotation.
The rotation calculation unit 104 outputs rotation data indicating the calculated rotation matrix R to the data output unit 105.

The data output unit 105 outputs the rotation data input from the rotation calculation unit 104 to the outside of the data processing apparatus 1. The data input unit 101 is, for example, a data input interface.
In addition, the data output unit 105 indicates the coordinates after rotation obtained by multiplying the coordinates for each sample point indicated by the query point group data input from the data input unit 101 by the rotation matrix R calculated by the rotation calculation unit 104. The rotating coordinate data may be output to the outside of the data processing device 1. Thereby, the coordinate for every sample in which the relative attitude | position between a query point group and a model point group was compensated is obtained.

(Example of point cloud data)
Next, an example of point cloud data will be described.
FIG. 2 is a diagram illustrating an example of point cloud data.
The point cloud data shown in FIG. 2 is formed of sample points obtained by sampling the portion of the building where the corridor and the lobby intersect and the shape of the inner wall in the vicinity. The basic configuration of this shape is that the quadrangular prism has a trapezoidal cross section in the X-Z plane that increases in length (height) in the Z-axis direction in the X-axis direction, and the length (width) in the Y-axis direction. Are formed by being joined at substantially the center of the rectangular parallelepiped longer than the other directions. The X axis, the Y axis, and the Z axis indicate the directions of the coordinate axes that are orthogonal to each other constituting the three-dimensional orthogonal coordinate system.

(Example of normal vector)
FIG. 3 shows an example of a normal vector.
3 (a) shows a normal vector of length 1 for each sample was calculated based on the point cloud data shown in FIG. 2, the distribution of the end point which is formed by placing the origin in the origin O _N . Since the end points of the normal vectors are distributed on a unit sphere having a radius of 1, this normal vector distribution is called a normal sphere. The density of the normal sphere indicates the density of the normal vector distribution. The higher the density, the higher the density of normal vectors, and the lower the density, the lower the density of normal vectors.

FIGS. 3B and 3C show portions of the normal sphere shown in FIG. 3A where the normal vector density is higher than a predetermined density threshold. The density threshold is higher in FIG. 3C than in FIG. FIG. 3C shows that the portion where the density of normal vectors is high is concentrated in a narrow region, particularly six isolated regions c1-c6. This indicates that the surface of the object indicated by the sample point indicated by the point cloud data is mainly directed in a specific direction. As described above, the principal component calculation unit 102 performs clustering on the normal vector for each sample point, and determines the center of gravity as a normal principal component as a representative for each cluster. Approximate the center of gravity of the region where the normal vector density is high. Accordingly, six normal principal components are calculated.
In the present embodiment, by using a normal principal component based on such a normal vector, when calculating a rotation matrix R indicating a rotation transformation centered on the origin, the object indicated by the query point group or the model point group is displayed. The shape of the surface and the relative translation position between those point clouds are discarded. On the other hand, since the information indicating the difference in posture between the objects indicated by each point group is maintained, the rotation matrix R can be obtained with high accuracy. In addition, as described above, the correspondence between the normal principal components between the point groups serving as the basis for calculating the rotation matrix R is an angle between them as an index of the degree of approximation between the normal principal components. Based on. From these things, the amount of calculation at the time of calculating rotation matrix R can be reduced remarkably.

The density of the distribution of the normal vector q _ni depends on the flatness of the shape indicated by the point group. Flatness is the degree to which the shape approximates a plane, that is, the degree of unevenness. As the flatness is higher, the directions of the plurality of normal vectors are aligned in one specific direction, and as the flatness is lower, the directions of the plurality of normal vectors are more randomly distributed. Therefore, the higher the flatness, the higher the distribution density of the normal vector q _ni . This is because when the normal vector is distributed around a certain point, a plane perpendicular to the direction indicated by the normal vector is dominant among the shapes of the subject.

The principal component calculation unit 102, when calculating the normal principal component, replaces the clustering with respect to the normal vector for each sample point, and has an area where the normal vector density is higher than a predetermined density threshold. These normal vectors may be extracted. In that case, the principal component calculation unit 102 calculates a representative (for example, the center of gravity) of the normal vector for each extracted region, and determines the calculated representative as the normal principal component.
The index indicating the density of the normal vector is, for example, the dispersion value _qσi in the normal direction. The dispersion value _{qσi in the} normal direction is a dispersion of normal vectors for each sample point within a predetermined range from the sample point i. Therefore, the smaller the variance value _qσi is, the higher the flatness is, and the larger the variance value _qσi is, the lower the flatness is.

(Data processing flow)
Next, data processing according to the present embodiment will be described.
FIG. 4 is a flowchart showing data processing according to the present embodiment.
(Step S101) The data input unit 101 acquires query point cloud data indicating the shape of the subject. Thereafter, the process proceeds to step S102.
(Step S102) The principal component calculation unit 102 calculates, for each sample point, a normal vector indicating the direction indicating the normal of the surface of the subject indicated by the query point cloud data. Thereafter, the process proceeds to step S103.

(Step S103) The principal component calculation unit 102 performs clustering on the distribution of the normal vector q _ni calculated at each sample point q _pi and classifies the distribution into a plurality of clusters. Determined as an ingredient. Thereby, the representative of the normal vector of the part where the normal vector distribution is distributed at a density higher than the predetermined density is extracted as the normal principal component. Thereafter, the process proceeds to step S104.
(Step S104) The correspondence unit 103 associates each of the normal principal components based on the query point group with one of the normal principal components based on the model point group based on the degree of approximation between the two. Thereafter, the process proceeds to step S105.
(Step S105) The rotation calculation unit 104 represents a rotation matrix indicating a relative direction between the normal principal component based on the query point group and the normal principal component based on the model point group corresponding to the normal principal component. Is calculated. Thereafter, the process shown in FIG.

  In the present embodiment, the generated rotation data indicates, for example, a difference in posture between the posture of the first object indicated by the query point group and the second object indicated by the model point group. If the posture of the first object is known, the posture of the first object can be acquired. Using this rotation data, it can be used for control of the posture of the first object, control of the operation of the robot based on the posture of the first object, control of the posture of other operation objects, and the like.

  As described above, in the present embodiment, of the normals of the surface of the first object indicated by the first data (for example, the query point cloud data), the region is distributed at a higher density than the predetermined density. A representative of the normal is calculated as a first normal principal component (for example, a normal principal component based on a query point group). Further, in the present embodiment, the normals of the area distributed at a higher density than the predetermined density among the normals of the surface of the second object indicated by the second data (for example, model point cloud data). The second corresponding to the first normal principal component from the representative second normal principal component (for example, the principal component based on the model point group) based on the degree of approximation with the first normal principal component. The normal principal component of is determined. In the present embodiment, a relative direction (for example, a rotation matrix) between the direction of the first normal principal component and the direction of the second normal principal component is calculated.

Accordingly, the relative relationship between the direction of the first normal principal component representing the surface normal of the first object and the direction of the second normal principal component representing the surface normal of the second object. The amount of processing is significantly reduced because the specific direction is directly calculated.
In addition, when the first normal principal component and the corresponding second normal principal component are used to match the direction of the first object and the direction of the second object, the surface of the first object Stable processing can be realized even if some of the regions are sparse or have high curvature.

(Second Embodiment)
Next, a second embodiment of the present invention will be described. About the same structure as embodiment mentioned above, the same code | symbol is attached | subjected and description is used.
Hereinafter, embodiments of the present invention will be described with reference to the drawings.
FIG. 5 is a block diagram showing a configuration of the data processing apparatus 2 according to the present embodiment.
The data processing device 2 includes a principal component calculation unit 202 and a correspondence unit 203 instead of the principal component calculation unit 102 and the correspondence unit 103 in the data processing device 1 (FIG. 1), and further includes a relative translation position calculation unit 206 and coordinate transformation. The unit 207 is included.

Similar to the principal component calculation unit 102 (FIG. 1), the principal component calculation unit 202 calculates a normal vector for each sample point based on the query point cloud data input from the data input unit 101, and performs clustering. A normal principal component is calculated for each cluster.
The principal component calculation unit 202 calculates the coordinates after rotation by multiplying the coordinates for each sample point indicated by the query point cloud data by the rotation matrix R calculated by the rotation calculation unit 104, and the direction of the object indicated by the query point cloud Is compensated for the relative attitude between the model point cloud and the direction of the object. Instead of multiplying the rotation matrix R, the principal component calculation unit 202 may employ the coordinates after rotation calculated in the process of calculating the rotation matrix R by the rotation calculation unit 104.

  Then, the principal component calculation unit 202 calculates a normal vector for the rotated coordinates for each sample point, and calculates a normal principal component in which the relative posture is compensated for the shape of the object indicated by the query point cloud data. . Thereby, since the relative translation position becomes dominant between the query point group and the model point group, the calculation of the relative translation position, which is originally a six-dimensional process, can be reduced to a three-dimensional process. The amount can be significantly reduced. The 6-dimensional includes a rotation around each coordinate axis in 3 dimensions in addition to the relative translation position in the 3D space.

  The principal component calculation unit 202 calculates the depth for the coordinates after rotation for each sample point. The depth is the distance from the origin to the plane (that is, the wall surface) to which the sample point of interest belongs. Then, the principal component calculation unit 202 multiplies the normal vector calculated for each sample point by the depth calculated for the sample point, and calculates a normal vector with depth information having the depth as a magnitude. . The normal vector with depth information corresponds to a vector of a cosine component in the direction of the normal vector in the coordinate vector indicating the coordinates of the sample point. Therefore, the principal component calculation unit 202 may calculate a normal vector with depth information based on the coordinate vector and the normal vector for each sample point.

The principal component calculation unit 202 represents a normal vector with depth information that represents a portion of the normal vector with depth information calculated for each sample point, the distribution of which is higher than a predetermined density. To extract. In the following description, this representative normal vector with depth information is called a wall surface main component.
Here, the principal component calculation unit 202 can calculate the wall surface principal component by performing the same processing as the normal principal component analysis described above on the normal vector with depth information calculated for each sample point. This processing is particularly called wall surface principal component analysis.

In the wall surface principal component analysis, the principal component calculation unit 202 performs clustering on the normal vector with depth information calculated at each sample point to classify into a plurality of clusters, and the representative vector for each classified cluster is used as the wall surface principal component. May be extracted as Here, the principal component calculation unit 202 may use, for example, a group average method.
The principal component calculation unit 202 may calculate the similarity s (hat) _ab between the two clusters a and b using, for example, Expression (4). Here, the description “(hat)” indicates that a hat symbol (circucumflex) is added immediately above the immediately preceding character. Here, the hat symbol indicates that it relates to the wall surface main component.

In Expression (4), c (hat) _a and c (hat) _b represent representative vectors of the clusters a and b, for example, the center of gravity. δ represents a predetermined minute real number for preventing the similarity s (hat) _ab from diverging. Further, c (hat) _a and c (hat) _b indicate the centers of gravity of the clusters a and b, respectively. Here, the denominator is multiplied by the norm of c (hat) _a -c (hat) _b in order to emphasize the effect of increasing the similarity s (hat) _ab as the distance between the clusters decreases.
In addition, the principal component calculation unit 202 calculates the center of gravity c (hat) _ab of one cluster formed by integrating the two clusters a and b, for example, the wall surface principal in each cluster using Expression (5). The center of gravity _cab of the component can be calculated as a representative vector.

The principal component calculation unit 202 generates wall principal component point group data including the calculated representative vector (for example, the center of gravity) for each cluster, and outputs the generated wall principal component point group data to the corresponding unit 203. Wall principal component point cloud data is formed from N (hat) _CQ three-dimensional vectors. Therefore, by limiting the processing target related to the alignment to N (hat) _CQ wall surface principal components, the processing amount can be significantly reduced.

Corresponding unit 203 includes wall surface principal components indicated by wall surface principal component point data based on the query point cloud input from principal component calculation unit 202 and wall principal component point cloud data based on the model point cloud. The association with any one of the above is performed based on the degree of approximation between the two.
The correspondence unit 203, for example, the wall surface principal component c (hat) indicated by the wall surface principal point cloud data based on the model point cloud corresponding to the wall surface principal component c (hat) _qi indicated by the wall surface principal point cloud data based on the query point cloud. ) _Mj is selected using equation (6).

In Expression (6), g _(i) represents an index j corresponding to the index i for identifying the wall surface principal component c (hat) _qi . j denotes an index for identifying the wall surface principal component c (hat) _mj . That is, g _(i) is the correspondence between the wall surface principal component c (hat) _qi and the wall surface principal component c (hat) _mj , in other words, the wall surface principal component c (hat) _qi and the corresponding wall surface principal component c ( Hat) Indicates a pair with _mj . N (hat) _CM represents the number of wall surface principal components c (hat) _mj indicated by the wall surface principal component cloud data. N (Hat) _CM and N (Hat) _CQ are 3 or an integer larger than 3, respectively.

Therefore, the equation (6) indicates that the wall surface principal component c (hat) _mj having the largest ratio of the inner product with the wall surface principal component c (hat) _qi to the distance between the wall surface principal component c _qi is selected. Show. As a result, the normal principal component c (hat) _{mj that} is closest to the wall surface principal component c (hat) _qi in both depth and direction is selected. The correspondence unit 203 performs this selection for each of the N (hat) _CM wall surface principal components c (hat) _qi .

As shown in Expression (7), the correspondence unit 203 uses the wall surface principal component c (hat) _{mg (i)} based on the model point cloud to the wall surface principal component c (hat) _qi based on the corresponding query point cloud. The difference is calculated as an inter-pair error vector ν _i for each pair related to the wall surface principal component c (hat) _{q i} .

Corresponding unit 203 corresponds to a correspondence between wall surface principal component c (hat) _qi and wall surface principal component c (hat) _mj and an inter-pair error indicating inter-pair error vector ν _i corresponding to wall surface principal component c (hat) _qi. Generate data. The correspondence unit 203 associates the generated inter-pair error data with the wall surface principal point point data based on the model point group, and outputs the data to the relative translation position calculation unit 206.
Note that, as in the case of the correspondence unit 103, the correspondence unit 203 uses the normal principal components indicated by the normal principal component point group data based on the query point group and the normal lines indicated by the normal principal component data based on the model point group. Associate with the principal component.

  The wall surface principal point data based on the model point cloud may be stored in advance in the storage unit 11 and read from the storage unit 11 or may be input from the main component calculation unit 202 in advance. . Further, the wall surface principal point group data based on the model point group may be generated from model point group data indicating the shape of the target generated using CAD (Computer Aided Design) technology.

Relative translation position calculation unit 206 receives paired error data and model wall principal component point group data based on the model point group from correspondence unit 203. The relative translation position calculation unit 206 is based on the inter-pair error vector ν _i indicated by the inter-pair error data and the wall surface principal component c (hat) _{q i} indicated by the wall surface principal point point data based on the corresponding model point group. Then, a translation error vector ε is calculated. The translation error vector ε is a wall surface principal component c (hat) _qi indicated by the wall surface principal component data based on the query point group, and a wall surface principal component c (hat) _mj corresponding to the wall surface principal component c (hat) _qi , It is a three-dimensional vector indicating a relative translation position with respect to a wall surface principal component c (hat) _mj indicated by wall surface principal component data based on the model point group. The translation error vector ε represents a relative translation position in which the relative position (relative translation position) of the wall surface principal component c (hat) _mj based on the position of the wall surface principal component c (hat) _qi is integrated between the pairs. .
The translation error vector ε approximates the relative translation position between the query point group and the model point group. Therefore, the translation error vector ε is used when compensating for the relative translation position between the query point group and the model point group.

The relative translation position calculation unit 206 calculates the translation error vector ε using at least three pair-to-pair error vectors ν _i . This is because there is a difference in posture between the object indicated by the query point group and the object indicated by the model point group, and this difference in posture (that is, the relative posture) is compensated. The relative translation position calculation unit 206 calculates the translation error vector ε using, for example, Expression (8).

In the formula (8), W is the sum of the weighting factors _{w m.} m is an index for identifying each of three different sets of N (hat) _CQ wall surface principal components c _qi . Since there are _three N (hat) _CQ C groups of such wall surface principal components, m represents any integer between 1 and N (hat) _CQ C ₃ . The three wall surface principal components constituting each set are represented as c _qj , c _qk , and c _ql , respectively. Here, j, k, and l are indices for identifying the principal components of the wall surface, and take different values (j ≠ k ≠ l). M _{(hat) CQ} is N _(hat) CQ _{C 3.}
Thus, the wall main component epsilon, the translation error vector epsilon (hat) _m in each set m consisting of three wall main component, by adding the respective multiplied values obtained by multiplying by the weighting factor w _m between pairs m The added value is normalized by the total sum W.
The weighting factor w _m is calculated based on the three wall surface principal components c _qj , c _qk , and c _ql related to the set m, as shown in Expression (9).

That is, the equation (9) is _obtained by calculating the two wall principals for each pair of wall principal components composed of two of the three wall principal components c (hat) _qj , c (hat) _qk , and c (hat) _ql. It shows that the outer product of the components is calculated, the norm of the calculated outer product is multiplied between the pairs, and the multiplied value is calculated as the weighting coefficient w _m .
Translation error vector for each set m of wall main component epsilon (hat) _m, as shown in equation (10), three wall main component c constituting the set m (hat) _{qj, c} (hat) _qk , c (hat) _ql is calculated based on _ql and inter-pair error vectors ν _j , ν _k , ν _l respectively corresponding thereto.

In Expression (10), [...] ⁻¹ represents an inverse matrix of the matrix.
Therefore, the translation error vector ε (hat) _m multiplied by the weighting factor w _m represents the inter-pair error vectors ν _j , ν _k , ν _l and the corresponding wall surface principal components c (hat) _qj , c (hat), respectively. _qk , c (hat) A component obtained by projecting to _ql and further projecting the component in the X-axis direction, Y-axis direction, and Z-axis direction is shown. By thus projecting the inter-pair error vectors ν _j , ν _k , ν _l onto mutually orthogonal components and obtaining the projected components as translation error vectors ε (hats) _m , positioning can be performed with high accuracy. Can do. Further, by taking a weighted average of the translation error vectors ε (hats) _m for every set m of the wall surface principal components with the weighting factor w _m , the difference in relative posture between the pairs can be reduced.
The relative translation position calculation unit 206 outputs translation data indicating the calculated translation error vector ε to the coordinate conversion unit 207.

The coordinate conversion unit 207 includes query point group data from the data input unit 101, rotation data indicating the rotation matrix R from the rotation calculation unit 104, and translation data indicating the translation error vector ε from the relative translation position calculation unit 206. Entered.
The coordinate conversion unit 207 converts the coordinates for each sample point indicated by the query point group data using the rotation matrix R and the translation error vector. Here, the coordinate conversion unit 207 calculates the coordinate after rotation by multiplying the coordinate (vector) for each sample point by the rotation matrix R, adds the translation error vector ε to the calculated coordinate, and converts the coordinate after conversion. Is calculated. A four-row, four-column homogeneous transformation matrix S indicating this calculation is shown in Expression (11).

In Expression (11), 0 is a 3 × 1 vector in which each element value is 0. 1 is the element value of the fourth row and fourth column of the homogeneous transformation matrix S. By calculating the coordinates after conversion in this way, it is possible to align and align the query point group with the model point group as the target position.
Note that the coordinate conversion unit 207 may employ the coordinates after rotation calculated in the process of calculating the rotation matrix R by the rotation calculation unit 104 or the principal component calculation unit 202 instead of multiplying by the rotation matrix R. .
The coordinate conversion unit 207 outputs converted coordinate data indicating the converted coordinates for each sample to the outside of the data processing device 2 via the data output unit 105. The output transformed coordinate data indicates the shape of the first object indicated by the query point group data in which the relative posture and the relative translation position are compensated so as to match the position and posture of the second object. Here, the data output unit 105 may output translation data instead of the converted coordinate data or together with the converted coordinate data, or may output the rotation data generated by the rotation calculation unit 104.

(Example of normal vector with depth information)
FIG. 6 shows an example of a normal vector with depth information.
6 (a) shows the end point of the distribution of the depth information with a normal vector for each calculated sample, which is formed by placing the origin in the origin O _N based on the point cloud data shown in FIG. 2 . The end points of the normal vectors are distributed on a curved surface having a radius of each depth. This distribution of normal vectors is called a normal sphere with depth information. The density of the normal sphere with depth information indicates the density of the distribution of normal vectors with depth information. The higher the density, the higher the density of the normal vector with depth information, and the lower the density, the lower the density of the normal vector with depth information.

FIG. 6B is a plan view obtained by observing the distribution of the normal vector with depth information shown in FIG. 6A in the negative direction of the Z axis. In this plan view, in addition to the distribution of normal vectors with depth information, the point groups shown in FIG.
FIG.6 (c) is the enlarged view to which the A area | region of FIG.6 (b) was expanded.
6B and 6C, there are points P where the distribution of normal vectors with depth information is concentrated at a high density. This point P indicates that a wall surface L having a normal line in the same direction as the position vector indicating the coordinates exists at a position separated by a depth corresponding to the norm of the position vector.
Therefore, clustering is performed on the normal vector with depth information for each sample point to extract a region with a high distribution density, and with the representative of the region calculated as the wall surface principal component, the normal direction and position of the wall surface Information about can be maintained.

(Process flow)
Next, data processing according to the present embodiment will be described.
FIG. 7 is a flowchart showing data processing according to the present embodiment.
The data processing shown in FIG. 7 includes steps S101 to S105 (FIG. 4) and steps S206 to S210. After the processing of steps S101 to S105 is completed, the process proceeds to step S206.
(Step S206) The principal component calculation unit 202 calculates the coordinates after rotation by multiplying the coordinates for each sample point indicated by the query point group data by the rotation matrix R. This compensates the relative posture between the query point group and the model point group. Thereafter, the process proceeds to step S207.
(Step S207) The principal component calculation unit 202 calculates a normal vector for the rotated coordinates for each sample point, and calculates a normal vector with depth information based on the calculated normal vector and the coordinates. Thereafter, the process proceeds to step S208.

(Step S208) The principal component calculation unit 202 performs clustering on the normal vector with depth information calculated at each sample point to classify into a plurality of clusters, and calculates a representative vector for each classified cluster as a wall surface principal component. To do. Thereafter, the process proceeds to step S209.
(Step S209) The correspondence unit 203 associates each of the wall surface principal components based on the query point group with one of the wall surface principal components based on the model point group. Thereafter, the process proceeds to step S210.
(Step S <b> 210) The relative translation position calculation unit 206 determines whether there is a pair of wall surface principal components based on the query point group and an inter-pair miscalculation vector corresponding to each of the wall surface principal components. A translation error vector indicating the relative translation position of is calculated. Thereafter, the process shown in FIG. 7 ends.

The translation data indicating the relative translation position calculated in the present embodiment indicates the position of the second object represented by the query point group based on the position of the first object represented by the model point. By using this translation data, it can be used for control of the position of the first object, control of the operation of the robot based on the position of the first object, control of the position of other operation objects, and the like.
In addition, the translation data can be used for compensation of the position in an electronic apparatus including an acceleration sensor that detects acceleration such as gravitational acceleration. Such an electronic device includes a multi-function mobile phone (so-called smartphone) having a position estimation function for calculating the position of the own device by second-order integration of detected acceleration. In addition, there is a robot having a position calculation function for calculating the position of the own machine based on the operation state (for example, the rotation speed of the motor) of the drive mechanism provided in the own machine.

  The accuracy of the position calculated by this position calculation function generally tends to be low due to accumulation of calculation errors and noise. Therefore, the data processing device 2 generates translation data indicating the relative translation position calculated at a predetermined time interval (for example, 1 minute) based on the query point cloud data obtained by photographing the electronic device. And this position calculation function can employ | adopt the relative translation position which the produced | generated translation data show as an origin of the position of an own machine, and can correct | amend the calculated position sequentially.

(Evaluation experiment)
Next, an evaluation experiment performed to show the effect of this embodiment will be described. Here, (1) initial position dependency evaluation experiment, (2) real-time evaluation experiment, and (3) robustness evaluation experiment, evaluation experiments performed from three different viewpoints will be described. In any evaluation experiment, as a comparison object, it compares with the experimental result by ICP method as a prior art.

First, an initial position dependency evaluation experiment will be described. In the initial position dependency evaluation experiment, the rotation matrix R and the translation error vector ε are calculated according to this embodiment for the query point group, and the error between the target rotation matrix R and the translation error vector ε is an error of the correction amount. Measure as These operations are executed for each of a plurality of predetermined initial positions using a model point group arranged at a fixed position. As the initial position, the rotation matrix R is set at intervals of 1 ° and the translation error vector ε is set at intervals of 0.1 m. However, since this model point group has rotational symmetry in the XY plane, each of the X coordinate, the Z coordinate, the rotation angle (elevation angle) around the Y axis, and the rotation angle (azimuth angle) around the Z axis. The initial position was distributed.
Moreover, it is investigated whether a global solution is obtained about each initial position. If a global solution cannot be obtained, it may fall into a local solution. Whether or not a global solution is obtained is determined based on whether or not the error falls below a predetermined error threshold. As a result, the convergence limit indicating the range of the initial position where a global solution can be derived is also treated as an evaluation value.

FIG. 8 is a diagram illustrating an example of a model point group.
The model point group shown in FIG. 8 is a point group used in the initial position dependency evaluation experiment and the real-time evaluation experiment. This point group is formed by 4.5 million sample points that simulate the indoor shape formed by the inner walls of the building. The simulated shape is formed by crossing two rectangular parallelepipeds whose longitudinal directions are the X direction and Y direction, respectively, at the center. However, Gaussian noise with a standard deviation of 5 cm is superimposed. The space covered by this point group has X, Y, and Z directions, and the lengths in the respective directions are 15 m, 15 m, and 5 m. Maximum density of the point group, i.e. the resolution is 10,000 samples per 1 m ^2.

FIG. 9 is a diagram showing the initial position dependency of the error.
FIG. 9A shows the initial position dependence of the azimuth angle error for each of the present embodiment and the prior art. In FIG. 9A, the vertical axis and the horizontal axis indicate the azimuth angle error and the initial azimuth angle, respectively. ◆ and x indicate the present embodiment and the prior art, respectively. An error threshold value for giving a convergence limit is set to 1 °.
According to this, in the present embodiment, the error in the azimuth angle is very small, generally less than 0.01 °, and does not depend on the initial azimuth angle. However, when the initial azimuth is −89 ° and 89 °, the error is 90 °. Therefore, the convergence limit is 88 °. This phenomenon is due to the fact that the model point cloud has a rotational symmetry of 90 ° (four phases), so that the alignment is performed in the direction rotated by 90 °.
Further, since the error varies greatly depending on whether or not a global solution has been obtained, it is possible to stably determine whether or not the convergence limit has been exceeded.

On the other hand, in the prior art, when the azimuth error is in the range of -9 ° to 9 °, the azimuth error is less than 1 °. In addition, in the range where the initial azimuth angle is −10 ° or less or 10 ° or more, the azimuth angle error increases rapidly to 10 ° or more, and the azimuth angle error increases as the absolute value of the initial azimuth angle increases. To increase. Thus, the convergence limit at which a global solution can be obtained is 9 °.
In general, the upper limit of the convergence limit of the alignment of the point group having n phase symmetry is 360 / n degrees (90 degrees in this example). When each convergence limit is normalized with this upper limit, the normalized convergence limit is 0.98 in the present embodiment and 0.10 in the prior art. This result shows that the present embodiment can achieve highly accurate alignment over a wider range.

FIG. 9B shows the initial position dependence of the elevation angle error for each of the present embodiment and the prior art. In FIG. 9B, the vertical axis and the horizontal axis represent the elevation angle error and the initial elevation angle, respectively. According to this, in the present embodiment, the error of the elevation angle is extremely small, generally less than 0.01 °, and does not depend on the initial elevation angle. However, when the initial elevation angle is −89 ° and 89 °, the error is 90 °. Thus, the convergence limit at which a global solution can be obtained is 88 °.
On the other hand, in the prior art, the elevation angle error is less than 1 ° when the elevation angle error is in the range of −6 ° to 6 °. In addition, when the initial elevation angle is −7 ° or less or 7 ° or more, the elevation angle error tends to increase as the absolute value of the initial elevation angle increases. Thus, the convergence limit at which a global solution can be obtained is 6 °.

FIG. 9C shows the initial position dependency of the X-coordinate error for each of the present embodiment and the prior art. In FIG. 9C, the vertical axis and the horizontal axis represent the X coordinate error and the initial X coordinate, respectively. An error threshold value for giving a convergence limit is set to 0.1 m.
According to this, in this embodiment, the error of the X coordinate is very small, generally less than 0.001 m, and does not depend on the initial X coordinate. However, when the initial X coordinate is −5.0 m and 5.0 m, the error is 3.3 m. Therefore, the convergence limit is 4.9 m.
On the other hand, in the prior art, when the X coordinate error is in the range of −1.6 m to 1.6 m, the X coordinate error is generally less than 0.1 m. In the range where the initial X coordinate error is -1.7 m or less or 1.7 m or more, the X coordinate error exceeds 0.1 m, and the X coordinate error increases as the initial X coordinate absolute value increases. . Therefore, the convergence limit for obtaining a global solution is 1.6 m.

FIG. 9D shows the initial position dependency of the Z-coordinate error for each of the present embodiment and the prior art. In FIG. 9D, the vertical axis and the horizontal axis represent the Z coordinate error and the initial Z coordinate, respectively. According to this, in this embodiment, the error of the Z coordinate is very small, generally less than 0.001 m, and does not depend on the Z coordinate. However, when the initial Z coordinate is −5.0 m and 5.0 m, the error is 3.3 m. Therefore, the convergence limit is 4.9 m.
On the other hand, in the prior art, when the Z coordinate error is in the range of −1.8 m to 1.8 m, the Z coordinate error is less than 0.2 m. Further, in the range where the initial Z coordinate error is -1.9 m or less or 1.9 m or more, the Z coordinate error exceeds 0.1 m, and the Z coordinate error increases as the initial Z coordinate absolute value increases. . Therefore, the convergence limit for obtaining a global solution is 1.8 m.
As described above, according to the initial position dependency evaluation experiment, according to the present embodiment, it is possible to align the query point group with high accuracy for each initial position, and to obtain the global solution. It is shown that the range of is widened.

  Next, a real time evaluation experiment will be described. Here, the real-time property is a concept that can include processing time stability according to the difference in the high-speed processing and the initial position. In the real-time evaluation experiment, the processing time required to align the query point group for each of a plurality of predetermined initial positions was observed for each of the present embodiment and the prior art. However, in setting the initial position, translation error vectors ε distributed at intervals of 0.1 m only in the X direction are set, that is, no rotation is given. Note that the query point group and model point group used in the real-time evaluation experiment are the same as those used in the initial position dependency evaluation experiment.

FIG. 10 is a diagram illustrating the initial position dependency of the processing time.
The ◆ mark and x mark indicate the present embodiment and the conventional technique, respectively, and the ◯ mark indicates the convergence limit. The vertical axis and the horizontal axis indicate the processing time and the initial X coordinate, respectively.
In this embodiment, the processing time is 0.524-0.537 seconds, which is much shorter than the conventional tens of seconds unit, and does not depend on the initial X coordinate. This is because in the present embodiment, the rotation matrix R and the translation error vector ε are directly calculated without relying on iterative processing as in the prior art. On the other hand, in the prior art, the processing time is between 9 seconds and 111 seconds, and the processing time becomes longer as the initial X coordinate becomes larger.

Next, a robustness evaluation experiment will be described. In the robustness evaluation experiment, it is verified whether or not alignment can be performed effectively even when a point cloud acquired in a real environment is used.
This is because the point group acquired in the actual environment includes a curved surface with some points sparse and a curved surface with a large curvature, and the accuracy may decrease.
Here, a query point group before processing is generated by giving rotation and translation to the acquired point group, and the acquired point group is used as a model point group as it is. Then, the query point group after processing according to the present embodiment is compared with the position of the model point group.

FIG. 11 is a photograph showing an example of an environment in which point cloud data is acquired.
FIG. 11 shows a corridor that is an interior of a building, and its basic configuration is a rectangular parallelepiped whose length in one direction is longer than the length in the other direction. However, the side of the rectangular parallelepiped is open everywhere, and is equipped with furniture such as desks, chairs, and waste bins. As a specific configuration, there are parts with sparse sample points and parts with large curvature. . 11 (a) and 11 (b), the viewpoints taken from each other are different.

FIG. 12 is a diagram illustrating an example of point cloud data before processing.
12A and 12B are a plan view and a perspective view of point cloud data acquired in the environment shown in FIG. The lightly displayed portion indicates a query point group before processing, and the darkly displayed portion indicates a model point group. Between the query point group and the model point group before processing, rotation and relative translation are given in the XY plane.
FIG. 12C shows the distribution of the normal vector with depth information calculated for each of the query point group and the model point group before processing shown in FIGS. 12A and 12B. The lightly displayed portion indicates the distribution of the normal vector with depth information related to the query point group before processing, and the darkly displayed portion indicates the distribution of the normal vector with depth information related to the model point group. In each of these distributions, a region where the distribution of normal vectors with depth information is dense is concentrated at several points according to the plane included in the imaging region. This indicates that the distribution of the normal vector with depth information can be represented by the calculated wall surface principal component.

FIG. 13 is a diagram illustrating an example of point cloud data after processing.
FIGS. 13A and 13B are a plan view and a perspective view of point group data, respectively. The lightly displayed portion indicates the query point group after processing, and the darkly displayed portion indicates the model point group. FIG. 13 shows that both point groups overlap each other. This result shows that in the present embodiment, even a point group acquired in a real environment including a part of which the points are sparse or a part of which the curvature is large can be aligned with a certain accuracy. In addition, not only inside the building but also point cloud data acquired outdoors, if it is an environment that partially includes a plane, such as a building or other installations, the alignment should be performed in the same way Can do.
On the other hand, in the ICP method of the prior art, since the minimum solution of the sum of errors with each nearest point is given for all sample points, it is theoretically difficult to superimpose such sparse point groups.

  As described above, in the present embodiment, the first depth that is a normal having the depth from the origin to the surface of the first object indicated by the first data (for example, query point cloud data) as a magnitude. Among the appended normals (for example, the depth-normal vectors based on the query points), the representative of the depth-normals distributed at a higher density than the predetermined density is represented by the first wall principal component (for example, Calculated as wall surface principal component based on query points). In the present embodiment, the second depth-added method that is a normal having the depth from the origin to the surface of the second object indicated by the second data (for example, model point cloud data) as a magnitude. Among the lines, from a second wall principal component (for example, a wall principal component based on a model point) that is representative of a normal with depth in a region that is distributed at a density higher than a predetermined density, the first A second wall surface main component corresponding to the first wall surface main component is determined based on a degree of approximation with the wall surface main component. In the present embodiment, the first wall surface principal component and the first wall surface principal component and the second wall surface principal component corresponding to the first wall surface principal component are used to determine the first A relative position (for example, a translation error vector) between the object and the second object is calculated.

  Thus, by using the first wall surface main component representing the depth normal of the surface of the first object and the second wall main component representing the depth normal of the surface of the first object. When aligning the position of the first object and the position of the second object, it is possible to realize stable processing even if the surface of the first object includes a sparse region or a region with a high curvature. it can. Further, since the relative position between the first wall surface principal component and the corresponding second wall surface principal component is directly calculated without performing the iterative processing, the processing amount can be significantly reduced.

  In the above-described embodiment, the case where point cloud data is used as data indicating the shape of an object has been described as an example. However, the present invention is not limited to this. Any data may be used as long as the data indicates the shape of the object. For example, instead of point cloud data, a plane image showing a two-dimensional shape of an object and a depth image (for example, a depth map) showing the distance or depth from the viewpoint (origin) to each point on the surface of the object A pair may be used.

Note that a part of the data processing apparatuses 1 and 2 in the above-described embodiment, for example, the principal component calculation units 102 and 202, the corresponding units 103 and 203, the rotation calculation unit 104, the relative translation position calculation unit 206, and the coordinate conversion unit 207. May be realized by a computer. In that case, the program for realizing the control function may be recorded on a computer-readable recording medium, and the program recorded on the recording medium may be read by the computer system and executed. Here, the “computer system” is a computer system built in the data processing apparatuses 1 and 2 and includes an OS and hardware such as peripheral devices. The “computer-readable recording medium” refers to a storage device such as a flexible medium, a magneto-optical disk, a portable medium such as a ROM and a CD-ROM, and a hard disk incorporated in a computer system. Furthermore, the “computer-readable recording medium” is a medium that dynamically holds a program for a short time, such as a communication line when transmitting a program via a network such as the Internet or a communication line such as a telephone line, In this case, a volatile memory inside a computer system that serves as a server or a client may be included that holds a program for a certain period of time. The program may be a program for realizing a part of the functions described above, and may be a program capable of realizing the functions described above in combination with a program already recorded in a computer system.
Moreover, you may implement | achieve part or all of the data processing apparatus in embodiment mentioned above as integrated circuits, such as LSI (Large Scale Integration). Each functional block of the data processing devices 1 and 2 may be individually made into a processor, or a part or all of them may be integrated into a processor. Further, the method of circuit integration is not limited to LSI, and may be realized by a dedicated circuit or a general-purpose processor. In addition, when an integrated circuit technology that replaces LSI appears due to the advancement of semiconductor technology, an integrated circuit based on the technology may be used.

  As described above, the embodiment of the present invention has been described in detail with reference to the drawings. However, the specific configuration is not limited to the above, and various design changes and the like can be made without departing from the scope of the present invention. It is possible to

DESCRIPTION OF SYMBOLS 1, 2 ... Data processing apparatus, 101 ... Data input part, 102, 202 ... Main component calculation part,
103, 203 ... corresponding unit, 104 ... rotation calculation unit, 105 ... data output unit,
DESCRIPTION OF SYMBOLS 11 ... Memory | storage part, 206 ... Relative translation position calculation part, 207 ... Coordinate conversion part

Claims (8)

Principal component calculation for calculating, as a first normal principal component, a normal of a region distributed at a density higher than a predetermined density among the normals of the surface of the first object indicated by the first data And
Among the normals of the surface of the second object indicated by the second data, the first normal principal component that is representative of the normals of the region that is distributed at a density higher than a predetermined density is used. A corresponding portion that defines a second normal principal component corresponding to the first normal principal component based on the degree of approximation to the normal principal component of
A relative direction calculation unit that calculates a relative direction between the direction of the first normal principal component and the direction of the second normal principal component;
A data processing apparatus provided.   The principal component calculation unit is higher than a predetermined density among the normals of the surface of the first object based on first point cloud data composed of a plurality of points representing the shape of the first object. The data processing apparatus according to claim 1, wherein a center of gravity of a normal in an area distributed by density is calculated as the first normal principal component.   The principal component calculation unit classifies the normals of the surface of the first object into groups of a plurality of normals based on a distance between normals of the surface of the first object, and a method belonging to each group The data processing apparatus according to claim 2, wherein the first normal principal component is calculated for each line. The principal component calculation unit has a higher density than a predetermined density among the first normal lines with a depth that is a normal line having a depth from the origin to the surface of the first object as a magnitude. A representative of the distributed normal with depth is calculated as the first wall principal component,
The corresponding portion is distributed at a higher density than a predetermined density among the second normal lines with a depth that is a normal line having a depth from the origin to the surface of the second object as a magnitude. A second wall principal corresponding to the first wall principal component based on a degree of approximation with the first wall principal component from a second wall principal component that is representative of a depth normal of a region that is present Define the ingredients,
A relative position between the first object and the second object based on a difference between the first wall surface principal component and a second wall surface principal component corresponding to the first wall surface principal component. A relative translation position calculation unit for calculating
The data processing device according to claim 1, further comprising:   The principal component calculation unit has a predetermined density among normals with depth of the surface of the first object based on first point cloud data including a plurality of points representing the shape of the first object. The data processing apparatus according to claim 4, wherein the center of gravity of a normal line with depth in a region distributed at a higher density is calculated as the first wall surface main component.   The principal component calculation unit determines a normal with depth of the surface of the first object based on a distance between the normals with depth of the surface of the first object. The data processing apparatus according to claim 5, wherein the first wall surface principal component is calculated for each normal with depth belonging to each group. Principal component calculation for calculating, as a first normal principal component, a normal of a region distributed at a density higher than a predetermined density among the normals of the surface of the first object indicated by the first data Process,
Among the normals of the surface of the second object indicated by the second data, the first normal principal component that is representative of the normals of the region that is distributed at a density higher than a predetermined density is used. A corresponding process for determining a second normal principal component corresponding to the first normal principal component based on the degree of approximation to the normal principal component of
A relative direction calculation step of calculating a relative direction between the direction of the first normal principal component and the direction of the second normal principal component;
A data processing method. In the computer of the data processing device,
Principal component calculation for calculating, as a first normal principal component, a normal of a region distributed at a density higher than a predetermined density among the normals of the surface of the first object indicated by the first data procedure,
Among the normals of the surface of the second object indicated by the second data, the first normal principal component that is representative of the normals of the region that is distributed at a density higher than a predetermined density is used. A corresponding procedure for determining a second normal principal component corresponding to the first normal principal component based on the degree of approximation to the normal principal component of
A relative direction calculation procedure for calculating a relative direction between the direction of the first normal principal component and the direction of the second normal principal component;
Data processing program for executing