Adding neighbours of a point on an image to an array

I am working on a region growing algorithm and I have it setup so I click a point (voxel) in an image and it adds the co-ordinates of that point to an empty zeros array (called list), as well as adding the co-ordinates of the 8 neighbouring voxels to the list. This is then in a loop so it then searches the neighbours of those 8 neighbouring voxels and also adds those to the array (list).

My issue is this then means many of the co-ordinates added to the list are repeats, as some the neighbours of the neighbours inevitably are the same voxels. I am trying to come up with some sort of exclusion statement that tells the program not to add the co-ordinates to the list if they are already in it. The relevant piece of code is below- any help/pointers would be much appreciated. P.S., the j value of 10 is arbitrary while I figure out how to proceed.

for j = 1:10
        X = list(listposition,1);
        Y = list(listposition,2);
        neighbours = [X-1 Y+1;X-1 Y;X-1 Y-1;X Y+1;X Y-1;X+1 Y+1;X+1 Y;X+1 Y-1;];
    
        for i = 1:8
           
           if neighbours(i,1)>=1&&neighbours(i,1)<=size(A,2)&&neighbours(i,2)>1&&neighbours(i,2)<size(A,1)
                listposition = listposition + 1;
                list(listposition,1) = neighbours(i,1);
                list(listposition,2) = neighbours(i,2);
               
          
            end
        end
    end

Answer 1

[VINAYAK LUHA]

Hi Henry,

It is my understanding that the “Region Growing Algorithm” you want to implement is popularly known as Breadth First Search (BFS) in literature which involves visiting all the coordinates at the same level in the grid (image) before moving to the next level. It starts at a given source coordinate and then explores its neighbouring coordinates before progressing to the subsequent level of coordinates.

Follow the below steps to implement the said “Region Growing Algorithm”:

• Initialize a 2D matrix “vis” to mark the visited coordinates.
• Initialize a queue called “q” to keep track of the coordinates that need to be visited in a given level.
• Begin exploration by enqueuing the source coordinate set in the queue “q”, register this event by setting 1 against the enqueued coordinate set in the “vis” matrix.
• While the queue “q” is not empty, perform the following steps:
• Dequeue a coordinate set from the front of the queue “q”.
• Explore all the adjacent vertices of the dequeued coordinate set that have not been visited.
• Enqueue each unvisited adjacent coordinate set into the queue.
• Mark each visited coordinate set as explored.

Once the queue is empty, the BFS algorithm has explored all reachable coordinates from the source coordinate.

Kindly refer to the below code snippet for understanding the implementation of the algorithm:

grid = zeros(100,100,3);
vis  = zeros(size(grid));
drs  =[[-1,0];[-1,1];[0,1];[1,1];[1,0];[1,-1];[0,-1];[-1,-1]];
vis=bfs(50,50,grid,vis,drs);

function vis=bfs(i,j,grid,vis,drs)
q=[[i,j]];
vis(i,j)=1;
while(~isempty(q))
    e     =q(1,:);
    grid(e(1,1),e(1,2),:)=[255,0,0];
    drawnow
    imshow(grid);
    q     =q(2:end,:);
    for k=1:8
        ni=e(1,1)+drs(k,1);
        nj=e(1,2)+drs(k,2);
        if(isvalid(ni,nj,vis,grid))  
            q=[q;[ni,nj]];
            vis(ni,nj)=1;
        end        
    end    
end
end

function x=isvalid(i,j,vis,grid)
if(i>size(grid,1)||i<1||j>size(grid,2)||j<1||vis(i,j)==1)
    x=0;    
else   
    x=1;    
end
end

I hope that this provides you with a deeper understanding of the algorithm.

Regards,

Vinayak Luha