Computer Stereo Vision for Autonomous Driving

The most commonly used car sensors include: a) passive sensors, such as cameras; b) active sensors, such as LIDARs, Radars and ultrasonic transceivers; and c) other types of sensors, such as global positioning systems (GPS), inertial measurement unit (IMU), among others. When choosing them, we need to consider many different factors, such as sampling rate, field of view (FoV), accuracy, range, cost and overall system complexity¹¹1autonomous-driving.org/2019/01/25/positioning-sensors-for-autonomous-vehicles.

Cameras capture 2D images, by collecting light reflected on 3D objects. Images captured from different views can be utilized to reconstruct the 3D driving scene geometry. Most autonomous car perception tasks, such as visual semantic driving scene segmentation and object detection/recognition, are developed for images. In Sec. 3, we provide readers with a comprehensive overview of these tasks. The perspective (or pinhole) camera model and the mathematical principles of multi-view geometry are discussed in Sec. 4. Acquired image quality is always subject to environmental conditions, such as weather and illumination pitas2000digital . Therefore, the visual information fusion from other sensors is typically required for robust autonomous car perception.

LIDAR illuminates a target with pulsed laser light and measures the source-target distance, by analyzing the reflected laser pulses detection2013ranging . Due to its ability to generate highly accurate 3D driving scene geometry models, LIDARs are generally mounted on autonomous cars for depth perception. Current industrial autonomous car localization and mapping systems are generally based on LIDARs. Furthermore, Radars can measure both the range and radial velocity of an object, by transmitting an electromagnetic wave and analyzing its reflections bureau2013radar . Radars have already been established in the automotive industry, and they have been prevalently employed to enable intelligent vehicle advanced driver assistance system (ADAS) features, such as adaptive cruise control and autonomous emergency braking\@footnotemark. Similar to Radar, ultrasonic transceivers calculate the source-object distance, by measuring the time between transmitting an ultrasonic signal and receiving its echo westerveld2014silicon . Ultrasonic transceivers are commonly used for autonomous car localization and navigation.

In addition to the aforementioned passive and active sensors, GPS and IMU systems are commonly used to enhance autonomous car localization and mapping performance zheng2019low . GPS can provide both time and geolocation information for autonomous cars. However, its signals can become very weak, when GPS reception is blocked by obstacles in GPS-denied regions, such as urban regions samama2008global . Hence, GPS and IMU information fusion is widely adopted to provide continuous autonomous car position and velocity information zheng2019low .

Car chassis technologies, especially Drive-by-Wire (DbW), are required for building autonomous vehicles. DbW technology refers to the electronic systems that can replace traditional mechanical controls liu2019chassis . DbW systems can perform vehicle functions, which are traditionally achieved by mechanical linkages, through electrical or electro-mechanical systems. There are three main vehicle control systems that are commonly replaced with electronic controls: 1) throttle, 2) braking and 3) steering.

A Throttle-by-Wire (TbW) system helps accomplish vehicle propulsion via an electronic throttle, without any cables from the accelerator pedal to the engine throttle valve. In electric vehicles, TbW system controls the electric motors, by sensing accelerator pedal for a pressure (input) and sending signal to the power inverter modules. Compared to traditional hydraulic brakes, which provide braking effort, by building hydraulic pressure in the brake lines, a Brake-by-Wire (BbW) system completely eliminates the need for hydraulics, by using electronic motors to activate calipers. Furthermore, in vehicles that are equipped with Steer-by-Wire (SbW) technology, there is no physical connection between the steering wheel and the tires. The control of wheels’ direction is established through electric motor(s), which are actuated by electronic control units monitoring steering wheel inputs.

In comparison to traditional throttle systems, electronic throttle systems are much lighter, hence greatly reducing modern car weight. In addition, they are easier to service and tune, as a technician can simply connect a laptop to perform tuning. Moreover, an electronic control system allows more accurate control of throttle opening, compared to a cable control that stretches over time. Furthermore, since the steering wheel can be bypassed as an input device, safety can be improved by providing computer controlled intervention of vehicle controls with systems, such as Adaptive Cruise Control and Electronic Stability Control.

