New Scene Change Detector version 
Published: 2021-08-18 07:59:14

There are three versions of the algorithm based on speed setting of rav1e. Detailed description of each version is down below. 
* Fast version - pixel-based version with improved threshold. 
   * Corresponds to speed level 10 of ravie
   * Performs a downsampling
* Medium version - based on motion vectors with iproved threshold. 
   * Corresponds to speed level 7-9 of ravie
* Slow version - histogram metric with block-based approach. 
   * Corresponds to speed level 0-6 of ravie

### Results
| Version | F score on BBC Planet Earth|F score on open source videos|
| --- | ---:| ---:|
|New fast version|  0.7441|0.6652|
|Old fast version|  0.6543|0.5951|
|New medium version|0.7802|0.7032|
|New slow version|  0.9217|0.7504|
|Old slow version|  0.7024|0.5628|

So the F score of the fast version is improved by 0.0898 on BBC and 0.0701 on open sorce videos.
So the F score of the slow version is improved by 0.2193 on BBC and 0.1876 on open sorce videos.


### Desciption of each version
* **Fast version** is a simple calculation of the pixel-wise difference. For each corresponding pixel the difference of values is taken and summed up. The final dissimilarity metric is the average values of all pixels. I improve the old version by adjusting threshold and modifying the metric itself by calculating numerical differentive.
* **Medium version** is improved version of the old slow version with adaptive threshold. To build dissimilarity metric motion vectors between two consecutive frames are computed. Frames are divided into blocks and each block on the second frame is shifted by motion vector. Dissimilarity metric is the average difference between all blocks. I improve the old version by adjusting threshold and modifying the metric itself by calculating numerical differentive.
* **Slow version** block-based histogram metric. Frames are divided into non-overlapping blocks. Then the mean value of this histogram is calculated and compared with the value of the corresponding block. Dissimilarity metric is the average difference between all blocks.

### Results and examples of each version
#### Slow version
The slow version is marked in the legend as _"with blocks"_. _"Without blocks"_ is the similar metric but without division of frames into blocks.
Results on BBC dataset:
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/p7bc3kldc06bc7f4garh.png)
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/esey2w2bo3y1brmlf5ip.png)
Results on open-source videos:
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/x9en1owgh6oyono62926.png)
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vz2s2usqwwnm8l5kb354.png)
#### Medium version
Here you can see charts of performance (F score, precision and recall) of the algorith depending on the threshold. These results were obtained with open-sourced videos from youtube.com and vimeo.com
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ttodfkd2sku61basvx57.png)
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/747caqwhnz1q2em3yt2t.png)
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ma8vfvjv6z2n8q4efgb3.png)

Here also the results on BBC Planet Earth datset:
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rva4r30vpwrbpl0temb4.png)
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ilmo9bhgq93ce94qh9rd.png)
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7keabmbbpvj32i5t5mek.png)
And precision-recall curve:
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/emvqhgte8av30aywh7ok.png)

#### Fast version
Here you can see experiments with threshold for fast version. The bold line represents old fast version, the bottom line here is the old slow version of the algorithm:
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/or7tm3f2g8ill22y3auq.png)

Detailed analysis can be seen here:
* [Fast version](https://dev.to/aleksandrgushchin/threshold-experiments-for-scene-change-detector-2hbp)
* [Medium version] (https://dev.to/aleksandrgushchin/august-02-august-03-weekly-status-565a)
* [Slow version](https://dev.to/aleksandrgushchin/august-02-august-03-weekly-status-565a) at the end of the post 

### Speed

| Version |Average FPS on BBC Planet Earth (360x288)|Average FPS on open source videos (1280x720)|
| --- | ---:| ---:|
|Fast version|  234|22|
|Medium version|222|18|
|Slow version|  156|13|


### Overall metric improvement
Here I want to show how I improved metric values in all version from the old ones.
Blue line represent values of algorithm's metric on frames, orange - threshold, gray lines represent if algorithm marked this frame as scene change.
Here is the example of the outcome on one of the videos:
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vhm4qvkq2blgohnvsjmg.png)
The top picture shows original metric values, the bottom one shows metric after improvement.
You can see that the peaks with the scene changes became more distinct, so the threshold is easier to tune.

 

### Unsuccessful ideas
Here is a list of ideas that I implemented, but they turned out to be impractical:
* Slow version with motion vectors
   * Each block is shifted by motion vectors. It slowed down algorithm even more and decreased F score.
* Combining medium version with the slow one
   * The idea was to marked frames as scene change if one of version said so. Again, it slowed down algorithm and did not bring any gain to F score. 
* Separate metric for flashes
   * I implemented a few metrics for flashes detection and deployed them. But ofted flashes occurs several frames in a row and and contains scene change. Because of this it is difficult for algorithm to decide if these flashes contains scene change or not. 


### Possible improvements:
* Threshold 
   * Possible dependency on metric values (maximum value on past frames, mean and std values). Current threshold can perform worse then static threshold in some cases. The example is on the picture. It can be seen that threshold varies around the same value. If it took into account the mean value of past frames, for example, it would be more accurate:
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/lpm4raohfs4jfo30w87n.png)
* Version based on edge detection
   * It can be useful to take into accound another feature of frames - object edges. Combining with existing versions it can boost F score
* Metric
   * Adjusting metric values according to nearest values. For example, by substructing the mean value of surrounding frames. 
* Block-based metric improvement
   * It may be useful to experiment with the blocks individually rather than just taking the mean value of all them all. For example, if difference between _k_ blocks is near zero algorithm should'n mark this frame as scene change no matter what other blocks has. Or if _k_ blocks have difference about maximum of possible value algorithm mark this frame as scene change no matter what other blocks has.
* Dowsampling for medium and slow versions:
   * For videos with high resolution it may be considered to dowsample them to HD or so. This will significantly increase the speed, but will have a small impact on F score.