Projet final: Stabilisation de vidéo

- Détermination d'une trajectoire optimale -

par Olivier Duguay

GIF-4105/7105 Photographie Algorithmique, Hiver 2015

1-Contexte 2-Objectifs 3-Approche 4-Limitations 5-Améliorations 6-Paramètres Matlab

1-Contexte

Pas toujours idéal!
Pas toujours idéal!
De nos jours, l'utilisation de caméra est quasi omniprésente, car, presque tout le monde en ont une dans les poches ou à porter de la main. De plus en plus de gens utilisent leur caméra sur leur téléphone intelligent pour filmer toute sorte de vidéo, cependant, la qualité du résultat n'est pas toujours bonne. Bien souvent les vidéos prises à la première personne (du genre des vidéos «GoPro») ou prises sans le moindre stabilisateur par monsieur Tout-le-Monde avec son cellulaire qui se filme en jouant au soccer par exemple, ne donne pas un vidéo agréable à regarder. Par agréable, on veut dire le fait que la vidéo soit stable et fasse bien le suivi de la zone d'intérêt du vidéo. Bien que la stabilisation optique parvient à filtrer les hautes fréquences, celle-ci ne parvient pas toujours à adoucir les effets de distorsions basses fréquences engendrés par une personne qui marche avec la caméra en main. Pour effectuer la stabilisation, nous avons tenté de reproduire les résultats d'un article traitant de ce sujet et écrit par Matthias Grundmann, Vivek Kwatra et Irfan Essa en collaboration avec Google Research et la Georgia Institut of Technology.

L'article en question peut être retrouvé ICI !.

2-Objectifs

Les objectifs du projet de stabilisation de vidéo sont somme toute assez simples à expliquer, mais beaucoup plus durs à implémenter. Il faut au final, recréer une vidéo plus stable que l'originale en minimisant les accélérations soudaines et autres distorsions. Le rendu final doit avoir l'allure d'un film tourné à l'aide d'un chariot et d'une caméra stable comme on le fait au cinéma. L'algorithme doit pouvoir être utilisé après que la vidéo soit tournée, on ne fait donc par de traitement en direct (live), mais bien du «post-process video stabilization». Finalement on peut ajouter quelques méthodes de tracking d'objets afin de rendre l'algorithme plus stable et de bien recentré le vidéo final, par exemple, en utilisant un détecteur de visage on peut s'assurer que la vidéo soit le plus possible focalisée sur ce visage par exemple.

3-Approche

La stabilisation peut se résumer en 3 grandes étapes, soient ;

1) L'estimation de la trajectoire (possiblement instable) de la caméra (en utilisant le vidéo source)

2) L'estimation d'une nouvelle trajectoire de caméra optimale (plus stable)

3) Reconstruction d'une nouvelle vidéo en utilisant l'estimation de la trajectoire la plus stable, un tracking de zones intéressant (visage, voiture, ballon, etc.) ainsi que le redimensionnement du vidéo (cropping)

Étape 1 - Estimation de la trajectoire initiale

Détection Traquage
Détection Traquage


Pour effectuer l'estimation de la trajectoire prise par la caméra, l'algorithme de «traquage» de points de Kanade, Lucas et Tomasi à été utilisé. Il est plus communément appelé Kanade-Lucas-Tomasi (KLT) feature tracker. L'utilisation de cet algorithme permet de déterminer pour des points d'intérêts P1(x,y) d'une image I1, les points d'intérêt P2(x,y) correspondants dans une image I2 (dans ce cas, l'image suivante dans le vidéo). On aura donc des paires de correspondances que l'algorithme pourra traquer sur toutes les images.

On doit d'abord déterminer des points d'intérêts dans l'image initiale et leur choix est important, car en choisissant mal ceux-ci, les résultats peuvent être plus ou moins bons. En effet, il est difficile de faire la correspondance d'un pixel noir parmi un arrière-plan noir donc, il faut utiliser des points qui sont plus facilement discernables. Pour ce faire, il existe de nombreux algorithmes de détection de points importants (tels des coins, des variations de couleurs importantes, gradient élevé, etc.), mais chacun d'eux fourni des résultats différents qui font en sorte que les rendus finaux sont meilleurs avec certains algorithmes que d'autre. Dans le cadre de ce projet, 3 algorithmes ont été testés, soit :
KLT Pyramide
Pyramide de l'algoritme KLT

1) L'algorithme de détection de points/coins de Harris