The perspective (or pinhole) camera model, as illustrated in Fig. 5, is the most common geometric camera model describing the relationship between a 3D point $\mathbf{p^{\text{C}}}=[x^{\text{C}},y^{\text{C}},z^{\text{C}}]^{\top}$ in the camera coordinate system (CCS) and its projection $\mathbf{\bar{p}}=[x,y,f]^{\top}$ on the image plane $\Pi$. $\mathbf{o^{\text{C}}}$ is the camera center. The distance between $\Pi$ and $\mathbf{o^{\text{C}}}$ is the camera focal length $f$. $\hat{\mathbf{p}}^{\text{C}}=[\frac{x^{\text{C}}}{z^{\text{C}}},\frac{y^{\text{C}}}{z^{\text{C}}},1]^{\top}$ are the normalized coordinates of $\mathbf{p^{\text{C}}}=[x^{\text{C}},y^{\text{C}},z^{\text{C}}]^{\top}$. Optical axis is the ray originating from $\mathbf{o^{\text{C}}}$ and passing perpendicularly through $\Pi$. The relationship between $\mathbf{p}^{\text{C}}$ and $\bar{\mathbf{p}}$ is as follows trucco1998introductory :

$$\mathbf{\bar{p}}=f\hat{\mathbf{p}}^{\text{C}}=\frac{f}{z^{\text{C}}}\mathbf{p^{\text{C}}}.$$

(8)

Since lens distortion does not exist in a perspective camera model, $\mathbf{\bar{p}}=[x,y,f]^{\top}$ on the image plane $\Pi$ can be transformed into a pixel $\mathbf{{p}}=[u,v]^{\top}$ in the image using fan2018real :

$$u=u_{o}+s_{x}x,\ \ \ v=v_{o}+s_{y}y,$$

(9)

where $\mathbf{p}_{o}=[u_{o},v_{o}]^{\top}$ is the principal point; and $s_{x}$ and $s_{y}$ are the effective size measured (in pixels per millimeter) in the horizontal and vertical directions, respectively trucco1998introductory . To simplify the expression of the camera intrinsic matrix $\mathbf{K}$, two notations $f_{x}=fs_{x}$ and $f_{y}=fs_{y}$ are introduced. $u_{o}$, $v_{o}$, $f$, $s_{x}$ and $s_{y}$ hartley2003multiple are five camera intrinsic parameters. Combining (8) and (9), a 3D point $\mathbf{p}^{\text{C}}$ in the CCS can be transformed into a pixel $\mathbf{p}$ in the image using fan2019cvprw :

$$\begin{split}\mathbf{\tilde{p}}=\frac{1}{z^{\text{C}}}\mathbf{K}\mathbf{p^{\text{C}}}=\frac{1}{z^{\text{C}}}\begin{bmatrix}f_{x}&0&u_{o}\\ 0&f_{y}&v_{o}\\ 0&0&1\\ \end{bmatrix}\begin{bmatrix}x^{\text{C}}\\ y^{\text{C}}\\ z^{\text{C}}\\ \end{bmatrix}\end{split},$$

(10)

where $\tilde{\mathbf{p}}=[\mathbf{{p}}^{\top},1]^{\top}=[u,v,1]^{\top}$ denotes the homogeneous coordinates of $\mathbf{p}=[u,v]^{\top}$. Plugging (10) into (8) results in:

$$\hat{\mathbf{p}}^{\text{C}}=\mathbf{K}^{-1}\mathbf{\tilde{p}}=\frac{\mathbf{\bar{p}}}{f}=\frac{\mathbf{p^{\text{C}}}}{z^{\text{C}}}.$$

(11)

Therefore, an arbitrary 3D point lying on the ray, which goes from $\mathbf{o}^{\text{C}}$ and through $\mathbf{p}^{\text{C}}$, is always projected at $\bar{\mathbf{p}}$ on the image plane.

In order to get better imaging results, a lens is usually installed in front of the camera trucco1998introductory . However, this introduces image distortions. The optical aberration caused by the installed lens typically deforms the physically straight lines provided by projective geometry to curves in the images zhang2000flexible , as shown in Fig. 6(a). We can observe in Fig. 6(b) that the bent checkerboard grids become straight when the lens distortion is corrected.

Lens distortion can be categorized into two main types: 1) radial distortion and 2) tangential distortion fan2018real . The presence of radial distortion is due to the fact that geometric lens shape affects straight lines. Tangential distortion occurs because the lens is not perfectly parallel to the image plane trucco1998introductory . In practical experiments, the image geometry is affected by radial distortion to a much higher extent than by tangential distortion. Therefore, the latter is sometimes neglected in the process of distorted image correction.

The generic geometry of stereo vision is known as epipolar geometry. An example of the epipolar geometry is shown in Fig. 8.

$\Pi_{\text{L}}$ and $\Pi_{\text{R}}$ represent the left and right image planes, respectively. $\mathbf{o}_{\text{L}}^{\text{C}}$ and $\mathbf{o}_{\text{R}}^{\text{C}}$ denote the origins of the left camera coordinate system (LCCS) and the right camera coordinate system (RCCS), respectively. The 3D point $\mathbf{p}^{\text{W}}=[x^{\text{W}},y^{\text{W}},z^{\text{W}}]^{\top}$ in the WCS, is projected at $\mathbf{\bar{p}_{\text{L}}}=[x_{\text{L}},y_{\text{L}},f_{\text{L}}]^{\top}$ on $\Pi_{\text{L}}$ and at $\mathbf{\bar{p}_{\text{R}}}=[x_{\text{R}},y_{\text{R}},f_{\text{R}}]^{\top}$ on $\Pi_{\text{R}}$, respectively. $f_{\text{L}}$ and $f_{\text{R}}$ are the focal lengths of the left and right cameras, respectively; The representations of $\mathbf{p}^{\text{W}}$ in the LCCS and RCCS are $\mathbf{p^{\text{C}}_{\text{L}}}=[x^{\text{C}}_{\text{L}},y^{\text{C}}_{\text{L}},z^{\text{C}}_{\text{L}}]^{\top}=\frac{{z_{\text{L}}^{\text{C}}}}{f_{\text{L}}}\mathbf{\bar{p}_{\text{L}}}$ and $\mathbf{p^{\text{C}}_{\text{R}}}=[x^{\text{C}}_{\text{R}},y^{\text{C}}_{\text{R}},z^{\text{C}}_{\text{R}}]^{\top}=\frac{{z_{\text{R}}^{\text{C}}}}{f_{\text{R}}}\mathbf{\bar{p}_{\text{R}}}$, respectively. According to (4), $\mathbf{p^{\text{C}}_{\text{L}}}$ can be transformed into $\mathbf{p^{\text{C}}_{\text{R}}}$ using:

$$\mathbf{p^{\text{C}}_{\text{R}}}=\mathbf{R}\mathbf{p^{\text{C}}_{\text{L}}}+\mathbf{t},$$

(14)

where $\mathbf{R}\in\mathbb{R}^{3\times 3}$ is a rotation matrix and $\mathbf{t}\in\mathbb{R}^{3\times 1}$ is a translation vector. $\mathbf{e^{\text{C}}_{\text{L}}}$ and $\mathbf{e^{\text{C}}_{\text{R}}}$ denote the left and right epipoles, respectively. The epipolar plane is uniquely defined by $\mathbf{o^{\text{C}}_{\text{L}}}$, $\mathbf{o^{\text{C}}_{\text{R}}}$ and $\mathbf{p^{\text{W}}}$. It intersects $\Pi_{\text{L}}$ and $\Pi_{\text{R}}$ giving rise to two epipolar lines, as shown in Fig. 8. Using (11), $\mathbf{p^{\text{C}}_{\text{L}}}$ and $\mathbf{p^{\text{C}}_{\text{R}}}$ can be normalized using:

$$\begin{split}\mathbf{\hat{p}^{\text{C}}_{\text{L}}}=\frac{\mathbf{p^{\text{C}}_{\text{L}}}}{z^{\text{C}}_{\text{L}}}={\mathbf{K}_{\text{L}}}^{-1}\mathbf{\tilde{p}}_{\text{L}},\ \ \ \mathbf{\hat{p}^{\text{C}}_{\text{R}}}=\frac{\mathbf{p^{\text{C}}_{\text{R}}}}{Z^{\text{C}}_{\text{R}}}=\mathbf{K_{\text{R}}}^{-1}\mathbf{\tilde{p}_{\text{R}}},\end{split}$$

(15)

where $\mathbf{K_{\text{L}}}$ and $\mathbf{K_{\text{R}}}$ denote the intrinsic matrices of the left and right cameras, respectively. $\mathbf{\tilde{p}}_{\text{L}}=[{\mathbf{p}_{\text{L}}}^{\top},1]^{\top}$ and $\mathbf{\tilde{p}}_{\text{R}}=[{\mathbf{p}_{\text{R}}}^{\top},1]^{\top}$ are the homogeneous coordinates of the image pixels $\mathbf{p}_{\text{L}}=[u_{\text{L}},v_{\text{L}}]^{\top}$ and $\mathbf{p}_{\text{R}}=[u_{\text{R}},v_{\text{R}}]^{\top}$, respectively.

Essential matrix $\mathbf{E}\in\mathbb{R}^{3\times 3}$ was first introduced by Longuet-Higgins in 1981 longuet1981computer . A simple way of introducing the defining equation of $\mathbf{E}$ is to multiply both sides of (14) by $\mathbf{p^{\text{C}}_{\text{R}}}^{\top}[\mathbf{t}]_{\times}$:

$$\begin{split}\mathbf{p^{\text{C}}_{\text{R}}}^{\top}[\mathbf{t}]_{\times}\mathbf{p^{\text{C}}_{\text{R}}}=\mathbf{p^{\text{C}}_{\text{R}}}^{\top}[\mathbf{t}]_{\times}(\mathbf{R}\mathbf{p^{\text{C}}_{\text{L}}}+\mathbf{t}).\end{split}$$

(16)

According to (3), (16) can be rewritten as follows:

$$-\mathbf{p^{\text{C}}_{\text{R}}}^{\top}[\mathbf{p^{\text{C}}_{\text{R}}}]_{\times}\mathbf{t}=\mathbf{p^{\text{C}}_{\text{R}}}^{\top}[\mathbf{t}]_{\times}\mathbf{R}\mathbf{p^{\text{C}}_{\text{L}}}+\mathbf{p^{\text{C}}_{\text{R}}}^{\top}[\mathbf{t}]_{\times}\mathbf{t}.$$

(17)

Applying (2) to (17) yields:

$$\mathbf{p^{\text{C}}_{\text{R}}}^{\top}[\mathbf{t}]_{\times}\mathbf{R}\mathbf{p^{\text{C}}_{\text{L}}}=\mathbf{p^{\text{C}}_{\text{R}}}^{\top}\mathbf{E}\mathbf{p^{\text{C}}_{\text{L}}}=0,$$

(18)

The essential matrix $\mathbf{E}$ is defined by:

$$\mathbf{E}=[\mathbf{t}]_{\times}\mathbf{R}$$

(19)

Plugging (15) into (18) results in:

$${\hat{\mathbf{p}}^{\text{C}}_{\text{R}}}{}^{\top}\mathbf{E}{\hat{\mathbf{p}}^{\text{C}}_{\text{L}}}=0,$$

(20)

which depicts the relationship between each pair of normalized points ${\hat{\mathbf{p}}^{\text{C}}_{\text{R}}}$ and ${\hat{\mathbf{p}}^{\text{C}}_{\text{L}}}$ lying on the same epipolar plane. It is important to note here that $\mathbf{E}$ has five degrees of freedom: both $\mathbf{R}$ and $\mathbf{t}$ have three degrees of freedom, but the overall scale ambiguity causes the degrees of freedom to be reduced by one hartley2003multiple . Hence, in theory, $\mathbf{E}$ can be estimated with at least five pairs of $\mathbf{{p^{\text{C}}_{\text{L}}}}$ and $\mathbf{{p^{\text{C}}_{\text{R}}}}$. However, due to the non-linearity of $\mathbf{E}$, its estimation using five pairs of correspondences is always intractable. Therefore, $\mathbf{E}$ is commonly estimated with at least eight pairs of $\mathbf{{p^{\text{C}}_{\text{L}}}}$ and $\mathbf{{p^{\text{C}}_{\text{R}}}}$ trucco1998introductory , as discussed in Sec. 4.2.

As introduced in Sec. 4.2, the essential matrix creates a link between a given pair of corresponding 3D points in the LCCS and RCCS. When the intrinsic matrices of the two cameras in a stereo rig are unknown, the relationship between each pair of corresponding 2D image pixels $\mathbf{p}_{\text{L}}=[u_{\text{L}},v_{\text{L}}]^{\top}$ and $\mathbf{p}_{\text{R}}=[u_{\text{R}},v_{\text{R}}]^{\top}$ can be established, using the fundamental matrix $\mathbf{F}\in\mathbb{R}^{3\times 3}$. It can be considered as a generalization of $\mathbf{E}$, where the assumption of calibrated cameras is removed hartley2003multiple . Applying (15) to (20) yields:

$${\tilde{\mathbf{p}}_{\text{R}}}^{\top}{\mathbf{K}_{\text{R}}}^{-\top}\mathbf{E}{\mathbf{K}_{\text{L}}}^{-1}\tilde{\mathbf{p}}_{\text{L}}={\tilde{\mathbf{p}}_{\text{R}}}^{\top}\mathbf{F}\tilde{\mathbf{p}}_{\text{L}}=0,$$

(21)

where the fundamental matrix $\mathbf{F}$ is defined as:

$$\mathbf{F}={\mathbf{K}_{\text{R}}}^{-\top}\mathbf{E}{\mathbf{K}_{\text{L}}}^{-1}.$$

(22)

$\mathbf{F}$ has seven degrees of freedom: a 3$\times$3 homogeneous matrix has eight independent ratios, as there are nine entries, but the common scaling is not significant. However, $\mathbf{F}$ also satisfies the constraint $\text{det}(\mathbf{F})=0$, which removes one degree of freedom hartley2003multiple . The most commonly used algorithm to estimate $\mathbf{E}$ and $\mathbf{F}$ is “eight-point algorithm” (EPA), which was introduced by Hartley in 1997 hartley1997defense . This algorithm is based on the scale invariance of $\mathbf{E}$ and $\mathbf{F}$: $\lambda_{\mathbf{E}}{\mathbf{p}^{\text{C}}_{\text{R}}}^{\top}\mathbf{E}{\mathbf{p}^{\text{C}}_{\text{L}}}=0$ and $\lambda_{\mathbf{F}}{\tilde{\mathbf{p}}_{\text{R}}}^{\top}\mathbf{F}{\tilde{\mathbf{p}}_{\text{L}}}=0$, where $\lambda_{\mathbf{E}},\lambda_{\mathbf{F}}\neq 0$. By setting one element in $\mathbf{E}$ and $\mathbf{F}$ to $1$, eight unknown elements still need to be estimated. This can be done using at least eight correspondence pairs. If the intrinsic matrices $\mathbf{K}_{\text{L}}$ and $\mathbf{K}_{\text{R}}$ of the two cameras are known, the EPA only needs to be carried out once to estimate either $\mathbf{E}$ or $\mathbf{F}$, because the other one can be easily worked out using (21).

An arbitrary 3D point $\mathbf{p^{\text{W}}}=[x^{\text{W}},y^{\text{W}},z^{\text{W}}]^{\top}$ lying on a planar surface satisfies:

$$\mathbf{n}^{\top}\mathbf{p^{\text{W}}}+b=0,$$

(23)

where $\mathbf{n}=[n_{x},n_{y},n_{z}]^{\top}$ is the normal vector of the planar surface. Its corresponding pixels $\mathbf{p}_{\text{L}}=[u_{\text{L}},v_{\text{L}}]^{\top}$ and $\mathbf{p}_{\text{R}}=[u_{\text{R}},v_{\text{R}}]^{\top}$ in the left and right images, respectively, can be linked by a homography matrix $\mathbf{H}\in\mathbb{R}^{3\times 3}$. The expression of the planar surface can be rearranged as follows:

$$-{\mathbf{n}^{\top}\mathbf{p^{\text{W}}}}/{b}=1.$$

(24)

Assuming that $\mathbf{p}^{\text{C}}_{\text{L}}=\mathbf{p}^{\text{W}}$ and plugging (24) and (15) into (14) results in:

$$\begin{split}\mathbf{{p^{\text{C}}_{\text{R}}}}=\mathbf{R}\mathbf{{p^{\text{C}}_{\text{L}}}}-\frac{1}{b}\mathbf{t}{\mathbf{n}^{\top}\mathbf{p^{\text{C}}_{\text{L}}}}=\bigg{(}\mathbf{R}-\frac{1}{b}\mathbf{t}{\mathbf{n}^{\top}}\bigg{)}{z^{\text{C}}_{\text{L}}}{\mathbf{K}_{\text{L}}}^{-1}\tilde{\mathbf{p}}_{\text{L}}={z^{\text{C}}_{\text{R}}}{\mathbf{K}_{\text{R}}}^{-1}\tilde{\mathbf{p}}_{\text{R}}\end{split}$$

(25)

Therefore, $\tilde{\mathbf{p}}_{\text{L}}$ and $\tilde{\mathbf{p}}_{\text{R}}$ can be linked using:

$$\tilde{\mathbf{p}}_{\text{R}}=\frac{z^{\text{C}}_{\text{L}}}{z^{\text{C}}_{\text{R}}}{\mathbf{K}_{\text{R}}}\bigg{(}\mathbf{R}-\frac{1}{b}\mathbf{t}{\mathbf{n}^{\top}}\bigg{)}{\mathbf{K}_{\text{L}}}^{-1}\tilde{\mathbf{p}}_{\text{L}}=\mathbf{H}\tilde{\mathbf{p}}_{\text{L}}.$$

(26)

The homography matrix $\mathbf{H}$ is generally used to distinguish obstacles from a planar surface fan2018road . For a well-calibrated stereo vision system, $\mathbf{R}$, $\mathbf{t}$, $\mathbf{K}_{\text{L}}$ as well as $\mathbf{K}_{\text{R}}$ are already known, and $z^{\text{C}}_{\text{L}}$ is typically equal to $z^{\text{C}}_{\text{R}}$. Thus, $\mathbf{H}$ only relates to $\mathbf{n}$ and $b$, and it can be estimated with at least four pairs of correspondences $\mathbf{p}_{\text{L}}$ and $\mathbf{p}_{\text{R}}$ fan2018road .

3D scene geometry reconstruction with a pair of synchronized cameras is based on determining pairs of correspondence pixels between the left and right images. For an uncalibrated stereo rig, finding the correspondence pairs is a 2D search process (optical flow estimation), which is extremely computationally intensive. If the stereo rig is calibrated, 1D search should be performed along the epipolar lines. An image transformation process, referred to as stereo rectification, is always performed beforehand to reduce the dimension of the correspondence pair search. The stereo rectification consists of four main steps trucco1998introductory :

1. 1.

   Rotate the left camera by $\mathbf{R}_{\text{rect}}$ so that the left image plane is parallel to the vector $\mathbf{t}$;

2. 2.

   Apply the same rotation to the right camera to recover the original epipolar geometry;

3. 3.

   Rotate the right camera by $\mathbf{R}^{-1}$;

4. 4.

   Adjust the left and right image scales by allocating an identical intrinsic matrix to both cameras.

After the stereo rectification, the left and right images appear as if they were taken by a pair of parallel cameras with the same intrinsic parameters, as shown in Fig. 9, where $\Pi_{\text{L}}$ and $\Pi_{\text{R}}$ are the original image planes; ${\Pi^{\prime}_{\text{L}}}$ and ${\Pi^{\prime}_{\text{R}}}$ are the rectified image planes. Also, each pair of conjugate epipolar lines become collinear and parallel to the horizontal image axis trucco1998introductory . Hence, determining the correspondence pairs is simplified to a 1D search problem.

A well-rectified stereo vision system is illustrated in Fig. 10,

which can be regarded as a special epipolar geometry introduced in Sec. 4.2, where the left and right cameras are perfectly parallel to each other. $x_{\text{L}}^{\text{C}}$ and $x_{\text{R}}^{\text{C}}$ axes are collinear. $\mathbf{o}_{\text{L}}^{\text{C}}$ and $\mathbf{o}_{\text{L}}^{\text{C}}$ are the left and right camera optical centers, respectively. The baseline of the stereo rig $T_{c}$, is defined as the distance between $\mathbf{o}_{\text{L}}^{\text{C}}$ and $\mathbf{o}_{\text{R}}^{\text{C}}$. The intrinsic matrices of the left and right cameras are given by:

