k-center Problem vs. k-means Clustering

#1
Hi,
beim k-means Clustering ist mir bekannt, dass dieser sehr häufig in der Bildverarbeitung (v.a. medizinischen Bildverarbeitung) verwendet wird.
Beim Lesen einiger Paper zum k-center Problem bin ich nun schon mehrmals darauf gestoßen, dass diesen neben der Lösung der Platzierung von Warenhäusern auch für die Bildverarbeitung verwendet wird.
Was ich suche wäre ein konkretes Beispiel in der Bildverarbeitung (vorzugsweise medizinische Bildverarbeitung) in welchem das k-center Problem jemals verwendet wurde.
Während ich zum k-means Clustering geradezu Unmengen an Beispielen finde, finde ich zum k-center Problem keines.

Hat jemand einen Tipp?
 

-AB-

Well-Known Member
c-b Team
c-b Experte
#2
Auf einem Bild würden beide Algorithmen (bzw: k-means und ein Algorithmus, der k-center löst) ja relativ ähnlich agieren.
Grob gesagt würde man k Pixel suchen, die das Bild, bzw, dessen Features, optimal abdecken - aber anstatt die gemittelte Distanz der zugeordneten Pixel zu minimieren, minimiert man die maximale Distanz.

Distanz ist hier natürlich nicht nur von den Koordinaten des Pixels, sondern auch seines Wertes abhängig.

bin ich nun schon mehrmals darauf gestoßen, dass diesen neben der Lösung der Platzierung von Warenhäusern auch für die Bildverarbeitung verwendet wird.
Hm. Zitieren die ihre Quellen? ;)

Hmm. Diese Quelle hier nutzt scheinbar k-center um k-means zu initialisieren.... Ist wohl nicht ganz das, was du dir erhofft hast ;)

Hmm, wenn man 5 Anti-Krebs Spritzen setzen möchte, und jede hat eine limitierte "Wirkungsreichweite" - dann könnte man k-center nutzen, um 5 Punkte zu finden, die die maximale Distanz zwischen Stich und detektierter Tumorzelle minimieren. Hierfür ist ja unwichtig, exakt welche Zelle von welcher Spritze betroffen wird, eine Zuordnung ist also nicht nötig. Außerdem ist die durchschnittliche Distanz unwichtig, sondern nur die maximale - es sollen eben alle Zellen erreicht werden.

Ist natürlich wild aus den Fingern gesogen. Aber vielleicht für ein Problem dieser Art.
 
#3
Vielen Dank für die schnelle Antwort.

Auf einem Bild würden beide Algorithmen (bzw: k-means und ein Algorithmus, der k-center löst) ja relativ ähnlich agieren.
Genau davon bin ich bisher auch ausgegangen.

Grob gesagt würde man k Pixel suchen, die das Bild, bzw, dessen Features, optimal abdecken - aber anstatt die gemittelte Distanz der zugeordneten Pixel zu minimieren, minimiert man die maximale Distanz.
genau, nach meinem Verständnis sollen die Kreise, welche jeweils Pixel mit ähnlichen Merkmalen beinhalten, minimal sein und somit einen möglichst großen Abstand zueinander haben.

Distanz ist hier natürlich nicht nur von den Koordinaten des Pixels, sondern auch seines Wertes abhängig.
Hm. Zitieren die ihre Quellen? ;)
Leider nicht.

Hmm. Diese Quelle hier nutzt scheinbar k-center um k-means zu initialisieren.... Ist wohl nicht ganz das, was du dir erhofft hast
ja leider nicht, aber trotzdem interessant der Ansatz in diesem Paper

Hmm, wenn man 5 Anti-Krebs Spritzen setzen möchte, und jede hat eine limitierte "Wirkungsreichweite" - dann könnte man k-center nutzen, um 5 Punkte zu finden, die die maximale Distanz zwischen Stich und detektierter Tumorzelle minimieren. Hierfür ist ja unwichtig, exakt welche Zelle von welcher Spritze betroffen wird, eine Zuordnung ist also nicht nötig. Außerdem ist die durchschnittliche Distanz unwichtig, sondern nur die maximale - es sollen eben alle Zellen erreicht werden.

Ist natürlich wild aus den Fingern gesogen. Aber vielleicht für ein Problem dieser Art.
Diesen Gedanken find ich sehr sehr interessant. Vielleicht geht der Einsatz von Algorithmen zum k-Center Problem mehr in Richtung Operationsplanung oder Therapieplanung für welche ja ebenfalls Bilddaten nötig sind. Nur das in diesem Fall vielleicht die Segmentierung (Feststellen wo sich z.B. der Tumor befindet) bereits durch ein anderes Clusterverfahren, z.B. k-means, stattgefunden hat und anschließend u.a. für die Planung das k-Center eingesetzt wird.
 

-AB-

Well-Known Member
c-b Team
c-b Experte
#4
Clusterisierung mit bekannter Anzahl ist in diesem Feld doch ohnehin.... Seltsam?

Vielleicht geht es auch um völlig andere Cluster. Solange man die Distanz/Differenz zwischen zweier Individuen/Knoten messen kann, lassen sich obige Verfahren ja anwenden.
So könnte man z.B. Bilder von Lungengewebe (oder etwas beliebig anderem) in eine bestimmte Anzahl von Krankheitsbildern aufteilen (Weil man wusste, dass man Bilder von gesunden Lungen, entzündeten Lungen, Raucherlungen und Asbestlungen hat) und dann mittels k-center quasi ein "Paradebeispiel" für jede Krankheitsform raussuchen.
 
#5
Clusterisierung mit bekannter Anzahl ist in diesem Feld doch ohnehin.... Seltsam?
Bei Anwendung der Clusteranalyse zur Segmentierung von medizinischen Bilddaten (z.B. mit Hilfe von k-means) werden Bildmerkmale als homogene Bildstrukturen betrachtet, d.h. diese Pixel weisen ähnliche Merkmalsvektoren auf. Also wird hier die Analyse vom Bildraum in den Merkmalsraum verlegt.
Im Merkmalsraum wird dann nach Cluster gesucht, danach erfolgt eine Rücktransformation in den Bildraum, sodass zuvor im Merkmalsraum zusammenhängende Segmente (Cluster) im Bildraum nicht mehr zusammenhängend sind, da z.B. verstreute Tumore vorliegen.

Wenn man k=2 wählt erhält man eine Gruppierung der Objekt- und Hintergrundpixel in 2 Clustern.
Wenn man k sukzessive erhöht erhält man eine Feindifferenzierung der Bildstrukturen, sodass bei einem bestimmten k der Tumor zu einem großen Teil erkannt werden kann. Sicher kommt es bei einem zu groß gewählten k zu einer Übersegmentierung, d.h. die Bildstrukturen werden zersplittert.
Hier wäre dann wohl der Experte der erfahrene Arzt gefragt welche k's interessant sind.

Inwieweit sich k-center beim clustern von Merkmalsvektoren im Merkmalsraum von k-means unterscheiden würde bzw. ob überhaupt sinnvoll sein könnte, ist bei mir momentan noch eine offene Frage. Ich tendiere momentan mehr zur Möglichkeit das k-center in der Operations-und/oder Therapieplanung infolge vorliegender segmentierter Bilddaten eingesetzt werden könnte. Ich verbinde k-center immer noch mit Anwendungen in welchen Entfernungen, Erreichbarkeiten etc. eine große Rolle spielen. Aber möglicherweise irre ich mich hier und erkenne einen besonderen möglichen Einsatz von k-center in der Bildverarbeitung nicht.
 
Oben