Diskrete Tomographie

Mathematische Verfahren zur Lösung von Problemstellungen in Industrie und Wirtschaft. Ein wissenschaftliches Programm gefördert durch das Bundesministerium für Bildung, Wissenschaft, Forschung und Technologie.

Was ist Diskrete Tomographie?

Die hochauflösende Transmissionselektronenmikroskopie (High-Resolution-Transmission-Electron-Microscopy) ermöglicht es, moderne Materialien sowie elektronische Bauelemente mit hoher räumlicher Auflösung zu charakterisieren. Bei dieser Abbildungsart handelt es sich um eine gewichtete Projektion des dreidimensionalen Objektes auf eine zweidimensionale Bildebene. Routinemäßig erreicht die HRTEM eine räumliche Auflösung, bei der in kristallinen Materialien einzelne Atomsäulen unterschieden werden können. Mit Methoden der quantitativen hochauflösenden Gitterabbildung (QUANTITEM) läßt sich dabei die Atomkonzentration einzelner Atomsäulen bestimmen, [8], [7]. Allerdings fehlt bei der hochauflösenden Gitterabbildung die Information über die Position (Höhe) der Atome auf diesen Atomsäulen. Diese Ambiguität kann reduziert werden, wenn die Probe relativ zum Elektronenstrahl gekippt wird.

Bei vielen Problemstellungen, etwa bei der Untersuchung innerer Grenzflächen, ist es erforderlich, aus den gewonnenen Projektionen die volle dreidimensionale Struktur zu rekonstruieren. So interessiert man sich etwa für die Grenzflächenstruktur Silizium/Siliziumdioxyd, um im Rahmen einer Qualitätskontrolle Rückschlüsse auf die Qualität von Halbleiterbausteinen ziehen zu können, die zur Weiterverarbeitung in Computerchips eine genügend glatte Oberfläche aufweisen müssen. Bei metallischen Legierungen sind ferner die Form und Zusammensetzung kleiner kristalliner Ausscheidungen bzw. Atomcluster relevant, um gezielt bestimmte Materialeigenschaften einstellen zu können.

Motiviert durch die Fortschritte im physikalisch-technischen Bereich beschäftigt sich das mathematische Gebiet der diskreten Tomographie mit der Analyse des zugehörigen diskreten Rekonstruktionsproblems und der Entwicklung effizienter Verfahren.

Im "makroskopischen Bereich" ist die Mathematik des Problems der Inversion von Radon- bzw. X-Ray-Transformierten gut verstanden; sie hatte wesentlichen Anteil an der Entwicklung der Computertomographie, die in der Medizin erfolgreich zur Visualisierung menschlicher Organe oder in der Technik bei zerstörungsfreien Prüfverfahren eingesetzt wird. Dabei werden Objekte untersucht, die aus sehr vielen Atomen bestehen, so daß ein einzelner X-Ray-Strahl eine Zahl von Atomen der Grössenordung 10^23 "sieht"; eine diskrete Modellierung ist hier natürlich nicht praktikabel. Den bahnbrechenden Erfolgen der Computertomographie makroskopischer Objekte liegt daher eine kontinuierliche Modellierung zugrunde. Bei einer Auflösung auf atomarer Skala verliert das Problem hingegen seinen kontinuerlichen Charakter und muß diskret modelliert werden. Da die Anzahl von Atomen auf Geraden bestimmt werden kann, werden die Atome als Punkte aufgefaßt, so daß mathematisch (idealisiert) die Aufgabe darin besteht, eine Menge von Punkten im dreidimensionalen Raum zu rekonstruieren, die durch zweidimensionale "diskrete Röntgenbilder" gegeben sind.

Von physikalischer Seite besteht die Forderung, mit möglichst wenigen X-Rays auszukommen, da aufgrund der Elektronenbestrahlung die zu untersuchende Probe bereits nach wenigen Aufnahmen beschädigt wird. Ferner ist zu berücksichtigen, daß bei der HRTEM, bedingt durch das begrenzte Auflösungsvermögen, einzelne Atomsäulen nur für bestimmte Projektionsrichtungen unterschieden werden können, die überdies aufgrund der technischen Anforderungen an die Kippsteuerung in einer Ebene liegen.

Da im allgemeinen eine endliche Zahl von Gitter-X-Rays zur eindeutigen Rekonstruktion von atomaren Strukturen nicht ausreicht, sind für den Nachweis von Eindeutigkeitsaussagen bei nur endlich vielen X-Rays Einschränkung an die zu rekonstruierenden Mengen nötig. In [3] wird mit Hilfe von Methoden der Geometrie und der algebraischen Zahlentheorie ein Problem von L. Shepp gelöst und gezeigt, daß konvexe Gittermengen durch nur vier geeignete diskrete Gitter-X-Rays eindeutig bestimmt sind. Hierdurch ergibt sich insbesondere auch eine Stabilitätsaussage für ein Resultat von Gardner & McMullen [6] aus dem Bereich der kontinuierlichen "geometrischen Tomographie". Ferner wird gezeigt, daß für beliebige ebene Mengen von sieben Gitterrichtungen die entsprechenden X-Rays stets zur Determination endlicher Gittermengen ausreichen. Außerdem werden interaktive Techniken der sukzessiven Determination untersucht und auch hierfür bestmögliche Ergebnisse erzielt (vgl. auch [2]). Natürlich ist die Eigenschaft der Konvexität für viele der relevanten Anwendungen zu restriktiv. Abschwächungen auf "Richtungskonvexität" scheinen dagegen einerseits physikalisch haltbar zu sein, andererseits aber auch mathematisch handhabbare Einschränkungen der Mehrdeutigkeiten zu erlauben. Entsprechende Untersuchungen werden in diesem Forschungsprojekt durchgeführt werden.

Auf der algorithmischen Seite konnte die Komplexität der relevanten Aufgaben vollständig bestimmt werden. Das Rekonstruktionsproblem im Falle von zwei X-Rays läßt sich unter anderem auf ein Max-flow Problem zurückführen und ist daher effizient lösbar. Im Falle von mehr als zwei X-Rays wird das Problem bereits streng NP-vollständig, [4]. Analoge Aussagen ergeben sich auch für den polyatomaren Fall, in dem kristalline Strukturen zu rekonstruieren sind, die aus mehreren Atomsorten bestehen (hier ist das Problem sogar schon für zwei X-Rays NP-vollständig, wenn mindestens drei verschiedene Atomsorten auftreten, [5][1]) und für höherdimensionale X-Rays.

In Kooperation mit P. Schwander, einem Physiker am Institut für Halbleiterphysik, Frankfurt/Oder , der maßgeblich an der Entwicklung und Weiterentwicklung von QUANTITEM beteiligt ist ([8], [7]), werden Algorithmen konstruiert - basierend auf Methoden der polyedrischen Kombinatorik einerseits und der algebraischen Testmengentheorie andererseits -, um aus den praktisch vorliegenden physikalischen Datensätzen die vollen dreidimensionalen Strukturen approximativ bestimmen zu können. Hierbei sind mögliche Dateninsuffizienzen zu berücksichtigen, so daß Verfahren benötigt werden, die trotz Datenfehlern und unvollständiger Information (Mehrdeutigkeit) die physikalische Struktur jedenfalls einschränken und mögliche Variabilitätsbreiten angeben.

Literatur

1
M. Chrobak and C. Dürr.
Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms.
Preprint.
2
R.J. Gardner and P. Gritzmann.
Successive determination and verification of polytopes by their X-rays.
J. Lond. Math. Soc., II. Ser., 50(2):375-391, 1994.
3
R.J. Gardner and P. Gritzmann.
Discrete tomography: determination of finite sets by x-rays.
Trans. Am. Math. Soc., 349(6):2271-2295, 1997.
4
R.J. Gardner, P. Gritzmann, and D. Prangenberg.
On the computational complexity of reconstructing lattice sets from their X-rays.
Discrete Mathematics, im Druck.
5
R.J. Gardner, P. Gritzmann, and D. Prangenberg.
On the computational complexity of determining polyatomic structures by X-rays.
Theoretical Computer Science, im Druck.
6
R.J. Gardner and P. McMullen.
On Hammer's X-ray problem.
J. Lond. Math. Soc., 21(2):171-175, 1980.
7
C. Kisielowski, P. Schwander, F.H. Baumann, M. Seibt, Y. Kim, and A. Ourmazd.
An approach to quantitative high-resolution transmission electron microscopy of crystalline materials.
Ultramicroscopy, 58:131-155, 1995.
8
P. Schwander, C. Kisielowski, F.H. Baumann, Y. Kim, and A. Ourmazd.
Mapping projected potential, interfacial roughness, and composition in general crystalline solids by quantitative transmission electron microscopy.
Physical Review Letters, 71(25):4150-4153, 1993.

