==== 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.