Preface: Out of all the Stack Exchange networks with which I am familiar, this seems the most appropriate for the following question. Please let me know if there's a more suitable network for similar questions in the future.
Question: What are some reasonable resources (e.g. computer-vision libraries) to which I should refer for optimally parameterizing uncommon curves (e.g. a more obfuscated version of this squiggly line) that I extract from a photo I take with a smartphone.
I suspect that the solution to my problem is rather difficult based on Travis' answer on What is parameterization?:
Many common shapes (lines, circles, other conic sections, planes, spheres, etc.) have well-known parameterizations, and graphs of functions from $\mathbb{R}^m$ to $\mathbb{R}^n$ have canonical parameterizations that are easy to write down, but like you say, for sufficiently complicated shapes parameterization can be a very difficult problem.
Thanks in advance for your help!
Best Answer
I'll assume you want to obtain a curve that fits to some 2D curve in an image. In other words, you have arbitrary noisy samples from the true curve and/or points nearby it (e.g., the curve may have some kind of thickness). It would be very helpful if you knew the ordering of your points in advance (not just a set of pixel positions).
If you know the ordering of the points, you should use spline interpolation. Notice that such a parameterization is adaptive to the number of points. In this case, you are done and don't need to read further :)
If you simply have a set of pixel positions, you now have an optimization problem on your hands. This is more likely in most real computer vision applications. The challenge is to fit some kind of parameterized model of a curve through a set of 2D points on the image. There are myriad ways to do this. For example, one could try to impose an ordering on the curve by starting at a point one believes to be an endpoint, and "growing" the curve out by nearest neighbour search, thus imposing an ordering and allowing one to use spline interpolation.
Alternatively, my suggestion is to use a parameterization in terms of "control points", the number of which you specify in advance. Two very popular models like this, used in both computer vision and computer graphics (for fitting to images and generation, respectively), are Bezier curves and Catmull-Rom splines. The idea is then to figure out the positions of the control points. More trivially of course, one can simply choose to have the curve be composed by straight line segments between the control points (i.e. a linear spline).
I think one approach is do something as in active contour models, also called "snakes". Let the control point positions be $P=(c_1,\ldots,c_n)$ for $c_i\in\mathbb{R}^2$. The curve is then some function $C:\mathbb{R}\rightarrow\mathbb{R}^2$, with $C(t)$ being some position on the curve and $t\in[0,1]$, say (e.g., $C(0)=c_1$ and $C(1)=c_n$). Note that using a cubic spline is generally preferrable since it prevents jarring changes in curvature (i.e., it looks nice to the human eye :) ). Let $Q = (q_1,\ldots,q_m)$ be the known point positions.
We want to choose $P$ such that we get (1) a curve that fits $Q$ and (2) is a "nice" curve. Without (2), our curve could run wild all over the image but as long as it hits the points in $Q$, it will have a good score according to (1), which of course is undesirable.
The classical way to handle (2) is to penalize the length and curvature of $C$: $$ \mathcal{E}_I[C] = \gamma\int_0^1 |C'(t)|^2 dt + \eta \int_0^1 |C''(t)|^2 dt $$ where I note that if you are not parameterizing by arclength you will have to use the equations here for curvature, while for (1) we can for example do something like $$ \mathcal{E}_E[C] = \alpha \sum_{q\in Q} \min_{t\in[0,1]} || C(t) - q ||_2^2 $$ meaning that for each point in $Q$, the closest point on $C$ to it should not be far away. Thus, our optimization problem is just to find $$ P^* = \arg\min_{P} \mathcal{E}_E[C] + \mathcal{E}_I[C] $$ which can be done by gradient descent for example.
There are a ludicrous number of papers utilizing such techniques, but an old computer vision classic is Snakes: Active Contour Models by Kass et al.
As for software or libraries, I don't know of any, sorry. However, there are many implementations of active contours on Github you could learn from. For optimization you could use any automatic differentiation framework, for example (or any optimization algorithm/framework, e.g., say evolutionary ones, really).
A few related links: [1], [2], [3], [4], [5], [6].