What Gap Filling Algorithms are used Nexus 2?

There are four gap filling options available in Nexus 2.

Woltring (Quintic spline)

This has slightly different behaviour for the pipeline operation compared to the manual fill.

Both versions generate a quintic spline using valid frames around the gap as seed data. The gap is filled using the interpolated values from the spline. If there are insufficient frames surrounding the gap, the fill is rejected.

Pipeline

Searches backwards and forwards from the gap looking for (Number of Gap Frames / 2) + 5 consecutive valid frames on each side, but will accept a minimum of 5 valid frames on either or both sides if the preferred range is not available. Searches the entire length of the clip looking for the valid frame ranges.

Manual

Searches up to (Number of Gap Frames / 2) + 5 frames backwards and forwards from the gap. Requires a minimum of 10 valid frames in this range - these are not required to be consecutive.

Pattern

Manual fill operation only.

Generates linear interpolations between the valid frames either side of the gap and between the same frames in a donor trajectory. The interpolated value in the gap trajectory is then offset by the difference between the interpolated and true values in the donor trajectory. Mathematically:

Let F(t) be the value in the position of the trajectory to fill at frame t, and D(t) that of the donor trajectory. Let t0 and t1 be the valid frames before and after the gap, respectively. Then if we define the interpolated position V of trajectory Gat frame t as:

V(G(t)) = ( G(t1)-G(t0) ) * ( t - t0 ) / ( t1-t0 ) + G(t0)

then:

F(t) = V(F(t)) - V(D(t)) + D(t)

Rejects the fill if the donor trajectory has any invalid frames within the gap region, or if the donor or fill trajectory are invalid at either t0 or t1

Rigid Body

Takes a number of trajectories and assumes these move as a rigid body. The gaps in the selected trajectory are filled as if this trajectory is also a part of the same body. Manual filling is restricted to 3 donor trajectories and fills gaps in a single trajectory; the pipeline operation will use as many donor trajectories as possible, and will attempt to fill the gaps in each selected trajectory using all the other selected trajectories as donors.

Define the state at frame t as an (n x 3) matrix M(t) whose rows are the position vectors of the donor trajectories, P(t) as the position of the fill trajectory, and tx as a reference frame in which the positions of the donors and fill trajectory are all known.

We transform M into M by subtracting the mean value of the column i from each row entry M(t)(i,j):

M(i,j) = M(i,j) - O(j), where O(j) = ( (i=1->n) ∑ M(i,j) / n )

We then create a covariance matrix C = M(tx)' M(t) and perform an SVD such that C = U S V*

We take L to be the the identity matrix, except that if det( V U* ) < 0, then L(3,3) = -1. Then we can generate a rotation matrix R(tx) = V L U* (This is effectively the Kabsch algorithm to find the optimal rotation between two point clouds)

The interpolated position at frame t based on reference frame tx is then defined as:

G(t, tx) = R(tx) ( P(t) - O(tx) ) + O(t)

and

F(t) = ( G(t, t1) - G(t, t0) ) * ( t - t0 ) / ( t1 - t0 ) + G(t, t0)

where t0 and t1 are the valid frames before and after the gap, respectively.

The fill is rejected if there are fewer than 3 valid donor trajectories at any frame t0 <= t <= t1, or if the trajectory to fill is invalid at t0 or t1.

Kinematic

Determines the fill based on the position and orientation of a segment. The manual operation operates on a single selected trajectory, while the pipeline operation attempts to fill gaps in all trajectories associated with the selected segment.

The mathematics of this operation are simply:

G(t, tx) = R(t) R(tx)' ( P(t) - O(tx) ) + O(t)

and

F(t) = ( G(t, t1) - G(t, t0) ) * ( t - t0 ) / ( t1 - t0 ) + G(t, t0)

where R(t) is the rotation matrix defining the orientation of the segment in the world at frame t, O(t) is the origin position of the segment at frame t, and t0 and t1 are the valid frames before and after the gap, respectively.

The fill is rejected if there are no kinematics for the selected segment at any frame t0 <= t <= t1, or if the trajectory to fill is invalid at t0 or t1.

Still need help?