Detecting scenechanges!?!

[killerhis]

OK short question... a method to detect SceneChanges.. with high accuracy... any suggestions? Like using which filter and which settings?

Hope to get some responce.. Need this info to make a sertain filter!!

So who got some ideas?

[sh0dan]

Seems like a development question.

A commonly used method is averaging luma difference between two frames. If it is larger than a threshold -> scenechange.

YDifferenceFromPrevious() will do this for you, if you're writing a conditional filter. If you're looking for code, it's used in temporalsoften, mipsmooth or you can look in the conditional funtions.

[killerhis]

I've tried YDifferenceFromPrevious() a while ago, didnt got me 100% scenechange detection.. anyone knows a better way?

[bilu]

May be an inspiration for development. It could be great if Avisynth filters could somehow benefit from motion vectors.

http://forum.doom9.org/showthread.php?s=&threadid=66682

Bilu

[mf]

With my sleepy head, I've just thought of something. KillerHIS, you want to get rid of scenechange film tape(or whatever it is), right? How about measuring YDifferenceFromPrevious for the entire frame, measuring YDifferenceFromNext for only the part that contains the film tape, and measuring YDifferenceFromNext for the part that doesn't contain the film tape. If you have a film tape scenechange, you should have a big YDifferenceFromPrevious for the entire frame, a big YDifferenceFromNext for the film tape part, and a small YDifferenceFromNext for the rest of the frame.

[killerhis]

LOL MF.... you think I'm that stupid :sly:

That's my old Idea.. which I worked out.. problem is.. detection aint 100% secure.. its more like 60%. When you got a lot of motion. it detect it as a scenechange. And if you higher the thresholds, you miss the real scenechanges :(

I'll keep working on this and hopefully get something good!

[mf]

Ok then how about measuring the color too ? Cause the film tape is usually greyscale.. :D

[scharfis_brain]

how about measuring the luma/chroma difference from frame to frame forwards AND backwards about lets say 10 frames.

now you can build a luma/chroma-differnce-curve.

on a scene-change there will be a jump in this curve.

building the differncial
(in German Ableitung: f'(x) )
of this curve should give a peak at the scene-change.

Look at this quick drawing:

http://home.arcor.de/scharfis_brain/samples/scenedet.gif

Or a I totally off?

[arlsair]

Originally posted by scharfis_brain
of this curve should give a peak at the scene-change.
That there is a jump in the differential-curve, I can understand, but where comes the peak from?

[scharfis_brain]

Since I cannot explain this in english, I'll now break the rules to explain this in German. Sorry for that.


Die obere Kurve ist die Luma-Differenzkurve.
Die untere die 1. Ableitung der oberen.
f_unten(t) = f_oben'(t)

durch den sprung des luma-differenzwertes (obere Kurve) kommt es bei der Ableitung derselben zu einem Peak in der unteren Kurve.


I hope, that Arlsair understands my explantation, so that he is (maybe) able to translate it....

[Wilbert]

That's not an explanation, but a repetition of what you said above. I think alsair understood that. The question is why does a jump in a function results in the derivative being infinite at that point.



It is well known that the derivative of the stepfunction is given by the dirac delta function. In other words

H'(x) = delta(x)

Where H(x) = 1 for x>=0 and = 0 for x<0 (the value at x=0 is not relevant), and delta(x) = infinity at x=0 and = 0 elsewhere.

Note that the derivative doesn't exist (at x=0) in the normal sense, because the left and right limit should be equal in x=0.

You can check it by integrating:

For x>=0:

int_0^x H'(x) = H(x) = 1
int_0^x delta(x) = 1

Similar, for x<0:

int_0^x H'(x) = H(x) = 0
int_0^x delta(x) = 0



Sorry for the math :) The function with the jump is quite similar to the stepfunction.

[killerhis]

you could talk all mathamatically, but math needs to be applied!

So just in plain english. When a huge difference occure in a small periode, you get a peak(between 2 frames) but if there occures a small difference in a small periode then it almost stay constant!

Other words, messure the difference between frame. I'll see what more options are left!

[arlsair]

Originally posted by killerhis
So just in plain english. When a huge difference occure in a small periode, you get a peak(between 2 frames) but if there occures a small difference in a small periode then it almost stay constant!
I don`t think so. Mathematically it doesn`t matter how big the jump in the curve is: if there is a jump, you get an infinite big peak.
But I think this method could detect to much scenechanges. This can occur in e.g. high-motion scenes. So there have to be a threshold to override this fake-scenechanges.

