Algorithme de détection des "grappes" de points

Question

J'ai une zone 2D avec des "points" répartis sur cette zone. J'essaie maintenant de détecter des "grappes" de points, c'est-à-dire des zones présentant une certaine densité élevée de points.

Avez-vous des idées (ou des liens vers des articles) sur la manière de détecter élégamment ces zones ?

Answer 1

Pourquoi ne pas définir une résolution arbitraire pour votre espace, et calculer pour chaque point de cette matrice, une mesure de la distance de ce point à tous les points, puis vous pourriez faire un "graphique thermique" et utiliser un seuil pour définir les groupes.

C'est un bon exercice pour le traitement, peut-être que plus tard je posterai une solution.

EDIT :

C'est ici :

//load the image
PImage sample;
sample = loadImage("test.png");
size(sample.width, sample.height);
image(sample, 0, 0);
int[][] heat = new int[width][height];

//parameters
int resolution = 5; //distance between points in the gridq
int distance = 8; //distance at wich two points are considered near
float threshold = 0.5;
int level = 240; //leven to detect the dots
int sensitivity = 1; //how much does each dot matters

//calculate the "heat" on each point of the grid
color black = color(0,0,0);
loadPixels();
for(int a=0; a<width; a+=resolution){
  for(int b=0; b<height; b+=resolution){
    for(int x=0; x<width; x++){
      for(int y=0; y<height; y++){
        color c = sample.pixels[y*sample.width+x];        
        /**
         * the heat should be a function of the brightness and the distance, 
         * but this works (tm)
         */
        if(brightness(c)<level && dist(x,y,a,b)<distance){
          heat[a][b] += sensitivity;
        }
      }
    }
  }
}

//render the output
for(int a=0; a<width; ++a){
  for(int b=0; b<height; ++b){
    pixels[b*sample.width+a] = color(heat[a][b],0,0);
  }
}
updatePixels();
filter(THRESHOLD,threshold);

EDIT 2 (code un peu moins inefficace mais même résultat) :

//load the image
PImage sample;
sample = loadImage("test.png");
size(sample.width, sample.height);
image(sample, 0, 0);
int[][] heat = new int[width][height];
int dotQ = 0;
int[][] dots = new int[width*height][2];
int X = 0;
int Y = 1;

//parameters
int resolution = 1; //distance between points in the grid
int distance = 20; //distance at wich two points are considered near
float threshold = 0.6;
int level = 240; //minimum brightness to detect the dots
int sensitivity = 1; //how much does each dot matters

//detect all dots in the sample
loadPixels();
for(int x=0; x<width; x++){
 for(int y=0; y<height; y++){
   color c = pixels[y*sample.width+x];
   if(brightness(c)<level) {
       dots[dotQ][X] += x;
       dots[dotQ++][Y] += y;
   }
 }
}

//calculate heat
for(int x=0; x<width; x+=resolution){
 for(int y=0; y<height; y+=resolution){
   for(int d=0; d<dotQ; d++){
     if(dist(x,y,dots[d][X],dots[d][Y]) < distance)
       heat[x][y]+=sensitivity;
   }
 }
}

//render the output
for(int a=0; a<width; ++a){
 for(int b=0; b<height; ++b){
   pixels[b*sample.width+a] = color(heat[a][b],0,0);
 }
}
updatePixels();
filter(THRESHOLD,threshold);

/** This smooths the ouput with low resolutions
* for(int i=0; i<10; ++i) filter(DILATE);
* for(int i=0; i<3; ++i) filter(BLUR);
* filter(THRESHOLD);
*/

Et la sortie avec un échantillon Kent (réduit) :

Answer 2

Je suggère d'utiliser un noyau à décalage moyen pour trouver le centre de densité de vos points.

Illustration du décalage moyen http://cvr.yorku.ca/members/gradstudents/kosta/compvis/file_mean_shift_path.gif

Cette figure montre qu'un noyau à décalage moyen (centré initialement sur le bord de l'amas) converge vers le point de densité maximale de l'amas.

En théorie (en résumé) :

Plusieurs réponses à cette question ont déjà fait allusion à la manière de faire du mean-shift :

• Papa brouille l'image et trouve le point le plus sombre. est en fait un estimation de la densité du noyau (KDE), qui est la base théorique du mean-shift.

• Les deux sites j0rd4n y Bill le Lézard a suggéré de discrétiser votre espace en blocs et d'inspecter leurs densités.

Ce que vous voyez dans la figure animée est une combinaison de ces deux suggestions : elle utilise un "bloc" mobile (c'est-à-dire le noyau) pour rechercher la densité localement la plus élevée.

Le décalage moyen est une méthode itérative qui utilise un voisinage de pixels appelé le noyau (similaire à celui-ci ) et l'utilise pour calculer le moyenne des données d'image sous-jacentes. Le site moyenne dans ce contexte est la moyenne pondérée par les pixels des coordonnées du noyau.

A chaque itération, le moyenne du noyau définit ses coordonnées centrales pour l'itération suivante - c'est ce que l'on appelle le équipe . D'où le nom décalage moyen . La condition d'arrêt des itérations est lorsque la distance de décalage tombe à 0 (c'est-à-dire que nous sommes au point le plus dense du voisinage).

Une introduction complète au décalage moyen (à la fois en théorie et en application) peut être trouvée dans cette présentation ppt.

En pratique :

Une implémentation du décalage moyen est disponible dans OpenCV :

int cvMeanShift( const CvArr* prob_image, CvRect window,
                 CvTermCriteria criteria, CvConnectedComp* comp );

O'Reilly's Learning OpenCv (extraits du livre sur Google) a également une bonne explication sur son fonctionnement. En gros, il suffit de lui fournir votre image de points (prob_image).

En pratique, l'astuce consiste à choisir la taille de noyau adéquate . Plus le noyau est petit, plus vous devez l'initier près du cluster. Plus le noyau est grand, plus votre position initiale peut être aléatoire. Cependant, s'il y a plusieurs groupes de points dans votre image, le noyau peut converger juste entre eux.

Answer 3

Pour ajouter un peu d'aide à Trebs Je pense qu'il est important de définir d'abord de manière réaliste ce qu'est un cluster. Bien sûr, "des points plus proches les uns des autres", c'est plutôt vague.

Prenez cet ensemble d'échantillons que j'ai généré, je sais qu'il y a une forme de cluster là, je l'ai créé.

Cependant, l'identification programmatique de ce "cluster" pourrait être difficile.

Un humain pourrait considérer qu'il s'agit d'un grand amas toroïdal, mais votre programme automatisé va plus probablement décider qu'il s'agit d'une série de petits amas à proximité semi-étroite.

Notez également qu'il existe des régions de très haute densité qui, dans le contexte de l'image globale, ne sont que des distractions.

Vous devrez tenir compte de ce comportement et éventuellement enchaîner des groupes de densité similaire séparés seulement par des vides insignifiants de densité inférieure, selon l'application spécifique.

Quoi que vous développiez, je serais au moins intéressé de savoir comment il identifie les données de cet ensemble.

(Je pense qu'il serait bon d'examiner les technologies derrière le HDRI ToneMapping, car elles fonctionnent plus ou moins sur la densité de lumière, et il existe des cartes de tonalité "locales" et des cartes de tonalité "globales", chacune donnant des résultats différents).

Answer 4

Appliquez un filtre de flou à une copie de votre zone 2D. Quelque chose comme

1 2 3 2 1
2 4 6 4 2
3 6 9 6 3
2 4 6 4 2
1 2 3 2 1

Les zones "plus sombres" identifient maintenant des groupes de points.

Answer 5

Vous pouvez essayer de créer un Quadtree représentation des données. Les chemins les plus courts du graphique correspondraient aux zones à forte densité.

Ou, pour le dire plus clairement : avec un Quadtree et une traversée par ordre de niveau, chaque nœud de niveau inférieur composé de "points" représente une zone de haute densité. À mesure que le niveau des nœuds augmente, ces nœuds représentent des zones de plus faible densité de "points".