An Accurate Linear Method for 3D Line Reconstruction for Binocular or Multiple View Stereo Vision

Abstract

For the problem of 3D line reconstruction in binocular or multiple view stereo vision, when there are no corresponding points on the line, the method called Direction-then-Point (DtP) can be used, and if there are two pairs of corresponding points on the line, the method called Two Points 3D coordinates (TPS) can be used. However, when there is only one pair of corresponding points on the line, can we get the better accuracy than DtP for 3D line reconstruction? In this paper, a linear and more accurate method called Point-then-Direction (PtD) is proposed. First, we used the intersection method to obtain the 3D point’s coordinate from its corresponding image points. Then, we used this point as a position on the line to calculate the direction of the line by minimizing the image angle residual. PtD is also suitable for multiple camera systems. The simulation results demonstrate that PtD increases the accuracy of both the direction and the position of the 3D line compared to DtP. At the same time, PtD achieves a better result in direction of the 3D line than TPS, but has a lower accuracy in the position of 3D lines than TPS.

1. Introduction

The 3D line reconstruction is a basic problem in computer vision and optical measurements. It is widely used in computer vision problem, such as 3D scene reconstruction, non-cooperative target reconstruction and pose estimation for symmetric targets. Line features in the image are robust, stable, and easy to extract; the corresponding lines and points are often used in 3D reconstruction. In the position and attitude estimation for the non-cooperative target, the non-cooperative target is often reconstructed by points, lines, rectangles, or other shapes composed of lines, then the reconstructed model is used for tracking and relative pose estimation in subsequent frames. In pose estimation for the long symmetrical target, such as rockets and missiles, the direction of the target’s central axis is often used to represent the target’s attitude, which is often reconstructed by the Direction-then-Point (DtP) method. From the above analysis, we can determine that the accuracy of the 3D line is of significance for computer vision.

There are many studies on the reconstruction and measurement of non-cooperative targets [1,2,3,4,5,6,7,8,9,10,11] or attitude measurement of long symmetric targets based on binocular or multiple stereo vision. There are many kinds of non-cooperative targets to be reconstructed, especially targets in the space, such as satellites and spacecrafts. Many of them are based on feature points [2], point clouds [3,4], ellipses, circles [5,6] and line structures [7,8], and so on. However, the number of the feature points is huge, and the matches between them are more complicated and less robust than the feature lines. The ellipses and circles are more difficult to extract than the feature lines. There always are obvious line features on the target. After the corresponding line matching, the reconstructed line can be used to reconstruct the target.

At present, there is not much research on 3D line reconstruction. For binocular stereo vision, the plane intersection method [12] and Two Points (TPS) are the main two methods for line reconstruction. The principle of the plane intersection method is that the 3D line locates on the plane consisting of the optical center and the line segment in the corresponding image. The intersection line of the planes of the two cameras can be calculated. We can obtain a point on the line; therefore, we also call this method Direction-then-Point. TPS is a direct method for 3D line construction. It utilizes two pairs of corresponding image points on the 2D line (generally, they are the endpoints), then two 3D points on the line can be calculated, and the 3D line is uniquely determined. Obviously, this method does not utilize the information of the 2D line, and its accuracy depends on the points’ accuracy. DtP has a lower requirement for not needing corresponding points on the 2D line. Because the degeneracy of 3D lines is more severe than for 3D points, only 3D points on the baseline cannot be reconstructed, and the 3D line coplanar with the baseline cannot be reconstructed [13]; when the 3D line is close to coplanar with the baseline, the TPS can achieve higher accuracy than the DtP method. For a multiple camera system, the iterative method [13] based on minimizing the distance between the extracted line segment in the image and the line projected to the image is used. The reconstructed line is used by many other algorithms in computer vision. Many scholars analyze the influence of camera position, intersection angle, and relationship between the line and camera’s imaging plane on the accuracy of the reconstruction result of the 3D line [11,12,13,14,15,16,17,18,19,20]. For 3D line reconstruction in stereo vision, the optimal condition is that the angle between the optical axes of the two cameras is 90 degrees, and the 3D line is parallel to both imaging planes of the two cameras and perpendicular to, not coplanar with, the baseline [18]. However, because the baseline of the stereo cameras is always short relative to the target distance, the requirement for two cameras with near-vertical optical axes cannot be satisfied. At the same time, because the 3D lines on the target always form a certain structure, such as a triangle, a quadrangle, etc., the requirement that every 3D line be nearly parallel to the imaging plane cannot be satisfied too.

As can be seen from the above description, DtP only uses line information and does not need corresponding points’ information, but it has low position accuracy because it does not use the position information of the cameras. TPS uses two pairs of corresponding points; therefore, it can achieve better positional accuracy than DtP. However, it is difficult to obtain two pairs of corresponding image points under certain conditions. Considering the above situation, we proposed a novel method for line reconstruction based on a pair of corresponding image points and the 2D line direction. Firstly, we used the intersection method to obtain the 3D coordinates in the world coordinate system from the corresponding image points [21,22,23]. Secondly, we used this point as a point on the line to be solved to calculate the direction of the line. The point on the line is obtained before the line direction, thus call this method is named Point-then-Direction (PtD). The differences between the DtP, PtD and TPS methods are shown in

Table 1. The differences between Direction-then-Point (DtP), Point-then-Direction (PtD) and Two Points (TPS) methods.

Difference	DTP	PtD	TPS
Pairs of corresponding image points	0	1	2
Can be reconstructed while the line is coplanar with the baseline (no point on the baseline)	×	×	✓
Can be reconstructed while the line is coplanar with the baseline (one point on the baseline)	×	×	×
Use of the camera’s optical center	×	✓	✓
Use of the information of the 2D line	✓	✓	×

.

The simulation results demonstrated that PtD can achieve more accurate results, both on direction and position than DtP, because it combines the information of the corresponding image points. At the same time, it can achieve a more accurate direction but less accurate position than TPS. If there is only one pair of corresponding image points on the line, the linear method proposed in this paper can achieve better results.

2. Direction-then-Point Method

2.1. Stereo-Vision Scenario

A pinhole camera model [12] was used in this study. As shown in Figure 1, The world coordinate system is $O_w-X_w{Y}_w{Z}_w$, which is a right-handed coordinate system. The image coordinate system is $O_i-X_i{Y}_i$, $O_i$ in the top left corner of the image, $X_i$ faces right, and $Y_i$ faces down. The camera coordinate system is $O_c-X_c{Y}_c{Z}_c$, where $O_c$ is the camera’s optical center. The z-axis is pointing in the positive direction of the optical axis; the x-axis is perpendicular to the z-axis horizontally to the right; and the y-axis is perpendicular to the x-axis and to the z-axis, whose direction is determined by the right-handed definition criterion.

2.2. Plane Representation by a Single Camera

As shown in Figure 1, AB is the 3D line $I$, C₁ and C₂ are the optical centers of the two cameras, A₁B₁ is the projection of $I$ on camera C₁, and A₂B₂ is the projection of $I$ on camera C₂. When atmospheric refraction is not considered, we can assume that $I$ is on the plane C₁A₁B₁ and also on the plane C₂A₂B₂. Therefore, if we can attain both of the planes’ equations in the world coordinate system, then we can obtain the direction of the 3D line and a point on the line.

Next, we derive its expression by taking a camera as an example. The equation of the line in the image coordinate system is:

$${\mathit{A}}^T\mathit{X}=0$$

(1)

where $\mathit{A}={\left[\begin{array}{ccc}a& b& c\end{array}\right]}^T$ and $\mathit{X}={\left[\begin{array}{ccc}x& y& 1\end{array}\right]}^T$. The image plane is the $z_c=f$ plane in the camera coordinate system, where $f$ is the physical focal length of the camera. The z-axis of the camera coordinate system passes through the principal point of the image plane $\left(C_x,C_y\right)$, so the transformation from the image coordinate system to the camera coordinate system is determined as:

$$\{\begin{array}{c}{x}_c=\left(x-C_x\right)d_x\\ y_c=\left(y-C_y\right)d_y\end{array}$$

(2)

where $\left(x_c,y_c\right)$ is in the camera coordinate system, $\left(x,y\right)$ is in the image coordinate system, and $\left(d_x,d_y\right)$ is the actual physical size of the camera pixel.

The line in the image can be expressed in the camera coordinate system as:

$$\{\begin{array}{c}a\left(\frac{x_c}{d_x}+C_x\right)+b\left(\frac{y_c}{d_y}+C_y\right)+c=0\\ z_c-f=0\end{array}$$

(3)

The equivalent focal length of the camera is abbreviated as:

$$\{\begin{array}{c}{F}_x=f/d_x\\ F_y=f/d_y\end{array}$$

(4)

The plane equation can be summarized as:

$$F_x{x}_c+b{F}_y{y}_c+\left(a{C}_x+b{C}_y+c\right)z_c=0$$

(5)

Given the parameter matrix $\mathit{n}={\left[\begin{array}{ccc}a{F}_x& b{F}_y& a{C}_x+b{C}_y+c\end{array}\right]}^T$, the plane equation is then rewritten as:

$${\mathit{n}}^{\mathit{T}}{\mathit{P}}_{\mathit{c}}=0$$

(6)

where ${\mathit{P}}_{\mathit{c}}={\left[\begin{array}{ccc}{x}_c& y_c& z_c\end{array}\right]}^T$ is a point from the camera coordinate system, and $\mathit{n}$ is the normal vector of the plane. $\mathit{R}$ and $\mathit{t}$ are the rotation matrix and the translation vector from the world coordinate system to the camera coordinate system, respectively. Therefore, the point in the world coordinate system can be transformed to the camera coordinate system using Equation (7).

$${\mathit{P}}_{\mathit{c}}=\mathit{R}{\mathit{P}}_{\mathit{w}}+\mathit{t}$$

(7)

where ${\mathit{P}}_{\mathit{w}}={\left[\begin{array}{ccc}{x}_w& y_w& z_w\end{array}\right]}^T$ is a point in the world coordinate system. The plane equation in the world coordinate system can then be derived as:

$${\mathit{n}}^{\mathit{T}}\mathit{R}{\mathit{P}}_{\mathit{w}}+{\mathit{n}}^{\mathit{T}}\mathit{t}=0$$

(8)

2.3. Plane Intersection

The plane equations of the two cameras, respectively, are:

$$\{\begin{array}{c}{\mathit{n}}_{\mathbf{1}}^{\mathit{T}}{\mathit{P}}_{\mathit{w}}+d_1=0\\ {\mathit{n}}_{\mathbf{2}}^{\mathit{T}}{\mathit{P}}_{\mathit{w}}+d_2=0\end{array}$$

(9)

The 3D line $\mathit{I}=\left(l,m,n\right)$ must be located on these two planes. Therefore, the direction vector of $\mathit{I}$ can be solved as:

$$\mathit{I}={\mathit{n}}_{\mathbf{1}}^{\mathit{T}}\times {\mathit{n}}_{\mathbf{2}}^{\mathit{T}}= \left[\begin{array}{ccc}i& j& k\\ {\mathit{n}}_{11}& {\mathit{n}}_{12}& {\mathit{n}}_{13}\\ {\mathit{n}}_{21}& {\mathit{n}}_{22}& {\mathit{n}}_{23}\end{array}\right].$$

(10)

A 3D line can be uniquely determined by a point and the direction vector. Therefore, we chose the foot point $P_0\left(x_0,y_0,z_0\right)$ from the $O_w$ to the $\mathit{I}$; $\left(l,m,n\right)\ast P_0{}^T=0$. $P_0$ can be solved by $\left(l,m,n\right)\ast P_0{}^T=0$ and Equation (9). The point is directly solved by direction, and as a result the overall accuracy mainly depends on the accuracy of the line direction.

3. Point-then-Direction Method

3.1. Stereo Vision Scenario for PtD

As shown in Figure 1, Camera C₁ and Camera C₂ observe the line $I$ from different directions, and the projections on the image are A₁B₁ and A₂B₂, respectively. In this paper, we assume that one of the two endpoints of the line segments are the corresponding image points, i.e., A₁ and A₂ are the corresponding image points, or B₁ and B₂ are the corresponding image points. If the camera parameters and the line extracted from the image are error-free, the 3D point will be on the line obtained by the DtP, and then the results obtained by the DtP and Ptd are same. However, if either the camera parameters or the line extracted from the image have an error, the 3D point may not be on the line $\mathit{I}$.

In a similar manner to the image-space residual method for camera calibration, the line $\mathit{I}$ was projected to the image plane according to the theoretical model, and the angle between the projection and the 2D line extracted on the image plane was considered as the angle residual. We also minimized the square sum of all the angles. In this paper, this term is called the IAR. As shown in Figure 2, the C₂A₂B₂ plane is the plane composed of the optical center and the axis of the camera; A’B’ is the 3D line; B₂A₃ is the projection of A’B’ on the image plane; and α is the image angle residual.

From the above definition and stereo-vision scenario, we can ascertain that the 3D line passes through the 3D point, and the intersection of the plane composed of the 3D line and the camera’s optical center and the corresponding imaging plane is parallel to the 2D line on the image. For a multiple camera system, we can obtain the least square solution.

The mathematical expression is derived below.

3.2. Image-Space Angle Residual

3.2.1. Definition of the Problem

It is assumed that the direction of the 3D line $\mathit{I}$ is$\left(l,m,n\right)$, and $\mathit{I}$ passes through a point ${\mathit{P}}_{\mathbf{0}}\left(x_0,y_0,z_0\right)$ in the world coordinate system. It is easy to see that $\mathit{I}$ also passes through the point ${\mathit{P}}_{\mathbf{1}}\left(x_0+l,y_0+m,z_0+n\right)$. In this paper, the ${\mathit{P}}_{\mathbf{0}}$ is obtained by the intersection method of minimizing the distance from the spatial point to the back projection ray to obtain the three-dimensional coordinates from the corresponding image points ${\mathit{A}}_{\mathbf{1}}$ and ${\mathit{A}}_{\mathbf{2}}$ [24]. The plane of each camera passes through the point ${\mathit{P}}_{\mathbf{0}}$,${\mathit{P}}_{\mathbf{1}}$ and the corresponding optical center. The plane consisting of $\mathit{I}$ and the optical center of the ith camera can be expressed as:

$$\left|\begin{array}{cccc}x& y& z& 1\\ O{x}_i& O{y}_i& O{z}_i& 1\\ x_0& y_0& z_0& 1\\ x_0+l& y_0+m& z_0+n& 1\end{array}\right|=0$$

(11)

Or

$$\left|\begin{array}{cccc}x& y& z& 1\\ O{x}_i& O{y}_i& O{z}_i& 1\\ x_0& y_0& z_0& 1\\ l& m& n& 0\end{array}\right|=0$$

(12)

where $\left(O{x}_i,O{y}_i,O{z}_i\right)$ is the optical center of the ith camera. The plane equation after simplification is:

$${\mathit{n}}_{wi}{}^{\mathit{T}}{\mathit{P}}_w+d_i=0$$

(13)

It can be seen from Equation (12) that ${\mathit{n}}_{wi}$ can be represented linearly by $\mathit{I}$. Letting the relationship matrix be M:

$${\mathit{n}}_{wi}{}^T={\mathit{I}}^{\mathit{T}}{M}_i$$

(14)

It is obvious that M is a full rank matrix. Assuming the transformation matrix from the world coordinate system to the camera coordinate system is $\left[\begin{array}{cc}{\mathit{R}}_i& {\mathit{t}}_i\\ 0& 1\end{array}\right]$, the plane is expressed in the camera coordinate system as:

$${\mathit{n}}_{ci}{}^T={\mathit{n}}_{wi}{}^T\left[\begin{array}{cc}{\mathit{R}}_{\mathit{i}}& {\mathit{t}}_{\mathit{i}}\\ \mathbf{0}& \mathbf{1}\end{array}\right]$$

(15)

From the image plane equation $z=f$, the direction of the intersection line is ${\mathit{I}}_i=\left({\mathit{n}}_{ci1},{\mathit{n}}_{ci2},0\right)$. Then, the angle between the 2D line in the image plane and the projection of $\mathit{I}$ on the corresponding image is:

$${\alpha }_i={cos}^{-1}\left(\frac{\left[\begin{array}{cc}{\mathit{n}}_{ci1}& {\mathit{n}}_{ci2}\end{array}\right]{\left[\begin{array}{cc}{a}_i& b_i\end{array}\right]}^T}{\begin{array}{cc}\Vert {\mathit{n}}_{ci1}& {\mathit{n}}_{ci2}\Vert \end{array}\begin{array}{cc}\Vert a_i& b_i\Vert \end{array}}\right)$$

(16)

where $a_i$ and $b_i$ are coefficients of the linear equation ${\mathrm{a}}_{i}x+b_{i}y+c_i=0$ in the image plane.

Therefore, the optimized objective function is:

$$min{\displaystyle \sum }_{i=1}^N{\alpha }_i^2$$

(17)

where N is the number of cameras.

3.2.2. Linear Method

A method of linearly solving for the minimum value is given by the derivation below.

The original expression is very complicated, especially the partial derivative expression. The numerator and the denominator contain $\left(l,m,n\right)$, which cannot be solved linearly. Therefore, the expression is deformed.

If the two 2D lines ${\mathit{I}}_1={\left(a_1,b_1,c_1\right)}^T,{\mathit{I}}_2={\left(a_2,b_2,c_2\right)}^T$ are nearly parallel, the angle is:

$${\alpha }_i={tan}^{-1}{a}_1/b_1-{tan}^{-1}{a}_2/b_2$$

(18)

This is a small angle, and we have:

$$\left|{\alpha }_i\right|\approx \left|tan\left({\alpha }_i\right)\right|=\left|\frac{\frac{a_1}{b_1}-\frac{a_2}{b_2}}{1+\frac{a_1{a}_2}{b_1{b}_2}}\right|=\left|\frac{a_1{b}_2-a_2{b}_1}{a_1{a}_2+b_1{b}_2}\right|$$

(19)

For the sake of discussion, we divided $a_1,b_1$ and $a_2,b_2$ by the larger one, respectively, so that the maximum value was 1. Then:

$$1\le \left|a_1{a}_2+b_1{b}_2\right|\approx \left|a_1{}^2+b_1{}^2\right|\le 2$$

(20)

where $\left|{\alpha }_i\right|$ is positively correlated with $\left|a_1{b}_2-a_2{b}_1\right|$. $\left|\alpha \right|$ is the absolute value of $\mathsf{\alpha }$. Then, Equation (17) can be used instead of Equation (21) as the optimization solution objective function:

$$min({\displaystyle \sum }_{i=1}^N{\left(a_i{\mathit{n}}_{ci2}-b_i{\mathit{n}}_{ci1}\right)}^2$$

(21)

From the previous derivation, ${\mathit{n}}_{ci1},{\mathit{n}}_{ci2}$ is a linear function of $\mathit{I}={\left(l,m,n\right)}^T$. The equation can therefore be recorded as ${{\displaystyle \sum }}_{i=1}^N{\left({\mathit{G}}_i{}^T\mathit{I}\right)}^2$, where ${\mathit{G}}_i$ is the coefficient of $\mathit{I}$ in Equation (18), and it can be representative of a normal vector to a plane.

This can be thought of as a function of ${\left(l,m,n\right)}^T$, which is a function of $\left(l,m,n\right)$. Clearly, this function is a basic elementary function—it is continuous and differentiable in the domain of the definition, and the minimum value must exist. At the point where the minimum value is obtained, the partial derivative of $\left(l,m,n\right)$ exists and it is 0, and the partial derivative is obtained separately.

$$\{\begin{array}{c}{y}_l^{\prime }={\displaystyle {\displaystyle \sum }_{i=1}^N}\left({\mathit{G}}_{i1}{\mathit{G}}_{\mathit{i}}{}^{\mathit{T}}\mathit{I}\right)=0\\ y_m^{\prime }={\displaystyle {\displaystyle \sum }_{i=1}^N}\left({\mathit{G}}_{i2}{\mathit{G}}_{\mathit{i}}{}^{\mathit{T}}\mathit{I}\right)=0\\ y_n^{\prime }={\displaystyle {\displaystyle \sum }_{i=1}^N}\left(G_{i3}{\mathit{G}}_{\mathit{i}}{}^{\mathit{T}}\mathit{I}\right)=0\end{array} .$$

(22)

We can solve Equation (19) by the SVD [25] decomposition of the coefficient matrix to obtain $\left(l,m,n\right)$.

3.2.3. Efficiency Analysis

The linear method for minimizing the image angle residual is as follows.

• Solve the 3D coordinate of the corresponding image points with a time complexity of $O\left(n\right)$;
• Solve the line parameters projected onto the image plane with a time complexity of $O\left(n\right)$;
• Solve the coefficient matrix with a time complexity of $O\left(n\right)$;
• Find the final result in fixed time.

It can be seen from the above analysis that the image angle residual method can be solved only by calculating the 3D point coordinate, the projection line parameter, the solution coefficient matrix, and the least-squares solution, so the time complexity is $O\left(n\right)$.

4. Experiments

Because the ground truth was not easy to obtain in the real experiment, we used the simulation to verify the accuracy of the algorithm and then we used only the real data to verify the validity of the algorithm.

4.1. Simulation

We simulated many conditions to validate the accuracy of our method. Firstly, the variation of the intersection angle of the two cameras and the 3D line’s attitude variation were simulated to verify the accuracy and robustness of the proposed algorithm. Secondly, the various error conditions for the stereo vision were simulated, including the 2D line extraction error, the external camera parameter error, and both the above errors. Thirdly, we verified the accuracy while in a multiple camera system. Finally, we assessed the time performance of our method in a multiple camera system.

4.1.1. Simulation Environment

The simulation platform was Windows 10 Pro, the implementation language of the algorithm was C++, the implementation environment was Microsoft Visual Studio 2013, and the processor was an Intel(R) Core TM i7-9850H 2.6GHz.

The equivalent focal length was (2181.8, 2181.8) and the image principal point was (1024, 1024). The cameras were arranged in a circle around the target, and the radius of the circle was 4.5 m. The origin of the world coordinate system was the center of the circle. The two endpoints of the 3D line were $A\left(-0.5,-0.5,-0.5\right)$ and $B\left(1.5, 1.5, 1.5\right)$. The top view of the simulation scenario is shown in Figure 3.

4.1.2. Simulation Description

• The corresponding image points used in the PtD method were obtained by adding the same error to the projection of the endpoint A in the image, which ensured that PtD method was also solved under the same error conditions.
• The TPS, DtP, and PtD methods were used for each simulation. We used the angle between the result and the ground truth and the distance from the two endpoints to the result line to evaluate the accuracy. All simulations were calculated 1000 times, and the root mean square (RMS) of the angular error and the average of distance were obtained. The units of angular error were degrees, and the units of distance error were meters.

  $$E={\cos }^{-1}\frac{\mathit{I}{\mathit{I}}_t}{\Vert \mathit{I}\Vert \Vert {\mathit{I}}_t\Vert }$$

  (23)

  $$E_d=abs\left(d_{AI}\right)+abs\left(d_{BI}\right)$$

  (24)

In the above equation ${\mathit{I}}_t(l_t,m_t,n_t)$ is the ground truth, and $\mathit{I}(l,m,n$) is the algorithm’s result. $d_{AI}$ is the distance between the endpoint $A$ of the 3D line segment to the result line, and $d_{BI}$ is the distance between the endpoint $B$ of the 3D line segment to the result line.

Simulations were conducted separately to determine the following conditions:

• Angle between optical axes of binocular cameras.
• 3D line’s attitude.
• Line segments extraction error in image.
• Errors of all camera external parameters.
• All camera external parameters and extraction errors.
• Number of cameras.
• Running time.

Case 1 was to verify the precision under the different angle between the two cameras. Case 2 was to verify the precision under the target’s different attitude. Cases 3–5 were to verify the precision under the error of the cameras’ parameters. Case 6 was to verify the precision as the number of cameras increased. Case 7 was to test the temporal performance of the algorithm.

4.1.3. Simulation Results

The simulation details and results are given, respectively.

Firstly, we simulated the intersection angles of two cameras, which varied to verify the accuracy of the three methods. As shown in Figure 3, C₁ was placed in the fixed point (4.5,0,0), and C₂ was moved on the circle with a radius of 4.5 m. The angle between the optical axes of C₁ and C₂ varied from 30° to 150°. We simulated two conditions of the 3D line, one of which was the 3D line perpendicular to the baseline of C₁ and C₂. When the 3D line was perpendicular to the baseline, the endpoints of the 3D line segment were $A\left(-0.5,-0.5,-0.5\right)$ and $B\left(-0.5,1.5,-0.5\right)$. From the definition of the simulation scenario, we knew that, as the intersection angle changed from 30° to 150°, the line segment AB was always perpendicular to the baseline, and the distance between AB and the baseline became smaller and smaller. When the 3D line is not perpendicular to the baseline, the endpoints of the 3D line segment were $A\left(-0.5,-0.5,-0.5\right)$, $B\left(1.5,1.5,1.5\right)$. A Gaussian error with a mean of 0 was added to the optical center of the camera, with a 5 cm RMS value. A Gaussian error with a mean of 0 was added to the camera angle, with a 1° RMS value. A Gaussian error with a mean of 0 was added to the x- and y-directions of the two endpoints of the 2D line segments, with a 2-pixel RMS value. The results are shown in Figure 4.

When the 3D line remained unchanged, the error was relevant to the intersection angle. In the beginning, the three methods achieved the same accuracy. As the intersection angle varied from 30° to 150°, the distance between the baseline and AB grew smaller and smaller. In other words, they were becoming closer and closer to each other, which meant the intersection condition was getting worse; the PtD method had the same accuracy as the DtP method. TPS had the best positional accuracy but the worst angular accuracy. In the condition where the 3D line was not parallel to the imaging plane and was not perpendicular to the baseline, PtD had higher accuracy both on the position and angle than DtP; TPS achieved the worst angular accuracy, and DtP achieved the worst positional accuracy.

Secondly, we simulated the condition where the 3D line moved while the intersection angle remained unchanged; the C₁ and C₂ places were fixed. Endpoint A was (−0.5,−0.5,−0.5), The initial position of endpoint B was (−0.5,1.5,−0.5), and the $k$th position was $\left(-0.5-k\ast 0.05,1.5,-0.5-k\ast 0.05\right)$; $k$ was the offset time. The end position of point B was (−5.5,1.5,−5.5). A Gaussian error with a mean of 0 was added to the optical center of the camera, with a 5 cm RMS value. A Gaussian error with a mean of 0 was added to the camera angle, with a 1° RMS value. A Gaussian error with a mean of 0 was added to the x- and y-directions of the two endpoints of the 2D line, with a 2-pixel RMS value. The results of the simulation while the intersection angles are 90° and 120°, and shown in Figure 5a,b respectively.

As shown in Figure 5, at the start, the TPS method had the best positioning accuracy and the worst angular accuracy. However, as the intersection condition became, the TPS had the best accuracy both in direction and position. The reasons are as follows.

Firstly, the 3D line became longer, and the final length was 3.68-times greater than that of the initial length. Therefore, theoretically, if only the influence of the line length was considered, the direction error of TPS would be the 1/3.68 of the original value. However, the error of the 3D point B increased because the intersection angle of 3D point B became smaller. Therefore, the error reduction was not proportional.

Secondly, the angle between the 3D line and the baseline remained unchanged—it was always 90°. However, the angle between the 3D line and the imaging plane varied from 0 to 45° and the distance between the 3D line and the baseline became smaller. At the start, when the intersection angle was 90°, the distance between the 3D line and the baseline was 3.89 m; when the intersection angle was 120°, the distance between the 3D line and the baseline was 2.94 m. At the end, however, the distances were 2.50 m and 2.30 m, respectively. The lengths of the baseline were 6.36 m and 7.79 m, respectively. From the above analysis, we can determine that the smaller distance aggravated the degeneracy of the lines’ reconstruction.

Thirdly, we simulated the condition where the cameras and the 3D line remained unchanged, but the errors of the camera’s external parameters and 2D line were different. The intersection angle was 120°. The endpoints of the 3D line were $A\left(0.5,-0.5,0.5\right)$and $B\left(1.5,1.5,1.5\right)$. We simulated for 2D line error, the error of the camera external parameters, and all above errors. The error details were as below:

Case 1: A Gaussian error with a mean of 0 was added to the x- and y-directions at the head and the tail of the line segment, with 0–4 pixels of RMS. The results are shown in Figure 6.

From Figure 6, we can see that if only the same 2D line error existed, the 3D line’s accuracy of the three methods, from most to least accurate, was TPS, PtD, then DtP.

Case 2: A Gaussian error with a mean of 0 was added to the optical center of the camera, with 1 mm to 50 mm of RMS, and the step size was 1 mm. A Gaussian error with a mean of 0 was added to the camera angle, with 0.05–2.5° of RMS. The simulation results are shown in Figure 7.

From Figure 7, we can see that under the same error of the camera’s external parameters, the directional accuracy of the 3D line of the three methods, from most to least accurate, was PtD, DtP, then TPS, and the positional accuracy of the 3D line of the three methods from most to least accurate, was TPS, PtD, then DtP.

Case 3: A Gaussian error with a mean of 0 was added to the optical center of the camera, with 1 mm to 50 mm of RMS, and the step size was 1 mm. A Gaussian error with a mean of 0 was added to the camera angle, with 0.05–2.5° of RMS. A Gaussian error with a mean of 0 was added to the x-and y-directions of the two endpoints of the 3D line, with 0.1–5 pixels of RMS. The simulation results are shown in Figure 8.

From Figure 8, we can see that under same error of external camera’s parameters and the 2D lines, the 3D line’s direction accuracy of the three methods, from most to least accurate, was PtD, DtP, then TPS, and the 3D line’s position accuracy of the three methods, from most to least accurate, was TPS, PtD, then DtP. The position accuracies of TPS and PtD are close, and the directional accuracy of PtD was far better than TPS.

Additionally, we simulated the condition where the camera number varied from 2 to 20; the cameras were evenly distributed on the circle as shown in Figure 3. The DtP method used the LS [26] directly solve this scenario. A Gaussian error with a mean of 0 was added to the optical center of the camera, with a 10 mm root mean square (RMS) value. A Gaussian error with a mean of 0 was added to the camera angle, with a 0.5° RMS value. A Gaussian error with a mean of 0 was added to the x- y-directions of the two endpoints of the 3D line, with a 1-pixel RMS value. The endpoints of the 3D line were$\mathrm{A}\left(0.5,-0.5,0.5\right),\mathrm{B}\left(1.5,1.5,1.5\right)$. The results are shown in Figure 9.

From Figure 9, we can see that as the number of cameras increased, the accuracy of the three methods increased gradually, indicating that these methods utilized the constraints of the multi-camera. Similar to the result in Figure 8, with the increase in the number of cameras, under the same error of the external camera’s parameters and the 2D lines, the 3D line’s direction accuracy of the three methods, from most to least accurate, was PtD, DtP, then TPS, and the 3D line’s positional accuracy of the three methods, from most to least accurate, was TPS, PtD, then DtP. The positional accuracies of TPS and PtD were close, and the directional accuracy of the PtD method was far better than the TPS method.

Finally, we simulated the condition where the camera number increased from 2 to 20 to verify the time performance of our method. The linear algorithm took a small amount of time; therefore, for the convenience of comparison, we counted the time it took to run 10,000 times. A Gaussian error with a mean of 0 was added to the optical center of the camera, with a 5 cm RMS value. A Gaussian error with a mean of 0 was added to the camera angle, with a 1° RMS value. A Gaussian error with a mean of 0 was added to the x- y-directions of the two endpoints of the 2D line segments, with a 2-pixel RMS value. The simulation results are shown in Figure 10.

Figure 10 confirms that all three methods are linear methods; TPS took the longest, then PtD, and the fastest was DtP. DtP only needs to solve each plane equation and then solve the least-squares method; PtD needs to solve the 3D point coordinate and the line parameters in two steps; TPS needs to solve the 3D point coordinate two times, which explains the variances in running time between the methods.

4.1.4. Simulation Conclusion

The simulation results are shown in

Table 2. All simulation results.

Method	Case 1		Case 2		Case 3	Case 4	Case 5	Case 6
	Perpendicular	Not Perpendicular	90°	120°
(A)DtP	S	F	S→T	S→T	T	S	S	S
PtD	F	F	F→S	F→S	S	F	F	F
TPS	T	S	T→F	T→F	F	T	T	T
DtP(D)	T	S	T	T	T	T	T	T
PtD	S	S	S	S	S	S	S	S
TPS	F	F	F	F	F	F	F	F

. The “F” in the table means first, the “S” means second, and the “T” means third and the “S->T” means from second to third.

From the above simulation results, we can come to some conclusions:

• Under the same error of the external camera parameters and the 2D line, the PtD method has the best directional accuracy, and the TPS method has the best positional accuracy.
• When the intersection condition was normal, the 3D line’s direction accuracy of the three methods, from most to least accurate, was PtD, DtP, then TPS, and the 3D line’s position accuracy of the three methods, from most to least accurate, was TPS, PtD, and DtP. Therefore, if the direction accuracy is more important, the PtD method should be used, and if positional accuracy is more important, the TPS method should be used—provided that there are two pairs of corresponding image points.
• When the intersection condition was bad and the target was relative long, TPS achieved the best accuracy, both in the direction and position of the 3D line. However, it needs two pairs of corresponding image points, which is sometimes hard to satisfy. PtD achieved better accuracy than DtP both in the direction and position of the 3D line, so PtD can be used if there is only one pair of corresponding image points.

4.2. Physical Experiment

We used physical experiment 1 to verify the precision of our method, and used physical experiment 2 (in which TPS could not be used) to verify the correctness of the algorithm.

4.2.1. Physical Experiment 1

Physical Environment

We used three cameras to measure the lines—the camera setup is shown in Figure 11. The physical environment is shown in Figure 12. The target was a checkerboard and was placed in front of the cameras. The precision of the checkerboard was 0.01 mm. The 3D lines to be reconstructed were the four edge lines in the checkerboard, as marked in Figure 12. The length of the lines 1, 3, 5, and 7 were 30 cm, and the lines 2, 4, 6, 8 were 21 cm. From the positional relationship between the camera and the target, we could ascertain that (a) was in a better intersection condition than (b), and the lines 1 and 3 were in a better intersection condition than the lines 2 and 4. All cameras were calibrated by the diagonal markers behind the checkerboard, and the 3D coordinates of the diagonal markers were obtained by the total station Leica TS60, with an accuracy of 0.6 mm. At the same time, we also obtained the 3D coordinates of the four corners of the checkerboard using the Leica TS60. PtD, DtP, and TPS methods were used to reconstruct the four 3D lines. The camera and lens models were Basler (acA1440—220uc) and RICOH (6 mm 1:1.4), respectively.

Experimental Procedure

The procedure of the experiment was as follows:

• The world coordinate system was established by the total station. The total station was used to obtain the coordinates of the calibration control points. The coordinate system direction was vertically upwards (Y) and horizontal (XZ), and the system constituted a right-hand coordinate system.
• The stereo cameras were used to take photos synchronously. The checkerboard was placed at two angles to verify the accuracy of the methods in two conditions. One was where the 3D lines were parallel to the imaging plane, and the other was not. The calibration control points were extracted from the image, and the 3D coordinates were used to calibrate all of the cameras in a unified world coordinate system. All parameters of the camera were calibrated, including the main point, equivalent focal length, lens distortion, and external parameters of the camera.
• The 2D lines and the corresponding image points were extracted from the two images by extracted the two endpoints of the 2D lines. The corresponding image points were one of the endpoints of the 2D lines.
• After the correction of lens distortion, DtP, PtD, and TPS were used separately to obtain the 3D line I.

First, we estimated the precision by the distance of two points—the results are shown in

Table 3. Errors of the total station (mm).

Line No.	Measured Distance	Ideal Distance
1	300.0	300.0
2	210.1	210.0
3	300.2	300.0
4	210.0	210.0
5	300.1	300.0
6	210.1	210.0
7	300.0	300.0
8	210.0	210.0

. From the results, we determined that the maximum of the distance error was 0.2 mm and the corresponding angle was ${tan}^{-1}\left(\frac{0.2}{300}\right)=0.038°$. The theoretical accuracy of the total station was 0.6 mm, which meant a corresponding angle ${tan}^{-1}\left(\frac{0.6}{210}\right)=0.16°$.

The errors between the coordinates obtained by the total station and given by the intersection method [21] to demonstrate the precision of the cameras’ parameters are shown in

Table 4. Results of 3D points’ errors (mm).

Point No.	X	Y	Z
1	−0.2	−0.7	−0.0
2	−0.5	−0.5	−0.1
3	−0.2	−0.6	−0.0
4	0.4	−0.5	0.8
5	−0.4	−0.2	0.6
6	−0.0	−0.0	0.1
7	−0.5	−0.6	0.2
8	−0.1	−0.5	0.7

. The ith point was the top or left endpoint of the ith line.

Therefore, we used the point coordinates obtained by the total station to calculate the direction of the line as the ground truth ${\mathit{I}}_t$. We calculated the angle between ${\mathit{I}}_t$ and $\mathit{I}$ as the angular error, and the sum of distances from the two endpoints to $\mathit{I}$ as the distance error, to estimate the accuracy of our method.

All the results are shown in

Table 5. Experiment results for good conditions.

No.	DtP	PtD	TPS	DtP	PtD	TPS
1	0.10	0.10	0.09	2.4	1.2	1.4
3	0.10	0.11	0.12	1.6	1.5	1.4
5	0.12	0.12	0.12	0.9	0.8	0.7
7	0.06	0.07	0.08	1.6	1.5	1.6
sum	0.38	0.4	0.41	6.5	5	5.1

and

Table 6. Experiment results for bad conditions.

No.	DtP	PtD	TPS	DtP	PtD	TPS
2	0.58	0.28	0.03	7.7	2.0	1.1
4	0.78	0.50	0.23	6.8	2.0	1.6
6	0.07	0.07	0.16	2.9	0.4	0.7
8	1.07	1.08	0.08	4.1	4.3	1.5
sum	2.5	1.93	0.5	21.5	8.7	4.9

. The second, third and fourth columns are angular errors (°), and the fifth, sixth and seventh columns are distance errors (mm).

From the above tables, we can see that for the lines 1, 3, 5, and 7, the sum of the angular errors of the 3D line, from lowest to highest, was TPS, PtD, then DtP, and they were very close; the maximum difference was 0.02. The sum of the distance error of the 3D line, from highest to lowest, was DtP, PtD, then TPS. For the lines 2, 4, 6, and 8, the accuracy of the direction and distance, from lowest to highest, was TPS, PtD, then DtP. However, the TPS needed two pairs of corresponding image points, which was difficult to meet under certain conditions, such as in physical experiment 2.

4.2.2. Physical Experiment 2

Physical experiment 2 was designed to verify the correctness of our method if there were more than two cameras.

Physical Environment

The setup for the physical experiment is shown in Figure 13. The target was placed on the board in the center, and the diagonal markers on the side were the calibration control points. The 3D line to be reconstructed was the target’s central axis. The resolution of the camera was 4288 × 2848 pixels, and the equivalent focal distance was approximately 5200.

Experimental Procedure

The experiment was conducted as follows:

• The total station was used to obtain the coordinates of the calibration control points in the world coordinate system. The total station coordinate system was used as the world coordinate system. The coordinate system direction was vertically upwards (Y) and horizontal (XZ) and the system constituted a right-hand coordinate system.
• The same camera was used to take photographs from nine different locations. The calibration control points were extracted from the image, and the three-dimensional coordinates were used to calibrate all of the cameras in a unified world coordinate system.
• The 2D line was extracted from the image. The corresponding image point was the top point of the target.
• DtP and PtD were used separately to obtain the results. For hard-to-find pairs of corresponding image points on the target, TPS was not used.

All the target directional results are shown in

Table 7. Experimental results.

Camera No.	DtP	PtD
2	(−0.012, 1, −0.014)	(−0.012, 1, −0.014)
6	(−0.020, 1, −0.022)	(−0.016, 1, −0.019)
9	(−0.017, 1, −0.012)	(−0.018, 1, −0.014)

. It can be seen from the table that the results of the two methods were essentially the same.

5. Conclusions

Considering the problem of 3D line reconstruction in binocular or multiple view stereo vision, where there is only a pair of corresponding points on the line, a new method called PtD was proposed. Compared to DtP and TPS methods, PtD uses both point and line information for 3D line reconstruction. The simulation results in this paper demonstrate that our method achieves the best accuracy for determining direction; and although the positional accuracy of our method is worse than TPS, it is better than DtP. The physical experiment shows that under bad intersection conditions, the PtD method achieves better accuracy than the DtP method.