Message Boards Message Boards

Creating a network graph from an image

Szabolcs Horvát
Posted 6 years ago

Pre-process the image to obtain a reasonable skeleton.

For example,

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

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]

Comparisong

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.
POSTED BY: Szabolcs Horvát
10 Replies
Sort By:

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!

POSTED BY: EDITORIAL BOARD
Natash A
Natash A
Posted 6 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];
graph(tail,head)

Would it possible to obtain this from the final step that you have shown? Thanks a ton
POSTED BY: Natash A

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 BY: Szabolcs Horvát
Natash A
Natash A
Posted 6 years ago

I tried replicating the steps shown above Using this command,

finalGraph = SimpleGraph@First@ConnectedGraphComponents[graph]

gives,

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
POSTED BY: Natash A

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 BY: Szabolcs Horvát
Natash A
Natash A
Posted 6 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
POSTED BY: Natash A

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].
POSTED BY: 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.
POSTED BY: Szabolcs Horvát
Natash A
Natash A
Posted 6 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).
POSTED BY: Natash A

This one is actually easy to find ... e.g. googling "image to matrix Mathematica" takes me straight to ImageData.
POSTED BY: Szabolcs Horvát
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract