Convert an image to a graph object

Hey!

I'm working with retinal fundus images.

I have a binary image for which I have perfomed thinning followed by skeletonization and obtained the keypoints(branch points,end points, crossover points). Now I want to construct a graph object with these keypoints as nodes and add an edge between them if they are directly connected. I tried using bwlabel() but the problem I'm facing with it is that I'm getting the coordinates of points which are indirectly connected, i.e. they have another keypoint between them. How can I remove those unwanted edges? Or please suggest any other way to solve the problem.

I have attached the images here:

Image Folder

Answer 1

[Maneet Kaur Bagga]

Hi,

As per my understanding, you want to construct a graph object from a binary image with keypoints as nodes and edges representing direct connections.

Assuming you have the license to the "Image Processing Toolbox", the possible workaround for it can be as follows:

Load the skeletonized image and indentify the keypoints(branch points and endpoints) using the "bwmorph" function, then convert the identfied points to coordinates.

% Assuming 'binaryImage' is your loaded binary image
binaryImage = imread('path_to_your_image.png');
branchPoints = bwmorph(binaryImage, 'branchpoints');
endPoints = bwmorph(binaryImage, 'endpoints');
[branchY, branchX] = find(branchPoints);
[endY, endX] = find(endPoints);

Using the coordinates of the MATLAB's graph function intialize the graph without the edges initially. Following the MATLAB Documentation for the latest release till "R2024a" it does not have any direct function to have a built in function to find the direct connections between the nodes of a graph, so you can do it using custom tracing algorithms like "DFS" or "BFS".

Once the edges are generated you can visualizd the graph using "plot" function.

G = graph([], []);
for i = 1:size(directConnections, 1)
    G = addedge(G, directConnections(i, 1), directConnections(i, 2));
end
plot(G);

Please refer to the MathWorks Documentation for better understanding of the functions:

bwmorph: https://www.mathworks.com/help/images/ref/bwmorph.html

Hope this helps!

Answer 2

[Christine Tobler]

From a graph theory perspective (others may have better ideas from the image processing side), I would start by making a graph object with all the pixels in your skeletonization. You could give them XData and YData from the image, and connect two points if they're within some radius. That radius is probably best determined by plotting the resulting graph until it looks right.

Then, you would want to eliminate all the "white points", which in the graph should translate to nodes of degree two, that are part of a line of nodes connected one-by-one. I would try something like this:

• Call paths = shortestpathtree(G, someEndPoint, OutputForm="cell");
• Loop over each path in output paths
• Find all key points in the current path, discard other nodes. Note down pairs of key points.
• Now build a new graph containing only the key points, and the edges extracted in the previous algorithm.
• Call simplify on this graph, since it's likely several edges have been registered multiple times.

For example, a path might be [endPoint1 ... branchPoint1 ... branchPoint2 ... endPoint2] (with ... denoting nodes that aren't key points). You would extract from this newEdges = [endPoint1 branchPoint1; branchPoint1 branchPoint2; branchPoint2 endPoint2], adding on to this newEdges table for each path in the paths cell array.

Note here I'm assuming that all nodes are connected - if this isn't the case for some other picture, you would need to compute the connected components first, and then use one end point from each of the components.