Matlab code runs too slow on three dimensional array

Tag: matlab , vector , for-loop , vectorization Author: tom_pengtao Date: 2012-12-20

I'm trying to vectorize the following code:

% code before 
% code before 
% a lot of code before we got to the current comment 
% 
% houghMatrix holds some values 
for i=1:n
    for j=1:m
        for k = 1:maximalRadius            
            % get the maximal threshold 
            if houghMatrix(i,j,k) > getMaximalThreshold(k)                           
                lhs = [j i k];

                % verify that the new circle is not listed 
                isCircleExist = verifyCircleExists(circles,lhs,circleCounter);

                % not listed - then we put it in the circles vector 
                if isCircleExist == 0
                    circles(circleCounter,:) = [j i k];                    
                    fprintf('Circle % d: % d, % d, % d \n', circleCounter, j, i, k);
                    circleCounter = circleCounter + 1;                    
                end
            end
        end
    end
end

Using tic tac I got the below outputs :

>> x = findCircles(ii);
Circle  1:  38,  38,  35 
Circle  2:  89,  51,  34 
Circle  3:  72,  66,  11 
Circle  4:  33,  75,  30 
Circle  5:  90,  81,  31 
Circle  6:  54,  96,  26 

    Elapsed time is 3.111176 seconds.
>> x = findCircles(ii);
Circle  1:  38,  38,  35 
Circle  2:  89,  51,  34 
Circle  3:  72,  66,  11 
Circle  4:  33,  75,  30 
Circle  5:  90,  81,  31 
Circle  6:  54,  96,  26 

    Elapsed time is 3.105642 seconds.
>> x = findCircles(ii);
Circle  1:  38,  38,  35 
Circle  2:  89,  51,  34 
Circle  3:  72,  66,  11 
Circle  4:  33,  75,  30 
Circle  5:  90,  81,  31 
Circle  6:  54,  96,  26 

    Elapsed time is 3.135818 seconds.

Meaning - average of 3.1 seconds .

I tried to vectorize the code , but the problem is that I need to use the index i,j,k in the body of the inner for (the 3rd for) .

Any suggestions how to vectorize the code would be greatly appreciated

Thanks

EDIT :

% -- function [circleExists] = verifyCircleExists(circles,lhs,total) --
%
%
function [circleExists] = verifyCircleExists(circles,lhs,total)

    MINIMUM_ALLOWED_THRESHOLD = 2;

    circleExists = 0;
    for index = 1:total-1                
        rhs = circles(index,:);
        absExpr = abs(lhs - rhs);
        maxValue = max( absExpr );
        if  maxValue <= MINIMUM_ALLOWED_THRESHOLD + 1
            circleExists = 1;
            break
        end
    end

end

Other Answer1

Heres what I think you want to do: For each valid coordinate triplet, you want to check whether there has been a nearby triplet already, otherwise, you add it to the list. This operation can be fully vectorized if there's no possibility of "chaining", i.e. if each cluster of possible candidate voxels can only accomodate one center. In this case, you simply use:

%# create a vector of thresholds
maximalThreshold = getMaximalThreshold(1:maximalRadius);

%# make it 1-by-1-by-3
maximalThreshold = reshape(maximalThreshold,1,1,[]);

%# create a binary array the size of houghMatrix with 1's 
%# wherever we have a candidate circle center
validClusters = bsxfun(@gt, houghMatrix, maximalThreshold);

%# get the centroids of all valid clusters
stats = regionprops(validClusters,'Centroid');

%# collect centroids, round to get integer pixel values
circles = round(cat(1,stats.Centroid));

Alteratively, if you want to follow your scheme of selecting valid circles, you can get the ijk indices from validClusters as follows:

[potentialCircles(:,1),potentialCircles(:,2), potentialCircles(:,3)]= ...  
       sub2ind(size(houghMatrix),find(validClusters));

nPotentialCircles = size(potentialCircles,1);


for iTest = 2:nPotentialCircles
    absDiff = abs(bsxfun(@minus,potentialCircles(1:iTest-1,:),potentialCircles(iTest,:)));

    if any(absDiff(:) <= MINIMUM_ALLOWED_THRESHOLD + 1)
       %# mask the potential circle
       potentialCircles(iTest,:) = NaN;
    end
end

circles = potentialCircles(isfinite(potentialCircles(:,1)),:);