# How to convert an image to a graph and get the positions of the edges?

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

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???

-
Is this helpful: How to convert a 2D image into a 3D graphics? ? – Yves Klett Jul 31 '12 at 19:29
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? – Silvia Jul 31 '12 at 19:39
do you want the lists of pixel coords for each edge to be grouped together? – acl Jul 31 '12 at 19:44
There is some code here to convert an image of a maze into a graph with edges and all. – Daniel Lichtblau Jul 31 '12 at 20:03
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. – Vitaliy Kaurov Jul 31 '12 at 20:28

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

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

AbsoluteOptions[g, VertexCoordinates]


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

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


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]


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]


-
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! – gab Jul 31 '12 at 22:16
@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! – Vitaliy Kaurov Jul 31 '12 at 22:19
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. – JEP Dec 1 '14 at 23:49
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]] – Jason B Dec 17 '15 at 8:28

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

img = Binarize[Import["http://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


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}]
}] &


-
Thanks! That sounds like a great idea, I'll give it a try! – gab Jul 31 '12 at 20:24
@gab Thank you :) btw I edited the import line just now. – Silvia Jul 31 '12 at 20:26