K-Means Algorithmus - Ich verstehe es einfach nicht

[wurstsalat]

Hallo, ich versuche gerade einen K-Means Algorithmus selber zu schreiben.

Ich mache das gerade in Matlab aber im Prinzip denke ich ist die Syntax erstmal egal - ich komme leider nicht voran.

Zwei Probleme die ich scheinbar habe sind:

- Ich lande immer in einem endlos-loop wenn ich zu dem norm() kommando komme, welches mir in einachen tests die euclidische distanz zwischen den beiden momentanen vektoren liefern soll

- Leider bin ich mir auch noch immer unsicher wie ich denn am Ende den neuen Mittelwert wieder nach oben schicken kann und ob ich das alles richtig mache.

Im Prinzip schwimme ich noch ein wenig und trotz viel Nachlesen komme ich nicht voran. Kann mir irgendwer auf die Spruenge helfen bitte??

---

function [label, newI] = kmeans(I, K)


[Iheight, Iwidth, bits] = size(I)

Ilength = Iheight * Iwidth


I = reshape(I,[],3);

I = im2double(I);


Label = zeros(Iheight * Iwidth, 1);



%create random absolute RGB values for Ktemp

Ktemp = rand(1,3) * 255

Kcompare = 0




while Kcompare ~= Ktemp

    Kcompare = Ktemp


    %cycle through each RGB value in image

    for n = 1 : Ilength


        min = inf;


        %cycle through each centroid

        for i = 1 : K


            %measure eucledian distance between centroid and RGB value

            distance = norm(Ktemp - I(n,);


            %if distance is less than minimum assign current centroid

            if distance < min;

                min = distance;

                label(n) = K;

            end

        end

    end


    % ==> each RGB value in I has a label now



    %cycle through K's

    for i = 1 : K


        %set count and Ktemp to 0

        count = 0

        Ktemp = [0,0,0]


        %go through each row and add up values for current K

        for n = 1 : 1 : Ilength

            if label(n) == K

                count = count + 1

                ktemp = ktemp + I(n,

            end

        end

        Ktemp = Ktemp / count

    end


end


newI = reshape(l, Iwidth, Iheight);








  --[/code]

[flashpixx]

help kmeans

sollte helfen. Ich empfehle aber ein Neural Gas

Phil

[wurstsalat]

was ist ein Neural Gas ?

Der Kmeans Hilfe bin ihc mir natuerlich bewusst, aber ich komme trotzdem nicht weiter. Zumal ich ja meinen eigenen schreiben will und nicht den schon implementierten benutzten will.

Mein Problem scheint zu sein, dass es zum einen selbst bei einem Bild von 50x50 pixeln ziemlich lange (eine minute) dauert um am Ende des Algorithmuses anzukommen und ausserdem scheine ich immer nur Label Nummer 1 zuzuweisen, anstatt durch die K's durch zu gehen.

[flashpixx]

zum k-Mean: Numerical Recipes Electronic

Der k-Mean muss nicht zwingend zu einem sinnvollen Ergebnis kommen, denn er ist initialisierungsabhängig. ZUm Code selbst, arbeite nicht mit einzelnen Vektoren, sondern mit Matrizen, sprich wenn Du 3 auf jedem Farbanteil Deines Bildes einen k-Mean laufen lassen willst, würdest Du eine 3x2 Matrix verwenden, wobei die Spalten dann die Clusterzentren sind.

Weiterhin ist mir aber nicht klar, was Dein Code bewirken soll, sehe ich das richtig, dass Du versuchst in einem RGB Bild für jeden Farbanteil ein Zentrum zu bestimmen? Wenn das ist, dann kannst Du nicht mit den Werten 0..255 arbeiten, sondern Deine Daten müssen binär vorliegen, sprich Du musst diskretisieren. Das Zentrum wird sich dann so im 2D bei Dir anordnen, dass es von allen Punkten gleich weit entfernt liegt

Ich würde eher ein Neural Gas oder Spectral Clustering verwenden, da sie wesentlich stabiler sind:

Neural gas - Wikipedia, the free encyclopedia

Cluster analysis - Wikipedia, the free encyclopedia

Phil

[wurstsalat]

Danke fuer die Antwort.

Ich versuche mal zu erklaeren, tut mir leid aber mein Deutsch ist ein wenig eingerostet -

Ich bin mir bewusst, dass es bessere Methoden gibt, es geht hier um das Prinzip bzw. eine Uebung fuer einen Test. Ich kannte den Neural Gas Algorithmus allerdings noch nicht, sehr interessant.

Ich verstehe nicht 100% was du mit dem Vektoren/Matrizten Kommentar gemeint hast aber ich glaube ich habe das jetzt richtig gemacht, siehe unten?

Der Code waehlt k zufaellig generierte RGB Centroid-Farbwerte aus, scannt das Bild nach aehnlichen Farbwerten und gibt den Werten die dem jeweiligen Centroid-Wert am naechsten liegen ein label, dann wir der entsprechende Centroid neu justiert und auf den Mittelwert der mit ihm zusammenhaengenden Farbwerte gestellt. Dann geht es wieder von vorne los.

Somit kann man Objekte in einem Bild erkennen wenn diese farblich von Hintergruenden oder anderen Objekten trennbar sind. Dies funktoiniert natuerlich nur sinnvoll wenn die Anzahl der Zentren gut gewaehlt ist (das ist nochmla ein aderes Thema), aber mal angenommen du und dein bester Freund stehen in einem blauen und roten Anzug vor einer weissen wand, dann sollte ich hier am Ende ein neues Bild rausbekommen was mir mit drei Farbwerten (jeweils der Mittelwert von dem blaune, roten und weissen bereich) die Objekte darstellt.

Leider habe ich noch immer das Problem, dass ich die Farbwerte nicht rauskriege, sondern scheinbar nur wieder das Gleiche bild. Ich verstehe irgendetwas noch nicht, kannst du vielleicht mal unabhaengig davon ob du mit dem algorithmus einverstanden bist probieren zu erklaeren warum ich das nicht herauskriege? Waere sehr toll, vielen Dank!

function [newI] = kmeans(I, K)


[Iheight, Iwidth, bits] = size(I);

Ilength = Iheight * Iwidth;


I = reshape(I,[],3);

I = im2double(I);


label = zeros(Iheight * Iwidth, 1);



%create k amount of random absolute RGB values for Ktemp

Ktemp = rand(K,3) * 255;


Kcompare = 0;


while Kcompare ~= Ktemp

    Kcompare = Ktemp;


    %cycle through each RGB value in image

    for n = 1 : Ilength


        min = inf;


        %cycle through each centroid

        for i = 1 : K


            %measure eucledian distance between centroid and RGB value

            distance = norm(Ktemp(K, - I(n,);


            %if distance is less than minimum assign current centroid

            if distance < min

                min = distance;

                label(n) = K;

            end

        end

    end


    % ==> each RGB value in I has a label now



    %cycle through K's

    for i = 1 : K


        %set count and Ktemp to 0

        count = 0;

        Ktemp = zeros(K,3);


        %go through each row and add up values for current K

        for n = 1 : 1 : Ilength

            if label(n) == K

                count = count + 1;

                Ktemp(i, = Ktemp(i, + I(n,;

            end

        end

        Ktemp = Ktemp / count;

    end


end


newI = reshape(I, Iwidth, Iheight, 3);



  [/code]

[flashpixx]

Ich bin mir bewusst, dass es bessere Methoden gibt, es geht hier um das Prinzip bzw. eine Uebung fuer einen Test. Ich kannte den Neural Gas Algorithmus allerdings noch nicht, sehr interessant.

Somit kann man Objekte in einem Bild erkennen wenn diese farblich von Hintergruenden oder anderen Objekten trennbar sind. Dies funktoiniert natuerlich nur sinnvoll wenn die Anzahl der Zentren gut gewaehlt ist (das ist nochmla ein aderes Thema), aber mal angenommen du und dein bester Freund stehen in einem blauen und roten Anzug vor einer weissen wand, dann sollte ich hier am Ende ein neues Bild rausbekommen was mir mit drei Farbwerten (jeweils der Mittelwert von dem blaune, roten und weissen bereich) die Objekte darstellt.

Du kannst nicht einfach den k-Mean auf ein Bild anwenden. Du musst diskrete Werte verwenden. Du möchtest Farbcluster in Deinem Bild finden, d.h. Du musst den k-Mean für jeden Farbanteil RGB durchführen und vor allem darfst Du nicht, die Farbwerte auslesen, sondern Du musst die Informationen als Vektoren in einem Raum beschreiben in dem Du dann clusterst.

Ich möchte jetzt nicht die Grundlagen eines Clusteringverfahren diskutieren, aber wie mir scheint, ist die Grundüberlegung in Deinem Algorithmus schon falsch.

Phil

[wurstsalat]

Jeder Farbwert ist ein Punkt in 3D. Meine K Anzahl von zufallsgenerierten Zentren hat auch jeweils 3 (RGB) Koordinaten. Ich berechne den Unterschied zwischen jedem Pixel im Bild und den Zentren (euklidischer Abstand, norm() ) und markiere die Pixel entsprechend ihrer Zugehoerigkeit. Dann basierend auf den Durchschnittswert der Pixel rejustiere ich das neue Zentrum.

D.h. ich berechne den Vektor zwischen zwei Punkten!

Entweder verstehe ich dich ueberhaupt nicht oder umgekehrt?

[flashpixx]

D.h. ich berechne den Vektor zwischen zwei Punkten!

Nein, definitiv nicht: Du berechnest den Farbvektor zwischen 2 Farbvektoren, das würde bildlich einenem Vektor innerhalb des RGB Würfels entsprechen. Du arbeitest nicht auf den Positionen, sondern auf Farben !!

Überlege dir folgendes:

Du suchst in einem weißen Bild einen schwarzen Punkt. Wenn ich Deine Farbvektoren betrachte, dann hast Du dort entweder [0 0 0] oder [1 1 1]

stehen.

Was Du aber möchtest ist die Position des schwarzen Punktes also [0..Picture-Width, 0..Picture-Height] und den dahinter liegenden Farbvektor.

Du möchtest in einem Bild eine Fläche / Zentrum finden. Im Moment versuchst Du eine Anhäufung von Farben zu finden.

Phil

[wurstsalat]

Aaah - jetzt verstehen wir uns (nicht) !

Du hast schon recht, aber genau das will ich ja auch tun, ich will nach Farben clustern.

Wie schon in dem oben gennanten Beispiel versucht habe zu erklaeren, wenn du in einem roten Anzug vor einer weissen Wand stehst dann will ich eine Selektion aller "roten" Pixel dem einen Cluster zugewiesen haben (label 0) und eine Selektion der anderen, "weissen" Pixel dem zweiten Cluster zugewiesen haben (label1).

Dann will ich den Mittelwert der roten Pixel hernehmen und alle Pixel mit label 0 mit diesem Mittelwert ersetzten. Das Gleiche mit weiss. Am Ende ist also bei z.b. zwei Clustern ein Bild entstanden, dass nur zwei Farben hat und dich von der Wand differenziert.

[flashpixx]

Okay, dann ist klar ein Farbclustering, d.h. Du hast Pixtur-Weight * Picture-Height Vektoren. Ich rate Dir ganz dringend nicht k-Mean einzusetzen, sondern andere Verfahren, die Konvergenz wird wohl Schwierigkeiten machen.

Warum verwendest Du nicht zunächst die kmean Funktion von Matlab und schaust zunächst, ob es das gewünschte Ergebnis liefert, wenn es das dann macht, dann kannst Du ihn selbst implementieren.

Ich kann Dir aber wirklich zu einem Neural Gas raten, siehe die freie Matlab Toolbox: SOM Toolbox

Phil