Get the center line from some ordered scatters

Question

I have some ordered scatter points that, according to their index values, can be connected into a closed loop.Now I want to get the center line of this loop. I have tried two algorithms, one based on Voronoi graphs and one based on graphics. For the Voronoi algorithm, I used the algorithm of https://github.com/fitodic/centerline. Here is the resurlt of the Voronoi graphs.

But there are branches at the tip,like this:

Another method is based on graphics, I define the outline as white inside and black outside, like this

I used skimage.morphology to get the skeleton.

skeleton = medial_axis(binary_image).astype(np.uint8) * 255

But from the results, the effect is not as good as the first algorithm.

Is there any good way to extract the midline of this outline?

The definition of a middle arc looks like this

--------------------Renewal------------------

I found a problem similar to mine, but I didn't know how he removed the branches and connected the midpoints. How do I draw a line along the center of the object

And another problem, but his solution seems less precise. python cv2 draw a center curve in a curved object

Answer 1

Very simple idea (based on graphics):

Divide the white region to several sub-regions (along to long direction of the white region), then calculate "center"(center of gravity or some other) position of each sub-regions. Finally, connect these( as a poly-line or spline, etc).

Answer 2

Your question assumes the shape enclosed by your loop is "elongated", which means it has a distinct centerline. If, for example, your shape was an equilateral triangle, then this assumption would not be valid. Its medial-axis (which is what your centerline figure refers to) would have three symmetric branches and not have such a distinct centerline.

Still, under the assumption that your shape does have a distinct centerline, the Voronoi graph should only have small branches extending from it. In this case, one can think of the following pruning procedure based on analyzing the Voronoi graph:

• Identify junction nodes in the graph - nodes with degree > 2.
• Split the graph into junction-free paths - for example by removing the junction nodes.
• The longest path is your centerline.

An alternative possible pruning procedure can be the following "peeling" procedure:

• Identify all leaf nodes in the graph - nodes with degree = 1.
• Remove all leaf nodes and repeat until there are only two leaf nodes left. The remaining graph is a single path on the centerline.

Note, the result of the second procedure can be a little different than the first.

Both procedures can be implemented in python using basic networkx operations such as G.nodes, G.degree and G.remove_nodes

The resulting centerline (under the "elongated assumption") will be a locus of centers of the tangent circles and therefore not touch the loop at its end-points. This is a direct result of the definition of the medial-axis. As @ChristophRackwitz noted in his comment, if you want the centerline to extend to the boundary you will have to extrapolate it yourself. For example, by extending a line in the direction defined at the end-points.

Answer 3

If you're gonna prune the graph resulting from Voronoi, I'd recommend this approach:

• simplify degree-2 nodes (A-B-C => A-C), updating the lengths of such edges
• any nodes with degree >= 3 (forks)? if not, done
• consider all leaf nodes (each having a single incident edge)
• find the leaf node with the shortest edge connecting it
• delete it
• repeat

I assume that nodes with degree 2 don't exist or are continuously simplified because this algorithm needs to know the length of a true edge, i.e. fork-fork or leaf-fork length. If you had strings of nodes connected by unit length edges, that'd make the entire thing needlessly complicated.

I am suggesting this iterative approach because the previous two approaches nuke all available leaf edges in a single iteration. That may remove more than you want. It's all about edge cases. If you're unlucky, your graph is a midline with a little stub going off in the middle. If you nuke that node, you're left with two halves of the trunk. If you just prune the stub, all is well.

This is a greedy algorithm. It doesn't optimize for the longest path (I haven't reasoned through this). You may not want a longest path. You do want to prune the fuzz.

The advantage of this approach is that it doesn't just nuke a junction and shake all the branches off the trunk. It allows you to keep the longest branch.

You should evaluate the results. Those branches may still be weird and need pruning.