JP2000113192A - Analyzing method for three-dimensional shape data and recording medium - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide an analyzing method capable of calculating the complexity of three-dimensional(3D) shape data. SOLUTION: In a step ST11, the shape data of alignment object is read. Next, in a step ST12, a 2D feature image expressing the features of 3D shape near arbitrary points, namely, candidate points on the surface of 3D shape to become the alignment object is prepared. Next, in a step ST13, the complexity index on the surface of 3D shape to become the alignment object is calculated from the feature image and the complexity of the feature image is digitized.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for analyzing three-dimensional shape data and a recording medium, and more particularly, to a method for analyzing three-dimensional shape data related to preprocessing prior to a process for aligning three-dimensional shape data and executing the method. The present invention relates to a recording medium on which a program to be recorded is recorded.

[0002]

2. Description of the Related Art First, a concept of a process for aligning three-dimensional shape data will be described with reference to FIGS. In order to obtain three-dimensional shape data (hereinafter, referred to as shape data) obtained by converting a three-dimensional shape into a data, a three-dimensional image is taken using a device such as a three-dimensional scanner. In this case, not all portions can be photographed, and some portions may become blind spots. Therefore, it is necessary to shoot from multiple viewpoints. In this case, registration of the shape data obtained from each viewpoint (Registrati
on).

FIG. 9 shows an entire image of an object OB, and FIGS. 10 and 11 show partial shape data of two regions R1 and R2 of the object OB, respectively, which are photographed. In order to obtain the shape data of the entire object OB, it is necessary to collect and combine partial shape data as shown in FIGS. At this time, the coordinates of each partial shape data are shared and positioning is performed. This is a positioning process.

[0004] In short, for example, in FIG. 9, although the regions R1 and R2 have overlapping portions, the position of each partial shape data is determined so that the overlapping portions overlap.

Prior to such a positioning process, a rough comparison of the partial shape data of the regions R1 and R2 is performed, and a process of determining the approximate arrangement of each partial shape data is performed.
This is called pre-processing or search processing. This pre-processing will be further described with reference to FIGS.

[0006] The shape data of the point P1 shown in FIG.
Comparing the shape data of the point P2 shown in FIG. 1, the point P1 on the relatively steep curved surface and the point P2 on the relatively gentle curved surface
And have different data because the shapes are different in complexity.

On the other hand, comparing the shape data of point P3 shown in FIG. 10 with the shape data of point P4 shown in FIG.
Since both exist on the same curved surface, their data are similar.

Therefore, the partial layout data of the regions R1 and R2 should be arranged so that the points P3 and P4 are close to each other and the points P1 and P2 are close to each other. Not determined. in this way,
In the pre-processing for performing a rough data comparison for the approximate arrangement of the partial shape data, an index used for data comparison is the complexity of the shape data.

Next, an example of a conventional method of calculating the complexity of shape data will be described with reference to FIG. FIG. 12 shows an example in which a local area LSA including the calculation target point Q extends over a plurality of polygon meshes PG.
Note that the calculation target point Q corresponds to the point P1 shown in FIG.

In FIG. 12, when the average normal vector at the calculation target point Q is AN, the local area LSA
Are distributed in a hemisphere centered on the direction of the average normal vector AN. The distribution is oriented in one direction when the local area LSA is close to a plane, but varies as the complexity increases. The statistical variance of the normal vector is used as the complexity of the shape data.

[0011]

As described above,
Conventionally, in the analysis of the three-dimensional shape data, the complexity is directly calculated from the three-dimensional shape data, so that there is a problem that a long time is required for processing.

SUMMARY OF THE INVENTION The present invention has been made to solve the above problems, and has as its object to provide an analysis method capable of calculating the complexity of three-dimensional shape data at high speed.

[0013]

According to a first aspect of the present invention, there is provided a method for analyzing three-dimensional shape data, the method reflecting a characteristic of the three-dimensional shape based on the three-dimensional shape data obtained by converting a three-dimensional shape into data. Step of creating a two-dimensional feature image (a)
And a step (b) of calculating a complexity index obtained by quantifying the complexity of the feature image.

According to a second aspect of the present invention, in the method for analyzing three-dimensional shape data, the step (a) may include arbitrarily setting a point of interest on the surface of the three-dimensional object; Setting a tangent plane perpendicular to the normal
(a-1) and a step (a-2) of displaying the height difference around the point of interest on the tangent plane as a contour line, wherein the step (b) is the same as the perimeter of the contour line. (B-1) setting a circle having a circumference and matching the center of gravity of the surface defined by the contour line with the center of the circle;
(B-2) calculating the distance of the contour line from the outer periphery of the circle on the center line of the circle for each center line and adding the calculated distance to the complexity index.

A recording medium according to a third aspect of the present invention comprises:
A program for causing a computer to execute the method for analyzing three-dimensional shape data according to claim 1 is recorded.

A recording medium according to a fourth aspect of the present invention comprises:
Steps (a-1), (a-2), and (b-
A program for causing a computer to execute steps 1) and (b-2) is recorded.

[0017]

DESCRIPTION OF THE PREFERRED EMBODIMENTS As an embodiment of a method for analyzing three-dimensional shape data according to the present invention, a pre-processing (searching process) prior to a positioning of three-dimensional shape data is shown in FIGS.
This will be described with reference to FIG.

<Overall Flow of Preprocessing> FIG. 1 is a flowchart showing the overall flow of preprocessing. In step ST1 shown in FIG. 1, first, a candidate point (point of interest) for preprocessing in the alignment target shape is arbitrarily set, and a complexity index is calculated for all the candidate points. In other words, this is a step of selecting candidate points for preprocessing in the partial shape data to be aligned as shown as points P1 to P4 in FIGS. 10 and 11, and calculating the respective complexity indexes. .

Next, in step ST2, a point having a matching shape is searched based on the calculated complexity index. This is a step of comparing the complexity indices of the candidate points on a brute force basis and searching for one having a similar index value. The positioning process is performed based on the result obtained in this step.

FIG. 2 is a flowchart for further explaining the operation of step ST1 shown in FIG. 1. First, in step ST11, shape data of a shape to be aligned is read.

Next, in step ST12, an arbitrary point on the surface of the three-dimensional shape to be aligned, that is, a two-dimensional feature image near the candidate point is created. This is a step of creating two-dimensional image data representing the features of the three-dimensional shape, and is a step that is a feature of the present invention. The creation of the two-dimensional feature image will be described in more detail later.

Next, in step ST13, a complexity index of the surface of the three-dimensional shape to be aligned is calculated from the feature image, and the complexity of the feature image is quantified. An example of calculating the complexity index will be described later in more detail.

Then, it is confirmed whether or not the complexity index has been calculated for all the candidate points, and if there are uncalculated candidate points, the operations of steps ST12 and ST13 are repeated (step ST14).

FIG. 3 is a flowchart for further explaining the operation of step ST2 shown in FIG. 1. First, in step ST21, each of the comparison data A and the compared data B of the partial shape data to be aligned is determined. Compare the complexity indices X and Y. For example, the candidate point selected from one of the two partial shape data is used as comparison data, the complexity index of the candidate point and the candidate point selected from the other partial shape data are used as comparison data, This is the step of comparing the complexity indices of the points.

In step ST22, when the absolute value of the difference between the complexity indices X and Y is larger than a predetermined set value, the compared data B is excluded. this is,
This is a step of narrowing down alignment targets by excluding completely different shape data. If the absolute value of the difference between the complexity indices X and Y is equal to the set value, the remaining candidate points are selected to be compared data and compared with the comparison data A (step ST23).

Then, it is checked whether or not all the candidate points of the two partial shape data have been compared. If there is an uncompared candidate point, the process proceeds from step ST21 to step ST21.
The operation of step 23 is repeated (step ST24). And
The approximate arrangement of the partial shape data is determined based on the complexity index of the finally remaining candidate points.

<Example of Creating Feature Image> An example of a method of creating a two-dimensional feature image will be described below with reference to FIGS. FIG. 4 shows a curved surface CS as shape data to be aligned. Then, a candidate point AP for preprocessing is set at one point of the undulation UD on the curved surface CS. Further, a plane (tangential plane) PS that is perpendicular to the normal NL at the candidate point AP is set on the curved surface CS.

With respect to this tangent plane PS, the shape around the candidate point AP is represented by a contour line. FIG. 5 shows a tangent plane PS on which the contour lines CL1 to CL3 are displayed. The contour line extracts the data about the height from the shape data of the curved surface CS, and outputs the tangent plane PS.
Plots are made corresponding to the above coordinates, and coordinates having the same height data are virtually connected on the tangent plane PS.
The contour lines represent the three-dimensional shape of the curved surface CS, and the tangent plane P
The contour displayed in S can be said to be image data obtained by projecting a three-dimensional shape feature on a two-dimensional plane, that is, a feature image.

FIG. 6 shows a flowchart of the two-dimensional feature image creation process. In FIG. 6, first, as shown in step ST121, a candidate point for preprocessing is set at an arbitrary position on the surface of the three-dimensional shape.

Then, in step ST122, a normal line at the candidate point is set, and a tangent plane is set so as to be perpendicular to the normal line.

Then, a three-dimensional shape around the candidate point is displayed on the tangent plane by contour lines to create a characteristic image (step ST).
123). It goes without saying that these processes are performed for all candidate points in all partial three-dimensional shapes to be aligned.

<Method of Calculating Complexity Index> Next, an example of a method of calculating the complexity index will be described with reference to FIGS. Note that the following description uses 3D as a two-dimensional feature image.
This is a method suitable for displaying a dimensional shape by contour lines.

First, the concept of the method of calculating the complexity index when the contour display is used will be described with reference to FIG. FIG. 7 shows a contour line CL1 on the tangent plane shown in FIG. 5 and a circle CC substantially surrounding the contour line CL1. Here, the circle C
C is set to have the same circumference as the circumference of the contour line CL1. The center of gravity CG obtained for the shape defined by the contour line CL1 and the center CP of the circle CC are arranged to overlap.

When the contour line CL1 and the circle CC are arranged in this manner, since the contour line CL1 is circular, that is, the candidate point does not exist on a smooth spherical surface, each outer periphery and the center of gravity CG
(The same as the center CP). That is, the distance from the center of gravity is shifted by the distance D as shown in FIG. The absolute value of the distance D is obtained for the entire circumference, and the value obtained by adding them is defined as the complexity index at the contour line of 1. In other words, the distance of the contour line from the outer periphery of the circle on the center line of the circle is calculated for each center line and added.

The above processing is performed for all contour lines on the tangent plane, and the complexity index at each contour line is added to obtain the complexity index at the feature image, that is, the complexity index at the candidate point.

FIG. 8 shows a flowchart of the process of calculating the complexity index. In FIG. 8, first, step S
As shown in T131, a circle having the same circumference as the circumference of one contour is set, and the circle and the contour are overlapped so that the center of gravity of the contour coincides with the center of the circle.

Next, as shown in step ST132,
Perimeter and center of gravity (= center) for contours and circles
Is obtained for the entire circumference (not necessarily the entire circumference), and the sum of the absolute value of the deviation of the distance from the center of gravity for the entire circumference (not necessarily the entire circumference) is 1
The complexity index at one contour line.

Then, in step ST133, it is confirmed whether or not the complexity index has been obtained for all the contour lines on the tangent plane.
The operations of 131 and ST132 are repeated.

Finally, a complexity index of the feature image is obtained by adding the calculated complexity of all the contour lines (step ST134).

<Characteristic Effects> As described above,
According to the present invention, when calculating a complexity index of a candidate point for preprocessing, a feature of a three-dimensional shape is displayed as a feature image which is a two-dimensional image, and a complexity index is obtained from the feature image. Therefore, the processing time can be reduced as compared with the method of directly obtaining the complexity from the three-dimensional shape data.

As a method of calculating the complexity of a two-dimensional image, various conventional methods can be used.
A wide range of choices can be made for the complexity indexing method, and an indexing method suitable for various applications can be obtained.

<Another Example of Complexity Indexing Method> Another example of the complexity indexing method will be described below. First, 1
One is to express the complexity by geometric fractal dimension values. This method focuses on the property that two-dimensional figures take values between 0 and 2 in principle in accordance with their complexity. That is, the three-dimensional shape is changed to 2
If the figure expressed in dimension is simply a straight line, it is 1
Although it is a two-dimensional image, if the straight line has irregularities, the dimension value increases to 1.1 dimensions, 1.2 dimensions, and the most complicated image is two dimensions. By using such a method, it is possible to quantify the complexity of an image in which, for example, a three-dimensional shape is displayed as contour lines.

One method is to define the complexity by the average information amount of the target image. This method focuses on the property that a complex image has a larger amount of information. For example, a three-dimensional shape can be represented by an image composed of pixels with shading corresponding to the height, and the complexity of the image can be quantified by the appearance probability of shading.

One of the methods is to define the complexity by the variance of the target image. This method is useful for complex images.
This focuses on the property that pixels having a large number of bits are concentrated. For example, projecting a three-dimensional shape onto a two-dimensional plane,
By dividing the area into predetermined areas, the number of bits per pixel in the area is measured, and the complexity of the image can be quantified based on the distribution of pixels according to the number of bits.

As described above, the complexity index of a two-dimensional image can be obtained by various methods. Needless to say, in the present invention, a complexity index obtained by other methods may be used.

<Another Example of Application of Complexity Index> In the above description, an example has been described in which preprocessing prior to positioning of three-dimensional shape data is performed using the calculated complexity index. The application of the index is not limited to the pre-processing.

For example, it can be used as a boundary expression representing a three-dimensional shape based on the obtained complexity index, for example, a judgment index for regenerating a polygon mesh. For example, the shape is complicated at the vertex portion representing the feature of the shape, and by taking measures such as reducing the mesh interval of the polygon mesh based on the complexity index, the boundary expression of the three-dimensional shape can be more accurately represented. .

Also, it can be used as an index of the degree of compression (the ratio of the amount of compressed data to the original data) in the compression processing of the three-dimensional shape data. By increasing the degree, the amount of compressed data can be adjusted.

<Writing on Recording Medium>
The method of analyzing three-dimensional shape data stores a program that causes the control unit of the three-dimensional shape data analysis device as a dedicated computer to execute the steps of the flowcharts shown in FIGS. 1 to 3, 6, and 8 described above. It can be realized by leaving it, but write the above program on a recording medium such as a flexible disk,
By reading this, the three-dimensional shape data taken into a general-purpose personal computer or workstation may be analyzed.

[0050]

According to the method for analyzing three-dimensional shape data according to the first aspect of the present invention, a feature of a three-dimensional shape is displayed as a two-dimensional feature image, and a complexity index is obtained from the feature image. Therefore, the processing time can be reduced as compared with the method of directly obtaining the complexity from the three-dimensional shape data. In addition, various conventional methods can be used to calculate the complexity of a two-dimensional image, and a wide range of complexity indexing methods can be selected, and an indexing method suitable for various application purposes can be selected. Obtainable.

According to the method for analyzing three-dimensional shape data according to the second aspect of the present invention, the shape around the point of interest is displayed as a feature image by contour lines, and a circle having the same circumference as the circumference of the contour line is displayed. , A complexity index is obtained by comparing the above, so that the complexity index that reflects the characteristics of the three-dimensional shape relatively accurately can be obtained while the complexity index calculation process is relatively simple.

According to the recording medium of the third aspect of the present invention, a program for executing the method of analyzing three-dimensional shape data of the first aspect is recorded, and this program is executed by a computer. By 3
The processing time can be reduced as compared with the method of directly obtaining the complexity from the dimensional shape data.

According to the recording medium of claim 4 of the present invention, the steps (a-1), (a-2),
Since a program for executing the steps (b-1) and (b-2) is recorded, by executing this program on a computer, the calculation process of the complexity index is relatively simple. It is possible to obtain a complexity index that reflects the feature of the dimensional shape relatively accurately.

[Brief description of the drawings]

FIG. 1 is a flowchart illustrating the positioning of a method for analyzing three-dimensional shape data according to the present invention.

FIG. 2 is a flowchart illustrating a main part of a method for analyzing three-dimensional shape data according to the present invention.

FIG. 3 is a flowchart illustrating a complexity index comparison process.

FIG. 4 is a conceptual diagram illustrating an example of a feature image creation method.

FIG. 5 is a diagram showing a characteristic image by contour display.

FIG. 6 is a flowchart illustrating a method for creating a characteristic image.

FIG. 7 is a conceptual diagram illustrating a method of calculating a complexity index from a feature image by contour display.

FIG. 8 is a flowchart illustrating a method of calculating a complexity index from a feature image by contour display.

FIG. 9 is a conceptual diagram illustrating the alignment of shape data.

FIG. 10 is a conceptual diagram illustrating alignment of shape data.

FIG. 11 is a conceptual diagram illustrating alignment of shape data.

FIG. 12 is a conceptual diagram illustrating an example of a conventional method of calculating the complexity of shape data.

[Explanation of symbols]

PL tangent plane, AP candidate point, NL normal, CL1-C
L3 contour, CG center of gravity, CP center

Claims (4)

[Claims] (A) creating a two-dimensional feature image reflecting the three-dimensional features based on three-dimensional shape data obtained by converting a three-dimensional shape into data; (b) complexity of the feature images Calculating a complexity index obtained by digitizing the three-dimensional shape data. 2. The step (a) comprises: (a-1) arbitrarily setting a point of interest on the surface of the solid, and setting a normal line at the point of interest and a tangent plane perpendicular to the normal line. (A-2) displaying a height difference around the point of interest on the tangent plane as a contour line, wherein the step (b) comprises: (b-1) a perimeter of the contour line Setting a circle having the same circumferential length as the above, and matching the center of gravity of the surface defined by the contour line with the center of the circle; (b-2) from the outer circumference of the circle on the center line of the circle 2. The method for analyzing three-dimensional shape data according to claim 1, further comprising: calculating a distance between the contour lines for each of the center lines, and adding the calculated distance to the complexity index. 3. A computer-readable recording medium on which a program for causing a computer to execute the method for analyzing three-dimensional shape data according to claim 1 is recorded. 4. The method according to claim 2, wherein steps (a-1) and (a)
4. The computer-readable recording medium according to claim 3, wherein a program for causing a computer to execute the steps of -2), (b-1), and (b-2) is recorded.