Recherche de fichiers vidéo en double par la base de données (en millions), les empreintes digitales? La reconnaissance de formes?

Question

Dans le scénario suivant:

J'ai eu un projet ayant un catalogue qui compte actuellement une dizaine de milliers de fichiers vidéo, le nombre va augmenter de façon spectaculaire.

Cependant beaucoup d'entre eux sont des doublons. Avec tous les fichiers vidéo que j'ai associé des informations sémantiques et descriptif que je veux fusionner les doublons pour achive meilleurs résultats pour chacun.

Maintenant, je besoin d'une sorte de procédure où je métadonnées d'index dans une base de données, et chaque fois qu'une nouvelle vidéo entre dans le catalogue les mêmes données sont calculées et en correspondance avec la base de données.

Le problème est les vidéos ne sont pas des copies exactes. Ils peuvent avoir des qualités différentes, sont Amby recadrée, filigrané ou une suite / prequel. Ou sont coupés au début et / ou fin.

Malheureusement, mieux la comparaison plus cpu et de la mémoire, il obtient donc je prévois intensif sur la mise en œuvre de plusieurs couches de comparaison qui commencent par très gracieux, mais comparision rapide (Maby vidéo lengh avec une tolérance de 10%) et se terminent par la comparaison finale qui décide si son vraiment un double (ce serait un vote communautaire).

Alors que j'ai une communauté pour vérifier les résultats, il suffit de fournir des « bonnes » avec des suppositions un faible ratio miss.

Alors maintenant, ma question est ce que les couches peuvent les gars vous pensez ou avez-vous une meilleure approche?

Je ne me soucie pas l'effort pour créer les métadonnées, j'ai assez d'esclaves pour le faire. Juste le comparision devrait être rapide. Donc, si elle aide que je peux convertir 100 fois la vidéo et ...

Voici mes idées actuelles:

• Longueur vidéo (secondes)

• première et dernière analyse d'image des images

Je rééchantillonner l'image à une taille miniature et obtenir les valeurs rgb moyennes alors pixel serialize par pixel si la couleur à ce pixel est supérieure / inférieure à la moyenne représentée par 0 ou 1. Je reçois une chaîne binaire que je peut stocker dans mysql et faire un booléen somme de bits (soutenu par mysql interne) et compter les bits restants uneval (ainsi supporté à l'intérieur, qui serait alors la distance de Levenshtein des chaînes de bianry)

Developement
• du débit au fil du temps avec le même codec VBR

Je transcode la vidéo dans un fichier vidéo VBR avec les mêmes paramètres exacts. je regardais le bitrate à certains points de temps (pourcentage de la vidéo terminé ou secondes absolues .. alors nous n'analyser une partie de la vidéo). même chose que de l'image. Iif le débit binaire est supérieur à la moyenne de sa 1 sa 0 autre. nous faisons une chaîne binaire et le stocker dans db et calculer la distance Levenshtein plus tard

• analyisis audio (bitrate et décibel varaition au fil du temps comme le bitrate de la vidéo)

• Analyse keyframe

comarision d'image comme la première et la dernière image, mais à des positions des images clés? Nous utiliserions les mêmes fichiers sources que nous avons utilisé pour calcluiations bitrate, car les images clés sont lourds dépendent du codec et les paramètres.

• developement de couleur au fil du temps

Peut-être que nous allons prendre une ou plusieurs zones / pixels dans l'image et voir comment ils develope au fil du temps. Outre le changement Abov / inférieur à la moyenne. noir / blanc suffirait, je pense.

• présenter les suggestions à l'utilisateur pour approbation finale ...

Ou vais-je le chemin complètement faux? Je pense que je ne peux pas être le premier à avoir ce problème, mais je ne l'ai pas eu de chance de trouver des solutions.

Answer 1

Ceci est un énorme problème, donc j'ai choisi d'écrire une réponse assez longue pour essayer de décomposer le problème en plusieurs parties qui peuvent être plus faciles à résoudre.

Il est important que les comparaisons soient effectuées à l'aide des ressources de calcul et de temps disponible: Je doute une solution qui prend des mois à terme sera très utile dans une base de données vidéo dynamique. Et la taille de la base de données fait probablement l'utilisation des ressources cloud computing infaisable. Donc, nous nous soucions vraiment le coût local de chaque comparaison dans plusieurs domaines différents:. 1) stockage de données, 2) les ressources de calcul et 3) temps

