Extended decimate detection

[sh0dan]

Written by neuron2 in another thread in another time ;)
Is it possible to set the frame rate and count in the filter's destructor, where we know how many duplicates we have?

What would the point be - I'm not quite following you there?

When the filter is detroyed it means that the client AVI is finished.

Are you planning on writing a "logfile" in the destuctor? And doing some kind 2 pass decimation?

Edit: You can ONLY set fps in the constructor - after that the 'vi' information is passed on to the next filter, and finally to VFW. So you have to know the fps, the number of frames, when you initialize your filter.
It is possible to request any number of frames in the constructor - but I don't think reading through the entire file on load is a very good solution.

[Guest]

Have an option that does this:

pass=0: causes filter to count the dups to be removed
pass=1: runs removing those dups, taking the count as a parameter and setting fps and count in constructor

I've seen a 'greater than threshold' number of requests for random decimation, either for duplicates, combed frames, blends, etc. It is time to do something about it. :)

Probably I'd make a new stand-alone filter rather than clutter up Decimate.

[sh0dan]

I'm sure you realize I'll be a big task, with a big number of variables that might make it hard. Some of my own thoughts.

- Removing duplicates to achieve smooth motion. If the goal if the decimator is to achieve smooth motion I doubt a "free" decimate routine would be much more successful in this. If there isn't a simple pattern in the duplicates I doubt a "free" decimate filter will be able to find it.

- Desync. As the framerate is constant, but the decimation isn't, there will likely be parts more than one frame out of it's original position. This is where desync becomes visible.
If the goal is to do better 24/30fps hybrid, there will be larger frame delocations, effectively causing desync.

- Decimating for compressability. This doesn't make much sense. IIRC a duplicate XviD P-frame takes about 150 bytes - not really a big deal.

I have a hard time seeing the usefulness of a filter like this. It might be I'm missing something.

