GetRandomEllipseImage3D.m

% GetRandomEllipseImage3D(K)
% generate a logical image with K overlapping ellipses
% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Copyright (c) 2016, Drexel University
% All rights reserved.
% 
% Redistribution and use in source and binary forms, with or without
% modification, are permitted provided that the following conditions are met:
% 
% * Redistributions of source code must retain the above copyright notice, this
%   list of conditions and the following disclaimer.
% 
% * Redistributions in binary form must reproduce the above copyright notice,
%   this list of conditions and the following disclaimer in the documentation
%   and/or other materials provided with the distribution.
% 
% * Neither the name of PixelRep nor the names of its
%   contributors may be used to endorse or promote products derived from
%   this software without specific prior written permission.
% 
% THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
% AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
% IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
% DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
% FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
% DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
% SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
% CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
% OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
% OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function [bw,pts]=GetRandomEllipseImage3D(K)

IMSIZE = [200,200,200];
mu = [100,100,100];

bw = false(IMSIZE);

pts = {};
bValidEllipse=0;

while ~bValidEllipse
    for kk=1:K
        pts{kk} = GetRandomEllipsePts(mu);
    end
    
    % place each ellipse
    for kk=2:K
        ptsCombined=vertcat(pts{1:kk-1});
        idxK = 1+round((length(pts{kk})-1)*rand());
        idxCombined = 1+round((length(ptsCombined)-1)*rand());
        offset = ptsCombined(idxCombined,:)-pts{kk}(idxK,:);
        pts{kk} = pts{kk} + repmat(offset,[size(pts{kk},1), 1]);
    end
    idxPts={};
    for kk=1:K
        idxPts{kk}=sub2ind(IMSIZE,pts{kk}(:,1),pts{kk}(:,2),pts{kk}(:,3));
    end
    
    idxPtsOverlap=GetOverlap(idxPts);
    % make sure no ellipse is fully contained in another
    nNonOverlap=idxPtsOverlap(2.^[0:K-1]);
    nNonOverlap=cellfun(@length,nNonOverlap);
    if all(nNonOverlap~=0)
        bValidEllipse=1;
    end
end

ptsCombined=round(vertcat(pts{:})); 
idxCombined=sub2ind(size(bw),ptsCombined(:,1),ptsCombined(:,2),ptsCombined(:,3));
bw(idxCombined)=1;
end


function pts = GetRandomEllipsePts(mu)
maxRad = 30;

sig = randEllipse(maxRad);

pts = genEllipseCoordPts(mu, sig);

end

function Sigma = randEllipse(maxRad)
    % Generate random ellipse size and orientation
    
    % Axis ratios (0.3,1.0)
    randRat = 0.7*rand(1,3) + 0.3;
    
    % Principal axis radii created as cumulative product of axis ratios
    paRad = maxRad * randRat;
    
    % Generate random orientation by subspace algorithm [1] uses a
    % Householder transform with an implicit reflection of the ith
    % axis, this guarantees the total transform is a rotation.
    % 
    % [1] Diaconis and Shahshahani, "The subgroup algorithm for generating uniform random variables".
    %     Probability in the Engineering and Informational Sciences, 1(01), 15-32, 1987.
    R = 1;
    for i=2:3
        % Uniform vector on i-dimensional unit sphere
        Gs = randn(i,1);
        Us = Gs ./ sqrt(sum(Gs.^2));
        
        ei = [-1; zeros(i-1,1)];
        v = (ei-Us) / sqrt(sum((ei-Us).^2));
        
        subR = [ei [zeros(1,i-1); R]];
        R = subR - 2*v*(v'*subR);
    end

    Lambda = diag(paRad);
    A = Lambda * R;
    
    Sigma = A'*A;
end

function points = genEllipseCoordPts(mu, Sigma)
    d = size(mu,2);
    projSig = ceil(sqrt(max(abs(Sigma),[],1)));
    
    coordRange = cell(1,d);
    for i=1:d
        coordRange{i} = round([-projSig(i):projSig(i)] + mu(i));
    end
    
    gridCell = cell(1,d);
    [gridCell{:}] = meshgrid(coordRange{:});
    
    gridPts = zeros(numel(gridCell{1}),d);
    for i=1:d
        gridPts(:,i) = gridCell{i}(:);
    end
    
    vt = (gridPts - repmat(mu, size(gridPts,1),1));
    bInside = (sum((vt/Sigma) .* vt,2) <= 1);
    
    points = gridPts(bInside,:);
end

function idxPtsOverlap=GetOverlap(idxPts)

K=length(idxPts);
idxPtsOverlap={};
% idxPtsOverlap goes from 1..2^K-1
% the index is a binary vector specifying the overlap regions,
% e.g. 1,2,4,8, etc are points only in ellipses 1,2,3,4 etc.
% 3 is in 1 and 2, 5 is in 4 and 1, etc.
% no overlap between superset and subset pixels
for n=1:(2^K)-1
    rgBinary=de2bi(n);
    idx1 = find(rgBinary);
    if length(idx1)==1
        idxPtsOverlap{n}=idxPts{idx1};
        continue
    end
    nIntersect=idxPts{idx1(1)};
    for i=2:length(idx1)
        nIntersect=intersect(nIntersect,idxPts{idx1(i)});
    end
    idxPtsOverlap{n}=nIntersect;
end

for i=1:length(idxPtsOverlap)
    for j=1:length(idxPtsOverlap);
        if i==j
            continue
        end
        rgBinaryI = de2bi(i);
        rgBinaryJ = de2bi(j);
        
        if length(find(rgBinaryI))<length(find(rgBinaryJ))
            idxPtsOverlap{i}=setdiff(idxPtsOverlap{i},idxPtsOverlap{j});
        end
    end
end
end