Stereo matching is also called parallax estimation and binocular depth estimation

  • The input: a pair captured at the same time, passing byPolar correctionLeft and right images ofIlandIr
  • 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 formulaz = b*f / dDepth maps are available
    • b: Optical center distance between two cameras
    • f: Focal length from the optical center of the camera to the imaging plane
    • d: 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 functionMatching pixelThe 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 toDmin~Dmax, so for each pixel of the reference image, use oneW*H*DThe 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 toParallax spread.
    1. 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
    2. 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).
    3. Spread to low signal-to-noise ratio, the matching effect is not very good
    4. And you end up with a new matrixS
  • 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, includingEliminate 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