Empreinte perceptive de vidéos pour le contrôle d'accès

Avez-vous déjà voulu comparer des vidéos sans les regarder ? Détecter un changement, une retouche sans les confondre avec d'éventuelles variations dues au transcodage ? Les fonctions de hashage cryptographiques (MD5, SHA-1, etc.) sont conçus pour générer des empreintes radicalement différentes au moindre changement, et sont donc inadaptés à la comparaison d'image et à fortiori de vidéos, où des images similaires doivent aussi avoir une empreinte similaire.

Fort heureusement, il existe une famille d'algorithmes dits de hashage perceptif, parfois appellés algorithmes de hashage d'image car ils sont essentiellement faits pour comparer deux matrices. Les implémentations ne sont pas égales selon les langages que vous utilisez, mais github.com/JohannesBuchner/imagehash donne une bonne idée de comment sont implémentés les algorithmes les plus connus : ahash, phash, dhash et whash que j'utilise ci-après.

>>> from PIL import Image
>>> import imagehash
>>> hash = imagehash.whash(Image.open('test.png'))
>>> print(hash)
ffff06000000187c

La comparaison de differentes empreintes est permise avec ce genre d'algorithmes. Contrairement à l'égalité stricte utilisée pour les empreintes cryptographiques, les empreintes perceptives ne définissent pas de frontière entre ce qui est similaire et dissimilaire ; la comparaison est donc faite sur la base d'un seuil qu'il nous incombe de définir, souvent sur la base de tests (que je fais d'ailleurs en fin d'article !).

>>> otherhash = imagehash.average_hash(Image.open('other.bmp'))
>>> print(otherhash)
ffff3720200ffff
>>> print(hash == otherhash)
False
>>> print(hash - otherhash) # Hamming distance under the hood
36 # number of bits differing, to be compared with the threshold

Comment interpréter ce résultat ? Tout dépend de la longueur désirée de l'empreinte, mais globalement plus l'image est différente, plus le résultat est élevé.

Des images aux vidéos

Avant de passer au hashage perceptif de vidéos, on peut noter que les algorithmes précédents sont très loin d'être les seuls disponibles. Le domaine scientifique est encore actif au sujet du hashage d'image, étant donné les utilisations potentielles pour la reconnaissance d'images.

Dans la littérature, ce domaine de recherche active est communément appelé Near Duplicate Video Clip Detection (NDVC), et désigne des systèmes capables de déterminer si une vidéo est équivalente ou identique à une autre, souvent en comparant un clip aux empreintes contenues dans une base de données existante de clips (comme ContentId sur YouTube)^[1]. Les algorithmes cherchent en général à être insensibles à plusieurs critères communs d'une manipulation qui, si elle est lègère, ne doit pas impacter trop fortement l'indice de similarité :

• luminosité
• contraste
• gamma
• redimensionnement
• rotation
• bruit
• filtre
• colorimétrie
• compression
• etc.

En plus de ces critères, un système NDVC peut aussi inclure des caractéristiques temporelles pour être capable de détecter et localiser des vidéos au sein d'autres vidéos plus longues. Pour tout vous avouer, je ne suis pas intéressé par tous ces critères, car je cherche juste à savoir si une vidéo fournie est effectivement la même qu'une vidéo supposément transcodée à partir de celle-ci. Je n'ai donc potentiellement à faire qu'à des changements dus à la compression, au changement des frames per seconde et au potentiel changement de codec : espace de couleur et bit depth. Ces critères sont en général assez simples à couvrir et les algorithmes les supportent bien ; toute comparaison d'algorithme se résumera donc essentiellement à sa vitesse et sa robustesse à sélection de frames. Si toutefois vous êtes intéressés par une rétrospective des techniques plus avancées utilisées dans les NVDC utilisés en production, je ne peux que vous recommander Using Perceptual Hash Algorithms to Identify Fragmented and Transformed Video Files, de Ola Kjelsrud^[2], qui résume avec clarté la situation en prenant exemple sur de nombreux systèmes commerciaux existants.