(I don't mean to turn this into a huge concept discussion resulting in nothing - feel free to ignore me) ;)

Maybe a "simple" modification of decimate would help. In my experience a syntax that would allow "remove x frames within this cycle", would help? It would need for "cycle" to be able to be larger (perhaps up to 100 frames or something)

[manono]

Hi-

remove x frames within this cycle

I don't know if that would help the fellow in the other thread or not. I don't know if he did enough counting to establish whether or not there was a cycle.

But it would sure help me. In my silent film encoding, in my quest to return the "original" frame rate, I've seen cycles of up to 150 frames and commonly see them in the 50-80 range. Because the Decimate cycle is limited to a maximum of 25, I'm sometimes unable to get the frame rate back to original because some duplicate frames are, of necessity, left behind. In addition, having to use multiple Decimate commands slows the encoding considerably, although I don't know if Decimate(x,y) (where x=number of dupes to remove in a cycle of y) would speed things up.

[sh0dan]

Simply storing the frame differences and remove frames based on the "score", would make it possible.

Now that we have proper speed in the YV12 decimate this shouldn't be that hard on the system.

[Guest]

@sh0dan

Please elaborate on your last post. You totally lost me. Was that addressing manono's issue? If so, how does your answer apply? :confused:

[sh0dan]

Now Decimate does (roughly - not taking all modes into account)

"For each cycle frame, do difference to previous,
"remove the frame with the smallest difference" - perhaps blend

instead it could be:

"For each frame in cycle, do difference to previous"
"Remove x frames with the least difference" - perhaps blend

Sorry about bringing the confusing "score" thing into this - it just sounded more cool. :cool:

IIRC it will only be a minor change to decimate, but it would be a lot better to use in some situations.

[Guest]

The problem is manono wants gigantic cycles. Currently, Decimate() gets cycle frames on every GetFrame() call. It'll murder the cache or get very slow, won't it?

[sh0dan]

I'll be a tough job on the cache - I very much agree to that!

<Explicit> I wish we could get the cache hints up and running. I have some half-done code lying around trying to set up a "cache-client" relationship between each filter and the parent filter - there are just so many things to consider. I wish there was an easy solution to this - Bidoche has had some great input to this, but for it to be perfect (that means without major memoryusage) a lot would have to be rewritten.

On the other hand - in a worst-case-scenario the processing time would be doubled, if frames cannot be cached. I guess that until we get a good solution it would still be a nice thing to have.

[Guest]

Has anyone tried to murder the cache to see if Avisynth can live through it?

[Guest]

OK, I went ahead and attempted cachicide. :devil:

I modified Decimate() to accept cycles up to 200 and then ran a clip with cycle=200. Apart from the long delays that occurred, all worked just fine. Avisynth held up like a champ.

I will go ahead and make the addition of the remove parameter, so that manono can do things like this:

Decimate(cycle=150,remove=25) # 25fps :eek:

This may be close enough to random decimation for all practical purposes.

@sh0dan

For the record: manono proposed this enhancement to Decimate() to me in email some time ago. Therefore, he gets credit for the idea. :p

[manono]

Hi-

Gee, I hope I'm not the only one that will find this very useful. But thanks!

Therefore, he gets credit for the idea.

Unfortunately, I'm not an original thinker. I've wished many times the max cycle number could be raised, but I got the Decimate(x,y) idea from something I read here. For the life of me, though, I can't find the thread.

[Guest]

Shoosh, I'm giving you the credit.

[N_F]

@all - Sorry to go off topic but as manono brought the silenced films up in this thread....

@manono - Is there any way you could make a short clip of one of those silenced films available? I'd like to see if I'm up to the challenge.

[manono]

Hi N_F-

Sure, I'll send you a PM.

[JuanC]

Originally posted by manono
Therefore, he gets credit for the idea.

Unfortunately, I'm not an original thinker. I've wished many times the max cycle number could be raised, but I got the Decimate(x,y) idea from something I read here. For the life of me, though, I can't find the thread. It could have been Bach:
http://forum.doom9.org/showthread.php?s=&threadid=41549

[manono]

Hi JuanC-

Thanks for pointing out that thread, as I hadn't seen it before. So it's not the one I was thinking of. But it's not a perfect example of the need for neuron2's revision, as it can be fixed using the current tools.

As Bach realized, Decimate(3) is the wrong solution, as it will take out non-duplicate frames, and leave behind a slight jerk every so often. If that is the cycle (11 dupes in every 34 frames), then the correct combination for that particular case is Decimate(4).Decimate(17).Decimate(24).

Of course, running 3 Decimates is slow, and maybe the new solution will be faster. And there are many other cases where you would need to remove a frame in a cycle greater than 25. I'm anxious to try it out.

[Guest]

> I'm anxious to try it out.

:scared: Oh no, pressure. :scared:

If it wasn't exerted by my hero manono I could just ignore it...

Well, I finished the first bit...using an array of size cycle for the drop frame data and defaulting it to use dropframe[0] for the closest duplicate so the current code will continue to work. But then the red wine kicked in and I decided to read my Feng-Hsiung Hsu book on Deep Blue instead. My next burst of sober energy will sort the dropframe array and then use it to remove the appropriate number of frames per cycle. Adjusting the frame count and rate is the easy part.

[Guest]

It turned out to be harder to do this than I expected and I had to go back to the drawing board. It is absolutely essential that random access be supported. Doing that for r-out-of-c decimation does not exactly jump out at you, especially when the duplicates can be randomly placed in the cycles. Nevertheless I believe I have discovered an algorithm. Let in be the requested frame and use be the frame to be delivered.

1. use = in + r * (in/(c-r))

2. examine the cycle that contains use and count how many dups there are in the cycle up to and including use

3. use = use + count from step 2

4. while (use is a dup) use++

5. return use

Note that the test for 'is a dup' will not allow more than r dups per cycle. This requires some limited scanning but at least not from the beginning of the file. :) Can any of the resident geniuses simplify this? I'll start coding this new feaure in the next few days.

[Guest]

I have it working!

I'm going swimming now. When I get back I'll do a little more testing and then put up an alpha.

As an experiment, I did a MultiDecimate(cycle=5,remove=2) and it was borderline watchable. :)

[Guest]

