✔ Punkteansammlung zusammenfassen

chmee

chmee

verstaubtes inventar
Premium-User
N Abend Jungs.. Ich finde noch keinen konkreten effizienten Weg, jene Frage zu beantworten bzw. in Code umzuwandeln.

Gegeben:
In einer 2D-Welt (zB Koordinatensystem, Screen) sind Punkte verteilt, welche durch ihre Koordinaten bekannt sind, also ein Array (ID,X,Y). Diese Punkte entstehen durch die Analyse/Umformung eines Webcambildes, ergo ist zu 99,99% anzunehmen, dass sie sich an bestimmten Positionen häufen. Weiterhin ist die Position und die Pixelmenge dynamisch.
Points.gif
So sieht so ein Bild von der Webcam aus.

Gesucht:
Ein Algorithmus, der sinnvoll (logisch) nach Häufchen zusammenfasst, das Ergebnis könnte der Mittelpunkt sein oder auch die Umrahmung.
Points2.gif
Interessant wäre der Algorithmus und irgendein effizienter Ansatz. Muß ich wirklich n*(n-1) Vergleiche anstellen oder gibt es dafür seit dem Mittelalter bekannte Algorithmen? Fällt Jemandem eine Analogie aus einem anderen Fachbereich ein? Netzwerktopologien, Kartenvermessung, das Brückenproblem, Graphen etc pp...

Ich freu mich über jede Antwort, mal schauen, was ich lesen darf :D
mfg chmee
 
"Ein Algorithmus, der sinnvoll nach Häufchen zusammenfasst"? In der Informatik nennt man sowas das "Cluster Analysis", da gibts verschiedene Algorithmen...

Wenn du weißt, wieviele "Häufchen" auf dem Bildschirm sind kannst du zum Beispiel "k-means" durchführen. Ansonsten wären "CLARANS", "BIRCH" oder "DBSCAN" Algorithmen, die genau dein Problem lösen. Die geben dir dann die Punktmengen zurück, die du dann nur noch mit einem Rechteck umrahmen mußt.

Für alles weitere empfehle ich die (englische) Wikipedia, ich werd hier nicht alle Algorithmen diskutieren... :-)
 
Hi Chmee, ich bin nicht wirklich sehr mit Mathe vertraut. Jedoch dachte ich zuerst das jene Fragestellung sicher auch schon beim kartografieren von Sternenkarten und Haufenbestimmung vorkam.

Naja zumindest fand ich ein Forum in dem ein sehr ähnliches Thema behandelt wurde unter andren gehts um das Thema robuste Schätzverfahren vieleicht kommt das der Sache nahe.
Hier das angesprochene Forum: http://www.autoit.de/index.php?page=Thread&postID=108709

Edit: war wohl schon jemand schneller :D
 
Euch beiden vielen Dank. Auf den Punkt. Bin schon am Stöbern.

Achso, für die Faulen hier die Links zum Lesen:

RANSAC - http://de.wikipedia.org/wiki/RANSAC-Algorithmus
DBSCAN - http://de.wikipedia.org/wiki/DBSCAN#DBSCAN-Algorithmus
OPTICS - http://de.wikipedia.org/wiki/OPTICS

mfg chmee

p.s.: Joe, die Diskussion in Deinem angeführten Thread/Link zielt scheinbar auf einen (1!) gewichteten Punkt hinaus, das reicht mir nicht. Robust, ja, das muß mein Code werden, aber er muß definitiv auf mehrere Objekte/Cluster ausgerichtet sein. Anzahl der Cluster ist unbekannt. Ich lese mich grad in DBSCAN/OPTICS ein. (Wers sehr genau haben will, sollte mal nach CHAMELEON suchen)
 
Naja hätte auch eher von mir als Thread eines Forums benannt werden sollen als gleich als Forum betituliert.

Habe mir mal etwas dazu durchgelesen:
Moderne Clusteralgorithmen – eine vergleichende Analyse auf zweidimensionalen Daten
Dort scheints aber immer wieder kleinere Ausreisser zu geben so das es nicht vollends korreckt bestimmt wird. Noch dazu fallen ja einige Objekte,
je nachdem wie vermehrt verteilt sie auftreten,
nach dem bilden eines Rechtecks(Mittelpunktbestimmung) ja wieder raus. ODER das Rechteck überschneidet andre Objekte eines andren Clusters.

