14
$\begingroup$

I have the following image

enter image description here

Is it possible to extract the lines from this image and then convert those lines to a graph representation? I tried using ImagesLines[] with Binarize[] but got very bad results.

$\endgroup$
6
  • $\begingroup$ Try option ImageLines[...,Method-> "Segmented"->True] $\endgroup$ Commented Dec 30, 2021 at 17:37
  • $\begingroup$ @UlrichNeumann I tried that but the lines didn't line up with the image, there were either too many lines or many lines were missing. $\endgroup$ Commented Dec 30, 2021 at 17:44
  • $\begingroup$ MorphologicalGraph@Thinning@Invert@i? $\endgroup$
    – Carl Lange
    Commented Dec 30, 2021 at 17:47
  • $\begingroup$ Ah yes,ColorNegate, not Invert $\endgroup$
    – Carl Lange
    Commented Dec 30, 2021 at 18:27
  • $\begingroup$ Do you have the image in its original scale, in a non-lossy (non-JPEG) format? $\endgroup$
    – Szabolcs
    Commented Dec 30, 2021 at 21:59

2 Answers 2

21
$\begingroup$
g = IndexGraph[
  MorphologicalGraph[
   Thinning[ColorNegate[Binarize[pic]], Method -> "MedialAxis"]]]

enter image description here

Then you can merge vertices that are close each other:

pts = GraphEmbedding[g];

Median[EuclideanDistance[pts[[#[[1]]]], pts[[#[[2]]]]] & /@ 
  EdgeList[g]]

13.0384

f = Nearest[Thread[pts -> Range[Length[pts]]]]

merge = Select[f[#, {All, 10}] & /@ pts, Length[#] > 1 &];

You can check the grouping of vertices:

HighlightGraph[g, merge, VertexSize -> 1]

enter image description here

and final graph:

final = Fold[VertexContract, g, merge]

enter image description here

$\endgroup$
12
$\begingroup$

First, use the method of deleting the branch points developed in this answer:

img = Import["https://i.sstatic.net/aLhGVm.png"];

imb = Thinning[ColorNegate@Binarize@img];

edges = DeleteSmallComponents@MorphologicalTransform[imb, 
   If[#[[2, 2]] == 1 && Total[#, 2] == 3, 1, 0] &];

edgesLabeled = MorphologicalComponents[edges];
edgesLabeled // Colorize

image

Second, extract the branch points (nodes) and separate them from the edges by making their labels sufficiently large, as I did here:

nodes = imb - edges;
threshold = 10^Ceiling[Log10[Max[edgesLabeled] + 1]];
nodesLabeled = MorphologicalComponents[nodes] * threshold;
nodesLabeled // Colorize

image

edgesPlusNodesLabeled = edgesLabeled + nodesLabeled;
edgesPlusNodesLabeled // Colorize

image

Now it is easy to reconstruct the graph:

neighbors = 
  ComponentMeasurements[edgesPlusNodesLabeled, 
   "Neighbors", #Label < threshold &];
coords = ComponentMeasurements[edgesPlusNodesLabeled, 
   "BoundingDiskCenter", #Label >= threshold &];

Graph[UndirectedEdge @@@ neighbors[[All, 2]], 
 VertexCoordinates -> coords, VertexSize -> .2]

graph

Overlay on the original image:

HighlightImage[img, {Thick, Line /@ neighbors[[All, 2]] /. coords, 
  Green, Translate[Disk[{0, 0}, Offset[2]], coords[[All, 2]]]}]

image

$\endgroup$
2
  • 2
    $\begingroup$ Your answer and halmir's are both excellent! If I could accept two I would have but I chose the halmir's because it's simpler. $\endgroup$ Commented Dec 31, 2021 at 11:43
  • $\begingroup$ This is a particularly interesting question, and I asked a similar question for non-planar graphs. See mathematica.stackexchange.com/questions/261413/… $\endgroup$
    – licheng
    Commented Dec 31, 2021 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.