# How to ensure that MorphologicalGraph produces a planar graph?

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"];


This is the graph we get:

MorphologicalGraph[im]


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:

(source)

• Would collapsing triangles be an option? – Henrik Schumacher Jun 14 '18 at 12:41
• Is theEdgeWeight option on MorphologicalGraph helpful? If you can get it to use ManhattanDistance instead of just the number of pixels perhaps – SPPearce Jun 14 '18 at 12:55
• @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. – Szabolcs Jun 14 '18 at 13:17
• @HenrikSchumacher Not triangles, because in general they can be large, but contracting tiny triangles (as KraZug said) might work. – Szabolcs Jun 14 '18 at 13:18
• 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 :) – halirutan Jun 15 '18 at 16:00

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"];


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 ImageMorpolocigalOperationsDumpoMorphologicalGraph). There, you find the following

vertices = ImageAdd[
];
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]


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)

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[%]


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

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",

• 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. – Szabolcs Jun 15 '18 at 16:15
• The key function is ImageMorphologicalOperationsDumpConstrainedMComponents`, 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. – Szabolcs Jun 15 '18 at 16:16