FindSimilarity - Trouver les différences entre plusieurs vidéos
Introduction
Bonjour,
Je souhaite vous présenter une petite expérience que je viens d'écrire.
Cela fait plusieurs années que je souhaitais m'amuser sur la librairie OpenCV mais sans jamais en avoir eu l'utilité. J'ai profité d'avoir un peu de temps libre, pour écrire un petit programme dont le but est de comparer un ensemble de vidéos.
Le but est ensuite de dire si dans cet ensemble de vidéos, deux vidéos sont identiques, ou se ressemblent, ou sont trop éloignées.
J'ai souhaité faire cette expérience par amusement, je n'ai donc pas passé beaucoup de temps sur la qualité du code écrit. Ce dernier aurait pu être mieux découpé, posséder des commentaires, des tests unitaires, ... . Si vous voulez utiliser ce code pour un véritable usage production, n'hésitez pas à améliorer celui ci.
Vous pouvez trouver le code source de cette expérience à l'adresse suivante : https://gogs.shadoware.org/ShadowareOrg/find-similarity.
Le jeux de données
J'ai pris plusieurs films en DVD que je possède. Possédant un NAS, et une chromecast, j'encode ces DVD au format vidéo et je les y dépose. Malheureusement la qualité est dégradée par rapport au DVD.
Pour constituer le jeu de données, je prends ces films encodés, que je dépose dans un dossier. Je copie certains d'entre eux telquel
mkdir example
cd example
cp ../film1.avi film1_copy.aviJ'encode certains de ces films avec une résolution différente :
avconv -i film2.m4v -preset veryslow -s 320x240 film2.320x240.m4v
avconv -i film2.m4v -preset veryslow -s 640x480 film2.640x480.m4vComment fonctionne la comparaison
Avant de parler de la comparaison, parlons des fichiers que nous allons comparer. Le programme va se constituer une liste des fichiers à comparer et pour chaque fichier va lire les informations suivantes :
- la durée du film
- la largeur
- la hauteur
- une miniature du film (utilisée pour comparer à l'oeil les vidéos)
Ensuite, une fois les méta-données récupérées, le programe se constitue une liste de paires de fichiers à comparer en sélectionnant les fichiers qui ont une durée identique à +/- 5
secondes. Ce paramètre est modifiable au niveau de la constante DELTA_SEC.
Enfin vient la comparaison pour laquelle je me suis simplement basé sur les exemples du site OpenCV que vous pouvez trouver dans la rubrique Video Input with OpenCV and similarity measurement.
J'ai utilisé l'algorithme PSNR (Peak signal-to-noise ratio) pour déterminer si les deux images de la vidéos sont plutôt proches ou éloignées. Cet algorithme calcul la distorsion entre deux images. Il est principalement utilisé pour quantifier la performance réalisée par un encodeur lors de la compression d'une vidéo. Une valeur entre 30 et 50 signifie que les images sont relativement proches. Plus la valeur est haute, et plus la qualité d'image est conservée entre les deux images. Si la valeur est inférieure à 30 on peut estimer qu'il y a une forte chance pour que les images soit différentes.
Vous pouvez retrouver les formules utilisées par le calcul sur le site d'OpenCV ou sur la page Wikipedia. Est-ce que ce calcul est le meilleur pour trouver les images similaires ? Je ne sais pas. Si vous avez d'autres propositions, on peut les tester.
Sur une vidéo on a une multitude d'images (sur un film d'une heure et demie à 25 images secondes, nous en avons 135 000), on pourrait comparer chaque image de la vidéo pour se faire une moyenne, de mon coté j'ai préféré comparer une image au milieu de la vidéo afin de parcourir plus vite les vidéos.
De la même manière pour m'abstraire de la taille de la vidéo qui peut avoir été modififée, je redimensionne, à tort ou à raison, les deux images à une taille identique (arbitrairement: 160x120).
Je vous présente donc ci-dessous l'algorithme que vous pouvez retrouver sur le site d'OpenCV. J'ai légèrement modifié l'algorithme pour redimensionner les images ainsi que pour retourner une valeur de PSNR infiniment grande quand deux vidéos sont identiques.
double getPSNR(const cv::Mat& F1, const cv::Mat& F2) {
cv::Mat I1, I2;
cv::resize(F1, I1, cv::Size(160, 120));
cv::resize(F2, I2, cv::Size(160, 120));
cv::Mat s1;
cv::absdiff(I1, I2, s1); // |I1 - I2|
s1.convertTo(s1, CV_32F); // cannot make a square on 8 bits
s1 = s1.mul(s1); // |I1 - I2|^2
cv::Scalar s = sum(s1); // sum elements per channel
double sse = s.val[0] + s.val[1] + s.val[2]; // sum channels
if( sse <= 1e-10) { // for small values return zero
return std::numeric_limits<double>::infinity();
} else {
double mse = sse / (double)(I1.channels() * I1.total());
double psnr = 10.0 * log10((255 * 255) / mse);
return psnr;
}Optimisation
La raison qui fait que je voulais m'amuser avec OpenCV c'est qu'il permet de faire ces calculs à l'aide du GPU au lieu du CPU.
L'utilisation du GPU permet d'améliorer la vitesse de calcul pour tout ce qui est traitement d'image, ce pour quoi un GPU est prévu pour. Pour plus d'informations sur l'utilisation du GPU dans OpenCV peut être trouvé sur la page CUDA d'OpenCV.
Le problème est que sur la version de Debian jessie que j'utilise, OpenCV n'est pas compilé avec CUDA, et ne permet donc pas d'utiliser le GPU. J'ai donc dû compiler ma propre version d'OpenCV.
Pour cela la première étape consiste à récupérer le code source et à se positionner sur la branche que l'on souhaite compiler. Pour ma part je préfère compiler sur la branche 2.4, plus proche de la version de Debian.
git clone https://github.com/opencv/opencv.git
git checkout 2.4Viens ensuite la compilation :
mkdir build
cd build
cmake -D CMAKE_BUILD_TYPE=RELEASE -D CMAKE_INSTALL_PREFIX=/home/phoenix/usr/local -DENABLE_SSE=ON -DENABLE_SSE2=ON -DENABLE_SSE3=ON -DWITH_TBB=ON -DWITH_1394=ON -DWITH_V4L=ON -DWITH_OPENGL=ON -DWITH_GTK=ON -DWITH_JASPER=ON -DWITH_JPEG=ON -DWITH_PNG=ON -DWITH_TIFF=ON -DWITH_OPENEXR=ON -DWITH_PVAPI=ON -DWITH_EIGEN=ON -DCMAKE_SKIP_RPATH=ON -D WITH_CUDA=ON -D ENABLE_FAST_MATH=1 -D CUDA_FAST_MATH=1 -D WITH_CUBLAS=1 -DWITH_IPP=ON -D CUDA_GENERATION=Auto -D WITH_FFMPEG=ON ../J'active lors de la compilation le maximum d'optimisation dont CUDA. J'active également FFMPEG sans lequel le nombre de fichier reconnu baisse énormément sur ma machine. Après avoir lancé cmake j'obtiens le résultat suivant :
-- General configuration for OpenCV 2.4.13.1 =====================================
-- Version control: 2.4.13.1-48-gac118ae
--
-- Platform:
-- Host: Linux 3.16.0-4-amd64 x86_64
-- CMake: 3.6.2
-- CMake generator: Unix Makefiles
-- CMake build tool: /usr/bin/make
-- Configuration: RELEASE
--
-- C/C++:
-- Built as dynamic libs?: YES
-- C++ Compiler: /usr/bin/c++ (ver 4.9.2)
-- C++ flags (Release): -fsigned-char -W -Wall -Werror=return-type -Werror=address -Werror=sequence-point -Wformat -Werror=format-security -Wmissing-declarations -Wundef -Winit-self -Wpointer-arith -Wshadow -Wsign-promo -Wno-narrowing -Wno-delete-non-virtual-dtor -Wno-comment -Wno-array-bounds -Wno-aggressive-loop-optimizations -fdiagnostics-show-option -Wno-long-long -pthread -fomit-frame-pointer -ffast-math -msse -msse2 -msse3 -ffunction-sections -O3 -DNDEBUG -DNDEBUG
-- C++ flags (Debug): -fsigned-char -W -Wall -Werror=return-type -Werror=address -Werror=sequence-point -Wformat -Werror=format-security -Wmissing-declarations -Wundef -Winit-self -Wpointer-arith -Wshadow -Wsign-promo -Wno-narrowing -Wno-delete-non-virtual-dtor -Wno-comment -Wno-array-bounds -Wno-aggressive-loop-optimizations -fdiagnostics-show-option -Wno-long-long -pthread -fomit-frame-pointer -ffast-math -msse -msse2 -msse3 -ffunction-sections -g -O0 -DDEBUG -D_DEBUG
-- C Compiler: /usr/bin/cc
-- C flags (Release): -fsigned-char -W -Wall -Werror=return-type -Werror=address -Werror=sequence-point -Wformat -Werror=format-security -Wmissing-declarations -Wmissing-prototypes -Wstrict-prototypes -Wundef -Winit-self -Wpointer-arith -Wshadow -Wno-narrowing -Wno-comment -Wno-array-bounds -Wno-aggressive-loop-optimizations -fdiagnostics-show-option -Wno-long-long -pthread -fomit-frame-pointer -ffast-math -msse -msse2 -msse3 -ffunction-sections -O3 -DNDEBUG -DNDEBUG
-- C flags (Debug): -fsigned-char -W -Wall -Werror=return-type -Werror=address -Werror=sequence-point -Wformat -Werror=format-security -Wmissing-declarations -Wmissing-prototypes -Wstrict-prototypes -Wundef -Winit-self -Wpointer-arith -Wshadow -Wno-narrowing -Wno-comment -Wno-array-bounds -Wno-aggressive-loop-optimizations -fdiagnostics-show-option -Wno-long-long -pthread -fomit-frame-pointer -ffast-math -msse -msse2 -msse3 -ffunction-sections -g -O0 -DDEBUG -D_DEBUG
-- Linker flags (Release):
-- Linker flags (Debug):
-- ccache: NO
-- Precompiled headers: YES
--
-- OpenCV modules:
-- To be built: core flann imgproc highgui features2d calib3d ml video legacy objdetect photo gpu ocl nonfree contrib java python stitching superres ts videostab
-- Disabled: world
-- Disabled by dependency: -
-- Unavailable: androidcamera dynamicuda viz
--
-- GUI:
-- QT: NO
-- GTK+ 2.x: YES (ver 2.24.25)
-- GThread : YES (ver 2.42.1)
-- GtkGlExt: NO
-- OpenGL support: NO
-- VTK support: NO
--
-- Media I/O:
-- ZLib: /usr/lib/x86_64-linux-gnu/libz.so (ver 1.2.8)
-- JPEG: /usr/lib/x86_64-linux-gnu/libjpeg.so (ver )
-- PNG: /usr/lib/x86_64-linux-gnu/libpng.so (ver 1.2.50)
-- TIFF: /usr/lib/x86_64-linux-gnu/libtiff.so (ver 42 - 4.0.3)
-- JPEG 2000: /usr/lib/x86_64-linux-gnu/libjasper.so (ver 1.900.1)
-- OpenEXR: /usr/lib/x86_64-linux-gnu/libImath.so /usr/lib/x86_64-linux-gnu/libIlmImf.so /usr/lib/x86_64-linux-gnu/libIex.so /usr/lib/x86_64-linux-gnu/libHalf.so /usr/lib/x86_64-linux-gnu/libIlmThread.so (ver 1.6.1)
--
-- Video I/O:
-- DC1394 1.x: NO
-- DC1394 2.x: YES (ver 2.2.3)
-- FFMPEG: YES
-- codec: YES (ver 56.1.0)
-- format: YES (ver 56.1.0)
-- util: YES (ver 54.3.0)
-- swscale: YES (ver 3.0.0)
-- resample: YES (ver 2.1.0)
-- gentoo-style: YES
-- GStreamer: NO
-- OpenNI: NO
-- OpenNI PrimeSensor Modules: NO
-- PvAPI: NO
-- GigEVisionSDK: NO
-- UniCap: NO
-- UniCap ucil: NO
-- V4L/V4L2: NO/YES
-- XIMEA: NO
-- Xine: NO
--
-- Other third-party libraries:
-- Use IPP: IPP not found
-- Use Eigen: NO
-- Use TBB: NO
-- Use OpenMP: NO
-- Use GCD NO
-- Use Concurrency NO
-- Use C=: NO
-- Use Cuda: YES (ver 7.5)
-- Use OpenCL: YES
--
-- NVIDIA CUDA
-- Use CUFFT: YES
-- Use CUBLAS: YES
-- USE NVCUVID: NO
-- NVIDIA GPU arch: 21
-- NVIDIA PTX archs:
-- Use fast math: YES
-- Tiny gpu module: NO
--
-- OpenCL:
-- Version: dynamic
-- Include path: /home/phoenix/Developpement/ExternalSoftware/opencv/3rdparty/include/opencl/1.2
-- Use AMD FFT: NO
-- Use AMD BLAS: NO
--
-- Python:
-- Interpreter: /usr/bin/python2 (ver 2.7.10)
-- Libraries: /usr/lib/x86_64-linux-gnu/libpython2.7.so (ver 2.7.10rc1)
-- numpy: /usr/lib/python2.7/dist-packages/numpy/core/include (ver 1.8.2)
-- packages path: lib/python2.7/dist-packages
--
-- Java:
-- ant: /usr/bin/ant (ver 1.9.4)
-- JNI: /usr/lib/jvm/java-7-openjdk-amd64/include /usr/lib/jvm/java-7-openjdk-amd64/include /usr/lib/jvm/java-7-openjdk-amd64/include
-- Java tests: YES
--
-- Documentation:
-- Build Documentation: NO
-- Sphinx: NO
-- PdfLaTeX compiler: /usr/bin/pdflatex
-- Doxygen: YES (/usr/bin/doxygen)
--
-- Tests and samples:
-- Tests: YES
-- Performance tests: YES
-- C/C++ Examples: NO
--
-- Install path: /home/phoenix/usr/local
--
-- cvconfig.h is in: /home/phoenix/Developpement/ExternalSoftware/opencv/build
-- -----------------------------------------------------------------Pour que la compilation se déroule sans problème, il vous faudra installer certains paquets sur votre distribution. Sur Debian Jessie, j'ai installé nvidia-cuda-toolkit en
version 7.5.18-4~bpo8+1. Comme vous pouvez les voir c'est une version qui provient du repository de backports. La version 6.0.37-5 ne me permettait pas d'activer CUDA. J'ai
donc du monter l'ensemble du driver propriétaire sur mon poste de développement.
Rasssurez-vous, si vous ne voulez pas utiliser les backports ou ne pas utiliser de driver propriétaire, vous pouvez tester le programme dans sa version CPU. :)
Voici comment le code a été ré-écrit pour utiliser le GPU à la place du CPU:
struct BufferPSNR { // Optimized GPU versions
// Data allocations are very expensive on GPU. Use a buffer to solve: allocate once reuse later.
cv::gpu::GpuMat gF1, gF2, gI1, gI2, gs, t1,t2;
cv::gpu::GpuMat buf;
};
double getPSNR_GPU_optimized(const cv::Mat& F1, const cv::Mat& F2, BufferPSNR& b) {
b.gF1.upload(F1);
b.gF2.upload(F2);
cv::gpu::resize(b.gF1, b.gI1, cv::Size(160, 120));
cv::gpu::resize(b.gF2, b.gI2, cv::Size(160, 120));
b.gI1.convertTo(b.t1, CV_32F);
b.gI2.convertTo(b.t2, CV_32F);
cv::gpu::absdiff(b.t1.reshape(1), b.t2.reshape(1), b.gs);
cv::gpu::multiply(b.gs, b.gs, b.gs);
double sse = cv::gpu::sum(b.gs, b.buf)[0];
if( sse <= 1e-10) // for small values return zero
return std::numeric_limits<double>::infinity();
else {
double mse = sse /(double)(F1.channels() * F1.total());
double psnr = 10.0*log10((255*255)/mse);
return psnr;
}
}L'utilisation de la structure BufferPSNR permet de ne pas perdre de performance lors de l'initialisation relativement lourde des objets GpuMat. Sans cela, l'utilisation du Gpu
serait moins performant que la version Cpu.
L'expérience
Maintenant place à l'expérience. Nous allons lancer notre programme sur notre jeu d'essai comprenant les vidéos issue des DVD, ainsi que les vidéos recompressées pour l'expérience. Si l'expérence se déroule bien l'algorithme devrait nous detecter les fichiers dupliqués, ainsi que les fichiers recompressés.
Lancement et selection des dossiers
La première étape est la sélection des dossiers que l'on souhaite comparer. Le programme ira lire récursivement l'ensemble des dossiers pour y trouver l'ensemble des fichiers vidéos.
La sélection d'un projet provient de mon envie de départ de pouvoir enregistrer l'avancement du projet au fur et à mesure. Cette étape n'a pas été réalisée mais l'existance du mode projet existe toujours.
Une fois le dossier projet choisi, il faut sélectionner la liste des dossiers contenant les vidéos et lancer le programme ...
Comparaison des vidéos
Dans cette étape le programme compare l'ensemble des vidéos présentes dans les dossiers. L'ensemble du processus tourne dans des threads afin de ne pas figer l'IHM, grâce à l'API
QtConcurrent.
Les étapes de la recherche sont donc :
- Constitution de la liste des fichiers
- Récupération des méta-données
- Création de la liste des paires de fichiers (en filtrant sur la durée)
- Calcul du PSNR pour chaque paire de fichiers
- Filtrage pour ne garder que les paires de fichiers dont le PSNR est supérieur à 30 db.
Lors de mon développement je me suis basé sur l'API QtConcurrent pour faire les différentes étapes. Faisant beaucoup de développement NodeJS ces derniers temps je suis habitué à
l'utilisation des promesses et de leur enchainement pour faire des processus complexes. J'ai trouvé dommage de ne pas retrouver la même chose dans l'API QtConcurrent. Pour
reproduire un équivalent, lorsqu'un QFuturese termine, le signal émis par QFutureWatcher est récupérer par un SLOT du moteur qui s'occupe de lancer l'étape suivante.
La page de résultat
La page de résultat liste les vidéos considérées identiques suite à l'étude d'une des images. Un coup d'oeil visuel permet alors de se faire un avis sur la question, et de supprimer la vidéo que l'on souhaite.
Comme on peut le voir le programme retrouve les vidéos dont l'image est identique, ainsi que les films qui ont été redimensionnés sans trop de soucis. Le problème se situe alors au niveau du bruit qui est généré. Plusieurs films sont considérés comme proches alors que complètement différents. Pour régler ce problème, comparer plusieurs images d'une même vidéo à des timestamps différents pourrait peut-être régler le problème.
Je vous conseille de vérifier manuellement la qualité et la similarité de chaque vidéo manuellement avant toute suppression.
Conclusion
En conclusion, j'ai trouvé l'expérience intéressante, et maintenant qu'elle est terminée, je vais pouvoir en tenter une autre ;). Est-ce que le programme continuera d'évoluer ? Pourquoi pas ? Cela dépendera des PR (Pull Request) et des demandes faites par les utilisateurs, ainsi que du temps que j'ai envie de passer dessus.