Attached herein for your decimating pleasure please find MultiDecimate() 1.0.0 beta 1. Please read the text help file included in the distribution for limitations and future plans. This is a first release to prove the concept and get user feedback.

[EDIT: Alpha withdrawn as I may have found a bug. Please stay tuned for a fixed release.]

[Guest]

Well, there was no bug; the program was operating as designed. :(

The problem was that the random access algorithm was not fully correct. I've thought more and concluded that there is no correct random access algorithm that doesn't require as much scanning as a 2-pass solution.

Therefore, I have implemented the 2-pass solution and tested it locally. Note that the second pass is very fast as there is no calculation involved or frame processing involved. 'manono' will be doing some additional testing and then I'll release it here. It seems to work well on his funny-money silent films that have weird duplicate patterns, like 43 out of every 143 frames!

The use of two passes allows for the insertion of a (GUI) application that permits manual tweaking of the decimation decisions, if desired. It also allows for totally random decimation, such as "remove all combed frames in the clip" (because the correct frame count is known before the second pass begins).

[Guest]

OK, here is a test version. It does n-out-of-m decimation with a maximum cycle size of 250. 'manono' reports that it is working well on his silent movies.

http://shelob.mordor.net/dgraft/misc/multidecimate102.zip

Instructions and limitations are in the help file, of course.

Later versions will add YV12 and additional decimation modes.

[Dali Lama]

Originally posted by neuron2
It also allows for totally random decimation, such as "remove all combed frames in the clip" (because the correct frame count is known before the second pass begins).

Very interesting. I don't really understand how this may work. Can you elaborate neuron2? I think this may mean that those clips that have two nearly identical frames, but just slight combing may be removed better now? (such as mouth combing in anime?)

Perhaps I am wrong?

Dali

[Guest]

@Dali Lama

The first pass is used to gather metrics about the frames. Then the GUI application is used to translate from the metrics to the decimation list used by the second pass (i.e., a list relating requested frame numbers to the frame numbers to be returned). Currently, the metrics collected are just frame differences, and the GUI selects the most similar n out of m frames to decimate.

The metrics gathered could however be other things, such as amount of combing. That doesn't mean that the combing detection will be better than what we have already, however! But the two-pass mechanism allows for decimating all the frames detected as combed, which cannot be supported by the existing Decimate().

The GUI application can also be enhanced to allow totally random editing of the frame remove list, thereby allowing completely random decimation.

The basic idea is simply to allow decimation that doesn't fit the 1-in-n mold.

[MrBunny]

@neuron2

This might be a bit off topic, but since we were mentioning the topic of silents this is somewhat appropriate.

I've noticed in many of the silent movies that I've looked at, it's set up with a sequence of action, then a few seconds with some written dialog and then back to the action. What I've found is that during the cycle with a change from dialog to action, decimate will sometimes take a frame from the dialog instead of a duplicate from the action section. In the cases I've seen, the action duplicate frames aren't exactly duplicate (although you can tell that they are the same frame).

I'm not exactly sure how decimate works, but I was wondering if there was a possibility of adding a new mode to it that would do the following:
1. It checks for all frames that are deemed "duplicate" (according to a certain threshold) in the current cycle.
2. It then checks each of these frames to see if it is part of a sequence of duplicate frames (guided a certain metric like threshold2 and with a sequence length given by the user) and exempts those frames from being chosen to dropped.
3. If there are more pairs of duplicate frames, it chooses the one to drop as it normally would. If there are no pairs left then it drops the exempt frame.

After having read the description of the multidecimate algorithm, this still seems to be a potential problem when encoding silents or even any movie with a series of still frames. In fact, I think that it could be worse with multidecimate as I'm not sure how the multiple frames are chosen. It seems to me that it might be possible that all the dropped frames could come from dialog instead of the actual action sequences. Unfortunately I don't have any such material on me at the moment, so this is mostly theoretical (except for what I've observed before).

Thanks for your time as always,

Mr. B

[Guest]

@MrBunny

Thank you for the report. I am well aware of this issue (it is mentioned in the MultiDecimate help file!) and am working to develop a solution.

[Guest]

We don't want to just exempt the static scenes, because to do so may result in too much decimation of action frames. Probably we want to specify a certain run size for duplicates, such that runs of this size or greater are decimated at the defined ratio, and no more.

[Guest]

Here's my plan for the static scene problem. Tell me if you think it is not OK.

You will select a mode called "cycle-based: protect static scenes". The existing mode will be "cycle-based: naive". Later will be added "global: remove all duplicates".

To protect static scenes you'll configure the duplicate threshold, which is the metric below which dups are declared, and the dup run length, equal to and above which protection will be applied. Protection will consist of calculating how many dups there should be in the run based on the remove/cycle ratio, and then changing the metric on the others in the run to be very high, so that they don't get decimated early. I'll use a trick that will cause multiple runs to be equally decimated.

Later I will add preference for doubletons and then singletons, as that is necessary for clips like Princess Mononoke.

I will begin coding this tomorrow unless I hear objections by then.

[MrBunny]

@neuron2

It seems I musta missed that in the readme :o

The layout you suggested seems about right. The only question I have is the following. How can the calculations for the number of post decimate frames be calculated without considering the other frames within a cycle (in the edge condition)? For example, given a sequence of 11 duplicate frames, after a decimate(cycle=5), you can have anywhere from 10 to 8 duplicates left depending on the types of frames surrounding the dupe sequence.
To illustrate, given a sequence of duplicate frames (D), unique frames (U) and fieldmatched duplicate frames (T) and using | as cycle boundaries:

Situation 1 (10 dupes left):
TTDDD|DDDDD|DDDTT -> correctly decimated it should be TDDD|DDDD|DDDT

Situation 2 (9 dupes left):
UUDDD|DDDDD|DDDTT -> correctly decimated it should be UUDD|DDDD|DDDT

Situation 3 (8 dupes left):
UUDDD|DDDDD|DDDUU -> correctly decimated it should be UUDD|DDDD|DDUU

Situation 4 (Example with dupes starting cycle, 9 dupes left)
UUTTU|DDDDD|DDDDD|DUTTU -> correctly decimated it should be UUTU|DDDD|DDDD|DUTU

I hope it's kinda clear what I think the problem could be with processing just the duplicate frames first and not considering the other frames that aren't duplicate, but share a cycle with part of that sequence. It was for this reason that I'd originally thought to run decimate as normal, then check if that frame was part of a sequence and only use it if there wasn't another pairs of frames that could be considered duplicate and not within a sequence.

[Guest]

@MrBunny

We're going a bit at cross purposes here. I am addressing MultiDecimate() where the large cycles can cause a problem for static sequences. I wasn't addressing these normal 1-in-5 cycles.

However, you do raise valid issues. The big problem is that we can't tell the difference between duplicates resulting from the 3:2 pulldown and those from a static scene. Besides, this never really arose as a practical problem when doing 3:2 decimation. There was a practical problem with animation that originated at 12fps, and that was solved with mode=2. But unless you produce a clip that really shows a practical problem based on your theoretical observations, I'm not going to get very excited about it, especially as doing anything about it will be extremely difficult. :)

[Guest]

MultiDecimate 1.0.3 supports static scene protection. Get it here:

http://shelob.mordor.net/dgraft/misc/multidecimate103.zip

[thalos]

@neuron2: thanks bunches for the filter... its the first solution i've found to getting 120fps encodes back to NTSC standards without creating too much jerkiness... i've been trying several ways and accidently stumbled upon it. My problem was that the source included runs of both 3 and 4 dupes one after the other. The result is still a little jerky... but i guess i'll live. Though on another note... i think i might have broken something when i tried the following:

Cycle=20 Remove=15 and Threshold=1.0 Run=15

Not sure what caused what... but the dfile began to grow rather large... it was about 4gb when i killed it. If you want i can post the mfile i used too...

[Guest]

Hi,

About that dfile growing. Get 1.0.5 from my web site. Sorry.

Any feedback you have or feature requests will be gratefully received.

If you can make available a clip that comes out jerky, I can probably fix it.

Thank you.

[thalos]

thanks for the quick fix...

Here's the short clip of one of the worst problem scenes...
http://www.cudelts.org/misc/Gravion%20Clip%20[120fps][Divx5].avi

Here's the full Opening sequence...
http://www.cudelts.org/misc/Gravion%20Clip%20-%20OP%20[120fps][Divx5].avi

I ended up using cycle=4 remove=3... which produced a reasonably non-shaky clip.

I think the problem pretty much is rather unique one to encodes at 120fps that combine both 24fps and 29fps encodes into a single source. Right now the sequence does just fine decimating the 29fps scenes... and the 24fps scenes creates AABCDEEFGH sequences... which creates small hiccups... The problem is really only that noticable during panning sequences... so... if you think you could make this even smoother... lemme know how you do it. :p

[Guest]

Originally posted by thalos
I think the problem pretty much is rather unique one to encodes at 120fps that combine both 24fps and 29fps encodes into a single source. Isn't that the whole reason for 120fps in the first place? Or is it also used for non-hybrid 24/30fps material?

Right now the sequence does just fine decimating the 29fps scenes... and the 24fps scenes creates AABCDEEFGH sequences... which creates small hiccups... The problem is really only that noticable during panning sequences... so... if you think you could make this even smoother... lemme know how you do it.The old hybrid clip problem. You could try this: Create your MultiDecimate'd sequence as above (you'll have AABCDEEFGH sequences). Then run that through Decimate(mode=1) with an appropriate threshold. That will convert C D E E F G to C D E E/F F G, where E/F is a blend. If you think this improves panning smoothness, we could contemplate adding similar functionality to MultiDecimate().

