|
|
3D reconsruction from multiple views
Alexandre Goy
Microengeneering, February 2002
Professor: Michael Unser, Assistant: Thierry Blu
Biomedical Imaging Group, EPFL
|
|
|
We present here a 3D reconstruction algorithm for an object constituted of N points that can be used with a minimal set of three orthogonal projections (photograph for example) on planes of unknown orientation. This algorithm gives neither the spatial orientation nor the scale of the object but only determines its shape.
Twoapplication examples on real objects are given. We remark that, in real applications, the quality of reconstruction is limited above all by the limited resolution of the images and by the fact that it is not always possible to be in an orthogonal-projective situation. The algorithm itself gives a precision that only depends on the computer. Independently of the resolution, the recognition of points on a tridimensionnal object, between two views, is also a problem.
Situations can occurs where the matching of points on different views is unknown. This problem is encountered, for example, when the references points on an object are automaticaly detected by image processing operations. We propose in this work a procedure (in MATLAB) for the automatical matching of the points between two views. However, this algorithm remains slow because of the large amount of computing it supposes for the testing of all combinations and could'nt be used for real time vision without some adaptations.
|
|
 |
|
On this figure, we show the 3D points n1, n2, n3 and their projection onto planes n1', n2', n3' and n1'', n2'', n3''. G is the center of gravity of the object. By linearity, G', G'' are also the center of gravity of the projections P' and P''. We can use these points (G, G', G'',...) to define a coordinate system for measuring the position of the projected points. The views don't need to be orthogonal as it appears in this figure, in fact, as we said, the orientation of views is unknown. It is important to note that we need at least 3 views and 4 points for applying the algorithm.
|
|
|
|
Main steps in the algorithm:
- Build a measurement matrix S with the coordinates of the points in the views such that each pair of columns of S contains the X and Y coordinate vector of all N points in a view. S is consequently of size Nx2P. Moreover, it can be shown hat the rank of S is 3, and close to 3 in the presence of noise.
- Compute the singular value decomposition (SVD) of S in order to have: S = UDVt, where D is diagonal and t denotes the transpose. Since S is of rank 3, we can keep only the first 3 columns of U and V which become U' and V'.
- Build vectors Ai and Bi which are the i-th and i+1-th columns of V't.
- Solve the linear system of equation (2 equation for each view i): Ait*G0*Ai-Bit*G0*Bi=0, Ait*G0*Bi=0, where G0 is a 3x3 symetric matrix which contains 6 unknowns elements.
- When you have G0, compute G such that: G = U'*inv(G0)*U't.
- Digonalize G for calculating the shape of the object. G is, in fact a NxN matrix which contains all scalar poducts of the poisition vectors of the points. It can be shown that G is an invariant (conservation of scalar product under the change of orthonormal coordinate system).
|
|
|
|
- A bias can appear between real position of a point and its reconstruction. It means that the average of several reconstructions based on noised datas is not equivalent to the real object. However, this error remains low for a sufficient number of views.
|
|
- As the algorithm is based on orthogonal projections, the size of the object in the projection direction has to be small in comparison to the distance from the observer. One reduces the error when the field angle of the camera is small.
|
|
- The number of points has no importance for the quality of the reconstruction. The information for the reconstruction is contained in the views and not in the position of any other point.
|
The two figures besides show the evolution of standard deviation (on the right) and bias (on the left) in function of the number of points.
|
 |
|
| - The output noise decreases with the number of views, following the law: noise_out = 1/sqrt(noise_in). |
The two figures besides show the evolution of standard deviation (on the right) and bias (on the left) in function of the number of views. We can observe the good fitting of the left curve with the 1/sqrt(P) function. The bias is more difficult to bring into equation, but it decrease quite rapidly.
|
 |
|
- The angular proximity of views leads to increased scattering in the average projection direction (X in the tests).
|
On the left: Evolution of the standard deviation in each direction (s_x in blue, s_y in green, s_z in red) in function of the angle (in rad) between the views
On the right: Statistic s = sqrt(s_y^2+s_z^2)/s_x. When the views are angularly close, the standard deviation (scattering) in the X direction is the largest.
It is important to note that the behaviour of the statistic beyond 0.3-0.4 rad is highly dependent on the distribution of the views. The test has been made with a particular distribution, which is an arbitrary choice. Finally, the test is valid only for low angle (which is what we intend to test).
|
 |
|
|
Tests on real object
|
| Example 1: In this example, P = 4 and N = 148. The use of the algorithm supposes to:
- select the reference points on the image.
- pairing the points between each pair of views (making such that you know which point on a view corresponds the other on the second view).
- measure the coordinates of points in a system centered on the center of gravity of the points.
- Apply the algorithm to extract the 3D pattern.
|
|
Image |
Reconstruction |
|
 |
 |
|
| Example 2: Here, we want to compare the theory with the practise. To verify the improvement of reconstruction with an increasing number of views, we apply the algorithm on a set of eight points which define 5 length on the object. We then calculate the ratio k between the real length (measured on the object) and the reconstructed one. For ideal measurements, the value of k is the same for each segment. We then measure the satandard deviation of the 5 values of k obtained for each number of view, this value is a measurement of the quality of the reconstrucion. |
|
 |
 |
| Beside, on the left: the evolution of k with the nuber of views and on the right: the values of k for each segment. As we expect, the standard deviation of k decrease a lot. However, we see that it can also increase, which is explained probably by the fact that all points are not easy to recognize on every views. Too large uncertainty of point position in a view can have a dtrimental effect on the quality of reconstruction, even if there is an additional view. |
 |
|
