5. Reconstruction accuracy of tube-like objects
5.3 Cylinder fitting algorithm
In this section an algorithm that fits a cylinder to a set of points is presented and analyzed.
A cylinder is completely defined by its radius, and the line that runs through its center, referred in the followings as cylinder’s center line. The cylinder fitting problem can be solved by finding the center line and radius that minimize the sum of the squared distances between the set of points and the surface of the cylinder. Thus the fitting problem is performed in two steps: in the first step the central line is fitted to the points, and in the second step the optimal radius is computed. Once the center line is calculated, then the distance from a point to the cylinder surface can be obtained subtracting the radius from the distance from the point to the center line. Then the fitting problem becomes:
( )
where
R
*denotes the optimal radius of the fitted cylinder, N is the number of the points,{ p
i, i = 1 , N }
is the set of points, and cl is the estimated central line of the cylinder.In order to solve the above minimization problem, the central line has to be estimated. A line in 3D space is defined by a point on the line and a direction vector that specifies the direction of the line. As the line that optimally fits to a set of points passes through the centroid of the points, then only the direction of center line remains to be estimated.
If
∑
is the centroid of the points and d is the direction of the center line, then the equation of the center line is
c
0+ t * d
, where t is the parameter of the line.The remaining unknown, direction of the center line, can be very elegantly computed using Principal Component Analysis (PCA). PCA is a technique that reduces multidimensional datasets to lower dimensions, retaining only those characteristics of the dataset that contribute most to its variance. To determine the principal components of a dataset, the eigenvectors and eigenvalues of the dataset covariance matrix have to be computed. The eigenvectors with the largest eigenvalues correspond to the dimensions that have the strongest correlation in the dataset. For a deeper understanding of PCA technique, the reader is referred to [66, 67].
The direction vector of the cylinder’s center line is given by the coefficients of the first principal component. The second and third PCs are orthogonal to the first, and their coefficients define directions that are perpendicular to the line.
Several experiments are performed in order to evaluate the performance a cylinder fitting algorithm. In the first experiment it is tested the way the number of the points influences the radius of fitted cylinder. A variable number of points are randomly placed over the surface of a cylinder having a radius of 35 units and a length of 250 units. The number of the points varies between 5 and 500. No noise was added to the points. To be noted that in this experiment the length is much bigger than the diameter of the cylinder.
Figure 5.8 Fitted cylinder radius function of the number of points
Reconstruction accuracy of tube-like objects 83
The fitted cylinders radiuses are plotted against the number of the points in Figure 5.8. It is obvious that a small number of points results in a very bad estimation of the radius. This is due to the fact that the center line of the cylinder cannot be accurately estimated.
As the points are randomly distributed – and the same they are in a real configuration – there is no symmetry and centroid of the points doesn’t coincide with the center of the real cylinder, and thus the estimated center line has also a direction different of the real one. These can be seen in the Figure 5.9 – a closer look for 3 configurations corresponding to 10, 50, and 200 points.
The computed radiuses of the fitted cylinders are in this case: 26.8964, 34.1071 and 34.5704.
Figure 5.9 Left column: three configurations for 10, 50 and 200 points distributed over the surface of a cylinder. Right column: the center line of fitted cylinders
Figure 5.10 Fitted cylinder radius function of the number of the cylinder length
The second performed experiment shows the influence of the cylinder length on the fitted cylinder radius. A number of 200 points are randomly placed over the surface of a cylinder having a radius of 35 units and a length varying between 10 and 260 units. The results are depicted in Figure 5.10. It can be observed the estimation error of the radius is big when the length of the cylinder is smaller than its diameter. That happens because in that case the dominant direction of the variance is not anymore along the cylinder center line. This behavior can be seen in the Figure 5.11 for three different lengths of the cylinder: 30, 70 and 90.
It was shown that not all the configurations are well tolerated by the cylinder fitting algorithm. The estimation accuracy of the fitted cylinder highly depends on the number of the points and the ratio of cylinder length and diameter. The symmetry of the points’ distribution also affects the accuracy of estimation. For example, if a higher number of points are concentrated in the same area of the cylinder, they will influence more the position of the fitted center line. The cylinder fitting algorithm allows us to use the estimated radius as a measure of reconstruction accuracy. As it is, the algorithm doesn’t perform well for many general configurations, and will generate additional errors when measuring the reconstruction accuracy. On the other side, only the center line of the cylinder cannot be accurately estimated. As the reconstructed points are aligned to the
Reconstruction accuracy of tube-like objects 85
model points before estimating the reconstruction accuracy, then the best practice would be to skip the line fitting step and to use the center line of the model. Thus only the radius of the reconstructed points needs to be estimated.
Figure 5.11 The fitted cylinder center line for three different lengths of the cylinder: 30, 70, 90.