JP2000353244A - A method for obtaining a fundamental matrix, a method for restoring Euclidean three-dimensional information, and a three-dimensional information restoring apparatus. - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To provide a three-dimensional information restoring device capable of stably and accurately restoring Euclidean three-dimensional information from a plurality of images taken by an uncalibrated camera. A three-dimensional information restoration device includes an uncalibrated camera (3).
Image data 72 captured and anisotropically transformed by the
Means for obtaining a fundamental matrix by applying Kanatani's optimal estimation method, means 78 for obtaining a set of projective projection matrices from the basic matrices, and Euclidean projection from a two-dimensional projection coordinate system corresponding to each projective projection matrix. Means for obtaining a basis transformation matrix for a coordinate system in a general space, and means 80 for restoring Euclidean three-dimensional information using the basis transformation matrix. Means for obtaining a basis conversion matrix, estimating an initial value of an internal parameter of the uncalibrated camera from the projective projection matrix, and preparing an initial value of the basis transformation matrix; and a predetermined error evaluation function from the estimated initial value. Means for obtaining a basis conversion matrix by iterative calculation using

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to image processing for processing an image from a camera or the like, and in particular, to the field of image processing and image recognition for acquiring environmental information by processing an image, and to three-dimensional image processing. The present invention relates to the field of image measurement for measuring position and distance.

[0002]

2. Description of the Related Art References related to this field include the following.

[0003]

[Table 1]

[Definition of terms] Definitions of main terms used in this specification are described below.

[0005] An "uncalibrated camera" refers to a camera for which knowledge of the camera position, attitude, lens focal length, and the like cannot be obtained in advance.

The term "corresponding point" refers to an image position of the same point on an object in a plurality of images of the object.

[0007] "Projective Reconstruction
“ion)” refers to restoring three-dimensional information including a certain degree of uncertainty from a plurality of images photographed at different positions or different postures.

[0008] A "fundamental matrix" is a matrix of 3 rows x 3 columns, rank (rank) 2 that describes a geometric relationship between two images for projective restoration. Means

Here, "Euclidean restoration" refers to the restoration of three-dimensional information whose size is indefinite, although the shape of the target object can be known.

[0010] In the following description, the curly braces “{” and “}”, which are symbols indicating a set, are replaced by “<” and “< May be written as ">". [Summary of the Prior Art] The problem of capturing a target object with a camera and estimating three-dimensional information of the target object only from an image is a central problem in the fields of computer vision and image recognition. In particular, cameras for which knowledge of camera position, posture, lens focal length, etc. cannot be obtained in advance (called uncalibrated cameras)
Attention has been paid to a method of restoring three-dimensional information of a target object using an image captured in the above.

[0011] To apply these techniques,
The corresponding points need to be determined. Various methods have been proposed for obtaining corresponding points. In many cases, a location where the luminance of a pixel changes greatly in an image is extracted as an edge of the image, and calculation is performed using a correlation. Once the coordinates of the corresponding point on the image are determined, three-dimensional information of the target object can be obtained using the geometric projection relationship.

In order to restore three-dimensional information from an uncalibrated image, a plurality of images taken at different positions or at different postures are required. In addition, the three-dimensional information cannot be uniquely determined by this alone, and the restored information includes some kind of indefiniteness. The method of restoring three-dimensional information while leaving indefiniteness is a projective restoration (Projective Reconstruction).
ion). As an early paper on projective reconstruction [2]
And [10] are famous. [7] compares various projective reconstruction methods.

In order to perform projective restoration, it is necessary to first calculate a geometric relationship between two images. This relationship is described by a matrix of 3 rows × 3 columns and rank (rank) 2,
This matrix is called a fundamental matrix.

The calculation of the fundamental matrix is the first step for restoring three-dimensional information, but the calculation is not always easy. In particular, this calculation is greatly affected by noise included in the image, and therefore, it has been difficult to calculate the basic matrix with high accuracy. Therefore, [4] proposes a method that introduces the optimal evaluation function, calculates the fundamental matrix with high accuracy, and simultaneously evaluates its reliability. Also [9]
Evaluates the performance of various algorithms for calculating the fundamental matrix, proposes a calculation method with sufficient accuracy by taking various measures in numerical calculation.

If the basic matrix between the two images can be calculated, the relationship between the plurality of images can be described next. When information of three or more images is used instead of two, it is possible to perform Euclidean restoration with less indefiniteness instead of projective restoration. Euclidean restoration here means that you can know the shape of the target object,
Its size is indeterminate. In the Euclidean restoration, the length ratio, the angle, and the like of the object can be accurately restored.
A method for Euclidean restoration from three or more images obtained from an uncalibrated camera is realized by [8], [5], and [1].

[0016]

Among the methods for calculating the fundamental matrix, Kanatani's optimal estimation method proposed in [4] has excellent characteristics that accuracy and reliability are obtained at the same time. However, numerical instability remains. That is, in this method, if the iterative calculation converges, the basic matrix can be estimated with high accuracy. In addition, the method of [9] has a problem that the reliability of the fundamental matrix cannot be obtained.