Puh also ich mit meinem Halbwissen würde sagen da hast du dir ja was vorgenommen. Bei mir raucht schon der Kopf wenn ich nur die Formeln sehe :D
Dennoch ein intressantes Thema möglicherweisse wurde dies auch schon in der Spieleprogrammierung benötigt.
 
Zuletzt bearbeitet:
Joe hat gesagt.:
Habe mir mal etwas dazu durchgelesen:
Moderne Clusteralgorithmen – eine vergleichende Analyse auf zweidimensionalen Daten
Zum Vergrößern anklicken....
Teile davon kommen mir bekannt vor, vermutlich aus der Einführungsvorlesung damals.
Joe hat gesagt.:
Dort scheints aber immer wieder kleinere Ausreisser zu geben so das es nicht vollends korreckt bestimmt wird. Noch dazu fallen ja einige Cluster,
je nachdem wie vermehrt verteilt sie auftreten,
nach dem bilden eines Rechtecks(Mittelpunktbestimmung) ja wieder raus. ODER das Rechteck überschneidet andre Cluster.
Zum Vergrößern anklicken....
Das ist normal, das es da Ausreisser gibt, jeder Algorithmus hat mal seine Stärken und Schwächen. Man muß halt den auswählen, der auf das persönliche Problem passt.
Joe hat gesagt.:
Puh also ich mit meinem Halbwissen würde sagen da hast du dir ja was vorgenommen. Bei mir raucht schon der Kopf wenn ich nur die Formeln sehe :D
Zum Vergrößern anklicken....
Für die Algorithmen gibts bestimmt schon Referenzimplementierungen, je nachdem in welcher Sprache man sie denn braucht. Für java würde ich zum Beispiel das Programm "Weka" anschauen, da sind DBSCAN und Konsorten bereits implementiert. Und da Weka OpenSource ist kann man sich da vielleicht bedienen, wenns keine lizenzrechtlichen Probleme gibt.

Für ein hierarchische Clustering habe ich auch noch ein paar Algorithmen bereits in der Schublade liegen. Aber ich hab auch eine Diplomarbeit in dem Themenumfeld geschrieben, daher ist das glaub ich auch verständlich. ;-)
Joe hat gesagt.:
Dennoch ein intressantes Thema möglicherweisse wurde dies auch schon in der Spieleprogrammierung benötigt.
Zum Vergrößern anklicken....

Wenn dich das Thema interessiert, das ist im Buch von Han und Kamber "Data Mining" meiner Meinung nach sehr gut erklärt (jedenfalls im englischen Original, die deutsche Übersetzung habe ich nie gelesen). Eher eine praktische Einführung gibt das Begleitbuch zu Weka.
 
So einfach ist es nun für mich auch nicht, aber am Ende zählt, dass ich es geschafft habe(n werde). Ich brauch eben so einen Alg. und anstatt mir einen auszudenken, der im schlimmsten Fall rumwackelt und langsam ist, stellt man eben solch eine Frage :D

Danke für die PDF - Abendlektüre fürs Allgemeinwissen (auch wenn ich auf Parties damit nicht wirklich rumstolzieren kann, vielleicht bei der statistischen Verteilung der belegten Brötchen)

mfg chmee
 
Das Bild oben ist aus vvvv - in welchem ich auch c#-code verbraten kann - und einige Algorithmen aus OpenCV (wie zB contour, trautner und haar) sind auch schon umgesetzt. contour ist meine aktuelle Basis, heisst also, ich hab mehrere Objekte, aber damit ist noch lange nicht geklärt, ob das ein Kopf, 2 Personen oder 5 Schneeflocken sind..

Nun ist mein simpler Ansatz, ich lasse zB max. 30 Objekte von contour finden und abhängig von ihrer Entfernung zueinander und örtlicher Häufung kann ich sagen, das ist ein Mensch (und keine Schneeflocke zb).. zB könnte ich definieren, mindestens 3-4 Objekte/Blobs in umittelbarer Umgebung sind ein Mensch, die andere Objekthäufung ist ein weiterer Mensch.. einzelne Objekte werden als Rauschen definiert und fliegen raus.

Dafür eben ein passender Alg.s
mfg chmee

Nachtrag Das oben verlinkte PDF (..vergleichende Analyse..) ist eine gute Basis für die Auswahl des geeigneten Algorithmus. BIRCH fällt bei mir raus, da es die Anzahl der zu findenden Cluster als Input benötigt. DBSCAN sagt mir zu, weil.. einfach mal selbst lesen :D

