G06V 10/762
Definition
Diese Klassifikationsstelle umfasst:Techniken zur Gruppierung von Mustern, um eine bestimmte Struktur oder eine Bedeutung in Bildern oder Videos zu entdecken.
Anmerkungen – technischer Hintergrund
Diese Anmerkungen liefern weitere Informationen über die technischen Sachverhalte, die in diese Stelle klassifiziert werden:
Das Ziel der hier klassifizierten Techniken ist es, Gruppen ähnlicher Objekte zu identifizieren und Objekte einer Gruppe (Cluster) entsprechend einem Maß für ihre Ähnlichkeit zuzuordnen. Die Trennbarkeit wird durch Messung der Ähnlichkeit oder Unähnlichkeit bestimmt. Solche Verfahren werden in der Regel in einem hochdimensionalen Merkmalsraum durchgeführt, der durch Extraktion von Merkmalen aus dem Bild oder Video konstruiert wird, können aber auch in der ursprünglichen Domäne durchgeführt werden, z.B. in der Bilddomäne im Falle der Bildsegmentierung.
Bei der Gruppierung von Mustern kann jedes Muster ausschließlich zu einem einzigen Cluster gehören (hartes Clustering) oder, entsprechend einem Ähnlichkeitsmaß (oder Proximitätsmaß), zu einem gewissen Grad gleichzeitig zu mehreren Clustern gehören (unscharfes Clustering [Fuzzy Clustering]). Zudem kann die Ähnlichkeit je nach dem verwendeten Clustering-Verfahren (a) zwischen Vektoren, (b) zwischen einem Vektor und einer Vektormenge (oder einem Cluster) und (c) zwischen Vektormengen (oder verschiedenen Clustern) definiert werden.
Beispiele für Proximitätsmaße sind: Unähnlichkeitsmaße (basierend auf l1-, l2- und l∞-Normen), Ähnlichkeitsmaße (inneres Produkt, Kosinus, Korrelationskoeffizient nach Bravais-Pearson, Tanimoto-Abstand usw.).
Zu den Clustering-Algorithmen gehören:
a) Clustering auf der Grundlage statistischer Maße (die hauptsächlich numerische Daten verwenden), die eine Kostenfunktion J in Bezug auf mögliche Gruppierungen festlegen, welche einem globalen oder lokalen Optimierungskriterium unterliegt, und ein Clustering liefern, das J optimiert. Beispiele für solche Algorithmen sind:
- Harte Clustering-Algorithmen, bei denen ein Vektor ausschließlich zu einem bestimmten Cluster gehört, z.B. k-Means, k-Medoids, Linde-Buzo-Gray, ISODATA, DBSCAN, Neural Gas;
- Unscharfe Clustering-Algorithmen, bei denen ein Vektor bis zu einem gewissen Grad zu einem bestimmten Cluster gehört, z.B. Fuzzy c-Means, Adaptive Fuzzy C-Shells [AFCS], Fuzzy C Quadric Shells [FCQS] oder Modified Fuzzy C Quadric Shells [MFCQS];
- Probabilistische Clustering-Algorithmen, die bayesschen Klassifizierungsargumenten folgen und bei denen jeder Vektor dem Cluster gemäß einem probabilistischen Konzept zugewiesen wird, z.B. Expectation-Maximization [ EM], Gaussian Mixture Model [ GMM] oder Mean-Shift;
b) Graphbasierte Clustering-Algorithmen, z.B. Minimum Spanning Tree [MST] Clustering, Clustering auf der Grundlage gerichteter Bäume, spektrales Clustering, Graph-Cut-Optimierung;
c) Kompetitive Lernalgorithmen für das Clustering, bei denen eine Gruppe von Repräsentanten ausgewählt wird und das Ziel darin besteht, alle Repräsentanten in Regionen eines Vektorraums zu verschieben, die in Bezug auf andere Vektoren “dicht” sind. Beispiele sind Leaky-Learning-Algorithmen, selbstorganisierende Karten [Self-Organizing Maps, SOM], lernende Vektorquantisierung [Learning Vector Quantisation, LVQ].
Das hierarchische Clustering ist ein beliebtes Verfahren aus der Klasse des graphbasierten Clustering, mit agglomerativen oder divisiven Varianten. Zur Bestimmung der Gruppierungen können verschiedene Kriterien herangezogen werden, z.B. solche, die auf der Matrixtheorie mit Unähnlichkeitsmatrizen basieren. Die in diesem Schema enthaltenen Algorithmen sind:
- Single-Link-Algorithmus;
- Complete-Link-Algorithmus;
- Weighted Pair Group Method Average [WPGMA];
- Unweighted Pair Group Method Average [UPGMA];
- Weighted Pair Group Method Centroid [WPGMC];
- Ward- oder Minimum-Variance-Algorithmus.
Beispiele
Clustering von Gesichtsbildern zur Erkennung von Affinität zwischen Personen mit einem graphbasierten Clustering-Algorithmus.
Querverweise
Informative Querverweise
| Mustererkennung oder maschinelles Lernen, mittels Klassifizierung | G06V 10/764 |
| Mustererkennung oder maschinelles Lernen, mittels Regression | G06V 10/766 |
| Mustererkennung oder maschinelles Lernen, Verarbeitung von Bildmerkmalen in Merkmalsräumen | G06V 10/77 |
| Mustererkennung oder maschinelles Lernen, Fusion | G06V 10/80 |
| Wiederauffinden von Informationen bei Einzelbildern; Clusteranalyse; Klassifizierung | G06F 16/55 |
| Wiederauffinden von Informationen bei Videodaten; Clusteranalyse; Klassifizierung | G06F 16/75 |
| Bildanalyse; Segmentierung; Kantenerkennung | G06T 7/10 |
Glossar
| AFC | Adaptive Fuzzy Clustering. |
| alternierende Clusterschätzung [Alternating Cluster Estimation, ACE] alternierende Clusterschätzung ACE | Wenn eine Partitionierung mit einer bestimmten Form erhalten werden soll, kann der Benutzer Zugehörigkeitsfunktionen U(V, X) und Prototypfunktionen V(U, X) definieren. Das Clustering wird wie folgt geschätzt: |
| AO | Alternative Optimisation. |
| CCM | Compatible Cluster Merging. |
| Clustering durch Graphpartitionierung | ein gewichteter Graph wird in disjunkte Teilgraphen partitioniert, indem eine Reihe von Kanten entfernt wird (Schnitt). Die grundlegende Zielfunktion besteht darin, die Größe des Schnittes zu minimieren, die als Summe der Gewichte aller zum Schnitt gehörenden Kanten berechnet wird. |
| Compatible Cluster Merging [CCM] Compatible Cluster Merging | beginnt mit einer ausreichend großen Anzahl von Clustern und reduziert die Anzahl sukzessive, indem ähnliche (kompatible) Cluster in Bezug auf einige Kriterien wie: wobei: die Menge der Eigenvektoren des i-ten Clusters. |
| DBSCAN | Density-Based Spatial Clustering of Applications with Noise, ein nicht-parametrischer Clustering-Algorithmus, bei dem die Anzahl der Cluster nicht im Voraus festgelegt werden muss. |
| FACE | Fast-ACE. |
| FCQS FCQS [Fuzzy C-Quadric Shells] Fuzzy C-Quadric Shells | FCQS kann zur Wiederherstellung von Clustern eingesetzt werden, die die Form einer Quadrik haben. Für die Schätzung der Cluster wird die folgende Kostenfunktion minimiert: |
| FCSS | Fuzzy C-Spherical Shells. |
| FCV | Fuzzy C-Varieties. |
| FHV | Fuzzy Hyper Volume. |
| Fuzzy c-Means Clustering | ● Wähle eine Anzahl von Clustern. ● Weise jedem Punkt zufällig Koeffizienten für die Zugehörigkeit zu den Clustern zu gemäß der folgenden Formel. ● Wiederhole bis der Algorithmus konvergiert:
|
| Gustafson-Kessel [GK] | der GK-Algorithmus assoziiert jedes Cluster mit dem Clusterzentrum und seiner Kovarianz. Das Hauptmerkmal des GK-Clusters ist die lokale Anpassung der Distanzmatrix, um ellipsenförmige Cluster zu identifizieren. Die Zielfunktion von GK lautet: wobei: |
| HCM | Hard c-Means. |
| K-Means Clustering | |
| KNN | k-nächste-Nachbarn, ein Klassifizierungsalgorithmus, der für eine gegebene Datenprobe die k ähnlichsten Proben aus einem Trainingssatz auswählt, ihre jeweiligen Klassenlabels abruft und der Datenprobe durch Mehrheitsentscheidung ein Klassenlabel zuweist; Variante: 1NN, d.h. KNN für k=1. |
| LVQ | lernende Vektorquantisierung [Learning Vector Quantisation]. |
| Partitioning Around Medoids [PAM] – die gebräuchlichste Realisierung von k-Medoid-Algorithmen Partitioning Around Medoids PAM | 1. Initialisierung: Wähle zufällig k der n Datenpunkte als Medoide aus. 2. Ordne jeden Datenpunkt dem nächstgelegenen Medoid zu ("nächstgelegen" hier gewöhnlich im Sinne der euklidischen/Manhattan-Distanz). 3. Für jeden Medoid m. - Für jeden Nicht-Medoid-Datenpunkt x.
4. Wähle die Konfiguration mit den niedrigsten Kosten. 5. Wiederhole Schritte 2 bis 4, bis sich das Medoid nicht mehr verändert. |
G06V 10/762
Definition Statement
This place covers:Techniques of grouping patterns together in order to reveal a certain structure or a meaning in images or video.
Notes – technical background
These notes provide more information about the technical subject matter that is classified in this place:
The object of techniques classified here is to identify groups of similar entities and to assign entities to a group (cluster) according to a measure of their similarity. Separability is determined by measuring the similarity or dissimilarity. Such techniques are usually performed in a high-dimensional feature space constructed by extracting features from the image or video, but can also be performed in the original domain, e.g. in the image domain in the case of image segmentation.
Regarding the grouping of patterns, any pattern may belong exclusively to a single cluster (hard clustering) or it may belong simultaneously to more than one cluster up to a certain degree (fuzzy clustering) according to a similarity (or proximity) measure. In addition, depending on the clustering method used, proximity may be defined (a) between vectors, (b) between a vector and a set of vectors (or a cluster), and (c) between sets of vectors (or different clusters).
Examples of proximity measures are: dissimilarity measures (based on l1, l2, and l∞ norms), similarity measures (inner product, cosine, Pearson’s correlation coefficient, Tanimoto distance, etc.).
Clustering algorithms include:
a) clustering based on statistical measures (which mainly employ numerical data) which adopt a cost function J related to possible groupings which is subject to a global or local optimisation criterion, and return a clustering that optimises J. Examples of such algorithms are:
- Hard clustering algorithms, where a vector belongs exclusively to a specific cluster, e.g. k-means, k-medoids, Linde-Buzo-Gray, ISODATA, DBSCAN, Neural Gas;
- Fuzzy clustering algorithms, where a vector belongs to a specific cluster up to a certain degree, e.g. fuzzy c-means, adaptive fuzzy C-shells (AFCS), fuzzy C quadric shells (FCQS), modified fuzzy C quadric shells (MFCQS);
- Probabilistic clustering algorithms, which follow Bayesian classification arguments and in which each vector is assigned to the cluster according to a probabilistic set-up, e.g. expectation maximisation (EM), Gaussian mixture model (GMM), mean-shift;
b) Graph-based clustering algorithms, e.g. minimum spanning tree (MST) clustering, clustering based on directed trees, spectral clustering, graph-cut optimisation;
c) Competitive learning algorithms for clustering, in which a set of representatives is selected and the goal is to move all representatives to regions of a vector space that are “dense” in terms of other vectors. Examples are leaky learning algorithms, self-organising maps (SOM), learning vector quantisation (LVQ).
Hierarchical clustering is a popular technique in the class of graph-based clustering, with its agglomerative or divisive variants. Various criteria can be used for determining the groupings, such as those based on matrix theory involving dissimilarity matrices. Algorithms included in this scheme are:
- Single link algorithm;
- Complete link algorithm;
- Weighted pair group method average (WPGMA);
- Unweighted pair group method average (UPGMA);
- Weighted pair group method centroid (WPGMC);
- Ward or minimum variance algorithm.
Examples
Clustering face images to detect affinity between persons using a graph-based clustering algorithm
References
Informative references
| Pattern recognition or machine learning, using classification | G06V 10/764 |
| Pattern recognition or machine learning, using regression | G06V 10/766 |
| Pattern recognition or machine learning, processing image features in feature spaces | G06V 10/77 |
| Pattern recognition or machine learning, fusion | G06V 10/80 |
| Information retrieval of still images; Clustering; Classification | G06F 16/55 |
| Information retrieval of video data; Clustering; Classification | G06F 16/75 |
| Image analysis; Segmentation; Edge detection | G06T 7/10 |