Construire la matrice de contiguïté dans MATLAB
Tenir compte d'un ensemble de points disposés sur une grille de taille N-par-M.
Je suis en train de construire la matrice de contiguïté tels que
voisins points sont connectés.
Par exemple, dans une grille 3x3 avec un graphique:
1-2-3
| | |
4-5-6
| | |
7-8-9
Nous devrions avoir la correspondante de la matrice de contiguïté:
+---+------------------------------------------------------+
| | 1 2 3 4 5 6 7 8 9 |
+---+------------------------------------------------------+
| 1 | 0 1 0 1 0 0 0 0 0 |
| 2 | 1 0 1 0 1 0 0 0 0 |
| 3 | 0 1 0 0 0 1 0 0 0 |
| 4 | 1 0 0 0 1 0 1 0 0 |
| 5 | 0 1 0 1 0 1 0 1 0 |
| 6 | 0 0 1 0 1 0 0 0 1 |
| 7 | 0 0 0 1 0 0 0 1 0 |
| 8 | 0 0 0 0 1 0 1 0 1 |
| 9 | 0 0 0 0 0 1 0 1 0 |
+---+------------------------------------------------------+
En bonus, la solution devrait fonctionner pour les deux 4 - et 8-connecté voisins points, c'est:
o o o o
o X o vs. o X o
o o o o
Ce que le code que j'ai jusqu'à présent:
N = 3; M = 3;
adj = zeros(N*M);
for i=1:N
for j=1:M
k = sub2ind([N M],i,j);
if i>1
ii=i-1; jj=j;
adj(k,sub2ind([N M],ii,jj)) = 1;
end
if i<N
ii=i+1; jj=j;
adj(k,sub2ind([N M],ii,jj)) = 1;
end
if j>1
ii=i; jj=j-1;
adj(k,sub2ind([N M],ii,jj)) = 1;
end
if j<M
ii=i; jj=j+1;
adj(k,sub2ind([N M],ii,jj)) = 1;
end
end
end
Comment cela peut-il amélioré pour éviter tous les le bouclage?
- non, ce n'est pas de devoirs. Mon but ultime est de tracer ces points et de tracer des lignes entre les points de connexion sous forme de graphique. La chose intéressante est que ces points n'ont pas à rester sur la grille..
Vous devez vous connecter pour publier un commentaire.
Si vous remarquez, il ya un motif distinct pour les matrices d'adjacence vous êtes en train de créer. Plus précisément, elles sont symétriques et bandes. Vous pouvez tirer parti de ce fait pour créer facilement votre matrices à l'aide de la
diag
de la fonction (ou lespdiags
fonction de si vous voulez faire une matrice creuse). Voici comment vous pouvez créer la matrice de contiguïté pour chaque cas, à l'aide de votre matrice d'échantillon ci-dessus à titre d'exemple:4-connecté voisins:
Et vous obtiendrez le tableau suivant:
8 relié voisins:
Et vous obtiendrez le tableau suivant:
Juste pour le fun, voici une solution pour construire la matrice de contiguïté par calcul de la distance entre toutes les paires de points sur la grille (pas le moyen le plus efficace de toute évidence)
Et voici un peu de code pour visualiser la matrice de contiguïté et le graphe de points de connexion:
Je viens de trouver cette question lors de la recherche pour le même problème. Cependant, aucune des solutions travaillé pour moi à cause de la taille du problème qui a nécessité l'usage de matrice creuse types. Voici ma solution qui fonctionne à grande échelle des instances:
Votre code actuel ne semble pas si mal. D'une façon ou d'une autre vous avez besoin pour itérer sur tous les voisin paires. Si vous avez vraiment besoin d'optimiser le code, je dirais:
1 <= i <= (N*M)
[i-M, i+1, i+M, i-1]
dans le sens horaireAvis que, pour obtenir toutes les voisin paires de nœuds:
i % M != 0
(depuis Matlab n'est pas basée sur 0 mais 1)i > M
Ce serait leed pour une seule boucle (mais même nombre de N*M itérations), à ne pas faire appel sub2ind(), et n'a que deux instructions if dans la boucle.
Viens de tomber sur cette question. J'ai un beau travail m-fonction (lien:
sparse_adj_matrix.m
) qui est assez général.Il peut gérer 4-connexion de la grille (dans un rayon de 1 selon la norme L1), 8-connexion de la grille (dans un rayon de 1 selon L_infty norme).
Il peut également aider à la 3D (et arbitrairement supérieur domensional grilles).
La fonction peut également connecter les nœuds plus loin que le rayon = 1.
Voici le signiture de la fonction:
100x200
) et je voudrais obtenir le valide 8-contiguïtés seulement pour les pixels blancs (foreground
), c'est à dire, dans certains cas, certains de la 8-voisins de(i,j)
ne sont pas valides car ils peuvent appartenir à l'arrière-plan. J'aimerais obtenir les seules celles qui sont au premier plan. Comment pourrais-je construire une matrice de contiguïté à l'aide de votresparse_adj_matrix
script?ii
etjj
vous pouvez sélectionner (à l'aide de logiques d'indexation), mais les indices qui appartient à pixels blancs.Pour chaque nœud dans le graphe d'ajouter une connexion à la droite et l'autre vers le bas. Vérifiez que vous n'avez pas trop loin de votre grille. Considérons la fonction suivante qui construit la matrice de contiguïté.
L'exemple ci-dessus
AdjMatrixLattice4(3,3)=