# Number of pixel comparison needed to establish correspondence

I am reading the paper titled Variable Baseline/Resolution Stereo David Gallup, Jan-Michael Frahm, Philippos Mordohai, Marc Pollefeys

Section 3 of the paper talks about the time complexity of the standard stereo, within it, subsection for fixed baseline case says the following

In stereo, each pixel must be tested against the pixels along the corresponding epipolar line within the disparity range of the scene. Because the depthrange is defined by the scene, the disparity range is some fraction of the image width, and thus increases with resolution. Letting $$D$$ be the ratio of the disparity range to the image width ($$w$$), the number of pixel comparisons needed is

$$T_{fixed} = D~w^2~h = \frac{D~w^3}{a}$$

Here, symbol $$a$$ is the aspect ratio and $$h$$ is the height of the image ($$h = {w}/{a}$$).

We know that the search for correspondence is restricted to epipolar line and thus actual number of comparisons should be way lower than the number given above.
OR
I am missing something?

## 1 Answer

I am missing something?

Indeed, the context is standard stereo and (all) pixel comparisons ($$w\times h$$).

In a rectified image, the epipolar line can be typically be about the width of the image. Thus the search range would be $$D\times w$$.

Thus total number of comparisons = $$D\times w \times wh$$.