Proposition d’un cadre pour l’analyse automatique, l’interprétation … · 2015-01-27 · Proposition d’un cadre pour l’analyse automatique, l’interprétation et la recherche

Proposition d’un cadre pour l’analyse

automatique, l’interprétation et la recherche

interactive d’images de bande dessinée

Thèse réalisée parClément Guérin

Sous la direction de Karell Bertet et Arnaud Revel

Soutenue le 24 novembre 2014

Contexte État de l’art Cadre Analyse contextuelle ConclusionRechercheSéquence 2

De ses origines…

• Apparition dans la deuxième moitié du XIXème siècle

– Patrimoine mondial

– Principalement produit en Europe, au Japon et aux États-Unis

• Langage universel

La bande dessinée


…aux portes du numérique…

• Nouveaux mediums

– Émergence des webcomics

– Développement des supports numériques de lecture

– Production d’œuvres originales ou adaptées

• Big Data

– Indexation : masse critique d’albums

– Préservation : œuvres rares ou anciennes

La bande dessinée

De ses origines…


De ses origines… …aux portes du numérique…

• Nouveaux mediums– Qu’est-ce qu’une bande dessinée numérique ?

– Numérique ≠ numérisée

– Comment retranscrire la richesse de la narration ?

• Big Data– Comment indexer de tels contenus ?

– Complexité de la structure des documents

– Hétérogénéité des œuvres

La bande dessinée

…levant de nouveaux défis.


• Où se situent les cases ? Les bulles ?

• Reconnaitre le texte ? Les onomatopées ?

• Détecter les personnages

• Qu’est-ce qu’une case ? Une bulle ?

• Que signifie leur position dans l’image ?

• Que peut-on déduire de leur forme ?

• Quels sont les liens qui les unissent ?

D’une part visuel…

Un problème d’interprétation d’images


D’une part visuel…

• Où se situent les cases ? Les bulles ?

• Reconnaitre le texte ? Les onomatopées ?

• Détecter les personnages

• Qu’est-ce qu’une case ? Une bulle ?

• Que signifie leur position dans l’image ?

• Que peut-on déduire de leur forme ?

• Quels sont les liens qui les unissent ?

…d’autre part sémantique…



• Projet eBDtheque débuté en 2011– Financement CPER– Deux thèses, un postdoc, un ingénieur– Six permanents

• Deux aspects complémentaires– Traitement d’images (bottom-up)– Représentation des connaissances (top-down)

• Synergie entre ces deux approches


…qu’il nous faut résoudre.

Traitement d’images(Thèse de Christophe Rigaud)

Représentation des connaissances

(Thèse de Clément Guérin)

Système d’analyse hybride

D’une part visuel… …d’autre part sémantique…

Plan de la présentation

9


Un cadre pour l’analyse de BD

Sequence

de lecture

Contexte Etat de l’art

Analyse

contextuelle

Recherche

d’information

Conclusions Perspectives

10



Sequence

de lecture


Analyse

contextuelle

Recherche

d’information



• Quelques travaux portant sur l’analyse visuelle

– Cases [Arai10, Ho11, Li12, Ponsard12, Rigaud12]

– Bulles [Arai11, Ho12, Rigaud13a]

– Texte [Su11, Li13, Rigaud13b]

– Personnages [Takayama12, Ho13, Rigaud14a]

• Initiatives récentes

Analyse d’images de BD

D’un point de vue visuel…

Traitement d’images




D’un point de vue visuel…

• Peu de propositions pour l’analyse sémantique

– Encodages XML [ComicsML11, CBML12]

– Une ontologie [Rissen12]

– Ordonnancement des cases [Ponsard12]


…d’un point de vue sémantique…





• Pas de travaux portant sur une approche générale mettant en interaction analyse visuelle et sémantique de la bande dessinée

• Existence de nombreux exemples appliqués à d’autres domaines


...et à la jonction des deux.




…d’un point de vue sémantique…D’un point de vue visuel…


• Prendre en compte la connaissance a priori…– Ontologies, représentation d’un domaine

particulier pour une tâche donnée [Uschold96]

– Notions de concept, de relation, d’attribut et d’individu

• …dans un cadre de raisonnement formel– OWL, basé sur les logiques de description

– Classification : subsomption, instanciation

– Vérification : satisfiabilité, consistance

Représenter les connaissances liées aux images…

Systèmes d’analyse hybride d’images

Voiture ≡ Vehicule and possède 4 Roue

Véhicule

Roue

possède

couleurattribut

diamètreattribut

VéhiculeVoiture isA

« Renault Clio »


Fossé sémantique :

« Manque de concordance entre l’information qu’il est possible d’extraire automatiquement de données et ce que ces mêmes données signifient pour un utilisateur dans un contexte particulier »

[Smeulders00]

• Annotation d’images [Tousch12]

• Description du contenu visuel [Bannour11]

• Guidage dynamique de l’analyse d’images [Forestier13]


…pour lever les ambiguïtés sémantiques.

Plage, mer, arbre, vacances…





Image de plageJaune et en bas = sable

Bleu/blanc et en haut = cielBleu et au milieu = mer




[Smeulders00]







A = mer ?D = sable ?

C = mer ?

D

A B

C




[Smeulders00]





En résumé

• Peu de travaux portant sur la BD

– Domaine d’intérêt récent

– Efforts concentrés sur le traitement d’images

• Les ontologies ont la capacité de

– Formaliser les codes de la bande dessinée

– Servir de cadre à des recherches complexes et non ambiguës

– Renforcer l’analyse visuelle des planchesTraitement d’images



19



Sequence

de lecture


Analyse

contextuelle

Recherche

d’information



Objectifs

• Interaction avec un système de traitement d’images

– Structurer les données manipulées

– Évaluation et validation de ces données

• Recherche efficace et déduction d’information

– Représenter fidèlement le domaine de la bande dessinée

– Faire émerger la sémantique des données

Deux ontologies et une base d’évaluation annotée


Vue d’ensemble

Ontologie bande dessinée

Base d’évaluation

Ontologie image Ontologie bande dessinéeOntologie image



• Image

– Matériau initial

– Propriétés caractéristiques

• Région d’intérêt (ROI pour « Region Of Interest »)

– Polygone, ligne, point…

– Format Well-Known Text (WKT)

– Coordonnées dans l’image

Image, régions d’intérêt…

Ontologie image

hasWidthhasHeight

hasResolutionhasFormatisLosslessinverseFunctional

Image

ROI

hasROI

hasWKThasArea

hasXhasY


• Différents extracteurs pour différents type d’objets– Spécificité des traitements– Type d’objets recherchés prédéfini

• Différentes natures d’extracteurs– Automatique = propositions– Vérité terrain (Ground Truth) =

références

• Propagation aux régions d’intérêt

Ontologie image

…extracteurs, vérité terrain…

ROIGT ≡ ROI and hasExtractor some GroundTruthROIAuto ≡ ROI and hasExtractor some ExtractorAuto

Extractor

hasExtractor

Image

ROI

hasROI

inverseFunctional

hasROIType

ROIAuto

ROIGT

ExtractorAuto

GroundTruth

isAisA

isA isA

disjointWith: ExtractorAuto disjointWith: GroundTruth

disjointWith: ROI GT

disjointWith: ROI Auto

Image, régions d’intérêt…


• Mise en correspondance des régions d’intérêt– Entre une proposition et une

référence– Type et position des éléments– Relations d’intersections

spatiales– Une évaluation par

correspondance

Ontologie image

…et mécanisme d’évaluation.

Image

ROI

ROIAuto

ROIGT

Extractor

ExtractorAuto

GroundTruth

Evaluation

hasROI

isA

hasExtractor

hasCandidatehasReference

isA

isA isA

functionalfunctional

Image, régions d’intérêt… …extracteurs, vérité terrain…


• Mise en correspondance des régions d’intérêt– Entre une proposition et une

référence– Type et position des éléments– Relations d’intersections

spatiales– Une évaluation par

correspondance

Ontologie image

Validation ≡ Evaluation and hasFScore some double[>=s]Error ≡ Evaluation and hasFScore some double[<s]

Image

ROI

ROIAuto

ROIGT

Extractor

ExtractorAuto

GroundTruth

Evaluation

ErrorValidation

hasRecallhasPrecision

hasFScore

hasROI

isA

hasExtractor


disjointWith: ValidationdisjointWith: Error

isAisA

isA

isA isA

containsoverlapsdisjoint

functionalfunctional

transitivesymmetric

…et mécanisme d’évaluation.Image, régions d’intérêt… …extracteurs, vérité terrain…




Vue d’ensemble

Ontologie image Ontologie bande dessinée

Image

ROI

ROIAuto

ROIGT

Extractor

ExtractorAuto

GroundTruth

Evaluation

ErrorValidation

hasROI

isA

hasExtractor


isAisA

isA

isA isA


Ontologie image

Image

ROI

ROIAuto

ROIGT

Extractor

ExtractorAuto

GroundTruth

Evaluation

ErrorValidation

hasROI

isA

hasExtractor


isAisA

isA

isA isA




Des albums, des planches…

• Informations bibliographiques

– Année, auteur, collection, etc.

– Contexte de l’œuvre

• Planche ≠ page

Comic

Plate

hasPlate

hasNextPlate

hasCollectionhasTitle

hasDrawerhasWriterrightToLeft

hasDatehasISBN

hasWebsite

hasNumberonDoublePage



…leur contenu…

• Composants graphiques principaux

– Case, bulle, flèche, texte, personnage

– Structure arborescente

– Notion de succession

Comic

Plate

Panel

Balloon

Character

TextLine Tail

hasPlate

hasPanel

hasBalloon

hasCharacter

hasTextLine hasTail

hasDirection

hasRank

hasRankhasText

hasRank

hasNextBalloon

hasNextTextLine

hasNextPanel

hasNextPlate

hasCollectionhasTitle

hasDrawerhasWriterrightToLeft

hasDatehasISBN

hasWebsite

hasNumberonDoublePage

Des albums, des planches…



…ses contraintes…

• Contraintes fortes sur le domain et le range des relations– Une planche fait partie d’un album– Une case appartient à une planche– Une bulle appartient à une case– Une ligne appartient à une bulle– Un personnage appartient à une case

– Appartenance transitivehasContent

isA isA isAisAisA

type: transitive

propriétés

domain: Comic

range: Plate

type: inverseFunctional

domain: Panel

range: Balloon


propriétés

domain: Balloon

range: TextLine


domain: Panel

range: Character


domain: Plate

range: Panel


propriétés propriétéspropriétéspropriétés

hasCharacterhasPlate hasPanel hasBalloon hasTextLine

hasContent

isA isA isAisAisA

type: transitive

propriétés

domain: Comic

range: Plate


domain: Panel

range: Balloon


propriétés

domain: Balloon

range: TextLine


domain: Panel

range: Character


domain: Plate

range: Panel




hasContent

isA isA isAisAisA

type: transitive

propriétés

domain: Comic

range: Plate


domain: Panel

range: Balloon


propriétés

domain: Balloon

range: TextLine


domain: Panel

range: Character


domain: Plate

range: Panel




hasContent

isA isA isAisAisA

type: transitive

propriétés

domain: Comic

range: Plate


domain: Panel

range: Balloon


propriétés

domain: Balloon

range: TextLine


domain: Panel

range: Character


domain: Plate

range: Panel




hasContent

isA isA isAisAisA

type: transitive

propriétés

domain: Comic

range: Plate


domain: Panel

range: Balloon


propriétés

domain: Balloon

range: TextLine


domain: Panel

range: Character


domain: Plate

range: Panel




hasContent

isA isA isAisAisA

type: transitive

propriétés

domain: Comic

range: Plate


domain: Panel

range: Balloon


propriétés

domain: Balloon

range: TextLine


domain: Panel

range: Character


domain: Plate

range: Panel




Des albums, des planches… …leur contenu…



…et ses spécialisations.

• Spécialisation des bulles, lignes de texte et personnages

NarrativeBalloon ≡ hasTextLine some TextLineNarrativeTextLine ≡ isLineOf some NarrativeBalloon

SpeechBalloon ≡ NarrativeBalloon and hasTail some TailSpokenTextLine ≡ isLineOf some SpeechBalloon

Speaker ≡ Character and says some SpeechBalloon

BalloonCharacter TextLine

NarrativeBalloon

NarrativeTextLine

SpeechBalloon

SpeakerSpoken

TextLine

isA

isA

isA

isA

isA

says

domain: CharacterRange: SpeechBalloon

Des albums, des planches… …ses contraintes……leur contenu…



Composition des deux ontologies

Ontologie bande dessinéeOntologie image

Imageimage ≡ Platebd

Panelbd ≡ ROIimage and hasExtractor some (hasROIType value « Panel »)Balloonbd≡ ROIimage and hasExtractor some (hasROIType value « Balloon »)

…

Image

ROI

Extractor

Plate

Tail

TextLine

Balloon

Panel Character


Vue d’ensemble


Ontologie image

Image

ROI

ROIAuto

ROIGT

Extractor

ExtractorAuto

GroundTruth

Evaluation

ErrorValidation

hasROI

isA

hasExtractor


isAisA

isA

isA isA



Comic

Plate

Panel

Balloon

Character

TextLine Tail

hasPlate

hasPanel

hasBalloon

hasCharacter

hasTextLine hasTail

hasNextBalloon

hasNextTextLine

hasNextPanel



Construction d’une vérité terrain…

• Absence de base d’évaluation publique

• Hétérogénéité du jeu de données– 100 pages, 850 cases, 1092 bulles,

1550 personnages et 4691 lignes de texte– BD anciennes, manga, comics, webcomics– Obtention des droits auprès des auteurs et des éditeurs

• Annotations– Visuelles : segmentation des éléments– Sémantiques : numérotation, forme des bulles, orientation

des flèches, type et transcription du texte– Liens bulle <> texte et bulle <> personnage

• Mise en ligne en 2013 sous le nom de base « eBDtheque », à disposition de la communauté scientifique


…à laquelle confronter notre modèle.Construction d’une vérité terrain…

40

50

60

70

80

90

100

10 20 30 40 50 60 70 80 90 100

Pro

po

rtio

n d

'élé

me

nts

co

nfo

rme

s au

m

od

èle

(%

)

Pourcentage de superficie couvert par le conteneur direct (%)

Cases

Bulles

Lignes de texte

Personnages


• Évaluation de la consistance entre – La base eBDtheque (A-Box)– Notre conceptualisation (T-Box)

• Appartenance basée sur l’intersection spatiale– Recherche des taux de recouvrement

optimaux pour notre base

• Suppression des éléments inconsistants– Bon résultats pour les cases et les

personnages– Texte et bulles logiquement en retrait– 18,4% des lignes de texte de notre base se

trouvent en dehors de toute bulle

Cases Bulles Texte Personnages

99,6% 87,4% 81,6% 94,9%Proportion des éléments de la base eBDtheque cohérents avec les contraintes de l’ontologie

35



Sequence

de lecture


Analyse

contextuelle

Recherche

d’information



Problématique

• Navigation case par case souvent trop rigide

Proposer au lecteur une navigation séquentielle respectueuse de l’expérience originale

𝑆𝑢𝑖𝑣𝑎𝑛𝑡 𝐶𝑖 , 𝐶𝑗 ← 𝑆𝑢𝑑 𝐶𝑖 , 𝐶𝑗𝑆𝑢𝑖𝑣𝑎𝑛𝑡 𝐶𝑖 , 𝐶𝑗 𝑏𝑑

← ¬𝑆𝑢𝑑 𝐶𝑖 , 𝐶𝑗 , ¬𝑆𝑢𝑑 𝐶𝑗 , 𝐶𝑖 , 𝐸𝑠𝑡 𝐶𝑖 , 𝐶𝑗

𝑆𝑢𝑖𝑣𝑎𝑛𝑡 𝐶𝑖 , 𝐶𝑗 𝑚𝑎𝑛𝑔𝑎← ¬𝑆𝑢𝑑 𝐶𝑖 , 𝐶𝑗 , ¬𝑆𝑢𝑑 𝐶𝑗 , 𝐶𝑖 , 𝐸𝑠𝑡 𝐶𝑗 , 𝐶𝑖

• Comment définir 𝑆𝑢𝑑 et 𝐸𝑠𝑡– Relations spatiales topologiques (RCC8)


Relations spatiales

• Relations topologiques (RCC8)– Cases séparées (SP)– Cases superposées (PO)– Cases imbriquées (CO)

ROI Panel


Relations spatiales


X SP Y

Sud(C1,C3)

𝑆𝑢𝑑 𝐶𝑖 , 𝐶𝑗 ← 𝑆𝑃 𝐶𝑖 , 𝐶𝑗 , (∀ 𝑦𝑖𝑖 , 𝑦𝑗𝑖 , 𝑦𝑗𝑖 > 𝑦𝑖𝑖)

𝐸𝑠𝑡 𝐶𝑖 , 𝐶𝑗 ← 𝑆𝑃 𝐶𝑖 , 𝐶𝑗 , (∀ 𝑥𝑖𝑖 , 𝑥𝑗𝑖 , 𝑥𝑗𝑖 > 𝑥𝑖𝑖)

Est(C1,C2)


Relations spatiales


X SP Y

Sud(C1,C3)

𝑆𝑢𝑑 𝐶𝑖 , 𝐶𝑗 ← 𝑆𝑃 𝐶𝑖 , 𝐶𝑗 , (∀ 𝑦𝑖𝑖 , 𝑦𝑗𝑖 , 𝑦𝑗𝑖 > 𝑦𝑖𝑖)

𝐸𝑠𝑡 𝐶𝑖 , 𝐶𝑗 ← 𝑆𝑃 𝐶𝑖 , 𝐶𝑗 , (∀ 𝑥𝑖𝑖 , 𝑥𝑗𝑖 , 𝑥𝑗𝑖 > 𝑥𝑖𝑖)

𝑆𝑢𝑑 𝐶𝑖 , 𝐶𝑗 ← 𝑃𝑂 𝐶𝑖 , 𝐶𝑗 , 𝑦𝑗𝑐 > 𝑦𝑖𝑐 , 𝑦𝑗𝑐 − 𝑦𝑖𝑐 > |𝑥𝑗𝑐 − 𝑥𝑖𝑐|

𝐸𝑠𝑡 𝐶𝑖 , 𝐶𝑗 ← 𝑃𝑂 𝐶𝑖 , 𝐶𝑗 , 𝑥𝑗𝑐 > 𝑥𝑖𝑐 , 𝑥𝑗𝑐 − 𝑥𝑖𝑐 > |𝑦𝑗𝑐 − 𝑦𝑖𝑐|

Sud(C1,C3)Est(C1,C2)

Est(C1,C2)


Relations spatiales


X SP YX CO Y

Sud(C1,C3)Sud(C1,C3)Est(C1,C2)

Est(C1,C2)


Identifier les parcours possibles…

Génération de la séquence

• Génération d’un ordre partiel– Conservation de l’indéterminisme de la séquence– Attribution d’un rang à chaque case

• Intégration au modèle via des règles SWRL– Sélection des cases provenant d’une même page

et d’un même extracteur– Assertion d’une relation de succession

1 2

3

5

3

4

6

Panel

hasNextPanel



…puis en évaluer la pertinence.

• Expérimentations sur les cases de la base eBDtheque– Évaluation des liens plutôt que des rangs– 849 cases pour 100 pages

• Généralisable aux bulles et aux lignes de texte

Jeu de données Nombre de relations Résultats

BD0 (eBDtheque) 749 94,65%



BD1 = BD0 \ I (Inclusions) 746 95,03%




BD2 = BD1 \ DP (Doubles pages) 703 97,58%








…puis en évaluer la pertinence.

• Expérimentations sur les cases de la base eBDtheque– Évaluation des liens plutôt que des rangs– 849 cases pour 100 pages

• Généralisable aux bulles et aux lignes de texte














BD3 = BD2 \ Outlier 581 99%


44



Sequence

de lecture


Analyse

contextuelle

Recherche

d’information



Analyse contextuelle des planches

• Point de jonction entre les deux aspects du projet

• Mise en œuvre du cadre pour une compréhension progressive d’une planche


Analyse contextuelle des planches

• Point de jonction entre les deux aspects du projet

• Mise en œuvre du cadre pour une compréhension progressive d’une planche

Étape 2 : évaluation des

hypothèses

Étape 3 : déduction

d’information

Étape 1 : formulation

d’hypothèses


Des éléments les plus simples…

Boucle d’interaction

Cohérence des propositions

avec le modèle

Classification des différents

éléments

Proposition de cases, bulles et lignes de texte

2 cases (P)

5 bulles (B)

9 lignes (T)

2 flèches (Q)




Mises à l’écart des propositions

incohérentes

Classification des différents

éléments


2 cases (P)

5 bulles (B)

7 lignes (T)

2 flèches (Q)





incohérentes

Classification des éléments

validés


2 bulles de narration (NB)

2 bulles de dialogue (SB)

2 lignes de narration (NT)

2 lignes de dialogue (ST)


…aux éléments plus complexes.



incohérentes


validés

Estimation des zones

personnages




2 personnages (C)




Correction et évaluation des zones


validés


personnages




2 personnages (C)




Correction et évaluation des zones

Liaison des personnages

aux bulles


personnages




2 personnages (C)


Performances du système

En environnement contrôlé…

– Objets à évaluer fournis par l’algorithme correspondant– Autres objets fournis par la vérité terrain

Objets évalués Rappel (%)

Cases (Max = 99,6%)

Hypothèses [Rigaud14b] 81,24

Validation 80,69 (-0,55)

Bulles(Max = 87,4%)

Hypothèses [Rigaud14c] 57,90


Lignes de texte (Max = 81,6%)

Hypothèses [Rigaud13c] 61,00

Hypothèses + OCR 60,13


Personnages (Max = 94,9%)

Hypothèses 19,28

Extraction 23,31 (+4,03)


Objets évalués Rappel (%) Précision (%)

Cases (Max = 99,6%)

Hypothèses [Rigaud14b] 81,24 86,55

Validation 80,69 (-0,55) 87,03 (+0,48)

Bulles(Max = 87,4%)

Hypothèses [Rigaud14c] 57,90 73,84

Validation 54,79 (-3,11) 88,76 (+14,92)


Hypothèses [Rigaud13c] 61,00 19,66

Hypothèses + OCR 60,13 42,43

Validation 44,54 (-16,46) 65,05 (+22,62)


Hypothèses 19,28 26,91

Extraction 23,31 (+4,03) 33,55 (+6,64)

Validation 21,57 (-1,74) 40,52 (+6,97)

• Limiter le biais lié à l’interdépendance des éléments

Objets évalués Rappel (%) Précision (%) F-mesure (%)

Cases (Max = 99,6%)

Hypothèses [Rigaud14b] 81,24 86,55 83,81

Validation 80,69 (-0,55) 87,03 (+0,48) 83,74 (-0,07)

Bulles(Max = 87,4%)

Hypothèses [Rigaud14c] 57,90 73,84 64,91

Validation 54,79 (-3,11) 88,76 (+14,92) 67,75 (+2,84)


Hypothèses [Rigaud13c] 61,00 19,66 29,75

Hypothèses + OCR 60,13 42,43 49,75

Validation 44,54 (-16,46) 65,05 (+22,62) 52,88 (+3,13)


Hypothèses 19,28 26,91 22,47

Extraction 23,31 (+4,03) 33,55 (+6,64) 27,51 (+5,04)

Validation 21,57 (-1,74) 40,52 (+6,97) 28,16 (+0,65)


0

0,2

0,4

0,6

0,8

1Cases

Liensbulle-perso.

PersonnagesTexte

Bulles


…puis en complète autonomie.

• Hypothèses– Extraction des cases, bulles

et lignes de texte

• Validation des hypothèses

• Hypothèses– Position des personnages (P)

• Validation et déduction– Liens bulles de

dialogue/personnages (BDP)

Limite théoriqueRésultats (F-score)



0

0,2

0,4

0,6

0,8

1Cases

Liensbulle-perso.

PersonnagesTexte

Bulles




et lignes de texte


• Hypothèses– Position des personnages (P)






0

0,2

0,4

0,6

0,8

1Cases

Liensbulle-perso.

PersonnagesTexte

Bulles




et lignes de texte


• Hypothèses– Position des personnages






0

0,2

0,4

0,6

0,8

1Cases

Liensbulle-perso.

PersonnagesTexte

Bulles




et lignes de texte


• Hypothèses– Position des personnages


dialogue/personnages



58



Sequence

de lecture


Analyse

contextuelle

Recherche

d’information



• Mécanismes de recherche pas toujours optimaux

Recherche d’information

Recherche par mots clés / par l’exemple

(+) Facile à utiliser

(-) Trouver les bons mots clés / le bon exemple

(-) Hétérogénéité / fossé sémantique

(-) Incomplétude des résultats

Recherche par navigation dans une arborescence

(+) Très intuitifs

(+) Pas de connaissance a priori requise

(-) Arborescence statique définie en amont

Recherche par requête formelle (SQL, SPARQL)

(+) Permet d’obtenir des résultats complets

(-) Difficile à utiliser, peu intuitifs

(-) Connaissance de la structure des données nécessaire


Recherche par facettes« Navigation Conceptuelle Abstraite » (ACN) [Ferré14]

(+) Intuitif (principe de navigation)(+) Structure dynamique (treillis)(+) Consistant (une requête renvoie toujours des résultats)(+) Complet (une requête renvoie toujours tous les résultats)

(-) Pas encore aussi efficace que les SGBD sur de larges jeux de données

Recherche d’information

Base de connaissances

intension(requête)

extension(résultats)

navigation

concept


• Informations structurées au sein d’un treillis de concepts

• Caractéristiques proches = proximité spatiale– Affiner une requête = concepts suivants– Élargir une requête = concepts précédents

• Génération et navigation dans le treillis coûteuse– Calcul d’intension (resp. extension)

d’ensembles d’objets (resp. attributs)– Opérations d’intersection d’ensembles à la volée

Navigation dans un treillis


• Adaptation et optimisation de l’algorithme LOA [Demko11]– Basé sur un comptage des objets de l’extension– Intégration dans une bibliothèque Java

pour la gestion des treillis

• Transformation de l’extension (resp. intension) de chaque attribut (resp. observation) en mot binaire– La taille des mots correspond au nombre d’observations

(resp. attributs)– Les données doivent être triées

• Calcul de l’extension d’un ensemble d’attributs par une opération de ET logique entre les extensions de ses éléments

Optimisation du calcul des successeurs

p1 p2 p3 p4 p5

Bulle x x x x

Wide x x

High x x

Medium x x

Character x x

p1 p2 p3 p4 p5

Bulle 1 1 1 1 0

Wide 0 1 0 0 1

High 1 0 0 1 0

Medium 0 0 1 0 1

Character 0 0 0 1 1

{BulleHigh

Character}0 0 0 1 0

p1 p2 p3 p4 p5

Bulle 1 1 1 1 0

High 1 0 0 1 0

Character 0 0 0 1 1


• Deux jeux de données extraits du modèle– 848 cases / 100 attributs (7 attributs par case en moyenne)– 848 cases / 3533 attributs (15 attributs par case en moyenne)– 0,18 seconde pour 500 concepts sélectionnés aléatoirement

Expérimentations

Successeurs immédiats Prédécesseurs immédiats

|O1| = 848|I1| = 100

|O1| = 848|I2| = 3533

|O1| = 100|I1| = 848

|O2| = 3533|I1| = 848

Bordat + TreeSet 3,06 s. 11767,52 s. 549,76 s. 994,00 s.

Bordat + BitSet 0,77 s. 196,58 s. 62,39 s. 9,77 s.

LOA + TreeSet 0,29 s. 11,26 s. 5,65 s. 1183,75 s.

LOA + BitSet 0,02 s. (14x) 0,15 s. (75x) 0,24 s. (24x) 1,20 s. (828x)

64



Sequence

de lecture


Analyse

contextuelle

Recherche

d’information


65Contexte État de l’art Cadre Analyse contextuelle ConclusionRechercheSéquence

• La bande dessinée face au numérique

– Nouveaux usages, nouveaux mediums

– Masse critique, indexation, préservation

• Contexte de projet « eBDtheque »

– Aspect traitement d’images

– Aspect représentation des connaissances

– Synergie

Conclusions

Traitement d’images(Thèse de Christophe Rigaud)


(Thèse de Clément Guérin)



Conclusions


Sequence

de lecture

Analyse

contextuelle

Recherche

d’information


Conclusions

Conceptualisation de la tâche de traitement d’images

Indépendante du domaine d’étude

Structure les informations en provenance d’extracteurset de bases de référence pour en permettre l’évaluation

Un cadre compose d’une

Ontologie image...


Conclusions

Conceptualisation du domaine de la bande dessinée

Intègre des contraintes fortes pour une exploitation en analyse d’images

Permet de modéliser de manière formelle90% d’une base hétérogène

...interagissant avec une

ontologie du domaine de

la bande dessinee...


Conclusions

Représentative de la diversité du domaine

Plusieurs milliers d’annotations visuelles et sémantiques

Disponible en ligne pour la communauté scientifiqueet utilisée par plusieurs équipes à l’université de Brême, l’université de Pékin et à l’Indian Institute of Science.

Clément Guérin, Christophe Rigaud, Antoine Mercier, et al. eBDtheque: a representative database of comics.

ICDAR, Washington DC, 2013

...valide sur une base

d’evaluation annotee.


Conclusions

Résultats cohérents sur la très grande majorité des planches

Laisse le lecteur libre de ses choix en cas d’ambiguïté

Norbert Tsopze, Clément Guérin, Karell Bertet et Arnaud Revel. Ontologies et relations spatiales dans la lecture d'une bande dessinée.

IC, Paris, 2012

Mis en oeuvre pour le

calcul de la sequence de

lecture...


Conclusions

Détection d’éléments complexes sans apprentissage ni apriori visuel mais grâce à une acquisition progressive ducontenu structurel de la planche

Amélioration générale des extractions grâce à une nette augmentation de la précision

Christophe Rigaud, Clément Guérin, Dimosthenis Karatzas, Jean-Christophe Burie et Jean-Marc Ogier. Knowledge-driven understanding of images in comic books.

Accepted for publishing in IJDAR.

Clément Guérin, Christophe Rigaud, Karell Bertet, Jean-Christophe Burie, Arnaud Revel et Jean-Marc Ogier. Réduction de l'espace de recherche pour les personnages de bandes dessinées.

RFIA, Rouen, 2014

...l’analyse contextuelle

des planches...


Conclusions

Amélioration sensible du temps de calcul des successeurs immédiats d’un concept

Application dans un contexte temps réel

Clément Guérin, Karell Bertet et Arnaud Revel. An approach to Sematic Content Based Image Retrieval using Logical Concept Analysis. Application to comicbooks.

« What can FCA do for AI? », Workshop of ECAI, Montpellier, 2012

Clément Guérin, Karell Bertet et Arnaud Revel. An efficient Java implementation of the immediate successors calculation.

CLA, La Rochelle, 2013

...et la recherche

d’information.


Perspectives


Sequence

de lecture

Analyse

contextuelle

Recherche

d’information


Développer les capacités de raisonnement

Intégration d’un raisonneur spatial formel

Approche logique floue pour les personnages

Evolution du modele

Perspectives


Extension prochaine aux bulles et aux lignes de texte

Application potentielle de lecture automatisée

Calcul de la

sequence de lecture

Perspectives


Limiter la chute de rappel dans les résultats

Augmenter le nombre d’itérations

Enrichir la boucle d’interaction de l’analyse contextuelle

PIA 2014 accepté avec l’entreprise Actialuna et le LIP6

Analyse

contextuelle

Perspectives


Poursuivre les travaux en recherche d’information

Tester sur de plus larges jeux de données

Eviter l’explosion combinatoire des attributs

ANR 2015 EXPION déposée

Recherche

d’information

Perspectives

78

Références bibliographiques

[Arai10]Kohei Arai et Herman Tolle. Method for Automatic E-Comic Scene Frame Extraction for Reading Comic on Mobile Devices.In Seventh International Conference on Information Technology : New Generations, pages 370-375, 2010

[Arai11]Kohei Arai et Herman Tolle. Method for Real Time Text Extraction of Digital Manga Comic.International Journal of Image Processing (IJIP), vol. 4, no. 6, pages 669-676, 2011

[Bannour11]Hichem Bannour et Céline Hudelot. Towards ontologies for image interpretation and annotation.In Content-Based Multimedia Indexing (CBMI), pages 211-216. IEEE, 2011

[CBML12]John A Walsh. Comic Book Markup Language : An Introduction and Rationale.Digital Humanities Quarterly (DHQ), vol. 6, no. 1, pages 1-50, 2012

[ComicsML11] Jason McIntosh. ComicsML, 2011

[Demko11]Christophe Demko et Karell Bertet. Generation algorithm of a concept lattice with limited object access. In International Conference on Concept Lattices and Their Applications (CLA), pages 239-250, 2011

[Ferré14] Sébastien Ferré. Reconciling Expressivity and Usability in Information Access -> from File Systems to the Semantic Web.Habilitation à diriger des recherches. 2014

[Forestier13]Germain Forestier, C. Wemmert et A. Puissant. Coastal Image Interpretation Using Background Knowledge and Semantics. Computers & Geosciences, vol. 54, no. 4, pages 88-96, 2013

[Han07]Eunjung Han, Jonyeol Yang, Hwangkyu Yang et Keechul Jung. Automatic Mobile Content Conversion Using Semantic Image Analysis. LNCS, pages 298-307, 2007

[Ho11]Anh Khoi Ngo Ho, Jean-Christophe Burie et Jean-Marc Ogier. Comics page structure analysis based on automatic panel extraction. In 9th IAPR International Workshop on Graphics Recognition, 2011

79


[Ho12]Anh Khoi Ngo Ho, Jean-Christophe Burie et Jean-Marc Ogier. Panel and Speech Balloon Extraction from Comic Books.In 10th IAPR International Workshop on Document Analysis Systems, pages 424-428. IEEE, 2012

[Ho13] Hoang Nam Ho, Christophe Rigaud, Jean-Christophe Burie et Jean-Marc Ogier. Redundant structure detection in attributedadjacency graphs for character detection in comics books. In International Workshop on Graphics Recognition (GREC), 2013

[Li12]Luyuan Li, Yongtao Wang, Zhi Tang et Liangcai Gao. Automatic comic page segmentation based on polygon detection. Multimedia Tools and Applications, vol. 69, no. 1, pages 171-197, 2012

[Li13]Luyuan Li, Wang Zhi Tang, Xiaoqing Lu et Liangcai Gao. Unsupervised speech text localization in comic images.In International Conference on Document Analysis and Recognition (ICDAR), pages 1190-1194, 2013

[Ponsard12]Christophe Ponsard, Ravi Ramdoyal et Daniel Dziamski. An OCR-Enabled Digital Comic Books Viewer.Computers Helping People with Special Needs, vol. 7382, pages 471-478, 2012

[Renouf07]Arnaud Renouf, Régis Clouard et Marinette Revenu. How to formulate image processing applications?In International Conference on Computer Vision Systems, 2007

[Rigaud12]Christophe Rigaud, Norbert Tsopze, Jean-Christophe Burie et Jean-Marc Ogier. Extraction robuste des cases et du texte de bandes dessinées. In Colloque International Francophone sur l'Ecrit et le Document (CIFED), pages 349-360, 2012

[Rigaud13a]Christophe Rigaud, Jean-Christophe Burie, Jean-Marc Ogier et Dimosthenis Karatzas. Speech balloon contour classification in comics. In International Workshop on Graphics Recognition (GREC), pages 23-25, 2013

[Rigaud13b]Christophe Rigaud, Jean-Christophe Burie, Jean-Marc Ogier, Dimosthenis Karatzas et Joost Van De Weijer. An Active Contour Model for Speech Balloon Detection in Comics.In International Conference on Document Analysis and Recognition (ICDAR), pages 1240-1244. IEEE, 2013

80


[Rigaud13c]Christophe Rigaud, Dimosthenis Karatzas, Joost Van De Weijer, Jean-Christophe Burie et Jean-Marc Ogier. Automatic Text Localisation in Scanned Comic Books. In International Conference on Computer Vision Theory and Applications, pages 814-819, 2013

[Rigaud14a]Christophe Rigaud, Dimosthenis Karatzas, Jean-Christophe Burie et Jean-Marc Ogier. Color descriptor for content-based drawingretrieval. In International Workshop on Document Analysis Systems (DAS), pages 267-271, 2014

[Rigaud14b] Christophe Rigaud. Segmentation and indexation of complex objects in comic book image. Ph.D. thesis, 2014.

[Rigaud14c]Christophe Rigaud et Clément Guérin. Localisation contextuelle des personnages de bandes dessinées. In Colloque International Francophone sur l’Écrit et le Document (CIFED), 2014

[Rissen12] Paul Rissen. A Comics Ontology, 2012

[Smeulders00]Arnold W.M. Smeulders, Marcel Worring, Simone Santini, Amarnath Gupta et Ramesh Jain. Content-based image retrieval at the end of the early years. In Pattern Analysis and Machine Intelligence, vol. 22, no. 12, pages 1349-1380, 2000

[Su11]Chung-Yuan Su, Ray-I Chang et Jen-Chang Liu. Recognizing text elements for svg comic compression and its novel applications. In International Conference on Document Analysis and Recognition (ICDAR), pages 1329-1333, 2011

[Takayama12]Kohei Takayama, Henry Johan et Tomoyuki Nishita. Face detection and face recognition of cartoon characters using featureextraction. In Image, Electronics and Visual Computing Workshop, 2012

[Tousch12]Anne-Marie Tousch, Stéphane Herbin et Jean-Yves Audibert. Semantic hierarchies for image annotation: a survey. Pattern Recognition, vol. 45, no. 1, pages 333-345, 2012

[Uschold96]Mike Uschold et Michael Gruninger. Ontologies: Principles, methods and applications.The Knowledge Engineering Review, vol. 11, no. 02, pages 93-136, 1996

81

Crédits illustrations

Slide 2 Eri Inoue Kyoumen Gensoukyoku

Slide 2Will Carlton

Szymon KudranskiTodd McFarlane

Spawn #206, Edition Image Comics

Slides 2, 5, 6 et 36Olivier Jolivet

Pascal BoisgibaultBoston Police : L’Affaire Pradi, Edition Clair de Lune

Slides 2 et 39 Alain Saint-Ogan Prosper et le Monstre Marin, Edition Hachette

Slide 39 Chris Ware Acme Novelty Library, Edition New York Pantheon

Slides 42 à 47 Jay Scott Pike Boy Love Girls #41, Edition Lev Gleason

Merci aux auteurs, aux éditeurs et à la Cité Internationale de la Bande Dessinée et de l’Imagepour leur gracieuse autorisation d’utilisation de leurs œuvres pour ces travaux.

82Pour aller plus loin…

Homogénéité de la vérité terrain


Outil d’annotation de la vérité terrain


Ordre de lecture


Exemples de différences


Exemples de différences


Position des personnages par rapport aux bulles

BulleW

N

E

SSW SE

NW NE

A1

A2

H1

H2


Évaluation de l’analyse contextuelle


Prédécesseurs immédiats

• Parcours dans les deux sens– Successeurs immédiats : contexte normal– Prédécesseurs immédiats : contexte inversé

p1 p2 p3 p4 p5

Bulle x x x x

Wide x x

High x x

Medium x x

Character x x

b w h m c

p1 x x

p2 x x

p3 x x

p4 x x x

p5 x x x


Algorithme Limited Object Access [Demko11]

Documents

Proposition d’un cadre pour l’analyse automatique, l’interprétation … · 2015-01-27 · Proposition d’un cadre pour l’analyse automatique, l’interprétation et la recherche