function [bitstream, layer_limits] = tree2bitstream_v2(tree, max_deltas, width, height)
% -------------------------------------------------------------------------
% MSc Project - MSc in Communications and Signal Processing
% Department of Electrical and Electronic Engineering
% Imperial College London, 2011
%
% Supervisor  : Dr Pier Luigi Dragotti
% Contributor : Andriy Gelman
% Author      : Jon Onativia Bravo
%
% File        : tree2bitstream_v2.m
% -------------------------------------------------------------------------
% Encode a tree of multiple levels of precision contours of multiple images
% into a binary bitstream. If the last level of precision has a max_delta
% between consecutive vertices of 1, the vertices will be encoded using
% Freeman chain code (3 bits per vertex with 8-connectivity neighbourhood).
%
% [bitstream] = tree2bitstream_v2(tree)
%
% INPUT:
%  - tree         : Tree containing the different images' contours.
%  - max_deltas   : Maximum delta of consecutive vertices for each level of
%                   precision.
%  - width        : Width of the original shape images.
%  - height       : Heigth of the original shape images.
%
% OUTPUT:
%  - bitstream    : Binary bitstream.
%  - layer_limits : Offsets in bits of the different levels of precision.
%

max_depth     = length(max_deltas);
num_of_layers = length(tree);

[req_bits, fields]   = get_required_bits_v2(tree, max_deltas, max_depth);

% Construct the intermediate byte stream with the values still in decimal 
% format that will be stored in the final bitstream
decimal_stream = zeros(1, fields);
bits_per_field = zeros(1, fields);
layer_limits   = zeros(1, max_depth);

ith_field = 1;

% First 2 fields will contain the image size (16 bits per value)
decimal_stream(ith_field) = width;
bits_per_field(ith_field) = 16;
ith_field = ith_field + 1;
decimal_stream(ith_field) = height;
bits_per_field(ith_field) = 16;
ith_field = ith_field + 1;

% Next field will contain the number of layers
decimal_stream(ith_field) = num_of_layers;
bits_per_field(ith_field) = 8;
ith_field = ith_field + 1;

% 8 bits to store the number of levels of the tree
decimal_stream(ith_field) = max_depth;
bits_per_field(ith_field) = 8;
ith_field = ith_field + 1;

layer_limits(1) = sum(bits_per_field);

% For each layer, store the first level of approximation of the contours
for ith_layer = 1 : num_of_layers
    num_of_contours = length(tree{ith_layer});
    decimal_stream(ith_field) = num_of_contours;
    bits_per_field(ith_field) = 8;
    ith_field = ith_field + 1;
    
    for ith_contour = 1 : num_of_contours
        % Retrieve the first level of the tree
        contour_verts = tree{ith_layer}{ith_contour}{1};
        
        % Store the length of the segment
        seg_len = size(contour_verts, 2);
        decimal_stream(ith_field) = seg_len;
        bits_per_field(ith_field) = 8;
        ith_field = ith_field + 1;
        
        % Store the absolute position of the first vertex
        decimal_stream(ith_field) = contour_verts(1,1);
        bits_per_field(ith_field) = 16;
        ith_field = ith_field + 1;
        decimal_stream(ith_field) = contour_verts(2,1);
        bits_per_field(ith_field) = 16;
        ith_field = ith_field + 1;
        
        % Retrieve the number of bits per vertex offset
        offset_bits = log2(max_deltas(1) + 1) + 1;
        
        for ith_vert = 2 : seg_len
            dx = contour_verts(1,ith_vert) - contour_verts(1,ith_vert-1);
            dy = contour_verts(2,ith_vert) - contour_verts(2,ith_vert-1);
            
            decimal_stream(ith_field) = dx;
            bits_per_field(ith_field) = offset_bits;
            ith_field = ith_field + 1;
            decimal_stream(ith_field) = dy;
            bits_per_field(ith_field) = offset_bits;
            ith_field = ith_field + 1;
        end
    end
end

layer_limits(2) = sum(bits_per_field);

