Aller au contenu

Géométrie Discrète - CM séance 04

4. Droites et plans discrets (suite)

4.4 Intersections de droites

Soit 2 droites 8-connexes \(D_1\) et \(D_2\), et \(S\) leur intersection.

Contrairement au cas de droites continues, \(S\) peut être

  • vide lorsque les droites continues sont sécantes ;
  • constitué de plusieurs points, éventuellement non connectés.

On peut voir empiriquement que \(S\) "grossi" et "s'allonge" lorsque l'angle entre les 2 droites est fin.

Rappels :
équation droite discrète 8-connexe : \(0 \leq ax + by +c < \max(|a|,|b|)\)
normale = \(\overrightarrow{(a,b)}\) ; vecteur directeur = \(\overrightarrow{(b,-a)}\) ; pente = \(-a/b\) .

Étude des cas d'intersection en fonction des 8 octants :

                        b^                                 
                         |  0 <= a <= b : -1 <= pente <= 0 
                         |                                 
                      \  |  /                              
                       \ | /  0 <= b <= a : pente <= -1    
                        \|/                                
                  -------O-------> a                       
                        /|\                                
                       / | \  0 <= -b <= a : pente >= 1    
                      /  |  \                              
                         |                                 
                         | 0 <= a <= -b : 0 <= pente <= 1

Remarque : en réalité il n'y a que 4 cas : si \(a < 0\), on a
\(0 \leq ax +by +c < \max(|a|,|b|)\)
\(\Leftrightarrow \; -\max(|a|,|b|) \leq ax +by +c -\max(|a|,|b|) < 0\)
\(\Leftrightarrow \; \max(|a|,|b|) \geq -ax -by -c+\max(|a|,|b|) > 0\)
\(\Leftrightarrow \; \max(|a|,|b|) > -ax -by -c+\max(|a|,|b|)-1 \geq 0\)
\(\Leftrightarrow \; 0 \leq -ax -by +c' < \max(|a|,|b|)\;\) où \(\;c' = \max(|a|,|b|)-c-1\) .

On peut donc se ramener d'un octant \(a,b\) situé à gauche (\(a \leq 0\)) à l'octant central-symétrique \((-a,-b)\) situé à droite (\(-a \geq 0\)).

Rappel : décomposition en fractions continues :

Toute fraction peut se décomposer sous la forme

\[ \frac{a}{b} = q_0 + \frac{1}{\displaystyle q_1 + \frac{1}{\displaystyle q_2 + \frac{1}{\displaystyle \ldots + \frac{1}{ q_n } } } } \]

On note : \(a/b = [q_0, q_1, ... q_n]\).

Exemple :

    151 / 34  = 4 + 15/34
     34 / 15  = 2 + 4/15
     15 / 4   = 3 + 3/4
      4 / 3   = 1 + 1/3

Donc \(151/34 = 4+1/(2+1/(3+1/(1+1/3))) = [4,2,3,1,3]\).

Théorème [Reveillès 1991 p.156] pour les droites 8-connexes :
Soit \(D_1\) de pente \(a/b\), \(D_2\) de pente \(a'/b'\), tels que \(0 < a'/b' < a/b \leq 1\) (donc dans le même octant), \(\text{pgcd}(a,b) = \text{pgcd}(a',b') = 1\), et de restes \(c_1 = c'_1 = 0\) ; leurs équations sont donc : \(D_1 : 0 \leq ax - by < b\) ; \(D_2 : 0 \leq a'x -b'y < b'\) .
Soit \([q_0, q_1, \ldots, q_n] = a/b\) ;
alors \(S = D_1 \cap D_2\) est 8-connexe ssi l'une des inégalités est satisfaite :
\[ \begin{array}{lcl} a'/b' < 1/(2q_1-1) & \text{si} & q_1 \geq 1 \text{ et } q_2 = 0 \\ a'/b' < 1/(2q_1+1) & \text{si} & q_1 \geq 1 \text{ et } q_2 = 1 \\ a'/b' < 1/(2q_1) & \text{si} & q_1 \geq 2 \text{ et } q_2 \geq 2 \\ a'/b' < q_2/(q_2+2) & \text{si} & q_1 = 1 \text{ et } q_2 \geq 2 \end{array} \]

Remarques :

  • \(q_0\) = 0 car \(a/b < 1\) ;
  • le théorème ne dépend que de \(q_1\) et \(q_2\), pas des termes suivants.

Théorème [Isabelle Sivignon 2004] :

  • Si \(D_1\) et \(D_2\) appartiennent au même octant, alors on peut se ramener au théorème de Reveillès ci-dessus ;
  • si \(D_1\) et \(D_2\) appartiennent à 2 octants voisins, alors \(S\) est soit vide, soit 8-connexe ;
  • sinon \(S\) est soit vide, soit est 1 seul pixel.

Notation : on écrit \(a | b\)   ("\(a\) divise \(b\)")   si \(b \text{ mod } a = 0\).
\(\Leftrightarrow \exists k \in \Bbb{Z}\) tel que \(k\,a = b\) .

Théorème pour les droites épaisses [Reveillès 1991 p.135] :
\(D_1\) : \(0 \leq ax + by +c < \omega\)
\(D_2\) : \(0 \leq dx + ey +f < \psi\)
soit \(\Delta = a\,e - d\,b\)   le déterminant ;
si \(\Delta | \omega\) et \(\Delta | \psi\), alors \(S\) pave le plan.

5. Transformations de distances

5.1 Distance discrète

Définition : une distance discrète sur \(\Bbb{Z}^n\) est une application \(d : \Bbb{Z}^n \times \Bbb{Z}^n \longrightarrow \Bbb{N}\) vérifiant : \(\forall A,B,C \in \Bbb{Z}^n\),

  1. positive : \(d(A,B) \geq 0\)
  2. définie : \(d(A,B) = 0 \Leftrightarrow A = B\)
  3. symétrique : \(d(A,B) = d(B,A)\)
  4. inégalité triangulaire : \(d(A,B) \leq d(A,C) + d(C,B)\)

Distances usuelles pour \((x_1, ...,x_n) \in \Bbb{R}^n\) : distances de Minkowski, induites par les normes \(\ell_p\) avec \(d_p(A,B) = \ell_p(\overrightarrow{AB})= \ell_p(B-A)\) :

\(\quad \ell_1 = \sum_{i=1 \ldots n} |x_i|\)
\(\quad \ell_2 = \sqrt{ \sum_{i=1 \ldots n} |x_i|^2 }\)   (distance euclidienne)
\(\quad \ell_\infty = \sup_{i=1 \ldots n} |x_i|\)

Exemple pour \(\Bbb{Z}^2\) dans la littérature :
\(d_4(P,Q) = |xp - xq| + |yp - yq| = \ell_1(Q-P)\)
\(d_8(P,Q) = \max( |xp - xq| , |yp - yq| ) = \ell_\infty(Q-P)\)

Pourquoi ces noms ?

Définition d'une boule : \(B_d(P,r) = \big\{ Q : d(P,Q) \leq r \big\}\)

                    1                     1 1 1
    B_d_4(O,1) =  1 O 1     B_d_8(O,1) =  1 O 1
                    1                     1 1 1

Boules \(d_4\) et \(d_8\) \(\Leftrightarrow\) voisinages \(N_4\) et \(N_8\).

Remarque : distance euclidienne, induite par la norme \(\ell_2\) : \(d_E(P,Q) = \sqrt{ |xp - xq|^2 + |yp - yq|^2 }\)

  • valeurs dans \(\Bbb{R}\), pas dans \(\Bbb{N}\)
  • \(d_E^2\) : valeurs dans \(\Bbb{N}\), mais :

d_E²( (0,0),(0,2) ) > d_E²( (0,0),(0,1) ) + d_E²( (0,1),(0,2) )
        = 4                     = 1                 = 1
non respect inégalité triangulaire \(\Rightarrow\) pas une distance.

Distance à un ensemble :
soit \(d : \Bbb{Z}^n \times \Bbb{Z}^n \rightarrow \Bbb{N}\) une distance,
\(X \subset \Bbb{Z}^n\) un sous-ensemble non vide,
\(P \in \Bbb{Z}^n\) un point, alors
\(d(P,X) = \inf \left\{ d(P,Q) \,:\, Q \in X \right\}\) .

Remarque : \(P \in X \;\Rightarrow\; d(P,X) = 0\)

Distance entre ensembles :
soit \(d : \Bbb{Z}^n \times \Bbb{Z}^n \rightarrow \Bbb{N}\) une distance,
soit \(A, B \subset \Bbb{Z}^n\) des sous-ensembles non vides.
Distance de Hausdorff : \(d_H(A,B) = \max \big\{ \sup_{a \in A} d(a,B)\,,\; sup_{b \in B}\,d(b,A) \big\}\)

