Motion Compensation and Temporal Up-Sample

[bobsobol]

I have an idea which I think should work, and I can manually achieve with okay results, but which I am not sufficiently skilled or knowlegeable to write.

I don't know if I'm posting in the right place (TBH I have great difficulty navigating forums but they do get things done) :)

The goal. Achieve non-block related motion compensated smooth and or upsample in X,Y and possibly Z via Morphing technology and automation.

Here's how.

Manual:-
Take two consecutive frames from a low resolution, or low frame rate (low temporal resolution) source.
Place them in WinMorph and map similar points, lines and shapes as vectors. Morph three frames of animation (source, interpolated and destination) at the same or higher resolution.

The middle frame looks less jaggie than the start or end frames because it is composed of the two others and blends similar areas according to thier shape, not the relation of pixels with each other.

The result is that you can get higher resolution, and or higher frame rate, by utalising Shapes in multiple frames. Get better results than a single frame resize and cleaner results than with FrameDbl(). (seit Tom Barry trbarry, Thankyou nice work, good effect) You can even render 4 frames and treble the frame rate etc. But in a manual form it's very slow and painstaking affair.

Automation:
AutoTrace or Vectorize the two frames in question with reduction/simplification.
HOW?
Use a method similar to VDub SmartSmoothHQ (seit Klaus Post and Donald Graft, a classic) Debug mode "Visualise Blur" to produce a bitmapped image with strong thin lines in black on a white background where contrast is highest. This is what you vectorise. Available OpenSource code (for anyone willing to take up the challenge) in http://sourceforge.net/projects/potrace or http://autotrace.sourceforge.net/