% Store following levels
for depth = 2 : max_depth
    offset_bits = log2(max_deltas(depth) + 1) + 1;
    
    for ith_layer = 1 : num_of_layers
        num_of_contours = length(tree{ith_layer});
        
        for ith_contour = 1 : num_of_contours
            % Number of segments of this level
            num_of_segs = length(tree{ith_layer}{ith_contour}{depth});
            
            % No need to store the number of segments because it
            % corresponds to the number of vertices of the previous
            % level
            
            if max_deltas(depth) > 1
                for ith_seg = 1 : num_of_segs
                    seg_verts = tree{ith_layer}{ith_contour}{depth}{ith_seg};
                    seg_len   = size(seg_verts, 2);

                    % Store the length of the segment
                    decimal_stream(ith_field) = seg_len-1;
                    bits_per_field(ith_field) = 8;
                    ith_field = ith_field + 1;

                    % The first vertex corresponds to the vertex of the
                    % previous level, no need to store it
                    for ith_vert = 2 : seg_len
                        dx = seg_verts(1,ith_vert) - seg_verts(1,ith_vert-1);
                        dy = seg_verts(2,ith_vert) - seg_verts(2,ith_vert-1);

                        decimal_stream(ith_field) = dx;
                        bits_per_field(ith_field) = offset_bits;
                        ith_field = ith_field + 1;
                        decimal_stream(ith_field) = dy;
                        bits_per_field(ith_field) = offset_bits;
                        ith_field = ith_field + 1;
                    end
                end
            else
                % Freeman encode the vertices
                offset_bits = 3;
                
                for ith_seg = 1 : num_of_segs
                    seg_verts = tree{ith_layer}{ith_contour}{depth}{ith_seg};
                    seg_len   = size(seg_verts, 2);

                    % Add 8 bits to store the segment length
                    decimal_stream(ith_field) = seg_len-1;
                    bits_per_field(ith_field) = 8;
                    ith_field = ith_field + 1;
                        
                    % The first vertex corresponds to the vertex of the
                    % previous level, no need to store it
                    for ith_vert = 2 : seg_len
                        dx = seg_verts(1,ith_vert) - seg_verts(1,ith_vert-1);
                        dy = seg_verts(2,ith_vert) - seg_verts(2,ith_vert-1);

                        if dx == 1 && dy == 0
                            decimal_stream(ith_field) = 0;
                        elseif dx == 1 && dy == 1
                            decimal_stream(ith_field) = 1;
                        elseif dx == 0 && dy == 1
                            decimal_stream(ith_field) = 2;
                        elseif dx == -1 && dy == 1
                            decimal_stream(ith_field) = 3;
                        elseif dx == -1 && dy == 0
                            decimal_stream(ith_field) = 4;
                        elseif dx == -1 && dy == -1
                            decimal_stream(ith_field) = 5;
                        elseif dx == 0 && dy == -1
                            decimal_stream(ith_field) = 6;
                        elseif dx == 1 && dy == -1
                            decimal_stream(ith_field) = 7;
                        end
                        
                        bits_per_field(ith_field) = offset_bits;
                        ith_field = ith_field + 1;
                    end
                    
                end
            end
        end
    end
    
    if depth < max_depth
        layer_limits(depth+1) = sum(bits_per_field);
    end
    
end

bitstream = decimal2binary(decimal_stream, bits_per_field);

if length(bitstream) ~= req_bits
    disp('The required bits and the actual bitstream length are different.')
end

end




function bitstream = decimal2binary(decimal_stream, bits_per_field)

decimal_stream = decimal_stream(:)';
num_elements   = length(decimal_stream);

% If the number of bits per field argument is not transmitted, compute it
% to be able to represent all the decimal values
if nargin == 1
    max_pos = max([0 max(decimal_stream)]);
    max_neg = min([-1 min(decimal_stream)]);
    
    N_pos = ceil(log2(max_pos + 1) + 1);
    N_neg = ceil(log2(-max_neg) + 1);
    
    N              = max([N_pos, N_neg]);
    bits_per_field = N * ones(1, num_elements);
end

if length(bits_per_field) < num_elements
    bits_per_field = bits_per_field(1) * ones(1, num_elements);
end

bitstream = false(1, num_elements);
b_idx     = 1;
for idx = 1 : num_elements
    d = decimal_stream(idx);
    N = bits_per_field(idx);
    
    b_end                  = b_idx + N - 1;
    bitstream(b_idx:b_end) = dec2bin(d, N);
    b_idx                  = b_end + 1;
end

end



