Discussion :

[Invité]

Bonjour,

Je dois réaliser un programme en C qui détermines les fonds et sommets d'un tableau à deux dimensions. Cad que ce tableau représente une "carte" et chaque case est un point qui a une certaine hauteur.
Je dois donc pouvoir dire telle case est un sommet, un fond ou aucun des deux.

Je pensais analyser les sommets et fonds ligne par ligne puis colonne par colonne. Et je compare chaque case avec la case précédente et la suivante.

Ensuite j'aurais comparé les 2 analyses: par exemple si une case est un sommet dans l'analyse ligne par ligne et dans celle colonne par colonne, dans ca cas c'est bien un sommet.

Mais c'est surtout dans l'analyse elle-même que je bloque, car j'ai 9 cas qui peuvent se présenter:

- case[x-1] < case[x] > case[x+1]
- case[x-1] < case[x] < case[x+1]
- case[x-1] < case[x] = case[x+1]
- case[x-1] > case[x] > case[x+1]
- case[x-1] > case[x] < case[x+1]
- case[x-1] > case[x] = case[x+1]
- case[x-1] = case[x] > case[x+1]
- case[x-1] = case[x] < case[x+1]
- case[x-1] = case[x] = case[x+1]

Dans certains cas on peut directement dire que c'est un sommet ou un fond, ou aucun des 2, mais dans d'autres il faut attendre d'être plus loin et revenir en arrière pour dire ça.

Je doute que je sois vraiment sur une piste très optimisée piste.
Comment envisageriez-vous ce problème ?

[fremen167]

A mon avis, ton algo a un défaut : il ne prend pas en compte les diagonales.
Exemple :
1111111
1222221
1223221
1242211
1232111
1121111

je dirais que seule la case de valeur 4 est un sommet (pas le 1er 3).

D'autre part, si tu as (par exemple) :
111111
234421
122111

le sommet est contitué de deux cases et non d'une seule. Il faudrait donc regrouper les points contigüs de même valeur.

[Invité]

Merci

En effet, ce que tu dis avec les diagonales est tout juste (ça complique encore les choses :s ).

Et pour le regroupement ce serait pas une mauvaise idée, maintenant c'est encore de le mettre en place

Si quelqu'un à des idées ou a déjà fait ce genre de chose ça m'intéresse.

[fremen167]

Je vois les choses comme ça : il me semble utile de gérer une donnée pour chaque point qui détermine si un point est :
- un max ;
- pas un max ;
- indéfini.
plus une liste des cases adjacentes de même valeur.

Par un parcours simple de la matrice, tu peux associer à chaque case :
- la liste des cases adjacentes ayant même valeur,
- si des cases adjacentes sont supérieure, "pas un max", sinon indéfini.

Tu reparcours ta liste :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
Pour un point donné (encore indéfini) :
si liste vide, c'est un max
sinon,
   (c'est là que ça se corse, on a pas de case adjacente plus grande
    mais on a des cases =)
    Il faudrait pouvoir étendre la liste des cases de même valeur adjacentes
    aux adjacentes des adjacentes (etc), ce qui défini une "zone d'égalité"
    Si on a atteint l'extension maximum et que toutes la zone est "indéfinie",
          toute la zone est maximum,
       Sinon,
          aucune des cases n'est un max.

Je sais, c'est pas génial , l'extension de la zone d'égalité, c'est coton. Mais j'ai pas mieux à te proposer pour le moment ! Tu peux quand-même t'en sortir en notant que quand tu étends ta zone :
dès qu'une case de la zone a une case adjacente supérieure ou déjà marquée comme "pas un max", tu peux t'arrêter et marquer toutes les cases de la zone comme "pas un max".
Comme ça, dès que tu traiteras une case dont une adjacente est égale et marquée, tu sauras la traiter directement. Les seules zones qu'il faut étendre complètement sont les zones "max".

[FR119492]

Salut !

Ton problème serait beaucoup plus simple si ta fonction z(x,y) était continue au lieu d'être donnée par des valeurs discrètes (c'est-à-dire sur les noeuds d'une grille). Il suffirait de chercher les points où les deux composantes du gradient sont nulles. Un tel point est

• un sommet si les dérivées dans les deux directions sont négatives;
• un fond si elles sont toutes deux positives;
• un col si elles sont de signes opposés.

Tu ne peux évidemment pas dériver une grandeur donnée par des valeurs discrètes. C'est pourquoi je te suggère d'interpoler d'abord ta fonction par un spline cubique dont tu peux calculer les dérivées premières et secondes dans les deux directions.

Je vois encore des pathologies possibles, mais commence quand même comme ça.

Bonne chance.
Jean-Marc Blanc

[Invité]

Merci à vous.

@FR119492: c'est vrai que ça aurait été également un moyen de le faire, mais mes connaissances en C ne sont pas assez avancée pour réaliser ça.

Sinon j'ai discuté avec une connaissance et j'ai trouvé une méthode plus simple que la première auquel je pensais.

Par exemple pour la recherche des sommets. "Il suffit" de comparer chaque case avec ses 8 voisins (3 ou 5 quand on est sur les bords). Quand il y a plus de valeur plus petit que de valeur égal, on a alors un sommet.

[fremen167]

Par exemple pour la recherche des sommets. "Il suffit" de comparer chaque case avec ses 8 voisins (3 ou 5 quand on est sur les bords). Quand il y a plus de valeur plus petit que de valeur égal, on a alors un sommet.

Ca me semble une drôle de définition d'un sommet

A mon avis, un sommet, ça doit être une case qui n'a que des cases adjacentes de valeur plus petite, ou un ensemble de case contigües qui n'ont que des cases adjacentes (hors celles de l'ensemble) de valeur plus petite.

[FR119492]

mais mes connaissances en C ne sont pas assez avancée pour réaliser ça

Tu pourrais aussi le faire en Fortran, Pascal, Assembleur ou dans MatLab!

Dans tous les cas, sois prudent et prend garde à la difficulté de localiser des sommets ou des fonds très plats.

Bonne chance.
Jean-Marc Blanc

[Graffito]

Bonjour,

Pour identifier les sommets:

• demarrer depuis le ciel,
• descendre jusquà trouver un point non traité : ce sera un sommet.
• eliminer tous les points voisins dont l'altitude est inférieure ou égale (plateau),
• réitérer le traitement d'élimination sur les voisins des voisins éliminés,
• continuer à chercher un autre sommet (point non éliminé) à la même altitude,
• si il y en a un, le traiter. sinon chercher un sommet à l'altitude inférieure parmi les points non éliminés .

Pour les fonds, algo semblable en partant du centre de la terre

[ToTo13]

Bonjour,

ce que tu demandes revient à considérer une image comme une carte d'élévation (ton tableau de hauteurs).
Or en imagerie, on utilise des méthodes pour résoudre le genre de problème que tu poses :
- Les extrémas d'ordre.
- La méthode des Top Hat en morphologie mathématique.

Accéssoirement, j'ai créé de manière brute un algorithme qui extrait tous les pics et les lacs d'un volume sous la nappe (une image considérée comme une carte d'élévation). Procéder de cette façon revient à répondre à ton problème.

[pseudocode]

Je dois donc pouvoir dire telle case est un sommet, un fond ou aucun des deux.

Il faudrait une definition claire de ces 3 cas. Je suppose que Sommet est un maximum local et Fond est un minmum local (reste a savoir la taille du voisinnage local).

Sinon, je suis d'accord avec Toto13: c'est une segementation de type carte d'élévation. On peut ajouter a la liste des methodes la recherche des "bassins de rétention" (cf. watershed)