"Advanced" framerate doubler

[athos]

I have an idea that is inspired by modern 100hz TVs. My TV for example, displays 100 frames per second, as opposed to the regular 50 with the PAL system. It accomplishes this by simply displaying every frame twice. This reduces flicker.

Now, nothing would be gained by implementing this for a computer media player, since the flicker is determined by the number of times the screen is refreshed, and not by the framerate of the movie being played. One frame in the movie might be displayed two or three times because the screen is being refreshed.

Since the frame is being digitized by the TV in order to display it twice (as opposed to just displaying what comes in from the input source), it can perform some processing on it. What it does it that it computes the extra frames to put in between the regular frames, which has the effect of making motion seem smoother. If you havent seen it, go in to a TV store and compare 100hz TVs (I dont know about the situation with NTSC) with this feature enabled, to regular 50hz TVs. Not only will they have less flicker, but also more "life-like" motion.

I might be wrong in some details, but the general idea is to produce in-between frames to double the framerate. On simple implementation would be to just interpolate two regular frames to form an in-between frame. This does not have to cost much cpu-power I think. Smart developers can probably think of much more advanced algorithms, for example by using the motion vectors from the video stream.

I'm not sure if this can be implemented in the DirectShow filter, because I think that you expect one frame out for every frame in? It should, however, be pretty easy to implement in a player.

What do you guys think? I have done tried to search for this in the forums and found nothing on the subject. I have only found things that are related to deinterlacing, but I'm thinking of something that should be performed on progressive video during playback.

[milan]

