7
$\begingroup$

MorphologicalGraph can produce a graph from an image. Such graphs should always be planar, but if the pixel structure has a certain unfortunate shape, then MorphologicalGraph will produce something that is not planar in the strict sense, causing trouble down the analysis pipeline (such as identifying faces and finding the dual graph).

Here's an example:

im = Image[{
   {0, 1, 0, 0, 0, 1, 0},
   {0, 0, 1, 0, 0, 1, 0},
   {0, 0, 0, 1, 1, 0, 0},
   {0, 0, 0, 1, 1, 0, 0},
   {0, 0, 1, 0, 0, 1, 0},
   {0, 1, 0, 0, 0, 0, 1}
  } , "Bit"];

enter image description here

This is the graph we get:

MorphologicalGraph[im]

enter image description here

Technically this is a planar graph, through this particular drawing of it is not. However, if we connected the four corner vertices with a cycle, it would no longer be planar. This simple example is just to illustrate the situations that cause non-planarity, or derail face identification.

Question: What practical ways are there to avoid this situation and get a graph without edge crossings from an image?


To illustrate the applications better, I work with images similar to this:

enter image description here

(source)

$\endgroup$
  • $\begingroup$ Would collapsing triangles be an option? $\endgroup$ – Henrik Schumacher Jun 14 '18 at 12:41
  • 1
    $\begingroup$ Is theEdgeWeight option on MorphologicalGraph helpful? If you can get it to use ManhattanDistance instead of just the number of pixels perhaps $\endgroup$ – KraZug Jun 14 '18 at 12:55
  • $\begingroup$ @KraZug Sounds like a good idea. Then I can contract vertices that are very close to each other. That would provide a relatively simple and practical solution. $\endgroup$ – Szabolcs Jun 14 '18 at 13:17
  • 1
    $\begingroup$ @HenrikSchumacher Not triangles, because in general they can be large, but contracting tiny triangles (as KraZug said) might work. $\endgroup$ – Szabolcs Jun 14 '18 at 13:18
  • 1
    $\begingroup$ Do not post such problems. They are evil! They are like "Nah, this is simple... uhh, wait.. hmm, shit.. oh christ.." and then two hours are gone :) $\endgroup$ – halirutan Jun 15 '18 at 16:00
3
$\begingroup$

This is only a start, but I need to write this down, because otherwise it bugs me the whole weekend. The main reason why this happens is two-fold. Firstly, the thinning algorithm is not perfect and in situations like the first example of Szabolcs, the 2x2 box in the middle is kept because with simple morphological operations it is not possible to thin this further without changing the connectivity.

This is the reason that when you try to find the branch-points in this image, you get not a point, but the complete inner 2x2 box

im = Image[{{0, 1, 0, 0, 0, 1, 0}, {0, 0, 1, 0, 0, 1, 0}, {0, 0, 0, 1,
      1, 0, 0}, {0, 0, 0, 1, 1, 0, 0}, {0, 0, 1, 0, 0, 1, 0}, {0, 1, 
     0, 0, 0, 0, 1}}, "Bit"];
MorphologicalTransform[im, "SkeletonBranchPoints", Padding -> 0]

Mathematica graphics

In itself, this is basically (a very cautious basically) not a problem. However, MorpholocialGraph is a bit inconsistent because although the above 2x2 box is one branch-point, it regards this as 4 different branch points.

From the image-processing point of view, this is wrong because it is one morphological component. The reason for this inconsistency can be seen in oMorphologicalGraph that you can reach by opening

<< GeneralUtilities`;
PrintDefinitions[MorphologicalGraph]

and clicking through iMorphologicalGraph (somehow, it's not possible to directly open Image`MorpolocigalOperationsDump`oMorphologicalGraph). There, you find the following

vertices = ImageAdd[
  MorphologicalTransform[skeleton, "SkeletonEndPoints", Padding -> 0],
  MorphologicalTransform[skeleton, "SkeletonBranchPoints", Padding -> 0]
];
vertexComponents = Replace[ImageData @ vertices, 1 :> PreIncrement[vertexCount], {2}];

The last line is in its essence a MorpholocicalComponents call that gives each vertex a unique integer-label. However, since it does not take into account that not each pixel is a separate branch-point, even connected pixel get different id's.

We can fix this by doing this on our own and replacing the last line with

vertexComponents = MorphologicalComponents[vertices];
vertexCount = ComponentMeasurements[vertices, "Count"] // Length;

pressing Shift+Enter applies the patch and we can try it out. First the good news

MorphologicalGraph[im]

Mathematica graphics

and it even works on the real example

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

Here are some places that changed (old -> fixed)

enter image description here enter image description here

enter image description here enter image description here

enter image description here enter image description here

However, there are some disgusting degenerated cases like this one

ImageResize[Import["https://i.stack.imgur.com/Sva6r.png"], {60, 60}, 
   Resampling -> "Nearest"] // Binarize;
MorphologicalGraph[%]

Mathematica graphics

Mathematica graphics

The cycle is ugly, but Szabolcs is surely able to remove it from the graph. When I understood him correctly, then this image should only create one vertex in the center and then, this is definitely an improvement to

Mathematica graphics

My final recommendation is to take the implementation of MorphologicalGraph and work from there. I had suggested in chat to implement the whole procedure manually, but maybe some fixes to the existing code will be enough.

Edit

I found the flaw in the last degenerated example. The branch-point has a hole in it. A better replacement for branch-points in this case is

ImageMultiply[
 FillingTransform[
  MorphologicalTransform[im, "SkeletonBranchPoints", 
   Padding -> 0]], im]

which leads to the center component being

Mathematica graphics

and then the graph will be

Mathematica graphics

$\endgroup$
  • $\begingroup$ So MorphologicalGraph really is implemented in pure Mathematica ... I had no idea. I was so sure it must have been something lower level that I didn't even try to check the source. $\endgroup$ – Szabolcs Jun 15 '18 at 16:15
  • $\begingroup$ The key function is Image`MorphologicalOperationsDump`ConstrainedMComponents, and internally it just uses a kernel function. I guess this is what does the shortest path calculation, but it is not 100% clear to me how to use it. $\endgroup$ – Szabolcs Jun 15 '18 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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