In addition, all of the methods relating to Euclidean restoration have a problem in that numerical calculations are unstable, and good results cannot be obtained when applied to any image data.

Further, in the conventional technology, extraction of corresponding points,
There have been studies on improving the individual techniques of calculating the fundamental matrix and converting to Euclidean reconstruction, but none of them has been realized.

Therefore, it is an object of the present invention to define the fundamental matrix as
A method for obtaining a basic matrix that can accurately restore three-dimensional information from multiple images taken with an uncalibrated camera by calculating accurately and stably with its reliability, Euclidean three-dimensional information An object of the present invention is to provide a restoration method and a three-dimensional information restoration device.

Another object of the present invention is to enable stable and accurate conversion from projective restoration to Euclidean restoration so that three-dimensional information can be obtained from a plurality of images taken by an uncalibrated camera. To find the fundamental matrix that can be accurately restored, Euclidean 3
An object of the present invention is to provide a three-dimensional information restoring method and a three-dimensional information restoring apparatus.

Still another object of the present invention is to provide a three-dimensional information restoring apparatus which integrates a series of steps of extracting corresponding points from a plurality of images taken by an uncalibrated camera, calculating a fundamental matrix, and restoring in a Euclidean manner. It is to provide.

[0022]

According to a first aspect of the present invention, there is provided a method for obtaining a basic matrix describing a relationship between images from a set of corresponding points between images, the method comprising: Preparing three or more pieces of image data of the target object photographed by the camera at different angles, performing a predetermined anisotropic transformation on the image data, and performing a predetermined anisotropic transformation Calculating the fundamental matrix between each image by applying Kanatani's optimal estimation method to the obtained image data.

According to the present invention, prior to using Kanatani's optimal estimation method, anisotropic transformation is performed on the data, so that the accuracy of calculating the initial value in Kanatani's optimal estimation method is greatly improved. As a result, numerical calculations in Kanatani's optimal estimation method are stable, and more accurate calculations are possible.

According to a second aspect of the present invention, there is provided a method for restoring three-dimensional information in a Euclidean manner. A step of obtaining a set of projective projection matrices between pairs of images from the image data, and a basis transformation from a two-dimensional projective coordinate system corresponding to each projective projection matrix to a coordinate system in a Euclidean space A step of obtaining a matrix and a step of restoring Euclidean three-dimensional information from the image data using the basis transformation matrix, wherein the step of finding the basis transformation matrix comprises: Estimating an initial value of an internal parameter of the uncalibrated camera using a QR decomposition from a 3 × 3 small matrix, and preparing an initial value of a basis transformation matrix;
Obtaining a basis conversion matrix by iteratively calculating a predetermined error evaluation function from the estimated initial value and satisfying a constraint condition selected in advance so as not to converge to an obvious solution.

According to the method of the second aspect, Bougnoux
The disadvantage that the method converges to a trivial solution, which has been observed in the method described above, is removed, and a more stable and robust solution can be obtained.

According to a third aspect of the present invention, in addition to the configuration of the second aspect of the present invention, the step of obtaining a set of projective projection matrices includes the steps of: Determining a basis matrix that describes the relationship between the two, and determining a set of projective projection matrices that satisfy a predetermined matching condition based on the basis matrix. Preparing three or more pieces of image data obtained by photographing the target object from different angles, performing a predetermined anisotropic transformation on the image data, and converting the image data by a predetermined anisotropic transformation Calculating the fundamental matrix between each image by applying Kanatani's optimal estimation method to the image data.

According to the invention of claim 3, according to claim 2,
In addition to the operation and effect of the invention described in (1), prior to using Kanatani's optimal estimation method when obtaining the fundamental matrix, anisotropic transformation is performed on the data, so the initial value calculation in Kanatani's optimal estimation method The accuracy of the method is greatly improved. As a result, numerical calculations in Kanatani's optimal estimation method become stable,
The base matrix is obtained with higher accuracy, and as a result, the accuracy of Euclidean three-dimensional information is improved.

According to a third aspect of the present invention, there is provided a three-dimensional information restoration apparatus comprising three or more images of a target object taken from different angles, which are taken by an uncalibrated camera having square pixels and having no skew. Means for obtaining a set of projective projection matrices between pairs of images from data, and a basis transformation matrix from a three-dimensional projective coordinate system corresponding to each projective projection matrix to a coordinate system in a Euclidean space And means for performing Euclidean three-dimensional information restoration from the image data using the basis transformation matrix, wherein the means for finding the basis transformation matrix comprises: Estimating initial values of the internal parameters of the uncalibrated camera using QR decomposition from the left 3 × 3 small matrix of the canonical form,
Means for preparing an initial value of a basis transformation matrix, and means for obtaining a basis transformation matrix by iteratively calculating from the estimated initial value using a predetermined error evaluation function, a projective projection matrix The means for determining the set of
Means for obtaining a basic matrix describing a relationship between images from a set of corresponding points between images; and means for obtaining a set of projective projection matrices satisfying a predetermined matching condition based on the basic matrix. Means for preparing three or more sets of image data of the target object taken from different angles, taken by an uncalibrated camera, and a predetermined non- Including means for performing isotropic transformation and means for calculating a basic matrix between each image by applying Kanatani's optimal estimation method to image data transformed by a predetermined anisotropic transformation .

