===== FAIN : Cours 1 =====

==== Notions de topologie discrète ====


Définition : une image 2d est représentée par une grille d'affichage I(x,y) telle que I(x,y) définit la couleur d'un pixel de coordonnées (x,y) avec <jsm>x,y \in \mathbb{N}</jsm>, <jsm>0\leq x \leq x_{max},0\leq y \leq y_{max}</jsm>

pixel(x,y) = centre du carré de coté égal à l'unité.

^ Couleurs ^
| {noir, blanc} = { 0, 1} |
|  niveaux de gris = {0,1,...,255} |
|  RVB =  {0,1,...,255}<sup>3</sup> |

=== Déf. : Voisins ===

Soit \$ p\left(x,y\right)\in\mathbb{Z}^2 \$ un point entier ou pixel

| NW=(x-1,y+1) ^ nord(p) = (x,y+1) | NE=(x+1,y+1) |
^ Ouest(p)=(x-1,y) |  **p**  ^ Est(p)=(x+1,y) ^
| SW ou SO = (x-1,y-1) ^ Sud(p)=(x,y-1) | SE=(x+1,y-1) |

Les quatre points N,S,E,O/W sont dits 4-voisins de p.  On rajoute NE, NW, SE, et SW pour avoir les huit points dits 8-voisins de p.

  * Avec le maillage triangulaire (triangles équilatéraux) les pavés ont des 3-voisins (ceux avec lesquels sont partagés des côtés ou bords) et des 12-voisins avec le rajout des neuf autres qui partagent juste un sommet (trois par sommet).
  * Avec le maillage hexagonal (seul autre pavage du plan avec une figure régulière) il n'y a que des 6-voisins : les six qui partagent un coté sont aussi les seuls voisins aux sommets.
  * En 3-d on trouve les 6-voisins (comme les 4-voisins de 2-d: \$ \left(x\pm 1,y,z\right), \left(x,y\pm 1, z\right), \left(x,y,z\pm 1\right) \$), des 26-voisins (toutes les cellules partageant au moins un sommet avec p), mais aussi des 18-voisins, qui partagent un côté avec p.  On peu aussi concevoir les 18-voisins comme l'ensemble des 26-voisins moins les 8 "coins" ou voisins purement diagonaux, ou encore \$ \left\{ \left(x\pm 1,y,z\right), \left(x,y\pm 1, z\right), \left(x,y,z\pm 1\right)\right\}\cup \left\{\left(x\pm 1,y \pm 1, z\right), \left(x,y\pm 1, z \pm 1\right), \left(x \pm 1,y,z\pm 1\right)\right\} \$)

==== Propriétés de voisinage ====

La relation de 4-voisinage (resp. 8-voisinage) est symétrique.

La relation de 4-voisinage (resp. 8-voisinage) définit un graphe dit de 4-connectivité (resp. 8-connectivité).

==== Déf. : Connexité ====

Soit un ensemble Z de points entiers dit une zone ou une région.  Elle est 4-connexe (8-connexe) si le graphe correspondant de la 4-connectivité (8-connectivité) est connexe.

==== Composantes connexes ====

Une composante connexe d'une région Z pour la 4-connexité (8-connexité) est une partie maximale 4-connexe (8-connexe). 


==== Un chemin ====

Soient \$ P,Q \in \mathbb{Z}^2 \$ des pixels. Un __chemin__ 4-connexe (8-connexe) de P à Q est une suite \$ P_0, P_1, \ldots P_n \$ telle que \$P_0 = P, P_n = Q, P_i\in V_4\left(P_{i+1}\right) \left[P_i\in V_8\left(P_{i+1} \right)\right]\;\forall i=0,\ldots ,n-1 \$

==== Corollaire ====

Une région Z est 4-connexe (8-connexe) \$\Leftrightarrow \; \forall P,Q\in Z \; : \exists \$ un chemin 4-connexe (8-connexe) de P à Q dans Z.

{{section>fain_1a}}

----
==== Navigation ====

[[fain_segments|]] -- [[fain_2|]]