Creating a network graph from an image

[szhorvat (Szabolcs Horvát)]

Pre-process the image to obtain a reasonable skeleton.

For example,

img = Import["https://github.com/DeepaMahm/cytoscape/raw/master/Bagah.jpeg"]

Notice that there is a white boundary. Crop it off, then pad the whole thing later to avoid trouble. Also, convert to gray.

gray = ImagePad[ImageCrop[ColorConvert[img, "Grayscale"], ImageDimensions[img] - 6],10]

Binarize with a manually chosen threshold.

bin = Binarize[gray, 0.07]

I chose to prune twice, as I obtained a better approximation of the connectivity I visually observe.

skeleton = Pruning[Pruning@Thinning[bin], 15]

Get the graph:

graph = MorphologicalGraph[skeleton]

It has some small junk in the upper left due to that letter B. Take the largest component to get rid of it. Also use SimpleGraph to get rid of one self-loop (“knot”).

But since all these functions discard properties such as vertex coordinates in 11.3, first we save them.

coordMapping = AssociationThread[VertexList[graph], GraphEmbedding[graph]];

Process graph as described above:

finalGraph = SimpleGraph@First@ConnectedGraphComponents[graph]

Re-insert coordinates:

finalGraph = Graph[ finalGraph, VertexCoordinates -> 
  Thread[VertexList[finalGraph] -> Lookup[coordMapping, VertexList[finalGraph]]] 
]

Compare with the original:

Show[img, Graph[finalGraph, GraphStyle -> "ThickEdge", EdgeStyle -> Opacity[0.6]], ImageSize -> Full]

You can see that the conversion is good, except that it does not consider multi-edges.

I do not think that there is a simple solution to deal with this problem. I have run into it myself. I believe one would need to re-implement MorphologicalGraph mostly from scratch, which I plan to do for IGraph/M at some point in the future.

If anyone has ideas about how to deal with this in a simple way purely within Mathematica (no C code), please let me know.

[deepam (Natash A)]

Thank you very much for the response. I would like to know whether it is possible to get the numbering of nodes and edges. This would allow me to manually add the missing edges at the nodes where multiple edges are present.
For instance, in MATLAB a graph is defined using the connections from tail node to head node,
Sample:

tail = [1 2 3 4 5 6 6 7 8 9 10  12 13 14 15];
head = [2 3 4 5 6 7 12 8 9 10 11 13 14 15 16];
graph(tail,head)

Would it possible to obtain this from the final step that you have shown?
Thanks a ton

[wolframcommunity (EDITORIAL BOARD)]

• Congratulations! This post is now a Staff Pick as distinguished by a badge on your profile! Thank you, keep it coming, and consider contributing your work to the The Notebook Archive!

[szhorvat (Szabolcs Horvát)]

Perhaps you mean VertexList[finalGraph] and EdgeList[finalGraph]? Do pay attention to the fact that while the vertex names of this graph are numbers, they do not coincide with the vertex indices (i.e. the position of each vertex in the VertexList).

If you would like to get a version of the graph where the vertex names are the same as the vertex indices, use indexGraph = IndexGraph[finalGraph].

[deepam (Natash A)]

I tried replicating the steps shown above
Using this command,

finalGraph = SimpleGraph@First@ConnectedGraphComponents[graph]

gives,

I notice additional terminal edges in the graph. Whereas, in the finalGraph that shows a comparison with the original, I don’t see any additional edges.
Indeed the image that I obtained after using the command given below has additional terminal edges and nodes,

skeleton = Pruning[Pruning@Thinning[bin], 15]

Also, could you please explain how the last image has been obtained? I’m curious to know how the graph has been overlapped on the original image.

Thanks a lot for the tip on indexGraph command. I’m looking for something like the example shown here, where the index of the nodes are displayed on the graph. I used those command for translating the finalGraph into a graph that displays the indices of nodes and edges. However, I suspect something went wrong, I could only get a square block.

Many thanks for the wonderful support

[szhorvat (Szabolcs Horvát)]

I included the last, missing command. If any of the commands I showed give a different output than what I show, let me know along with your Mathematica version.

First@ConnectedGraphComponents[g] can never output what you show (i.e. a non-connected graph).

[deepam (Natash A)]

I’m using Mathematica 9.0. I’m also attaching a screenshot of the outputs that I obtain

Please find my notebook here

[szhorvat (Szabolcs Horvát)]

It seems that some image processing functions worked differently in version 9. You would have to tune the parameters manually to deal with these differences (e.g. binarize differently).

Some other software, e.g. Fiji, have a feature to remove tiny loops before pruning. I think Pruning does not have this feature.

ConnectedGraphComponents does not exist in 9, but you can use Subgraph[g, First@ConnectedComponents[g]] instead of First@ConnectedGraphComponents[g].

[szhorvat (Szabolcs Horvát)]

These tiny loops that prevent pruning can be handled with something similar to this:

Thinning@ColorNegate@
  DeleteSmallComponents[ColorNegate[skeleton], 30, 
   CornerNeighbors -> False]

The idea is that each loop surrounds a small component. We “delete” (fill in) these small components, up to a size threshold, then run Thinning again. It is necessary to use ColorNegate because Mathematica considers “components” to be white, not black.

[deepam (Natash A)]

Hi,
I could generate the right figures after upgrading to Mathematica 11.3.
I would like to know how to obtain an output of the command,

skeleton = Pruning[Pruning@Thinning[bin], 15]

in the form of a matrix that stores the pixel information of the binary image. I am looking for this matrix to create a graph that can display the edges of the small branches(present at the junctions where there are multiple edges).

[szhorvat (Szabolcs Horvát)]

This one is actually easy to find … e.g. googling “image to matrix Mathematica” takes me straight to ImageData.