2) L'algorithme de valeurs propres minimale (Min Eigenvalue)

3) L'algorithme de détection de caractérisques FAST (Feature from Accelerated Segment Test)


La détection des points doit être bien fait pour de bons résultats, et il est une bonne chose de déterminer la robustesse des points utilisés (ne prendre que les meilleurs), la quantité de ceux-ci, car s'il sont trop nombreux, cela peut ralentir quelque peu le processus de stabilisation. De plus en déterminant une zone limite dans laquelle peuvent se trouver les points, on fait en sorte de bien faire le suivi d'un objet qui nous intéresse dans le vidéo afin de bien ajuster celui-ci avec l'objet en question.

Cet algorithme est utilisé de manière pyramidale, c'est-à-dire, qu'on effectue le calcul du mouvement des points à plusieurs échelles de redimensionnement d'image (de la plus petite vers la plus grande, soit l'image d'origine). Pour chaque niveaux de redimensionnement, on utilise un facteur d'échelle de 2 et habituellement, de 2-4 niveaux suffisent à l'obtention de bons résultats. Il est aussi important de bien déterminer une résolution (dimension) des blocs qui correspondent aux pixels entourant les points d'intérêt. Ces blocs doivent être ni trop petits, ni trop grands.

BiDirection
Erreur bidirectionnelle
Afin de rendre l'algorithme encore plus robuste, on utilise également l'erreur bidirectionnelle pour s'assurer de la validité de nos points. Cette valeur est déterminée par la distance en pixel qui sépare un point d'intérêt de son emplacement original de son emplacement après un traquage inverse. On détermine donc une erreur maximale entre 0 et 3 pixels se qui nous assure une bonne robustesse.

Avec ces points qui ont été traqués, il est possible, à l'aide de leurs coordonnées de trouver un système d'équations linéaires correspondants aux mouvements des points. En effet, à l'aide de ces équations il est aisé de retrouver les transformations qui ont permis de retrouver les différents points d'intérêts d'une image dans une seconde image. Ces transformations affines ou projectives (incluant donc les phénomènes de rotation, translation et facteur d'échelle) permetterons entre autres à reconstituer la trajectoire optimale de la caméra. Puisque nous sommes en présence d'une multitude (ce n'est pas toujours le cas !!!) de points, il faut donc faire le tri des meilleures options de transformations et pour se faire, nous avons fait l'utilisation de la méthode itérative MSAC (M-Estimator Sample Consensus), semblable à la technique dite RANSAC. Finalement, avec ces transformations déterminées il est possible d'approximer le mouvement de la caméra.

Afin de bien faire le suivi des points, il est impératif de redéterminer des nouveaux points d'intérêts après quelques images, puisque du début à la fin du vidéo, les points d'intérêts risquent de se «perdent» et nous ne voulons pas faire de la reconstitution de scène qui serait trop lourde et ralentirait le processus de stabilisation. On recalcule ainsi un nouveau système d'équations linéaires et ainsi de suite.

Finalement, avec ces transformations déterminées il est possible d'approximer le mouvement de la caméra et d'affirmer que cet algorithme KLT robuste permet une bonne rejection des «outliers» (données aberrantes) entre des paires de points et est moins dispendieux en terme de temps de calcul que l'utilisation de la technique dite «Structure from Motion».

FAST Velocity
Points d'intérêts détectés (algorithme FAST) Détection de la vélocité des mouvements

FAST Velocity
Mouvement en X et Y (caméra GoPro) Mouvement en X et Y (caméra standard)

Il est possible de remarquer que la stabilisation d'optique de la caméra GoPro Hero4 est nettement supérieure à celle des caméras standards, car on peut voir que les effets de hautes fréquences sont beaucoup plus atténués. Pour plus de détails, voir l'article de Tomasi (Good Feature to Track).

Étape 2 - Estimation de la trajectoire optimale

Decalage
Transformation et décalage entre 2 images
Pour estimer la trajectoire optimale que devrait prendre la caméra, on utilise les transformations obtenues précédemment pour déterminer la plus petite déformation entre 2 images. Cette déformation doit être minimale, mais optimale. Il faut s'assurer que l'image transformée est comprise dans le chemin optimal, et ce, pour un bon pourcentage de l'image, car on ne veut pas trop réduire notre vidéo finale lors de la reconstruction.

Afin de minimiser la transformation des images, il faut se fier aux transformations de l'image précédente et suivante auquel on leur associe un poids afin de créer un mélange des 3 transformations. On trouve ainsi une image la moins déformée possible, mais qui correspond le plus à l'image précédente. Généralement on donne un poids plus élevé à l'image suivante qu'à l'image précédente.

Une autre bonne habitude est d'utiliser des points de «tracking» à inclure en tout temps dans le calcul (s'il sont dans l'image bien sûr, et d'y associer une plus grande robustesse).Il existe d'autre technique à employer qui permet d'obtenir de meilleurs, mais il n'ont pas toutes été implémentées. L'algorithme du «Robust Optimal L1 Path» et toutes ses subtilités est bien décrit dans l'article dont ce projet est basé.

Path Blend
Estimation trajectoire optimale Transformations entre les images

Ici, on à donc nos systèmes d'équations linéaires (G), nos transformations (W) et les différences/décalage (R) entres les images transformées.

Étape 3 - Reconstitution du vidéo

Pour reconstruire le vidéo, on effectue un recadrage des images qui correspondent à la trajectoire optimale. Le recadrage doit faire en sorte de conserver la plus grande portion d'image possible comme nous n'utiliserons pas de reconstruction d'images. On détermine donc la plus grande fenêtre valide et il est même mieux de la mettre encore plus petit bien que nous perdons ainsi de l'information, mais on gagne en stabilité d'image.

moy moycorr moycorr
Mouvement moyen (sur 120 images) Mouvement moyen CORRIGÉ (sur 120 images) Fenêtrage optimal

moyS moycorrS
Mouvement moyen (sur 180 images) Mouvement moyen CORRIGÉ (sur 180 images)


Comme on peut le remarquer, pour le vidéo sur 180 prises avec une caméra standard (clip provenant de ce VIDEO!), il est difficile de déterminer un très bon chemin étant donné que le vidéo est EXTRÊMEMENT instable, un peu flou et donc la détection et le tracking de points à du mal à bien performé. Si on cherche des points robustes, on en trouve pas assez et ceux disponibles ne nous donnent pas de bonnes informations. Toutefois, on peut remarquer une plus grande stabilité de l'image avec notre algorithme. Pour les résultats avec la GoPro Hero4, il sont assez concluants. On remarque que mon pied à bouger rapide à plusieurs reprise, mais ce n'est pas cela qui rendrait le vidéo désagréable, c'est plutôt l'effet de vibration engendré par le longboard qui crée des distorsions de hautes et basses fréquences et qui font en sorte que le paysage semble flou. Avec notre algorithme on stabilise nettement l'image au cours du vidéo comme on peut le remarquer par les fenêtres du bâtiment et l'automobile blanche qui semblent beaucoup plus distinctes.

4-Limitations

Voici une énumération de quelques limitations de cette technique de stabilisation :

1) Ne fonctionne pas bien pour des vidéos trop flous

2) À du mal avec les mouvements trop brusques qui créer des transformations trop prononcées

3) À du mal à bien fonctionner s'il manque d'objets distincts dans la scène

4) Il faut constamment gérer la perte des points de repères

5-Améliorations

Voici une énumération de quelques améliorations au projet:

1) Pousser plus loin (plus de contraintes de détection) l'algorithme d'optimation du chemin. On pourrait y inclure des points fixes, un face-tracking et limité les transformations de mise à l'échelle, etc.

2) Faire le recadrage de manière dynamique (à chaque fois qu'on crée l'image déformée)

3) Utiliser la reconstitution d'image pour éviter le recadrage

4) Faire la fusion d'image avec une plus grande plage d'images

5) Avoir un rendu vidéo final :( !

6-Paramètres Matlab

select zone algo
Sélection d'image Détermination de zone Algorithme à utiliser

nbpts moycorr param
Nombre de points à traquer Qualité de détection Paramètres de l'algorithme KLT