Subpixel Stereo Correspondence
This webpage provides the code of the ENC (Enhanced Normalized Cross Correlation) Stereo Correspondence algorithm that provides stereo disparity with subpixel accuracy (for details, see [1] ). ENCC stereo algorithm is a local (window-based) algorithm that estimates the disparity given two stereo images. Local algorithms consider a window of the left image and scan the right image (based on a predefined disparity range) for the corresponding right window. This local approach is also known as winner-takes-all method.
In short, ENCC algorithm uses a linear kernel that is embodied into the normalized cross correlation function leading thus to a continuous function of subpixel correction parameter for each candidate right window.
Two modes are enabled here:
A) a typical local mode where the disparity decision regards the central pixel only of each investigated left window and
B) a shiftable-window mode where each pixel is matched based on the best window that participate into, regardless of its position inside the window.
In case of appearance variation between images, the zero-mean counterpart of the objective function can be enabled (this essentially implies the enhanced correlation coefficient function). Note that the ECC algorithm generalizes the above function in the sense that the pure translation model is replaced by 2D affine or homography.
The current implementations use first-order backward differences to compute the image derivative as described in [1]. However, the user can modify the code and enable other types of derivatives. As a better approximation, the ENCC value can be computed for different types of derivatives and the best-score disparity can be kept.
Find please below both Matlab- and C-based (MEX file) implementations of the ENCC stereo correspondence algorithm. The latter runs much faster than the former. Note that the code is provided "as is" without any kind of warranty. The use and the redistribution of the code is only permitted for academic purposes.
Matlab Code
Download the Matlab code from HERE.
Except for the stereo images, the other input arguments are: the size of the window, the disparity range, and two flags for zero-mean version and shiftable-window mode.
Example of using ENCC algorithm in shiftable-window mode for Map stereo pair:
>> img_left=imread('left.tif');
>> img_right=imread('right.tif');
>> window_size = [11 11];
>> disp_range = 30;
>> zero_mean_flag = 0;
>> shiftable_window_flag = 1;
>> [dispa, tau, rho] = encc(img_left, img_right, window_size, disp_range, zero_mean_flag, shiftable_window_flag);
The output arguments are:
dispa: the disparity map with subpixel accuracy
tau: the subpixel correction at each position. It has been already incorporated into dispa but is returned for the detection of sticky points (possible problematic areas) by checking tau values or their variation within local areas.
rho: the otpimum ENCC value for the corresponding pair of windows.
For help, type:
>>help encc
or see the M-file encc.m.
C Code in MEX environment
A MEX function that leads to substantial speedup is provided HERE. Precompiled files for 64-bit windows systems (compiled with ms visual c++ 9) and 64-bit Linux systems (compiled with gcc) are also provided. Users that meet compatibility problems should re-combile the file enccMEX.cpp with the following command
>> mex enccMEX.cpp
Having the mex file, the user can run the enccMEX function as with encc.m (same input/output arguments):
>> [dispa, tau, rho] = enccMEX(img_left, img_right, window_size, disp_range, zero_mean_flag, shiftable_window_flag);
for help type:
>>help enccMEX
or see the file enccMEX.cpp.
Results with Map stereo pair
The main contribution of the ENCC algorithm is the disparity map with subpixel accuracy. In addition, and unlike other objective functions used by local methods, ENCC objective function can also detect sticky points (near occlusions and discontinuities). See below the results for Map stereo pair for the shiftable-window mode by using an 11x11 window-size.
>> [dispa, tau, rho] = encc(img_left, img_right, [11 11], 30, 0, 1);
Left Image
Right Image
Disparity Map with ENCC
Disparity with standard NCC
Percentage of Bad Matching Pixels with subpixel thresholds
Provided that V is the set of points that are not occluded (wrt the left image) and U is the set of points that do not belong in depth discontinuities, we evaluate the percentage of bad matching pixels in the sets V and (V AND U) sets. In specific, we count the percentage of pixels whose absolute disparity error is above the threshold delta.
Use tau to detect possible sticky points.
It is obvious that points near occlusions and depth discontinuities are likely to return false positives, especially when a local algorithm is used. When we investigate a left window that sufficiently overlaps with such areas, the true matching window in the right image does not usually reflect high similarity with the former. This makes local algorithms to choose other candidate right windows thus leading to false positives. Given a left block, ENCC algorithm solves a maximization problem for each candidate right block so that a subpixel translation is estimated. Far from the true match, ENCC estimates a relatively large value of subpixel correction (tau) in order to maximize the objective function.
Note that shiftable-window mode sensibly cancels this detection ability of the algorithm. Instead, the use of zero-mean block (zero_mean_flag=1) helps algorithm towards this kind of detection.
In the following image, the points that return |tau|>1.5 (with black), as well as the occlusion map, are shown
Detected Problematic areas
Occlusions
Depth discontinuities