TP — Langages d'images et automates 2D

Travaux pratiques · MP (option informatique) · 2014-2015 · OCaml

Cours : Langages réguliers et automates · Expressions régulières

Mots de mots : images

Définition

Soit \(\Sigma\) un alphabet fini.

On appelle image sur \(\Sigma\) un \(m\)-uplet \(p = (w_1,\dots,w_m)\) où les \(w_i \in \Sigma^*\) sont des mots de même taille ; on note cette taille \(l_1(p)\). On note également \(l_2(p) = m\).

On note \(\Sigma^{**}\) l'ensemble des images sur \(\Sigma\).

Un sous-ensemble \(L \subset \Sigma^{**}\) est appelé un langage d'images sur \(\Sigma\) ou encore un langage 2D.

Si \(p = (p_{11}\dots p_{1n}, \dots, p_{m1}\dots p_{mn})\) on notera

\[ p = \begin{array}{|ccc|} \hline p_{11} & \dots & p_{1n} \\ \vdots & \ddots & \vdots \\ p_{m1} & \dots & p_{mn} \\ \hline \end{array} \]

Opérations élémentaires

Concaténées d'images

Si

\[ p = \begin{array}{|ccc|} \hline p_{11} & \dots & p_{1n} \\ \vdots & \ddots & \vdots \\ p_{m1} & \dots & p_{mn} \\ \hline \end{array} \quad\text{et}\quad q = \begin{array}{|ccc|} \hline q_{11} & \dots & q_{1n} \\ \vdots & \ddots & \vdots \\ q_{m'1} & \dots & q_{m'n} \\ \hline \end{array} \]

on note

\[ p \ominus q = \begin{array}{|ccc|} \hline p_{11} & \dots & p_{1n} \\ \vdots & \ddots & \vdots \\ p_{m1} & \dots & p_{mn} \\ \hline q_{11} & \dots & q_{1n} \\ \vdots & \ddots & \vdots \\ q_{m'1} & \dots & q_{m'n} \\ \hline \end{array} \]

appelée la concaténation verticale de \(p\) et de \(q\). On remarque qu'une condition de compatibilité est nécessaire.

Si

\[ p = \begin{array}{|ccc|} \hline p_{11} & \dots & p_{1n} \\ \vdots & \ddots & \vdots \\ p_{m1} & \dots & p_{mn} \\ \hline \end{array} \quad\text{et}\quad q = \begin{array}{|ccc|} \hline q_{11} & \dots & q_{1n'} \\ \vdots & \ddots & \vdots \\ q_{m1} & \dots & q_{mn'} \\ \hline \end{array} \]

on note

\[ p \,|\, q = \begin{array}{|ccc|ccc|} \hline p_{11} & \dots & p_{1n} & q_{11} & \dots & q_{1n'} \\ \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ p_{m1} & \dots & p_{mn} & q_{m1} & \dots & q_{mn'} \\ \hline \end{array} \]

appelée la concaténation horizontale de \(p\) et de \(q\). On remarque qu'une condition de compatibilité est nécessaire.

Concaténées de langages

Si \(L_1,L_2\) sont deux langages on notera \(L_1 \ominus L_2\) et \(L_1 \,|\, L_2\) les concaténées des deux langages. Attention, si aucune condition de compatibilité n'est satisfaite ces langages peuvent être vides !

On note \(L^{i\ominus} = L \ominus \dots \ominus L\) et \(L^{*\ominus} = \bigcup_{i\ge 0} L^{i\ominus}\), idem pour l'autre concaténation.

Pour \(L = \Sigma\) (les images \(1\times 1\), voir ci-dessous), on a \(\Sigma^{**} = (\Sigma^{* |})^{*\ominus} = (\Sigma^{*\ominus})^{*|}\).

Question 1

Prouver cette égalité.

Corrigé

