Comment reconstruire les pixels mélangés d'un fichier vidéo?

8

Supposons que vous ayez un fichier vidéo dont l'ordre des pixels a été mélangé une fois. Autrement dit, un ordre aléatoire a été défini une fois et appliqué à toutes les trames.

Existe-t-il une approche connue pour récupérer l'ordre initial des pixels?

J'ai quelques idées pour récupérer la topologie initiale en plaçant des pixels dont les valeurs sont corrélées dans l'espace et le temps plus près les unes des autres. Je me demande si cela a été étudié et si des algorithmes efficaces ont été publiés.

Ce problème peut également être considéré comme un moyen de projeter sur une matrice 2D un ensemble de valeurs variant dans le temps afin de pouvoir appliquer des techniques de vision par ordinateur (comme CNN), en supposant que ces valeurs sont en effet en quelque sorte corrélées.

Denis Dollfus
la source
1
Cela semble être un problème de jouet ou un défi de piratage? Au moins, cela ne semble pas lié au cryptage vidéo du monde réel, car il serait terrible pour la bande passante et peu sécurisé, tandis que le cryptage du flux d'octets en utilisant, par exemple, AES est rapide et fiable. Je suppose qu'une question immédiate est: avez-vous des données réelles et un problème à résoudre, ou demandez-vous dans l'abstrait, simplement par intérêt?
Neil Slater
À droite, les applications potentielles ne sont pas liées au déchiffrement / piratage, mais visent vraiment à appliquer des techniques de vision par ordinateur à n'importe quel domaine où les données ne sont pas organisées en images ... en organisant les données comme images de toute façon. Donc, si le problème des jouets peut être résolu sur les vidéos, je pense qu'il pourrait avoir des développements intéressants appliqués aux données 2D non natives.
Denis Dollfus
Cela semble intéressant, bien que je pense beaucoup dans une sorte de "l'essayer et voir si cela fonctionne, trouver une théorie plus tard". Il n'y a aucune raison dans mon esprit de soupçonner que la corrélation entre les caractéristiques d'un ensemble de données arbitraires devrait permettre la construction d'un graphique de type grille. Bien que pour les ensembles de données où il l'a fait, je peux voir le raisonnement où il pourrait être utile d'utiliser l'analyse d'image sur les données réorganisées. Le fait que quelqu'un ait ou non regardé ce désembrouillage des pixels dépend de son lien avec un problème utile ou intéressant - je ne peux pas y penser, mais je ne suis pas un chercheur. . .
Neil Slater
Je viens de rencontrer un problème similaire mais dans un contexte différent: dsp.stackexchange.com/questions/59808/…
Dilawar

Réponses:

3

Il s'agit d'un fascinant problème combinatoire. Je présenterais chaque pixel en utilisant sa trajectoire temporelle complète, puis je les intégrerais dans une grille en utilisant les k voisins les plus proches. Le véritable objectif est de maximiser la probabilité que la vidéo soit une séquence d'images naturelles (de la vie réelle), que vous pouvez tester avec un classificateur, mais vous pourrez peut-être vous en tirer avec un coût de finesse; disons, la somme des différences entre les pixels adjacents. Une fois que vous avez commencé à remplir la grille, les contraintes de lissage réduiront l'espace de recherche (puisqu'un pixel devra être proche de plusieurs autres pixels), accélérant ainsi les choses, en supposant que vous utilisez une structure de données efficace pour interroger les voisins les plus proches; voir par exemple http://www.itu.dk/people/pagh/SSS/ann-benchmarks/

Emre
la source
4

Il n'existe pas de solution générale à ce problème, même si nous ajoutons quelques hypothèses sur la distribution, par exemple, des couleurs et des formes dans les images ou le couplage temporel tel que des images consécutives similaires.

Problème

Laisser F1,,Fje Soit le n cadres originaux, chacun avec mpixels. LaisserPêtre la permutation qui est appliquée aux pixels de chaque image avant de les obtenir. Vous pouvez penserP comme le livre de codes de l'ennemi.

Maintenant, comme entrée que nous recevons P(F1),,P(Fn). Le but est de trouver la permutation inverseQpour restaurer les images. DoncQP=je est la carte d'identité et par exemple Q(P(F1))=F1. Notez que nous ne connaissons aucun des bons cadresFje.

Laisser Q1,...,Qm! Soit le m! fonctions de permutation possibles du m pixels.

Le but est de sélectionner l'unique j{1,,m!} pour que QjP=je.

Pas de solution générale

Dans notre modèle statistique, cela signifie sélectionner le Qj ce qui maximise la probabilité que Qj(P(Fje)) est tiré de la même distribution que les statistiques de référence pour les images et les statistiques temporelles entre les trames consécutives Qj(P(Fje) et Qj(P(Fje+1) qui est notre connaissance préalable.

Il y a un contre-exemple canonique où l'ennemi vous donne un film brouillé avec deux images où tous les pixels sont de la même couleur, doncn=2, F1=F2 et Qj(F1)=Qj(F2)=F1=F2 pour chaque j. Ainsi, pour tousj, les statistiques intra-trame et inter-trames sont équiprobables pour chaque j et ne nous donne aucune information pour sélectionner la permutation de vraisemblance maximale Qj (sauf dans le cas dégénéré où m!=1).

Ainsi, nous ne pouvons garantir l'unicité et le problème est insoluble sans autres hypothèses.

Autres hypothèses

Il est intéressant de voir si nous pouvons résoudre le problème en ajoutant plus de contraintes.

Si nous limitons l'ennemi à ne nous envoyer que des "vrais" films et en supposant qu'il y a suffisamment de pixels et d'images différents pour Qj avec une probabilité maximale existe, nous aurions encore à calculer des statistiques pour O(m!×n) images permutées pour trouver le maximum.

C'est une rupture de code par force brute.

Afin de bénéficier des réseaux de neurones, et en particulier de la rétropropagation, nous aurions besoin d'une fonction de perte différenciable par rapport à l'entrée (qui est un codage de j ou notre permutation Qj). La question serait alors de voir si une telle fonction peut être trouvée.

Sinon, le problème est plus similaire à la cryptanalyse dans le cas spécial où nous savons que le livre de code de l'ennemi est une permutation du texte clair (ou image claire).

mjul
la source
La mention de l'ennemi m'a fait me demander si l'on pouvait forger un film brouillé qui aurait deux solutions qui ressembleraient toutes deux à de vrais films.
Denis Dollfus
C'est le cœur du problème auquel je suis confronté en ce moment: dsp.stackexchange.com/questions/59808/… . Bien que je puisse supposer que l'activité (dans la vidéo liée à ce post) est de rechange et groupée.
Dilawar