$$\mathbf{K}_{\text{L}}=\mathbf{K}_{\text{R}}=\mathbf{K}=\begin{bmatrix}f&0&u_{o}\\ 0&f&v_{o}\\ 0&0&1\end{bmatrix},$$

(27)

respectively. Let $\mathbf{p}^{\text{W}}=[x^{\text{W}},y^{\text{W}},z^{\text{W}}]^{\top}$ be a 3D point of interest in the WCS. Its representations in the LCCS and RCCS are $\mathbf{p_{\text{L}}^{\text{C}}}=[x_{\text{L}}^{\text{C}},y_{\text{L}}^{\text{C}},z_{\text{L}}^{\text{C}}]^{\top}$ and $\mathbf{p_{\text{R}}^{\text{C}}}=[x_{\text{R}}^{\text{C}},y_{\text{R}}^{\text{C}},z_{\text{R}}^{\text{C}}]^{\top}$, respectively. Since the left and right cameras are considered to be exactly the same in a well-rectified stereo vision system, $s_{x}$ and $s_{y}$ in (9) are simply set to $1$ and $f_{x}=f_{y}=f$. $\mathbf{p}^{\text{W}}$ is projected on $\Pi_{\text{L}}$ and $\Pi_{\text{R}}$ at $\bar{\mathbf{p}}_{\text{L}}=[x_{\text{L}},y_{\text{L}},f]^{\top}$ and $\bar{\mathbf{p}}_{\text{R}}=[x_{\text{R}},y_{\text{R}},f]^{\top}$, respectively. $\mathbf{o}^{\text{W}}$, the origin of the WCS, is at the center of the line segment $L=\{t\mathbf{{o}_{\text{L}}^{\text{C}}}+(1-t)\mathbf{{o}_{\text{R}}^{\text{C}}}\ |\ t\in[0,1]\}$. $z^{\text{W}}$ axis is parallel to the camera optical axes and perpendicular to $\Pi_{\text{L}}$ and $\Pi_{\text{R}}$. Therefore, an arbitrary point $\mathbf{p^{\text{W}}}$ in the WCS can be transformed to $\mathbf{p}_{\text{L}}^{\text{C}}$ and $\mathbf{p}_{\text{R}}^{\text{C}}$ using:

$$\mathbf{p}_{\text{L}}^{\text{C}}=\mathbf{I}\mathbf{p}^{\text{W}}+\mathbf{t}_{\text{L}},\ \ \ \ \mathbf{p}_{\text{R}}^{\text{C}}=\mathbf{I}\mathbf{p}^{\text{W}}+\mathbf{t}_{\text{R}},$$

(28)

where $\mathbf{t}_{\text{L}}=[\frac{T_{c}}{2},0,0]^{\top}$ and $\mathbf{t}_{\text{R}}=[-\frac{T_{c}}{2},0,0]^{\top}$; Applying (11) and (15) to (28) results in the following expressions:

$$\begin{split}x_{\text{L}}=f\frac{x^{\text{W}}+{T_{c}}/{2}}{z^{\text{W}}},\ \ \ y_{\text{L}}=f\frac{y^{\text{W}}}{z^{\text{W}}},\\ x_{\text{R}}=f\frac{x^{\text{W}}-{T_{c}}/{2}}{z^{\text{W}}},\ \ \ y_{\text{R}}=f\frac{y^{\text{W}}}{z^{\text{W}}}.\end{split}$$

(29)

Applying (29) to (9) yields the following expressions:

$$\mathbf{p}_{\text{L}}=\begin{bmatrix}u_{\text{L}}\\ v_{\text{L}}\end{bmatrix}=\begin{bmatrix}f\frac{x^{\text{W}}}{z^{\text{W}}}+u_{o}+f\frac{{T_{c}}}{2z^{\text{W}}}\\ f\frac{y^{\text{W}}}{z^{\text{W}}}+v_{o}\end{bmatrix},\ \ \ \mathbf{p}_{\text{R}}=\begin{bmatrix}u_{\text{R}}\\ v_{\text{R}}\end{bmatrix}=\begin{bmatrix}f\frac{x^{\text{W}}}{z^{\text{W}}}+u_{o}-f\frac{{T_{c}}}{2z^{\text{W}}}\\ f\frac{y^{\text{W}}}{z^{\text{W}}}+v_{o}\end{bmatrix}.$$