According to the fourth aspect of the present invention, the data is subjected to anisotropic transformation prior to using the Kanatani optimal estimation method in obtaining the fundamental matrix. The accuracy of value calculation is greatly improved. Furthermore, when a projective projection matrix is obtained from the fundamental matrix obtained in this way, and when Euclidean 3D information is restored, it converges to a trivial solution as seen in Bougnoux's method. Defects are eliminated. As a result, the numerical calculation in Kanatani's optimal estimation method is stable, and in addition to the fact that the fundamental matrix is obtained with higher accuracy,
Euclidean three-dimensional information can be obtained more stably, accurately, and robustly.

[0030]

DESCRIPTION OF THE PREFERRED EMBODIMENTS [Hardware Configuration] Hereinafter, a three-dimensional information restoration apparatus according to an embodiment of the present invention will be described. The three-dimensional information restoration device is realized by software executed on a computer such as a personal computer or a workstation. In FIG.
The appearance of the three-dimensional information restoration device is shown.

Referring to FIG. 1, the three-dimensional information restoring apparatus is a CD-ROM (Compact Disc Read-Only Memory).
Drive 50 and FD (Flexible Disk) drive 5
And a display 42 as a display device connected to the computer main body 40
And a keyboard 46 and a mouse 48 as input devices also connected to the computer main body 40, and a camera 30 connected to the computer main body 40 for capturing images. In the apparatus according to the present embodiment, a video camera is used as the camera 30, and a plurality of images obtained while moving the target object in front of the camera 30 will be described later.
It is assumed that dimension information restoration processing is performed.

FIG. 2 is a block diagram showing the configuration of the three-dimensional information restoration apparatus. As shown in FIG. 2, a computer main body 40 constituting the system 20 includes a CD-R
In addition to the OM drive 50 and the FD drive 52, CPUs (Central Process
ng Unit) 56, ROM (Read Only Memory) 58,
It includes a RAM (Random Access Memory) 60, a hard disk 54, and an image capturing device 68 for capturing an image from the camera 30. A CD-ROM 62 is mounted on the CD-ROM drive 50. An FD 64 is mounted on the FD drive 52.

As described above, the main parts of the three-dimensional information restoring device are computer hardware and CPU 56.
And software executed by the software. Generally, such software is FD drive 52, FD
CD-ROM stored in a storage medium such as CD-ROM
The data is read from the storage medium by the drive 50 or the FD drive 52 and temporarily stored in the hard disk 54. Alternatively, when the device is connected to a network, the data is temporarily copied to a hard disk 54 from a server on the network. Then, the data is further read from the hard disk 54 to the RAM 60 and executed by the CPU 56. Note that, when connected to a network, the RAM 60
May be directly loaded and executed. The hardware itself of the computer shown in FIGS. 5 and 6 is general. Therefore, the most essential parts of the present invention are the FD drive 52, the FD 64, and the hard disk 54.
Software stored in a storage medium such as

As a recent trend, a general method is to prepare various program modules as a part of an operating system of a computer, and an application program calls these modules as needed to advance processing. In such a case, the software itself for realizing the three-dimensional information restoration device does not include such a module, and the three-dimensional information restoration device is realized only when the computer cooperates with the operating system. However, as long as a general platform is used, it is not necessary to distribute software including such modules, and the software itself that does not include those modules and a recording medium on which the software is recorded (and the software is distributed on a network) Data signal in such a case) can be considered to constitute an embodiment.

Since the operation of the computer itself shown in FIGS. 1 and 2 is well known, detailed description thereof will not be repeated here. [Schematic Configuration] Referring to FIG. 3, in the apparatus of the present embodiment, a plurality of images are obtained by arbitrarily moving target object 70 in front of fixed camera 30 (uncalibrated camera). The three-dimensional information of the target object 70 shown there is restored from 72-1 to 72-ni. Or, from a plurality of images obtained by shooting the target object from different directions with a camera, 3
The dimensional information may be restored.

The apparatus according to the present embodiment restores three-dimensional information by using a method including the following three steps. (1) A plurality of images 72-1 of the target object 70
From to 72-n _i, searches the corresponding point between images are determined (74). From the correspondence relationship between (2) The obtained plurality of images 72-1 to 72-n _i, the aid of epipolar geometry, to restore the three-dimensional information in the three-dimensional projective space (76, 78). (3) Convert the obtained three-dimensional information in the three-dimensional projective space into three-dimensional information in the Euclidean space (8)
0).

Here, there is no restriction on the camera except that the image sensor is square. Even if the image sensor is not a square, the image sensor can be treated as a square by performing a predetermined conversion as described later.

Of the above-mentioned methods, the following points are of interest in the present embodiment. (1) In the calculation of the fundamental matrix (76), a combination of the prior art Kanatani's optimal estimation method [4] and Hartley's image normalization method [3] is used, and a more robust and stable solution can be estimated. Use a method. (2) In Euclidean three-dimensional reconstruction (80), a new method that avoids the disadvantage of Bougnoux's method [1] of converging to an obvious solution is used. (3) Combine input of images, search for corresponding points, and restoration of three-dimensional shapes to propose a consistent system.

[0039] Hereinafter, as an image 72-1 to 72-n _i in FIG. 7 is obtained will be described or carried out how the following process step 74. [Determination of Corresponding Points] First, the target object 70 is
Among a plurality of images 72-1 to 72-n _i obtained by photographing a, determines the corresponding points. Conventional methods can be used for this determination.

For example, in each image, a location where the luminance of a pixel changes greatly is extracted as an edge, and a continuous edge is extracted as an outline of an object. Of the extracted contours, a point having a large curvature is set as a candidate for a corresponding point, and the corresponding point is determined based on their correlation between images. [Calculation of Fundamental Matrix] First, mathematical expressions used in the calculation of the fundamental matrix will be described below. In the description, these formulas will be referred to as needed.

[0041]

(Equation 1)

It is assumed that the uncalibrated image x _j ⁽ⁱ⁾ is the coordinates of the j-th feature point of the image i in the two-dimensional projection space on the image. Further chi ^S, over the image set S, and the corresponding point pairs. For example, χ _j ^{1,2} = (x _j ⁽¹⁾ , x _j ⁽²⁾ )
χ _j ^{{1, 2}} ∈χ {1, 2}. However, {1, 2} represents a set of image numbers.

Let S be {1, 2,..., N _i }. If n _p (n
Given a set of corresponding points _p ^{S for} _p ≥ 9), Kanatani
By using the optimal estimation method [4], a fundamental matrix describing the relationship between two images can be calculated. Specifically, χ
^{{1, k}} , (k = 2, ..., n ⁱ ), | χ ^{{1 , k}} | = n _p , 3 × 3, ran
Calculate the fundamental matrix F _1k of k 2. In the fundamental matrix F _1k , Expression (1) holds for all pairs of corresponding points (x ⁽¹⁾ , x ^(k) ).

That is, equation (1) holds for all elements of χ ^{{1, k}} . In Kanatani's optimal estimation method, the normalized covariance matrix V ₀ [x _j ⁽⁾ of not only the pair of corresponding points χ ^{{1, k}} but also χ _j ^{{1, k}} ∈χ ^{{1, k} 1)} ] and V ₀ [x _j ^(k) ]. These matrices represent the distribution shape of the noise contained in x. The relationship between the actual covariance matrix V [x] of x and V ₀ [x] is as shown in Expression (2). Here, ε in the equation (2) is called a noise level, and represents the magnitude of noise. Here, it is assumed that V ₀ [x] = diag (1,1,0).
("Diag" represents a diagonal matrix with the elements in parentheses on the main diagonal.) This assumption is a good approximation if the noise on the coordinates of the image data is Gaussian noise. .

The advantage of Kanatani's optimal estimation method is that the fundamental matrix
The point is that not only can _F1k be calculated, but also the noise level _ε1k on the image data can be estimated. By using the noise level ε _1k , it is possible to statistically determine a threshold value for removing outliers (wrong association) of image data without using empirical values. .

The core of Kanatani's optimal estimation method is a numerical calculation method called a renormalization method. In this renormalization method,
First, an initial value is obtained by a linear solution. Then, iteratively calculate the solution until it reaches the true solution. in this way,
Convergence to a true solution is not always guaranteed, and divergence often occurs. The cause is considered to be a problem in the linear solution for calculating the initial value. That is, when the initial value and the true solution are significantly different, it is expected that the result of the iterative calculation will not converge.

Here, Hartley proposes in [3] a method of greatly improving the accuracy of the linear calculation method (Hartley).
(ley's image normalization method). This is a method of performing anisotropic conversion on image data in advance, and then calculating a basic matrix by linear calculation. This technique greatly improves numerical stability and accuracy. In the present embodiment, the combination of Hartley's image normalization method and Kanatani's optimal estimation method makes it possible to calculate the fundamental matrix more stably. FIG. 4 shows the flow of the processing.

Referring to FIG. 4, first, for all images i, x _j
⁽ⁱ⁾ Apply Hartley's anisotropic transformation to j = 1, ..., n _p (9
0). It is assumed that the matrix T _i is an anisotropic transformation matrix applied to the image i. Then, x _j ⁽ⁱ⁾ is transformed according to equation (3). Corresponding to this conversion, Kanatani's optimal estimation method
The normalized covariance matrix is also transformed as shown in equation (4). By applying Kanatani's optimal estimation method to the data subjected to the anisotropic transformation in this way (92), F _1k = T ₁ F ′ _1k T _k and a noise level ε _1k = ε ′ _1k are obtained. [Projective Restoration] Next, projective restoration will be described. The formulas used here are summarized first. In the following description, this formula will be referred to as needed.

[0049]

(Equation 2)

In the projective restoration, first, when a set of corresponding points of χ ^S and a basic matrix F _1k (k = 2,..., N _i ) are given, five corresponding points are selected from them. to select a set of Y ^S. This 5
From the set of points, projective projective matrix P _i, to calculate the _{P 2, P 3, Pn i} . Projective projective matrix P _i is used to describe an image i, the relationship between the three-dimensional projective coordinate system. Y ^S is selected so as to satisfy a predetermined condition such that no four points are on the same plane. FIG. 5 shows an example where n _i = 3, and FIG.
Shows the flow of this processing. Hereinafter, description will be made with reference to these drawings. The selection of the set of corresponding points and the calculation of the fundamental matrix therefrom correspond to step 100 in FIGS.

Here, a method of calculating the projective projection matrix P _i will be described (steps 102 to 10).
8). If no noise is present, as described in [9], from F _1k and y ^{{1, k}} , P ′ ₁ ^(k) , P ′ _k , k = 2,
..., n _i can be calculated (step 102) and y
P ′ ₁ ⁽²⁾ calculated from ^{1,2} and F ₁₂ , y ^{{1, k}} and F _1k , 2 ≠ k
P ′ ₁ ^(k) calculated from the values agree. That is, P ' ₁ ⁽²⁾ = P' ₁
^(k) . However, this is not true when noise is present.

Even in the presence of noise, in order to obtain a consistent set of projection matrices (P ₁ ,..., Pn _i ), P ′ ₁ ⁽²⁾
= P ' ₁ ^(k) H 4x4 homography matrix H that converts P' ₁ ^(k) to P ' ₁ ⁽²⁾ , such as _k2 , k = 2, ..., n _{i k2} is estimated (step 104). As shown in [3], any pair of projection matrices (P ' ₁ ^(k) , P' ^k ) = canonical form as ((I | 0), P ' _k X _1k ) Can be transformed and such a homography matrix X _1k is defined as in equation (5).

Therefore, the homography matrix H _k2 is obtained according to the equation (6). This homography matrix
Using H _k2 , a set of temporary projection matrices (P " ₁ , P" ₂ , ..., P "n _i )
= (P ' ₁ ^{( 2)} , P' ₂ H ₂₂ , ..., P'n _i H _ni2 )
06). This intermediate set of projection matrices (P " ₁ , P" ₂ , ..., P "
n _i ) to obtain a consistent projection matrix (P ₁ , ..., Pn _i ), the following Epipolar Adj
ustment) (step 108).

A set of intermediate projection matrices (P " ₁ , P" ₂ ,..., P "
n _i ) and the set of pairs of corresponding points χ ^S , P ” _i , i = 1, ..., n
_The error function shown in the equation (7) is minimized by the Powell method described in [6] while changing each of the eleven elements of _i . Where d used in equation (7) is
Is defined by The fundamental matrix is a set of projection matrices (P " _i , P" _k ), 1≤i <k using the method shown in [9].
Calculated from ≦ n _i.

X _j ⁽ⁱ⁾ = (u _j ⁽¹⁾ , v _j ⁽¹⁾ , 1), x _j ^(k) = (u _j ^(k) ,
v _j ^(k) , 1), and the projection matrices P ₁ and P _k , the method of [9] is again used to projectively restore X _j . p
Let ₁ ^[i] and p _k ^[i] be the i-th vectors of the matrices P ₁ and P _k , respectively. Then, the projective restoration is equivalent to singular value decomposition of the linear homogeneous equation shown in Expression (9) and finding its null space. That is, the eigenvector for the minimum eigenvalue of A ^T A is the solution. [9] states that this method is better than other projective reconstruction methods.

However, in the present invention, the robustness is further improved.
Therefore, the first and second rows of the matrix A have weights 1 / ω
₁₂And weights 1 / ω in the third and fourth rows₃₄Multiplied by
Solve weighted linear equations iteratively at each step
I did it. Where ω₁₂And ω ₃₄Is the formula (1)
0) is a value defined by (11).

By iteratively solving the weighted linear equation in this way, it is possible to give a geometrical meaning to this minimization. In other words, this operation minimizes the distance on the image between the extracted point on the image and the projected point of the projected restoration point _{Xj on} the image. [Euclidean Restoration] 3 as determined above
Given a set of × 4 projection matrices (P ₁ , ..., Pn _i ),
A set of 3 × 4 Euclidean projection matrices (P ₁ ,..., Pn _i ) corresponding to a real three-dimensional space must be calculated (step 80 in FIG. 7). The method will be described below. The formulas referred to in this description are listed below.

[0058]

(Equation 3)

[0059]

(Equation 4)

[0060]

(Equation 5)

The Euclidean projection matrix P _k , k = 1,
..., _ni are defined by equation (12). However, 3x
The three matrix A _k is a matrix of camera internal parameters, and T _k
Is a matrix of camera external parameters. More specifically, the matrix A _k is defined by equation (13).

The matrix T _k is defined by equation (14). The 3 × 3 matrix R _k appearing in the equation (14) is a rotation matrix, and t _k represents a translation vector.

The following two constraints exist for each P _k . From Expression (12), Expressions (15) and (1)
6) is obtained. Equations (15) and (16) can be used to associate the aspect ratio and skew with each row vector of the left 3 × 3 small matrix of matrix P _k . That is, the expressions (17) and (18) need to be satisfied.

The Euclidean projection matrix corresponds to a special case of the projective projection matrix. Therefore, the problem of obtaining a Euclidean projection matrix from a projective projection matrix is a problem in that a basis transformation matrix H (4 × 4, det (H)) from a projective coordinate system to a coordinate system of a Euclidean subspace is used. ≠
0).

Any projective projection matrix P _{k represents the} projection of an image, which is a two-dimensional projection space, onto the same three-dimensional projection space coordinate system. Therefore, according to equation (19)
x _j ^k = (u _j ^(k) , v _j ^(k) , 1) can be obtained. However where the matrix _{P k = P k H, k} = 1, ..., n i is the Euclidean projective _{^{matrix, H -1 X j, j =}} 1, ..., n p is restored to It should be Euclidean three-dimensional information.

In the following description, it is assumed that the camera has a square pixel (ie, aspect ratio = 1),
It is assumed that there is no skew. As described in Expression (13), s _u ^(k) and s _v ^(k) represent the size of a pixel. In this case, s _u ^(k) and = s _v ^(k) , and γ ^{(k )} = 0. Therefore, α ^(k) = _αu ^(k) = _αv ^(k) . If the use of the camera not square pixel ^{_{s u (k), = s}} v (k) but does not hold, the transformation matrix diag (1 of the corresponding point projective coordinates x ^(k) 3 × 3,
By multiplying by s _v ^(k) , / s _u ^(k) , 1), the following description can be applied.

To find the homography matrix H for a square pixel and skew-free camera, Bougnoux
Method [1] is used. In [1], a parameterized basis transformation matrix Q (α, q) is estimated from a set of canonical forms of projective projection matrices (see Equation (20)). X is represented by the formula (5)
Assuming that the matrix satisfies the equation (21) estimated in the same way as the above, H is obtained as the equation (22).

In [1], during the initialization process, A ₁ = A _k is assumed for all k, and the image center (u ₀₎ of the first image is assumed.
Α ⁽¹⁾ is obtained by solving the Kruppa equation, assuming ⁽¹⁾ , v ₀ ⁽¹⁾ ) as (0, 0). Also, by selecting the initial value of the Euclidean projection matrix to (A ₁ | 0), the initial value of Q (α, q) (Equation (22)) can be changed to (A ₁ | 0) = (I | 0). ) Q (α,
q). A ₁ = A for all k
_{Since k} and α = α ⁽¹⁾ , the initial value of Q (α, q) can be uniquely determined except for q. As in [1], q '= A ₁ q
In other words, a linear equation is created from A ₁ and the set of canonical forms shown in equation (20), and q ′ can be solved. If q ′ is obtained, q is obtained by solving q ′ = A ₁ q with respect to q.

Here, q ′ and its covariance matrix COV [q ′]
The best results were obtained when was solved by the weighted least squares method. This solution uses a weight according to the indefiniteness of q ′, and is calculated using an iterative method and singular value decomposition. A solution is obtained in approximately two to three iterations. This solution has larger residuals but much less uncertainty than other general solutions.

In [1], in order to impose the constraint conditions of equations (23) and (24), nonlinear minimization is performed while changing α and q. However, in the Euclidean case, the constraints in equations (17) and (18) are not sufficient.
This is because there is a trivial solution (Equation (25)) that satisfies the right sides of Equations (23) and (24).

Therefore, equation (23) must be replaced with equation (26). Expression (24) holds only when Expression (27) holds.

In the present embodiment, the error function shown in equation (28) is minimized in order to correctly minimize it. The Powell method [6] is used for this minimization. From this linear equation, it can be seen that the required number of images is a minimum of three ([1]). [Experimental results and evaluation]-Fundamental matrix calculation Kanatani's optimal estimation method and Ha
In order to confirm the superiority of the combination method with rtley's image normalization method, we compared the four other methods described in [9] with the method adopted by the present invention, including Kanatani's optimal estimation method did. The method compared is as follows. (1) Linear method. The elements of the fundamental matrix are represented by a 9-dimensional vector f
And solved by reducing the calculation of f to an eigenvalue problem. {F} = 1 is normalized. (2) Hartley's anisotropic transformation and linear solution (3) Non-linear solution to minimize the distance between each point and the corresponding epipolar line (4) Similar to nonlinear solution 3 (5) Kanatani's optimal estimation method (6) An improved Kanatani's optimal estimation method (the present invention) In the experiment, 100 corresponding point data generated by computer were used. Then, the epipole position of each image was obtained by using each method, and the result was compared with the accurate position. Table 2 shows the results. Here, the position of the true epipole is shown at the top of Table 2. Zhang [9] for method (1) to method (4)
This is the method that has been compared. From Table 2, method (2)
(3) It can be seen that the accuracy of (6) is outstanding compared to the others. In addition, as shown in Table 2, the position closest to the accurate epipole position (the top row in Table 2) is the result of applying the method (6) according to the present invention.

[0073]

[Table 2]

Table 3 shows the mean square error (RMS) of the epipole coordinates of each method. Here, the value entered in the column of "method 0" represents an accurate value.

[0075]

[Table 3]

As shown in Table 3, only the methods (5) and (6) can obtain the noise level. Moreover, it can be easily seen from Table 3 that the method (6) represents a more accurate noise level. -Euclidean three-dimensional reconstruction Among several experimental results, the experimental results of restoring the Euclidean three-dimensional structure of a patterned rigid object are shown.
FIG. 7 shows n _i = 6 images, and FIG. 8 shows a set of n _p = 50 corresponding points. Using these corresponding points, a series of processes such as obtaining a fundamental matrix and performing Euclidean restoration was performed. Since n _i = 6 ≧ 3 and n _p = 40 ≧ 9,
The number of data is enough. As further shown in FIG.
Looking at these six images, it can be seen that the position and orientation of the target object in each image are sufficiently different and are suitable for Euclidean restoration.

As a premise of this processing, it is assumed that there is only an uncertainty in the position of the corresponding point and there is no mistake in the corresponding relation. 5 sets of images χ ^{{1, k}} , k =
First, when the fundamental matrix is calculated using the fundamental matrix calculation method according to the present invention by using 2, ..., 6, the noise level ε _1k ∈
[0.51, 0.68], and the epipolar geometry could be estimated with subpixel accuracy for all k.

Further, the basis of the three-dimensional projection space is a set of five corresponding points χ ^S , j in the corresponding point set Y ^S (S = {1,..., 6}).
∈ {10, 22, 38, 8, 35}. As is clear from FIG. 7, it can be seen that none of these five points is on a plane or almost on a plane. Therefore, it can be understood that these points can theoretically be the basis of good projection coordinates.

Now, paying attention to the upper 2 × 4 small matrix on P ″ _k , the change of the n _i · (2 · 4) elements is 1.51% at maximum with respect to the initial value. _In the lower 1 × 4 matrix of _k , this n
_i・ (1 ・ 4) elements change 0.06% max.
Met.

From this result, it is possible to obtain a projective projection matrix that can explain a set of corresponding points of 40 images with sub-pixel accuracy. In addition,
The × 4 small matrix represents the plane at infinity, and this plane corresponds to the intrinsic parameters of the camera. That is, the inclination of this plane at infinity is calculated by the nonlinear epipolar correction method.
This means that the estimation was performed with an accuracy of 0.02 ° or less.

Here, Bo is applied to the six images shown in FIG.
The Euclidean restoration method by ugnoux method was applied. Here, α ^(k) = f ^(k) / s _u ^(k) = 7.5 / 0.0099 [pixel / mm]
Was given as a constant. Further, the image center of the first image was set at (u ₀ ⁽¹⁾ , v ₀ ⁽¹⁾ ) = (320, 240). After performing the nonlinear minimization in this way, camera internal parameters as shown in the following Table 4 were obtained. In Table 4, each row represents an image number.

[0082]

[Table 4]

Ideally, α ^(k) is set to 1.0, and γ ^(k) and s ^(k)
Should be 0 in each case. Further, since each image is photographed by the same camera, the focal length f ^(k) should be constant. Actually, of course, noise is always present in the image, so an accurate value cannot be obtained. However, as shown in Table 4, according to the present invention, the focal length is an ideal value of 757.6.
Is obtained.

FIG. 9 shows the result of the Euclidean restoration performed in this manner. The target object is a box-shaped object as shown in FIG. As shown in FIG. 9, the three surfaces of the restored three-dimensional shape are planes and are orthogonal to each other, and it can be seen that the shape of the target object shown in FIG. 7 has been accurately restored.

As described above, according to the present invention, using a set of corresponding points of an image, a Euclidean 3
The dimensional shape can be restored. In particular, in the fundamental matrix calculation, we succeeded in obtaining a more robust and stable solution by applying the anisotropic transformation found in Hartley's image normalization method to Kanatani's optimal estimation method. Further, even in terms of precision, a technique comparable to the other techniques considered to have the highest accuracy was obtained.

Further, as for the Euclidean three-dimensional shape reconstruction, Bougnoux's method was improved, and a solution with less indefiniteness could be calculated by using an iterative least squares method. Furthermore, it became possible to prevent Bougnoux's method from converging to a trivial solution at the stage of nonlinear optimization.

The embodiments disclosed this time are to be considered in all respects as illustrative and not restrictive. The scope of the present invention is defined by the terms of the claims, rather than the description above, and is intended to include any modifications within the scope and meaning equivalent to the terms of the claims.

[Brief description of the drawings]

FIG. 1 is an external view of a system according to an embodiment of the present invention.

FIG. 2 is a block diagram illustrating a hardware configuration of a system according to an embodiment of the present invention.

FIG. 3 is a flowchart showing a data flow and a processing flow in the system according to the embodiment of the present invention;

FIG. 4 is a flowchart of a basic matrix calculation process.

FIG. 5 is a diagram schematically illustrating a process of performing projective three-dimensional restoration from image data.

FIG. 6 is a flowchart of a process of performing projective three-dimensional restoration.

FIG. 7 is a diagram showing six images used in the experiment.

FIG. 8 is a diagram showing a set of corresponding points obtained in an experiment.

FIG. 9 is a schematic diagram showing a result of Euclidean restoration in an experiment.

[Explanation of symbols]

20 three-dimensional information reconstructing apparatus 30 camera 70 object 72-1 to 72-n _i image

────────────────────────────────────────────────── ───

[Procedure amendment]

[Submission date] August 18, 2000 (2000.8.1)
8)

[Procedure amendment 1]

[Document name to be amended] Statement

[Correction target item name] 0007

[Correction method] Change

[Correction contents]

[0007] "Projective Reconstruction
"ion)" refers to restoring three- dimensional information from a plurality of images taken at different positions or at different orientations, including certain indeterminacy.

[Procedure amendment 2]

[Document name to be amended] Statement

[Correction target item name] 0010

[Correction method] Change

[Correction contents]

[0010] photographing the target object [SUMMARY OF PRIOR ART In the camera, the problem of estimating the three-dimensional information of the target object only from the image, computer vision, a central problem in the field of image recognition. In particular, attention has been paid to a method of restoring three-dimensional information of a target object using an image captured by a camera (called an uncalibrated camera) for which knowledge of the camera position, posture, lens focal length, and the like cannot be obtained in advance. ing.

Continued on the front page (72) Inventor Keisuke Kinoshita 5 Shiraya, Inaya, Seika-cho, Soraku-gun, Kyoto Prefecture F-term in ATI Human Information and Communication Research Laboratories (reference) 2F065 AA04 AA12 AA53 BB05 DD03 DD04 FF04 FF42 JJ03 JJ09 JJ26 QQ00 QQ17 QQ18 QQ21 QQ24 QQ32 QQ34 QQ42 SS13 UU05 5B057 BA02 CA12 CA16 CC01 DA20 DB02 DC16 DC32 5L096 CA04 EA18 FA06 FA12 HA01

Claims (4)

[Claims] 1. A method for obtaining a basic matrix describing a relationship between images from a set of corresponding points between images, comprising three images of a target object taken from different angles, taken by an uncalibrated camera. Preparing the above image data, performing a predetermined anisotropic transformation on the image data, and applying Kanatani's optimal estimation method to the image data converted by the predetermined anisotropic transformation. Applying to calculate a fundamental matrix between each image. 2. A projective projection matrix between a pair of images from three or more image data obtained by photographing an object from different angles and photographed by an uncalibrated camera having square pixels and having no skew. And a step of obtaining a basis transformation matrix from a two-dimensional projection coordinate system corresponding to each of the projective projection matrices to a coordinate system of a Euclidean space, and from the image data using the basis transformation matrix Restoring Euclidean three-dimensional information, wherein the step of obtaining the basis transformation matrix is performed by using the left 3 × 3 small matrix of the canonical form of the projective projection matrix as Q
Estimating an initial value of an internal parameter of the uncalibrated camera using an R-decomposition and preparing an initial value of a basis transformation matrix; and iteratively calculating from the estimated initial value using a predetermined error evaluation function. Obtaining a basis transformation matrix according to Eq. (3). 3. The step of obtaining a set of projective projection matrices includes: obtaining a basic matrix describing a relationship between images from a set of corresponding points between images; Obtaining a set of projective projection matrices satisfying the matching condition, wherein the step of obtaining the basic matrix comprises: obtaining three or more pieces of image data of the target object taken from different angles, taken by an uncalibrated camera. Preparing, and performing a predetermined anisotropic transformation on the image data, and applying the Kanatani optimal estimation method to the image data converted by the predetermined anisotropic transformation to each image. Calculating a basic matrix between the three-dimensional information. 4. A projective projection matrix between a pair of images from three or more image data obtained by photographing an object from different angles and photographed by an uncalibrated camera having square pixels and having no skew. Means for determining a set of..., A means for determining a basis transformation matrix from a two-dimensional projective coordinate system corresponding to each projective projection matrix to a coordinate system of a Euclidean space, and using the basis transformation matrix. Means for restoring Euclidean three-dimensional information from the image data, wherein the means for obtaining the basis transformation matrix is based on a left 3 × 3 small matrix of a canonical form of the projective projection matrix. Q
Means for estimating the initial values of the internal parameters of the uncalibrated camera using the R-decomposition and preparing an initial value of the basis transformation matrix; and iterative calculation using a predetermined error evaluation function from the estimated initial values. Means for determining a basis transformation matrix by calculating the basis matrix describing a relationship between images from a set of corresponding points between the images. Means for obtaining a set of projective projection matrices satisfying a predetermined matching condition based on the basic matrix, wherein the means for obtaining the basic matrix is captured by an uncalibrated camera. Means for preparing three or more image data obtained by photographing the target object from different angles, means for performing a predetermined anisotropic conversion on the image data, and the predetermined anisotropic conversion Thus for the converted image data, and means for computing the fundamental matrix between the images by applying the optimum estimation of Kanatani, restoration apparatus of three-dimensional information.