Une image \(p\) à \(m \ge 1\) lignes et \(n \ge 1\) colonnes est la concaténation verticale de ses \(m\) lignes, chacune étant la concaténation horizontale de ses \(n\) lettres : \(p \in (\Sigma^{*|})^{*\ominus}\). De même, \(p\) est la concaténation horizontale de ses \(n\) colonnes, chacune concaténation verticale de ses \(m\) lettres : \(p \in (\Sigma^{*\ominus})^{*|}\). Les deux inclusions réciproques sont immédiates, puisque ces deux langages sont formés d'images.

L'égalité \((L^{*|})^{*\ominus} = (L^{*\ominus})^{*|}\) est en revanche fausse pour un langage quelconque : avec \(L\) formé de l'image \(1 \times 2\) \(\begin{array}{|cc|}\hline a & b\\\hline\end{array}\) et de l'image \(2 \times 1\) \(\begin{array}{|c|}\hline c\\ d\\\hline\end{array}\), l'image à trois lignes \(ab\), \(cc\), \(dd\) est dans \((L^{*|})^{*\ominus}\) mais pas dans \((L^{*\ominus})^{*|}\) : ses colonnes de largeur \(1\) commencent par \(a\) ou \(b\), et une colonne de largeur \(2\) ne contient que des lignes \(ab\).

Expressions régulières

Pour tout \(a \in \Sigma\), on note encore \(a\) l'image \(1\times 1\) qui contient \(a\).

Une expression utilisant de tels langages élémentaires et les opérations \(\ominus, |, *\ominus, *|, \cup, \cap, {}^c\) est appelée une expression régulière.

Question 2

Décrire le langage des échiquiers sur \(a\) et \(b\) ayant un nombre pair de colonnes à l'aide d'une expression régulière.

Reconnaissance par automates four-way

On considère un alphabet \(\Sigma\) et \(8\) symboles qu'on considère comme n'étant pas dans \(\Sigma\) : \(\nwarrow, \uparrow, \nearrow, \rightarrow, \searrow, \downarrow, \swarrow, \leftarrow\). On note \(\Sigma'\) l'alphabet \(\Sigma\) étendu par ces 8 symboles.

Un automate four-way sur \(\Sigma\) est un \(n\)-uplet \((Q,q_i,q_a,q_r,\delta)\) où \(Q\) est un ensemble fini d'états, \(q_i \in Q\) est l'état initial, \(q_a\in Q\) l'état d'acceptation et \(q_r \in Q\) l'état de rejet. La fonction \(\delta : Q \times \Sigma' \rightarrow Q \times \{\Downarrow, \Leftarrow, \Uparrow, \Rightarrow\}\) est appelée la fonction de transition.

Comment fonctionne un tel automate sur une image :

• On considère qu'on peut border l'image et que les bords contiennent les symboles que l'on a rajoutés à \(\Sigma'\).
• On se place sur la case en haut à gauche de l'image dans l'état \(q_i\).
• À chaque étape on regarde le symbole sur la case où on se trouve, et avec \(\delta\) on en déduit le nouvel état et la direction dans laquelle on se déplace d'une case.
• Tant qu'on ne tombe ni sur un état de rejet ni sur un état d'acceptation, on itère.

Une image bordée par les symboles de $\Sigma'$ ; la case de départ est en orange

Question 3

Décrire un automate pour reconnaître :

• les mots carrés ;
• les mots quadrillés.

On étend directement ces automates en des variantes non déterministes en associant un ensemble de couples (nouvel état, direction).

Deux théorèmes surprenants en contraste du cas 1D :

Théorème

Les automates four-way non déterministes sont strictement plus puissants que les déterministes.

Théorème

Les langages reconnus ne sont pas clos par concaténation.

Travaux pratiques

Images

On définit le type

type 'a image = 'a array array

des images sur les éléments de type 'a.

On suppose ici que les images sont des matrices : si im est une image alors tous les im.(i) ont même taille appelée la largeur de l'image.

La taille de im est appelée sa hauteur.

Question 4

Écrire une fonction dim qui renvoie le couple (hauteur, largeur) d'une image.

Corrigé

let dim im =
  let l1 = Array.length im in
  if l1 > 0 then (l1, Array.length im.(0)) else (0, 0)

Question 5

Écrire une fonction hconcat réalisant la concaténation horizontale de deux images en supposant qu'elle soit définie.

Corrigé

let hconcat i1 i2 =
  let l11, l12 = dim i1 in
  let _, l22 = dim i2 in
  let i3 = Array.make_matrix l11 (l12 + l22) i1.(0).(0) in
  for i = 0 to l11 - 1 do
    for j = 0 to l12 - 1 do
      i3.(i).(j) <- i1.(i).(j)
    done;
    for j = 0 to l22 - 1 do
      i3.(i).(l12 + j) <- i2.(i).(j)
    done
  done;
  i3

Question 6

Écrire une fonction vconcat réalisant la concaténation verticale de deux images en supposant qu'elle soit définie.

Corrigé

let vconcat i1 i2 =
  let l11, l12 = dim i1 in
  let l21, _ = dim i2 in
  let i3 = Array.make_matrix (l11 + l21) l12 i1.(0).(0) in
  for j = 0 to l12 - 1 do
    for i = 0 to l11 - 1 do
      i3.(i).(j) <- i1.(i).(j)
    done;
    for i = 0 to l21 - 1 do
      i3.(l11 + i).(j) <- i2.(i).(j)
    done
  done;
  i3

Par exemple, avec im0 = [| [| 0 |] |] et im1 = [| [| 1 |] |], vconcat (hconcat im0 im1) (hconcat im1 im0) est le quadrillage \(2\times 2\).

Question 7

Écrire des fonctions :

1. carre telle que carre n renvoie un carré de n par n de 0 ;
2. quadrillage telle que quadrillage n renvoie un carré de n par n de 0 ou de 1 en alternant comme dans un échiquier ;
3. carre_centre telle que carre_centre n renvoie un carré de \(2n+1\) par \(2n+1\) de 0 avec un 1 au centre.

Automate four-way

On considère les types

type direction = Haut | Bas | Gauche | Droite
type 'a etendu = Coin of direction * direction
               | Bord of direction | Lettre of 'a
type ('a, 'b) auto4dir = { initial : 'b; accepte : 'b; rejete : 'b;
                           delta : 'b * 'a etendu -> 'b * direction }

Question 8

Écrire une fonction etend telle que etend im x y renvoie un élément du type 'a etendu correspondant aux valeurs de \(x\) et de \(y\) (par exemple, pour \((x,y)=(0,0)\) on renvoie Coin (Haut, Gauche)).

Corrigé

Comme sur la figure, \(x\) est la colonne et \(y\) la ligne dans l'image bordée : les cases de l'image ont pour coordonnées \(1 \le x \le l\) et \(1 \le y \le h\), et la case \((x,y)\) contient im.(y-1).(x-1).

let etend im x y =
  let h, l = dim im in
  let v = if y = 0 then Some Haut else if y = h + 1 then Some Bas else None in
  let hz = if x = 0 then Some Gauche else if x = l + 1 then Some Droite else None in
  match v, hz with
  | Some dv, Some dh -> Coin (dv, dh)
  | Some d, None | None, Some d -> Bord d
  | None, None -> Lettre im.(y - 1).(x - 1)

Question 9

Écrire une fonction delta_carre qui implémente la fonction de transition de reconnaissance par un automate four-way des carrés.

En déduire l'automate a4carre correspondant.

Corrigé

États : \(0\) (aller à droite), \(1\) (descendre), \(4\) (bord droit atteint), \(3\) acceptation, \(2\) rejet.

let delta_carre (q, c) =
  match q, c with
  | 0, Coin (Bas, Droite) -> 3, Haut   (* image vide *)
  | 0, Lettre _ -> 1, Droite
  | 1, Lettre _ -> 0, Bas
  | 1, Bord Droite -> 4, Bas
  | 4, Coin (Bas, Droite) -> 3, Haut
  | _ -> 2, Haut

let a4carre = { initial = 0; accepte = 3; rejete = 2; delta = delta_carre }

Question 10

Écrire une fonction reconnait telle que reconnait a4 im teste si im est reconnu par l'automate a4.

Corrigé

let reconnait a4 im =
  let x = ref 1 and y = ref 1 in
  let q = ref a4.initial in
  while !q <> a4.accepte && !q <> a4.rejete do
    let q', d = a4.delta (!q, etend im !x !y) in
    q := q';
    match d with
    | Haut -> decr y
    | Bas -> incr y
    | Gauche -> decr x
    | Droite -> incr x
  done;
  !q = a4.accepte

Si l'automate ne rencontre jamais l'état d'acceptation ni celui de rejet, la boucle ne termine pas.

Automate cellulaire pour les langages

On considère le type :

type ('a, 'b) autocell = { initial : 'b; finaux : 'b list;
                           delta : 'b * 'b * 'a -> 'b }

Question 11

Reprendre les questions du paragraphe précédent (automate pour carré et reconnaissance).

Corrigé

let reconnait_cell ac im =
  let l1, l2 = dim im in
  let qim = Array.make_matrix (l1 + 1) (l2 + 1) ac.initial in
  for i = 0 to l1 - 1 do
    for j = 0 to l2 - 1 do
      qim.(1 + i).(1 + j) <-
        ac.delta (qim.(i).(1 + j), qim.(1 + i).(j), im.(i).(j))
    done
  done;
  List.mem qim.(l1).(l2) ac.finaux

Pour les carrés, l'état \(1\) marque les cases de la diagonale, \(2\) celles au-dessus et \(3\) celles en dessous : l'image est carrée si et seulement si la case en bas à droite est sur la diagonale.

let delta_carre (q1, q2, _) =
  match q1, q2 with
  | 0, 0 | 2, 3 -> 1
  | 0, 1 | 0, 2 | 2, 1 | 2, 2 -> 2
  | _ -> 3

let ac_carre = { initial = 0; finaux = [1]; delta = delta_carre }

Autre exemple : l'automate suivant reconnaît les images (non vides) de largeur paire, l'état \(2\) marquant les colonnes d'indice impair.

let delta_largeur_paire (q1, q2, _) =
  match q1, q2 with
  | 0, 1 | 2, 1 -> 2
  | _ -> 1

let ac_largeur_paire = { initial = 0; finaux = [2]; delta = delta_largeur_paire }

Question 12

Écrire une fonction delta_quadrillage qui implémente la fonction de transition de reconnaissance par un automate cellulaire des quadrillages.

En déduire l'automate acquadrillage correspondant.

Corrigé

Les états \(1\) et \(2\) marquent les cases \(0\) et \(1\) d'un quadrillage commençant par \(0\), les états \(4\) et \(3\) les cases \(0\) et \(1\) d'un quadrillage commençant par \(1\) ; l'état \(5\) est un puits.

let delta_quadrillage (q1, q2, c) =
  match q1, q2, c with
  | 0, 0, 0 -> 1
  | 0, 0, 1 -> 3
  | 0, 3, 0 | 3, 0, 0 | 3, 3, 0 -> 4
  | 0, 4, 1 | 4, 0, 1 | 4, 4, 1 -> 3
  | 0, 1, 1 | 1, 0, 1 | 1, 1, 1 -> 2
  | 2, 0, 0 | 0, 2, 0 | 2, 2, 0 -> 1
  | _ -> 5

let acquadrillage = { initial = 0; finaux = [1; 2; 3; 4];
                      delta = delta_quadrillage }