Un coût clé à considérer est celui d'extraire les données nécessaires à partir de chaque vidéo pour ce que les mesures de comparaison doivent être utilisés. Une fois les données extraites sont disponibles, le coût d'effectuer une comparaison doit être envisagée. Enfin, les comparaisons nécessaires pour correspondre à toutes les vidéos de l'autre doit être effectuée.

Le coût des deux premières étapes est O (1) sur le nombre de vidéos. Le coût de la dernière étape doit être pire que O (1), potentiellement bien pire. Donc, notre objectif principal devrait être de minimiser les coûts de la dernière étape, même si cela signifie ajouter beaucoup au début, quelques étapes simples.

Les algorithmes optimaux pour ce processus dépendra en grande partie des caractéristiques de la base de données, le niveau auquel il existe plusieurs correspondances simples et. Si 100% des vidéos correspondent à une autre vidéo, nous voulons réduire au minimum le coût d'un match réussi. Cependant, le cas le plus probable est que les matchs seront rares, donc nous voulons réduire au minimum le coût d'une correspondance infructueuse. C'est-à-dire, s'il y a un moyen rapide et sale pour dire « ces deux vidéos ne peuvent pas être matchs, alors nous devrions l'utiliser d'abord, avant même de commencer à confirmer un match.

Pour caractériser la base de données, tout d'abord faire un échantillonnage et correspondant à la main pour estimnate le degré de correspondance au sein de la base de données. Cette expérience devrait montrer comment les vidéos redondantes « agglomérées »: Si la façon dont il était susceptible d'avoir plus d'une seule avait un match, vidéo donné? Quel est le pourcentage de tous les matches faisaient également partie d'un match multiple? Ce processus donne un « modèle » de la base (une distribution statistique) qui sera utilisé pour faciliter l'algorithme de sélection et de mise au point du système.

À l'avenir, je suppose que les matchs sont relativement rares. Après tout, s'il y a beaucoup de matches, les vidéos seront « agglutiner », ce qui rend efficace la base de données plus petits, et ce qui rend le problème plus simple. Supposons que les séjours de problème aussi difficile que possible.

Je préconise une approche de catégorisation multi-niveaux, où nous avions construit une séquence d'algorithmes qui effectuent à plusieurs reprises la décision binaire de « ces deux vidéos ne correspondent pas » / « ces deux vidéos peuvent éventuellement correspondre ». Seul le dernier algorithme dans les besoins de la chaîne de production la réponse « Ces deux vidéos correspondent. »

Classification / algorithmes correspondant peut échouer dans l'une ou l'autre de deux façons: faux positifs (vidéos non-correspondance sont mislabled comme correspondant) et Faux négatif (vidéos correspondants sont mal étiquetés comme non-appariement). Chacune de ces mauvaises décisions a une gamme de probabilités qui y sont associés, et nous voulons réduire au minimum les deux.

Depuis que nous construisons un pipeline d'algorithme, nous voulons des algorithmes qui sont très bons à identifier les non-correspondances sans erreur, ce qui signifie qu'ils doivent avoir un très faible faux taux de rejet, et nous ne se soucient pas beaucoup sur le taux de fausses acceptations. Par exemple, le clone de Weird Al d'une vidéo peut regarder et le son très semblable à l'original, et nous pouvons ne pas être en mesure de démontrer qu'il n'est pas un match à l'original que plus tard dans la conduite de l'algorithme.

Le plus simple, la plus rapide, la plupart des algorithmes fiables devrait être exécuté d'abord, puisque la majorité écrasante de tests vaste donnera le résultat « ne correspondent pas ». Le contrôle plus simple serait de rechercher des fichiers identiques dans la base de données, quelque chose fait par de nombreux services d'entretien et de systèmes de fichiers de base de données simple et rapide.Après cette analyse est exécutée, nous pouvons supposer que nous aurons réellement besoin d'ouvrir et de lire les fichiers vidéo pour détecter des différences.

Étant donné que la comparaison vidéo est relativement difficile, nous allons commencer avec l'audio. Pensez à la base de données en tant que premier étant une collection de MP3 qui peut contenir des doublons. Après tout, si nous obtenons un bon match audio, il est très probable, nous aurons un match vidéo, et vice-versa. Nous pouvons dire en toute sécurité l'audio est un représentant de « juste » pour la vidéo. Heureusement, une recherche rapide sur Internet donnera beaucoup d'indentification audio et des paquets comparaison fiables, rapides et matures. L'empreinte audio devrait être généré pour chaque vidéo dans la base de données. Vidéos qui manquent d'une piste audio tomberaient automatiquement dans l'ensemble « pourrait correspondre ».

