function [ summedArea ] = calcSummedArea( energy )
%calcSummedArea Computes the summed area table
%  This computes the summed area table (from top to bottom) of the
%   provided energy function.


[width height] = size(energy);
summedArea = zeros(width, height);
summedArea(1,:) = energy(1,:);

energy(:,1) = max(max(energy));
energy(:,height) = max(max(energy));

diagonalFactor = 1.0;

for x = 2 : width
    for t = 1 : height
        best = summedArea(x-1,t);
        if (t > 1)
            if (best > diagonalFactor * summedArea(x-1,t-1))
                best = diagonalFactor * summedArea(x-1,t-1);
            end
        end
        if (t < height)
            if (best > diagonalFactor * summedArea(x-1,t+1))
                best = diagonalFactor * summedArea(x-1,t+1);
            end
        end
        summedArea(x,t) = energy(x,t) + best;
    end
end