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.

Improve this question
$\endgroup$
6
  • $\begingroup$ Try option ImageLines[...,Method-> "Segmented"->True] $\endgroup$
    – Ulrich Neumann
    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$
    – AccidentalTaylorExpansion
    Dec 30, 2021 at 17:44
  • $\begingroup$ MorphologicalGraph@Thinning@Invert@i? $\endgroup$
    – Carl Lange
    Dec 30, 2021 at 17:47
  • $\begingroup$ Ah yes,ColorNegate, not Invert $\endgroup$
    – Carl Lange
    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
    Dec 30, 2021 at 21:59

2 Answers 2

Reset to default
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

Improve this answer
$\endgroup$
12
$\begingroup$

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

img = Import["https://i.stack.imgur.com/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

Improve this answer
$\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$
    – AccidentalTaylorExpansion
    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
    Dec 31, 2021 at 13:46

Your Answer

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

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