Voyons ce que l'on peut faire pour porter notre réflexion jusque-là centrée sur une image à une vidéo, c'est à dire un ensemble d'image ou frames. Le programme suivant prend en entrée un fichier source (et ses éventuelles variantes) et un fichier auquel le(s) comparer :

import sys
import hashlib
import imagehash
import numpy as np
from moviepy.editor import VideoFileClip
from PIL import Image


def hash_file_crypto(filename, blocksize=2**20):
  m = hashlib.sha256()
  with open(filename, "rb") as f:
      while True:
          buf = f.read(blocksize)
          if not buf:
              break
          m.update(buf)
  return m.hexdigest()


def hash_frame(frame):
  pil_frame = Image.fromarray(np.uint8(frame)).convert('RGB')
  return imagehash.whash(pil_frame, hash_size=16)

def compare_files(
  original_file,
  new_file,
  use_stdout=False,
  fps=1.0, # take one frame per second
  up_to=5 / 100 # up to 5% of hash can be different btw two similar images / anything higher will prove videos to be different
):
  """Perceptual comparison of two videos, with potential resolutions"""
  def hash_values_of(filepath):
    with VideoFileClip(filepath) as clip:
      return [
        hash_frame(f)
        for f in clip.iter_frames(1, dtype=float)
      ]

  if hash_file_crypto(new_file) is hash_file_crypto(original_file):
    sys.exit(0)

  original_file_hashes = hash_values_of(original_file)
  new_file_hashes = hash_values_of(new_file) # even if longer, will have same similarity

  differences = [
    (original_file_hash - new_file_hash) / len(new_file_hashes[0].hash)**2
    for original_file_hash, new_file_hash in zip(original_file_hashes, new_file_hashes)
  ]

  max_differences = [
    d
    for d in sorted(differences)[-int(len(original_file_hashes)/10):]
  ]

  ratio = max_differences and min(max_differences) or 0.0
  print(ratio)

Quel que soit le nombre de frames que l'on collecte, on obtient à la fin une liste (H = \{h_{1}|...|h_{n}\} \) contenant les empreintes de chaque frame prise dans la vidéo, nommé ci-dessus file_hashes ou new_file_hashes.

Quand les empreintes de deux vidéos (H_{1} \) et (H_{2} \) (resp.) sont comparées, chaque empreinte de frame (h_{i1} \) de (H_{1} \) est comparée à la frame correspondante (h_{i2} \) de (H_{2} \). Dans cette version du code, on retient la différence la plus élevée (\max_{\{H_{1} - H_{2}\}} \) pour le comparer au seuil, mais on pourrait retenir un pourcentage de frames au-dessus du seuil comme manière de détecter des vidéos différentes.

Vous pouvez trouver la version complète du code sur git.rigelk.eu/rigelk/pyvideohash.

Et pour les vidéos longues ?

Vous l'avez sûrement deviné, plus une vidéo est longue, plus on a de frames à comparer. Avec de longues vidéos, le coût du hashage de toutes les frames peut vite rendre l’opération très coûteuse à l’échelle. Comme pour un filet de pêche avec des trous plus grands, on pourrait uniquement sélectionner une frame toutes les n secondes, au risque de perdre en précision en échange d'un gain de vitesse substantiel.

Mais que se passe lorsque l'on fait varier n pour obtenir (N \) frames ? Comment estimer la valeur a saisir pour optimiser précision et vitesse ? Si votre but est de faire un système de détection de similarité locales par rapport à une base de données, vous devrez distribuer uniformément votre sélection de frames. Mais notre cas est bien plus simple : la comparaison n'est pas faite avec une empreinte déjà calculée, mais refaite au moment de la comparaison ; la comparaison ne cherche pas à identifier mais à mettre en évidence des différences suffisantes pour rejeter l'identité. On peut alors prendre moins de frames en ignorant les frames similaires dans la vidéo d'origine^[3][4], en les prenant aléatoirement, ou encore en indentifiant les key frames plus représentatives de la vidéo^[5] (résistance au changement de framerate et au transcodage), ou celle représentant une scène^[6] pour chaque scène d'une vidéo (résistance à l'édition temporelle d'une vidéo).