Mais il y a une « chasse aux sorcières » ici: Qu'en est-il des voix off? Si est codé deux fois une vidéo donnée, avec et sans voix off, sont-ils un match ou non? Qu'en est-il du son français contre l'espagnol ou en anglais? Si ceux-ci doivent tous être considérés comme un match, puis le test audio peut devoir être sautée.

À ce stade, nous savons que les entrées du système de fichiers sont « assez différentes », et nous savons que les pistes audio sont « assez différentes » (si testé), ce qui signifie que nous ne pouvons pas rebutés regarder les données vidéo tout plus long. Heureusement, cela devrait être fait pour seulement une petite fraction de la base de données vidéo, afin que nous puissions tolérer un certain coût. Comme précédemment, nous voulons toujours essayer d'abord d'éliminer rapidement plus de non-matchs avant d'essayer de marquer positivement un match.

Étant donné que nous devons prendre des changements de résolution en compte (par exemple, de 1080p à l'iPod), nous aurons besoin d'un moyen d'information vidéo de caractériser qui est non seulement indépendant de la résolution, mais aussi tolérant du bruit ajouté et / ou les données perdues dans le cadre de la modification de la résolution. Nous devons tolérer des changements de fréquence d'images (par exemple, de 24 images par seconde à 30 images par seconde de la vidéo d'un film). Il y a aussi des changements de rapport d'aspect à prendre en compte, tels que de 4: 3 NTSC 16: 9 HD. Nous voudrions gérer les changements d'espace de couleurs, tels que de la couleur au noir et blanc.

Ensuite, il y a des transformations qui affectent tout cela à la fois, comme transcoder entre HD et PAL, ce qui peut affecter simultanément l'espace couleur, frame-rate, rapport d'aspect, et la résolution. La caractérisation devrait également être tolérant d'un certain degré de culture et / ou de remplissage, tels que se passerait-il d'un rebroussement-et-vient entre 4: 3 et 16: 9 rapports d'aspect (letterbox, mais pas Recadrage). Nous avons également devrions gérer les vidéos qui ont été tronquées, telles que la suppression des crédits de la fin d'un film caractéristique. Et, évidemment, il faut aussi gérer les différences créées par différents codeurs qui ont été nourris d'un flux vidéo identique.

C'est tout à fait une liste! Considérons certaines choses que nous pouvons choisir de ne pas expliquer: Je pense qu'il est correct de ne pas trouver une correspondance warpant d'image est présente, malgré le fait que la déformation anamorphique n'est pas rare, surtout dans les films grand écran de 35 mm qui ont été directement balayé sans reconstruction anamorphique (personnes de grande taille-maigre). On peut également choisir d'échouer lorsque les grands sont présents dans filigranes au milieu du cadre, bien que nous voulons tolérer plus petits dans les coins filigranes. Et enfin, il est OK pour ne pas faire correspondre les vidéos qui ont été déformées ou temporellement dans l'espace basculées, comme quand on est un mo-de slo l'autre, ou a été renversé de gauche à droite.

Est-ce que juste couvrir sur l'espace vidéo? Si tout va bien, il est clair pourquoi il est important de commencer par le système de fichiers et l'audio! C'est, tout d'abord penser à votre base de données plus comme une collection de MP3 avant de l'envisager comme une collection vidéo.

Ignorant l'audio, la vidéo est juste une séquence ordonnée d'images fixes. Nous sommes donc actuellement à la recherche d'un ou plusieurs algorithmes de comparaison d'images combinées avec un ou plusieurs algorithmes de comparaison de séries chronologiques. Cela pourrait être des paires d'algorithmes séparés (caracrize chaque trame, puis caractériser la séquence de trames), ou il pourrait être fusionnés en un seul algorithme (voir les différences entre les images).

Les images elles-mêmes peut être décomposé en outre, dans un monochrome d'image « structurel » et une couleur « overlay ». Je crois que nous pouvons ignorer en toute sécurité les informations de couleur, si elle est pratique informatiquement de le faire.

De ce qui précède, il peut sembler comme je l'ai supposé que nous allons devoir décoder complètement une vidéo afin d'effectuer des comparaisons sur elle. Ce n'est pas nécessairement le cas, bien que la comparaison des données codées a de nombreuses difficultés qui limitent son utilité. La seule exception notable à cette règle est pour les encodages vidéo niveau d'objet tels que MP4, où ont été effectuées des comparaisons multi-images de très haut niveau. Malheureusement, les comparaisons d'objets entre les flux MP4 n'a pas vu beaucoup de recherches, et je suis au courant de pas de paquets en mesure de remplir cette fonction. Mais si vous trouvez un, utilisez-le!

La plupart des autres flux vidéo numériques utilisent le codage des programmes tels que MPEG2, Quicktime, ou quelque chose de similaire. Ces systèmes utilisent tout le concept de cadres clés et cadres de différence, bien que chacun met en œuvre différemment. Lorsque des vidéos sont comparés (ceux qui ne sont pas la même taille), il est peu probable que les images clés et les cadres de différence correspondent à un degré utile. Toutefois, cela ne signifie pas qu'il est impossible, et les paquets existent qui tentent d'extraire des informations utiles à partir de ces flux sans effectuer un décodage complet. Si vous trouvez un qui est rapide, il peut tomber dans un « pourquoi ne pas essayer » catégorie de tests.

L'une astuce je vais utiliser est au lieu de décoder complètement les cadres, je place les décoder uniquement dans les canaux de composants séparés (HSV, HSL, YUV, peu importe) et pas tout le chemin vers le framebuffer RGB (à moins que ce qui a été encodées , bien sûr). A partir de là, je crée ensuite la luminance séparée et des cadres de chrominance (couleur) et les comparaisons peuvent être effectuées dans des domaines connexes. Tout le décodage d'un framebuffer RVB peut introduire des erreurs qui peuvent rendre plus difficile de trouver les matchs.

Ensuite, je voudrais jeter les informations de couleur. Depuis une vidéo monochrome doit correspondre à sa couleur originale, nous ne soucions pas simplement de la couleur!

Comment peut la séquence résultante des images monochromes être comparées à une autre séquence qui peut paraître très différente, mais peut encore peut-être un match? Il y a eu littéralement des décennies de recherche dans ce domaine, en grande partie classé sous la rubrique « détection de correspondance échelle invariant ». Malheureusement, très peu de ces recherches ont été appliquées directement à déterminer quand les vidéos ne ou ne correspondent pas.

Pour nos besoins, nous pouvons aborder cette question de plusieurs directions. Tout d'abord, nous devons savoir pour nous-mêmes ce qui est et n'est pas un match dans le domaine monochrome. Par exemple, nous ne se soucient pas de différences au niveau des pixels, car même si deux vidéos correspondants, mais avaient-différents la même résolution, nous devons tolérer un certain niveau de bruit dû à des choses comme les différences de codeur.

A simple (mais lent) voie à suivre pour transformer chaque image en une forme qui est indépendante à la fois la résolution et le rapport d'aspect. Une telle transformation est dans le domaine des fréquences spatiales, et la FFT 2D est idéal pour cela. Après avoir jeté la composante imaginaire, la partie réelle peut être tronquée à des fréquences élevées pour éliminer le bruit et à des fréquences basses pour éliminer les effets de rapport d'aspect, puis étalonnée par rapport à une échelle standard éliminer les différences de résolution. Les regards de données résultant comme une petite image étrange qui peut être directement comparés les flux vidéo.

Il y a beaucoup d'autres stratégies de transformation d'image possible, beaucoup beaucoup plus efficace que la FFT, et une recherche documentaire devrait les mettre en évidence. Malheureusement, je connais peu qui ont été mises en œuvre dans les bibliothèques logicielles qui sont aussi faciles à utiliser que la FFT.

Une fois que nous avons transformé le monochromecadres dans un domaine plus petit et plus utile, nous devons encore effectuer la comparaison à un autre tel courant d'une autre vidéo. Et cette vidéo est à peu près certain de ne pas être un match cadre à cadre, donc une comparaison simple va certainement échouer. Nous avons besoin d'une comparaison qui prendra sur les différences de compte dans le domaine temporel, y compris ajoutés / supprimés cadres et les différences de taux de trame.

Si vous regardez la séquence des images FFT, vous remarquerez un comportement très distinct. La scène se sont brusques et extrêmement faciles à repérer, les coupes peuvent également être distingués, et il y a généralement des changements que lents observés dans la FFT entre les coupes. A partir de la séquence de TFR, nous pouvons étiqueter chaque image comme étant la première après une coupure / fade, ou un cadre entre les coupes / fades. Ce qui est important est le temps entre chaque coupe / fade, indépendamment des nombre de trames entre eux, ce qui crée une signature ou une empreinte digitale qui est en grande partie indépendante du taux de trame.

Prendre cette empreinte d'un ensemble de données vidéo donne qui est massivement plus petite que la vidéo elle-même. Il est également une séquence linéaire de nombres, un simple vecteur de séries temporelles, un peu comme l'audio, et peut être analysé à l'aide un grand nombre des mêmes outils.

Le premier outil consiste à effectuer une corrélation, pour déterminer si le motif des coupes dans une vidéo est un jeu proche de celle dans une autre vidéo. S'il y a des différences importantes, alors les vidéos sont différents. Si elles sont un match serré, les seuls quelques TFR après chaque coupe corrélatifs doivent être comparés afin de déterminer si les images sont assez semblables pour être un match.

Je ne vais pas entrer dans la comparaison des TFR 2D ici, car il y a de nombreuses références qui font le travail beaucoup mieux que je peux.

Note: Il y a beaucoup d'autres manipulations (au-delà d'une FFT 2D) qui peut être appliqué à des cadres monochromes pour obtenir des empreintes digitales supplémentaires. Les représentations de contenu de l'image réelle peut être créé par l'extraction des bords intérieurs de l'image (littéralement comme une empreinte digitale FBI), ou par seuillage sélectivement l'image et l'exécution d'une « blobbing » opération (création d'une liste liée de descripteurs de régions connexes). Suivi de l'évolution des bords et / ou blobs entre les images peuvent être utilisées non seulement pour générer des listes de coupe, mais peut également être utilisé pour extraire des caractéristiques d'image de haut niveau supplémentaires qui seraient perdus en utilisant une FFT 2D.

Nous avons construit une séquence d'algorithmes de comparaison qui devrait être très rapide à trouver non-correspondances, et ne nécessitent pas trop de temps pour déterminer de façon concluante les matchs. Hélas, ayant des algorithmes ne fait pas une solution! Il faut tenir compte de plusieurs questions liées à la façon dont ces algorithmes devraient être appliquées au mieux.

Tout d'abord, nous ne voulons pas d'ouvrir et de lire chaque fichier vidéo tout plus de fois que nécessaire, sinon le CPU pourrait bloquer en attente de données du disque. Nous ne voulons pas lire plus loin dans un fichier que nécessaire, si nous ne voulons pas arrêter de lire trop tôt et raterons un match plus tard. Si les informations qui caractérise être sauvé chaque vidéo, ou doit-il être recalculée en cas de besoin? La résolution de ces problèmes permettra un système de comparaison vidéo efficace et efficace pour être développé, testé et déployé.

Nous avons montré qu'il est possible de comparer des vidéos avec un peu d'espoir de trouver des correspondances dans des conditions très variables, avec une efficacité de calcul.

Le reste a été laissé comme un exercice pour le lecteur. ; ^)

Answer 2

Bonne question! L'essai ne dira que ces facteurs seront les meilleurs indicateurs. Quelques idées:

• développement du débit au fil du temps avec le même codec VBR: Cela semble très gourmand en temps processeur, mais je pense qu'il donnerait d'excellents résultats. analyse audio semble que cela donnerait des résultats similaires avec moins de travail.
• première et dernière analyse de l'image du cadre: ne serait-50% de ceux-ci serait noir? Une meilleure idée pourrait être d'utiliser le cadre très moyen, mais je ne compte pas sur cette technique étant fiable.
• Utiliser des statistiques bayésiens pour enregistrer les facteurs rendent les meilleures contributions à un match positif. Cela pourrait se faire dans la phase de test pour éliminer les comparaisons inutiles et coûteuses.
• Obtenir les utilisateurs pour aider! Laissez groupe d'utilisateurs doublons de trouver ensemble. Ils votent sur celui avec la meilleure qualité et que l'on agira comme la version primaire / officielle au sein du groupe.
• Démarrer avec les comparaisons plus faciles et ajouter des tests plus sophistiqués lorsque vous trouverez les lacunes des simples. Durée de la vidéo serait un bon pour commencer, alors peut-être une analyse audio rudimentaire, et de travailler votre chemin à partir de là.

Answer 3

Juste essayer ce produit - double vidéo Recherche (. Ex Recherche visuelle poney), qui peut trouver des fichiers vidéo en double de différents bitrates, formats, résolutions et etc.

Par exemple, l'étoile-wars.avi (H.264 640x480) et sw.mpg (1280x720 MPEG) sera détecté comme doublons, si les deux d'entre eux sont des copies d'un grand film -. Star Wars

Selon leur site web, le produit utilise des techniques d'empreintes digitales vidéo, comme des cadres clés exctraction ou lissée. comme celui-ci, ne pas être indépendant de l'encodage vidéo, la résolution, la qualité, bitrate et etc.