Hier noch eine weitere lesenswerte PDF - DBSCAN & Majorclust
http://www.uni-weimar.de/medien/webis/publications/downloads/theses/busch_2005.pdf
DBSCAN-Algorithmus als Pseudocode a.d. Seiten 41-45 erklärt.

Und Hier eine sehr gut lesbare Javascript-Umsetzung inkl. Begleittext zum Verstehen.
 
Ich hab mir einen simplen Algorithmus überlegt. Robust mit Sicherheit nicht, Clusterindizierung auch nicht eindeutig, aber erstmal funktionsfähig - und vor Allem recht schnell, weil immer O(n)=Sum(n) und nicht O(n)=n²-n.

Die Idee ist ganz einfach: Gegeben ist eine Punktesammlung, der erste Punkt wird ins Clusterarray kopiert. Nun wird mit einer Schleife i das Punktearray durchlaufen
(A) wenn der Punkt i(X,Y) einem Punkt im Clusterarray näher als "Distanz" wird er mit jenem Punkt C gemittelt - und der Clusterzähler clusterC wird um Eins erhöht
(B) wenn der Punkt i keinem Punkt in C nahe genug ist, wird jener Punkt als neuer Clusterpunkt C eingetragen und der Clusterzähler clusterC bekommt eine 1 eingetragen.

Bei der Ausgabe kommt noch die minimale Anzahl von Punkten zum Tragen - wenn ein Cluster also mindestens aus minPTS Punkten generiert ist, so soll er ausgegeben werden.

Quellcode in html/css/php (einfach nur copy/paste, fertig zum Anschauen)
HTML: 
<!DOCTYPE html PUBLIC
    "-//W3C//DTD XHTML 1.0 Transitional//EN"
    "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="de">
    <head>
       <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
        <title>phreekz simplest Cluster</title>
        <style type="text/css">
        body {
          margin:0px;
          padding:0px;
          }
          .pts{width:10px;
          height:10px;
          background-color:#00ff00;
          font-size:8px;
          z-index:20}
          .clu{background-color:#cc0000;
          font-size:10px;
          color:#fff;
          text-align:center;
          z-index:10}
        </style>
    </head>
    <body>
<?php
$posX=array();
$posY=array();
$clusterX=array();
$clusterY=array();
$clusterC=array();

// Punkte per random generieren
for($i=0;$i<40;$i++)
{
 $posX[$i]=rand(1,400);
 $posY[$i]=rand(1,400);
}
$lenPts=count($posX);
$minPTS=1;
$distance=80;

$clusterX[]=$posX[0];
$clusterY[]=$posY[0];
$clusterC[]=1;
for($a=0;$a<$lenPts;$a++)
{
  echo "<div class='pts' style='position:absolute;top:".$posX[$a]."px;left:".$posY[$a]."px;'>".$a."</div>";

  $cluster=-1;
  $lenCluster=count($clusterX);
  //echo $lenCluster."<br/>";
  for($b=0;$b<$lenCluster;$b++)
  {
    $distx=$posX[$a]-$clusterX[$b];
    $disty=$posY[$a]-$clusterY[$b];
    $Dist=sqrt($distx*$distx+$disty*$disty);
    //echo $distx." - ".$disty." - ".$Dist."<br/>";
    if($Dist>$distance)
    {
    //echo "NEW-";
    }
    else
    {
      $cluster=$b;
      //echo "OLD-";
    }
  }
  if($cluster==-1)
  {
    $clusterX[]=$posX[$a];
    $clusterY[]=$posY[$a];
    $clusterC[]=1;
    //echo "NEW cluster<br/>";
  }
  else
  {
    $clusterX[$cluster]=($clusterX[$cluster]+$posX[$a])/2;
    $clusterY[$cluster]=($clusterY[$cluster]+$posY[$a])/2;
    $clusterC[$cluster]=$clusterC[$cluster]+1;
    //echo "old cluster<br/>";
  }
}
for($d=0;$d<count($clusterX);$d++)
{
  if($clusterC[$d]>$minPTS)
  {
    echo "<div class='clu'";
    echo " style='position:absolute;top:".$clusterX[$d]."px;left:".$clusterY[$d]."px;";
    echo "width:".(15+$clusterC[$d]*5)."px;height:".(15+$clusterC[$d]*5)."px;'>".$d." - ".$clusterC[$d]."</div>";
  }
}
?>
 </body>
</html>

Wie es mit Daten klarkommt, die sich ~25Hz ändern, werd ich heut abend sehen ;)

mfg chmee
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück