Adjacence des Composantes Connexes

  • 0 \subseteq \mathbb{Z}^2 : objet
  • F \subseteq \mathbb{Z}^2 \setminus O : fond

Définition

Soient

  • \left\{O_1 , \ldots ,O_m\right\} l'ensemble des k-composantes connexes de O;
  • \left\{F_1 , \ldots ,F_n\right\} l'ensemble des k'-composantes connexes de F;

On dira que O_i est adjacent à F_j s'il existe p\in O_i et q\in F_j tels que p et q sont 8'adjacents. p\in V_8\left(q\right) \; \Leftrightarrow \; q\in V_8\left(p\right)

Propriétés

O_i et F_j sont adjacentes si et seulement si \exists p \in O_i,\; \exists q \in F_j \; |\quad p\in V_4\left(q\right)\; \& \;q \in V_4\left(p\right) . (p et q sont 4-adjacents).

Démonstration

S'il existe p\in O_i et q\in F_j tels que p et q sont 8'adjacents, p\in V_8\left(q\right) \; \Leftrightarrow \; q\in V_8\left(p\right) , soit ils sont 4-adjacents et il n'y a rien a démontrer, soit ils ne sont que 8-adjacents : voisins diagonaux. Considerons un de leurs 4-voisins communs, s. Or, O et F sont des composantes connexes, et ne peuvent avoir des 4-voisins du même type (objet ou fond) qui ne fassent pas partie de la composante. s appartient à l'un ou l'autre.

p s
q

Suivi d'arêtes

Suivi d'arêtes (parcours d'un chemin bord d'une composante connexe).

FIXME Dessins à rajouter. Objet toujours à gauche.

F F
\leftarrow
* \uparrow F
* \uparrow F
* \uparrow F

Propriété : balance des tournants

Si g est le nombre de tournats d'un quart de tour & gauche et d est le nombre de tournats (d'un quart de tour) à droite, alors | g - d | = 4 et

  • si g = d + 4 alors la composante à gauche du chemin de bord est est entourée par celle à droite
  • si d = g + 4 alors la composante à droite (du chemin de bord) est entourée par cell à gauche.

O_i entoure F_j si tout chemin 4-connexe partant d'un point de F_j et allant vers l'infini rencontre nécéssairement O_i .

K-Arbre de composantes connexes

G=\left( \left\{ O_1 , O_2 , \ldots O_m \right\} \cup \left\{F_1 , \ldots F_n \right\},\; A_k\right)
où A = l'ensemble des arêtes correspondant à la notion d'adjacence, est un graphe non-orienté simple qui est un arbre. Il est appelé le k-arbre de composantes connexes.

FIXME Dessin à reproduire

Images Homéomorphes

Deux images I1 et I2 sont dites homéomorphes si leurs k-arbres de composantes connexes son isomorphes .

G\left(S,A\right), G'\left(S',A'\right) sont dits isomorphes s'il existe une bijection f: S\rightarrow S' telle que \left\{x,y\right\} \in A\; \Leftrightarrow \; \left\{F\left(x\right),f\left(y\right)\right\}\in A' .

Caractéristique d'Euler

Calcul à partir des éléments suivants (pas tous à la fois)

s combien de pixels de l'objet?
a combien de pixels en configuration [1 1] ou [1 1]T ? 1 1 1
1
d combien de pixels (ou de paires?) en config 1 _
_ 1
_ 1
1 _
t combien de triangles? _ 1
1 1
1 _
1 1
1 1
1 _
1 1
_ 1
q combien de quads? 1 1
1 1
x combien de XOR? 1 0
0 1
0 1
1 0
q3 combien de triangles qui ne sont pas dans un quad? 0 1
1 1
1 O
1 1
1 1
1 0
1 1
0 1
q1 combien de singletons dans un carré? 1 0
0 0
0 1
0 0
0 0
0 1
0 0
1 0
  • E4 = (q1 - q3 + 2 x ) / 4 = S - a + q
  • E8 = (q1 - q3 - 2 x ) / 4 = s - a - d + t - q
  • E4 = nombre de composantes 4-connexes de l'objet moins le nombre de composantes 8-connexes du complémentaire plus 1
  • E8 = nombre de composantes 8-connexes de l'objet moins le nombre de composantes 4-connexes du complémentaire plus 1

point "simple"

son adjonction ou retrait ne change pas l'arbre de composantes connexes.

 
m1ilc/fain_6.txt · Dernière modification: 2010/01/11 07:24 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki