0
$\begingroup$

I am looking for a way to fit a spline of order 2 to a 2d image or point cloud. The input will be an gray scale image. The start and end points are given as 2D coordinates. The goal is to find a spline that minimizes the energy or average image value that the spline is crossing.

It might be easier to understand with the example image:

Example image. Given are the start and endpoint of the spline.

The blue line is the target. It should approx. through the valley. I hope it is clear what I need...

I already tried to solve the problem with a LiveWire algorithm but that doesn't lead to a smooth and reliable result.

The programming language is python if that is of any importance.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ The question of course is: How do you define "energy"? $\endgroup$
    – Wolfgang Bangerth
    May 7, 2020 at 13:30
  • $\begingroup$ The energy would be defined by the image/pixel values the curve is crossing. Is that understandable? $\endgroup$
    – gtpMurdoc
    May 8, 2020 at 5:07
  • $\begingroup$ No. You have a formula in mind, but we have no idea what that formula is. You need to be more explicit in what you want. It's a bit like telling me -- over the phone, without video, that you want to go "over there but that there is an obstacle in your way". There's really nothing we can help you with if you don't tell us where "over there" is and what "the obstacle" is. $\endgroup$
    – Wolfgang Bangerth
    May 8, 2020 at 12:33

1 Answer 1

Reset to default
0
$\begingroup$

Do you mean you want to fit a polynomial of degree 2 passing through the end points? If so, it’s a 2D optimization problem. Parametrize the curve in some way, say, as a function of a third point on the curve. Evaluate your cost function on a set of points in the image, say a grid of points covering the image or a region of the image around the straight line connecting the points if you want to limit the possible curves. Pick the global minimum and then refine the result using a nonlinear optimizer.

If you meant you want a spline with several nodes along the way, the larger optimization space can result in an intractable problem. If the path can be roughly approximated by a single polynomial, you can start with the method above and then refine it. Find the minimum of the image for points along the curve, and use this point to divide the curve into two segments. Then apply the same method to the two smaller pieces to get a two-piece spline. You can keep subdividing until the cost function converges or the number of subdivisions is more than a preset limit.

To evaluate the energy along the curve, use a bilinear interpolation of the image, evaluated on points along the curve.

Improve this answer
$\endgroup$
3
  • $\begingroup$ You are right. I am more looking for a polynomial than a spline. I like your answer and I will try what you propose. Thank you! $\endgroup$
    – gtpMurdoc
    May 8, 2020 at 7:08
  • $\begingroup$ Just for completeness, this is what I used in the end: I calculated the polynom parameter using the polyfix algorithm in python using the start, end and mid point of the x and y axis. To "optimize" I simply changed the y_mid value for the polyfix calculation iterative and stopped if the average amplitude value on the line was minimal. The average amplitude value was computed using a bilinear interpolation, discretized for every x value. $\endgroup$
    – gtpMurdoc
    May 11, 2020 at 5:58
  • $\begingroup$ I think you mean polynomial, not polygon, and polyfit instead of polyfix. Right? $\endgroup$
    – Amit Hochman
    May 13, 2020 at 9:55

Your Answer

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

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