Extraction de linéiques : ELIESER

Algorithme d'extraction

On utilise cet algorithme déjà existant (cf demo ELIESER) afin de trouver le chemin représentant la route entre 2 ensembles de points S₀ et S₁. En effet, le données ne fournissant aucune information sur la forme de la route entre deux noeuds, on choisit calculer cette forme en fonction de la position des extrémités.

Le calcul est basé sur une fonction d'énergie (ou de coût) . Cette fonction $\Phi$ est définie sur les cliques de trois pixels successifs, et dépend de

• L'homogénéité des niveaux de gris,
• le contraste avec le fond,
• la courbure locale (la courbure maximale d'une suite de trois pixels est 45 degrés).

Illustration

L'algorithme de programmation dynamique trouve le chemin d'énergie minimale  en effectuant:

• des balayages successifs de l'image jusqu'a convergence,
• des mise à jour pour chaque pixel de l'énergie necessaire pour y arriver à chaque passage.

=> Le résultat est le chemin d'énergie minimale depuis le point de S₀ jusqu'a chacun des points de l'image.