[Guest]

I have released version 1.0.6 at my web site. It adds global (non-cycle-based) decimation modes, for example, "remove all duplicates but protect static scenes".

Feedback will be appreciated.

[Guest]

Please get version 1.0.7. Version 1.0.6 is setting incorrect frame rates for global decimation modes.

[IanB]

Donald,

Do you intend to include any of the new Telecide() v5 advances into Decimate()?

I have an interest in processing certain 42 minute 80 Mb DivX files from 30 fps crude deinterlaced into smooth flowing 25 fps suitable for watching on a pal TV. I generally use a script of the form :-

AviSource("divx.avi", True, "YUY2")
Decimate(mode=0, cycle=5)
# resize, levels, etc
AssumeFPS(25, 1, True)
ResampleAudio(44100)

Given the original program material is true 24 fps film, that been 3:2 telecine broadcast, either single field captured or bash deinterlaced, then heavily compressed. I end up with an avi file that has a strong 5 frame cycle (4 frames then a "sort of" duplicate).

In scenes with strong motion Decimate() work very well, however when the motion is less strong Decimate() tends to make poor choices for the duplcate frame to remove. This causes noticable motion jitter, I can fix it with an override file but that means watching to find the jittery bits, fixing, then watching it for real. Given the material is "watch once" it's not worth the extra effort.

Running Decimate(mode=2, cycle=5, show=true) [because the output is in a convienient form] and examining the metrics it is fairly obvious why this happens. The delta values due to noise is about the same as the normal motion (or lack) deltas. Typical delta stats of a jittery stream versus a smooth stream are :-

in frm 121, use frm 152
150: 1.18
151: 1.14
152: 1.09 <- True duplicate
153: 1.11
154: 1.06 <- decimate mode=0 wrong choice

in frm 145, use frm 182
180: 1.80
181: 2.06
182: 1.05 <- strong difference
183: 2.06
184: 2.13

The problem as I see it is that Decimate() has no concept of "these delta's are to close to make a sane choice, use previous pattern to choose" it needs a sort of inertia to ride thru the quite parts.

Any chance of a new mode with such inertia?

IanB

P.S. Any chance of printing all the metrics in mode=0 like you do in mode=2?

[Guest]

@IanB

My plate is so full handling decent video properly that it is doubtful I'll ever find time to address things like repairing videos that have been misprocessed. I hope you can appreciate my time limitations.

[IanB]

@neuron2

No problem, just providing feedback about uses and limitations encountered.

The new 2 pass telecide log show lots of promise in allowing for the (near ;-) auto generation of an appropriate decimate override file.

Cheers

IanB