Analysis Filter: BlendWeight

[mg262]

Here's a filter I wrote while trying to analyse something... it's not polished, not optimised and probably of fairly marginal use but just in case, here goes:
_______________________________________


BlendWeight

Brief description:
Takes a frame which is a weighted average (i.e. blend) of previous and next frames, and calculates the weights used.

Full description:
BlendWeight(clip, int) - takes a YV12 clip and a frame number n, and finds alpha such that the difference of [n] and

(1-alpha) * [n-1] + alpha * [n+1]

is minimised in the 2-norm. (Here [k] is frame k, treated as a vector of pixels).

(The size of the difference in the 2-norm is the sum of the squares of the differences for each pixel -- I think this may be the same as the SAD = square average difference? Anyway, it's a reasonably sensible measure.)

Only the Y plane is used; chroma information is ignored.

Alpha is written to weight.txt and a descriptive line is appended to BlendWeight log.txt.

The output is identical to the luma of the original filter except for frame n; the output for frame n is re-blended from prev. and next frames using the alpha computed. (Chroma is deleted.)


Example:
_______________________________________
Loadplugin("D:\cp\BlendWeight\Release\BlendWeight.dll")

avisource("fr3.avi")
#ditch the bottom field
separatefields()
selecteven( )

converttoyv12()
greyscale()

o=last

BlendWeight(4310)
BlendWeight(4312)
BlendWeight(4314)
BlendWeight(4316)
BlendWeight(4318)

BlendWeight(4335)
BlendWeight(4337)
BlendWeight(4339)

subtract(o,last)
stackvertical(o,last)
_______________________________________

This gives the following log file:

Frame 4310 = 0.2033 x prev. Frame + 0.7967 x next Frame
Frame 4312 = 0.3909 x prev. Frame + 0.6091 x next Frame
Frame 4314 = 0.6176 x prev. Frame + 0.3824 x next Frame
Frame 4316 = 0.7962 x prev. Frame + 0.2038 x next Frame
Frame 4318 = 1.0149 x prev. Frame + -0.0149 x next Frame
Frame 4335 = 0.2140 x prev. Frame + 0.7860 x next Frame
Frame 4337 = 0.3912 x prev. Frame + 0.6088 x next Frame
Frame 4339 = 0.6028 x prev. Frame + 0.3972 x next Frame


Notes:

I wrote this while trying to analyse a DVD with blended fields. The results in the case I'm looking at are thrown off slightly by a slight horizontal wobble; I might write a version to compensate for this. But the filter seems to be accurate enough to bring out the pattern in the case above (i.e. very close to multiples of 0.2). If anyone else has seen this pattern anywhere, I would be grateful if you would tell me!

[scharfis_brain]

IMO those weights occur on PAL -> NTSC conversions.

[mg262]

>IMO those weights occur on PAL -> NTSC conversions.

It's a PAL source. Do you mean NTSC->PAL as well? I wrote this as a prerequisite to a plugin to reverse 24->25fps conversion, making the assumption that the resampling was regular - i.e. that it looked like this:



(example for 4fps -> 5 fps; so

new 0 = old 0
new 1 = 1/4 old 0 + 3/4 old 1
new 2 = 2/4 old 1 + 2/4 old 2
new 3 = 3/4 old 2 + 1/4 old 3
new 4 = old 3 )

But when I tried to start the reverse conversion it became obvious that something more complex was happening. (BTW I was considering top field only.)

I trimmed the example above to make it more readable, but here's a wider pattern - as you can see, the weights seem to step up by 0.2. each time:

Frame 4096 = 0.2024 x prev. Frame + 0.7976 x next Frame
Frame 4098 = 0.3927 x prev. Frame + 0.6073 x next Frame
Frame 4100 = 0.6036 x prev. Frame + 0.3964 x next Frame

Frame 4237 = 0.2158 x prev. Frame + 0.7842 x next Frame
Frame 4239 = 0.4203 x prev. Frame + 0.5797 x next Frame
Frame 4241 = 0.6024 x prev. Frame + 0.3976 x next Frame
Frame 4243 = 0.7997 x prev. Frame + 0.2003 x next Frame
Frame 4245 = 1.0060 x prev. Frame + -0.0060 x next Frame

Frame 4310 = 0.2033 x prev. Frame + 0.7967 x next Frame
Frame 4312 = 0.3909 x prev. Frame + 0.6091 x next Frame
Frame 4314 = 0.6176 x prev. Frame + 0.3824 x next Frame
Frame 4316 = 0.7962 x prev. Frame + 0.2038 x next Frame
Frame 4318 = 1.0149 x prev. Frame + -0.0149 x next Frame

Frame 4335 = 0.2140 x prev. Frame + 0.7860 x next Frame
Frame 4337 = 0.3912 x prev. Frame + 0.6088 x next Frame
Frame 4339 = 0.6028 x prev. Frame + 0.3972 x next Frame

Frame 4344 = 0.6090 x prev. Frame + 0.3910 x next Frame
Frame 4346 = 0.8051 x prev. Frame + 0.1949 x next Frame
Frame 4348 = 0.9963 x prev. Frame + 0.0037 x next Frame

Those frames are selected by hand to be ones where the blend is visible and the camera is stationary. Animation seems to change every other 'underlying' frame (field? anyway, I'm only looking at top field), whereas the camera moves every frame.

Most runs of blended frames like these are followed by sequences which have no blended frame, but where each frame is duplicated, which is consistent with animation changing every other frame.

There doesn't seem to be any periodicity in the occurrence of the runs of blended frames.

Anyway, thx for the thoughts...


Edit: I think sometimes animation stays for 3 underlying frames, causing quick changes like:

Frame 4385 = 0.4200 x prev. Frame + 0.5800 x next Frame
Frame 4387 = 0.6087 x prev. Frame + 0.3913 x next Frame
Frame 4389 = 0.8085 x prev. Frame + 0.1915 x next Frame

Frame 4392 = 0.5987 x prev. Frame + 0.4013 x next Frame

[scharfis_brain]

Some time ago, I wrote a article about weird types of interlacing
(basically, how weird FILM to PAL conversions in real life are).

including the FILM->NTSC->PAL conversion:
http://home.arcor.de/scharfis_brain/...terlacing/#2.3

but it is in german, and I do NOT intend to translate it.
(also it will need a major re-write, but I do have some lacks in time and ambition to do so)

majbe the sketches on that page will help you to understand the NTSC->PAL conversions

btw.: you need to analyse ALL fields. not only the even or odd ones alone.
restore24 is able to restore fieldblended video.
It uses a special edge-dection-mask for identifying the blends.
Your approach of weight-detection is similar to the approach of removeblend.dll
it is even capable to resote 29.97fps progressive content, that has been blended into PAL.
but 59.94fps into PAL are - who wonders - not recoverable.

In real life, there is NO constant pattern to work with.
every scene cut will adjust the pattern offset. THis is why deblending video is THAT hard to realize.

But I am VERY interested into your ideas.

[mg262]

Thank you for the link. (Babel Fish copes with it nicely.) There is absolutely *no* Way I would have figured out that some of those weird patterns happen without your explanations.

I've now analysed some of the bottom field too and the whole thing looks a bit like your pattern 2.2.2, except with four blended frames on each field rather than six. The basic pattern does repeat every 50 fields, but gets interrupted at weird places - some that are not by any stretch of the imagination scene cuts.


Since you're interested, original idea was like this (sticking with the 4->5 fps example throughout):

1. I assumed conversion was as in the previous post, but not that everything lined up; this picture shows what I mean:



So I was going to use the BlendWeight filter to figure out how shifted the bottom part was relative to the top part. With a little work it is still possible to break the situation into blocks of 4 pixels each of which is converted to 5 pixels, so it still basically looks like the situation described above.

2. The conversion described above could be written as

y=Ax,

Where

y is the vector of new pixels (size 5), x is the vector of old pixels (size 4), and A is the 5x4 matrix:



3. Now to reverse this, we can again use least squares regression. We have A and y and want to find x minimising the size of (y-Ax) in the 2-norm. A bit of algebra gives:

x = (A'A)^{-1}A'y where A' is the transpose of A

4. A particular coefficient of x corresponds to one frame in the output; so this could have been implemented nicely in AviSynth as follows:

For a given frame,
- find the appropriate blocks,
- compute matrix A (which doesn't have to be as nice as in the example above because of the shifts),
- compute (A'A)^{-1}A' (which is very quick compared to processing the pixels),
- take the row (vector) corresponding to the frame in question
- for each pixel, take the appropriate vector of corresponding pixels in prev/following frames, and multiply (dot product) with the row of (A'A)^{-1}A'.

So e.g. you might find that for a particular new frame each pixel ends up as
(-.3) * frame 5 + .8 * frame 6 + .4 * frame 7 + (-.2) * frame 8
[totally made up example with silly coefficients].


This method would work fine on your case 2.2.2, and I think on all your other examples (though I haven't checked carefully) were it not for the scene cuts. It might still be possible to make it work but it depends on knowing/figuring out more about the scene cuts.

As I said, in my case, they don't always seem to be scene cuts. If you have any idea when/where/how they are placed I would really like to know! In the meantime, I think I'm just going to have to analyse the thing (perhaps automating part of the process) until I get a better idea of where they are placed.


What else... restore24 I found out about, but only after I had this idea, so I decided to implement it anyway. But I'm going to look at restore24 whether or not this works -- anything by Didée is not to be missed!

[Mug Funky]

it's not just scenechanges - there's also the possibility of further editing after conversion. for example the region-4 '80s Astroboy boxset (PAL)*. footage was converted to PAL from a japanese master, then re-edited to match up with the american version (which had been heavily edited in parts). a lot of the time these edits happened on scenechanges, but sometimes it's right in the middle of a scene. worse still, premiere pro has b-frame issues and would occasionally shift frames around at scenecuts (previewing and editing would be fine, but on export the frames are in the wrong order. if i ever meet adobe's programming team, there'll be chunks to scrape off the wall).

i'm not sure how much material like that is out there, but i'd say there's quite a bit.

* actually, it looks much, much better than the american version which uses abominably bad film as a source, so if you want good astroboy, either get the r4 one or the japanese "tetsuwan atomu".

[edit]

if you need samples of field-blends, i've got shelves of the stuff i hope you like anime.

[kassandro]

Originally posted by mg262

(The size of the difference in the 2-norm is the sum of the squares of the differences for each pixel -- I think this may be the same as the SAD = square average difference? Anyway, it's a reasonably sensible measure.)

SAD is the 1-norm (sum of the absolute values of the differences) and it has the advantage that Intel has hard wired it into SSE instruction unit of their cpus (the psadbw instruction). However, in your problem the 2-norm is the right norm (with the 1-norm it couldn't be solved in reasonable time). In fact, your problem is a very special and very simple least square problem and already Gauss (the guy on the 10 DM bill), who was the first to study such problems, observed that the square norm (= 2-norm) is the way to go.
Intel should have also hard wired the square norm into the cpu, because it is also the natural norm for DCT and the Fourier transform in general and if the search for motion vectors would be done with the square norm instead of SAD the motion vectors would be of considerably higher quality, because the 1-norm doesn't bode well for the Fourier transform.

[mg262]

@Mug Funky

For the clip I'm working on (Jayce + Wheeled Warriors, French DVD 1st ep), I also happen to have a US DVD version, and the ratio works out to be about 25:29.974, so I'm hoping there's no manual cuts. Though from what you say, it's always possible that both are separately edited - but less likely here than with anime.

OTOH, if I rule out manual cuts, it's really hard to explain cases like this:



(Top field in top half; "0.6" means 0.6 * prev top field + 0.4 * next top field.) The normal pattern is like this:




I could try and restore 24fps from the NTSC version and use a least squares type approach to figure out how the PAL version derives from it, but there are the obvious difficulties like vertical resolution, colour matching... plus the fact that the US source seems to have a changing telecide pattern.

>if you need samples of field-blends, i've got shelves of the stuff
Thank you - I may well take you up on that... if I ever get something that works on this 'easy' case!

@kassandro

I haven't messed with ASM since pre-MMX days, although I might have to if I want to use this filter to analyse each frame. A quick search suggests that MMX PMADDWD and/or SSE2 PMULUDQ might be useful in computing the 2-norm -- although it will still be much slower than the 1-norm. Just found an elementary link on MMX dot product...

http://www.tommesani.com/MMXExamples.html#VectorDotProduct


Edit:

FWIW, It's just occurred to me that the least squares approach can also be used to reverse vertical resizing, e.g. reversing 720 x 240 -> 720 x 288; it works just as above, with

y = Ax

x = column of pixels in original source (240)
y = column of pixels in converted source (288)
A = 288 x 240 matrix used in resizing.

Computing ((A'A)^-1)A' is slower now, but once it's been done it can be used on every frame (field). Actually, the problem probably breaks nicely into lots of fast 6x5 matrices, but I have to think that through... .

[Mug Funky]

excellent. i'm watching this thread eagerly now. field-blends are the enemy of good compression. though since i got a DVD burner it's not been such a problem (re-encoding to reasonably high bitrates isn't a big problem with field-blends. QuEnc is teh shizzy for interlace).

de-blending has implications for a lot of other stuff too, though. un-converting a converted source can be quite beneficial in production situations as well.

oh, and in case i gave the wrong impression above - not all anime is messed up like the example i gave. it's the exception, not the rule. just something to keep in mind that pattern changes can and probably will happen. telecide-like overrides could probably help this - hardcore encoder people will have no qualms about manually stepping through their sources to get a good encode out of them.

[edit]

this situation may or may not be reversible - interlaced material that's been resized as progressive. these sources are rare and usually total crap, but i wonder if it's possible to pull the original fields out of it? if the material has been lanczos-downsized, i'd say no, because all frequencies above fs are filtered out by it (hence you don't actually see the familiar wavy pattern with lanczos pal to ntsc), but other resizers may retain enough info on the original. maybe i'm dreaming.

[kassandro]

Mug Funky,
the method of least squares is a method to solve a system of overdtermined linear equation in some sense. In the case of BlendWeight you have only one unknown, namely alpha, and you have 720x576 equations for full D1 clip. Thus in the case of BlendWeight you have an extremeley overdetermined system of linear equations. In the case of reversing an upsized clip you have still an overdetermined linear system but now with many unknown variables. Thus the method of least squares can be applied to reverse upsizing, i.e. you can downsize with it. I haven't really though about it, but probably the least square method results in the usual bilinear downsizing. Now, if you want to reverse downsizing, you unfortunately get an underdetermined linear system and the method of least squares cannot be applied. Thus the method of least squares can only be used for downsizing (and probably doesn't give anything new) but not for upsizing.


@mg262:
you are right, SSE can be nicely applied to BlendWeight. Actually you can compute the square norm and the inner product with another vector simultaneously. In this way with SSE 4 pixels can be processed simultaneously and with SSE2 even 8. Thus BlendWeight can be made pretty fast.

[scharfis_brain]

@mg262:
OTOH, if I rule out manual cuts, it's really hard to explain cases like this:

not hard to explain:
the underlayed video is not animated at 24 fps.
it is animated at much lower fps, like 12, 8 or 6 fps.
this means that blends can only occur if there is a movement change between two fields.

[mg262]

@Mug Funky

>un-converting a converted source can be quite beneficial in production situations as well.

In the case I'm working on, I'm hoping it will remove a fair amount of slow horizontal jitter (maybe better described as wobble) which looks like it was introduced during/after framerate conversion. (It will need a slight tweak to BlendWeight to do this.) I don't know how common jitter is though.

@kassandro

Bilinear downsizing and reupsizing would blur slightly at each stage, whereas reupsizing with least squares should hopefully remove the blur from downsizing. I think. (Even if I'm right, the effect might be too small to be worth bothering with.)

I'm not sure how useful the method would be in practice -- it would require you to know the exact original size (to the pixel) and the exact resizing mechanism. The only use I can think of is to reverse NTSC->PAL, and even then it could be messed up by crop/letterboxing. It was a random thought which might not be worth much!

@scharfis_brain
The animation is at 12fps (although the camera moves at 24fps) - i.e. each 'picture' is filmed twice. So during still scenes, the effect you're talking about means a blend is only visible every other frame, which gives the gaps between numbers in the normal pattern:



But I don't understand how that explains the picture-pattern I posted above, which had something like this:

TF: 0.2 --- 0.4 --- 0.6 --- --- 0.4 --- 0.6 --- 0.8
BF - no blurs

Maybe what happening is that occasional pictures are filmed once or three times rather than twice? I originally didn't think that was likely because I thought it will bring out the 'missing' numbers in the normal pattern, which I guessed were probably 0.1, 0.3, 0.5, 0.7, 0.9 (which don't turn up). They could be something else though.

I've been doing some more analysis; I modified the filter to scan the whole film and produce output like this:

2: 1002.5: (0.1988) 1.92
4: 1004.5: (0.3971) 2.29
6: 1006.5: (0.6109) 0.72
8: 1008.5: (0.8111) 0.66
2: 1015.0: (0.1964) 0.54
4: 1017.0: (0.3987) 1.01
6: 1019.0: (0.6049) 2.19
8: 1021.0: (0.8041) 2.36
4: 1027.5: (0.4001) 3.07
6: 1029.5: (0.6126) 2.79
8: 1031.5: (0.8060) 1.08

(2: is just for convenience; then frame number; then exact blend parameter, then closeness of match.)

- the 2-4-6-8 runs show up pretty clearly, so I have been able to break them up by hand and measure the periods between them. This kind of thing appears (measured in fields):

25, 25, 25, 25, 21, 25, 50, 25, 25, 25, 41, 25, 25, 25, 46, 25, 25, 60, 25, 25, 21, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 40, 25, 25, 25, 25, 25, 25, 31, 25, 25, 50, 15, 25, 21, 25, 25, 25, 10, 25, 25, 25, 25, 25, 25, 25, 21, 35, 50,

So the 'normal' pattern does seem to be the one above, with 25 fields between runs of blended fields. I don't know what causes the anomalies (if not cuts), although one possibility is that occasionally the picture is filmed one or three times rather than twice? I think this would involve assuming that the in between numbers are really 0.2, 0.4, etc. (rather than 0.1, 0.3, ...) so the full blending pattern looked like this:



I'm currently analysing these frames, which may help clear things up...



(it's a little hard to see at this scale, but the blurred 'disc/saw' in the third top field is distinct from the one in the second.)

[sh0dan]

I haven't had any material to properly test the filter on, but I thought it would be a good idea to make a conditional filter out of this.

That way it could return blend weights on the fly, so a filter could make intelligent decisions based on this information (duplicate frames, etc). It should be rather simple to code, but since I don't have the source it's hard to help. Basicly you should implement two functions. One returning the blendweight to the previous and one to the next frame.

The AviSynth code has examples (mentioned in another thread), and decomb has the IsCombed() function.

I don't know how useful it would be in scripts, but it's just an idea.

[AVIL]

Hi all,

¿Anybody knows how to use the last version of this plugin?. Dll is dated 18/11/2006. It don't accepts parameters and the output is a clip with a frame of 256x32.

Thanks in advance.

[Fizick]

try read a source.
Wilbert published some mg265's source here

[Wilbert]

http://forum.doom9.org/showthread.php?t=118430

[AVIL]

Hi,

From blendweight.cpp :

public:

BlendWeight(PClip _child, int startFrame, int endFrame, IScriptEnvironment* env);


....

double weight = num/denom;

......

return weight;

However the script :

AviSource("p1_40000_49999.avi").blendweight(100,200)

returns error:

Invalid arguments to function "blendweight"

If I try the script:

AviSource("p1_40000_49999.avi").blendweight()

It returns a fake clip of 256x32

And the script:

s=AviSource("p1_40000_49999.avi")


scriptclip(s,"subtitle(string(blendweight()))")

returns clip untouched, so blendweight don't returns any value that string can process.

IMHO the binary not belongs to source.

Regards.

Simple question: if this filter is telling you that a particular frame is made up of 0.6 x prev frame ('A') + 0.4 x next frame ('B'), how would you restore it to a non blended frame?

I.e would you invert frame B and merge it onto your blended frame, or use overlay in 'subtract' mode, or some other method?

[wonkey_monkey]

I've been considering this exact problem recently.

Flimsy, if a particular frame is a blend of a previous frame and the next frame, wouldn't you just replace it with one of those?

You'd only need some other method such as you suggest if you only had one "good" frame and one blended frame, and you wanted to restore the missing good frame. As it happens I've had to do exactly that for chroma only in my project, so I wrote a quick filter which did (A-B/2)*2 where A's frame has a blend of "correct" chroma and B chroma, and B is a clean frame. This was good enough, although I wonder if gamma should ever be taken account when dealing with luma blends? I also tried to write a filter like BlendWeight, but never got good answers from it.

If I was doing a frame de-blending strictly in plain AviSynth, I would probably do a mix of levels adjustment and subtract overlay, which seems to work more-or-less correctly in Photoshop, at least.

David

Originally Posted by davidhorman

Flimsy, if a particular frame is a blend of a previous frame and the next frame, wouldn't you just replace it with one of those?

Well, normally yes. But in this case I'm working with a bobbed clip which I'm hoping to weave back to get a full resolution frame.

So field 1 is from frame A, field 2 is a blend of frame A+B, field 3 is from frame B. I want to unblend field 2 so I can restore frame A.

The pattern is not actually that simple and becomes a nightmare later on, but I'll save that for a new thread.