It is possible to double framerate in directshow filter: ffdshow can do that. Just give me some good ideas (or source code) how to interpolate in-between frames and I will implement it to ffdshow (when I will have more time to work on it :( ).

[athos]

I was thinking something like this:
Lets say every frame is a two-dimensional array of integers, representing the color of each pixel. I want to compute the integers for in-between frame B, given frames A and C.
For each pixel B[x][y] = (A[x][y] + C[x][y]) / 2;
This would give each pixel in B the average color of the corresponding pixels in A and C.

[milan]

Yes, this would be very fast and with integer SSE instructions even faster, but what about scene changes? Some form of detection (which should be fast too) would be needed. I had this in mind when I was asking for good interpolation algoritm ideas.

[trbarry]

As an experiment I added an In-Between Frames option in the DScaler Greedy (High Motion) deinterlace plug-in.

It doesn't double but for 3:2 telecined movies it will do what you say for every 5'th frame, blending 2 adjacent frames together. So intead of seeing frames A,A,A,B,B ... when watching a move it will come out A,A,A+B,B,B ... which is much closer to a regular sequence.

I was somewhat disappointed with the results. Things looked smooth and okay on still or very slow motion and they also looked fine on very fast motion. But there is middle range of motion where the ghosting was fairly obvious.

If I were to do it again or try to improve it I'd probably try to suppress the blending in these middle cases and just choose one of the frames and put up with the judder. But it's very hard to do that when different parts of the screen move at different speeds. And you can't easily choose to blend some blocks and not others.

- Tom

[athos]

Ok, assuming that we can decide wether a frame is an I-frame, just copy A to B in case C is an I-frame.

Also, I think the ghosting will be less noticably if you really double the frame rate.

[OUTPinged_]

It doesn't double but for 3:2 telecined movies it will do what you say for every 5'th frame, blending 2 adjacent frames together. So intead of seeing frames A,A,A,B,B ... when watching a move it will come out A,A,A+B,B,B ... which is much closer to a regular sequence.



There was a plugin for photoshop that could morph one picture into another. It produced great pannings when i just moved target picture several pixels to the left. I wonder if there can be a filter like that implemented that will rebuild missing frames.

[-h]

Inserting frames in this manner (temporal interpolation) has been researched, for instance this (http://www.softlab.ntua.gr/~tourapis/papers/5252icip01.pdf) and this (http://www.stanford.edu/class/ee398b/project/02/repo.pdf).

-h

[athos]

Thanks for the links. It would be very interesting to see this implemented in ffdshow.

@milan - would it be possible to first implement some simple interpolation method, and then possibly expand it with other methods, giving the user a choice which one to use? I'm thinking the way you can choose what type of post-processing, noise etc. Perhaps a general method for doubling framerates, where the different implementations replace the method for calculating the frames to insert.

[milan]

OK, I'll try to code this today, because I would like you to release new ffdshow build tomorrow and maybe "simple" (just the averaging) framerate doubler should be included. However no other big changes, just XviD qpel should now be decoded correctly.
BTW I quickly looked at the papers, but unfortunatelly I don't have any experiences with motion estimation algorithms. But couldn't mpeg4 decoding routines be modified to interpolate frames? Motion vectors are known already and maybe they can be used in the process.

[athos]

One of the papers described interpolation using motion vectors, the images remind of the motion vector visualisation in ffdshow. Unfortunately, I'm not skilled enough to translate this into code.

One simple extension of the basic interpolation algorithm (in addition to the special case of I-frames), based on Tom's observation that it seems to work best with high- or low-motion secenes, is to only perform interpolation if the average difference between frames A and C is below or over some threshold values, otherwise just copy A. Some testing would be needed to determine suitable values for these thresholds, and/or these values could be provided by the user. This should still be pretty cheap regarding cpu utilization. Perhaps there is some other information on the amount of motion in or between frames available for this purpose?

[Leolo]

Hello,

Milan, do you plan to include support for MPEG2 transport streams in upcoming versions of ffdshow?

If so, I'd like to ask you a favour. Would you mind to implement support for .PVA files?

Right now there's only one directshow filter capable of decoding .PVA files (Elecard) but it's commercial and it's still in early beta stage (no seeking support, playback is choppy, refuses to play some files).

I thought that maybe you could be interested, because your playback filter is undoubtedly the most feature-packed of them all, and could be the solution we're been waiting for so long. (Believe me, it's a real pain to have to demux the .PVA files with PVAStrumento, and then mux them again with BBMpeg in order to watch the clips).

This is the official document that describes the .PVA format:

http://www.technotrend.de/download/av_format_v1.pdf

I don't know any programming language, and I'm not an expert in computing science. However, I'll gladly help you with betatesting if you want, and I'll contribute as much as I can. Please let me know if you are interested.

Thank you very much.
Best regards.

[Defiler]

Back to the original topic; I think this is a superb idea. I can't help with the code, but I'll be the project's official cheerleader.
Go go ffdshow!

[LoKi128]

Browsing around the web, I saw this program

DynaPel MotionPerfect (http://www.dynapel.com/private/mp_overview.htm)

It interpolates frames, and as far as the example video show, it does a damn good job at it too. If you have enough $$$, just buy it and run all your videos thru it :)

[Blight]

Just for some references.

RealVideo did (does?) this on low frame-rate video (10/15fps), it can look ok for some scenes, but ghosting does occur.

Doing REAL interpolation is MASSIVELY computational. But perhaps today's 2ghz computers can handle it if written well.

Still, even a 2 frame average could be interesting, perhaps for animated sources.

[trbarry]

If it was being done for only very small motion then maybe it would not be as expensive to do. I'm somewhat distrustful of things that do much temporal blending. But something that caught motion of only 1 or 2 pixels / frame might be interesting.

When I said above that the In-Between frames seemed to work only for very small or very large motion I meant that is where we could get away with it. But whether it accomplishes much useful with very fast motion is a different story. I think mostly it just got away with it because any ghosting was lost in the motion blur.

I'm skeptical of motion comp that catches fast motion anyway. It may work for compression but for deinterlacing or interpolation there is also apt to be a change in size, lighting, orientation, etc. if something moves very much.

But motion comp is really not my specialty so maybe these problems are solvable.

- Tom

[OUTPinged_]

trbarry, well using that kind of framerate decimation for 30i->24p FPS conversion can be more simple than it looks in these papers.

We have "previous", "current" and "next" frames available and we need to reconstruct "current" one. 3 frames are checked for continuous motion. then we just need to rebuild "current" frame so that it would be a tad closer to "next". Maximum value that motion will go away in 0.02 second wont be big.

[athos]

I agree that it sounds strange to "make up" frames to increase the motion of the video, but I have seen it work.

The method I proposed here is the simplest I could imagine (short of simply duplicating the frames which doesnt make much sense here), and I dont expect the results to be overwhelming. Method that produce really good results, such as 100hz TVs :) probably use some sort of motion estimation. AS you point out, this is pretty heavy on the cpu. But the thing is - we shouldnt have to perform this ME as it has allready been done in compression. The motion vectors are available, at least in Xvid and Divx3 (if im not mistaken).

