pre-allocation of array used like a FIFO stack

am writing a code for image segmentation based on region growing and am using an array as a FIFO stack , i don't know how to pre-allocate it and still can use it like a stack, am using it inside a loop so it's changinig size in every iteration and that makes my code run slow:

that's an example : ( array in question is "points_reg")

 points_reg=[points_reg;(i+vx(k)) (j+vy(k)) ];
 
 point=[points_reg(1,1) points_reg(1,2)];

        points_reg(1,:)=[];

[Uday Pradhan]

Hi Chabani, Before entering the loop how is the points_reg variable declared? Is it like a 1 - by - 2 row vector?

[chabani mohammed ali]

i declared : points_reg=zeros(1,2);

[Uday Pradhan]

So, I think at any iteration of the loop, after the horizontal concatenation, points_reg will be a 2 - by - 2 matrix. If this is the case, then we can simply do:

%initialise outside loop
points_reg = zeros(2,2);
%inside loop :
points_reg(2,:)=[(i+vx(k)) (j+vy(k))]; %add new entry in the second row
point=[points_reg(1,1) points_reg(1,2)]; %store the previous entry in point, this will get overwritten each time
points_reg(1,:)= points_reg(2,:); %replace the old entry with new one which will be chosen as "points" variable in the next iteration 

[chabani mohammed ali]

it's not the case. the size of points_reg changes "randomly"

in my code, for each point I compare it's value with the the value of each one of the 8 neighbours,

if abs( diffrence between the two values) < threshold

the neighbour is added to the same region as 'point' and his coordinates are stores at the end of points_reg.

this is a pseudo-code to explan:

while (~isempty(points_reg))

        point=[points_reg(1,1) points_reg(1,2)];

        points_reg(1,:)=[];

        i=point(1);
        j=point(2);

        

        for k = 1:8 

            if((i+vx(k))==0  || (i+vx(k))> rows ||(j+vy(k))==0 || (j+vy(k))> columns )
                continue; 
            end

            val_neighbour=I((i+vx(k)),(j+vy(k))); 
            

        
         
            if (abs(int8(mean_val) - int8(val_neighbour)) < threshold )

                 region(i+vx(k),j+vy(k))=mean_val; 
                  
                
                 
                 p=[i+vx(k)  j+vy(k)];
                
                
                
                
                 [Result,~] = ismember(p,points_reg,'rows'); 
                        
                 if (Result==0)
                     
                           points_reg=[points_reg; i+vx(k)  j+vy(k) ]
                     
                 end   
                 
             
            end   
            
        end
end

Answer 1

[Ameer Hamza]

The easiest and quickest (in terms of coding time, not efficiency) solution will be to use a cell array. Unlike numeric arrays, cell array does not require elements to be saved contiguously in memory and therefore tolerate the dynamic growth. Use each element in the cell array to store a 1x2 array. For the code in your question, something like this

points_reg{end+1}=[(i+vx(k)) (j+vy(k))];
point=points_reg{1};
points_reg(1)=[];

Here is time comparison for dynamic growth of a cell array. You can see there is no significant difference

x = {};
tic
for i = 1:1000000
    x{i} = rand(1,2);
end
t1 = toc

y = {};
tic
for i = 1:1000000
    y{end+1} = rand(1,2);
end
t2 = toc

For a million element, the output are

t1 =
    1.1684
t2 =
    1.8703

This should be an acceptable level of overhead in most cases.

[chabani mohammed ali]

thank you,

it's working but it's taking more time than the firste implementaion:

time for implementation with row vector: 13 sec

time for implementation with cell array: 54sec

i don't know if it's normal or not.

and there's somthing to change :

points_reg{1}=[];

this instruction deletes the content of the first cell not the first cell , so it became an empty array.

to delete the first cell:

points_reg(:,1)=[];

please edit it for others.