beteiligte Personen

Projektleitung

Wissenschaftliches Personal

Partner

Förderung

  • Dieses wissenschaftliche Programm wurde durch das Bundesministerium für Bildung, Wissenschaft, Forschung und Technologie (BMBF ) unter der Nr. GR7TM1/02.05 finanziert.
  • BEO Forschungszentrum Jülich 

Projektdurchführung

Projektdauer

  • 1. Oktober 1997 - 30. September 2000

Treffen und Ereignisse

  • 29. - 31. October 1997 - BMBF-Statusseminar 1997 in Heidelberg
  • 9. November 1998 - BMBF Workshop der Gruppe "Diskrete Optimierung, Verkehr und Einsatzplannung" in Berlin
  • 17. - 19. Februar 1999 - BMBF-Statusseminar 1999 in Erlangen

Publikationen

  • Discrete Tomography, P. Gritzmann. AvH-Magazin 66 (1995), 23--32.
  • On the reconstruction of binary images from their discrete Radon transform, R. Gardner, P. Gritzmann und D. Prangenberg. Proc. Intern. Symp. Optical Science, Engineering, and Instrumentation, Denver, SPIE, Vol. 2826, 1996, 121--132.
  • Discrete tomography: Determination of finite sets by X-rays, R. Gardner, P. Gritzmann. Trans. Amer. Math. Soc. 349 (1997), 2271--2295.
  • On the reconstruction of finite lattice sets from their X-rays, P. Gritzmann. Proc. 7th Intern. Workshop, DGCI'97, Montpellier, France (Hrsg. E. Ahronovitz and C. Fiorio), Lecture Notes on Computer Science, Springer 1997, 19--32.
  • Success and failure of certain reconstruction and uniqueness algorithms in discrete tomography, P. Gritzmann, D. Prangenberg, S. de Vries und M. Wiegelmann), Intern. J. Imaging Systems and Technology 9 (1998), 101--109.
  • On the computational complexity of determining polyatomic structures by X-rays, R. Gardner, P. Gritzmann und D. Prangenberg, Theor. Comput. Sci., 211 (1998).
  • On the computational complexity of reconstructing lattice sets from their X-rays, R. Gardner, P. Gritzmann und D. Prangenberg, Discr. Math. 202 (1999), 45-71.
  • Uniqueness and complexity issues in discrete tomography, R. Gardner, P. Gritzmann. In: ``Discrete Tomography: Foundations, Algorithms, Applications'' (Hrsg.: G. Herman und A. Kuba), Birkhauser, Boston, 1999.
  • Computational Complexity Issues in Discrete Tomography, Dieter Prangenberg, Dissertation.
  • Gröbner Bases and Primal Algorithms in Discrete Tomography, Markus Wiegelmann, Dissertation.

Poster

Technisch-physikalische Problemstellung
Physik Materialwissenschaften Technik
Modellierung und Interaktion
Mathematisches Modell Ziele Visualisierung der Ergebnisse
Mathematische Ergebnisse
Komplexität Primale Methoden Polyedrische Methoden

Animation von Packungs-Heuristiken

Problemstellung

  • Auf einem NxN Gitter befindet sich eine unbekannte Atom-Konfiguration (blau). Jedoch ist die Anzahl der Atome entlang der Geraden weniger Richtungen bekannt. Das Ziel ist es, eine Konfiguration zu finden, die die gleiche Anzahl von Atomen entlang jener Geraden besitzt, d.h. gesucht wird ein x in {0,1}^(NxN), das das zugehörige Gleichungssystem Ax=b erfüllt.
  • Für 3 oder mehr Projektionsrichtungen ist das Problem NP-vollständig. Da dennoch schnell Informationen über die Konfiguration gewonnen werden sollen, wird mit verschiedenen Strategien approximativ nach Konfigurationen gesucht, die Ax<=b mit möglichst großem x erfüllen.