@scharfi,wilbert:
Thanks, I was just not up for a moment, I think (or it was this bloodily painted graph ;-)

[Mug Funky]

with video, you can't really treat discrete frames as a continuous function, but if you do so you'll definitely increase your ability to detect scene changes.

basically those peaks measure the rate of change. if a change happens instantly, then obviously the rate of change is infinite. in reality it's just quite high...

for example take a car's airbag - the time it takes for your head to slow to the speed of the steering wheel (in an accident) is a lot less than the time it takes for it to slow down when it hits an airbag.

the shorter the time, the higher the force.

with scenechanges, the luma is changing (rather than the speed of your head :D). it'd be _nearly_ smooth in scenes, and when there's a cut, even a small one that would be missed by a scenechange detector (like cutting from 2 angles in the same actual scene), there will still be a sizeable jump in the rate of change as opposed to the actual change (which could easily be below any thresholds).

still, i think the derivative thing could have some problems with false positives in high motion scenes. i suppose a clever enough script could have overrides...

[edit]

incidentally, i know a guy doing his PhD thesis on scenechange detection... i haven't discussed his research though.

[sh0dan]

You could also import the stat-file from XviD. Have a look at XviDStatImport (http://forum.doom9.org/showthread.php?s=&threadid=68027&highlight=Xvid+stat+import).

[killerhis]

Thankz.. I'll take a looksie at it soon when I got the time. But can I detect all scenechanges using xvid stat files?

[sh0dan]

It's a different approach - it might give better results. I'm not using it for that, so I don't know.

However be sure to set maximum I-frame distance to a very large large, otherwise you will have a "fake" scenechange every X frames.

[WarpEnterprises]

I still don't see what would be the purpose of this detector?
1) to help some encoding
or
2) to analyze the content.

For 1) some false SC (e.g. filming out of a fast-moving car) won't hurt
2) would be much more demanding, maybe some global search strategies between the frames? (If there are common objects it's no SC)

[ARDA]

I don't know if I have understood correctly. But I remember that DIVIDEE has attached
some time ago a scene_change.zip. It is and unfinished work and was done before YV12
was included. It was developed for YUY2 AND RGB32. If I'm not wrong he intended to include
it in avisynth.
I still have that code in my HD. Unluckily I can't attach it; but if anyone is interested
just tell me where to e-mail it.

ARDA

[Wilbert]

I attached the code of Dividee.

[sh0dan]

Basicly it compares two frames pixel by pixel, and accumulates the number of cases where the difference is bigger than a given tolerance.

[d'Oursse]

Just one thing about what Scharfis Brain said :

it look at the derivative to find the scene change (he looks at the eventual peaks of f')

Such things are also done when you want to find the edges of objects in a image. I have read a paper where they use wavelets to find the peaks of a curve.

if some of you are interested, i can find the references.

[scharfis_brain]

forget about my idea of using f' for scene-detection.
It is useless.

lets assume following:

f(t)=x_t , where x_t is the avg-luma of the corresponding frame at the time t.

f'(t) is simply the rise of f(t)

now, delta-t is constant (time from frame to frame)

the rise can be calculated by
m = delta x_t / delta t

this means
m ~ delta x_t

it will be nothing else than just comparing luma differencies to luma differencies...

[WarpEnterprises]

What about using the Deshaker output/code from gunnar thalin?

[esby]

you can use histograms too, to detect a scene change...

example with RGB:

first you need to define a list of colored aggregates
eg: if you take r,g,b from 0 to 255
sqrt(r*r+g*g+b*b)/3 will vary between 0 and 255

If you divide the result (integer division) by a number called 'Qual'
you can define 255/qual levels.

If you compare the levels that changed between two pictures,
you can get an idea of the scene change.
A way to do it is to sum the abs of the difference of each level used.
Sum[i from 0 to nbLevels] of ( abs( hPrev[i] - hCurrent[i] ) )
(you can normalize the sum by dividing by the total number of values in each level == numbers of pixels of the image)

If this sum is equal to 0, the agregate did not change (in volume)
and you can guess there is probably no scene change.
If there is a scenechange, the colour repartition would probably be affected,
And the volume of the agregates would change... so would change the histogram levels...
And you would detect it. (by seeing a non 0 value for the normalized sum)

Of course the limit of the method, is that you are first limited by
the way you choose the agregates.
In the given example, it calculates using an approximation of the luminance (by calculating an rgb distance)...
So you would probably inherit the problem linked with luminance.
(eg no fading detected...,
and plasma effect considered as scene change...)

esby

[WarpEnterprises]

Would it be helpful to collect/make a small clip with _difficult_ scenechanges (e.g. fades, fast motion w.o.SC, ...), so that we can test our ideas?

[Schlumpf]

@sh0dan

I tried your suggestion and "abused" xvid for scenechange detection, or at least
hoped to do so, since my script fails to produce some valuable results.


LoadPlugin("C:\dvd\avisynth\XStatImport.dll")
there=AVISource("C:\Test\Test.avi").ConvertToYV12()
ScriptClip(there, "change = String(xvid_type)"+chr(13)+"change == chr(73) ? there.FreezeFrame(current_frame,current_frame+2,current_frame+3) : there ")
xstatimport("c:\Test\test.stats", show=false)


While this is the only version of the script that I managed to get to work,
it is only subpar, because Scriptclip only evaluates ONE Frame and not
the next three frames as written in my function :(
ConditionalFilter wouldn't work too, since it is based on comparing 2 different
sources, but in this case I have a source and a variable. So I thought passing
on the variable via FrameEvaluate would be the way to go.


LoadPlugin("C:\dvd\avisynth\XStatImport.dll")
video=AVISource("C:\Test\Test.avi").ConvertToYV12()

global sc = int(0)
FrameEvaluate(video, "change = String(xvid_type)"+chr(13)+"change == chr(73) ? sc = 1 : sc = 0 ")
xstatimport("c:\Test\test.stats", show=false)

function investigator(clip c)
{
final = (sc == 1) ? c.Greyscale() : c
return final
}

investigator(video)

I didnt bother to insert the FreezeFrame-stuff yet, wanted to make the internals
work rock-solid first. So, what I expected from this script was to turn the video
black and white at every I-Frame. In order to do so I let FrameEvaluate read out
the stats-file and change the variable sc to 1 for every I-Frame and to 0 for
the rest.The "investigator" function should then pick up this variable and
turn the video black and white if sc = 1 . Unfortunately it appears that
FrameEvaluate isn't regarded at all, because the video never turns black and
white. It seems that the value that is entered in global sc is taken all the
time without FrameEvaluate ever being considered.
If I enter global sc = int(0) = all coloured,
if I enter global sc = int(1) = all black&white. I couldn't delete that line either,
because Avisynth wouldn't recognize the variable sc anymore
(is there any other
way to introduce a variable for this purpose besides global?). And now I come
here as a helpless noob who has tried his best but exceeded his limits :(
If anybody would mind to help me, I'll gladly appreciate it :)

[sh0dan]

video = mpeg2source("C:\temp\2f2f\2f2f.d2v")
filtered = video.greyscale()
conditionalfilter(video, filtered, video, "(xvid_type == "+chr(34)+"I"+chr(34)+")" , "=","true", show=true)
xstatimport("c:\video.pass", show=true)

(You should of course disable both show=true)

[Schlumpf]

Wow, thanks sh0dan, that really did the trick! (Can you imagine how embarassing it is to come up with some monsterscripts and then you solve it within 4 lines :eek: )

However, now that the rough structure works I find it hard to implement my main goal: Freezing the following and the preceding frames. As I wrote in my earlier post, ScriptClip apparently only evaluates the current frame and does not cache the preceding or the following (If I'm wrong, please give me a hint! ), ConditionalFilter doesn't seem to cache either.
That's when I started experimenting with ConditionalReader. In its readme is described a way on how to apply values to certain ranges and that seemed just like what I needed.
I made a testfile (test-sc.txt) that looks like this:
Type Int

R 440 442 439
R 443 445 446

Frame 443 is an I-Frame and has severe jitter that continues until Frame 445, so I want to replace them all with Frame 446. But the jittering already starts in the preceding frames (440-442), so I want to replace them with Frame 439.
I tried to accomplish it with the following script:
doh=AviSource("C:\test\test.avi").ConvertToYV12().Killaudio()
ScriptClip(doh,"DuplicateFrame(SCKiller)")
ConditionalReader("c:\test\test-sc.txt", "SCKiller", false)

What I expected to happen: Condtionalreader will submit the ranges to Scriptclip together with the variable "SCKiller". DuplicateFrame,which is called up by Scriptclip, will then overwrite the frames with the "SCKiller"-Frame (439 and 446).

What really happens: Video is delayed by one frame (Accidental DuplicateFrame(0) ??). And: Original Frame 442 is replaced with Frame 441 (scenechange remains at frame 443,though) and Frame 446 is copied into Frame 445.Nothing else.
As usual I'm totally dependant on people who actually know what they do :(

Oh, one last thing: I was really paralyzed when I came across this (http://forum.doom9.org/showthread.php?s=&threadid=50105&perpage=20&highlight=conditional%20filtering&pagenumber=2) thread. Pay special attention to Homie FR's last post on hat page. He introduces a scene change detector that can actually replace the preceding and following frames and it WORKS >__> . The thing is: Whenever I look at it, my face turns into a question mark. Especially the SCCleaner and SCCond functions give me headaches. Why can he freeze over a range of 20 frames? (frame-10,frame+10,frame...) and still get a perfect output?
Am I missing something obvious or am I just plain dumb? ^__^°°

[esby]

Well i did not ring immediately into my head
that you wanted to detect scene change for framefreezing...
So just in case...
If you feel like doing it semi manually...
(aka controlling it and 'wasting' 2-5h for a 25 min eps...)
Supposing you already have a list of frames that got a scenechange...
Check this old thread...
http://forum.doom9.org/showthread.php?s=&threadid=59002

esby

PS: if you have a list of frame
just put them in a blank text file
one frameNumber per line
and save as .lbk
You might try the lbkiller internal scenechange detection too,
but it's not optimized at all, so fear... :)

(the custom scenedetection is a possible implementation of what i was suggesting in a previous reply...)

[LB]

you can get the scene change list I believe from just looking at the keyframes in a divx file. not to hard. (that is, if you don't mind encoding it first as a trial run).

[mf]

Originally posted by LB
you can get the scene change list I believe from just looking at the keyframes in a divx file. not to hard. (that is, if you don't mind encoding it first as a trial run).
*cough* That was the whole idea with the stats importing.

[esby]

indeed mf :)

anyway, supposing you get a stat file, extracting a list of frame
would be easy.
(and if you got time, relying on the tool scenedetector could be enough)

esby

[LB]

I'm linking my thread in the normal avisynth room to this thread here because it deals with what you all have been talking about. I modified the scenechange detector a tad using both Homie FR's script and sh0dan's script, and came up with this:

http://forum.doom9.org/showthread.php?threadid=70487

It works really really well. I'm trying to improve the detection routine though, and as you will see I created a black overlay which is placed on top of the video. Now, you can stop reading if you don't deal with anime, because this is basically my version of this scene changer is geared at. A lot of old anime has really nasty tears in the top and bottom upon a SC, so I think that by simply removing the main content of the video, and simply check for the appearance of like +50% white in the top/bottom of a frame, it will improve the detection rate dramatically.

The area I'm stuck on now though, is how to replicate the cuts/dupes I have made on the overlayed video, to the original video w/o the overlay. The only way to do that I believe is to deleteframe() and duplicateframe() on two videos at the same time, thus they will have the same cuts - video1 = black overlay'd with only ~20pix from the top/bottom visible; video2 = orig. video

But... how I go about doing this is what I can't figure out. Having one ghetto loop is about all my brain can handle, yet I need two, combined... :confused:

[esby]

I tried your script on a sample i have...
(i took some HxH vobs from my magical hat,
now you know why i was never able to sell this hat :D )

First i had to kill idtc=5
having an athlon :)

Secondly,
in some scenes, the scenechange is detected,
but the correction is :
* Somewhat correct, (i'll explain why i only say 'somewhat' and not perfect)
* uncorrect, the scenechange got moved from one frame...
* totally uncorrect, if we have frame 0 1 <sc> 2 3 we end with 0 2 1 3 ...

The last case could be a bit problematic :)

But now let I explain the 'why' of 'somewhat correct'... :mad:
take an example:

frame 0 1 2 3 <sc> 4 5 6 7

3 has a big black bar of 2-3 pixels on the bottom...
4 has a big white band on the top ...
5 has one too smaller...
6 is almost correct, 7 is ok

supposing you correct by doing that:

0 1 2 2 6 6 6 7
(since you cannot use 5 since it s still garbled)
You'll end most likely with a problem,
since 6 appears streched & blurry compared to 7 ...

And it is what i'm seeing oftenly in the sample i'm testing with.

check http://esby.free.fr/samples2/ to see an example...
pattern 0 1 2 sc 3 4 5 6 'corrected' as 0 2 1 3 4 5 6...
--> inversion & shift + frames distorted

esby

PS: for your answer, i personally think it is better to
detect the change once,
and check these manually or semi automatically after... (and correct these...)

[killerhis]

Well first thankz everyone for repling.. I'm kind bussy so I haven't worked and test all your ideas.. but I'll work on it soon :)

The hole point for auto scenechange detecting, is to get rid of manual removing scrates on old sources. As you probably seen often, on old sources (especially old anime sources) you got like white scrates on the top and bottom. For some reason, they only occure during scenechanging! If I somehow could detect a scenechange automaticly, I could find a effective method to get rid of the scratches. I already tried a lot of filters to get rid of the scratches, but with no effect.

So manual checking aint a option esby, otherwise I could better use the other method (using Tmpgenc ^_^)

[/edit] hehe I should waited 5 min, until Schlumpf did his post ^_^.. OK Schlumpf I'll test your AVS soon, and about the Minimum I-Frame Interval.. wasn't: Minimum I-frame / Maximum I-Frame = Frame Drop Ratio ??? (I could remeber something like that.. or isn't this true?)

[Schlumpf]

I found a way how to use Xvid for scenechange replacement (I just had to think simple, not complex :D ). It's not perfect and needs almost always 2 passes, but it should be faster than doing it manually.
I'll presume for this that you already generated a valid stats-file.
Make an avs-file that looks like this:

LoadPlugin("C:\dvd\avisynth\XStatImport.dll")
LoadPlugin("C:\dvd\avisynth\chr.dll")
Main=AviSource("C:\Test\Test.avi").ConvertToYV12().Killaudio().PointResize(160,120).AssumeFPS(48)
Clip1=Main.Write("c:\Test\sc_test.avs","FreezeFrame(","current_frame",",","current_frame+3",",","current_frame+3",")").Write("c:\Test\sc_test.avs","FreezeFrame(","current_frame-2",",","current_frame-1",",","current_frame-2",")").Write("c:\Test\failsafe.avs","ApplyRange(","current_frame-1",",","current_frame",",","chr(34)","Subtitle","chr(34)")
Clip2=Main
TestClip=Main.Trim(1,0)
ConditionalFilter(TestClip,Clip1,Clip2,"(xvid_type == "+chr(34)+"I"+chr(34)+")" , "=","true", show=false)
xstatimport("c:\test\test.stats", show=false)


The PointResize(160,120).AssumeFPS(48) stuff is for the speed. In fact you can raise the speed as high as your machine can take (mine started choking at 120 FPS ^^°), since this step is simply there for generating 2 avs-files and nothing else. Play the above script in any player you like.
Then we will check, if Xvid did its job right. Open the failsafe.avs in Notepad and mass-replace "Subtitle" with "Subtitle","SCENECHANGE?") (If chr.dll would let me write more than 7 variables in a line, this step wouldn't be necessary :/ ). Next, create a new script with just the following:

AviSource("C:\test\test.avi").ConvertToYV12().Killaudio()
Import("C:\Test\failsafe.avs")

ConvertToYV12() and Killaudio() are optional.
Now you will have the text SCENECHANGE? displayed every frame before and on the scenechange. If you see any mismatching, open the sc_test.avs and delete the corresponding lines. I would suggest to do that in Virtual Dub since you will need the framenumbers. I also like to do it in realtime (aka pressing the "play" button ;) ) but the speed here is up to you. When you cleaned up your sc_test.avs you can change the script to this:

AviSource("C:\test\test.avi").ConvertToYV12().Killaudio()
Import("C:\test\sc_test.avs")

And all the scenechanges should be well now.

By the way: If anybody knows how to reactivate the "Minimum I-Frame Interval" in current Xvid builds again, please tell me! :)
Would make the processing of high-motion scenes easier (way too many keyframes, right now :/ )

[scharfis_brain]

sorry for bumping this thread back to top, but while playing with motion/comb - masks I had some ideas...

what about using the masktools.dll function motionmask for detecting scenecuts?

the motionmask will always be nearly completely white on a scene-chenge!

if the scenechange is blended, we will get two following nearly white motionmasked frames. this should help freezing a frame on bad scene cuts.

Still nothing is scripted, those are just my ideas about this for now.