Title: Stereo Vision

Q: Erkläre die Stereo Pipeline
A: Rectification is a transformation process used to project images onto another image plane.
Epipolar Rectification is a special case of this, where two images are projected onto the same plane. In this epipolar plane we only have to search along the epipolar line (1D instead of 2D search). The baselines of the images are parallel to the x-axis, thus Epipolar lines coincide with horizontal scanlines. Epipolar Rectification is required to enforce the epipolar constraint.
Stereo Matching means generating a disparity map of two 2D images. This was the whole task of the exercise.
Depth via Triangulation calculates the Z-coordinate / depth of a pixel. By utilizing static information from camera calibration and the disparity, one can calculate the depth (via Simmilar Triangles).

Q: Window-Based Matching (+ Sliding Window, + Problems, + Large vs. Small)
A: ... is a method of local stereo.
Instead of matching just a single pixel, we center a small window on a pixel and match the whole window in the right image.
Formally:
Sliding Window Technique
Run-time depends largely on the window size, thus it is quite expensive and slow. However, a trick called the sl. w. tech. can be used to speed this up.
Large parts of the computation can be reused. Subtract one pixel, add another. Incremental computation => Large Speedup.
Problems
Untextured Regions
Aperture Problem (Horizontally equal textures)
Repetitive Patterns
Foreground Fattening Problem (All pixels within the window are assumed to have the same disparity => systematic error in regions close to disparity discontinuities.)
Large vs. Small Windows
Large windows better to handle:
* Untextured Regions
* Aperture Problem
* Repetitive Patterns
Small windows better to handle:
* Foreground Fattening Problem
=> Adaptive Windows

Q: Explain the Occlusion Problem
A: Pixels in the back are occluded. Left camera sees different pixel as right camera.
Occlusion Handling
* Left-Right Consistency Check => Occlusion Filling

Q: Explain the Idea of Dynamic Programming (Global Stereo)
A: ... is a global stereo Method. Optimization of E is np-complete.
However, there is a special case: If the graph is a tree => Dynamic Programming
How to remove edges from Graph, such that it becomes a tree?
- Scanline DP
- Tree DP by Veksler
- Semi-Global Matching by Hirschmueller
- Simple Tree by Bleyer
Pros and Cons
+ very fast
+ Good tradeoff between speed and accuracy
- Only for trees :-(

Dynamic Programming Example

Describe the Min-Cut Problem

Q: Describe an iterative algorithm for the fusion move
A: Start with an arbitrary labeling f
For each proposal g:
* Find f* = argmin E(f’) among f’ being one possible fusion of f and g.
* f := f

Q: Boolean Fusion Move Energy
* what is the meaning of x_p
* Are there any problems?
A: • xp = 0, if p takes the label of proposal 1
• xp = 1, if p takes the label of proposal 2
The Fusion Energy Can Be Non-Submodular
Finding the optimal fusion move is, in general, an np-complete problem
However, nowadays there exist powerful graph-cut-based optimization algorithms that can handle non-submodular energies

Explain Belief Propagation formally

Q: Which Smoothness Term Variants are there? What do they penalize?
A: First order smoothness functions:
* Linear smoothness function
* Potts model / Modified Potts Model
* Truncated linear smoothness function / Truncated Linear Model
Penalize disparity gradient
Second Order Smoothness
* Edge-Sensitive Smoothness Term
* Segment-Sensitive Smoothness Term
Penalizes curvature

Q: What is the Linear Smoothness Function?
How can the linear smoothness term be converted to a graph? (Min-Cut)
A: Basics
Smoothness function computed as absolute disparity difference
s(p,q) = |d_p - d_q)| * P
Forms a special case in which a global optimal solution can be computed via graph cuts
Computing the Global Optimum
Min-Cut / Graph
This cut assigns p to disparity 3 and q to disparity 1.
The costs are: m(p,3)+m(q,1)+2P
Problem
When using a linear smoothness function, the costs for many small jumps are not higher than the costs for one big jump in disparity.
=> leads to blurry disparity discontinuities
=> therefore called non-discontinuity preserving
A linear smoothness function is a poor choice for stereo.

Q: Why do we need Second Order Smoothness?
What is penalized with SOS?
Advantages and Problems
A: SOS penalizes the curvature of a surface
Three points are required to calculate the curvature c
c(p,q,r) = |dp-2dq+dr| ... where p and r are q’s left and right neighbors
This value is then truncated, same as in the trunc. linear model
s(p,q,r) = min(c(p,q,r), k) * P
Advantages
Curvature is 0 if the surface is a plane
=> Fronto-parallel planes are no longer cheaper than slanted planes
Problems
Planar favored over rounded (Might be ok)
SOS requires three pixels. Thus it is called a higher-order term. Minimizing these is a very challenging problem.

Q: What is the Data Term Squared Intensity Difference?
* Definition
* Is it a good choice?
A: m(p,q) = (Ip - Iq)²
Probably not a good choice:
* Sensitive to outliers
* Typically performs slightly worse than absolute difference

Q: Data Term: Sampling Insensitive Measure
* Problem, Idea
* Definition
A: Problem: Samples are typically taken at different curve positions in the left and right images.
=> Different intensities.
Idea: Look at the neighboars (and interpolate)
p- = (Iq + Ip)/2
Advantage: We have also included the “correctly sampled” pixel p-
=> low intensity dissimilarity and high chances for correct match

Q: What is the Mutual Information data term?
* Chicken and Egg problem
* Advantages / Disadvantages
* Calculation
* Algorithm
A: Computing Mutual Information Scores
For each pixel p, we look-up its matching point q in the right image using our current disparity map.
Note the Intensity Ip and Iq in a <Ip, Iq> datagram
Transform the datagram to mutual information scores, with P = -log(P)
=> Those intensity pairs that occurred frequently should be given low matching costs.
Chicken and Egg problem, Algorith
The score requires a disparity, which is not available at the beginning. Thus following algorithm often used:
1. Calculate disparity map using some other mean
2. Repeatedly Compute new Disparity map using Mutual Information Scores
Advantage
Mutual Information is a pixel-based measure.
In contrast to window-based measures, artifacts at disparity borders are avoided
Disadvantages
Mutual Information can only model radiometric changes that are valid for the whole image.
eg. the whole left image is darker than the right one.
=> It cannot model radiometric changes that occur only locally
Unfortunately, radiometric distortions are oftentimes local. :-(

Q: Data Term: Census
* Calculation / Algorithm
* Discussion
A: We do not directly match the intensities, but the loca texture represented as a bit-string.
=> Problems in untextured regions