Laboratoire Bordelais de Recherche en Informatique 23/02/2014 5. Chapitrage des documents audio- visuels numériques Un plan de montage est une unité de

Laboratoire Bordelais de Recherche en Informatique

11/04/23

5. Chapitrage des documents audio-visuels numériquesUn plan de montage est une unité de base.

Afin d’assurer une description moins redondante – groupement des plans en scènes

t=2283 t=2457 t=2646 t=2802

… t=11322 t=11526 t=13698


11/04/23

Groupement en scènes

Typologie des approches : (1) Considérer des images-clés représentatives

de chaque plan et les regrouper en classes-scènes dans l’espace de description des images

(2) Considérer des descripteurs globaux pour les plans de montage et regrouper les plans dans l’espace de description des plans

(3) trouver les frontières significatives de rupture du contenu vidéo ou audio/vidéo


11/04/23

Algorithmes de classification-groupementappliqués au groupement en scènes Les descripteurs vidéo sont représentés par des

vecteurs Il s’agit de partitionner l’espace ou un domaine

en classes – scènes

Classification : supervisée et non-supervisée.

- CS : les classes sont connues a priori, on doit affecter à chaque vecteur d’entrée sa classe

(ex. scènes de l’intérieur / de l’extérieur après l’apprentissage)

-CSN : les classes sont à déterminer en fonction de la distribution (structure) des données dans l’espace.

nRx


11/04/23

Algorithme de K-moyennes(I) J. MacQueen, “Some methods for classification and analysis of multivariate observations”, Proc. Of the Fifth

Berkley Symposium on Math. Stat. And Prob., pp. 281 – 296, 1967

Principe : CNS avec le nombre des classes connus a priori.

Paramètre : le nombre k de classes entrée : un échantillon de M vecteurs-descritpeurs x1,...

xM. (1) Choisir k centres initiaux c1,... ck

(2). Pour chacun des M vecteurs, l'affecter à la classe i dont le centre ci est le plus proche

(3). Si aucun élément ne change de classe alors arrêt. (4). Calculer les nouveaux centres : pour tout i, ci est la

moyenne des éléments de la classe i (5). Aller en 2


11/04/23

Classification hiérarchique agglomérative Principes : (1) A l’initialisation chaque vecteur descripteur dans l’échantillon de

données forme une classe. (2) Tant que le nombre de classes est supérieur à k ( à la limite k=1)

Regrouper les classes les plus proches au sens d’une distance D

Distance entre les classes lien minimal lien maximal distance moyenne

yxdji CyCx

ji CCd ,max,