GreedyA

  • Strategie: Teste in einer zufälligen Reihenfolge jede Position des Gitters darauf, ob das Plazieren eines Atoms unter den Bedingungen der gegebenen Projektionen möglich ist (d.h. ob durch das Setzen des Atoms keine der Liniensummen größer als die jeweilig gegebene wird). Falls das möglich ist, setze dieses Atom.
  • Resultat: Man erhält eine Lösung, die Ax<=b erfüllt, bei der die Anzahl der gesetzten Atome mindestens 90% der Anzahl der Atome in der ursprünglichen Konfiguration beträgt. Beipiel einer GreedyA-Lösung: VRML2 (VRML2-Browser ) GIF89
  • Kritik: Die Reihenfolge der Betrachtung ist der wesentliche Faktor für die Güte des Ergebnisses, eine zufällige Wahl ist daher nicht empfehlenswert.

GreedyB

  • Strategie: Wie beim GreedyA soll jede Position des Gitters darauf geprüft werden, ob dort noch ein Atom Platz hat, die Reihenfolge der Betrachtung ist nun aber durch Gewichte vorgegeben: Ein Liniengewicht ist die restliche Linienkapazität geteilt durch die Anzahl der noch nicht betrachteten Positionen. Ein Positionsgewicht ist das Produkt der Liniengewichte der durch diese Position laufenden Linien. Die Geraden einer Richtung werden nach Gewichten sortiert und in fallender Reihenfolge betrachtet. Für jede Gerade werden alle darauf liegenden Positionsgewichte berechnet und diese ebenfalls in fallender Reihenfolge auf die übliche Weise überprüft.
  • Resultat: Man erhält wiederum eine gültige '<='-Lösung, bei der die Anzahl der gesetzten Atome mindestens 95% beträgt. Beipiel einer GreedyB-Lösung: VRML2 (VRML2-Browser ) GIF89
  • Kritik: Die Reihenfolge der Betrachtung berücksichtigt, daß manche Positionen wesentlich wichtiger sind als andere, die Informationen dafür werden aber für die Linien nur einmal am Anfang erstellt, für die Punkte nur einmal pro Linie, wobei sich aber die Gewichte nach jeder betrachteten Position verändern.

GreedyC

  • Strategie: Hier werden alle Positionsgewichte berechnet und die Positionen, nach fallenden Gewichten geordnet, betrachtet. Jedoch werden alle Gewichte nach jedem Schritt aktualisiert und dann wird mit dem jeweils größten Gewicht fortgefahren.
  • Resultat: Man erhält wiederum eine gültige '<='-Lösung, bei der die Anzahl der gesetzten Atome mindestens 98% beträgt. Beipiel einer GreedyC-Lösung: VRML2 (VRML2-Browser ) GIF89

VRML2-Dateien und animierte GIFs für unterschiedliche Löser und Richtungen

Die dargestellten Beispiele arbeiten auf einem 10x10 Gitter und zeigen eine etwa 100 Sekunden lange Animation. Dies veranschaulicht die Vorgehensweise der Löser, tatsächlich haben echte Probleme die Größenordnung 500^2. Ebenso sind die gezeigten 10x10 Probleme um den Faktor 10000 verlangsamt, sie sind in Wirklichkeit in 10 Millisekunden gelöst.
Die als kleine Würfel dargestellten Kandidatenpunkte des Gitters sind mit ihrem Positionsgewicht eingefärbt: von dunkelgrau (kleines Gewicht) bis hellrot (großes Gewicht), das jeweils maximale Gewicht (s.u.) wird weiß dargestellt.
Bedeutung der Zahlen:
  • VRML:
    oben links(lila): Anzahl der Atome im Original
    oben rechts(gelb): bisher gesetzte Atome
    unten(cyan): aktuell maximales Gewicht
  • GIF89:
    im Standbild links: Anzahl der Atome im Original
    rechts oben: bisher gesetzte Atome
    rechts unten: aktuell maximales Gewicht
Animationskontrolle im VRML-Beispiel: Die drei Schalter unten rechts bedeuten: manuell zurück - Automatik ein/aus - manuell vor

2 Richtungen 3 Richtungen 4 Richtungen 5 Richtungen
GreedyA VRML2 GIF89 VRML2 GIF89 VRML2 GIF89 VRML2 GIF89
GreedyB VRML2 GIF89 VRML2 GIF89 VRML2 GIF89 VRML2 GIF89
GreedyC VRML2 GIF89 VRML2 GIF89 VRML2 GIF89 VRML2 GIF89

VRML2-Browser zum Betrachten der Beispiele