18
$\begingroup$

I am trying to convert an image to a graph. My image is already skeletonized and looks pretty much like this:

enter image description here

What I need to do is identify all vertices and edges, and in particular get a list of pixel positions for each edge. I've seen that using MorphologicalGraph would get me the vertices, but is there any way to also extract information about the position of the edges?

EDIT: First, thanks a lot for all your comments! Let me clarify. @acl: I would like the lists of pixel coordinates for each edge to be grouped together. @Yves Klett: I think that this solution would not work, it gives a morphological graph and I need the pixel coordinates from the original image. @Silvia, @Daniel Lichtblau: I could extract all pixel positions this way, but I need to know which pixel belongs to which branch...

@Vitaliy Kaurov: I need to know which vertex is connected to which, and this can be done using MorphologicalGraph. But I also need to know the exact path between 2 vertices, so for each branch on the image, I need the list of pixel coordinates. As you show in your answer, edges found using MorphologicalGraph do not match single-pixel image branches (and I need the latter). I guess that Silvia's answer would be a solution. What's interesting though is that to get to the morphological graph, Mathematica has to process the information on the pixel coordinates of the branches! But probably doesn't store it anywhere???

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Is this helpful: How to convert a 2D image into a 3D graphics? ? $\endgroup$
    – Yves Klett
    Jul 31, 2012 at 19:29
  • 2
    $\begingroup$ If what you want is the coordinate of EVERY point on a edge, maybe you just Binarize the image and Position all 1 in the ImageData array? $\endgroup$
    – Silvia
    Jul 31, 2012 at 19:39
  • 2
    $\begingroup$ do you want the lists of pixel coords for each edge to be grouped together? $\endgroup$
    – acl
    Jul 31, 2012 at 19:44
  • $\begingroup$ There is some code here to convert an image of a maze into a graph with edges and all. $\endgroup$
    – Daniel Lichtblau
    Jul 31, 2012 at 20:03
  • 1
    $\begingroup$ Could you please specify more precisely what you need, especially in the light of comments by Silvia, acl and my answer. Then we can help you more. $\endgroup$
    – Vitaliy Kaurov
    Jul 31, 2012 at 20:28

2 Answers 2

Reset to default
18
$\begingroup$

Though vertex coordinates of the MorphologicalGraph graph are given in terms of image pixel dimensions:

i = Import["https://i.stack.imgur.com/cET4A.png"];
g = MorphologicalGraph[i, EdgeStyle -> Directive[Orange, Opacity[.5], Thickness[.01]], 
  GraphStyle -> "ThickEdge"];

AbsoluteOptions[g, VertexCoordinates]

enter image description here

edges and single-pixel image branches will not exactly match:

Show[ColorNegate@Dilation[i, 1], g]

enter image description here

But we can use vertex coordinates of the graph to arrive to indexing pixels for true image branches. This builds an image where white pixels present only at vertexes (or branching points):

vi = Image[Reverse@ReplacePart[ConstantArray[0, Reverse@ImageDimensions[i]], (# ->1)&
/@Reverse /@ Round[AbsoluteOptions[MorphologicalGraph[i], VertexCoordinates][[2]]]]];

And this removes branching points (make them equal to background). Note I use weak Dilation to make sure I disconnect all the branches.

mc = MorphologicalComponents[ImageMultiply[i, ColorNegate[Dilation[vi, 2]]]]; 
Dilation[ mc // Colorize, 3]

enter image description here

This app shows how you can pick and highlight different branches:

Manipulate[Show[ImageAdd[i,Dilation[Image[SparseArray[{{1, 1} -> 0,Reverse@
ImageDimensions[i] -> 0}~Join~((# -> 1) & /@ Position[mc, n])]], 3]],ImageSize -> 
400], {{n, 1, "branch"}, 1, Max[mc], 1, Appearance -> "Labeled"}, FrameMargins -> 0]

enter image description here

Improve this answer
$\endgroup$
5
  • $\begingroup$ thanks! that looks like a similar solution to Silvia's, I guess removing the vertices by dilation is key... As a side note, I'm very new to Mathematica, and amazed at the beautiful pictures/animations that one can do with very little code, thanks for sharing! $\endgroup$
    – gab
    Jul 31, 2012 at 22:16
  • 1
    $\begingroup$ @gab yes solution is similar to Silvia, who also have quite beautiful logic there like {"SkeletonEndPoints", "SkeletonBranchPoints"}. I am glad you find things here appealing - welcome to Mathematica SE! $\endgroup$
    – Vitaliy Kaurov
    Jul 31, 2012 at 22:19
  • 1
    $\begingroup$ I was trying to run the code above and get an error on the line: vi = ... If I've understood the error message properly the problem is that AbsoluteOptions[MorphologicalGraph[i], VertexCoordinates] has only a single component. $\endgroup$
    – JEP
    Dec 1, 2014 at 23:49
  • 1
    $\begingroup$ I get the same error as JEP, not sure if it is a problem with version 10 or not, but it works if you change the [[2]] to a [[1,2]] $\endgroup$
    – Jason B.
    Dec 17, 2015 at 8:28
  • $\begingroup$ As mentioned by above, for version 10+ at least VertexCoordinates seems to return a list, so the code needs modifying in the definition of vi. $\endgroup$
    – SPPearce
    Oct 18, 2018 at 8:32
11
$\begingroup$

In case you want EVERY point on edges, this is my implementation:

img = Binarize[Import["https://i.stack.imgur.com/cET4A.png"] // Thinning];

The pointSetImg stores all vertexes in the image img:

pointSetImg = ImageAdd @@ (MorphologicalTransform[img, #1] & ) /@
     {"SkeletonEndPoints", "SkeletonBranchPoints"};

By subtracting pointSetImg from img, imge with all edges separated is obtained:

edgeSetImg = ImageSubtract[img, Dilation[pointSetImg, DiskMatrix[1]]];

Separate every connected image component:

edgeSeparatedArray = MorphologicalComponents[edgeSetImg];

Now edgeSeparatedArray is a ImageData-like array with each connected component represented by a unique integer:

Tally[Flatten[edgeSeparatedArray]] // Shallow

{{0, 1429814}, {1, 65}, {2, 100}, {3, 6}, {4, 26}, {5, 1}, {6, 65}, {7, 57}, {8, 3}, {9, 27}, <<370>>}

So for example you want the coordinates of points of the sixth edge, you can do this:

Position[edgeSeparatedArray, 6]

{{137, 934}, {138, 934}, {139, 934}, {140, 934}, {141, 934}, {142, 934}, {143, 934}, {144, 934}, {145, 934}, {146, 933}, {147, 933}, {148, 933}, {149, 933}, {150, 933}, {151, 933}, {152, 933}, {153, 932}, {154, 932}, {155, 932}, {156, 932}, {157, 931}, {158, 931}, {159, 931}, {160, 931}, {161, 930}, {162, 930}, {163, 930}, {164, 930}, {165, 929}, {166, 929}, {167, 929}, {168, 929}, {169, 929}, {170, 929}, {171, 929}, {172, 929}, {173, 929}, {174, 929}, {175, 929}, {176, 929}, {177, 929}, {178, 930}, {179, 930}, {180, 930}, {181, 930}, {182, 930}, {183, 930}, {184, 930}, {185, 930}, {186, 930}, {187, 930}, {188, 930}, {189, 931}, {190, 931}, {191, 931}, {192, 931}, {193, 931}, {194, 931}, {195, 930}, {196, 930}, {197, 930}, {198, 930}, {199, 929}, {200, 929}, {201, 929}}

Show all edges in an image:

edgeSeparatedArray // Colorize

Mathematica graphics

Note: There may be some vertexes get too close that the ImageSubtract erasures the edges between them completely. In that case you may want to ImageResize you original image before go through all the above process.

Update:

As OP asks for a function which takes any two vertex as input and output the points on the edge between them (if any), my implementation is following:

  1. Obtain the separated vertexes image and count the number of vertexes:

    pointDilatedSeparatedArray = MorphologicalComponents[pointSetImgDilated];
vertexSetSize = Max[Tally[Flatten[pointDilatedSeparatedArray]][[All, 1]]]

    274

  2. Define function edgeForVertexFunc which takes No. of vertex as input and output the No.s of all edges connecting to the correspond vertex:

    edgeForVertexFunc = Compile[{
   {vertexNum, _Integer},
   {pointDilatedSeparatedArray, _Integer, 2},
   {edgeSeparatedArray, _Integer, 2}},
  Module[{rowm, rowM, colm, colM},
   {{rowm, rowM}, {colm, colM}} = Sort[#][[{1, -1}]] & /@
     (Position[pointDilatedSeparatedArray, vertexNum]\[Transpose]);
   edgeSeparatedArray[[rowm - 1 ;; rowM + 1, colm - 1 ;; colM + 1]] //
      Flatten // Union // Complement[#, {0}] &
   ],
  CompilationTarget -> "C", RuntimeOptions -> "Speed"]

    Then we use it to obtain edges set for each vertex:

    (edgeForVertexSet = edgeForVertexFunc[#,
   pointDilatedSeparatedArray, edgeSeparatedArray
   ] & /@ Range[vertexSetSize])//Shallow

    {{3}, {1, 3, 4}, {5}, {2, 5, 6}, {7}, {8}, {4, 8, 9}, {1, 10, 11}, {2, 12, 13}, {11, 14, 15}, <<264>>}

  3. Define function coordPickFunc for extracting "coordinates" (row- and column-indices) of n in some SeparatedArray:

    coordPickFunc = 
 Compile[{{n, _Integer}, {SeparatedArray, _Integer, 2}}, 
  Position[SeparatedArray, n], CompilationTarget -> "C", 
  RuntimeOptions -> "Speed"]

    Function edgeNumBetweenVertex for finding No. of common edge between vertex i & j, and function edgeCoordBetweenVertex and vertexCoord for extracting coordinates:

    edgeNumBetweenVertex[i_, j_] := 
 Intersection[edgeForVertexSet[[i]], edgeForVertexSet[[j]]]

edgeCoordBetweenVertex[i_, j_] := 
If[# == {}, {}, coordPickFunc[#[[1]], edgeSeparatedArray]] &[edgeNumBetweenVertex[i, j]]

vertexCoord[i_] := Mean[coordPickFunc[i, pointDilatedSeparatedArray]]

Applications

There is no edge between 5-th and 7-th vertexes:

edgeCoordBetweenVertex[5, 7]

{}

The coordinates of 13-rd and 32-nd vertexes are:

vertexCoord /@ {13, 32}

{{403, 1284}, {544, 1135}}

The edge between them goes through points with coordinates as:

edgeCoordBetweenVertex[13, 32]//Shallow

{{405, 1282}, {406, 1281}, {407, 1280}, {408, 1279}, {409, 1278}, {410, 1277}, {411, 1276}, {412, 1275}, {413, 1274}, {414, 1271}, <<146>>}

Show it on graphics:

edgeSetImg // ImageData // ArrayPlot[#, DataReversed -> True,
   Epilog -> {
     Blue, Thick, Line[Reverse /@ edgeCoordBetweenVertex[13, 32]],
     Red, PointSize[.005], Point[Reverse[vertexCoord@#] & /@ {13, 32}]
     }] &

Mathematica graphics

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! That sounds like a great idea, I'll give it a try! $\endgroup$
    – gab
    Jul 31, 2012 at 20:24
  • $\begingroup$ @gab Thank you :) btw I edited the import line just now. $\endgroup$
    – Silvia
    Jul 31, 2012 at 20:26

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.