CODEWITHSUNDEEP
calgorithmmathinterpolation
SetSlapShot
SetSlapShot

Reputation: 1298

Conceptual Interpolation algorithm

G' Morning SO-

I'm trying to move some bounding boxes on a video. I'm at sort of a sticking point . If I've got a frame on a data file every 15 frames, then I have to create 14 frames in between each real one. Since it's a tool (actually part of an ffmpeg plugin), it needs to work for any gap size.

I've written a function that takes the distance between two points, and how many frames it has to smoothly transition from the beginning point to ending point. What this function would ideally return is an array of how many pixels to shift from the preceding frame

For example if x at frame 1 was 50, and at frame 16 was 65, then I would have an array of all ones so that each frame would add one to the frame before. Here's what I've got so far:

int* generateSequence(int difference, int numStep){
  int* sequence = (int*)malloc(sizeof(int*)*numStep);
  int i;
  for(i=0; i<numStep; i++){ 
    sequence[i] = 0;
  }
  while(difference > numStep){
    for(i=0; i<numStep; i++){ 
      sequence[i]++;
    }
    difference -= numStep;
  }

I'm satisfied with this part, (which would add one to EACH frame in between for every multiple of the distance between the two over the number of frames in between).

But now I'm getting to the point where I would need to add one to SOME frames but not all. All I've got is these jury rigged algorithms that aren't very portable for a tool that produces different frame distances...

double delta = difference/numStep;
if(delta >=.05 && delta< .20){
  for(i=0; i<numStep; i+=6){ 
    sequence[i]++;
  }
}

Should I be using a modulus operator or maybe approaching it differently? Hard coding in what seem like arbitrary values doesn't sit too well with me.

Upvotes: 1

Views: 213

Answers (2)

cheeken
cheeken

Reputation: 34655

More generally, it sounds like you want to generate the "smoothest" series of x integers whose sum is y. (Smoothness is minimal average distance between elements in the series.)

This can be achieved with the following algorithm.

given sum and steps
float step = sum/steps
float delta = 0
sequence = []
for x:
    int integerstep = round(step + delta)
    delta += step - integerstep
    sequence.push(round(integerstep))

An example implementation in python (sorry, not a c person) can be found below.

def renderSmoothIntegerSequence(steps, distance):
    step = float(distance)/steps
    delta = 0
    sequence = []
    for _ in xrange(steps):
        integerstep = int(round(step + delta))
        delta += step - integerstep
        sequence.append(integerstep)
    return sequence

Example invocations:

>>> print renderSmoothIntegerSequence(5,8)
[2, 1, 2, 1, 2]
>>> print renderSmoothIntegerSequence(5,7)
[1, 2, 1, 2, 1]
>>> print renderSmoothIntegerSequence(32,1)
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
>>> print renderSmoothIntegerSequence(1,50)
[50]

Upvotes: 1

MusiGenesis
MusiGenesis

Reputation: 75286

In order for this box animation to be smooth, you will need to be able to draw the rectangle on each frame such that the rectangle's coordinates are not quantized by integer. In order words, if your interpolation calculation results in (for example) an X value of 21.354 and a Y value of 50.813, then rounding these values to 21 and 51 respectively will not work; the resulting movement of the rectangle will be very jerky and irregular.

The problem is that frames of a video are pixel-based, which means there's usually no built-in way to draw lines or rectangles with real (aka floating-point, as opposed to integer) coordinates. If the library you're using to draw the rectangle onto each frame only supports integer coordinates and not floating-point coordinates (and you should check this, because many graphics libraries do support floating-point coordinates, which would make this task very easy for you), then you'll have to roll your own for this.

What library are you using to actually draw these rectangles onto each frame of the video?

Upvotes: 1

Related Questions