Recover curves from noisy collection of points

Question

Background: I'm trying to make a system that tracks a number of bubbles in a video

I'm implementing the bubble detection in the single image case using the Circular Hough Transform. Due to occlusion, blur and other factors, this detection will never be 100% accurate. I am tuning the detection procedure for high recall, possibly at the expense of precision.

Once this is done and applied to a sequence of frames from a video, I will have a number of detections that can be characterised as points in 4D space - x-position, y-position, radius and frame index.

Is there a procedure that can recover curves from this 4D point cloud?

Answer 1

As long as the curve is not too curly, one way of doing it is to first use a SVD of the points (centered to mean zero) to get the dominant direction in space. If your centered points are the rows of a matrix $X=USV^T$, and $u$ is the first column of $U$, you can do an error in variables fit to a stochastic model of the form $X_{k:}=p(u_k+\eta)+\epsilon$ using a univariate low degree polynomial.

In the more curly case, solve instead the problem $P(X_{k:},u_k)\approx 0$ with a bivariate polynomial ansatz for $P$, using the smallest singular vector of the matrix of the resulting linear problem $A z=b$ for the coefficients $z$.

If the curve is curled up in a complex way, you'd have to disentangle it first by using a heuristics to extract from the cloud shorter and more well-behaved pieces of the curve.