Message Boards Message Boards


Creating a network graph from an image

Posted 3 years ago
10 Replies
13 Total Likes

Pre-process the image to obtain a reasonable skeleton.

For example,

img = Import[""]

enter image description here

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]

Mathematica graphics

Binarize with a manually chosen threshold.

bin = Binarize[gray, 0.07]

Mathematica graphics

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

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

enter image description here

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.

10 Replies
Posted 3 years ago

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];

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

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].

Posted 3 years ago

I tried replicating the steps shown above Using this command,

finalGraph = SimpleGraph@First@ConnectedGraphComponents[graph]


enter image description here

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]

enter image description here

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

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).

Posted 3 years ago

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

enter image description here

Please find my notebook here

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].

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

  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.

Posted 3 years ago

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).

This one is actually easy to find ... e.g. googling "image to matrix mathematica" takes me straight to ImageData.

enter image description here - 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!

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract