Brevet FR2872665A1 — publié le 20060106

L'invention concerne un dispositif et une méthode de compression de documents vidéo. L'invention concerne plus particulièrement la compression vidéo 5 adaptée à l'archivage. Les contraintes de compression d'un document vidéo sont moins importantes lorsqu'il s'agit d'archiver de la vidéo que lorsqu'il s'agit de compresser de la vidéo pour de la transmission. En effet, une vidéo destinée à être compressée, transmise et 10 décompressée en temps réel doit être compressée en prenant les images les unes après les autres, dans un ordre chronologique, comme le font des méthodes de codage telles que MPEG-2 par exemple. Lorsque les images sont destinées à être enregistrées sur des supports de stockage pour du stockage longue durée, tels des disques durs par exemple, il est possible de les compresser dans un ordre quelconque de manière à optimiser la quantité d'information stockée et ainsi à minimiser les ressources de stockage nécessaires. Les contraintes de compression ne sont donc pas les mêmes que dans le cas de codage/décodage temps réel. L'invention concerne donc l'ordonnancement des images d'un document vidéo avant codage de manière à augmenter le taux de compression. Effectivement, plusieurs méthodes de compression de données utilisent des regroupements en clusters. Cependant, une fois les clusters finalisés, le codage est effectué directement sur les images dans leur ordre chronologique. La présente invention permet de s'affranchir de cet ordre chronologique et de coder les images en obtenant un taux de compression optimisé. A cet effet, l'invention concerne un procédé de compression de 30 documents vidéo comprenant les étapes de: - décomposition du document vidéo en plans, - extraction d'images représentatives desdits plans, mesure des distances entre lesdites images représentatives, - regroupement des images dont la distance est inférieure à un seuil prédéterminé dans un groupe d'images, - calcul du coût relatif de codage de chaque image par rapport aux autres images du groupe d'images, Selon l'invention le procédé comprend les étapes de - calcul d'un arbre de recouvrement minimal pour chaque groupe d'images minimisant le coût de codage de chaque groupe d'images - codage de chaque groupe d'images en parcourant les images dans l'ordre donné par ledit arbre de recouvrement. L'arbre de recouvrement minimal peut permettre de modifier l'ordre de codage des images et ainsi d'améliorer le taux de compression. Ceci est particulièrement adapté, mais pas exclusivement réservé, à de la compression destinée à de l'archivage où le temps de codage n'est pas important et où l'ordre de codage n'est pas important. Selon un mode de réalisation préféré, la première image codée de l'arbre de recouvrement est codée en mode intra. Selon un mode de réalisation préféré, les images autres que la première image sont codées en mode prédictif par rapport à l'image précédente dans l'arbre de parcourt optimal. Selon un mode de réalisation préféré, plusieurs images espacées dans 25 l'arbre de recouvrement sont codées en mode intra. L'invention sera mieux comprise et illustrée au moyen d'exemples de modes de réalisation et de mise en oeuvre avantageux, nullement limitatifs, en référence aux figures annexées sur lesquelles: la figure 1 représente la décomposition de la vidéo en groupes d'images représentatives. la figure 2 représente les étapes du procédé selon l'invention, la figure 3 représente un arbre de recouvrement minimal, la figure 4 représente un dispositif selon l'invention. Un document vidéo est constitué d'une succession d'images, elles mêmes pouvant souvent être regroupées en plans, les plans correspondant à 5 des ruptures de prise de vue. La figure 1 représente une décomposition d'un document vidéo en plans P1, P2, P3,...,P10. La figure 1 va être décrite en parallèle avec la figure 2 illustrant les étapes du procédé permettant d'obtenir la découpe du document vidéo illustrée en figure 1. Différentes méthodes de décomposition d'une vidéo en plans existent, illustré par l'étape 1 de la figure 2. Une telle méthode est notamment décrite dans la demande de brevet français 0213978 déposée le 28 octobre 2002 au nom de la société Thomson Licensing SA. Cette demande décrit également l'extraction d'images clés (étape 2 de la figure 2) pour chaque plan. Une ou plusieurs images clés peuvent être extraites de chaque plan, ceci étant dépendant de la quantité de mouvement du plan, un plan présentant de forts mouvements pouvant être caractérisé par plus d'une image clé. Ensuite, les images clés sont regroupées en fonction de leur similarité (étape 4 figure 2). La similarité est calculée par une mesure de distance entre images. La mesure de distance entre images est basée sur la distance entre attributs F. F est représentatif d'une caractéristique de l'image choisie, à titre illustratif et non limitatif, parmi la texture, la couleur. A titre d'alternative, les coefficients dominants de la transformée en ondelettes peuvent également être pris en tant qu'attribut. Différentes méthodes de calcul des attributs existent (étape 3 figure 2) et sont bien connues de l'homme du métier. La distance D calculée peut être une distance de type euclidienne à titre illustratif. Lorsque la distance D est inférieure à un seuil prédéterminé c, qui peut par exemple être fixé en fonction du type de document vidéo, les images sont regroupées en groupes ou clusters , étape 5 de la figure 2. Ces groupes d'images présentent alors une similarité visuelle importante. Lorsque plusieurs images clés sont extraites d'un même plan, et que lors de l'étape de regroupement en clusters elles ne figurent pas dans le même cluster, alors les clusters auxquels elles appartiennent sont fusionnés. Le nombre de clusters obtenus dépend du seuil c prédéterminé de mesure de similarité et de la méthode utilisée pour le regroupement en clusters. Chaque cluster comporte toutes les images d'un certain nombre de 10 plans. Ensuite, pour chaque paire d'images dans chaque cluster, un coût de codage est calculé. Chaque image est sélectionnée une à une et on évalue le coût de 15 codage (étape 6, figure 2) relatif de chaque image par rapport aux autres. Ensuite, à partir de ces coûts de codage, un arbre de recouvrement minimal est calculé pour chaque cluster (étape 7, figure 2). Cet arbre de recouvrement minimal permet de trouver un chemin de parcourt de 20 l'ensemble des images d'un cluster qui minimise les coûts de codage. Parmi les algorithmes de calcul d'un arbre de recouvrement minimal, l'algorithme de Kruskal est utilisé. Dans d'autres modes de réalisation, l'algorithme de Prim peut 25 également être utilisé. Un exemple d'un tel arbre de recouvrement est donné en figure 3 dans laquelle les points représentent les images du cluster. Le cluster Ci comprend 7 images numérotées 11 à 17. Les images 11 à 17 d'un même plan à l'intérieur d'un cluster sont 30 consécutives. L'algorithme de Kruskal appliqué sur le cluster 11 à 17 donne l'arbre de recouvrement donné en partie droite de la figure 3. Cet arbre donne l'ordonnancement dans lequel les images doivent être codées pour obtenir un coût de codage minimal, c'est-à-dire un coût de codage qui permet une compression maximale de la séquence vidéo. Lorsque l'arbre de recouvrement est calculé pour chaque cluster, les images sont codées selon un ordre compatible avec l'arbre de recouvrement (étape 8, figure 2). Le choix de l'image d'origine est arbitraire; le choix le plus avantageux est de prendre l'image ayant le codage intra le plus court. Une fois l'image d'origine choisie, les images restantes sont ordonnées selon l'ordre de descendance dans l'arbre. Selon cet exemple, l'image 4 est la première image qui sera codée. Cette image est donc codée selon un mode de codage intra, c'est-à-dire uniquement spatial. Les images suivantes sont codées selon un mode prédictif par rapport à l'image précédente dans l'arbre. L'image 17 est codée par rapport à l'image 17, l'image 16 est codée par rapport à l'image 13 de même que l'image 12. L'image I1 est codée par rapport à l'image 12 et l'image 15 est codée par rapport à l'image 11. Dans d'autres exemples, il est possible que plusieurs images soient codées en mode intra. Ceci notamment dans le cas où le cluster comporte un nombre important d'images. Dans ce cas, certaines images sont choisies, espacées régulièrement dans l'arbre de recouvrement, pour être codées en mode Infra. Plusieurs schémas de codage prédictif peuvent être envisagés. Notamment, dans le mode de réalisation proposé, les images sont codées selon un schéma de codage conforme à la norme MPEG-2 ou MPEG-4. Une fois codées, les images sont archivées dans un support de stockage tel un disque dur par exemple, ainsi qu'une description de la structure de clusters et d'arbre permettant de reconstituer la vidéo globale. Chaque image est identifiée par une étiquette temporelle permettant d'ordonnancer les images et de reconstituer le flux vidéo lors du décodage. L'invention est par exemple particulièrement adapté à des programmes dans lesquels un plan revient régulièrement. Ceci est particulièrement vrai dans le cas de journaux ou de magazines télévisés où les images comportent régulièrement des plans sur les journalistes qui présentent l'émission. La figure 4 représente un système dans lequel l'invention est mise en oeuvre. Le système comprend une caméra 11. La caméra capture un événement et les informations vidéo sont transmises à une unité de traitement 10 9. L'unité de traitement 9 est adaptée à É effectuer la décomposition du document vidéo en plans, É extraire des images représentatives desdits plans, É mesurer des distances entre lesdites images représentatives, 15 É regrouper des images dont la distance est inférieure à un seuil prédéterminé dans un groupe d'images, É calculer le coût relatif de codage de chaque image par rapport aux autres images du groupe d'images, É calculer un arbre de recouvrement minimal pour chaque groupe 20 d'images minimisant le coût de codage de chaque groupe d'images. Une fois ceci effectué, les informations d'ordonnancement des images sont transmises au dispositif de codage 12. Le dispositif de codage 12 est adapté pour coder les images vidéo avant de les transmettre à l'unité 25 d'archivage 10, qui peut être un disque dur, un DVD... Revendications 1. Procédé de compression de documents vidéo comprenant les étapes 5 de: Décomposition (1) du document vidéo en plans, extraction (2) d'images représentatives desdits plans, mesure (3, 4) des distances entre lesdites images représentatives, regroupement (5) des images dont la distance est inférieure à un seuil prédéterminé dans un groupe d'images, calcul (6) du coût relatif de codage de chaque image par rapport aux autres images du groupe d'images, caractérisé en ce qu'il comprend les étapes de calcul (7) d'un arbre de recouvrement minimal pour chaque groupe d'images minimisant le coût de codage de chaque groupe d'images codage (8) de chaque groupe d'images en parcourant les images dans l'ordre donné par ledit arbre de recouvrement. 2. Procédé selon la revendication 1 caractérisé en ce que la première image codée de l'arbre de recouvrement est codée en mode intra. 3. Procédé selon l'une des revendications 1 à 2 caractérisé en ce que les 25 images autres que la première image sont codées en mode prédictif par rapport à l'image précédente dans l'arbre de parcourt optimal. 4. Procédé selon la revendication 1 caractérisé en ce que plusieurs images espacées dans l'arbre de recouvrement sont codées en mode 30 intra. 5. Dispositif de compression de documents comprenant des moyens (9) de: Décomposition du document vidéo en plans, 15 extraction d'images représentatives desdits plans, mesure des distances entre lesdites images représentatives, regroupement des images dont la distance est inférieure à un seuil prédéterminé dans un groupe d'images, calcul (6) du coût relatif de codage de chaque image par rapport aux autres images du groupe d'images, caractérisé en ce qu'il comprend des moyens (9) de calcul d'un arbre de recouvrement minimal pour chaque groupe d'images minimisant le coût de codage de chaque groupe d'images des moyens (12) de codage de chaque groupe d'images en parcourant les images dans l'ordre donné par ledit arbre de recouvrement.