Just throwing some ideas here: From what I understand, given pixel [x,y] in frame A, its new position in frame C can be determined (or at least predicted) using the motion vectors (please correct me if i'm wrong). So in order to extend the averaging algorithm to use the motion vectors, the position of this pixel in frame B (which we are calculating) should be the average distance between its position in frame A and frame B. A simple illustration:

+---+---+---+---+---+---+
| A | | | | | |
+---+---+---+---+---+---+
| | \ | | | | |
+---+---+---+---+---+---+
| | | B | | | |
+---+---+---+---+---+---+
| | | | \ | | |
+---+---+---+---+---+---+
| | | | | C | |
+---+---+---+---+---+---+
| | | | | | |
+---+---+---+---+---+---+

In the above illustration, the pixel "B" would have the average value of pixels "A" and "C". To fill in the gap of the "A" pixel when computing "B", i think it should be copied from "C", since copying it from "A" would yeild duplicate pixels in the resulting frame "B".

I realise this is pretty hard for me to explain in text, and also my thoughts could even be fundamentally wrong. I will try to study the pdf documents posted here by -h and see if I can understand their methods.

Framerate doubling should of course be performed last of all things, there is no need to apply any filters to these computed frames.

[-h]

I realise this is pretty hard for me to explain in text, and also my thoughts could even be fundamentally wrong. I will try to study the pdf documents posted here by -h and see if I can understand their methods.

This is one of the preliminary ("simple") methods that Alexis begins his temporal interpolation paper with, and goes on to refine it to remove many of its inherent problems.

I will definitely attempt to implement this in an Avisynth filter at some point in time, along with any other promising methods that won't take too long.

-h

[SirDavidGuy]

Determining the MV should be easy, since it is included in the video stream. What would help with interpolation (As the Tourapis paper suggests) is a pixel based scheme. You could do a simple search for the best pixel within a certain range of where the MV suggests it would be (which would be much less computationally intensive than doing some SAD calculations).

You could measure it by using some Luma component, and the similiarities between the chroma and Luma channels (eg. U is about 1/3 of Y, V is about 1/4 of it, search first for the 10 most similiar Luma values within the search radius, then decide which is the most similiar when comparing all three channels.

This could also help with deinterlacering in FFDShow.

[trg100]

Hmm, interesting topic...

My initial thought here is that the frames generated by interpolation are gonna have to look pretty damn good. Think about it, if you are using these frames to double the frame rate then a full half of your movie will consist of these frames. I suspect that a simple averaging algorithm will generate frames that look fairly crappy.

Opinons??

(I admit I haven't studied more advanced methods of temporal interpolation.)

[milan]

New ffdshow version should be released today with framerate doubling by averaging. It uses Integer SSE instructions (pavgb), but this should be OK, because older computers wouldn't be able to display 50 fps anyway. No scene change detection is implemented yet, but results aren't as bad as I was expecting.
Just check ffdshow sourceforge page regularly.

[athos]

New alpha build is up, see http://forum.doom9.org/showthread.php?s=&postid=202410#post202410
Download it from http://sourceforge.net/projects/ffdshow/

[vinouz]

:(
and what about 'old' Non XP athlons (I think @1.3Ghz, I could manage some sort of CPU usage - not every video is 768*576@25FPS...)
vinouz

[SirDavidGuy]

Originally posted by milan
New ffdshow version should be released today with framerate doubling by averaging. It uses Integer SSE instructions (pavgb), but this should be OK, because older computers wouldn't be able to display 50 fps anyway. No scene change detection is implemented yet, but results aren't as bad as I was expecting.
Just check ffdshow sourceforge page regularly.

Are you sure you want to go in this direction for temporal interpolation? A pixel-motion based method wouldn't be much slower, but would significantly increase quality (and the resulting code could help with deinterlacing, with some changes).

[milan]

No I don't, but this was easy to implement. If you have better algorithm, then please send me some example source code and I'll integrate it to ffdshow and perhaps try to MMX optimize it too.

[vinouz]

and perhaps try to MMX optimize it too
thanks :rolleyes:

[athos]

I have studied Milan's code for frameratedoubling (it's very nice and clean imo) and although I understand some of it, I dont have enough understanding of for example MV to specify a refinement of the framedoubling algorithm directly in code. Therefore I will describe a simple algorithm in plain english here, and I hope that Milan will be able to translate this inte code. I am aware that this might not be the cleanest, fastest solution, but I see it as a step forward.

PURPOSE
The intention of this refinement of the previous, simpler, algorithm is to create in-between frames that take into account motion, using the motion vectors that are provided from encoding, while avoiding ghosting and transparency of occluded areas.

SETUP
We have two frames, A and C. Just like in the previous algorithm, we want to produce a frame B which is a "half-step" between A and C, but this time we want to use the Motion Vectors in A. C probably also has Motion Vectors, but these will only come into play in the next iteration when we want to produce frame D between C and E.

Like I said earlier, I do not have a thorough understanding of motion vectors, but I assume that the MV's of frame A can be useed to calculate the corresponding position of the pixels in C. If i take a pixel x,y in A and "follow" the MV's "all the way" I will be at position x',y' in C. At least I hope MV's can be used this way.

METHOD
Create a frame A', by moving the pixels from A, following the MV's of A "half-way" (remember, by "all the way" we would end up at their corresponding position in C). For example, lets take a pixel at pos 1,0. By following the MV's fully, it would be at pos 3,0. Half-way would mean 2,0.
- If multiple pixels end up at the same position, use the average.
- Some pixels in A' will be empty, copy these from C. These are pixels that were occluded by something in A.

Create a frame C', by moving the pixels from C, using the MV's of A in reverse (backwards). That is, calculate which corresponding position the pixels in C have in A, using the MVs of A. Note: the MV's of C are not used at all.
- Like A', average pixels that "collide".
- For any empty pixels, copy these from A.
  EDIT: Come to think of it, maybe these should be copied from C instead of A...
  EDIT2: The more I think of it, the more certain I get that these should be copied from C. IE: Empty pixels in both A' and C' should be copied from C.

Interpolate A' and C' to create B, preferably by the same method used in the simple averaging algorithm.


COMMENTS
What do you think of this proposed solution? Like I said, I am aware that this probably could be done in a cleaner way. Still I hope it wont be too slow. The intermediate frames, A' and C', can be saved between calls to the process()-method and reused, so they dont have to be allocated every time (as all pixels are replaced). There has to be some way to keep track of which pixels have been filled and not in A' and C', so one knows which ones need to be copied from C and A, respective.



Another note: I think it would be preferable to perform this framerate doubling last in the chain of filters. This is because there should be no need to perform any post-processing or such on these calculated frames.

[SirDavidGuy]

please send me some example source code and I'll integrate it to ffdshow and perhaps try to MMX optimize it too.

Sure, but I'm not too good a coder (eg. Will take a while, and I might get bored in the process).

Is C++ okay? (I thought FFDShow was in C, I am not sure though).