idamnjanovic@10: function [varargout] = reggrid(sz,num,mode)
idamnjanovic@10: %REGGRID Regular sampling grid.
idamnjanovic@10: %  [I1,I2,...,Ip] = REGGRID([N1 N2 ... Np], NUM) returns the indices
idamnjanovic@10: %  of a regular uniform sampling grid over a p-dimensional matrix with
idamnjanovic@10: %  dimensions N1xN2x...xNp. NUM is the minimal number of required samples,
idamnjanovic@10: %  and it is ensured that the actual number of samples, given by
idamnjanovic@10: %  length(I1)xlength(I2)x...xlength(Ip), is at least as large as NUM.
idamnjanovic@10: %
idamnjanovic@10: %  [I1,I2,...,Ip] = REGGRID([N1 N2 ... Np], NUM,'MODE') specifies the
idamnjanovic@10: %  method for distributing the samples along each dimension. Valid modes
idamnjanovic@10: %  include 'eqdist' (the default mode) and 'eqnum'. 'eqdist' indicates an
idamnjanovic@10: %  equal distance between the samples in each dimension, while 'eqnum'
idamnjanovic@10: %  indicates an equal number of samples in each dimension.
idamnjanovic@10: %
idamnjanovic@10: %  Notes about MODE:
idamnjanovic@10: %
idamnjanovic@10: %    1. The 'eqnum' mode will generally fail when the p-th root of NUM
idamnjanovic@10: %    (i.e. NUM^(1/p)) is larger than min([N1 N2 ... Np]). Thus 'eqdist' is
idamnjanovic@10: %    the more useful choice for sampling an arbitrary number of samples
idamnjanovic@10: %    from the matrix (up to the total number of matrix entries).
idamnjanovic@10: %  
idamnjanovic@10: %    2. In both modes, the equality (of the distance between samples, or
idamnjanovic@10: %    the number of samples in each dimension) is only approximate. This is
idamnjanovic@10: %    because REGGRID attempts to maintain the appropriate equality while at
idamnjanovic@10: %    the same time find a sampling pattern where the total number of
idamnjanovic@10: %    samples is as close as possible to NUM. In general, the larger {Ni}
idamnjanovic@10: %    and NUM are, the tighter the equality.
idamnjanovic@10: %
idamnjanovic@10: %  Example: Sample a set of blocks uniformly from a 2D image.
idamnjanovic@10: %
idamnjanovic@10: %    n = 512; blocknum = 20000; blocksize = [8 8];
idamnjanovic@10: %    im = rand(n,n);
idamnjanovic@10: %    [i1,i2] = reggrid(size(im)-blocksize+1, blocknum);
idamnjanovic@10: %    blocks = sampgrid(im, blocksize, i1, i2);
idamnjanovic@10: %
idamnjanovic@10: %  See also SAMPGRID.
idamnjanovic@10: 
idamnjanovic@10: %  Ron Rubinstein
idamnjanovic@10: %  Computer Science Department
idamnjanovic@10: %  Technion, Haifa 32000 Israel
idamnjanovic@10: %  ronrubin@cs
idamnjanovic@10: %
idamnjanovic@10: %  November 2007
idamnjanovic@10: 
idamnjanovic@10: dim = length(sz);
idamnjanovic@10: 
idamnjanovic@10: if (nargin<3)
idamnjanovic@10:   mode = 'eqdist';
idamnjanovic@10: end
idamnjanovic@10: 
idamnjanovic@10: if (any(sz<1))
idamnjanovic@10:   error(['Invalid matrix size : [' num2str(sz) ']']);
idamnjanovic@10: end
idamnjanovic@10: 
idamnjanovic@10: if (num > prod(sz))
idamnjanovic@10:   warning(['Invalid number of samples, returning maximum number of samples.']);
idamnjanovic@10: elseif (num <= 0)
idamnjanovic@10:   if (num < 0)
idamnjanovic@10:     warning('Invalid number of samples, assuming 0 samples.');
idamnjanovic@10:   end
idamnjanovic@10:   for i = 1:length(sz)
idamnjanovic@10:     varargout{i} = [];
idamnjanovic@10:   end
idamnjanovic@10:   return;
idamnjanovic@10: end
idamnjanovic@10: 
idamnjanovic@10: 
idamnjanovic@10: if (strcmp(mode,'eqdist'))
idamnjanovic@10:   
idamnjanovic@10:   % approximate distance between samples: total volume divided by number of
idamnjanovic@10:   % samples gives the average volume per sample. then, taking the p-th root
idamnjanovic@10:   % gives the average distance between samples
idamnjanovic@10:   d = (prod(sz)/num)^(1/dim);
idamnjanovic@10:   
idamnjanovic@10:   % compute the initial guess for number of samples in each dimension.
idamnjanovic@10:   % then, while total number of samples is too large, decrese the number of
idamnjanovic@10:   % samples by one in the dimension where the samples are the most crowded.
idamnjanovic@10:   % finally, do the opposite process until just passing num, so the final
idamnjanovic@10:   % number of samples is the closest to num from above.
idamnjanovic@10:   
idamnjanovic@10:   n = min(max(round(sz/d),1),sz);   % set n so that it saturates at 1 and sz
idamnjanovic@10:   
idamnjanovic@10:   active_dims = find(n>1);    % dimensions where the sample num can be reduced
idamnjanovic@10:   while(prod(n)>num && ~isempty(active_dims))
idamnjanovic@10:     [y,id] = min((sz(active_dims)-1)./n(active_dims));
idamnjanovic@10:     n(active_dims(id)) = n(active_dims(id))-1;
idamnjanovic@10:     if (n(active_dims(id)) < 2)
idamnjanovic@10:       active_dims = find(n>1);
idamnjanovic@10:     end
idamnjanovic@10:   end
idamnjanovic@10: 
idamnjanovic@10:   active_dims = find(n<sz);    % dimensions where the sample num can be increased
idamnjanovic@10:   while(prod(n)<num && ~isempty(active_dims))
idamnjanovic@10:     [y,id] = max((sz(active_dims)-1)./n(active_dims));
idamnjanovic@10:     n(active_dims(id)) = n(active_dims(id))+1;
idamnjanovic@10:     if (n(active_dims(id)) >= sz(active_dims(id)))
idamnjanovic@10:       active_dims = find(n<sz);
idamnjanovic@10:     end
idamnjanovic@10:   end
idamnjanovic@10: 
idamnjanovic@10:   for i = 1:dim
idamnjanovic@10:     varargout{i} = round((1:n(i))/n(i)*sz(i));
idamnjanovic@10:     varargout{i} = varargout{i} - floor((varargout{i}(1)-1)/2);
idamnjanovic@10:   end
idamnjanovic@10:   
idamnjanovic@10: elseif (strcmp(mode,'eqnum'))
idamnjanovic@10:   
idamnjanovic@10:   % same idea as above
idamnjanovic@10:   n = min(max( ones(size(sz)) * round(num^(1/dim)) ,1),sz);
idamnjanovic@10: 
idamnjanovic@10:   active_dims = find(n>1);
idamnjanovic@10:   while(prod(n)>num && ~isempty(active_dims))
idamnjanovic@10:     [y,id] = min((sz(active_dims)-1)./n(active_dims));
idamnjanovic@10:     n(active_dims(id)) = n(active_dims(id))-1;
idamnjanovic@10:     if (n(active_dims(id)) < 2)
idamnjanovic@10:       active_dims = find(n>1);
idamnjanovic@10:     end
idamnjanovic@10:   end
idamnjanovic@10:   
idamnjanovic@10:   active_dims = find(n<sz);
idamnjanovic@10:   while(prod(n)<num && ~isempty(active_dims))
idamnjanovic@10:     [y,id] = max((sz(active_dims)-1)./n(active_dims));
idamnjanovic@10:     n(active_dims(id)) = n(active_dims(id))+1;
idamnjanovic@10:     if (n(active_dims(id)) >= sz(active_dims(id)))
idamnjanovic@10:       active_dims = find(n<sz);
idamnjanovic@10:     end
idamnjanovic@10:   end
idamnjanovic@10:   
idamnjanovic@10:   for i = 1:dim
idamnjanovic@10:     varargout{i} = round((1:n(i))/n(i)*sz(i));
idamnjanovic@10:     varargout{i} = varargout{i} - floor((varargout{i}(1)-1)/2);
idamnjanovic@10:   end
idamnjanovic@10: else
idamnjanovic@10:   error('Invalid sampling mode');
idamnjanovic@10: end
idamnjanovic@10: