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 :)

Improve this question
$\endgroup$
4
  • 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, 2016 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, 2016 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, 2016 at 13:05
  • $\begingroup$ yes, and then I could probably continue with some form of 1). $\endgroup$
    – user1809923
    Jun 15, 2016 at 13:20

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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, 2016 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, 2016 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, 2016 at 8:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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