Description

Stereo Matching
Computer Vision
Stereo Matching
• For pixel 𝑥0 in one image, where is the corresponding point 𝑥1 in another image?
• Stereo: two or more input views
• Based on the epipolar geometry, corresponding points lie on the epipolar lines (next lectures…)
• A matching problem

Components of a Stereo Vision System
• Calibrated cameras
• Rectified images
• Compute disparity
• Estimate depth
Image Rectification
• Re-project image planes onto a common plane
parallel to the line between optical centers.
• Pixel motion is horizontal after this transformation.
(The testing images in this assignment have been rectified.)
Image Rectification
• [Loop and Zhang 1999]

Loop and Zhang. Computing Rectifying Homographies for Stereo Vision. In CVPR 1999.

• After rectification, stereo matching becomes the disparity estimation problem.
• Disparity = horizontal displacement of corresponding points in the two images

• You need to implement Disparity Estimation in hw4.
• “Hello world” algorithm: block matching
• Consider SSD (Sum of Squared Distance) as matching cost
𝑑 0 1 2 3 … 33 … 59 60
SSD 100 90 88 88 … 12 … 77 85

• Block matching result

Ground-truth Window 5×5 After 3×3 median filter

Typical Stereo Pipeline
• It consists of 4 steps:
• Cost computation
• Cost aggregation
• Disparity optimization
• Disparity refinement
D. Scharstein and R. Szeliski. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. IJCV 2002.
Step 1: Cost Computation
• Matching cost
• Squared difference (SD): 𝐼𝑝 − 𝐼𝑞 2
• Absolute difference (AD): |𝐼𝑝 −𝐼𝑞|
• Normalized cross-correlation (NCC)
• Zero-mean NCC (ZNCC)
• Hierarchical mutual information (HMI)
• Census cost
• Truncated cost
00111010
Hamming
= 2
Distance
Image patch Local binary pattern
10111000
Hirschmuller and Scharstein. Evaluation of stereo matching costs on images with radiometric differences. PAMI 2008.
Step 2: Cost Aggregation
• Illustration of the matching cost
The disparity with min cost at certain location
Different disparities
Different pixels
Raw cost
Smoothed by box filter
Smoothed by bilateral filter
Smoothed by guided filter Ground-truth
Rhemann et al. Fast cost-volume filtering for visual correspondence and beyond. In CVPR 2011.
Step 3: Disparity optimization
• Winner-take-all

• Left-right consistency check
• Compute disparity map 𝐷𝐿 for left image
• Compute disparity map 𝐷𝑅 for right image
• Check if 𝐷𝐿 𝑥, 𝑦 = 𝐷𝑅 𝑥 − 𝐷𝐿 𝑥, 𝑦 , 𝑦
• If Yes, keep the computed disparity Note: 𝐷𝑅 are only used in this step!!
• If No, mark hole (invalid disparity) Only need to keep 𝐷𝐿 for the next step.

• Hole filling
• 𝐹𝐿, the disparity map filled by closest valid disparity from left
• 𝐹𝑅, the disparity map filled by closest valid disparity from right
• Final filled disparity map 𝐷 = min(𝐹𝐿, 𝐹𝑅) (pixel-wise minimum)
• Tips: pad maximum disparity for the holes in boundary

• Weighted median filtering

Ma et al. Constant time weighted median filtering for stereo matching and beyond. In ICCV 2013.

Assignment Description
Good News:
• computeDisp.py (TODO) you CAN use cv2.ximgproc package
with plenty of filtering operations
Maximum possible disparity
(do not need to search the disparity larger than it)
You are not forced or limited to those tips. But, they are good for you to improve your algorithm.
CANNOT use deep learning based methods.
Assignment Description
• main.py
• Read image, execute stereo matching, and visualize disparity map.
• Usage: python3 main.py –image {input_image}
• eval.py (DO NOT EDIT this file)
• Compute disparity maps of the left image for the four standard test pairs from Middlebury v2
Tsukuba Venus Teddy Cones

with gt without gt with gt without gt
• Evaluation metric: bad pixel ratio (error threshold = 1)
Package
• Python: 3.6+
• Python standard library
• https://docs.python.org/3.6/library/
• Opencv-contrib-python: 3.4.2.16
• pip3 install opencv-contrib-python==3.4.2.16
Report
• Your student ID, name
• Visualize the disparity map for all 4 testing images.
• Report the bad pixel ratio for 2 testing images with given gt.
• Describe your algorithm in terms of the standard 4-step pipeline.
Submission (1/2)
• Directory architecture:
+ R09876543/
– computeDisp.py
– report.pdf
• Put above files in a directory (named StudentID) and compress the directory into zip file (named StudentID.zip)
• e.g. R09876543.zip
• After TAs run “unzip R09876543.zip”, it should generate one directory named “R09876543”.
• If any of the file format is wrong, you will get zero point.
• Do NOT copy homeworks (code and report) from others
• Submit to NTU COOL
• Late policy: http://media.ee.ntu.edu.tw/courses/cv/22S/hw/delay_policy.pdf
Submission (2/2)
• If we can not execute your code, you’ll get 0 points. But you’ll have a chance to modify your code.
• Your code has to be finished in 10 mins.
• Otherwise, you’ll only get 70% points.
• Intel Core i7-6800K CPU + 128GB RAM
• We will execute your code on Linux system, so make sure your code can be executed on Linux system before submitting homework.

Grading (Total 15%)
• Code: 60% (15% for each testing image)
Score Tsukuba Venus Teddy Cones
15 < 8 < 5 < 18 < 15
12 >= 8 >= 5 >= 18 >= 15
5 >= 9 >= 7 >= 24 >= 20
0 >= 10 >= 10 >= 30 >= 25
• Report : 30%
• Ranking: 10% (on average score of all testing images)
• 10%, Top ~30%
• 7%, Top ~60%
• 5%, Top ~80%
• 0%, others
22
• Yu-Kai Chen (陳昱愷)
E-mail: chenyukai@media.ee.ntu.edu.tw
Location: 線上
• Chih-Ting Liu (劉致廷)
E-mail: jackieliu@media.ee.ntu.edu.tw
Location: 線上
23