View
107
Download
0
Category
Preview:
Citation preview
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 …
Recommended