JPH07210679A - 3D object shape description recognition method - Google Patents

Abstract

(57) [Summary] [Object] The present invention relates to a three-dimensional object shape description recognition method, and an object thereof is to obtain an object extremely similar to original data. [Configuration] A step of fitting a function to original data when comparing a shape of data and a shape of a target model stored in advance and selecting a candidate object, and a step of determining a function to be fitted in the step, Comparing the values of the parameters of the fitted function.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a three-dimensional object shape description recognition method, and more particularly to a three-dimensional object shape description recognition method for efficiently comparing the similarity of three-dimensional shapes.

[0002]

2. Description of the Related Art Conventionally, as a method of shape comparison for natural objects, various geometrical features are extracted from the target two-dimensional contour data and examined, and the geometrical features are analyzed to determine similar shapes. The main methods are to recognize the target by comparing the positional relationship of the target feature information (features such as eyes, mouth, and eyebrows in the case of a face).

Further, as a method of making a comparison based on the difference in the coefficient of the spherical harmonic function, there is a method in which the sum of the differences in the coefficient sequence is used as a criterion for determining the similarity.

[0004]

In the comparison method using a two-dimensional contour shape, an appropriate comparison cannot be made unless a contour that well expresses the characteristic shape of the object is used, and the object is a three-dimensional shape. ， It was difficult to find this contour.

Further, the local feature comparison method has a problem in that it is impossible to recognize the overall (schematic) shape of a three-dimensional shape. Furthermore, in the comparison method based on the difference in the coefficient of the spherical harmonic function, even if two different shapes are similar,
It was judged that they were different, and it was necessary to normalize the target shape. In addition, the coefficient string of the spherical harmonic function may have completely different coefficients even if the shape is the same, depending on how the origin is taken, and it is not possible to simply classify the shapes by comparing the values of the coefficient string.

The object of the present invention is to recognize a three-dimensional object shape description which makes it possible to obtain an object very similar to the original data by repeating the fitting of the function representing the closed surface to the original data and the comparison of the function parameters. To provide a method.

Another object of the present invention is to provide a three-dimensional object shape description recognition method which makes it possible to compare stable function parameters by applying a spherical harmonic function and other functions to the original data. is there.

Another object of the present invention is to provide a three-dimensional object shape description recognition method which makes it possible to compare more detailed shapes by changing the order of the spherical harmonics. Another object of the present invention is to provide a three-dimensional object shape description recognition method capable of judging global shape similarity using a spectrogram formed by a coefficient sequence of spherical harmonics. It is in.

Still another object of the present invention is to normalize the spectrogram formed by the coefficient sequence of the spherical harmonic function,
An object of the present invention is to provide a three-dimensional object shape description recognition method capable of recognizing similar shapes of original data.

[0010]

In order to solve the above-mentioned problems, the invention according to claim 1 applies a function to original data, a step of determining a function to be applied in the step, and an object shape. Is compared based on the function parameter.

Further, in the invention described in claim 2, in the invention described in claim 1, as a function to be applied, a spherical harmonic function and a function capable of representing a closed curved surface other than the spherical harmonic function are used.

The invention according to claim 3 is the same as the invention according to claim 2, further comprising a step of varying the order of the spherical harmonic function. The invention according to claim 4 is characterized in that, in the step of comparing the values of the function parameters in the invention according to claim 2, the step of correlating the waveform of the spectrogram formed by the coefficient sequence of the spherical harmonic function Have.

Further, the invention according to claim 5 is the invention according to claim 4, which further comprises a step of performing a comparison after normalizing the spectrogram formed by the coefficient sequence of the spherical harmonics.

[0014]

According to the invention of claim 1, the original data is
The approximate shape of the object can be obtained by applying the function representing the closed surface, and the candidates of the similar shape of the original data can be extracted by comparing the parameters of the function. Then, another function is used to fit the original data again, and the fitted function parameters are compared with the function parameters of the candidates selected as described above. By repeating this operation, candidates are gradually narrowed down, and finally an object most similar to the original data can be obtained.

According to the second aspect of the present invention, a spherical harmonic function and a function F representing a closed curved surface other than the spherical harmonic function are used as the functions to be applied in the above method. Find the general shape of an object. Next, using the center coordinates of the function F as the center coordinates of the original data, a spherical harmonic function is applied to the original data. This function is 3
It can be thought of as a three-dimensional version of the Fourier descriptor. In the present invention, the drawback of the spherical harmonic function in which the parameter of the function greatly changes depending on the position of the origin is solved by using the center of the function F and stably obtaining the origin at almost the same position if the shape is similar. This makes it possible to recognize the shape of the object by comparing the spectrograms of the spherical harmonic function coefficient sequences.

Further, according to the invention described in claim 3, by changing the order of the spherical harmonics in the above method,
By comparing the rough shapes of the original data using low-order spherical harmonics and gradually increasing the order, it becomes possible to perform more detailed shape comparisons.

According to the fourth aspect of the present invention, by comparing the waveform shapes of the spectrograms formed by the coefficient sequences of the spherical harmonics, it is possible to judge the overall shape similarity. Becomes

According to the invention described in claim 5, by normalizing the spectrogram formed by the coefficient sequence of the spherical harmonic function and then comparing the waveform shapes, even if the objects have similar shapes, If the shape is similar to the original data, it can be selected.

[0019]

Embodiments of the present invention will be described in detail with reference to the drawings. In this embodiment, a superquadratic function and a spherical harmonic function are used as the functions used for fitting the original data. The superquadratic function is a function that represents a kind of ellipsoid defined by the following equation (1). Here, ε1 and ε2 are called shape parameters and indicate powers of real numbers, and a1, a2, and a3 are called scale parameters and indicate sizes in the XYZ axis directions.

[0020]

[Equation 1]

The spherical harmonic function P _n ^m (X) is given by the following equation (2)
Is defined by

[0022]

[Equation 2]

Here, Pn represents a Legendre polynomial. The three-dimensional shape is expressed by the following equation (3) as a linear sum R (θ, φ) of spherical harmonics expressed in polar coordinates.

[0024]

[Equation 3]

Coefficients Amn and Bmn of the function represented by the equation (3)
Various shapes can be expressed by changing. On the contrary, from this fact, the similarity of the shapes of the objects can be judged by looking at the spectrogram of the coefficients Amn and Bmn (considering the coefficient sequence as a spectrogram).

For example, an object having an apparently different outline is
As an example, consider a spectrogram when expressed by an 8th-order spherical harmonic function (which is the case of D = 8 in the equation (3)),
On the horizontal axis, 90 coefficients are A00, B00, A from the left.
01, B01, A10, B10, A11, B11 ...
Line up in order. The horizontal axis represents the coefficient column and the vertical axis represents the coefficient values. In this case, the waveform of the coefficient sequence formed by the envelope of the coefficient values is obviously different depending on the shape of the object.

FIG. 1 is a block diagram of a data processing apparatus to which a three-dimensional object shape description recognition method according to the present invention is applied.
1 is a data input unit, 2 is a control unit for controlling various means, 3
Is a three-dimensional object of various shapes and an object / function parameter storage unit that stores and manages function parameters when a function is applied to these objects, and 4 is a display unit of the stored objects and function shapes. Reference numeral 20 is a function determining means, 21 is a function fitting means, 22 is a function parameter difference degree calculating means, and 23 is a candidate object selecting means. The control unit 2 is composed of a microprocessor and performs data processing described later according to a control program written in a memory (not shown). Hereinafter, the first to fourth embodiments will be described assuming a virtual circuit block having this function. (Embodiment 1) Embodiment 1 shows the invention described in claims 1 and 2. That is, in the first embodiment, the function determined as the function to be fitted is fitted to the original data, the object shape is compared based on the function parameter, and the spherical harmonic function and the other closed curved surface are represented as the function to be fitted. A superquadratic function is used as a function that can do this.

In the first embodiment, the content of the operation of the control unit 2 is performed according to the flowchart of FIG. First, according to the first procedure, the 3
The dimensional shape data (input data) is input from the data input unit 1 (100) and sent to the function fitting means 21. In the following, according to the third procedure, the function fitting means 21 uses the hyperquadratic function determined and designated as the function to be fitted by the function determining means 20 (101), and first, the least squares method is used to obtain the original data. The function is applied to (102). Specifically, the square error is defined by the following equation (4), and the function parameter is determined.

[0029]

[Equation 4]

Here, (Xc, Yc, Zc) represents the central coordinate G of the superquadratic function. Next, the fitted and approximated parameter P of the superquadratic function is sent to the function parameter dissimilarity calculation (comparison) means 22 and its center coordinate G is calculated.
Is sent to the function fitting means 21.

On the other hand, the object / function parameter storage unit 3 stores and manages the shape data of the three-dimensional object in advance by the second procedure. For example, for a certain three-dimensional object, the value of the parameter of the spherical harmonic function, the value of the parameter of the superquadratic function, and the like are stored.

In the function parameter difference degree calculating means 22,
The parameter P of the approximated quadratic function is compared with the value of the parameter of the quadratic function of the three-dimensional object stored in the object / function parameter storage unit 3 (103). Specifically, the Euclidean distance D of each parameter is calculated by the following equation (5) (103).

[0033]

[Equation 5]

Here, Ρ ^input represents the function parameter P fitted to the input data, and Ρ ^object represents the function parameter of the object stored in the object / function parameter storage unit 3.

Then, the candidate object selection means 23 selects candidate objects whose distance D is equal to or less than a threshold value as candidate objects O = {object # 1, object # 2, object # 3, object # 4, ...
.} Is selected (104). Thereby, the candidate object (function parameter of the object) is selected based on the shape comparison between the original data (data obtained from the original data) and the target model stored in advance.

Next, in the function determining means 20, the function fitting means 21 is instructed to use the spherical harmonic function next (105), and in the function fitting means 21, the spherical harmonic function is fitted to the original data, and the coefficient string. Is calculated (106).
Specifically, the least square error is calculated by the following equation (6).

[0037]

[Equation 6]

It is defined as Where (xc, yc, z
c) is the central coordinate G of the superquadratic function obtained above. This is because according to the super quadratic function, the center coordinates G can be stably obtained at substantially the same position if the shapes are similar. As a result, as a sequence of the coefficients Amn and Bmn of the spherical harmonic function, {A0
0, B00, A01, B01, A10, B10, A1
, B11 ...} is obtained.

Next, the function parameter difference degree calculating means 22
In step 106, the coefficient sequence of the spherical harmonic function of each of the candidate objects O previously selected in step 104 (stored in the object / function parameter storage unit 3 in advance) and the input data in step 106 are obtained. The degree of difference from the coefficient string is calculated (107). For example, the coefficient string of the coefficients Amn and Bmn is considered as the parameter P, and the similarity is judged based on the magnitude (distance) of the sum of squares of the differences between the coefficients based on the equation (5). Then, in the candidate object selecting means 23, the object having the smallest distance D is recognized as an object (final candidate) having a shape most similar to the original data and is taken out (108).

In the present embodiment, in comparing the function parameters (coefficients), the difference is calculated by the equation (5), etc., but the comparison means is not limited to this as long as the similarity of each parameter can be judged. Not something. (Second Embodiment) Next, a second embodiment will be described. The second embodiment shows the invention described in claim 3.

FIG. 3 is a flow chart showing the flow of the second embodiment. First, a superquadratic function is applied to the input data by the same steps as in the first embodiment (100 to 102). As a result, the above-mentioned center coordinate G
Is obtained by the function fitting means 21.

Next, in order to fit the spherical harmonic function, the function determining means 20 first instructs to use a low-order (for example, quadratic) function as the spherical harmonic function (10).
5). Therefore, the function fitting means 21 first fits the original data with the quadratic spherical harmonic function using the central coordinates G (110). As a result, the columns of the coefficients Amn and Bmn are {A00, B00, A01, B01, A1.
A coefficient sequence of 0, B10, A11, B11 ...} Is obtained.

Next, the function parameter difference degree calculating means 22
Then, each coefficient sequence when the object stored in the object / function parameter storage unit 3 is described by the quadratic spherical harmonic function is extracted, and this and the process 11 are performed first.
At 0, the degree of difference from the coefficient sequence of the spherical harmonic function obtained by the function fitting is calculated (107). Equation (5) is used as a means for obtaining the degree of difference.

Next, the candidate object selection means 23 selects an object whose distance D is less than or equal to a certain threshold value as a candidate object, and selects similar shapes (1
11) It is checked whether the number of selected similar shapes is n or less (112). The threshold value of the distance D and the value n are predetermined. The selected similar shapes are
It is used as a coefficient sequence stored in the object / function parameter storage unit 3.

If the number is not n or less in the process 112, the order of the spherical harmonic function is further increased by the instruction of the function determining means 20, and the same process (105 to 112) is performed for each of the remaining candidate objects.

In the process 112, when the number is n or less, the distance D between the coefficient sequence for each of the remaining candidate objects and the coefficient sequence obtained from the input data is calculated based on, for example, the equation (5), The object having the smallest D is recognized as an object having a shape most similar to the input data (114). In this way, when the number of candidate objects becomes one, the candidate object selecting means 23 recognizes this as the object (final candidate) closest to the original data (114).

In this embodiment, in comparing the function parameters (coefficients), the difference is calculated by the equation (5). However, it is only necessary to judge the similarity of each parameter, and the comparison means is limited to this. Not a thing. (Third Embodiment) Next, a third embodiment will be described. The third embodiment shows the invention described in claim 4.

FIG. 4 is a flow chart showing the flow of processing of the third embodiment. In the third embodiment, similar to the second embodiment, the processes from the data input to the fitting of the spherical harmonic function are performed (100 to 110).

Next, the coefficient of the spherical harmonic function fitted by the function fitting means 21 is taken out, and the coefficients Amn and B are obtained.
As a column of mn, {A00, B00, A01, B01, A
A coefficient sequence A of 10, B10, A11, B11} is created. On the other hand, the coefficient sequence of the object stored in the object / function parameter storage unit 3 is taken out and a similar coefficient sequence is created. Then, in the function parameter difference calculation means 22, as shown in FIG. 5, the coefficient sequence is considered as a spectrogram, and the correlation of the individual waveform shapes is obtained (121).
In FIG. 5, reference numeral 50 represents the spectrogram of the input data. The candidate object selecting means 23 correlates the waveform with each of the spectrograms of the other three-dimensional objects stored in the object / function parameter storage unit 3 and takes out the one having a high correlation (1
22). Further, in FIG. 5, 51, 52, 53 ...
Are object # 1, object # 2,
The respective spectrograms of the three-dimensional objects of the objects # 3, ... Then, the spectrogram 50 of the input data and the respective spectrogram 5 of the three-dimensional object
The waveforms of 1, 52, 53, ... Are compared with each other, and the object having the largest correlation value is recognized as the final candidate having the same shape as the original data and is extracted (12
3). (Fourth Embodiment) Next, a fourth embodiment will be described. The fourth embodiment shows the invention according to claim 5.

FIG. 6 is a flow chart showing the flow of processing in the fourth embodiment. In the fourth embodiment, similar to the processing procedure of the third embodiment, the processing up to the fitting of the spherical harmonics is performed,
A coefficient sequence is calculated (100 to 110).