Et pour les vidéos décalées ?

Je ne gère pas cela, ça ne m'intéresse pas dans mon cas d'usage où l'on n'accepte que des vidéos supposées identiques à l'exception de leur transcodage. Toutefois certain·e·s se sont intéressés à la question, et font en général appel à de la reconnaissance de scène pour décaler leur vidéo aux séquences les plus similaires.

Et niveau performances ?

Si comparer deux images est rapide, comparer deux video multiplie ce temps passé autant de fois que de paires d'images sélectionnées. Si vous estimez que 100 points de comparaison sont suffisants, il faudra environ 2 secondes pour comparer deux vidéos de 10 minutes chacune.

Tests contre un dataset spécifique aux NDVC

On teste alors notre algorithme sur le dataset CC_WEB_VIDEO^[7], qui contient des vidéos identiques, similaires, ayant quelques changements, des changements majeurs, étant des versions courtes/longues d'une même source ou étant totalement différentes. C'est un dataset conçu spécifiquement pour tester les NDVC comme le nôtre.

Les tests validés (je vous laisserai le soin de vérifier par vous-même avec un petit bash download_dataset.sh && poetry run pytest), on peut envisager d'utiliser cette technique pour les applications que j'ai évoquées, mais celle qui nous intéresse le plus est le contrôle d'accès. Mais pourquoi au juste ?

Dans une application comme PeerTube, le serveur est le seul apte à transcoder une vidéo. C'est autant une mesure de confort pour le producteur de vidéo et le visiteur que c'est un problème : l'utilisateur n'a pas à faire ni savoir comment faire le transcodage, mais c'est une étape coûteuse en temps machine et toutes les vidéos doivent y passer pour s'assurer de la bonne expérience utilisateur lors de la diffusion. L'impact le plus courant est d'avoir une file d'attente de transcodage pleine, ce qui peut entraîner des jours d'attente avant d'avoir sa vidéo pleinement transcodée dans toutes ses définitions. Évidemment, cela ne nous a pas échappé, mais les solutions potentielles sont difficiles à mettre en place :

• permettre à un administrateur d'ajouter des machines distantes pour aider au transcodage (long à développer)
• permettre à un producteur de vidéo de transcoder lui-même ses vidéos dans les définitions cibles (facile, mais manque de confiance*)

*: Si cette solution peut paraître élégante, elle pose le problème de la vérification des vidéos envoyées par l'utilisateur. Ces vidéos pourraient très bien être différentes, et nécessitent donc une vérification complémentaire par un modérateur que l'on devrait former pour ce travail inhabituel et pour lequel on doit créer une interface de modération spécifique à la comparaison de définitions d'une vidéo.

Pour rappel notre petit algorithme de comparaison de vidéo est résistant à des changements de :

• luminosité
• contraste
• gamma
• redimensionnement
• rotation
• bruit
• filtre
• colorimétrie
• compression
• temporalité
• framerate

Nous voilà donc avec une solution automatique assez fiable pour faire ce travail automatiquement (du moins dans un premier temps) et permettre aux producteurs de vidéos (et plus largement les tiers voulant aider au transcodage) de fournir eux-même les définitions déjà transcodées en même temps que leur vidéo …quand j'aurai le temps de proposer cette fonctionalité au sein de PeerTube (;´д｀).

@article{rigelk20200006,
  title = "Empreinte perceptive de vidéos pour le contrôle d'accès",
  author = "Rigel Kent",
  journal = "http://localhost:8080",
  year = "2020",
  url = "http://localhost:8080/blog/video-similarity/"
}