• Startseite
• Recherche
• Veröffentlichen
• Hilfe

Eingang zum Volltext

Lizenz

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:bsz:25-opus-33942
URL: http://www.freidok.uni-freiburg.de/volltexte/3394/

Ronneberger, Olaf

3D invariants for automated pollen recognition

3D-Invarianten zur automatischen Pollenerkennung

Kurzfassung in Englisch

In biomedical research we can see a clear tendency towards the study of cells and whole organisms in their natural 3D environment, away from the studies of isolated flat cells, that were grown in a synthetic 2D environment and were analyzed with 2D techniques. Another trend in biomedical research is the ever increasing need for high-throughput experiments, e. g., to retrieve statistically relevant information. The equipment for the automatic recording of great amounts of 3D volumetric data is available in many research laboratories today, but the recorded 3D data are still manually evaluated which has become the main bottleneck in many applications.

In this thesis the development of 3D invariants for the recognition of biological structures is described. These invariants are based on the Haar-integration-framework of Schulz-Mirbach (1995b). The invariance properties are reached by an integration over the desired transformation groups, e. g. rotation and translation. Several important aspects of the application of the Haar-integration framework to 3D volumetric data sets of biological structures are described. The most important extension is the introduction of deformation models such that the resulting features are robust to elastic deformations of the structures. Another important aspect is the reached robustness to even non-linear gray-scale transformations, that allow certain variations of the recording parameters between the training and the test objects. The direct computation of these invariants is computationally very expensive. Several new techniques are introduced that allow a fast computation of the invariants by means of the FFT, by the expansion of the integral into spherical harmonics series or by simultaneous computation of multiple invariants based on invertible vectorial kernel functions. Furthermore voxel-wise invariants are introduced for a simultaneous segmentation and recognition of 3D structures. Vectorial invariants are developed for a fast and reliable detection of spherical objects in cluttered environments. A very challenging application that demands many of the requirements to be fulfilled which are given in the biomedical research is the recognition of pollen grains. The high number of different pollen grains from different plants contain very different kinds of structures that have to be identified. For a part of these structures clear one-to-one correspondences can be identified, while for the other part of these structures only the statistical properties match.

In the given application we use microscopically recorded images to recognize a real-world object. For the correct interpretation of the gray values it is important to understand the different effects within a microscope. The main four steps, illumination, interaction of the object with the light, transformation of the emitted light, and the recording of the light are explained.

In pollen recognition (as in many other applications) we should differentiate between those results that can be reached within a clean and well-controlled laboratory environment and those results of a real-world routine application. In this thesis two representative data sets for these scenarios are used: The first one (denoted as "confocal data set" here) is a typical laboratory data set: The pollen were collected directly from the corresponding plants. They were carefully prepared on one slide per taxon and were manually recorded as a full 3D volumetric data set with confocal laser scanning microscopy. Due to the high costs of such a system and the time-consuming operation, only a small data set containing 389 pollen grains of 26 different taxa (15 grains per taxon) was recorded. The preparation and recording applied here guarantees a 100% correct labeling of the pollen grains and contains the lowest possible degree of distortion due to optical effects. On the other hand the used samples do not represent all variations within each taxon, such as different genera, species or subspecies, different growth conditions of the plants, etc. Furthermore this data set does not contain deformed, contaminated or agglomerated pollen grains or pollen grains at different levels of degradation and it does not contain the vast amount of other particles that are found in real air samples.

The second data set (denoted as "pollenmonitor data set") is a typical real-world data set. It was automatically collected, prepared and recorded by the first prototype of the pollenmonitor during the pollen season 2006 in Freiburg and Zürich. It contains about 22,750 pollen grains from 33 taxa together with about 170,000 other spherical airborne particles.

The detection of the pollen grains in the recorded volumetric data sets is done by vectorial voxel-wise invariants (named "MiSP detector" for Microscopical Spherical Particles). The precise segmentation of the detected pollen grains is performed by standard algorithms that were adapted to the given requirements. For the confocal data set a graph-cut-based segmentation was used. For the pollenmonitor data set a combination of a modified canny-edge detector, a model-based weighting of the found edges and a snake approach was applied. The feature extraction is done by the upper described invariants (named "MiSP invariants") which exhibit a high robustness to elastic deformations and nonlinear grayvalue transformations. At the same time these invariants are sensitive to subtle structural changes that cannot be modeled by deformations. The classification of the objects is performed with support vector machines that were optimized to deal with the very high dimensionality of the extracted feature vectors (e.g., 87,296 for the pollenmonitor data set).

