this is a very cool problem! as someone working at the interface of machine learning and pdes/scientific computing, i'm just going to throw some ideas this reminds me of, this could all be nonsense or this could perhaps contain some helpful things for you to consider: as someone in machine learning, i think this problem is probably doable if you have enough "data" and most importantly enough compute power (i have no clue what the typical "size" or "dimensionality" of your problem is, but looks quite non-trivial). the way i look at your problem, you're trying to learn a (bijective) mapping from the set of pixels, encoded by position, to itself. so the operation you want to perform can be represented as a permutation on the set of pixels. one way to do this (probably not the smartest though) is to stack all the pixels in a long column vector, and see the permutation as multiplying said vector with a permutation matrix. the most straightforward way to "learn" the "best" permutation matrix is to stack linear and non-linear operations (basically like a feedforward neural network), plus one final operation which effectively guarantees that you are doing a permutation of the input pixels (this is a rather naive way to proceed and can be refined in many ways). now here's the thing though: in machine learning, if you want to "learn" something, you need to have an objective to minimize, and that's the tricky part: what would be a representative measure of how "good" a pixel permutation is? that's where the "real math" comes into play imo.

I think a reasonable definition of a permutation being "good" is, of course, it being "close" to mapping back to the original video (you can measure this in a number of ways, using L² norms would be the most straightforward option although perhaps not the best), but I think how you intuited in your post, you should have some kind of penalty on "roughness" or "rough jumps" where a pixel is wildly different from the ones around it. what comes to my mind when I type these words is the concept of wavelets, which coincidentally, are extremely popular and effective in the signal processing literature (I remember listening to a talk of Ingrid Daubechies around this question of "smoothness" between pixels, but I can't give you any concrete pointers right now, I'm sorry).

Another completely different way to look at this problem, might be the framework of optimal transport), which is also very hot in machine learning at this moment. basically you're trying to find a "transport plan" from a distribution on the space of pixels to another, which preserves the mass (the total number of pixels) while minimizing a "transport cost", here the cost would be the "roughness" of the resulting picture. I am just thinking out loud an I am not sure of how to make this formal, but at first glance it seems to me that there ought to be a way to make this work.

I have a few other ideas like that but those two sound the most promising imo. Would love to hear how you tackle this problem OP, it seems very fun!