encodespiht.m

SPIHT coding implementation. using wavelet transforms as a key tool. compression and decoding is don

function [n_max, n,out,timeel] = encodeSPIHT(m, max_bits, level)
% encodeSPIHT - SPIHT encoder
%
% parameters:        m - source image
%                    max_bits - maximal bit count on the output
%                    level - transform depth
% outputs:           out - bitstream,
%                    n_max - max. step count
%                    n - last pass info
%                    timeel - time elapsed

%-----------   initialization  -----------------

disp(' ');
disp('SPIHT enkoder spusten');

bitctr = 0;
out = 2*ones(1,max_bits - 14);
n_max = floor(log2(abs(max(max(m)'))));
Bits_Header = 0;

%-----------   stream header  ----------------
% image size, max_pass and decomp. depth

out(1,[1 2 3]) = [size(m,1) n_max level]; bitctr = bitctr + 24;
index = 4;
Bits_Header = Bits_Header + 24;

%-----------   LIP, LSP, LIS init   ----------------
temp = [];
timeel = 0;
bandsize = 2.^(log2(size(m, 1)) - level + 1); 
temp1 = 1 : bandsize; 
for i = 1 : bandsize
    temp = [temp; temp1];  
end
LIP(:, 1) = temp(:); 
temp = temp';         
LIP(:, 2) = temp(:);

LIS(:, 1) = LIP(:, 1);
LIS(:, 2) = LIP(:, 2);
LIS(:, 3) = zeros(length(LIP(:, 1)), 1);

pstart = 1;
pend = bandsize / 2;
for i = 1 : bandsize / 2
    LIS(pstart : pend, :) = [];
    pdel = pend - pstart + 1;
    pstart = pstart + bandsize - pdel;
    pend = pend + bandsize - pdel;
end

LSP = [];

n = n_max;

disp('ENCODER: init finished');
disp(['ENKODER: Max steps = ' num2str(n_max)]);

%-----------   encoding   ----------------
while(n > 0)
    bitctr_backup = bitctr;
    tic;
    
    % Sorting Pass
    % LIP pass
    LIPtemp = LIP; temp = 0;
    for i = 1:size(LIPtemp,1)
        temp = temp+1;
        if (bitctr + 1) >= max_bits  
            % bitstream end condition
            if (bitctr < max_bits)
                out(length(out))=[];
            end
            return
        end
        
       % significance?
        if abs(m(LIPtemp(i,1),LIPtemp(i,2))) >= 2^n 
            % output -> 1
            out(index) = 1; bitctr = bitctr + 1; 
            index = index +1;
            
            % sign
            sgn = m(LIPtemp(i,1),LIPtemp(i,2))>=0; 
            out(index) = sgn; bitctr = bitctr + 1; 
            index = index +1;
            
            % into LSP
            LSP = [LSP; LIPtemp(i,:)];
            
            % LIP remove
            LIP(temp,:) = []; temp = temp - 1;     
        else
            % output -> 0 (not significant)
            out(index) = 0; bitctr = bitctr + 1; 
            index = index +1;
        end
    end
    
    % LIS pass
    LIStemp = LIS; temp = 0; i = 1; 
    while ( i <= size(LIStemp,1))
        temp = temp + 1;

        % LIS is entry type A
        if LIStemp(i,3) == 0  
            if bitctr >= max_bits
                return
            end
 
            % returns highest value from the subtree
            max_d = checkDescendant(LIStemp(i,1),LIStemp(i,2),LIStemp(i,3),m); 
            % is there significance?
            if max_d >= 2^n 
                % yes - output -> 1 
                out(index) = 1; bitctr = bitctr + 1;  
                index = index +1;
                x = LIStemp(i,1); y = LIStemp(i,2); 
                
                if (bitctr + 1) >= max_bits
                    if (bitctr < max_bits)
                        out(length(out))=[];
                    end
                    return
                end

                %top-left significance
                if abs(m(2*x-1,2*y-1)) >= 2^n    
                    % YES - into LSP, output -> 1 and sign
                    LSP = [LSP; 2*x-1 2*y-1];    
                    out(index) = 1; bitctr = bitctr + 1;
                    index = index +1;
                    sgn = m(2*x-1,2*y-1)>=0;   
                    out(index) = sgn; bitctr = bitctr + 1;
                    index = index +1;
                else
                    % NOT - into LIP, output -> 0
                    out(index) = 0; bitctr = bitctr + 1;
                    index = index +1;            
                    LIP = [LIP; 2*x-1 2*y-1];
                end
                
                if (bitctr + 1) >= max_bits
                    if (bitctr < max_bits)
                        out(length(out))=[];
                    end
                    return
                end
                
                %top-right significance
                if abs(m(2*x-1,2*y)) >= 2^n   
                    LSP = [LSP; 2*x-1 2*y];
                    out(index) = 1; bitctr = bitctr + 1;
                    index = index +1;
                    sgn = m(2*x-1,2*y)>=0;
                    out(index) = sgn; bitctr = bitctr + 1;
                    index = index +1;
                else
                    out(index) = 0; bitctr = bitctr + 1;
                    index = index +1;
                    LIP = [LIP; 2*x-1 2*y];
                end
                
                if (bitctr + 1) >= max_bits
                    if (bitctr < max_bits)
                        out(length(out))=[];
                    end
                    return
                end
                
                %bottom-left significance
                if abs(m(2*x,2*y-1)) >= 2^n     
                    LSP = [LSP; 2*x 2*y-1];
                    out(index) = 1; bitctr = bitctr + 1;
                    index = index +1;
                    sgn = m(2*x,2*y-1)>=0;
                    out(index) = sgn; bitctr = bitctr + 1;
                    index = index +1;
                else
                    out(index) = 0; bitctr = bitctr + 1;
                    index = index +1; 
                    LIP = [LIP; 2*x 2*y-1];
                end
                
                if (bitctr + 1) >= max_bits
                    if (bitctr < max_bits)
                        out(length(out))=[];
                    end
                    return
                end
                
                %bottom-right significance
                if abs(m(2*x,2*y)) >= 2^n
                    LSP = [LSP; 2*x 2*y];
                    out(index) = 1; bitctr = bitctr + 1;
                    index = index +1; 
                    sgn = m(2*x,2*y)>=0;
                    out(index) = sgn; bitctr = bitctr + 1;
                    index = index +1; 
                else
                    out(index) = 0; bitctr = bitctr + 1;
                    index = index +1;
                    LIP = [LIP; 2*x 2*y];
                end
                
                % space for more descendants?
                if ((2*(2*x)-1) < size(m) & (2*(2*y)-1) < size(m)) 
                    % YES - [x,y] into LIS, LIStemp as type B entry
                    LIS = [LIS; x y 1];          
                    LIStemp = [LIStemp; x y 1];  
                end
                
                % remove [x,y, typ] from LIS
                LIS(temp,:) = []; temp = temp-1; 
                
            else
                % no significance, output -> 0 and no changes
                out(index) = 0; bitctr = bitctr + 1;  
                index = index +1;
            end
        else  
            % type B entry in LIS
            if bitctr >= max_bits
                return
            end
            
            % maximal value from grandchildren
            max_d = checkDescendant(LIStemp(i,1),LIStemp(i,2),LIStemp(i,3),m);  
            
            % do they have significance?
             if max_d >= 2^n  
                % YES - output -> 1, add their parents into LIS, LIStemp as A type
                out(index) = 1; bitctr = bitctr + 1;  
                index = index +1;
                x = LIStemp(i,1); y = LIStemp(i,2); 
                LIS = [LIS; 2*x-1 2*y-1 0; 2*x-1 2*y 0; 2*x 2*y-1 0; 2*x 2*y 0]; 
                LIStemp = [LIStemp; 2*x-1 2*y-1 0; 2*x-1 2*y 0; 2*x 2*y-1 0; 2*x 2*y 0]; 

                % remove [x,y] from LIS
                LIS(temp,:) = []; temp = temp - 1; 
            else
                % NO - output -> 0
                out(index) = 0; bitctr = bitctr + 1; 
                index = index +1;  
            end
        end
        i = i+1;
    end
    
    bitctr_backup2 = bitctr;
    
    % Refinement Pass
    temp = 1;
    value = floor(abs(2^(n_max-n+1)*m(LSP(temp,1),LSP(temp,2))));
    
    % as long as there are items in LSP compliant with the following
    % condition
    while (value >= 2^(n_max+2) & (temp <= size(LSP,1)))  
        if bitctr >= max_bits
            return
        end
        s = bitget(value,n_max+2);
        % save MSB
        out(index) = s; bitctr = bitctr + 1;
        index = index +1;
        temp = temp + 1;
        if temp <= size(LSP,1)
            value = floor(abs(2^(n_max-n+1)*m(LSP(temp,1),LSP(temp,2))));
        end
    end
    
    time = toc;
    timeel = timeel + time;
    
    disp(['ENCODER: Step ' num2str(n_max-n) ' finished in ' num2str(time) 's. Sent (S/R): ' num2str(bitctr_backup2-bitctr_backup) '/' num2str(bitctr-bitctr_backup2) 'bits.']);  
    n = n - 1;
end