Autres distances entre ensembles pour la mesure de similarités : par ex. distance de Asplünd [1960].

5.2 Transformation de distance

Définition :
Soit \(I\) une image binaire,
\(X = \{ \,P \in I \,:\, I[P] > 0 \,\}\) = ensemble points forme,
\(\bar{X} = I \setminus X = \{ \,p \in I \,:\, I[P] = 0 \,\}\) = le fond, ou complémentaire
Soit \(d\) une distance discrète.
La transformation de distance \(DT_d(I)\) consiste à étiqueter chaque point objet à sa distance au complémentaire :
\[ DT_d \; \left( \; \begin{array}{rcl} I & \longrightarrow & J = DT_d(I)\\ p & \longmapsto & DT_d(p) = d(p, \bar{X}) \,. \end{array} \right. \]

\(J\) est appelée l'image des distances (distance map).

5.2.1 Première approche par pelage

On construit l'image des contours successifs pour une connexité \((n, n')\) :

à une étape \(k\), on considère :
la forme \(X_k = \{ \text{points} \geq k \}\)
le complémentaire \(\bar{X}_k = \{ \text{points} < k \}\)

Algorithme :

  • Initialisation :
    \(X_1 = \{ \text{fond à 0, forme à } \infty \}\) (en prenant par exemple \(\infty\) = INT_MAX dans <climits>)
  • Étape \(k\) :
    on abaisse à \(k\) les points du contour de \(X_k\) (ie. on marque à \(k\) les points \(> k\) qui ont au moins un \(n'\)-voisin \(< k\)).
  • Fin : quand \(X_k\) est vide.

Exemple : (taille 9x7, 0 tout autour)

        +---+---+                               +---+---+                     
  .   . |   |   | .   .   .   .   .       .   . |   |   | .   .   .   .   .   
    +---+---+---+---+---+---+               +---+---+---+---+---+---+         
  . |   |   |   |   |   |   | .   .       . |   |   |   |   |   |   | .   .   
    +---+---+---+---+---+---+               +---+---+---+---+---+---+         
  . |   |   |   |   |   |   | .   .       . |   |   |   |   |   |   | .   .   
+---+---+---+---+---+---+---+---+---+   +---+---+---+---+---+---+---+---+---+ 
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   | 
+---+---+---+---+---+---+---+---+---+   +---+---+---+---+---+---+---+---+---+ 
|   |   |   |   |   |   |   | .   .     |   |   |   |   |   |   |   | .   .   
+---+---+---+---+---+---+---+           +---+---+---+---+---+---+---+         
|   |   |   |   |   |   |   | .   .     |   |   |   |   |   |   |   | .   .   
+---+---+---+---+---+---+---+           +---+---+---+---+---+---+---+         
|   | .   . |   |   |   | .   .   .     |   | .   . |   |   |   | .   .   .   
+---+       +---+---+---+               +---+       +---+---+---+
Chaque point est à la distance \(k\) du fond → Image des contours = DT :
n=8, n'=4 → \(d_4\)
n=4, n'=8 → \(d_8\)
Très inefficace :
le nombre de passages dépend de l'épaisseur de la forme.
Exemple image 800x600 → jusqu'à 300 passages !

5.2.2 Détection de points caractéristiques : maximums locaux

Sur chaque contour \(k\), on marque les points qui n'ont pas de \(n'\)-voisin \(> k\).

Algorithme :
en 1 seul passage, recopie des max locaux dans le \(n'\)-voisinage dans une seconde image.

5.2.3 Transformation de distance inverse par pelage : RDT

L'ensemble des max locaux suffit pour retrouver la forme.

  • On cherche la valeur max dans l'image

  • pour \(k\) de max-1 à 1 :
    on balaye l'image,
    en marquant à \(k\) les points \(< k\) qui ont un \(n'\)-voisin \(> k\).

Chaque point de l'image résultante est à distance < de la valeur d'au moins un point de départ → image des distances inverse, RDT.

Très inefficace : le nombre de passages dépend de l'épaisseur de la forme.

Conclusion : 

graph LR
    A[Forme] -->|DT| B[max locaux]
    B --> |RDT| C[Forme]