Kernel Methods in Computer Vision: Object Localization, Clustering, and Taxonomy Discovery
Blaschko, Matthew Brian
In dieser Arbeit studieren wir drei fundamentale Computer Vision Probleme mit Hilfe von Kernmethoden. Zun ächst untersuchen wir das Problem, Objekte in natürlichen Bildern zu lokalisieren, welches wir als die Aufgabe formalisieren, die Bounding Box eines zu detektierendes Objekt vorherzusagen. In Kapitel II entwickeln wir hierfür ein Branch-and-Bound Framework, das es erlaubt uns, effizient und optimal diejenige Bounding Box zu finden, welche eine gegebene Qualit ätsfunktion maximiert. Dabei kann es sich sowohl um die Entscheidungsfunktion eines kernbasierten Klassifikators, als auch um ein Nearest-Neighbor Abstandsmaß handeln kann. Wir zeigen, dass dieses Verfahren bereits hervorragende Lokalisierungergebnisse erzielt, wenn es mit einer einfachen lineare Qualit ätsfunktion verwendet wird, die durch Trainieren einer Support-Vektor-Maschine gefunden wurde. In Kapitel III untersuchen wir, wie sich kernbasierte Qualit ätsfunktionen lernen lassen, die optimal für die Aufgabe der Objektlokalisierung geeignet sind. Insbesondere zeigen wir, dass Structured Output Regression dies ermöglicht: im Gegensatz zu Support-Vektor-Machinen kann Structured Output Regression nicht nur bin äre Entscheidungen treffen, sondern beliebige Elemente eines Ausgaberaumes vorhersagen. Im Fall der Objektlokalisierung besteht der Ausgaberaum dabei aus allen möglichen Bounding Boxes innerhalb des Zielbildes. Structured Output Regression lernt eine Funktion, die die Kompatibilit ät zwischen Eingaben und Ausgaben messen kann, und pr ädiziert anschließend dasjenige Element des Ausgaberaumes, welches die maximale Kompatibilit ät zur Eingabe aufweist. Für diese Maximierung l äßt sich exakt die Branch-and-Bound Optimierung aus Kapitel II verwenden, die zudem in einer Variante auch schon w ährend des Training als Teil eines Constraint Generation Prozesses einsetzbar ist. Im Anschluß wenden wir uns in Kapitel IV dem Problem des Clusterns von Bildern zu. Zun ächst führen wir eine Evaluation verschiedener Clustering-Algorithmen durch, wobei die Qualit ät der Clusterungen dadurch gemessen wird, wie gut diese einer bekannten, semantisch korrekten Partitionierung der Daten entsprechen. Die Studie zeigt hervorragende Ergebnisse insbesondere von Spectral Clustering Methoden, welche die Eigenvektoren einer passend normalisierten Kernmatrix zur Clusterung der Daten verwenden. Motiviert durch diesen Erfolg, entwickeln wir im folgenden eine Verallgemeinerung von Spectral Clustering für Eingabedaten, welche in mehreren Modalit äten gleichzeitig vorliegen, zum Beispiel Bilder mit zugehörgen Bildunterschriften. Analog zur Interpretation von Spectral Clustering als Kernel-PCA Projektion mit anschließendem Nachclusterungsschritt, verwenden wir regularisierte Kernel-CCA als Verallgemeinerung und clustern die Daten in der sich ergebenden projezierten Form nach. Der resultierende Algorithmus Correlational Spectral Clustering findet signifikant bessere Partitionen als gewöhnliches Spectral Clustering, und erlaubt dabei auch die Projektion von Daten, von denen nur eine Datenmodalit ät bekannt ist, z.B. Bilder ohne Unterschrift. In Kapitel V besch äftigen wir uns schließlich mit dem Problem, Taxonomien in Daten zu finden. Für eine gegebene Datenmenge möchten wir zugleich eine Partitionierung der Daten finden und eine Taxonomie ableiten, welche die sich ergebenden Cluster miteinander in Beziehung setzt. Der hierfür entwickelte Algorithmus Numerical Taxonomy Clustering basiert auf der Maximierung eines kernbasierten Abh ängigkeitsmaßes zwischen den Daten und einer abstrahierten Kernmatrix. Letztere berechnet sich aus einer Partitionierungsmatrix und einer positiv definiten Abstandsmatrix, welche die Beziehung zwischen den Datenclustern characterisiert. Indem wir für die Abstandsmatrix nur Matrizen zulassen, die durch additive Metriken induziert werden, können wir das Ergebnis ebenfalls als eine Taxonomie interpretieren. Um das entstehende Optimierungsproblem mit Nebenbedingungen zu lösen, greifen wir auf etablierte Verfahren aus dem Feld der Numerischen Taxonomie zurück, und wir können zeigen, dass Numerical Taxonomy Clustering nicht nur besser interpretierbare Ergebnisse liefert, sondern auch, dass sich die Qualit ät der entstehenden Clusterungen verbessert, falls die Daten tats ächlich eine Taxonomiestruktur besitzen.
In this thesis we address three fundamental problems in computer vision using kernel methods. We first address the problem of object localization, which we frame as the problem of predicting a bounding box around an object of interest. We develop a framework in Chapter II for applying a branch and bound optimization strategy to efficiently and optimally detect a bounding box that maximizes objective functions including kernelized functions and proximity to a prototype. We demonstrate that this optimization can achieve state of the art results when applied to a simple linear objective function trained by a support vector machine. In Chapter III, we then examine how to train a kernelized objective function that is optimized for the task of object localization. In particular, this is achieved by the use of structured output regression. In contrast to a support vector machine, structured output regression does not simply predict binary outputs but rather predicts an element in some output space. In the case of object localization the output space is the space of all possible bounding boxes within an image. Structured output regression learns a function that measures the compatibility of inputs and outputs, and the best output is predicted by maximizing the compatibility over the space of outputs. This maximization turns out to be exactly the same branch and bound optimization as developed in Chapter II. Furthermore, a variant of this branch and bound optimization is also utilized during training as part of a constraint generation step. We then turn our focus to the problem of clustering images in Chapter IV. We first report results from a large scale evaluation of clustering algorithms, for which we measure how well the partition predicted by the clustering algorithm matches a known semantically correct partition of the data. In this study, we see particularly strong results from spectral clustering algorithms, which use the eigenvectors of an appropriately normalized kernel matrix to cluster the data. Motivated by this success, we develop a generalization of spectral clustering to data that appear in more than one modality, the primary example being images with associated text. As spectral clustering algorithms can be interpreted as the application of kernel principal components analysis followed by a reclustering step, we use the generalization of regularized kernel canonical correlation analysis followed by a reclustering step. The resulting algorithm, correlational spectral clustering, partitions the data significantly better than spectral clustering, and allows for the projection of unseen data that is only present in one modality (e.g. an image with no text caption). Finally, in Chapter V, we address the problem of discovering taxonomies in data. Given a sample of data, we wish to partition the data into clusters, and to find a taxonomy that relates the clusters. Our algorithm, numerical taxonomy clustering, works by maximizing a kernelized dependence measure between the data and an abstracted kernel matrix that is constructed from a partition matrix that defines the clusters and a positive definite matrix that represents the relationship between clusters. By appropriately constraining the latter matrix to be generated by an additive metric, we are able to interpret the result as a taxonomy. We make use of the well studied field of numerical taxonomy to efficiently optimize this constrained problem, and show that we not only achieve an interpretable result, but that the quality of clustering is improved for datasets that have a taxonomic structure.
