JP2016091391A - Corresponding point search device, corresponding point search program, and corresponding point search method - Google Patents

Abstract

PROBLEM TO BE SOLVED: To improve the search accuracy of a correspondence point search device.SOLUTION: The correspondence point search device includes: a storage unit for storing the position information and connection information of each point of three-dimensional models comprising a point group; a sampling point determination unit for determining a plurality of sampling points in the point group about each of the three-dimensional models; a feature amount calculation unit for using the position information and connection information of each sampling point to calculate the feature amount of each sampling point; a similarity calculation unit for calculating the similarity between sampling points with each other of two three-dimensional models on the basis of the feature amount; and a correspondence point determination unit for determining a point corresponding to each sampling point of a first three-dimensional model among sampling points of a second three-dimensional model on the basis of the similarity. The feature amount calculation unit constructs a local depth image in a coordinate system of a virtual camera with a normal direction on a curve surface of a three-dimensional model as a Z direction, and with a gradient direction of an average diffusion length on the curve surface as a Y direction in each sampling point, and calculates a feature amount by using the depth of each pixel included in the local depth image.SELECTED DRAWING: Figure 1

Description

  The present invention relates to search processing for corresponding points between three-dimensional models.

  Conventionally, matching processing of points between three-dimensional models composed of point groups having three-dimensional position information, that is, search processing of corresponding points between two three-dimensional models has been performed.

  In the corresponding point search process of the three-dimensional model, the local feature amount of each point of the point group constituting the three-dimensional model is calculated, and the corresponding point is searched based on the similarity of the feature amount between the points. . Here, as examples of the local feature amount, for example, Spin Image and Local Depth SIFT have been proposed (see, for example, “Non-Patent Document 1”).

  However, the conventionally proposed local feature amount is calculated by using the feature of the shape of the local region, such as the long axis direction of the point group of the local region of the three-dimensional model. There are defects such as position information of each point of the point group constituting the 3D model and local deformation of the 3D model (for example, in the case of a 3D model of a whole human body, If the directions of the arms are different), the search accuracy (matching accuracy) is lowered.

Tal Darom and Yosi Keller, “Scale Invariant Features for 3D Mesh Models”. IEEE Transactions on Image Processing, vol.21, no.5, pp.2758-2769, May 2012.

  The present invention has been made to solve the above-described problems of the prior art, and provides a corresponding point search device, a corresponding point search program, and a corresponding point search method capable of improving the corresponding point search accuracy. The purpose is to provide.

  The present invention relates to a storage unit in which position information and connection information of each point of the first three-dimensional model and the second three-dimensional model composed of point groups are stored, and a point for each of the three-dimensional models. A feature value calculator that calculates a feature value for each sampling point using a sampling point determination unit that determines a plurality of sampling points from the group, and position information and connection information for each sampling point stored in the storage unit A similarity calculation unit that calculates the similarity between the sampling points of the first three-dimensional model and the sampling points of the second three-dimensional model based on the feature amount, and the first based on the similarity A corresponding point determination unit that determines points corresponding to the respective sampling points of the three-dimensional model from the sampling points of the second three-dimensional model. Dimensional model A local depth image is constructed in the virtual camera coordinate system in which the normal direction on the surface is the Z direction and the gradient direction of the average diffusion distance on the curved surface is the Y direction, and the depth of each pixel included in the local depth image is determined. The feature amount is calculated using the feature.

  According to the present invention, it is possible to improve the search accuracy for corresponding points.

It is a functional block diagram which shows embodiment of the corresponding point search apparatus concerning this invention. It is a schematic diagram which shows the example of the sampling point and connection information which are memorize | stored in the same apparatus. It is a schematic diagram which shows the example of two three-dimensional models compared. It is a flowchart which shows embodiment of the corresponding point search method concerning this invention. It is a flowchart which shows the example of the calculation process of the feature-value of each sampling point in the said corresponding point search method. It is a schematic diagram which shows the example of average diffusion distance (ADD). It is a schematic diagram which shows the example of the gradient direction of ADD calculated in the calculation process of the said feature-value. It is a schematic diagram which shows the positional relationship of the projection surface on which the local depth image constructed | assembled in the said feature-value calculation process is perspectively projected, the camera center of the virtual camera used for perspective projection, and a three-dimensional model.

  Hereinafter, a corresponding point search apparatus (hereinafter referred to as “this apparatus”), a corresponding point search program (hereinafter referred to as “this program”), and a corresponding point search method (hereinafter referred to as “this method”) according to the present invention are implemented. The form will be described with reference to the drawings.

FIG. 1 is a functional block diagram showing an embodiment of the present apparatus. The apparatus 10 includes a sampling point determination unit 11, a feature amount calculation unit 12, a similarity calculation unit 13, a corresponding point determination unit 14, and a storage unit 15.

  Here, the apparatus 10 is realized by an information processing apparatus such as a personal computer. This method, which will be described later, is executed by the apparatus 10 when the program operating on the apparatus 10 cooperates with the hardware resources constituting the apparatus 10.

  In addition, by operating the program on an information processing apparatus different from the apparatus 10, the information processing apparatus can function in the same manner as the apparatus 10 to execute the method.

  The storage unit 15 is a means for storing position information, connection information, and other information necessary for the apparatus 1 to be described later to implement the method.

  The position information is information on the three-dimensional coordinates of each point of the point group constituting the three-dimensional model.

  The connection information is information indicating a connection state (how to cut a triangular mesh to be described later) between points of a point group constituting the three-dimensional model.

  The storage unit 15 stores position information and connection information for each point of the point group constituting the three-dimensional model.

  The sampling point determination unit 11 is means for determining (extracting) sampling points from the point group constituting the three-dimensional model. As a sampling point determination method, for example, a method such as farthest point sampling is used.

  Sampling points are points to be searched for corresponding points in a point group constituting a three-dimensional model.

  FIG. 2 is a schematic diagram showing an example of sampling points and connection information (mesh) taking a three-dimensional model of a human whole body as an example, and FIG. 2B is surrounded by a rectangle in FIG. The part is extracted. In the figure, among the points of the point group constituting the three-dimensional model, adjacent points are connected by lines. That is, each side of the triangular mesh is a line connecting adjacent vertices. Also, in the same figure, the vertices of the triangular mesh, that is, the points marked with a circle among the points of the point group constituting the three-dimensional model are points determined as sampling points.

  FIG. 3 is a schematic diagram illustrating an example of two three-dimensional models to be compared. In the figure, a three-dimensional model of the whole human body is shown. In the three-dimensional model in FIG. 6A, six sampling points 1, 2, 3, 4, 5, 6 are determined. In the three-dimensional model (b), six points of sampling points a, b, c, d, e, and f are determined.

  Information indicating the number of sampling points (“6” in the example shown in FIG. 3) determined from the point group constituting each three-dimensional model is set in the apparatus 10 in advance (in the storage unit 15). Remembered).

  The feature amount calculation unit 12 is a means for calculating the feature amount of the sampling point using the position information and connection information for each vertex. The feature amount and its calculation method will be described later.

  The similarity calculation unit 13 is a means for calculating the similarity between sampling points. The similarity and its calculation method will be described later.

  The corresponding point determination unit 14 is a means for determining a corresponding point.

  The corresponding point is a sampling point of the other three-dimensional model corresponding to a sampling point of one of the two three-dimensional models to be compared. That is, in the example shown in FIG. 3, for each sampling point in FIG. 3A, one of the sampling points in FIG. 3B is determined as a corresponding point. That is, for example, the corresponding point of the sampling point 1 in FIG. 5A is one of the sampling points a, b, c, d, e, and f in FIG.

  Note that there may be a solution (case) in which a corresponding point corresponding to a sampling point of one three-dimensional model does not exist in the other three-dimensional model.

  A method for determining the corresponding points will be described later.

[Method] FIG. 4 is a flowchart showing an embodiment of the method.
First, for each of the two three-dimensional models to be compared, the apparatus 10 reads the position information and connection information of the point groups constituting each of them from the storage unit 15, and determines sampling points from the point groups (S1). ).

  Next, the apparatus 10 calculates a feature amount for each determined sampling point (S2).

FIG. 5 is a flowchart illustrating an example of a feature amount calculation process for each sampling point.
First, the present apparatus 10 reads position information and connection information of the constituent point groups from the storage unit 15 for each of the two three-dimensional models to be compared (S21).

  In the reading process (S21), the position information and the connection information read from the storage unit 15 in the above-described sampling point determination process (S1) may be used. In this case, it is not necessary to read these information from the storage unit 15 separately from the processing (S1).

  Next, the apparatus 10 determines, for each 3D model, the normal direction of each sampling point using the position information and connection information of all the vertices of the 3D model (S22).

  Next, the apparatus 10 determines the gradient direction of the average diffusion distance (ADD) of each sampling point for each three-dimensional model (S23).

  In determining the ADD gradient direction, the apparatus 10 first calculates a diffusion distance from all other sampling points of the same three-dimensional model for each vertex, and then calculates each sampling. The average value of the diffusion distance with the point is calculated as ADD.

The diffusion distance is a distance representing the connection strength of the graph structure. When the connection is strong, the diffusion distance is small (near), and when the connection is weak, the distance is large (far). The diffusion distance measures the shortest distance on the surface of the curved surface, almost the same as the geodesic distance, but is more robust to noise and data loss than the geodesic line. The diffusion distance d _D between the two points x and y can be calculated by the following equation.

  The graph Laplacian matrix can be obtained from the position coordinates for each vertex and the connection relationship.

  ADD is a scalar field where the central area of the 3D model is low and the end area of the 3D model is high.

  FIG. 6 is a schematic diagram illustrating an example of ADD in the case of a three-dimensional model of a human whole body. The figure shows that the ADD around the navel located at the center of the whole body is low, and the ADD around the fingertips and the top of the head located at the end of the whole body is high.

  FIG. 7 is a schematic diagram illustrating an example of the ADD gradient direction. The figure shows the sampling point that is the object of calculation of the ADD gradient direction in the center of the figure, and shows that there are six other vertices connected to this sampling point.

The apparatus 1 calculates the ADD gradient direction of the other vertex connected to the sampling point for each sampling point by the following equation.

ADD gradient direction = (V1 + V2 +... + Vn) / n

Here, n is the number of other vertices connected to the sampling point to be calculated in the gradient direction of ADD, and n = 6 in the example shown in FIG.
Further, V1, V2,..., Vn are gradient vectors of sides connecting the sampling points for calculation of the ADD gradient direction and other vertices connected to the sampling points, and are calculated by the following equations. The

V1 = (a1-a0) e1
V2 = (a2-a0) e2
...
Vn = (an−a0) en

Note that a0,..., An are ADD values of the respective points.
E0,..., En are values in the unit direction (vector) of each side connecting the sampling point to be calculated in the ADD gradient direction and other vertices, and x0,. Assuming the three-dimensional coordinates (three-dimensional position) of the point, the following formula is used.

e1 = (x1-x0) / | x1-x0 |
e2 = (x2-x0) / | x2-x0 |
...
en = (xn-x0) / | xn-x0 |

Returning to FIG.
The apparatus 10 constructs a local depth image for each sampling point (S24).
FIG. 8 is a schematic diagram showing the positional relationship between the three-dimensional model, the projection plane on which the local depth image is perspectively projected, and the camera center of the virtual camera coordinate system.

  Here, the coordinate system of the virtual camera sets, for each sampling point, the aforementioned normal direction as the Z direction and the aforementioned ADD gradient direction as the Y direction. The distance from the sampling point to the camera center of the virtual camera determines the size of the local area of the three-dimensional model that enters the local depth image (the range is wide if the distance is large, and the range is narrow if the distance is small). The resolution (for example, 50 × 50 pixels) of the local depth image for each sampling point is constant for each sampling point. Information indicating the distance from the sampling point to the center of the camera and the resolution of the local depth image is set in the apparatus 10 in advance (stored in the storage unit 15).

  In the local depth image, a line connecting the vertexes of the three-dimensional model (P, Q, R in the figure) from the camera center intersects with a projection plane set between the camera center and the three-dimensional model ( In the figure, it is constructed using P ′, Q ′, R ′).

  The value at each pixel of the local depth image is the size in the Z direction, that is, the distance in the Z direction from the camera center to each vertex (dP, dQ, dR in the figure).

Returning to FIG.
The apparatus 10 calculates a feature amount for each sampling point (S25). The feature amount for each sampling point is a set of values of each pixel included in the local depth image constructed for each sampling point (a 50 × 50 image matrix is represented as a vector).

Returning to FIG.
The apparatus 10 calculates the similarity (Euclidean norm) between the sampling points for every combination of the respective sampling points of the two three-dimensional models to be compared (S3). That is, in the example shown in FIG. 3, the similarity between the sampling point 1 in FIG. 3A and the sampling points a, b, c, d, e, and f in FIG. ) Of the sampling point 2 and the sampling points a, b, c, d, e, and f of FIG. 6B,...,... And the sampling point of FIG. The similarity to each sampling point a, b, c, d, e, f is calculated.

  Next, the apparatus 10 matches the sampling points of the two three-dimensional models to be compared, that is, the sampling points of one three-dimensional model (for example, the sampling points 1, 2, 3, and 3 shown in FIG. 3A). 4, 5, 6) and the other three-dimensional model sampling points (for example, sampling points a, b, c, d, e, f shown in FIG. 3B) are associated (S4). . This association is performed using, for example, the Hungarian method, and a one-to-one correspondence matching result between the sampling points of the two three-dimensional models to be compared is obtained.

● Summary According to the embodiment described above, the local depth image is constructed in the coordinate system using the gradient direction of the ADD calculated from the global information of the three-dimensional model, and the feature calculated from the local depth image Since the corresponding points are searched using the quantity, the search can be robust against local deformation and the search accuracy can be improved as compared with the conventional search performed using only the local information of the three-dimensional model. it can.

  Here, the features of the present apparatus described so far are collectively described below.

(Feature 1)
A storage unit for storing position information and connection information of each point of the first three-dimensional model and the second three-dimensional model configured by point groups;
For each of the three-dimensional models, a sampling point determination unit that determines a plurality of sampling points from the point group;
A feature amount calculation unit that calculates a feature amount for each sampling point using the position information and connection information for each sampling point stored in the storage unit;
A similarity calculation unit that calculates the similarity between the sampling points of the first three-dimensional model and the sampling points of the second three-dimensional model based on the feature amount;
A corresponding point determination unit that determines a point corresponding to each sampling point of the first three-dimensional model from sampling points of the second three-dimensional model based on the similarity;
Having
The feature amount calculation unit, for each sampling point,
Constructing a local depth image in the coordinate system of the virtual camera in which the normal direction on the curved surface of the three-dimensional model is the Z direction and the gradient direction of the average diffusion distance on the curved surface is the Y direction,
A feature amount is calculated using the depth of each pixel included in the local depth image.
Corresponding point search device characterized by the above.

(Feature 2)
The feature amount calculation unit is configured for each of the three-dimensional models.
Calculate the diffusion distance to other sampling points for each sampling point,
An average value of the diffusion distance for each sampling point is calculated as the average diffusion distance of the sampling points.
Corresponding point search device according to feature 1.

(Feature 3)
The feature amount calculation unit calculates a gradient direction of the average diffusion distance using the average diffusion distance for each sampling point.
Corresponding point search device according to feature 2.

(Feature 4)
The feature amount calculation unit constructs, as the local depth image, an image that is perspective-projected on a projection plane between the camera center of the coordinate system of the virtual camera and the curved surface of the three-dimensional model;
The corresponding point search device according to any one of features 1 to 3.

(Feature 5)
The similarity calculation unit includes:
The feature amount of the sampling point of the first three-dimensional model and the Euclidean distance between the sampling points of the second three-dimensional model,
Calculating the similarity between the sampling points of the first three-dimensional model and the sampling points of the second three-dimensional model;
The corresponding point search device according to any one of features 1 to 4.

DESCRIPTION OF SYMBOLS 10 Corresponding point search apparatus 11 Sampling point determination part 12 Feature-value calculation part 13 Similarity calculation part 14 Corresponding point determination part 15 Memory | storage part

Claims (7)

A storage unit for storing position information and connection information of each point of the first three-dimensional model and the second three-dimensional model configured by point groups;
For each of the three-dimensional models, a sampling point determination unit that determines a plurality of sampling points from the point group;
A feature amount calculation unit that calculates a feature amount for each sampling point using the position information and connection information for each sampling point stored in the storage unit;
A similarity calculation unit that calculates the similarity between the sampling points of the first three-dimensional model and the sampling points of the second three-dimensional model based on the feature amount;
A corresponding point determination unit that determines a point corresponding to each sampling point of the first three-dimensional model from sampling points of the second three-dimensional model based on the similarity;
Having
The feature amount calculation unit, for each sampling point,
Constructing a local depth image in the coordinate system of the virtual camera in which the normal direction on the curved surface of the three-dimensional model is the Z direction and the gradient direction of the average diffusion distance on the curved surface is the Y direction,
A feature amount is calculated using the depth of each pixel included in the local depth image.
Corresponding point search device characterized by the above. The feature amount calculation unit is configured for each of the three-dimensional models.
Calculate the diffusion distance to other sampling points for each sampling point,
An average value of the diffusion distance for each sampling point is calculated as the average diffusion distance of the sampling points.
The corresponding point search apparatus according to claim 1. The feature amount calculation unit calculates a gradient direction of the average diffusion distance using the average diffusion distance for each sampling point.
The corresponding point search apparatus according to claim 2. The feature amount calculation unit constructs, as the local depth image, an image that is perspective-projected on a projection plane between the camera center of the coordinate system of the virtual camera and the curved surface of the three-dimensional model;
The corresponding point search apparatus according to claim 1. The similarity calculation unit includes:
The feature amount of the sampling point of the first three-dimensional model and the Euclidean distance between the sampling points of the second three-dimensional model,
Calculating the similarity between the sampling points of the first three-dimensional model and the sampling points of the second three-dimensional model;
The corresponding point search apparatus according to claim 1.   6. A corresponding point search program that causes a computer to function as the corresponding point search device according to claim 1. A corresponding point search method executed by an apparatus including a storage unit in which position information and connection information of each point of a first three-dimensional model and a second three-dimensional model composed of point groups are stored. And
The device is
Determining a plurality of sampling points from the point group for each of the three-dimensional models;
Using the positional information and connection information for each sampling point stored in the storage unit to calculate a feature value for each sampling point;
Calculating the similarity between the sampling points of the first three-dimensional model and the sampling points of the second three-dimensional model based on the feature amount;
Determining a point corresponding to each sampling point of the first three-dimensional model from the sampling points of the second three-dimensional model based on the similarity;
Having
For each sampling point, the device
Constructing a local depth image in the coordinate system of the virtual camera in which the normal direction on the curved surface of the three-dimensional model is the Z direction and the gradient direction of the average diffusion distance on the curved surface is the Y direction,
A feature amount is calculated using a pixel value included in the local depth image.
The corresponding point search method characterized by this.

Images