The recognition rate on the confocal data set (389 pollen grains of 26 taxa) is very high. In a leaveone- out validation with a simple 1 Nearest Neighbor classifier only 3 of the 389 pollen grains were misclassified (99.2% recognition rate). With a support vector machine only 2 incorrectly classified pollen grains were obtained (99.5% recognition rate). In the second case the misclassified pollen were confused with another genus from the same family. The best recognition rates obtained by other approaches on typical "laboratory" data sets are 89% on a data set containing 3,800 pollen grains from 19 taxa, or 70% on a data set containing 16,220 pollen grains from 80 taxa.

For the rating of the results on the pollenmonitor data set another statistical measure that the recognition rate is useful. In pollen samples from the ambient air we are confronted with a very high number of particles other than pollen that have to be correctly rejected by the recognition system. Here the precision (fraction of correctly classified pollen within the objects, that were classified as pollen) is the most important statistical measure. The validation was done by splitting the pollenmonitor data set (22,750 pollen grains from 33 taxa + about 170,000 dust particles) into a training set and a test set. The training set contains only samples from Freiburg, while the test set contains samples from Freiburg and Zürich. The obtained precision for all 33 pollen taxa is 96.7% at a recall of 84.3%. The results for the five highly allergenic pollen taxa in this data set (that are monitored for the pollen forecasts) are 98.5% precision at a recall of 86.5%. The best results obtained by other approaches on a real-world data set (3104 pollen grains from 8 taxa + about 30,000 dust particles) is a precision of 30% at a recall of 64.9%.

The results obtained with the proposed MiSP invariants are significantly better than the state of the art in pollen recognition. Furthermore these techniques have proven to work not only on a small laboratory-type data set but also on a very large real-world data set. Especially the reached robustness to elastic deformations and the full 3D approach seems to be a key requirement for a reliable recognition of biological structures. We think that the new findings will be a valuable foundation for many further developments in the field of the recognition of biological structures in 3D volumetric data sets.

Kurzfassung in Deutsch

In der bio-medizinischen Forschung ist eine klare Tendenz erkennbar, die weg von der klassischen 2D Analyse einzelner flacher Zellen in einer synthetischen zweidimensionalen Umgebung hin zur Untersuchung von Zellen und ganzen Organismen in ihrer natürlichen dreidimensionalen Umgebung geht. Außerdem wächst der Bedarf an Experimenten, die an einer großen Zahl gleicher Systeme durchgeführt werden, um z.B. Daten für statistische Aussagen zu gewinnen. Die apparative Ausstattung zur Aufnahme großer Mengen dreidimendionaler Volumendaten ist heutzutage in vielen Forschungslaboratorien verfügbar, aber die Auswertung dieser Daten erfolgt immer noch manuell. Diese zeitaufwändige Auswertung ist inzwischen der Haupt-Engpass in vielen derartigen Anwendungen.

In der vorliegenden Dissertation wird die Entwicklung von 3D Invarianten zur Erkennung von biologischen Strukturen beschrieben. Diese Invarianten wurden mit Hilfe eines Schemas entwickelt, das von Schulz-Mirbach (1995b) angegeben wurde und auf der Haar-Integration beruht. Die benötigten Invarianzeigenschaften werden dabei durch die Integration über die entsprechende Transformationsgruppe wie z.B. Rotation und Translation erreicht. Verschiedene Erweiterungen des Haar-Integrations-Schemas werden beschrieben, die für die Anwendung auf 3D Volumendaten biologischer Strukturen benötigt werden. Die wichtigste Erweiterung ist dabei die Einführung eines Deformationsmodells, so dass die resultierenden Merkmale robust gegenüber elastischen Deformationen der betrachteten Strukturen werden. Ein weiterer wichtiger Aspekt ist die erreichte Robustheit gegenüber nicht-linearen Grauwert-Transformationen, die gewisse Veränderungen der Aufnahmebedingungen zwischen den Aufnahmen der Trainings- und der Test-Objekte erlaubt.

Die direkte Berechnung dieser Invarianten ist extrem rechenaufwändig. Mehrere neue Verfahren zur schnellen Berechnung der Invarianten durch den Einsatz der FFT, durch die Entwicklung des Integrals in eine Reihe von Kugelfunktionen, oder durch die simultane Berechnung von mehreren Invarianten, basierend auf invertierbaren vektoriellen Kernfunktionen, werden vorgestellt. Außerdem werden voxelweise berechnete Invarianten eingeführt, mit deren Hilfe die Segmentierung und Erkennung von 3D Strukturen in einem Schritt durchgeführt werden kann. Für eine schnelle und zuverlässige Detektion von kugelförmigen Objekten in sehr heterogenen Umgebungen werden vektorielle Invarianten entwickelt.

Eine sehr anspruchsvolle Anwendung, bei der viele der Anforderungen erfüllt werden müssen, die unter anderem in der bio-medizinischen Forschung auftreten, ist die Erkennung von Pollen. Die große Anzahl von verschiedenen Pollen der verschiedenen Pflanzen enthalten sehr unterschiedliche Typen von Strukturen, die identifiziert werden müssen. Für einen Teil dieser Strukturen können klare eins-zu-eins Korrespondenzen gefunden werden, während für einen anderen Teil der Strukturen nur die statistischen Eigenschaften übereinstimmen.

In der vorliegenden Anwendung soll ein reales Objekt anhand von mikroskopisch aufgenommenen Bildern erkannt werden. Für die korrekte Interpretation der Grauwerte ist es wichtig, die verschiedenen Effekte innerhalb des Mikroskops zu verstehen. Daher werden die vier wichtigsten Schritte, die Beleuchtung, die Wechselwirkung des Lichtes mit dem Objekt, die Transformation des emittierten Lichtes und die Aufnahme des Lichtes umfassend erläutert.

In der Pollen-Erkennung (so wie in vielen anderen Anwendungen) sollte man zwischen solchen Ergebnissen unterscheiden, die in einer sauberen, gut kontrollierbaren Labor-Umgebung erreicht werden können, und solchen Ergebnissen, die in einer realen Routineanwendung erreicht werden. In dieser Dissertation werden zwei repräsentative Datensätze für diese beiden Szenarien verwendet. Der erste (hier als "Konfokal-Datensatz" bezeichnet) ist ein typischer Labor-Datensatz: Die Pollen wurden direkt von den entsprechenden Pflanzen gesammelt und sorgfältig auf einem Objektträger pro Taxon präpariert. Von jedem Pollenkorn wurde manuell ein 3D Volumendatensatz mit einem konfokalen Laser-Scannnig-Mikroskop aufgenommen. Aufgrund der hohen laufenden Kosten eines solchen Systems und der zeitaufwändigen Aufnahme wurde nur ein relativ kleiner Datensatz mit 389 Pollen von 26 verschiedenen Taxa (15 Pollen pro Taxon) erzeugt. Dieses Vorgehen garantiert ohne Ausnahme die korrekte Zuordnung der Pollen zu der entsprechenden Pflanzenart und die geringst mögliche Verfälschung der Aufnahmen durch optische Effekte. Andererseits werden in diesem Datensatz nicht alle möglichen Variationen innerhalb eines Taxons abgedeckt. Dies betrifft vor allem Variationen aufgrund von verschiedenen Genera, Arten oder Unterarten innerhalb des Taxons, oder aufgrund von verschiedenen Wachstumsbedingungen der Pflanzen. Desweiteren enthält dieser Datensatz keine deformierten, kontaminierten oder agglomerierten Pollen, sowie keine Pollen in verschiedenen Zersetzungs-Zuständen und vor allem nicht die enorm hohe Zahl anderer Partikel, die in echten Luftstaubproben auftreten. Der zweite Datensatz (hier als "Pollenmonitor Datensatz" bezeichnet) ist ein typischer "Real-World"-Datensatz. Die Proben wurden in der Pollensaison 2006 vollautomatisch mit dem ersten Prototypen des Pollenmonitors gesammelt, präpariert und aufgenommen an den Standorten Freiburg und Zürich. Dieser Datensatz enthält insgesamt ca. 22.750 Pollen von 33 Taxa und etwa 170.000 andere rundliche luftgetragene Partikel.

Die Detektion der Pollen in den aufgenommenen volumetrischen Datensätzen erfolgt mit vektoriellen voxel-weisen Invarianten (hier als "MiSP detector" für "Microscopical Spherical Particles" bezeichnet). Für die nachfolgende Segmentierung der detektierten Partikel werden angepasste Standardverfahren eingesetzt: Eine graph-cut basierte Segmentierung für den Konfokal-Datensatz und eine Kombination aus einem modifizierten Canny-Edge-Detector, einer modellbasierten Gewichtung der gefundenen Kanten und einem Snake-Ansatz für den Pollenmonitor-Datensatz. Für die Merkmals-Extraktion werden die oben beschriebenen Invarianten eingesetzt (hier als "MiSP invariants" bezeichnet), die eine hohe Robustheit gegenüber elastischen Deformationen und nichtlinearen Grauwerttransformationen aufweisen. Trotzdem sind diese Invarianten noch sensitiv für subtile strukturelle Änderungen, die nicht durch eine elastische Deformation modelliert werden können. Für die Klassifikation der Objekte werden Support-Vektor-Maschinen eingesetzt, die für die Verarbeitung von sehr hoch-dimensionalen Merkmalsvektoren optimiert wurden (z.B. 87.296 Dimensionen beim Pollenmonitor Datensatz).

Die erreichte Erkennungsrate auf dem Konfokal-Datensatz (389 Pollen aus 26 Taxa) ist sehr hoch. In einer "leave-one-out validation" mit einem einfachen 1-nächster-Nachbar Klassifikator wurden nur drei Pollenkörner falsch klassifiziert (99.2% Erkennungsrate). Beim Einsatz einer Support-Vektor-Maschine sinkt diese Zahl auf 2 falsch klassifizierte Pollenkörner (99.5% recognition rate), wobei diese zwar einem anderen Genus zugewiesen wurden, der aber zur selben Familie gehört. Die besten Erkennungsraten mit anderen Ansätzen auf typischen Labor-Datensätzen liegen bei 89% bei einem Datensatz mit 3.800 Pollen aus 19 Taxa oder 70% bei einem Datensatz mit 16.220 Pollen aus 80 Taxa. Für die Bewertung der Ergebnisse auf dem Pollenmonitor-Datensatz ist ein anderes statisches Maß als die einfache Erkennungsrate sinnvoll. Pollenproben aus der Umgebungsluft enthalten eine sehr hohe Anzahl von anderen luftgetragenen Partikeln die von dem Erkennungssystem korrekt zurückgewiesen werden müssen. In diesem Fall ist die Präzision (Anteil der korrekt klassifizierten Pollen innerhalb aller Objekte, die als Pollen klassifiziert wurden) das wichtigste statistische Maß. Die Validierung des Systems auf dem Pollenmonitor-Datensatz (22.750 Pollen aus 33 Taxa + etwa 170.000 Staubpartikel) wurde durch eine Aufteilung in einen Trainings-Datensatz und einen Test-Datensatz durchgeführt. Der Trainings-Datensatz enthält nur Proben aus Freiburg, während der Test-Datensatz Proben aus Freiburg und aus Zürich enthält. Die erreichte Präzision bei der Betrachtung aller 33 Taxa ist 96.7% bei einer Erkennungsrate von 84.3%. Die Ergebnisse für die 5 hoch-allergenen Pollenarten (die für die Pollenflugvorhersagen relevant sind) liegen noch leicht darüber. Dort konnte eine Präzision von 98.5% bei einer Erkennungsrate von 86.5% erreicht werden. Die besten Ergebnisse, die mit anderen Ansätzen auf einem "Real-World"-Datensatz (3104 Pollen aus 8 taxa + etwa 30.000 Staubpartikel) erreicht wurden, liegen bei 30% Präzision bei einer Erkennungsrate von 64.9%.

Die erzielten Ergebnisse mit den vorgeschlagenen "MiSP invariants" sind signifikant besser als der Stand der Technik. Darüber hinaus konnte demonstriert werden, dass diese Techniken nicht nur auf kleinen Labor-Datensätzen sondern auch auf sehr großen "Real-World"-Datensätzen sehr gute Ergebnisse liefern. Insbesondere die erreichte Robustheit gegenüber elastischen Deformationen und der 3D Ansatz scheinen eine wesentliche Voraussetzung für die verlässliche Erkennung von biologischen Strukturen darzustellen. Wir glauben, dass die neuen Erkenntnisse eine wertvolle Grundlage für viele weitere Entwicklungen im Bereich der Erkennung von biologischen Strukturen in 3D Volumendaten sind.