Algorithm to detect curved lines from list of 2D points

Question

I am trying to extract horizontal lines from a set of 2D points generated from the photo of the model of a human torso:

The points "mostly" form horizontal(ish) lines in a more or less regular way, but with possible gaps/missing-points:

There can be regions where the lines deform a bit:

And regions with background noise:

Of course I would need to tune things so I exclude those parts with defects. What I am looking for with this question is a suggested algorithm to find lines where they are well-behaved, filling eventual gaps and avoiding eventual noise, and also terminating the lines properly upon some discontinuity condition.

I believe there could be some optimizing or voting "flood fill" variant that would score line candidates and yield only well-formed lines, but I am not experienced with this and cannot figure anything by myself.

This dataset is in a gist here, and it is important to note that X coordinates are integers, so points are aligned vertically. The Y coordinates though are decimal numbers.

Answer 1

These are integral curves to the vector field representing the direction pattern.

So maybe start by finding for each point the slope vector, the predominant direction, by taking points from the neighborhood and fitting a line with LS or performing a PCA. Increasing the neighborhood radius should allow to deal with the data irregularities thereby picking up a greater-scale slope trend instead of a local noise.

If you decide to do this, could you post here the slope field you find, so instead of points could we see some tangents?

Answer 2

I would start by finding the nearest neighbor of every dot, then the second nearest neighbor on the other side (I mean only considering the dots in the half plane opposite to the first neighbor).

If the distance to the second neighbor exceeds twice the distance to the first, ignore it.

Just doing that, I bet that you will reconstruct a great deal of the curves, with gaps left unfilled.

By estimating the local curvature along the curve (f.i. by computing the circumscribed circle of three dots, taking every other dot, you can discard noisy portions.

Then to fill the gaps, you can detect the curve endpoints and look for the nearest endpoint in an angle around the extrapolated direction.

First step in the processing: