Image Processing Image Processing usingusing

Finite AutomataFinite AutomataJean-Christophe JanodetJean-Christophe Janodet

Journée SATTICJournée SATTIC

Représentation des imagesReprésentation des imagesavec des automatesavec des automates

Travaux de K. Culik et J. Kari (début Travaux de K. Culik et J. Kari (début des 90’s)des 90’s)

PlanPlan1.1. Images de résolution multipleImages de résolution multiple

2.2. Images dénotées par des automatesImages dénotées par des automates

3.3. Applications de cette représentationApplications de cette représentation

Image de résolution finieImage de résolution finie

Image = tableau de 2Image = tableau de 2k k x 2x 2kk pixels pixels

= fonction= fonction{1,2,…, 2{1,2,…, 2kk}x{1,2,…, 2}x{1,2,…, 2kk} → C} → C

avecavec C = {Blanc, Noir} pour les images C = {Blanc, Noir} pour les images

binairesbinaires C = [0,1] pour les images à niveau de C = [0,1] pour les images à niveau de

grisgris C = [0,1]C = [0,1]33 pour les images couleurs pour les images couleurs

Relation Image / AutomateRelation Image / Automate

Plutôt que des coordonnées dans un Plutôt que des coordonnées dans un tableau, utilisation de mots sur l’alphabet tableau, utilisation de mots sur l’alphabet {0,1,2,3} comme adresses des pixels{0,1,2,3} comme adresses des pixels

Plutôt qu’une fonction quelconque dans C,Plutôt qu’une fonction quelconque dans C, une image binaire (pixels noirs et blancs) est une image binaire (pixels noirs et blancs) est

représentée par un DFA (adresses des points représentée par un DFA (adresses des points noirs)noirs)

une image à niveau de gris est représentée une image à niveau de gris est représentée par un automate à multiplicité (WFA)par un automate à multiplicité (WFA)

une image couleur est représentée par 3 WFAune image couleur est représentée par 3 WFA

Adressage des pixelsAdressage des pixels

Pixels désignés par des mots de Pixels désignés par des mots de ΣΣkk, avec , avec ΣΣ = = {0,1,2,3} plutôt que des couples de {1,2,…, {0,1,2,3} plutôt que des couples de {1,2,…, 22kk}x{1,2,…, 2}x{1,2,…, 2kk}}

Image de résolution 2Image de résolution 2kk x 2 x 2kk = fonction f : = fonction f :ΣΣkk → C → C

Image de résolution Image de résolution multiplemultiple

DéfinitionDéfinition

Généralisation : Image = fonctionGénéralisation : Image = fonction

f :f :ΣΣ** → C → C

telle que pour tout k ≥ 0, la restriction telle que pour tout k ≥ 0, la restriction de f à de f à ΣΣkk, notée f, notée fk k , soit une image de , soit une image de résolution 2résolution 2kk

Intuitivement, on souhaite que pour tout Intuitivement, on souhaite que pour tout k≥0, fk≥0, fkk soit une approximation de f soit une approximation de fk+1k+1 ; ; dans ce cas, fdans ce cas, f∞∞ est l’image « réelle » est l’image « réelle »

Cas des images à niveau Cas des images à niveau de grisde gris

f est f est Average PreservingAverage Preserving (AP), ssi pour tout mot w (AP), ssi pour tout mot wєєΣΣ**

f(w)=( f(w0) + f(w1) + f(w2) + f(w3) ) / 4f(w)=( f(w0) + f(w1) + f(w2) + f(w3) ) / 4

ExempleExemple

On considère f :On considère f :ΣΣ** → [0,1] défini par → [0,1] défini par

f(f(εε) = ) = ½½ , f(w1)=f(w2)=f(w), , f(w1)=f(w2)=f(w),

f(w0) = f(w) – (f(w0) = f(w) – (½½))|w|+2|w|+2 , f(w3) = f(w) + ( , f(w3) = f(w) + (½½))|w|+2|w|+2

Cas des images binairesCas des images binaires Image = fonction f :Image = fonction f :ΣΣ** → { Noir, Blanc } → { Noir, Blanc } Image = langage f (des points Noir) de Image = langage f (des points Noir) de ΣΣ**

Propriété AP pour images Propriété AP pour images binairesbinaires

En termes de fonction, f est AP siEn termes de fonction, f est AP si

f(w) = max( f(w0), f(w1), f(w2), f(w3) f(w) = max( f(w0), f(w1), f(w2), f(w3) ))

avec Blanc < Noiravec Blanc < Noir

En termes de langage, f est AP siEn termes de langage, f est AP si f est f est prefix closed prefix closed : si uv : si uv єє f, alors u f, alors u єє f f f est f est prefix trimmed prefix trimmed : si u : si u єє f, alors uv f, alors uv єє

f pour un v≠f pour un v≠εε

Contre-exempleContre-exempleTout langage f de Tout langage f de ΣΣ* * définit une image de résolution définit une image de résolution

multiple, mais elle n’est pas nécessairement AP multiple, mais elle n’est pas nécessairement AP

Images binaires et DFAImages binaires et DFA

Images à niveau de gris Images à niveau de gris et WFAet WFA

Images couleurs et WFAImages couleurs et WFA

Encodage / DécodageEncodage / Décodage

Passage d’un WFA de n états à une image Passage d’un WFA de n états à une image de N = 2de N = 2k k x 2x 2k k pixels :pixels :

Passage d’une image de résolution Passage d’une image de résolution multiple à un WFA : comme l’algorithme multiple à un WFA : comme l’algorithme DEES (Denis DEES (Denis et alet al, 2006), on crée des , 2006), on crée des états quand ils ne s’expriment pas comme états quand ils ne s’expriment pas comme combinaison linéaire des autres, sinon on combinaison linéaire des autres, sinon on ajoute des transitionsajoute des transitions

Exemple de constructionExemple de construction

Cas d’une image de Cas d’une image de résolution finierésolution finie

Problème :Problème : on n’a qu’une approximation de l’image on n’a qu’une approximation de l’image

réelle, la valeur de f(w) n’est pas connue réelle, la valeur de f(w) n’est pas connue pour tout mot wpour tout mot wєєΣΣ**

il s’agit d’exprimer un état comme il s’agit d’exprimer un état comme combinaison linéaire des autres…combinaison linéaire des autres…

Un problème d’inférence Un problème d’inférence grammaticale ?grammaticale ?

Une opportunité pour compresser les Une opportunité pour compresser les images …images …

Exemple, après Exemple, après compressioncompression

Opérations sur les WFAOpérations sur les WFA

Etant donnés A de n états et B de m Etant donnés A de n états et B de m états reconnaissant f et g, on peut états reconnaissant f et g, on peut construire :construire :

un WFA de m+n états reconnaissant f un WFA de m+n états reconnaissant f U g et faire la somme de deux imagesU g et faire la somme de deux images

un WFA de n états reconnaissant un WFA de n états reconnaissant λλf et f et rehausser le contraste (?)rehausser le contraste (?)

un un WFA de m.n états reconnaissant WFA de m.n états reconnaissant f.gf.g

Application du produitApplication du produit

Utilisation de transducteurs Utilisation de transducteurs : Zoom: Zoom

Autres transducteursAutres transducteurs

QuestionsQuestions

Quelle relation entre extraction du Quelle relation entre extraction du WFA d’une image et apprentissage WFA d’une image et apprentissage des WFA de langages des WFA de langages stochastiques ?stochastiques ?

Comment mesurer la distance entre Comment mesurer la distance entre deux WFA et faire de la classification deux WFA et faire de la classification d’images ?d’images ?

Autres …Autres …