(30)

The relationship between the so-called disparity $d$ and depth $z^{\text{W}}$ is as follows fan2018real :

$$d=u_{\text{L}}-u_{\text{R}}=f\frac{T_{c}}{z^{\text{W}}}.$$

(31)

It can be observed that $d$ is inversely proportional to $z^{\text{W}}$. Therefore, for a distant 3D point $\mathbf{p^{\text{W}}}$, $\mathbf{p}_{\text{L}}$ and $\mathbf{p}_{\text{R}}$ are close to each other. On the other hand, when $\mathbf{p^{\text{W}}}$ lies near the stereo camera rig, the position difference between $\mathbf{p}_{\text{L}}$ and $\mathbf{p}_{\text{R}}$ is large. Therefore, disparity estimation can be regarded as a task of 1) finding the correspondence ($\mathbf{p}_{\text{L}}$ and $\mathbf{p}_{\text{R}}$) pairs, which are on the same image row, on the left and right images and 2) producing two disparity images $\mathbf{D}_{\text{L}}$ and $\mathbf{D}_{\text{R}}$, as shown in Fig. 11.

The two key aspects of computer stereo vision are speed and accuracy tippetts2016review . Over the past two decades, a lot of research has been carried out to improve disparity estimation accuracy while reducing computational complexity. However, the stereo vision algorithms designed to achieve better disparity accuracy typically have higher computational complexity fan2018real . Hence, speed and accuracy are two desirable but conflicting properties. It is very challenging to achieve both of them simultaneously tippetts2016review .

In general, the main motivation of designing a stereo vision algorithm is to improve the trade-off between speed and accuracy. In most circumstances, a desirable trade-off entirely depends on the target application tippetts2016review . For instance, a real-time performance is required for stereo vision systems employed in autonomous driving, because other systems, such as data-fusion semantic driving scene segmentation, usually take up only a small portion of the processing time, and can be easily implemented in real-time if the 3D information is available fan2018real . Although stereo vision execution time can definitely be reduced with future HW advances, algorithm and SW improvements are also very important tippetts2016review .

State-of-the-art stereo vision algorithms can be classified as either computer vision-based or machine/deep learning-based. The former typically formulates disparity estimation as a local block matching problem or a global energy minimization problem fan2018road , while the latter basically considers disparity estimation as a regression problem luo2016efficient .

As discussed above, disparity estimation speed and accuracy are two key properties and they are always pitted against each other. Therefore, the performance evaluation of a given stereo vision algorithm usually involves both of these two properties tippetts2016review .

The following two metrics are commonly used to evaluate the accuracy of an estimated disparity image barron1994performance :

1. 1.

   Root mean squared (RMS) error $e_{\text{RMS}}$:

   $$e_{\text{RMS}}=\sqrt{\frac{1}{N}\sum_{\mathbf{p}\in\mathscr{P}}|\mathbf{D}_{\text{E}}(\mathbf{p})-\mathbf{D}_{\text{G}}(\mathbf{p})|^{2}},$$

   (41)

2. 2.

   Percentage of error pixels (PEP) $e_{\text{PEP}}$ (tolerance: $\delta_{d}$ pixels):

   $$e_{\text{PEP}}={\frac{1}{N}\sum_{\mathbf{p}\in\mathscr{P}}\delta\bigg{(}|\mathbf{D}_{\text{E}}(\mathbf{p})-\mathbf{D}_{\text{G}}(\mathbf{p})|>\delta_{d}\bigg{)}}\times 100\%,$$

   (42)

where $\mathbf{D}_{\text{E}}$ and $\mathbf{D}_{\text{G}}$ represent the estimated and ground truth disparity images, respectively; $N$ denotes the total number of disparities used for evaluation; $\delta_{d}$ represents the disparity evaluation tolerance.

Additionally, a general way to depict the efficiency of an algorithm is given in millions of disparity evaluations per second $\text{Mde}/s$ tippetts2016review as follows:

$$\text{Mde}/s=\frac{u_{\text{max}}v_{\text{max}}d_{\text{max}}}{t}{10^{-6}}.$$

(43)

However, the speed of a disparity estimation algorithm typically varies across different platforms, and it can be greatly boosted by exploiting the parallel computing architecture.