function out = dither_floyd_steinberg(im)
% function out = dither_floyd_steinberg(im)
% dithers a uint8 (8-bit) image im using the 
% Floyd-Steinberg algorithm. 
%
% out is of type uint8 and every pixel is either 0 or 255. 

% written by Ondrej Drbohlav in 2011 for the 
% Digital Image processing course. 

[M, N] = size(im); 

im = double(im); 
im = zero_enclose(im); 

valid = ones(M,N); 
valid = zero_enclose(valid);

% the error distribution matrix according to Floyd-Steinberg: 
distr = [0 0 0
         0 0 7
         1 5 3];

% uniform distribution of error:
%distr = [0 0 0
%         0 0 1
%         1 1 1];

% allocate the output image:
out = zeros(M+2, N+2, 'uint8'); 

for k=2:(M+1)
    for l=2:(N+1)
    
        % encode a pixel
        pixel_value = im(k, l); 
        % its output value 
        if pixel_value > 127 output_value = 255;
        else output_value = 0;
        end
        
        out(k,l) = output_value; 
        
        % the error is: 
        pixel_error = pixel_value - output_value;

        % distrubute this error to neighbors 
        distr_norm = sum(sum(valid(k-1:k+1, l-1:l+1) .* distr));

        if distr_norm>0 % this will be false only for the very
                        % last pixel
            correction = pixel_error * distr / distr_norm;
        end
        
        im(k-1:k+1, l-1:l+1) = im(k-1:k+1, l-1:l+1) + correction;
    end
end

out = out(2:end-1, 2:end-1); 

function x = zero_enclose(x)

[M, N] = size(x); 
b = zeros(M,1);    x = [b, x, b]; 
b = zeros(1,N+2);  x = [b; x; b]; 
