How to obtain adjacency matrix from a binary image?

Hi Mathworks Community,

I need your help to calculate the adjacency matrix of a binary image. Namely, the built-in MATLAB funciton bwconncomp(BW) allows me to find and to count the connected components in the binary image BW. However, I also need to extract the adjacency matrix for this image. Because I am working with a 3D image, I am using the 6-connectivity metric to define links in the adjacency matrix.

For easy illustration of what I want to achieve, consider the following 2D binary problem:

I have added, in red, numbers to label each pixel as a "vertex" in the underlying graph that could describe this binary image. Because I am interested in the 6-connectivity in 3D problems, in a example 2D problem, this definition corresponds to the 4-connectivity, i.e., a link exists between two squares that share a face, but does not exist for squares that neighbor each other diagonally. Therefore, I am looking for a funciton (or an approach) to obtain the following adjacency matrix:

My current approach ends up with too many if-statements that make the calculation very slow. Is there a way to directly extract the adjacency matrix from bwconncomp(BW) or a related function?

Thank you!

Answer 1

[Joel]

Hi,

You can try this approach:

1. Get connected components of image using ‘bwconncomp’. This should give the indices that are connected components.
2. Iterate through each set of connected components and check which elements in that set are neighbours. You can do this by considering 4 elements i.e. x+m, x-m, x+1, x-1 where x is the index and m is number of rows.
3. For e.g. if x and x+m are present in the array of connected components, you can add them to respective arrays.
4. Previous step can also be optimized by checking for indices that are out of bounds.
5. Now you can use the ‘graph’ and ‘adjacency’ functions to get your adjacency matrix.

Please refer to the following documentation for more information:

Graph with undirected edges - MATLAB - MathWorks India

Graph adjacency matrix - MATLAB adjacency - MathWorks India