Implementation of Absolute Differences Stereo Matching Algorithm

Good day!

I am trying to learn how to manually implement stereo matching algorithms. I'm basically starting with the most basic of them all - Absolute Difference.

I found some slides online that describe how to do it. Basically, from what I understand, I should calculate the difference between the pixels in my left image and the same pixel in the right image "shifted" by a certain distance/disparity. Then among these disparities, I select the minimum, which makes sense to me since the pixel with the lowest disparity means that it is most likely the same pixel in the left image.

I've prototyped that in MATLAB. Here is the code:

im_left = imread('tsu_left.png');
im_right = imread('tsu_right.png');

height = size(im_left, 1);
width = size(im_left, 2);

disparity_max = 16;

ad_costs = zeros(height, width,disparity_max);

for disparity = 1:disparity_max
    for row = 1:height
        for col = 1:width
            %Left to right matching
            col_disp = col - disparity;
            if col_disp < 1
                ad_costs(row, col, disparity) = 0;
            else
                %Average RGB
                left_pixel = (im_left(row, col, 1) + im_left(row, col, 2) + im_left(row, col, 3))/3;
                right_pixel = (im_right(row, col_disp, 1) + im_right(row, col_disp, 2) + im_right(row, col_disp, 3))/3;

                %Subtract averages
                ad_costs(row, col, disparity) = abs(left_pixel - right_pixel);
            end
        end
    end
end

min_costs = zeros(height, width);

for disparity = 1:disparity_max
    for row = 1:height
        for col = 1:width
            %The minimum disparity is chosen
            min_costs(row, col) = min(ad_costs(row, col, :));
        end
    end
end

Take note that I haven't implemented the variant where the differences in a certain window is summed, leading to Sum of Absolute Differences. I am only taking the difference per pixel, per disparity. The lecture slides I found online says that it should look like this (rightmost image):

https://dl.dropboxusercontent.com/u/92715312/lec.PNG

However, the result from the code above (using imshow(min_costs)) yield something like this:

https://dl.dropboxusercontent.com/u/92715312/res.PNG

I can't figure out why the outputs are so different. Is there some trivial step that I am missing, or is my understanding of how the algorithm works wrong? I am also using the tsukuba image.

This is most probably an imshow issue. The function imshow excepts the image to be in the range [0, 255] if it is a uint8, or [0.0, 1.0] if floating point.

Try:

imshow(min_cost, []);

Note, the empty array for the second argument. This tells Matlab to figure out the scaling.

Or, use:

imagesc(min_cost); axis image off;

EDIT:

Vanilla rectified stereo with some pixel dissimilarity meaure is fairly simple. See the code below:

function [D, C_min, C] = stereo_sad(I1, I2, min_d, max_d, w_radius)
  % function [D, C_min, C] = stereo_sad(I1, I2, min_d, max_d, w_radius)
  %
  % INPUT
  %   I1 the left stereo image
  %   I2 the right stereo image
  %   min_d minimum disparity
  %   max_d maximum disparity
  %   w_radius the radius of the window to do the AD aggeration
  %
  % OUTPUT
  %   D disparity values
  %   C_min cost associated with the minimum disparity at pixel (i,j)
  %   C  the cost volume for AD
  %

  if nargin < 5, w_radius = 4; end % 9x9 window
  if nargin < 4, max_d = 64; end
  if nargin < 3, min_d = 0; end

  % aggregation filter (window size to aggerate the AD cost)
  kernel = ones(w_radius*2+1);
  kernel = kernel ./ numel(kernel); % normalize it

  % grayscale is sufficient for stereo matching
  % the green channel is actually a good approximation of the grayscale, we
  % could instad do I1 = I1(:,:,2);
  if size(I1,3) > 1, I1 = rgb2gray(I1); end
  if size(I2,3) > 1, I2 = rgb2gray(I2); end

  % conver to double/single
  I1 = double(I1);
  I2 = double(I2);

  % the range of disparity values from min_d to max_d inclusive
  d_vals = min_d : max_d;
  num_d = length(d_vals);
  C = NaN(size(I1,1), size(I1,2), num_d); % the cost volume

  % the main loop
  for i = 1 : length(d_vals);
    d = d_vals(i);
    I2_s = imtranslate(I2, [d 0]);
    C(:,:,i) = abs(I1 - I2_s); % you could also have SD here (I1-I2_s).^2
    C(:,:,i) = imfilter(C(:,:,i), kernel);

  end

  [C_min, D] = min(C, [], 3);
  D = D + min_d;

end

To run the code

I1 = imread( ... your left image I2 = imread( ... your right image) D = stereo_sad(I1, I2, 0, 96, 4); imagesc(D); axis image off; colorbar

You will get a disparity map like the one below

The steps are:

1. shift the right image at every disparity
2. compute the Absolute Difference between the shifted image and the left image (or some other measure, like SSD)
3. Average with a rectangular window, this is a "box" filter
4. Store the averages in a cost "volume" per pixel
5. Disparity is located at the minimia of the cost volume per pixel. Disparity will be in the index into the minima

The operations can be done with builtin Matlab tools to produce easily readable code.

Hope that helps.