max ),(

yxdji CyCx

ji CCd ,min,

min ),(

pl

np

p

nl

ljijimoy yxd

nnCCd

ji

,1

),(11

d’après A. Laurent, LIRMM


11/04/23

Dendrogramme

d’après S. Benini, ICIP’2006


11/04/23

Problèmes sous-jacents Choisir les descripteurs x des plans vidéo :

descripteurs de bas – niveau ( couleur dominante, activité en mouvement,…)

descripteurs de niveau « moyen » sémantique : ex. présence des visages

Définir des mesures de similarité adéquates : Euclidienne – calculs importants, uniforme Hamming : représentation binaire (booléenne)

« Distorsion de codage » Difficultés d’évaluation par rapport à la vérité terrain

« manuelle »

Tnxxx ,...,1

Tnyyy ,...,1

ii

n

iH yxyxd

1

),(


11/04/23

Graphe de scènes et Story Units (M. Yeung’96)

Graphe de transition des scènes (STG) – une représentation compacte de la structure (scénario) d’une vidéo

STG est un graphe orienté

avec

V- ensemble des nœuds,

E – ensemble des arêtes

- ensemble des plans de montage d’une vidéo

jii vvEvVFVG ,,,,,

VSF i :

iS


11/04/23

Graphe de scènes et Story Units (M. Yeung’96)

Les plans de montage dans chaque sont similaires entre eux.

Continuité temporelle : pour le couple U, W donnée dans V, si il existe des plans

(continuité dans le temps)

Définissons - les indices du premier plan et du dernier plan représentés pas le graphe G

Si STG G est construit à partir des plans

alors et

mll SSS ,...,, 1

EWU , 1: lmWSetUS ml

)(),( GLSGFS

lGFS )(mGLS )(

iv


11/04/23

Graphe de scènes et Story Units(II)Associons un graphe non-orienté à G. et G ont le même ensemble des nœuds et-pour tout de G il existe l’arête correspondante dans avec les mêmes nœuds incidents.

Arête de rupture dans :

est une arête de rupture si se décompose en deux composantes connexes.

L’ensemble des arêtes de rupture partitionne en

ensemble des sous-graphes connexes, non-connéctés entre eux

Il induit la partition correspondante sur G :

avec la même F

Story Unit représenté par est une séquence des plans

Arêtes de rupture transitions entre story units

G EVG ˆ,ˆ

e

e G

G

e G

nGGG ˆ,...,ˆ,ˆ21

FEVGGGGG iiini ,,,,...,,...,, 21

iG iiiimll

GLSmGFSlSSSiii

,:,...,,1

G


11/04/23

Graphe de scènes et Story Units (III)

Groupement des plans dans les classes (clusteirng)

Ci – une classe comportant les plans vidéo similaires

Définissions

Objectif : construire une partition de l’ensemble des plans en classes telle que

Méthode : classification agglomerative hiérarchique (complete – link)

iCx

iCzy

i zyd

,

,max

iv

ijCwwxd ji ,),(

yxdji CyCx

ji CCd ,max,

max ),(


11/04/23

Graphe de scènes et Story Units (IV)

Algorithme de classification (Complete-link)1. Initialiser chaque cluster par un plan vidéo , NumCluster :=N2 . Arrêter si pour toutes les classes ou NumCluster=1

3. Trouver le couple des classes R et S les moins dissimilaires

4. Fusionner R et S dans une nouvelle classe

NumCluster:=NumCluster -1

5. Aller à 2.

NSSS ,...,, 21

BAd ,max

iv

BA

BABAdSRd ,,, maxmax


11/04/23

Graphe de scènes et Story Units (V)

Classification avec les contraintes temporelles

Distance temporelle entre les plans

La longueur de la fenêtre temporelle comme contrainte pour le processus de classification

Le même algorithme de classification mais avec une distance modifiée :

jijiebebSSd jiij

jit,0

,,min,

ijCwTwxdor

wxdandTyxd

jt

itCy i

,),(

),(,max

sinon,,,,,ˆ TSSdsiSSdSSd jitji

jit


11/04/23

Graphe de scènes et Story Units (VI)

Distance –couleur ( ou corrélation) entre les plans

- s’appuie sur les images clés, ou un ensemble des images clés.

- plusieurs choix sont possibles

ji SSd ,

mlSKfSKf

ji ffDSSdjjmiil

,, min,,


11/04/23

Segmentation en Scènes/Hyperscènes avec des descripteurs spatio-temporels

Scène (notée Si) : regroupement de plans consécutifs temporellement

Hyper-scène (notée Hi) : regroupement de scènes non consécutives

Plan

Scène

Hyper-scène

Methode de J. Benois-Pineau, D. Barba, W. Dupuy, A. Manoury, H. Nicolas

Hyper-scène


11/04/23

Block-diagramme

Estimation du mouvement

Segmentation en plan

Suppression des objets

Mesure de similarité

Clustering en scène

Clustering en hyper-scène

Création des mosaïque

couleur 1D

Document vidéo codé MPEG2

Carte des outliers Images sans

objets

Liste des plans

Paramètres du mouvement

mosaïque couleur 1D

Signatures couleur

Similarité entre plans

Regroupement en scènes

Regroupement en Hyper-scènes


11/04/23

Espace de descripteurs spatio-temporels pour le groupement

Signature visuelle : descripteur global d’un plan vidéo permettant d’identifier des plans sans ambiguïté.

Exemples : histogramme couleur de tout un plan vidéo, vecteur des mesures des points caractéristiques

spatio-temporels (x,y,t) etc.. Mosaïque Mosaïque 1D.


11/04/23

Mosaïque 1D : signature couleur d’un plan Descripteur intégrant à la fois les informations spatiales

et le mouvement

vecteur–couleur obtenu par compensation du mouvement dans le domaine de la transformée Radon – « X-ray »


11/04/23

Mosaïques 1D

Calcul des images X-Ray

Relation entre le mouvement 2D et 1D

dxtyxItyIx ),,(),(

dytyxItxIy ),,(),(

))(()()())(()()(

gy

gx

yytftTtdyxxtftTtdx

wk

k

ccx

c ykIw

yII1

),(1

)]([

hk

k

ccy

c kxIh

xII1

),(1

)]([

)( gmm mmtftTdm

tftf m)(

yy

xxm IsiT

IsiTT

2D

1DJ. BENOIS-PINEAU, W. DUPUY, D. BARBA TSI/2003, pp. 1167 – 1200, Hermes-Lavoisier


11/04/23

Modèle de mouvement : affine à 3 paramètrestranslation (2), divergence (1)

Méthode : estimation paramétrique robuste du mouvement global de

la caméra entre couples d’images ( type I-P ou type P-P) à

partir des vecteurs de déplacement (par macro-bloc)

extraits du flux MPEG2

Interpolation des paramètres manquants pour les images de type I

Informations de position des objets en mouvement : élimination des outliers

Estimation du mouvement

dx = tx + f(x-xg)

dy = ty + f(y-yg)


11/04/23

Document « Chancre coloré du platane », CERIMES © (Plan n°32 le parasite en culture sur une coupe de platane : zoom avant)


11/04/23

Div-Chancre

-0,05

-0,04

-0,03

-0,02

-0,01

0

0,01

0,02

frames

val

Div

Tx-Ty-3pars

-5

-4

-3

-2

-1

0

1

2

3

4

4590

4605

4620

4635

4650

4665

4680

4695

4710

4725

4740

4755

4770

4785

4800

4815

4830

4845

4860

4875

frames

vale

urs

Tx

Ty


11/04/23

Champs de déplacement


11/04/23

Compensation du mouvement 1D

Compensation dans le répère de la première image,

Antilope, CERIMES

Calcul des coordonnées 1D

)()()(

),(1

gjmj

jjj

mtmtftTtdm

tdmtmtm

Début du plan

]2/1)(int[ refjrefj tmtm -finalement au moment de temps de référence


11/04/23

Calcul des mosaïques 1D

refjrefj tttmMosMedtmMos ,...,1,0,),(),( Calcul de la valeur

Chancre coloré de platane, CERIMES


11/04/23

Groupement des plans en hyper-scènes Distance entre deux plans :

BD – distance « des fonds » - est basée sur la compensation du mouvement entre les mosaïques

CD – distance couleur : appariement de n segments de mosaïque Mosi avec n segments de Mosaïque Mosj

(d’après H. Nicolas, A. Manoury, 2004)

jijiji PPCDPPBDPPD ,,,min,

22

,,2

,,

,

1min, y

myj

yi

xm

xj

xi

OmVUYjidd

ji dmMosmMosdmMosmMosOCard

PPBDji

ym

xm

)(min1

,, ,,

2,,

,1),(, ,,

2,,

,1),(2 min

22

qp VUY

yqj

ypi

nqplk VUY

xlj

xki

nlkji osMosMosMosM

nPPCD


11/04/23

Structurations de référence

Hyperscène sémantique (« plancton »)

• Structuration manuelle sémantique (professionnel CERIMES)

• Structuration manuelle basée couleur (usager standard)

Hyperscène couleur (« bleu vif »)


11/04/23

Structuration automatique (séquence Chancre)

Exemples d’hyper scènes similaires à la structuration manuelle

H1

H2

H3

H4


11/04/23

Structuration automatique (séquence Chancre)

Exemples d’hyper scènes différentes des structurationsmanuelles, mais cohérentes

H3

H1

H2

H4

Exemple d’une hyper scène automatique peu cohérente


11/04/23

Performances

Séquence « Chancre » - Plan recall et plan précision (%) calculé pour la structuration automatique et par référence à la structuration couleur

Catégorie 1 Catégorie 2 Catégorie 3

Plan-recall Plan-précision Plan-recall Plan-précision

Plan-recall Plan-précision

53 71 23 50 18 30


11/04/23

Indexation cross-média en scènes par détection des ruptures significatives du contenu

Modèle du monde : coupure vidéo et silence audio – frontière d’une scène

J. Nesvadba, N. Louis, J. Benois-Pineau, M. Desainte-Catherine, M.K. Middelink,

« Semantic content segmentation of audio-visual documents using cross –media analysis »


11/04/23

Mesure Statistique

Energie (dB)

Temps (sec)

- 40 Line de décision

Silence

Temps (sec)

Audio

Video

Jitter < 0 Jitter > 0

Video shot

Jitter = 0

« Jitter » - « tremblement » audio-visuel


11/04/23

Méthode de décision

Soit deux hypothèses : H0: Changement de scène. H1: Pas de changement de scène. P(H0) + P(H1) = 1.

Théorème de Bayes– x un événement indépendant.

Log-vraisemblance :

Pr( / 0) Pr( 0)Pr 0 /

Pr( )

Pr( / 1) Pr( 1)Pr 1/

Pr( )

x H HH x

x

x H HH x

x

2 22 20 01 1

2 21 0

0log( ) ( )log( ) ( )log((1 Pr( 0) / Pr( 0))

12 2 2 2

HxxR H H

H


11/04/23

Résultats (I)

Corpus composé de: 60 minutes de séries 30 minutes de magazine 100 minutes de film

Deux types de résultats Résultats sur un mélange de genres vidéo en

utilisant les détecteurs audio et vidéo automatiques. Résultats sur un mélange de genres vidéo en

utilisant les détecteurs audio et vidéo idéaux.


11/04/23

Résultats (II)

Détecteurs réels Détecteurs idéaux

Rappel Précision Rappel Précision

Jitter fixe +/- 3 76.60% 46.00% 94.44% 71.43%

Jitter fixe +/- 10 81.12% 40.33% 97.78% 49.16%

Jitter fixe +/- 21 83.30% 31.65% 98.89% 32.72%

Méthode statistique 73.33% 45.52% 93.34% 72.41%

Documents

Laboratoire Bordelais de Recherche en Informatique 23/02/2014 5. Chapitrage des documents audio- visuels numériques Un plan de montage est une unité de