# How can I make a graph network from image of granular packing?

I have an image from experimental data of granular packing. I need to characterize the packing as a network. The network consist of node (center of granular particle) and edge. Two node are connected if there is a contact point of two granular particle.

I have tried to make a skeletonize, but it doesn't work because there are two (even more than two) node in one particle.

Can I extract the network from this image?

• Maybe this can be a starting point for you or for someone who will answer: img = ColorConvert[Import["https://i.stack.imgur.com/78BBP.png"], "Grayscale"]; dt = ImageAdjust@DistanceTransform@MedianFilter[Binarize[img], 3]. It's easy to get the disk centres from dt with MaxDetect. I do not have the time to play with this and will not post an answer. – Szabolcs Jan 13 at 12:15

Another starting point, where the objects being more or less fixed size disks is used ad hoc to measure their centroids as components after some mangling, and those which are close enough to each other are connected in the graph if out of sample of four hundred points along the edge at most four are not "white."

Image is in the variable img and plenty of magic constants are employed. (If it's not otherwise obvious, I have to make it explicit: having such hand-picked constants as 0.9, 40, 55, 300, 0.0025 or even 0.25 or 5 is definitely a weakness, not a strong point of a solution.)

(* Perform image manipulation steps, feeding from one to another. *)
(* You can replace a "//" with "// Echo //" to see an intermediate value. *)
MorphologicalBinarize[img, 0.9] // Blur[#, 40] & //
Binarize[#, 0.9] & // HitMissTransform[#, DiskMatrix[55]] & //
(* Measure component centroids on the manipulated image. *)
ComponentMeasurements[#, "Centroid"][[All, 2]] & //
Function[v,
(* Select valid edges from all pairs of components:
- those whose edge length is less than 300, and
- at most 4 values of 400 sampled along the edge have a value < 0.25 *)
Select[Subsets[v, {2}],
EuclideanDistance @@ # < 300 &&
Count[Table[Min@PixelValue[img, {t, 1 - t}.#], {t, 0, 1, 0.0025}],
_?(# < 0.25 &)] < 5 &] //
(* Overlay the graph on top of the original image. *)
Show[img,
(* Construct a graph object with vertices on component centroids,
and edges as filtered by the Select expression. *)
Graph[v, UndirectedEdge @@@ #, VertexCoordinates -> v,
VertexStyle -> Red, VertexSize -> 1/2], ImageSize -> Medium] &]


Following variant just generates the graph g:

g = (MorphologicalBinarize[img, 0.9] // Blur[#, 40] & //
Binarize[#, 0.9] & // HitMissTransform[#, DiskMatrix[55]] & //
ComponentMeasurements[#, "Centroid"][[All, 2]] & //
Function[v,
Select[Subsets[v, {2}],
EuclideanDistance @@ # < 300 &&
Count[Table[Min@PixelValue[img, {t, 1 - t}.#], {t, 0, 1, 0.0025}],
_?(# < 0.25 &)] < 5 &] //
Graph[v, UndirectedEdge @@@ #, VertexCoordinates -> v] &])


... on which you can perform graph operations:

CommunityGraphPlot[g]


• Wow, very impressive. – Henrik Schumacher Jan 13 at 12:33
• It is very good and get what I want to do this research. Thank you @kirma But as I am not expert in this notation syntax, I hope someone can transalet this syntax into step by step (line by line) notation. Thank you very much. – Iqbal Rahmadhan Jan 13 at 22:54
• And also I need to extract the graph for more exploration in network science, like community detection etc. So can I get that? – Iqbal Rahmadhan Jan 13 at 23:12
• @kirma Oh great! Thank you very much. That's all what I need. And again, thanks for your time, it's very helpful. – Iqbal Rahmadhan Jan 14 at 19:12
• I'll try to generalize this code for other data experimantation condition. Thanks. – Iqbal Rahmadhan Jan 14 at 19:13

This is far from perfect but may serve you as a starter. The main problem is the noise in the lower left corner and the upper right corner of the input image. I was able to get rid of some of it by apllying a MinFilter. Also the resulting graph may be postprocessed to remove some artifacts.

img = ColorConvert[Import["https://i.stack.imgur.com/78BBP.png"], "Grayscale"];
G = MorphologicalGraph[MinFilter[img, 5]]; // AbsoluteTiming
Show[img, G, ImageSize -> Medium]


• This will work better if you ImageResize smaller and then MorphologicalBinarize. I get nice results with MorphologicalGraph[MorphologicalBinarize[ImageResize[i, 250]]]. (Try varying the amount to resize by also) – Carl Lange Jan 13 at 12:09
• @Carl Lange Good idea. This take nicely care of the mess in the lower left corner. Several disks around the image boundaries get lost, though. Anyways, feell free to post your own solution. This question is definitely about some filtering and parameter tweaking for which I don't find time at the moment. – Henrik Schumacher Jan 13 at 12:32

First, I find the centroids of the disks (this is similar to what Szabolcs does in a comment):

img = Import["https://i.stack.imgur.com/78BBP.png"];
binarized = Binarize@MeanFilter[img, 10];

centroids = ComponentMeasurements[Binarize[distance, 0.7], "Centroid"][[All, 2]];
HighlightImage[distance, centroids, ImageSize -> 500]


Then I guess a disk radius and check how reasonable it is using HighlightImage:

disks = Disk[#, 115] & /@ centroids;
HighlightImage[
img,
Graphics[{White, disks}, Background -> Black]
]


It's not perfect, but let's compute the graph anyway:

adjacencyMatrix =
Outer[EuclideanDistance[#, #2] <= 2 115 &, centroids, centroids, 1];

Show[img, graph2, ImageSize -> 500]


As Szabolcs points out in a comment, NearestNeighborGraph can be used as well:

Show[
img,
NearestNeighborGraph[centroids, {All, 2 115}],
ImageSize -> 500
]


It has problems but there is some promise in this approach. If anyone is able to improve upon this (or if you were already working in this direction), feel free to post it as your own answer.

• An option is NearestNeighborGraph[points, {All, radius}]. – Szabolcs Jan 13 at 14:14
• @Szabolcs Thanks, that's exactly what I needed. – C. E. Jan 13 at 15:43
• It is very good. Is there a way that we can use MorphologicalGraph[] after get variabel distance? – Iqbal Rahmadhan Jan 13 at 22:57
• @IqbalRahmadhan yeah, but I didn't get great results with it. – C. E. Jan 14 at 4:11