Next, the function parameter difference degree calculating means 22
Then, the value of the coefficient string is further normalized (130), and the normalized coefficient string is used to analyze the spectrogram 50 of the input data and the object as shown in FIG. Correlate the gram waveform (12
1). Then, by the candidate object selection means 23,
The most correlated object (eg object #
4, object # 5) is selected (122). The object # 4 and the object # 5 have substantially the same normalized spectrogram.
In FIG. 7, reference numerals 54 and 55 represent spectrograms of the object # 4 and the object # 5 before normalization, respectively. At this stage, an object similar in shape to the original data is selected.

When selecting one final object,
Next, the candidate object selecting means 23 calculates the distance D between each coefficient of these two objects and the coefficient obtained from the input data based on the equation (5), and the object having the smallest D is the original data. It is recognized that the object has a shape similar to (123).

As described above, according to the fourth embodiment, it is possible to select, from the coefficient sequences of the first low-order spherical harmonics, those having similar global shapes, and the order of the spherical harmonics can be selected. By increasing, the shape of the original data can be recognized while gradually judging the local similarity of shapes.

The present invention has been described above with reference to the embodiments.
The present invention can be variously modified according to the gist thereof. For example,
In the present embodiment, the superquadratic function is used as the function of the first approximate approximation. However, many functions for expressing a three-dimensional shape are conceivable, and any basic object expressing an object shape may be used. It is not limited to the superquadratic function. Further, in the present embodiment, an example in which an object is described by one function is shown, but by applying another division method and applying this method to individual parts, it is possible to make the object shape dependent. Without this, shape recognition is possible. Furthermore, in the present embodiment, when the waveforms of spectrograms are compared with each other, correlation is taken, but any method that can determine the similarity of the waveforms is acceptable, and the present invention is not limited to this.

[0055]

As described above, according to the present invention,
In the three-dimensional object shape description recognition method, not only the object is described by one function, but also by changing the function to be applied according to the object, a wider range of object shapes can be recognized. In addition, since the spherical harmonics are unbiased with respect to rotation, the shapes can be compared regardless of the posture of the object. Also, by using the spherical harmonic function, not only the similarity of local shapes but also global shapes can be compared. Although the spectrogram changes depending on the position of the origin, by using the function center coordinates obtained by approximating another function, it is possible to make a stable shape comparison even if the origin shifts. Further, by comparing the waveform shapes, it is possible to recognize an object having a similar shape as a similar shape object even if only objects having different sizes from the original data are stored in the storage unit.

[Brief description of drawings]

FIG. 1 is a configuration diagram of the present invention.

FIG. 2 is a processing flowchart of the first embodiment.

FIG. 3 is a processing flowchart of a second embodiment.

FIG. 4 is a processing flowchart of a third embodiment.

FIG. 5 is a conceptual diagram of a processing course.

FIG. 6 is a processing flowchart of a fourth embodiment.

FIG. 7 is a conceptual diagram of a processing course.

[Explanation of symbols]

1 data input unit 2 control unit 3 object / function parameter storage unit 4 display unit 20 function determining unit 21 function fitting unit 22 function parameter dissimilarity calculating unit 23 candidate object selecting unit 50 spectrogram of input data 51, 52, 53 three-dimensional Each spectrogram of the object 54,55 The spectrogram of the candidate three-dimensional object selected in the initial selection

Claims (5)

[Claims] 1. A first procedure for inputting three-dimensional shape data of a target object, a second procedure for accumulating and managing shape data of a three-dimensional object, and original data and a target model that has been accumulated in advance. In the three-dimensional object shape recognition method including a third step of comparing a shape with a candidate object and selecting a candidate object, the third step includes a step of applying a function to original data and a function to be applied in the step. A three-dimensional object shape description recognition method, comprising: a step of determining and a step of comparing parameter values of the fitted function. 2. The three-dimensional object shape description recognition method according to claim 1, wherein in the step of determining the function, a spherical harmonic function and a function representing a closed curved surface other than the spherical harmonic function are used. 3. The three-dimensional object shape description recognition method according to claim 2, wherein the order of the spherical harmonic function is made variable in the step of determining the function. 4. The three-dimensional object shape description according to claim 2, wherein in the step of comparing the values of the function parameters, the waveform of the spectrogram formed by the coefficient sequence of the spherical harmonic function is correlated. Recognition method. 5. The three-dimensional object shape description recognition method according to claim 4, wherein in the comparison of the spectrograms, normalized spectrograms are compared.