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.

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.

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
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=...&postID=108709

Edit: war wohl schon jemand schneller

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
Dennoch ein intressantes Thema möglicherweisse wurde dies auch schon in der Spieleprogrammierung benötigt.

Zitat von Joe

Habe mir mal etwas dazu durchgelesen:
Moderne Clusteralgorithmen – eine vergleichende Analyse auf zweidimensionalen Daten

Teile davon kommen mir bekannt vor, vermutlich aus der Einführungsvorlesung damals.

Zitat von Joe

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.

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.

Zitat von Joe

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

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.

Zitat von Joe

Dennoch ein intressantes Thema möglicherweisse wurde dies auch schon in der Spieleprogrammierung benötigt.

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

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

Hallo,

mit welcher Technolgoie möchtest du denn diesen Anwendungsfall implementieren?

Eine gute Anlaufstelle wäre IMHO opencv:
http://opencv.willowgarage.com/wiki/
Dort findest du zahlreiche Verfahren und Algorithmen aus dem Beriech Computer Vision

Auch noch was schickes:
http://www.lac.inpe.br/JIPCookbook/5...uzzycmeans.jsp

Gruß Tom

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

Hier noch eine weitere lesenswerte PDF - DBSCAN & Majorclust
http://www.uni-weimar.de/medien/webi...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-Code:

<!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

Wen's noch interessiert. Hier ein Video von der Beta:



Am Besten in FullHD anschauen..
mfg chmee

Hi,

das sieht ja mal krass aus Was soll das denn werden wenns fertig ist?

Gruß Tom

Wenns fertig ist, kann ich Näheres dazu sagen

mfg chmee

Ist es mittlerweile fertig?

Ja, Projektübergabe war 04.02.2011. Es ging um eine Objektverfolgung via vvvv (deswegen auch die Programmierung in c#). Das Ziel war aber, nicht eine Person zu verfolgen, sondern 2 oder 3 Personen auseinander zu halten. Wir haben vor eine Webcam noch eine Türspionlinse angebracht, kamen damit auf einen etwa 6m breiten Sichtbereich bei ~3,30m Entfernung, die Schärfe spielte keine Rolle.

Knotenreihenfolge war (vereinfacht)

VideoIn(webcam)
->
Trautner (Differenzbilder von aufeinanderfolgenden Frames erstellen) - OpenCV-Modul in vvvv
->
Contour (Blobs erkennen/erstellen, als Koordinaten ausgeben) - OpenCV-Modul in vvvv
->
Cluster (Blobs zusammenfassen zu Gruppen via DBSCAN-Algorithmus) - vvvv-Modul hier

mfg chmee