3
$\begingroup$

I am looking for an algorithm to fit a chain of lines to a set of points/pixels. I am pretty sure that there is a suitable algorithm but I can't think of the correct search words to find it.

Here is an image to illustrate what I want: enter image description here

The figure shows a chain consisting of 3 individual lines. The lines are always connected, but their connecting points can be moved. The goal is to fit the connecting points such that the resulting lines are in a sense optimal with respect to the points/pixels (here in black with blue border), for example minimzing some distance. It would be nice if one could adapt this optimality criterion, e.g., such that the lines might snap to the point cloud coming from below the point cloud.

In my current problem I could also give some side conditions for the connecting (yellow) points, such as: point 1 has to be somewhere between x and y on the horizontal axis. Also, I could give conditions on the angles between the lines.

It would be awesome if someone could point me in the right direction and tell me actually what I am looking for :)

$\endgroup$
  • 1
    $\begingroup$ It's not clear enough to me what you want to achieve. Should all points lie on one side of the line? $\endgroup$ – adrianN Jun 15 '16 at 11:43
  • $\begingroup$ @adrianN: I realize, my description is not 100% clear in that aspect. Actually I would be interested in two things: 1) a solution minizming some distance criterion, 2) a snapping from below the point cloud (which would mean that "all" points lie above the lines). I am not quite sure what the better solution would be for me. Do both things result in very different algorithms? $\endgroup$ – user1809923 Jun 15 '16 at 11:47
  • $\begingroup$ If you want all points to be on one side of the line you could start with a triangulation of the point cloud, or a convex hull to find the "outer" points. $\endgroup$ – adrianN Jun 15 '16 at 13:05
  • $\begingroup$ yes, and then I could probably continue with some form of 1). $\endgroup$ – user1809923 Jun 15 '16 at 13:20
1
$\begingroup$

Yes. This is eminently doable. Here's the general recipe:

  1. Define an "loss function" $L$. The loss function takes as input the location of the connecting points, and it outputs a measure of how good/bad this set of connecting points is. Smaller is better. You mention "minimizing some distance"; this is where you put that, but you'll need to decide on a specific loss function you want to minimize. If there are four connecting points, the loss function will take the form $L((x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4))$ and will output a single real number. Choose a function that is continuous and differentiable.

  2. Use gradient descent to find a location for the connecting points that minimizes the loss function. Pick some reasonable initialization value (e.g., where the user initially drew the lines; or use some heuristic to pick a crude guess at where to put the connecting points), and then use gradient descent to improve this initial choice and find a minimum for $L$.

This should be very efficient. It's also very flexible: if you decide you want a different criterion for what the line should look like, you achieve that by modifying the loss function. There are standard libraries for gradient descent, or if you prefer, you can implement it yourself without too much difficulty.

$\endgroup$
  • $\begingroup$ Thanks, I like the idea! When using gradient descent however, it is not clear how to incorporate any side conditions (e.g. the angle between line 1 and line 2 must be smaller than X). Maybe another optimization algorithm is better suited? $\endgroup$ – user1809923 Jun 16 '16 at 6:30
  • $\begingroup$ @user1809923, one approach is to add a large penalty if the angle gets larger than X. (There are also other approaches, such as projected gradient descent: en.wikipedia.org/wiki/Gradient_descent#Extensions, en.wikipedia.org/wiki/…, stats.ox.ac.uk/~lienart/blog_opti_pgd.html, etc.) $\endgroup$ – D.W. Jun 16 '16 at 6:56
  • $\begingroup$ Thanks, I will give it a try as you suggest. After some research this problem also very much reminds me of B-splines or fitting of polylines. But I can't find tutorials that I could apply here (at least without too much effort for me). $\endgroup$ – user1809923 Jun 17 '16 at 8:45

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.