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

Question

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?

Answer 1

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]

Answer 2

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.sstatic.net/78BBP.png"], "Grayscale"];
G = MorphologicalGraph[MinFilter[img, 5]]; // AbsoluteTiming
Show[img, G, ImageSize -> Medium]

Answer 3

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

img = Import["https://i.sstatic.net/78BBP.png"];
binarized = Binarize@MeanFilter[img, 10];
distance = ImageAdjust@DistanceTransform[binarized];

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

graph2 = AdjacencyGraph[Boole@adjacencyMatrix, VertexCoordinates -> centroids];
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.