Compter le nombre de "zones" d'une matrice Fermé

Question

Bonjour,


Je souhaiterais créer une routine de comptage. Problème: je sèche sur l'algorithme (que je dois ensuite transcrire en Scilab).

Voilà ce que je cherche à faire.
Dans une matrice de type:
0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 1. 0. 0. 0. 1. 0. 0.
0. 1. 0. 0. 1. 0. 1. 0. 0. 0.
0. 0. 0. 0. 1. 1. 0. 0. 0. 0.
0. 0. 0. 0. 1. 0. 0. 0. 0. 0.
0. 0. 1. 0. 0. 0. 0. 0. 0. 0.
0. 1. 1. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 1. 1. 0. 1. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 

J'aimerais pouvoir compter de manière automatique le nombre de zones contenant des 1 (si plusieurs "1" sont adjacents et en tenant compte des diagonales, cela compte pour une zone).
Dans le cas qui précède, la routine doit donc retourner 5.

Pour l'instant, j'ai regroupé les coordonnés des 1 dans une matrice nx2, pour le cas qui précède on a:
2. 4.
2. 8.
3. 2.
3. 5.
3. 7.
4. 5.
4. 6.
5. 5.
6. 3.
7. 2.
7. 3.
9. 4.
9. 5.
9. 7.

Ensuite je bloque...

Quelqu'un a une idée, sachant que je ne dispose que des outils de Scilab pour mettre en oeuvre l'algorithme (while, for, if et stockage dans des matrices). 

Merci d'avance pour votre aide !

Dodni

philippe · Answer

Bonjour,

si tu modélise ton problème par un graphe (non-orienté)dont les sommets représentent les 1 de ta matrice et les arêtes représentent les connexions au plus proches voisins alors ton problème se ramène à compter le nombre de composantes connexes. 

Avec scilab tu peux donc résoudre ce problème en utilisant la toolbox METANET qui implémente les graphes. Voici une ébauche de l'algorithme :

-en entrée on donne la matrice M (sous forme "plein" ou "creuse" peu importe)
- créer ensuite le graphe  G correspondant au problème (avec make_graphe puis en ajoutant les sommets un a un avec add_nodes en parcourant ta matrice M)
-ajouter à G les arêtes (avec add_edge en faisant encore un parcours de la matrice M)
-calculer le nombre de composantes connexes avec [nc,ncomp] = connex(G)

si j'ai le temps je regarderai ça ce week-end, mais tu peux aussi chercher tout seul :-). Si tu ne connais pas METANET tu peux lire le document suivant :

https://perso.univ-rennes1.fr/philippe.roux/scilab/metanet/fiche_metanet.pdf
ou
https://perso.univ-rennes1.fr/philippe.roux/scilab/metanet/fiche_metanet.html

c'est pour scilab 4.1.2, pour scilab 5.2.x il y a eu quelques changements dans la structure de graphes de metanet ....

Philippe

Dodni · Answer

Bonjour Philippe,

Merci pour ta réponse. C'est vraiment sympa de prendre le temps de répondre à une question d'un anonyme total !

Entre temps hier soir j'ai mis en oeuvre une méthode bourrin mais qui fonctionne, sur base de if, for, while...

La technique que tu proposes m'intéresse dans la mesure ou j'ai la sensation qu'elle est susceptible d'améliorer la vitesse de traitement.

Ne t'embêtes pas, je vais chercher moi même (je retiens mieux quand je cherche !).

En revanche, en parcourant d'autre forums il me semble avoir vu ton nom sur des sujets relatifs au traitement d'images .tif.
J'en ai un à disposition qui contient des triplets de type (coordonnée_x,coordonnée_y, altitude_z). Sais tu comment les extraire du .tif ou as-tu connaissance de posts / tutoriels sur ce sujet ?

Une fois encore, merci pour tout !

Dodni

philippe · Answer

Pour ton problème de départ reposte sur ce forum si tu n'arrives pas à implémenter la solution avec les graphes. je jetterai un oeil ....

Pour les images *.tif, si c'est pour les importer dans scilab tu devrais regarder du coté de sivp :

http://sivp.sourceforge.net/

avec cette toolbox tu peux importer la plupart des formats d'images dans scilab avec la commande M=imread('monimage.ext') :

- si ton image est en niveau de gris alors M sera une matrice d'entiers 8 bits (type uint8 dans scilab) M(i,j) représente "l'altitude" du pixel de coordonnées (i,j)

- si ton image est en couleur alors M sera une "hypermatrice" c'est a dire un assemblage de 3 matrices (de uint8) telles que :

M(:,:,1) -> matrices des niveaux de rouge
M(:,:,2) -> matrices des niveaux de vert
M(:,:,3) -> matrices des niveaux de bleu

Philippe.

philippe · Answer

ça y est je l'ai fait, ça marche très bien, j'ai testé sur des graphes un peu gros (matrice 100*100 avec 2000  "1") l'exécution prend 1.5 seconde (2 secondes si j'affiche le graphe). si tu veux la solution demande ....

@+,

Philippe.

Compter le nombre de "zones" d'une matrice

4 réponses

Discussions similaires