Use this vectorised data as morphing points. Match similar vectors in each image and remove points which cannot be matched. (this is where I am fuzzyest, should be a similar process to Block based motion estimation/compensation, which I don't truly understand either) ;)

Morph (warp each image half way {for simple frame double} along it's motion path to the other and blend the two warped images {%50 blend for frame double}) available OpenSouces code to pull on at http://freeware.sgi.com/source/xmorph/.

You can see that different percentages of movement and blending will allow for strong Temporal Cleaning application or Frame Rate change without any of the usual nasty side effects. Okay I don't promise no side effects, and some frame rate changes will surely destroy many original frames, which is not good from the point of view of historical archiving.

Dirt and scratches will obviously confuse any filter attempting this, but if non-matches are simply discarded they should only slow the process down, not stop it working. Noise of other forms should be cancled out more effectivly than most temporal softening and I'm sure there is lot's of room for improvement and other applications.

What I'm not so sure of, is "can contemporary systems achieve this in a practicle time scale".

The kind of work I do I wouldn't mind if it took a day or two to process a 5 minuet clip, but it could take more even than that. I don't know. It would need to be tried.

So how about it? Anyone up to the challenge? Or dose this all sound pie in the sky?

[MfA]

Basically you are just replacing block motion compensation with warping mesh motion compensation. The problem with warping meshes is that they can't effectively deal with occlusion.

[bobsobol]

I've heard this word bandied about, but dont really understand it in a video sence. It's all to do with overbite or air pressure to me. Dosn't mean anything in video terms.

I guess it's to do with obscured objects in one image revealed in another. Like culling in vector or 3D rendering dosn't bother rendering obscured parts for speed and possibly memory management.

In any case I don't know how it's done in block based motion compensation, but manually with Vectors I create a vector when the covered area is and where it dissapears behind and get a squashing or stretching of the disappearing part being faded out by the blend, and it really isn't very noticable. (Not as noticable as deblocked block movement to my eye, YMMV) if motion was large enough to warrent it I could use a thin area of alpha transparency to streach on oversampled sources.

I've done this in animating stills but not for frame up-sample as it's never been great enough to warrent it.

I'm willing to bow to the more knowlegeable however.

Perhappse a combination of the two. Motion detection via blocks, create vectors along the corners of moving blocks, and warp from there.

It's the sharp corners of moving blocks which is most displeasing to my eye. Block smoothing helps but produces noticable errors, or bluring. And with vector shapes there are no such sharp corners to smooth.

[foxyshadis]

Well, if you want to start a useful discussion you should probably know what the state of the art in AVS motion compensation is currently. The two threads (and filters) of interest are:

Motion (http://forum.doom9.org/showthread.php?t=101859)
MVTools Truemotion (http://forum.doom9.org/showthread.php?t=102071)

Both of those are based on high-quality mesh-warping. Various ways to deal with occulsions have been bandied about and some partially implemented, but it'll probably take those two having a lot more time on their hands to be able to dig in and create full-proof ones. Just being able to detect occulsions is hard, being able to push an object through them (rather than just one-way matching on each side of the occulsion) is quite difficult.

Both are actually quite fast. Motion in particular can be over 100 fps while still giving amazing quality framerate change.

[Mug Funky]

interestingly enough, i re-visited Twixtor on a friend's computer the other day. it's improved a lot, and for high-motion animation (think of a whip-pan in flash) it really beat the pants off those avisynth methods. last time i used twixtor it couldn't even track a slow-moving vertical bar without motion-blur. i'm not sure what method it uses, but i think it might be phase-corellation plus mesh-warping. of course it's extremely slow...

i've only compared the three for motion-blurring though. not tried temporal upsampling.

[mg262]

bobsobol,

How about convincing us with some pictures ;).

Motion detection via blocks, create vectors along the corners of moving blocks, and warp from there.That what is being used, except that you take vectors from the centre of the blocks, not the corners.

Occlusion seems to be something of a code word... as well as one object actually covering another, it tends to happen at the edges of objects, where one block lies over two objects... and this last obviously causes problems. If we identified edges on a pixel-perfect level, it would be less of an issue. (And I would guess that with HDTV it's less problematic... though that has its own problems.)

I do have more to say, but I would rather say it after you try to flesh out the process, i.e. generate some pictures (if only for two frames).

but it'll probably take those two having a lot more time on their hands to be able to dig in and create fool-proof onesWell, it's more than that... I threw Motion together because I was in a mood to code, it was fast, and it had been asked for by people who had been kind + helpful to me in the past. It was good fun... but it took me well outside the area of video I have any intuition for (old animation). It's near the limit of the techniques I've seen described on the Internet... so it really needs understanding and intuition to progress, and they're unlikely to come from me.

That's why I tried particularly hard to expose the occlusion-handling mechanism in script; it lets anyone take the thing apart and pinpoint the weak spots to improve things. If the script is opaque I'll explain it better; if you all want more diagnostic tools you will have them; similarly for building blocks (e.g. more masks)...

(I do have a few things I want to implement... e.g. something that will improve behaviour on zooms, maybe a MotionDeint/MotionBob, maybe something that will keep the picture sharper. But none of it is groundbreaking. Lots of stuff is ruled out because I'd like to keep Motion fast.)

Mug Funky:

when you have a moment, it would be interesting to know whether Depan can track your fast pans... if it can, then phase correlation added to one of these things would probably work (and vice versa). Although phase correlation is much too slow for Motion... when I last tried it with the full frame using Depan+FFTW, it ran at 3-4 FPS (and the subpixel accuracy was pretty awful, but that's another story...).

[bobsobol]

Okay. @mg262 I'm gonna have a look at some of my real world low frame rate material, will try to post my hand temporal upsample and try the links provided by foxyshadis (TYVM the first I had read through, didn't understand a lot of it, but could see similarities and differences to what I was doing manually)

Then we can all compare results. The implementation is beyond me as I say. I don't know enough to design or code a filter, but I have "Done" it by hand, and liked what I got.

As I say I don't get on well with Forums, but other ppl seem to like them, and it seems to fire off interesting debates, so I perservere. (Anyone know a good VDub/AVISynth etc Wiki? Especially if it describes the problem of "occlusion" ;) j/k). Thanks mg262 for your description on that word too. So I'm getting that it is more vague than overlapping or obscured objects, and more generally to do with "where edges meet and collide".

Still having blur in those areas alone sounds way better than just bluring whole frames together.

Off topic noob question: Technically, are there any descriptions of how to post Video/Pictures in this forum? or is it just host it somewhere and quote the URL?

[communist]

Off topic noob question: Technically, are there any descriptions of how to post Video/Pictures in this forum? or is it just host it somewhere and quote the URL?
If you dont have any webspace to host have a look the sticky:
http://forum.doom9.org/showthread.php?t=96362

[bobsobol]

Okay, having trouble finding newer version of MVTools than 0.9.9, But documentation for 1.1 seems exciting. Stuff happening IRL here but got together a 5 frame segment of a clip I am working on at just over 8fps which I want to restore to it's original 50fps. (Classic BBC Sci-Fi, now junked but... Someone pointed a handy cam at the TV set and caught clips of it! :) )

http://rapidshare.de/files/11404183/LowFRate.avi.html
http://rapidshare.de/files/11404338/HiFRate.avi.html

My estimation of what "occlusion" is and how my manual method deals with it can best be seen between frames 18 and 23 in the HiFRate file. This is acceptable to me. ;)

[krieger2005]

For MVTools look at the Post of Didée here (http://forum.doom9.org/showthread.php?p=766736#post766736)

[bobsobol]

@krieger2005 Thanx.
Here is the same clip upsampled with MVFlowFPS2.

http://rapidshare.de/files/11444436/HiFRateFlow2.avi.html

I'm impressed, I must say. I think it's done a better job on the background than I did, but then the human eye is drawn to detail in faces.

It was completely confused by the motion between frames 12 and 18, Polly is moving her head rather quickly there, on the other hand the occlusion I noticed in my version between 18 and 24 is handled beautifully.

I conceed that I am out of date. I can't see the block edges I was smoothing out with other and earlier filters here. But maybe my attempts have given ideas on how to improve. The forums seem to sugest that progress on this has stalled.

FE How would it work if, instead of moving individual blocks along their own vector, you grouped blocks with similar motion vectors to a 2D vector shape and moved that along the motion vector? Is it possible to include a "Bad vector" frame file that you could add custom hand tweaked movement vectors where you know it's going to guess motion wrong? Something like the FrameTweaker in VirtualDub (Creds Chris LaRosa) perhappse.

I notice many people are uping the frame rate of Anime (neat idea) which is very clean, where old film suffers Temporal and offten Spacial lumanence flicker which seems to confuse the motion estimation when severe enough.

My clip already has global lumanence, flicker fixed, but of course the camera has caught scan lines at different places. The reverse process (pointing a video camera at a film projector) catches the shutter at different points producing (offten) a throbbing luminence blob in the middle of the screen, which MV see as movement. The same thing happens in scenes lit by fire or a candel, only that is completely unpredictable.

I can imagine strobing like the first Alien movie would drive it crackers, but just being able to tweak the change points would make a world of difference.

For now I'm likely to switch main processing to this, and tweak it's bad points (12 to 18) with my old method.

[Didée]

I can imagine strobing like the first Alien movie would drive it crackers, but just being able to tweak the change points would make a world of difference.
Make a combined motion search including search on a highpass-filtered clip. Small radius highpass'ing kicks out almost all luminance flicker.

[mg262]

bobsobol,

I'd be curious to see what you thought of the Motion equivalent... it's pretty easy to use; you put the latest Motion DLL and MotionProtectedFPS.avsi script in your plug-ins directory, and then use the command

MotionProtectedFPS(25)

[bobsobol]

@ Didée Thanx for that, it sounds like it could work, though I don't really understand how to implement from that description. (Prolly my lack of understanding rather than your description) I'm still trying to get my head around what all the parameters are and how they work, just needs more spare time.

I also had a thought that if you did a complete contrast and gamma match on both frames in the detection of motion vectors stage, and worked on the original for output. This might effectively be the same thing. I've only ever highpassed Sound... oh and vollyball ;)... so what it would do on Video I have no idea. I'd guess it'd take out mosquito noise in bright areas of the image, but that dosn't sound right somehow.

@ mg262 You're picking this up from a different thread? If you link it I'll be glad to have a look see.

[mg262]

Here: http://forum.doom9.org/showthread.php?p=750037#post750037

[bobsobol]

Cool. Looking. :)

Okay I see what you are getting at now. Had been trying to use the Motion Script function with MVtools.

Looks cool. I imagine the script function is de-jargoning the fileter, but the syntax seems far more user-friendly.

I was using MVtools before this descussion for MCT smooth, and alread had the impression it could use more modularisation than a single DLL. I'm sure the overhead isn't great, but maybe a core library and sub libs for similar command sets, they could encur performance penalties for little memory save tho, and most of us could use a little memory to increase performance. ;) MV tools Documentation is getting unwieldy tho. I realise that it's beta, but a doc clean is going to help testing some.

GZ on your documentation too mg262. Clean, prescise and cross referanced beautifully. A little gramma checking and some screenies (always nice to see what the result "should" be when you get the params right) and the docs a release quality. Hope the code is as close.

Have a long test encode eating CPU tonight. Will script up and post in the next day or so. :) (oh and remember to change my underpants... I'm so excited!)

(apes Kirl "Set a heading for Galifrey Mr. Solou, warp factor 50fps." ;) )

[bobsobol]

Okie dokie here's the results:-
I scripted a combined bi-directional motion compensation. And stuct to my target of 50fps for fairness. (100 was worse but I don't need 100 and have very low frame rate source so it's probably asking too much anyway.)

Motion Move - http://rapidshare.de/files/11836691/HiFRateMotionMove.avi.html

This showed up the blockieness I was winging about earlier. You can clean this up with Donald Grafts Blind Deblock or so, but thier promenence suggests to me that you are loosing something, and here it's Bens sholder. ;) So I tried the other two methods.

Motion Warp - http://rapidshare.de/files/11836864/HiFRateMotionWarp.avi.html

This is better aesthetically, but in many ways not that different from frame blending. There is a lot "wrong" with the motion it's determined here. Pollys nose in that head turn also goes out completely, but aesthetically the blended frames look better than pulling the nose off her face that MVTools did. Generally dosn't look as crisp as MVtools though.

Warpfast was somewhere in between. The blocky sections looked like blocks with rounded corners.

There is another section of this clip I'd like to share with you here that I haven't posted before, as it makes a point that wasn't necessary with MVtools and I haven't got to manually yet.

http://rapidshare.de/files/11837255/HiFRateMotionWarpL8R.avi.html

Here Polly moves here head in accross the screen, and Motion seems to be confused as to which of her oh so fab 8) 60's highlights is which?

I'm guessing there could be some logic in there to say this motion is surrounded by other motion which should alter the weighting of which image match should come out tops in the "avoid the maximum number of inprobables" stuff.

Never was much good at programming AI, I prefere hard and fast rules, but image recognition isn't that kind of game. Hence why I don't want to attempt this myself.

Anyway, MVtools didn't do that, and obviously I wouldn't cuz am smarter than the average CPU... Unless it's playing chess with me. ;)

It is possible that some change in contrast destinctions could also fix it. There is the horrozontal scan-line liminence bars going over it too.

Also notice that there are 30 frames in MVTools output and 34 in Motions. 30 I thought was about right when I did the math for that, haven't re-done it and my heads not in the right gear to attempt. ???:( Frames 31 to 34 of Motions output seems to be identical, though I haven't done a compare to show up differences. Is this to do with the Bi-direction, and should it not clip the extra frames from output even if it dose need them internally?

What do you think to the dot-to-dot idea for similar motion blocks mg262? Could turn block edges into straight lines?

Also is there a way of reducing the block size other than resize up, motion, resize back down? BTW all these clips are reduced from 768x576 PAL 1:1 PAR to 512x352 for small size with no artifacts (aside from bigger pixels and smaller motion blocks)

Keep up the good work. As I say, very easy to implement in a script, and promising results, but the weighting seems to be off for now, and... Blocks.... <shudder> ewww. ;) I'll keep checking back on these two. Hope I've given some food for thought.

[mg262]

Proper reply later... but try increasing the iterate parameter in the MotionProtectedFPS call, like this:

MotionProtectedFPS(target_framerate, iterate = 6)

and see if it helps the tracking...

[neuron2]

You can clean this up with Donald Graft's Blind Deblock. I'm pretty sure 'marcfd' made the BlindPP() filter.

[mg262]

What do you think to the dot-to-dot idea for similar motion blocks mg262? Could turn block edges into straight lines?I'm sorry, I'm not sure what idea you are referring to here... could you quote the relevant bit of discussion?

The move mode is mainly for extreme speed... there isn't much other reason to use it.

Edit: blocksize is very deliberately fixed at 8 x 8. The algorithms I'm using wouldn't cope well with other block sizes and I chose not to provide options that are inferior in 99% of cases. I would try motion compensating the original without resizing and see if the results are better. (If you aren't trying to use this for real-time playback, keep with a high value for iterate.)

[bobsobol]

@neuron2 Did he. My bad then, thanks for putting that straight. I just remember the one I used comes from DGDecode. ;)

@mg262 Quote: "I would try motion compensating the original without resizing and see if the results are better."

Actually I only resized down after to keep the Huffy small.

I could do with making a picture to illustrate my idea here. Err, I'll see if I can get one together, but....

Basically if you gave a number (index) to each direction and distance, roughly, and drew a line around all the blocks with similar (same) index passing through the center point of each one. Then warp the blob shape you have created in this fascion, rather than individual blocks.

Tried the
"MotionProtectedFPS(target_framerate, iterate = 6)" thing as a replacement for MotionFPS() but I'm getting an error "Script error: there is no function named "fitty2uv"" right now. The docs don't list MotionProtectedFPS() so I guess it's in the avsi. Haven't checked.

It dosn't seem to take the "method" parameter either.

I'm using "source.MotionProtectedFPS(50, iterate = 6)" and hoping I can do the "source=previous" after that.

Is that right or have I read you wrong? (Wouldn't suprise me, I'm sure these pills the Doc gave me are "Blond" pills;) )

[mg262]

Sorry, you will also need the older version of MaskTools (version 1 .5):

http://manao4.free.fr/MaskTools.htm

MotionProtectedFPS is the only one meant for direct use... MotionFPS is something for scripters to play with. So please use MotionProtectedFPS for evaluation.

If a group of touching blocks have the same motion vector, that really is the correct motion vector to use for the material in the interior of the group; anything else will be wrong in 99% of cases. Its where blocks with different motion vectors touch that the issues arise.

[bobsobol]

http://img58.imageshack.us/img58/5237/smoothedblockoutline7lw.jpg (http://imageshack.us)

Right, if the above link works you should see that I have shown two balls. Motion detection has identified blocks moving in a similar direction (the squares overlayed on the balls) the blue ball is just that, just for illustration of the blocky outline. The red ball has had it's outer limits identified, and a line drawn around the center of each of the blocks in that outer limit. The line is then NOT as blocky as blocks alone and if that outline were warped instead of the blocks the image may not "seem" as bad. (this is my way of thinking)

This may not be as "nice" as I think, and it's definatly not very scientific, but the human mind and it's enterpretation of what our eyes see, is far more creative than scientific, and the most accurate method of doing something is frequently not the most pleasing to the eye. (see resizing algorythems fe)

There is also room for play in this theory. My outline from the center of the blocks crops of bits of the ball, perhappse this is very bad, and identifying the "outer" edge of the blocks would be better, or perhappse splines would work better than regular lines. All of which is going to take progressivly more and more from the CPU and deter from performance, so at the very least (that is even if an improvement can be seen with this method) a balance will need to be found, and I accept all of this, and shoot me down if you like... I'm only trying to add ideas which occur to me as "worth trying". ;)

For real quality we would not be working with blocks or 8x8 or 16x16, but quater pels. That I'm sure is way out of current processor capabilities in a "reasonable" timescale, but alternatively, once the "outer limits" of a moving object have been identified in terms of blocks, perhappse one could break the block down into smaller blocks (or even pixels) and perform more rigerous motion detection on them. <<--- WARNING! Thinking about it, it's usually wizzard ideas like this that break my code projects and require me to go back to a backup. ;)

Right I'll go grab that version of MaskTools now. :)

Take care.

[MfA]

Hmm, rather than segmenting each block through fixed grid points I think it would be better to just segment each block at the pixel level ... it's not that much work with only 2 segments per block ... well at least for non warping motion compensation. When you throw mesh warping into the mix things get hard.

[mg262]

bobsobol, MfA,

I have seen something heading towards what you describe in a paper, though it breaks blocks into smaller blocks rather than trying to work down to the pixel level. (You can probably find something on it by searching for the word 'split' in the Motion thread.) The situation is more complex than the pictures because you can have four touching blocks all with different motion vectors, and drawing your boundary line suddenly becomes much less straightforward...

8x8 blocks are used because smaller blocks become far too susceptible to noise. Certainly comparing pixels or 2x2 blocks is completely useless. On the other hand, you can use overlapping blocks... but IMO this is relatively ineffectual for its cost.

As far as detecting occlusion and finding object boundaries goes, there is something out there called object-based motion compensation which identifies the different objects in a picture and therefore finds precisely the areas with discontinuities (as opposed to normal stretching of objects). See pages 12 and 13 of this (http://www.google.com/url?sa=t&ct=res&cd=5&url=http%3A//www.icce.org/authors_page/slides.pdf&ei=7EbdQ7CzPIKERaydiNYD&sig2=IkkDdSN33WaSC0HXxf08rw). Given something like that, one can definitely try and refine the boundaries before warping. I would say that the next generation of motion compensators (in terms of quality) will almost certainly need to use a mix of phase-correlation based methods and said OBMC. (NB I have no plans to build one... Motion was fun, but animation is my area of interest.)

[foxyshadis]

Isn't that essentially how AVC works? Start with a 16x16 block, break it down to 16x8, 8x16, 8x8, 8x4, 4x8, 4x4 blocks looking for the largest block sizes with coherent motion? That way you get fine-grained control without losing the size/coherency benefits of larger blocks.

[MfA]

I have seen something heading towards what you describe in a paper, though it breaks blocks into smaller blocks rather than trying to work down to the pixel level.I did not suggest working down to the pixel level as far as ME is concerned, I suggested segmenting each block down to the pixel level ... but you'd still only have a limited number of segments with a large number of pixels (most of the time, if one of the segments turned out too small you could choose to assign it's pixels to the closest neighbouring block instead). 2 segments is likely good enough, sure you could have 4 moving objects in a single block ... but covering the most common case is a good start.

[mg262]

foxyshadis,
sounds right... though of course AVC only needs block resemblance, not true motion.

MfA,
sorry, my mistake... but given the available input data (motion vector for each block), how would you go about the segmentation?

[MfA]

Don't segment based on motion, segment based on image content.

[mg262]

That's fine as a rough description, but I think it becomes a very tricky problem once you get down to specifics. Even identifying foreground objects in animated material is a hard problem, and IMO this is much messier. (Related note: there are many edge/feature detection algorithms out there in the literature, but you very rarely see them being used with motion compensation... and I think the reason is that while they can be made to look decent for a couple of screenshots, they just aren't robust enough for real use.)

[MfA]

Even when you get the boundaries completely wrong the magnitude of the error is unlikely to exceed that of plain block motion compensation. You are doing ME/MC on areas roughly the same number of pixels as blocks, just more excentrically shaped. It can go right, but not terribly wrong.

[mg262]

I will definitely agree that it will beat move-the-blocks type methods. But, especially since having seen Didée use warping methods for denoising, I think the only reason left to use move-based methods is for extreme speed. So I think the appropriate comparison is with warping.

A point I didn't make very well above is that currently there is no distinction between cases where neighbouring motion vectors differ and warping is appropriate (e.g. zooms) and where it isn't (object boundaries). Applying segmentation to zooms, etc. will result in something that is much worse than warping (just as simply moving blocks does).

Any sort of segmentation will also be much slower than simple warping (which can be made to run rather fast with a little linear maths). So I don't think segmentation can be usefully applied until we can distinguish object boundaries really well... which is one of the strengths of OBMC. Once we have that, it definitely makes sense to refine the boundaries to pixel level or so. But (IMO) not until then.

[Didée]

But, especially since having seen Didée use warping methods for denoising, ...
"especially since", huhuuh ... :o

FYI, after having played with both methods extensively, in the context of denoising I'm now back to plain block-moving MC, for various reasons too intricated and OT to explain here.*)
Framerate conversions are quite a different ballgame, and there I surely expect some advanced warping methods to achieve superior results. But for denoising, I can definetly achieve better results with block-moving than with [the current] warping methods.


... I think the only reason left to use move-based methods is for extreme speed.

Yeah ... "extreme" speed is what I'm planning. Be sure of that. /*rofl*/ :D


*)
Parts of the puzzle are that
a) the big enemy "blocking" OTOH is also helpful in identifying bad compensations, and
b) block-moving results in distorted areas with well defined shape and size, where warping results in distorted areas with irregular shapes, and tends to render much bigger areas of a frame unusable than block-moving does.

[foxyshadis]

[OT] Didée, someday Intel's going to honor your contributions by naming a whole processor line after you. xD