Stereo matching is also called parallax estimation and binocular depth estimation
- The input: a pair captured at the same time, passing by
Polar correctionLeft and right images ofIl
andIr
- The output: Parallax map corresponding to the parallax value of each pixel in the reference image (generally selected as the left image)
d
- According to the formula
z = b*f / d
Depth maps are availableb
: Optical center distance between two camerasf
: Focal length from the optical center of the camera to the imaging planed
: Parallax between two cameras
Background concept
In a geometric
[[Epipolar Geometry]]
Visual model
- Funnel type
- The parallel type
In the parallel stereovision model, the optical axes of the two cameras are parallel, so the opposites of the left and right images are parallel to each other and in the same image plane, so the parallax vector is parallel to the horizontal line of the image, making the parallax vector degenerate into a scalar
The basic flow
Matching cost calculation -> cost aggregation -> Parallax calculation -> parallax optimization
Matching cost calculation
- purpose: Calculated by matching cost function
Matching pixel和The candidate pixelsThe smaller the matching cost, the greater the correlation
Look for the pixels on the right that correspond to the pixels on the left, get the parallax, and you can calculate the depth based on the focal length and the distance to the center of light
- details: will limit the scope of inspection and search to
Dmin~Dmax
, so for each pixel of the reference image, use oneW*H*D
The THREE-DIMENSIONAL matrix (::DSI:: -disparity Space Image) stores the matching cost of each pixel in the parallax range - algorithm
- Photogrammetry: gray absolute value difference AD, gray absolute value sum SAD, normalized correlation coefficient NCC
- CV: Mutual information MI, Census transform CT, Rank transform RT, BT, etc
Cost aggregation
- Step to calculate the matching cost problem: only considering the local information, through the two pixels neighborhood within a certain window to the size of the pixel information calculation value, but it is easy to be affected by noise, when images are weak texture or repeated area (little noise impact of meaningful information area), the generation of value is likely to be unable to accurately reflect the correlation between pixels
- Fundamental purpose: Considering global information, DSI is optimized, so that the optimized generation value can accurately reflect the correlation between pixels
- General steps: similar to
Parallax spread.- Regions with high SNR have good initial matching effect, and the original cost can well reflect the correlation, so that the optimal parallax value can be obtained more accurately
- By establishing the relationship between adjacent pixels, the new generation value of each pixel under a certain parallax will be recalculated according to the generation value of adjacent pixels under uniform or nearby parallax (for example, adjacent pixels should have continuous parallax values).
- Spread to low signal-to-noise ratio, the matching effect is not very good
- And you end up with a new matrix
S
- Common methods: scan line generation, dynamic programming method, SGM algorithm path clustering
Note: This step is extremely critical and directly determines the accuracy of the algorithm
Parallax calculation
WTA (Winner Takes All) algorithm is used to select the parallax corresponding to the minimum generation value as the best parallax for the cost matrix S
Note again: because this has no essential operation, so the polymerization effect is very good
Parallax optimization
- purpose: Further optimize the parallax map obtained in the previous step to improve the quality of the parallax map, including
Eliminate error parallax,Appropriate smooth,Sub-pixel accuracy optimizationEtc. - algorithm
- Eliminating Error Parallax due to Occlusion and Noise: Left-Right Check algorithm
- Elimination of isolated outliers: elimination of small connected region algorithm
- Smoothing parallax graph: Median Filter, Bilateral Filter and other smoothing algorithms
- Other methods to improve the quality of parallax map include Robust Plane Fitting, Intensity Consistent constraint, Locally Consistent constraint, etc
- Sub-pixel accuracy optimization: Since the parallax value obtained by WTA algorithm is integral pixel accuracy, further sub-pixel refinement can be performed
- Unary conic fitting method: the cost under the optimal parallax and the substitution value under the left and right parallax are fitted into an unary conic, and the disparity value represented by the minimum point of the conic is taken as the subpixel disparity value after refinement
References
- Stereo Matching in 3D – Zhihu