DE19617162C2

DE19617162C2 - Verfahren zur Anwendung eines 3D-Gridding-Prozesses in einem Computertomographen sowie Computertomograph zur Durchführung des Verfahrens

Info

Publication number: DE19617162C2
Application number: DE19617162A
Authority: DE
Inventors: Juergen Forchheim Dipl Wohlrab
Original assignee: Siemens AG; Siemens Corp
Current assignee: Siemens AG; Siemens Corp
Priority date: 1996-04-29
Filing date: 1996-04-29
Publication date: 1998-04-16
Anticipated expiration: 2016-04-30
Also published as: US5781605A; DE19617162A1; JPH1043176A

Description

Die Erfindung betrifft ein Verfahren zur Gewichtung von random-verteilten Stützstellen SP im Frequenzraum, um einen 3D-Gridding-Algorithmus für eine dreidimensionale Fourier-Rekonstruktion für einen Computertomographen anwenden zu können sowie einen Computertomographen zur Durchführung des Verfahrens.

In der Computertomographie ist es heute Stand der Technik, daß Fächerprojektionen gemessen werden. Die Fächerprojektionen können durch eine geeignete Interpolation in Parallelprojek tionen umgerechnet werden.

Zur Rekonstruktion eines Schnittbildes aus Parallelprojektio nen gibt es die beiden Rekonstruktionsalgorithmen Faltungs- Rückprojektion und Fourier-Rekonstruktion. Hieraus läßt sich eine dreidimensionale Fourier-Rekonstruktion zur Volumenrekon struktion ableiten.

Für die zweidimensionale Fourier-Rekonstruktion ist ein Grid ding-Algorithmus bekannt. Der Gridding-Algorithmus beschreibt den Übergang vom Polargitter zum kartesischen Gitter im zwei dimensionalen Frequenzraum. In der älteren deutschen Patentanmeldung gemäß der DE 195 38 053 A1 wurde ein Rechenwerk zur Implementierung einer zweidimensionalen Fourier-Rekonstruktion vorgeschlagen.

Der zweidimensionale Gridding-Prozeß kann auf einen dreidimen sionalen Gridding-Prozeß erweitert werden: Der 3D-Gridding-Al gorithmus beschreibt den Übergang von im allgemeinen nicht im kartesischen Raster liegenden Stützstellen auf ein dreidimen sionales kartesisches Frequenzraster. Das zu rekonstruierende Volumen kann durch dreidimensionale Rücktransformation vom Frequenzbereich in den Ortsbereich bestimmt werden.

Der Erfindung liegt die Aufgabe zugrunde, ein Verfahren zur Ge wichtung von random-verteilten Stützstellen im Frequenzraum zu schaffen, um einen 3D-Gridding-Algorithmus für eine dreidimen sionale Fourier-Rekonstruktion für einen Computertomographen anwenden zu können, sowie einen Computertomographen zur Durch führung des Verfahrens auszubilden.

Diese Aufgabe ist für ein Verfahren gelöst durch die Merkmale des Patentanspruches 1. Eine effiziente Realisierung des Ver fahrens in einem Computertomographen ist gelöst durch die Merk male des Patentanspruches 2. Bei diesem Computertomographen ist zur effizienten Implementierung des Verfahrens zur Ermitt lung der Gewichte der im allgemeinen nicht im kartesischen Ra ster liegenden Stützstellen und des 3D-Gridding-Algorithmus eine Spezialhardware in Form eines Rechenwerkes für Volumen- Gridding mit Application Specific Integrated Circuits (VGR-ASIC) vorgeschlagen. Bei der Weiterbildung gemäß dem Pa tentanspruch 3 kann der zum Eingangsdatenbus A zugehörige Adreßbus ADR_A entfallen, wenn die zu den Daten gehörigen Adressen mit auf dem Datenbus A übertragen werden.

Die Erfindung ist nachfolgend anhand von Zeichnungen näher er läutert. Es zeigen:

Fig. 1 die wesentlichen Teile eines Computertomographen mit Fä cherstrahl zur Erläuterung des Erfindungsgedankens, und

Fig. 2 bis 5 graphische Darstellungen zur Erläuterung der Er findung.

In der Fig. 1 ist ein Röntgenstrahler 1 und ein aus einer Matrix von Detektorelementen bestehender Detektor 2 dargestellt. Die Komponenten 1 und 2 rotieren zur Abtastung eines Objektes 3 um eine Systemachse 4, so daß das Objekt 3 unter verschiedenen Richtungen von dem vom Röntgenstrahler 1 ausgehenden fächer förmigen Röntgenstrahlbündel 5 durchstrahlt wird. Die von den Detektorelementen des Detektors 3 gelieferten Daten werden ei nem Rechner 6 zugeführt, der Schichtbilder innerhalb des durch strahlten Volumens des Objektes 3 rekonstruiert, welche auf einem Monitor 7 wiedergegeben werden. Das Objekt 3 liegt dabei in einem durch das Röntgenstrahlbündel 5 erfaßten Meßfeld 8.

Darstellung der Rechenschritte des 3D-Gridding-Algorithmus:
Die Rechenschritte des 3D-Gridding-Algorithmus ergeben sich aus einer Analogie zum bekannten Gridding-Algorithmus für den zweidimensionalen Fall.

Der 3D-Gridding-Algorithmus ist nur dann anwendbar, wenn die Funktionswerte der i.a. nicht im kartesischen Raster liegenden Stützstellen bereits geeignet gewichtet sind.

Beim 3D-Gridding-Algorithmus trägt jeder Punkt zu NX . NY . NZ Punkten des kartesischen Gitters des kartesischen Frequenzku bus bei. In Fig. 2 ist der Beitrag eines i.a. nicht im karte sischen Raster liegenden Stützwertes SP auf den kartesischen Frequenzkubus anhand von NX=NY=NZ=4 dargestellt.

Der kartesische Frequenzkubus hat die Dimension FMATX . FMA TY . FMATZ (siehe Fig. 2 ). Ein komplexes Element des kartesi schen Frequenzkubus wird im folgenden durch FM[m][k][l] referenziert.

Zu Beginn des 3D-Gridding-Algorithmus werden die Elemente des kartesischen Frequenzkubus mit dem Wert 0.0+j0.0 initiali siert.

Für jeden der i.a. nicht im kartesischen Raster liegenden Stützwert SP müssen alle nachfolgenden Rechenschritte durch laufen werden.

Bestimmung der Koordinaten des Eckpunktes UP(FXUP,FYUP,FZUP) aus den Koordinaten der i.a. nicht im kartesischen Raster lie genden Stützstelle SP(FXSP,FYSP,FZSP):

<A1.< FXUP ist die x-Koordinate des linken, unteren, vorde ren kartesischen Rasterpunktes UP im dreidimensionalen Interpolationsfenster
(1 Subtraktion mit Rundung)
<A2.< FYUP ist die y-Koordinate des linken, unteren, vorde ren kartesischen Rasterpunktes UP im dreidimensionalen Interpolationsfenster
(1 Subtraktion mit Rundung)
<A3.< FZUP ist die z-Koordinate des linken, unteren, vorde ren kartesischen Rasterpunktes UP im dreidimensionalen Interpolationsfenster
(1 Subtraktion mit Rundung)

Bestimmung der Hilfsgrößen DX, DY und DZ:

<A4.< DX = FXSP - FXUP (1 Subtraktion)
<A5.< DY = FYSP - FYUP (1 Subtraktion)
<A6.< DZ = FZSP - FZUP (1 Subtraktion)

Die nachfolgend in den Schritten <A7.< bis <A30.< verwendete ganzzahlige Laufvariable i geht von i=0 bis i=NX-1.

Die nachfolgend in den Schritten <A7.< bis <A30.< verwendete ganzzahlige Laufvariable j geht von j=0 bis j=NY-1.

Die nachfolgend in den Schritten <A7.< bis <A30.< verwendete ganzzahlige Laufvariable h geht von h=0 bis h=NZ-1.

Der Indexbereich der Interpolationstabelle INTTABL in Richtung von 1 geht von pl=0 bis pl=LINTPL-1,
Interpolationstabelle INTTABK in Richtung von k geht von pk=0 bis pk=LINTPK-1,
Interpolationstabelle INTTABM in Richtung von m geht von pm=0 bis pm=LINTPM-1.

Dies schließt den Spezialfall mit ein, daß alle drei Interpo lationstabellen gleich sind, und in allen 3 Richtungen gleich interpoliert wird.

Bestimmung der Zugriffsindices px[i], py[j] und pz[h] auf die Interpolationstabellen INTTABL, INTTABK und INTTABM mit den jeweiligen Längen LINTPL, LINTPK, LINTPM:

<A7.< px[i] ist der auf die nächste ganze Zahl gerundete Wert von Absolutbetrag von (DX+i) . LINTPL . 2/NX
(1 Rundung, 1 Multiplikation und NX-1 Additionen;
der Wert LINTPL . 2/NX stellt eine Konstante dar und braucht nur einmal berechnet zu werden)
<A8.< py[j] ist der auf die nächste ganze Zahl gerundete Wert von Absolutbetrag von (DY+j) . LINTPK . 2/NY
(1 Rundung, 1 Multiplikation und NY-1 Additionen;
der Wert LINTPK . 2/NY stellt eine Konstante dar und braucht nur einmal berechnet zu werden).
<A9.< pz[h] ist der auf die nächste ganze Zahl gerundete Wert von Absolutbetrag von (DZ+h) . LINTPM . 2/NZ
(1 Rundung, 1 Multiplikation und NZ-1 Additionen;
der Wert LINTPM . 2/NZ stellt eine Konstante dar und braucht nur einmal berechnet zu werden).

Adressierung der Werte Ix[i], Iy[j] und Iz[h] der Interpola tionstabellen an den ermittelten Zugriffsindices px[i], py[j] und pz [h]:

<A10.< Ix[i] ist der Wert der Interpolationstabelle INTTABL beim Zugriffsindex px[i] (NX Zugriffe auf die Interpo lationstabelle INTTABL)
<A11.< Iy[j] ist der Wert der Interpolationstabelle INTTABK beim Zugriffsindex py[j] (NY Zugriffe auf die Interpo lationstabelle INTTABK)
<A12.< Iz[h] ist der Wert der Interpolationstabelle INTTABM beim Zugriffsindex pz[h] (NZ Zugriffe auf die Interpo lationstabelle INTTABM).

Berechnung der Zugriffsindices zl[i], zk[j] und zm[h] der Ele mente des kartesischen Frequenzkubus, die sich im dreidimen sionalen Interpolationsfenster der i.a. nicht im kartesischen Raster liegenden Stützstelle befinden:

<A13.< pl[i] = FXUP + i (NX Additionen)
<A14.< pk[j] = FYUP + j (NY Additionen)
<A15.< pm[h] = FZUP + h (NZ Additionen)
<A16.< zl[i] = {pl[i] wird modulo auf den Bereich [0,FMATX-1] abgebildet}
<A17.< zk[j] = {pk[j] wird modulo auf den Bereich [0,FMATY-1] abgebildet}
<A18.< zm[h] = {pm[h] wird modulo auf den Bereich [0,FMATZ-1] abgebildet}.

Adressierung der Werte FMZ[zm[h]] [zk[j]] [zl[i]] der Elemente des kartesischen Frequenzkubus, die sich im dreidimensionalen Interpolationsfenster der i.a. nicht im kartesischen Raster liegenden Stützstelle befinden:

<A19.< FMZ_RE[zm[h]] [zk[j]] [zl[i]] ist der Realteilwert des Speichers des kartesischen Frequenzkubus
FM[zm[h]] [zk[j]] [zl[i]]
(NX . NY . NZ Zugriffe auf kartesischen Frequenzkubus)
<A20.< FMZ_IM[zm[h]] [zk[j]] [zl[i]] ist der Imaginärteilwert des Speichers des kartesischen Frequenzkubus
FM[zm[h]] [zk[j]] [zl[i]]
(NX . NY . NZ Zugriffe auf kartesischen Frequenzkubus).

SP_RE ist der Realteil der i.a. nicht im kartesischen Raster liegenden Stützstelle SP.

SP_IM ist der Imaginärteil der i.a. nicht im kartesischen Ra ster liegenden Stützstelle SP.

Berechnung der Zuschläge ZU_RE[h] [j] [i] und ZU_IM[h] [j] [i] auf die Elemente des kartesischen Frequenzkubus, die im dreidimen sionalen Interpolationsfenster der i.a. nicht im kartesischen Raster liegenden Stützstelle SP liegen:

<A21.< ZUX_RE[i] = SP_RE . Ix[i] (NX Multiplikationen)
<A22.< ZUX_IM[i] = SP_IM . Ix[i] (NX Multiplikationen)
<A23.< ZU_RE[j] [i] = ZUX_RE[i] . Iy[j] (NY . NX Multiplika tionen).
<A24.< ZU_IM[j] [i] = ZUX_IM[i] . Iy[j] (NY . NX Multiplika tionen)
<A25.< Mul tiplikationen)
<A26.< ZU_IM[h] [j] [i] = ZUX_IM[j] [i] . Iz[h] (NZ . NY . NX Mul tiplikationen).

Bildung der Zuschläge auf die Elemente des kartesischen Fre quenzkubus, die im dreidimensionalen Interpolationsfenster der i.a. nicht im kartesischen Raster liegenden Stützstelle lie gen:

<A27.< FMZE_RE[zm[h]] [zk[j]] [zl[i]] = FMZ_RE[zm[h]] [zk[j]] [zl[i]] + ZU_RE[h] [j] [i]
(NX . NY . NZ Additionen)
<A28.< FMZE_IM[zm[h]] [zk[j]] [zl[i]] = FMZ_IM[zm[h]] [zk[j]] [zl[i]] + ZU_IM[h] [j] [i]
(NX . NY . NZ Additionen).

Übertragen der berechneten Werte in den Speicher des kartesi schen Frequenzkubus:

<A29.< Der Realteil der Speicherzelle FM[zm[h]] [zk[j]] [zl[i]] in dem kartesischen Frequenzkubus wird überschrieben mit dem neu berechneten Wert FMZE_RE[zm[h]] [zk[j]] [zl[i]].
(NX . NY . NZ Zugriffe auf kartesischen Frequenzkubus)
<A30.< Der Imaginärteil der Speicherzelle FM[zm[h]] [zk[j]] [zl[i]] in dem kartesischen Frequenz kubus wird überschrieben mit dem neu berechneten Wert FMZE_IM[zm[h]] [zk[j]] [zl[i]].
(NX . NY . NZ Zugriffe auf kartesischen Frequenzkubus).

Verfahren zur Ermittlung der Gewichte der i.a. nicht im karte sischen Raster liegenden Stützstellen:
Der 3D-Gridding-Algorithmus beschreibt den Übergang von im i.a. nicht im kartesischen Raster liegenden Stützstellen auf ein dreidimensionales kartesisches Frequenzraster. Dabei wird angenommen, daß die i.a. nicht im kartesischen Raster liegenden Stützstellen SP im Frequenzkubus random-verteilt sind. Dies erfordert eine geeignete Gewichtung der i.a. nicht im kartesi schen Raster liegenden Stützstellen vor der Durchführung des 3D-Gridding-Prozesses, um Verteilungsinhomogenitäten auszu gleichen. Die Funktionswerte des Frequenzkubus in Gebieten mit größeren Stützstellendichte wären sonst erhöht gegenüber den Funktionswerten in Gebieten mit niedrigerer Stützstellendich te.

Das hierzu erfundene Verfahren zur Gewichtung der i.a. nicht im kartesischen Raster liegenden Stützstellen ist wie folgt:

1. 3D-Pre-Gridding-Prozeß: Durchführung des 3D-Pre-Gridding- Prozesses, wobei für alle Stützstellen SP anstelle des tat sächlichen Funktionswertes der Funktionswert 1.0 hergenom men wird. Das Ergebnis des 3D-Pre-Gridding-Prozesses ist ein reeller Gewichtekubus FMG in einem kartesischen Ra ster, bei dem die Funktionswerte die Verteilungsinhomoge nitäten der Stützstellen SP beschreiben.
Beim 3D-Pre-Gridding-Algorithmus trägt genau wie beim 3D- Gridding-Algorithmus jeder Punkt zu NX . NY . NZ Punkten KR des kartesischen Gitters des kartesischen Gewichtekubus FMG bei. Für das 3D-Pre-Gridding werden genau wie beim 3D- Gridding die Interpolationstabellen INTTABL(x), INTTABK(y) und INTTABM(z) verwendet, wobei x, y und z den Abstand zwi schen einem kartesischen Rasterpunkt KR und der Stützstel le SP darstellen.
2. Gewichteinterpolation: Das Gewicht GEW für eine Stützstel le SP wird aus den NX . NY . NZ Punkten KRG des Gewichtekubus FMG ermittelt, die im dreidimensionalen Interpolationsfen ster des 3D-Gridding-Prozesses liegen. Die Funktionswerte FKRG der Punkte KRG werden dazu durch eine Bewertungsfunk tion BF in Funktionswerte FKRGK umgewandelt. Die Bewer tungsfunktion BF leistet dabei im wesentlichen eine Kehr wertbildung mit geeigneter Begrenzung der Ausgangswerte. Das Gewicht GEW wird aus den Funktionswerten FKRGK der Punkte KRG wie folgt bestimmt: Jeder Funktionswert FKRGK der Punkte KRG wird mit den entsprechenden Interpolations gewichten INTTABL(x) . INTTABK(y) . INTTABM(z) multipliziert, und die Ergebnisse werden aufaddiert. Das Endergebnis ist das Ge wicht GEW. x, y und z stellen den Abstand zwischen dem je weiligen kartesischen Rasterpunkt der Punkte KRG und der Stützstelle SP dar.

Darstellung der Rechenschritte des 3D-Pre-Gridding-Verfahrens: Die Rechenschritte des 3D-Pre-Gridding ergeben sich aus einer Analogie zum 3D-Gridding-Algorithmus. Der wesentliche Unter schied zum 3D-Gridding-Algorithmus besteht darin, daß beim 3D- Pre-Gridding für alle Stützstellen SP anstelle des tatsächli chen Funktionswertes der Funktionswert 1.0 hergenommen wird. Beim 3D-Pre-Gridding-Algorithmus trägt jeder Punkt zu NX . NY . NZ Punkten des kartesischen Gitters des kartesischen Gewichteku bus bei. Der kartesische Gewichtekubus ist reell. In Fig. 2 ist der Beitrag eines i.a. nicht im kartesischen Raster liegenden Stützwertes SP auf den kartesischen Gewichtekubus anhand von NX=NY=NZ=4 dargestellt.

Der kartesische Gewichtekubus hat die Dimension FMATX . FMA TY . FMATZ (siehe Fig. 2 ). Ein reelles Element des kartesischen Gewichtekubus wird im folgenden durch FMG[m] [k] [l] referen ziert.

Zu Beginn des 3D-Pre-Gridding-Algorithmus werden die Elemente des kartesischen Gewichtekubus mit dem Wert 0.0 initialisiert. Für jeden der i.a. nicht im kartesischen Raster liegenden Stützwert SP müssen alle nachfolgenden Rechenschritte durch laufen werden.

<B1.< FXUP ist die x-Koordinate des linken, unteren, vorde ren kartesischen Rasterpunktes UP im dreidimensionalen Interpolationsfenster (1 Subtraktion mit Rundung)
<B2.< FYUP ist die y-Koordinate des linken, unteren, vorde ren kartesischen Rasterpunktes UP im dreidimensionalen Interpolationsfenster (1 Subtraktion mit Rundung)
<B3.< FZUP ist die z-Koordinate des linken, unteren, vorde ren kartesischen Rasterpunktes UP im dreidimensionalen Interpolationsfenster (1 Subtraktion mit Rundung)

Bestimmung der Hilfsgrößen DX, DYund DZ:

<B4.< DX = FXSP - FXUP (1 Subtraktion)
<B5.< DY = FYSP - FYUP (1 Subtraktion)
<B6.< DZ=FZSP-FZUP (1 Subtraktion)

Die nachfolgend in den Schritten <B7.< bis <B23.< verwendete ganzzahlige Laufvariable i geht von i=0 bis i=NX-1.

Die nachfolgend in den Schritten <B7.< bis <B23.< verwendete ganzzahlige Laufvariable j geht von j=0 bis j=NY-1.

Die nachfolgend in den Schritten <B7.< bis <B23.< verwendete ganzzahlige Laufvariable h geht von h=0 bis h=NZ-1.

<B7.< px[i] ist der auf die nächste ganze Zahl gerundete Wert von Absolutbetrag von (DX+i) . LINTPL . 2/NX
(1 Rundung, 1 Multiplikation und NX-1 Additionen, der Wert LINTPL . 2/NX stellt eine Konstante dar und braucht nur einmal berechnet zu werden)
<B8.< py[j] ist der auf die nächste ganze Zahl gerundete Wert von Absolutbetrag von (DY+j) . LINTPK . 2/NY
(1 Rundung, 1 Multiplikation und NY-1 Additionen; der Wert LINTPK . 2/NY stellt eine Konstante dar und braucht nur einmal berechnet zu werden)
<B9.< pz[h] ist der auf die nächste ganze Zahl gerundete Wert von Absolutbetrag von (DZ+h) . LINTPM . 2/NZ
(1 Rundung, 1 Multiplikation und NZ-1 Additionen; der Wert LINTPM . 2/NZ stellt eine Konstante dar und braucht nur einmal berechnet zu werden).

Adressierung der Werte Ix[i], Iy[j) und Iz[h) der Interpolati onstabellen an den ermittelten Zugriffsindices px[i], py[j] und pz[h]:

<B10.< Ix[i] ist der Wert der Interpolationstabelle INTTABL beim Zugriffsindex px[i]
(NX Zugriffe auf die Interpolationstabelle INTTABL)
<B11.< Iy[j] ist der Wert der Interpolationstabelle INTTABK beim Zugriffsindex py[j]
NY Zugriffe auf die Interpolationstabelle INTTABK)
<B12.< Iz[h] ist der Wert der Interpolationstabelle INTTABM beim Zugriffsindex pz[h]
(NZ Zugriffe auf die Interpolationstabelle INTTABM).

Berechnung der Zugriffsindices zl[i], zk[j] und zm[h] der Ele mente des kartesischen Gewichtekubus, die sich im dreidimen sionalen Interpolationsfenster der i.a. nicht im kartesischen Raster liegenden Stützstelle befinden:

<B13.< pl[i] = FXUP + i (NX Additionen)
<B14.< pk[j] = FYUP + j (NY Additionen)
<B15.< pm[h] = FZUP + h (NZ Additionen)
<B16.< zl[i] = {pl[i] wird modulo auf den Bereich [0,FMATX-1] abgebildet}
<B17.< zk[j] = {pk[j] wird modulo auf den Bereich [0,FMATY-1] abgebildet}
<B18.< zm[h] = {pm[h] wird modulo auf den Bereich [0,FMATZ-1] abgebildet}.

Adressierung der Werte FMG[zm[h]] [zk[j]] [zl[i]] der Elemente des kartesischen Gewichtekubus, die sich im dreidimensionalen Interpolationsfenster der i.a. nicht im kartesischen Raster liegenden Stützstelle befinden:

<B19.< FMG[zm[h]] [zk[j]] [zl[i]] ist der Wert des Speichers des kartesischen Gewichtekubus
(NX . NY . NZ Zugriffe auf kartesischen Gewichtekubus).

Berechnung der Zuschläge ZU[h] [j] [i] auf die Elemente des kar tesischen Gewichtekubus, die im dreidimensionalen Interpolati onsfenster der i.a. nicht im kartesischen Raster liegenden Stützstelle SP liegen:

<B20.< ZUX[j] [i] = Ix[i] . Iy[j] (NY . NX Multiplikationen)
<B21.< ZU[h] [j] [i] = ZUX[j] [i] . Iz[h] (NZ . NY . NX Multipli kationen).

Bildung der Zuschläge auf die Elemente des kartesischen Gewich tekubus, die im dreidimensionalen Interpolationsfenster der i.a. nicht im kartesischen Raster liegenden Stützstelle lie gen:

<B22.< FMZG[zm[h]] [zk[j]] [zl[i]] = FMG[zm[h]] [zk[j]] [zl[i]]+ ZU[h] [j] [i]
(NX . NY . NZ Additionen).

Übertragen der berechneten Werte in den Speicher des kartesi schen Gewichtekubus:

<B23.< Die Speicherzelle FMG[zm[h]] [zk[j]] [zl[i]] in dem kar tesischen Gewichtekubus wird überschrieben mit dem neu berechneten Wert
FMZG[zm[h]] [zk[j]] [zl[i]].
(NX . NY . NZ Zugriffe auf kartesischen Gewichtekubus).

Darstellung der Rechenschritte der Gewichteinterpolation:
Hier werden die Rechenschritte des bereits vorgestellten Ver fahrens der Gewichteinterpolation beschrieben.

Bei der Gewichteinterpolation wird das Gewicht für einen i.a. nicht im kartesischen Raster liegenden Stützwert SP aus den NX . NY . NZ Punkten (siehe Fig. 2 ) des kartesischen Gitters des kartesischen Gewichtekubus FMG durch Interpolation bestimmt. Zur Durchführung der Gewichteinterpolation ist eine gültige kartesische Gewichtematrix notwendig. Die kartesische Gewich tematrix wird durch das 3D-Pre-Gridding bestimmt, oder für eine bekannte Stützstellenverteilung als Tabelle geladen.

Der kartesische Gewichtekubus hat die Dimension FMATX . FMA TY . FMATZ (siehe Fig. 2). Ein reelles Element des kartesischen Gewichtekubus wird im folgenden durch FMG[m] [k] [l] referen ziert.

Für jeden der i.a. nicht im kartesischen Raster liegenden Stützwert SP(FXSP,FYSP,FZSP) müssen alle nachfolgenden Rechen schritte durchlaufen werden.

Bestimmung der Koordinaten des Eckpunktes UP(FXUP,FYUP,FZUP) aus den Koordinaten der i.a. nicht im kartesischen Raster lie genden Stützstelle SP(FXSP, FYSP, FZSP):

<C1.< FXUP ist die x-Koordinate des linken, unteren, vorde ren kartesischen Rasterpunktes UP im dreidimensionalen Interpolationsfenster
(1 Subtraktion mit Rundung)
<C2.< FYUP ist die y-Koordinate des linken, unteren, vorde ren kartesischen Rasterpunktes UP im dreidimensionalen Interpolationsfenster
(1 Subtraktion mit Rundung)
<C3.< FZUP ist die z-Koordinate des linken, unteren, vorde ren kartesischen Rasterpunktes UP im dreidimensionalen Interpolationsfenster
(1 Subtraktion mit Rundung).

Bestimmung der Hilfsgrößen DX und DY:

<C4.< DX = FXSP - FXUP (1 Subtraktion)
<C5.< DY = FYSP - FYUP (1 Subtraktion)
<C6.< DZ = FZSP - FZUP (1 Subtraktion).

Die nachfolgend in den Schritten <C7.< bis <C23.< verwendete ganzzahlige Laufvariable i geht von i=0 bis i=NX-1.

Die nachfolgend in den Schritten <C7.< bis <C23.< verwendete ganzzahlige Laufvariable j geht von j=0 bis j=NY-1.

Die nachfolgend in den Schritten <C7.< bis <C23.< verwendete ganzzahlige Laufvariable h geht von h=0 bis h=NZ-1.

Der Indexbereich der Interpolationstabelle INTTABL in Richtung von l geht von pl=0 bis pl=LINTPL-1,
Interpolationstabelle INTTABK in Richtung von k geht von pk=0 bis pk=LINTPK-1,
Interpolationstabelle INTTABM in Richtung von m geht von pm=0 bis pm=LINTPM-l.

<C7.< px[i] ist der auf die nächste ganze Zahl gerundete Wert von Absolutbetrag von (DX+i) . LINTPL . 2/NX
(1 Rundung, 1 Multiplikation und NX-1 Additionen;
der Wert LINTPL . 2/NX stellt eine Konstante dar und braucht nur einmal berechnet zu werden)
<C8.< py[j] ist der auf die nächste ganze Zahl gerundete Wert von Absolutbetrag von (DY+j) . LINTPK . 2/NY
(1 Rundung, 1 Multiplikation und NY-1 Additionen;
der Wert LINTPK . 2/NY stellt eine Konstante dar und braucht nur einmal berechnet zu werden).
<C9.< pz [h] ist der auf die nächste ganze Zahl gerundete Wert von Absolutbetrag von (DZ+h) . LINTPM . 2/NZ
(1 Rundung, 1 Multiplikation und NZ-1 Additionen;
der Wert LINTPM . 2/NZ stellt eine Konstante dar und braucht nur einmal berechnet zu werden).

<C10.< Ix[i] ist der Wert der Interpolationstabelle INTTABL beim Zugriffsindex px[i] (NX Zugriffe auf die Interpo lationstabelle INTTABL)
<C11.< Iy[j] ist der Wert der Interpolationstabelle INTTABK beim Zugriffsindex py[j] (NY Zugriffe auf die Interpo lationstabelle INTTABK)
<C12.< Iz[h] ist der Wert der Interpolationstabelle INTTABM beim Zugriffsindex pz [h] (NZ Zugriffe auf die Interpo lationstabelle INTTABM).

<C13.< pl[i] = FXUP + i (NX Additionen)
<C14.< pk[j] = FYUP + j (NY Additionen)
<C15.< pm[h] = FZUP + h (NZ Additionen)
<C16.< zl[i] = {pl[i] wird modulo auf den Bereich [0,FMATX-1] abgebildet}
<C17.< zk[j] = {pk[j] wird modulo auf den Bereich [0,FMATY-1] abgebildet}
<C18.< zm[h] = {pm[h] wird modulo auf den Bereich [0,FMATZ-1] abgebildet}.

<C19.< FMG[zm[h]] [zk[j]] [zl[i]] ist der Wert des Speichers des kartesischen Gewichtekubus
(NX . NY . NZ Zugriffe auf kartesischen Gewichtekubus).

Berechnung des Gewichtes GEW(FXSP,FYSP,FZSP) der i.a. nicht im kartesischen Raster liegenden Stützstelle SP(FX- SP,FYSP,FZSP):

<C20.< IXY[j] [i] = Ix[i] . Iy[j] (NY . NX Multiplikationen)
<C21.< I[h] [j] [i] = IXY[j] [i] . Iz[h] (NZ . NY . NX Multipli kationen)
<C22.< Umwandlung der aus den in Schritt <C19.< gelesenen Wer te FMG[zm[h]] [zk[j]] [zl[i]] mit dem Operator, der die Bewertungsfunktion BF realisiert.
FMGBW[zm[h]] [zk[j]] [zl[i]]=BW(FMG[zm[h]] [zk[j]] [zl[i] ])
(NX . NY . NZ Operationen).
Sofern nach dem 3D-Pre-Gridding die Elemente der Ge wichtematrix FMG durch den mit der Bewertungsfunktion BW bewerteten Wert FMGBW ersetzt werden, kann der Re chenschritt <C22.< bei der Gewichteinterpolation ent fallen.
<C23.< Multiplikation der Werte FMGBW [zm[h]] [zk[j]] [zl[i]] mit dem entsprechenden Interpolationsgewicht I[h] [j] [i] und Addition der Ergebnisse. Das Ergebnis ist das Gewicht GEW(FXSP,FYSP,FZSP).
(NZ . NY . NX Multiplikationen, NZ . NY . NX-1 Additionen).

SP_RE(FXSP,FYSP,FZSP) ist der Realteil des Funktionswertes der i.a. nicht im kartesischen Raster liegenden Stützstelle SP(FX SP,FYSP,FZSP).

SP_IM(FXSP,FYSP,FZSP) ist der Imaginärteil des Funktionswertes der i.a. nicht im kartesischen Raster liegenden Stützstelle SP(FXSP,FYSP,FZSP).

Gewichtung der Stützstelle SP(FXSP,FYSP,FZSP):

<C24.< GSP_RE(FXSP,FYSP,FZSP) = SP_RE(FXSP,FYSP,FZSP) . GEW(FXSP,FYSP,FZSP)
(1 Multiplikation)
<C25.< GSP_IM(FXSP,FYSP,FZSP) = SP_IM(FXSP,FYSP,FZSP) . GEW(FXSP,FYSP,FZSP)
(1 Multiplikation).

Verarbeitungsablauf von 3D-Pre-Gridding, Gewichteinterpolati on und 3D-Gridding:
Der Vorteil des vorgestellten Verfahrens zur Bestimmung der Ge wichte der i.a. nicht im kartesischen Raster liegenden Stütz stellen besteht darin, daß die Rechenschritte <C1.< bis <C18.< von der Gewichteinterpolation mit den Rechenschritten <A1.< bis <A18.< des 3D-Gridding-Prozesses identisch sind. Dadurch läßt sich die Bestimmung der Gewichte der i.a. nicht im karte sischen Raster liegenden Stützstellen sehr effizient in Ver bindung mit dem 3D-Gridding-Prozeß implementieren.

Das Ergebnis ist ein 3D-Gridding-Verfahren mit schrittweiser Gewichteinterpolation:

a) Für eine Stützstelle SP werden zuerst die Rechen schritte <A1.< bis <A18.< des 3D-Gridding durchge führt. Somit sind automatisch auch die Rechenschritte <C1.< bis <C18.< der Gewichteinterpolation implemen tiert.
b) Anschließend wird mit <C19.< bis <C23.< das Gewicht GEW bestimmt, mit dem der Funktionswert der Stützstelle SP zur Durchführung des 3D-Gridding gewichtet werden muß. In Schritt <C24.< und <C25.< erfolgt dann die Ge wichtung des Funktionswertes der Stützstelle SP.
c) Dann werden die Rechenschritten <A19.< bis <A30.< des 3D-Gridding-Algorithmus durchgeführt.

Zur Durchführung der Gewichteinterpolation und des 3D-Grid ding-Prozesses ist eine gültige kartesische Gewichtematrix notwendig. Die kartesische Gewichtematrix wird durch das 3D- Pre-Gridding bestimmt, oder für eine bekannte Stützstellenver teilung als Tabelle geladen.

Sollen die Gewichteinterpolation und das 3D-Gridding nachein ander für mehrere Rekonstruktionen durchgeführt werden, und bleibt die Verteilung der i.a. nicht im kartesischen Raster liegenden Stützstellen SP jeweils gleich, so braucht das 3D- Pre-Gridding nur vor der Gewichteinterpolation der ersten Re konstruktion durchgeführt werden. Die beim 3D-Pre-Gridding er zeugte kartesische Gewichtematrix ist dann für alle Rekon struktionen mit der gleichen Verteilung der i.a. nicht im kar tesischen Raster liegenden Stützstellen SP gültig. Die karte sische Gewichtematrix könnte für eine bekannte Verteilung der Stützstellen SP auch als Tabelle geladen werden.

Ist die Verteilung der i.a. nicht im kartesischen Raster lie genden Stützstellen SP bei mehreren Rekonstruktionen verschie den, so ist vor der Gewichteinterpolation und dem 3D-Gridding jeweils ein 3D-Pre-Gridding durchzuführen.

Darstellung der in das VGR-ASIC implementierten Rechenschritte des 3D-Gridding-Algorithmus mit schrittweiser Gewichteinterpo lation:
Hier werden die Rechenschritte des 3D-Gridding-Algorithmus mit schrittweiser Gewichteinterpolation beschrieben, die in das VGR-ASIC implementiert werden sollen.

Der kartesische Frequenzkubus hat die Dimension FMATX . FMA TY . FMATZ (siehe Fig. 2). Ein komplexes Element des kartesi schen Frequenzkubus wird im folgenden durch FM[m] [k] [l] referenziert.

<D1.< FXUP ist die x-Koordinate des linken, unteren, vorde ren kartesischen Rasterpunktes UP im dreidimensionalen Interpolationsfenster
(1 Subtraktion mit Rundung)
<D2.< FYUP ist die y-Koordinate des linken, unteren, vorde ren kartesischen Rasterpunktes UP im dreidimensionalen Interpolationsfenster
(1 Subtraktion mit Rundung)
<D3.< FZUP ist die z-Koordinate des linken, unteren, vorde ren kartesischen Rasterpunktes UP im dreidimensionalen Interpolationsfenster
(1 Subtraktion mit Rundung)

Bestimmung der Hilfsgrößen DX, DY und DZ:

<D4.< DX = FXSP - FXUP (1 Subtraktion)
<D5.< DY = FYSP - FYUP (1 Subtraktion)
<D6.< DZ = FZSP - FZUP (1 Subtraktion).

Die nachfolgend in den Schritten <D7.< bis <D37.< verwendete ganzzahlige Laufvariable i geht von i=0 bis i=NX-1.

Die nachfolgend in den Schritten <D7.< bis <D37.< verwendete ganzzahlige Laufvariable j geht von j=0 bis j=NY-1.

Die nachfolgend in den Schritten <D7.< bis <D37.< verwendete ganzzahlige Laufvariable h geht von h=0 bis h=NZ-1.

<D7.< px[i] ist der auf die nächste ganze Zahl gerundete Wert von Absolutbetrag von (DX+i) . LINTPL . 2/NX
(1 Rundung, 1 Multiplikation und NX-1 Additionen; der Wert LINTPL . 2/NX stellt eine Konstante dar und braucht nur einmal berechnet zu werden)
<D8.< py[j] ist der auf die nächste ganze Zahl gerundete Wert von Absolutbetrag von (DY+j) . LINTPK . 2/NY
(1 Rundung, 1 Multiplikation und NY-1 Additionen; der Wert LINTPK . 2/NY stellt eine Konstante dar und braucht nur einmal berechnet zu werden)
<D9.< pz [h] ist der auf die nächste ganze Zahl gerundete Wert von Absolutbetrag von (DZ+h) . LINTPM . 2/NZ
(1 Rundung, 1 Multiplikation und NZ-1 Additionen; der Wert LINTPM . 2/NZ stellt eine Konstante dar und braucht nur einmal berechnet zu werden).

Adressierung der Werte Ix[i], Iy[j] und Iz[h] der Interpola tionstabellen an den ermittelten Zugriffsindices px[i], py[j] und pz[h]:

<D10.< Ix[i] ist der Wert der Interpolationstabelle INTTABL beim Zugriffsindex px[i] (NX Zugriffe auf die Interpo lationstabelle INTTABL)
<D11.< Iy[j] ist der Wert der Interpolationstabelle INTTABK beim Zugriffsindex py[j] (NY Zugriffe auf die Interpo lationstabelle INTTABK)
<D12.< Iz[h] ist der Wert der Interpolationstabelle INTTABM beim Zugriffsindex pz [h] (NZ Zugriffe auf die Interpo lationstabelle INTTABM).

<D13.< pl[i] = FXUP + i (NX Additionen)
<D14.< pk[j] = FYUP + j (NY Additionen)
<D15.< pm[h] = FZUP + h (NZ Additionen)
<D16.< zl[i] = {pl[i] wird modulo auf den Bereich [0,FMATX-1] abgebildet}
<D17.< zk[j] = {pk[j] wird modulo auf den Bereich [0,FMATY-1] abgebildet}
<D18.< zm[h] = {pm[h] wird modulo auf den Bereich [0,FMATZ-1] abgebildet}.

<D19.< FMG[zm[h]] [zk[j]] [zl[i]] ist der Wert des Speichers des kartesischen Gewichtekubus
(NX . NY . NZ Zugriffe auf kartesischen Gewichtekubus).

Berechnung des Gewichtes GEW der i.a. nicht im kartesischen Ra ster liegenden Stützstelle SP:

<D20.< IXY[j][i] = Ix[i] . Iy[j] (NY . NX Multiplikationen)
<D21.< I[h][j][i] = IXY[j][i] . Iz[h] (NZ . NY . NX Multipli kationen)
<D22.< Umwandlung der aus den in Schritt <D19.< gelesenen Wer te FMG[zm[h]][zk[j]][zl[i]] mit dem Operator, der die Bewertungsfunktion BF realisiert.
FMGBW[zm[h]] [zk[j]] [zl[i]]=BW(FMG[zm[h]] [zk[j]] [zl[i]])
(NX . NY . NZ Operationen). Sofern nach dem 3D-Pre-Gridding die Elemente der Ge wichtematrix FMG durch den mit der Bewertungsfunktion BW bewerteten Wert FMGBW ersetzt werden, kann der Re chenschritt <D22.< bei der Gewichteinterpolation ent fallen.
<D23.< Multiplikation der Werte FMGBW [zm[h]] [zk[j]] [zl[i]] mit dem entsprechenden Interpolationsgewicht
I[h] [j] [i] und Addition der Ergebnisse. Das Ergebnis ist das Gewicht GEW.
(NZ . NY . NX Multiplikationen, NZ . NY . NX-1 Additionen).

SP_RE ist der Realteil des Funktionswertes der i.a. nicht im kartesischen Raster liegenden Stützstelle SP.

SP_IM ist der Imaginärteil des Funktionswertes der i.a. nicht im kartesischen Raster liegenden Stützstelle SP. Gewichtung der Stützstelle SP:

<D24.< GSP_RE = SP_RE . GEW
(1 Multiplikation)
<D25.< GSP_IM = SP_IM . GEW
(1 Multiplikation).

<D26.< FMZ_RE[zm[h]] [zk[j]] [zl[i]] ist der Realteilwert des Speichers des kartesischen Frequenzkubus
FM[zm[h]] [zk[j]] [zl[i]]
(NX . NY . NZ Zugriffe auf kartesischen Frequenzkubus)
<D27.< FMZ_IM[zm[h]] [zk[j]] [zl[i]] ist der Imaginärteilwert des Speichers des kartesischen Frequenzkubus
FM[zm[h]] [zk[j]] [zl[i]]
(NX . NY . NZ Zugriffe auf kartesischen Frequenzkubus).

<D28.< ZUX_RE[i] = GSP_RE . Ix[i] (NX Multiplikationen)
<D29.< ZUX_IM[i] = GSP_IM . Ix[i] (NX Multiplikationen)
<D30.< ZU_RE[j] [i] = ZUX_RE[i] . Iy[j] (NY . NX Multiplika tionen)
<D31.< ZU_IM[j] [i] = ZUX_IM[i] . Iy[j] (NY . NX Multiplika tionen)
<D32.< ZU_RE[h] [j] [i] = ZUX_RE[j] [i] . Iz[h]
(NZ . NY . NX Multiplikationen)
<D33.< ZU_IM[h] [j] [i] = ZUX_IM[j] [i] . Iz[h]
(NZ . NY . NX Multiplikationen).

<D34.< FMZE_RE[zm[h]] [zk[j]] [zl[i]] =
= FMZ_RE[zm[h]] [zk[j]] [zl[i]] + ZU_RE[h] [j] [i]
(NX . NY . NZ Additionen)
<D35.< FMZE_IM[zm[h]] [zk[j]] [zl[i]] =
= FMZ_IM[zm[h]] [zk[j]] [zl[i]] + ZU_IM[h] [j] [i]
(NX . NY . NZ Additionen).

<D36.< Der Realteil der Speicherzelle FM[zm[h]] [zk[j]] [zl [i]] in dem kartesischen Frequenzkubus wird überschrieben mit dem neu berechneten Wert
FMZE_RE[zm[h]] [zk[j]] [zl[i]].
(NX . NY . NZ Zugriffe auf kartesischen Frequenzkubus)
<D37.< Der Imaginärteil der Speicherzelle
FM[zm[h]] [zk[j]] [zl[i]] in dem kartesischen Frequenz kubus wird überschrieben mit dem neu berechneten Wert FMZE_IM[zm[h]] [zk[j]] [zl[i]].
(NX . NY . NZ Zugriffe auf kartesischen Frequenzkubus).

Schnittstellen des VGR-ASICs:
Zur Durchführung des 3D-Pre-Gridding-Algorithmus werden als Eingangsdaten die kartesischen Koordinaten (FX,FY,FZ) der Stützwerte SP im Frequenzbereich benötigt. Die Ausgangsdaten des 3D-Pre-Gridding-Algorithmus ist der kartesische Gewichte kubus.

Zur Durchführung des 3D-Gridding-Algorithmus mit Gewichtein terpolation werden als Eingangsdaten die kartesische Gewichte matrix FMG und die Funktionswerte der i.a. nicht im kartesischen Raster Stützwerte SP sowie die kartesischen Koor dinaten (FX,FY,FZ) der Stützwerte SP im Frequenzbereich benö tigt. Die Ausgangsdaten des 3D-Gridding-Algorithmus ist der kartesische Frequenzkubus.

Sowohl die Funktionswerte der Stützwerte SP, als auch die Daten des kartesischen Frequenzkubus FM sind komplex. Die Daten der kartesischen Gewichtematrix FMG sind reell.

Für die Übergabe der kartesischen Koordinaten der Stützwerte SP an das VGR-ASIC werden zwei Varianten vorgeschlagen:
VK1: Koordinatenübergabe-Variante 1: Die kartesischen Koordi naten (FX,FY,FZ) der Stützwerte SP werden jeweils nach der Übergabe der Stützwerte SP in Koordinateneingangs puffer des VGR-ASICs geschrieben. Die Koordinatenüberga be-Variante 1 eignet sich auch für Rekonstruktions-Algo rithmen, bei denen die Koordinaten von aufeinanderfol gend an das VGR-ASIC übergebenen Stützwerten nicht in ei nem durch konstante Koordinateninkremente DFX, DFY und DFZ beschreibbaren Zusammenhang stehen.
VK2: Koordinatenübergabe-Variante 2: Die Stützwerte SP eines Projektionsspektrums werden in einem Blocktransfer in das VGR-ASIC übertragen. Es wird vorausgesetzt, daß sich innerhalb des Transferblocks die Koordinaten von aufein anderfolgend an das VGR-ASIC übergebenen Stützstellen SP durch konstante Koordinateninkremente DFX, DFY und DFZ bestimmen lassen. Zu Beginn des Blocktransfers werden dabei die nachfolgend bezeichneten Aufsetzwerte an das VGR-ASIC übergeben, aus denen das VGR-ASIC die kartesi schen Koordinaten von den im Blocktransfer übergebenen Stützwerten SP selbst generieren kann:

- die kartesischen Koordinateninkremente DFX, DFY und DFZ zwischen den im Blocktransfer übergebenen Stütz werten und
- die Anzahl der Stützwerte mit zugehöriger Richtung im Blocktransfer.
Die Koordinatenübergabe-Variante 2 eignet sich nicht für Rekonstruktions-Algorithmen, bei denen die Koordinaten von aufeinanderfolgend an das VGR-ASIC übergebenen Stützwerten nicht in einem durch konstante Koordinaten inkremente DFX, DFY und DFZ beschreibbaren Zusammenhang stehen.

Die Funktionswerte der Stützwerte SP und die kartesischen Ko ordinaten (FX,FY,FZ) der Stützwerte SP bzw. die zugehörigen Aufsetzwerte werden über einen Datenbus A (siehe Fig. 3) in un terschiedliche Eingangspuffer des VGR-ASICs geschrieben. Für die Eingangspuffer wird ein FIFO-Prinzip empfohlen.

Die Betriebsart des VGR-ASICs (3D-Pre-Gridding oder 3D-Grid ding mit schrittweiser Gewichteinterpolation), die Interpola tionstabellen und die Parameter, die für den 3D-Gridding- Algorithmus und den 3D-Pre-Gridding-Algorithmus benötigt wer den, werden während einer Initialisierungsphase über den Da tenbus A geladen.

Zur Adressierung der unterschiedlichen Eingangspuffer und der Interpolationstabellenspeicher dient der Adreßbus ADR_A.

Über den bidirektionalen Datenbus B bildet das VGR-ASIC durch read-modify-write-Zugriffe Zuschläge auf Random-Daten mit der Adresse RAND des Speichers SKART, in dem sich der kartesische Frequenzkubus befindet. Die zugehörige Adresse RAND wird vom VGR-ASIC generiert und auf den Adreßbus ADR_B gelegt, über den der Speicher des kartesischen Frequenzkubus adressiert wird.

Über den bidirektionalen Datenbus C bildet das VGR-ASIC durch read-modify-write-Zugriffe Zuschläge auf Random-Daten mit der Adresse RANDG des Speichers SKARTG, in dem sich der kartesische Gewichtekubus befindet. Die zugehörige Adresse RANDG wird vom VGR-ASIC generiert und auf den Adreßbus ADR_C gelegt, über den der Speicher des kartesischen Gewichtekubus adressiert wird.

Die Fig. 4 zeigt eine Darstellung der Schnittstellen einer weiteren Version des VGR-ASICs, das ohne den Adreßbus ADR_A auskommt. In diesem Fall müßten die zu den Daten zugehörigen Adressen mit auf dem Datenbus A übertragen werden.

Abbildung der Rechenschritte auf die Komponenten des VGR- ASICS:
Die Abbildung der Rechenschritte auf die Komponenten des VGR- ASICs soll hier anhand des 3D-Gridding mit schrittweiser Ge wichteinterpolation dargestellt werden. Die Abbildung der Re chenschritte des 3D-Pre-Griddings läßt sich daraus wie folgt ableiten:
Die Rechenschritte <B1.< bis <B18.< entsprechen den Rechen schritten <D1.< bis <D18.< mit der jeweils gleichen Ziffer.
Der Rechenschritt <B19.< entspricht dem Rechenschritt <D26.<
Der Rechenschritt <B20.< entspricht dem Rechenschritt <D30.<
Der Rechenschritt <B21.< entspricht dem Rechenschritt <D32.<
Der Rechenschritt <B22.< entspricht dem Rechenschritt <D34.<
Der Rechenschritt <B23.< entspricht dem Rechenschritt <D36.<.

Auf dem Bus C ist gemäß dem Rechenschritt <D19.< eine Anzahl von NX . NY . NZ Zugriffen notwendig. Die Zugriffe auf dem Bus C können parallel zu den Zugriffen auf dem Bus B erfolgen.

Um die Anzahl der Zugriffe auf dem Bus B möglichst gering zu halten, wird über den Bus B parallel auf Real- und Imaginärteil des kartesischen Frequenzkubus zugegriffen.

Auf dem Bus B sind somit zur Bearbeitung einer Stützstelle SP insgesamt 2 . NX . NY . NZ Zugriffe notwendig. Diese setzen sich wie folgt zusammen:

a) Rechenschritt <D26.< und <D27.< parallel: 2 . NX . NY . NZ Zu griffe,
b) Rechenschritt <D36.< und <D37.< parallel: 2 . NX . NY . NZ Zu griffe.

Die Fig. 5 zeigt eine Darstellung der Funktionsblöcke des VGR- ASICs mit ausgewählten Datenpfaden. Die Rechenelemente (siehe Fig. 5) des VGR-ASICs werden in der Verarbeitungsleistung so ausgelegt, daß sämtliche Rechenschritte hinter den 2 . NX . NY . NZ Zugriffen auf dem Bus B versteckt werden.

Die Anzahl der Zugriffe auf dem Bus B bestimmt somit die Ver arbeitungsleistung des VGR-ASICs. Geht man davon aus, daß jeder Zugriff auf dem Bus B die Dauer eines Rechentaktes besitzt, hat das VGR-ASIC eine Verarbeitungsleistung von 2 . NX . NY . NZ Rechen takten zur Bearbeitung eines Stützwertes SP.

Im folgenden wird eine mögliche Aufteilung der Rechenschritte <D1.< bis <D37.< auf die in Fig. 5 dargestellten Funktions blöcke dargestellt. Dabei ist jeweils die Auslastung des Funk tionsblockes zur Bearbeitung einer Stützstelle SP in Form von Rechentakten angegeben.

Addierer AADD:
+ 1 Subtraktion von Rechenschritt <D1.<: 1 Rechentakt
+ 1 Subtraktion von Rechenschritt <D2.<: 1 Rechentakt
+ 1 Subtraktion von Rechenschritt <D3.<: 1 Rechentakt
+ 1 Subtraktion von Rechenschritt <D4.<: 1 Rechentakt
+ 1 Subtraktion von Rechenschritt <D5.<: 1 Rechentakt
+ 1 Subtraktion von Rechenschritt <D6.<: 1 Rechentakt
+ NX-1 Additionen von Rechenschritt <D7.<: NX-1 Rechentakte
+ NY-1 Additionen von Rechenschritt <D8.<: NY-1 Rechentakte
+ NZ-1 Additionen von Rechenschritt <D9.<: NZ-1 Rechentakte
+ NX Additionen von Rechenschritt <D13.<: NX Rechentakte
+ NY Additionen von Rechenschritt <D14.<: NY Rechentakte
+ NZ Additionen von Rechenschritt <D15.<: NZ Rechentakte

Anzahl von Rechentakten von Addierer AADD insgesamt:
2 . (NX+NY+NZ) + 3

Spezialarithmetik S:
+ 1 Rundung von Rechenschritt <D1.<: 1 Rechentakt
+ 1 Rundung von Rechenschritt <D2.<: 1 Rechentakt
+ 1 Rundung von Rechenschritt <D3.<: 1 Rechentakt
+ 1 Rundung von Rechenschritt <D7.<: 1 Rechentakt
+ 1 Rundung von Rechenschritt <D8.<: 1 Rechentakt
+ 1 Rundung von Rechenschritt <D9.<: 1 Rechentakt
+ 1 Multiplikation von Rechenschritt <D7.<: 1 Rechentakt
+ 1 Multiplikation von Rechenschritt <D8.<: 1 Rechentakt
+ 1 Multiplikation von Rechenschritt <D9.<: 1 Rechentakt
+ NX Modulo-Rechnungen von Rechenschritt <D16.<: NX Rechen takte
+ NY Modulo-Rechnungen von Rechenschritt <D17.<: NY Rechen takte
+ NZ Modulo-Rechnungen von Rechenschritt <D18.<: NY Rechen takte
+ 1 Multiplikation von Rechenschritt <D24.<: 1 Rechentakt
+ 1 Multiplikation von Rechenschritt <D25.<: 1 Rechentakt Anzahl von Rechentakten von Spezialarithmetik S insgesamt:
NX+NY+NZ + 11

Zugriff auf Interpolationstabellen INTTABL, INTTABK und INT- TABM:
+ NX Zugriffe von Rechenschritt <D10.<: NX Rechentakte
+ NY Zugriffe von Rechenschritt <D11.<: NY Rechentakte
+ NZ Zugriffe von Rechenschritt <D12.<: NZ Rechentakte

Anzahl von Rechentakten beim Zugriff auf die Interpolati onstabellen INTTABL, INTTABK und INTTABM insgesamt:
NX+NY+NZ

Multiplizierer MR:
+ NX Multiplikationen von Rechenschritt <D28.<: NX Rechen takte
+ NX . NY Multiplikationen von Rechenschritt <D30.<: NX . NY Re chentakte
+ NX . NY . NZ Multiplikationen von Rechenschritt <D32.<:
NX . NY . NZ Rechentakte

Anzahl von Rechentakten von Multiplizierer MR insgesamt:
NX + NX . NY + NX . NY . NZ

Multiplizierer MI:
+ NX Multiplikationen von Rechenschritt <D29.<: NX Rechen takte
+ NX . NY Multiplikationen von Rechenschritt <D31.<: NX . NY Re chentakte
+ NX . NY . NZ Multiplikationen von Rechenschritt <D33.<:
NX . NY . NZ Rechentakte

Anzahl von Rechentakten von Multiplizierer MI insgesamt:
NX + NX . NY + NX . NY . NZ
Addierer AR:
+ NX . NY . NZ Additionen von Rechenschritt <D34.<: NX . NY . NZ Re chentakte

Addierer AT:
+ NX . NY . NZ Additionen von Rechenschritt <D35.<: NX . NY . NZ Re chentakte

Multiplizierer IMUL:
+ NX . NY Multiplikationen von Rechenschritt <D20.<: NX . NY Re chentakte
+ NX . NY . NZ Multiplikationen von Rechenschritt <D21.<:
NX . NY . NZ Rechentakte

Anzahl von Rechentakten von Multiplizierer IMUL insgesamt:
NX . NY + NX . NY . NZ

Operator Op (kann eventuell entfallen, siehe Rechenschritt <D22.<):
NX . NY . NZ Operationen von Rechenschritt <D22.<: NX . NY . NZ Rechentakte

Multiplizierer GMUL:
NX . NY . NZ Multiplikationen von Rechenschritt <D23.<:
NX . NY . NZ Rechentakte

Addierer GADD:
NX . NY . NZ-1 Additionen von Rechenschritt <D23.<: NX . NY . NZ-1 Rechentakte.

Wie die Auslastung der einzelnen Funktionsblöcke für die Bear beitung von einer Stützstelle SP zeigt, ist im für die Praxis wichtigen Fall von NX<=2 und NY<=2 und NZ<=2 die Auslastung aller Funktionsblöcke kleiner als der Wert 2 . NX . NY . NZ, der sich durch die Rechentakte beim Zugriff auf den Bus B ergibt. Somit lassen sich alle Rechenschritte durch geeignete Verzahnung hin ter dem Zugriff auf den kartesischen Frequenzkubus verstecken. Es ergibt sich als Verarbeitungsleistung des VGR-ASICS die Dau er von 2 . NX . NY . NZ Rechentakten zur Bearbeitung einer Stütz stelle SP.

Das Steuerwerk SW
steuert die Schnittstellen des VGR-ASICs,
steuert den Ablauf der Berechnungen auf den Funktionsblöcken,
und übernimmt die Adreßgenerierung.

Die Architektur des in Fig. 5 dargestellten VGR-ASICs ist so ausgelegt, daß alle Berechnungen des VGR-ASICs hinter den Zu griffen auf den Speicher SKART versteckt werden können. Die Zu griffsbandbreite des VGR-ASICs auf den Speicher SKART des kar tesischen Frequenzkubus bestimmt somit die Verarbeitungslei stung des VGR-ASICs.

Die maximale Zugriffsbandbreite des VGR-ASICs auf den kartesi schen Frequenzkubus im Speicher SKART wird dann erreicht, wenn das VGR-ASIC das alleinige Zugriffsrecht auf den Speicher SKART besitzt. Dadurch werden die zeitaufwendigen unteilbaren Read- Modify-Write-Zugriffe und die notwendige Arbitrierung beim Zu griff auf den Speicher SKART umgangen, die sich beim Zugriff von mehreren Teilnehmern auf die Speicher SKART ergeben würden. Dies stellt einen wesentlichen Vorteil der Verwendung eines VGR-ASICs entsprechend Anspruch 2 gegenüber einer Realisierung des 3D-Gridding-Algorithmus mit einem Multiprozessor-System dar, bei dem sich mehrere Prozessoren das Zugriffsrecht auf den kartesischen Frequenzkubus im Speicher SKART teilen müßten. Wenn mehrere Teilnehmer Zugriff auf den Speicher SKART haben, nimmt die Zugriffsbandbreite auf den Speicher SKART wegen Ar bitrierungsaufwand ab.

Die zu bearbeitenden Stützstellen SP können bei der Gewichte interpolation und beim 3D-Gridding auf NE Einheiten En mit n=1 bis n=NE von VGR-ASICs Gn (laut Anspruch 2) mit zugehörigen Speichern SKART Sn und SKARTG SGn aufgeteilt werden.

Die Gewichteinterpolation und das 3D-Gridding kann somit auf den NE Einheiten En parallel abgearbeitet werden. Sobald die Gewichteinterpolation und das 3D-Gridding auf allen NE Einhei ten En abgeschlossen ist, kann der Zugriff von den VGR-ASICs Gn auf die Speicher Sn weggenommen werden. Dann kann einer an deren Additionseinheit ADD_S der Zugriff auf die Speicher Sn erteilt werden, die die kartesischen Frequenzkuben aller NE Speicher Sn addiert. Das Ergebnis dieser Addition ist der kar tesische Frequenzkubus, der durch Berücksichtigung von allen zu bearbeitenden Stützstellen SP entsteht.

Die Durchführung des 3D-Pre-Gridding wird in diesem Fall von der Einheit E1 mit allen zu bearbeitenden Stützstellen SP durchgeführt. Die in der Einheit E1 erhaltene kartesische Ge wichtematrix muß dann jedoch vom Speicher SKARTG SG1 vor der Durchführung der Gewichteinterpolation und des 3D-Gridding in die Speicher SKARTG SG2 bis SGNE der Einheiten E2 bis ENE ko piert werden.

Claims

1. Verfahren zur Gewichtung von random-verteilten Stütz stellen SP im Frequenzraum, um einen 3D-Gridding-Algorithmus für eine dreidimensionale Fourier-Rekonstruktion für einen Computertomographen anwenden zu können mit folgenden Schrit ten:

A) 3D-Pre-Gridding-Prozeß:
- a) Durchführung des 3D-Pre-Gridding-Prozesses, wobei für alle Stützstellen SP anstelle des tatsächlichen Funk tionswertes der Funktionswert 1.0 hergenommen wird, so daß das Ergebnis ein reeller Gewichtekubus FMG in ei nem kartesischen Raster ist, bei dem die Funktionswer te die Verteilungsinhomogenitäten der Stützstellen SP beschreiben.
- b) Bei diesem 3D-Pre-Gridding-Algorithmus trägt wie beim 3D-Gridding-Algorithmus jeder Punkt zu NX . NY . NZ Punk ten KR des kartesischen Gitters des kartesischen Ge wichtekubus FMG bei.
- c) Für das 3D-Pre-Gridding werden wie beim 3D-Gridding die Interpolationstabellen INTTABL (x), INTTABK (y) und INTTABM(z) verwendet, wobei x, y und z den Abstand zwi schen einem kartesischen Rasterpunkt KR und der Stütz stelle SP darstellen.
B) Gewichteinterpolation:
- a) Das Gewicht GEW für eine Stützstelle SP wird aus den NX . NY . NZ Punkten KRG des Gewichtekubus FMG ermittelt, die im dreidimensionalen Interpolationsfenster des 3D- Gridding-Prozesses liegen.
- b) Die Funktionswerte FKRG der Punkte KRG werden dazu durch eine Bewertungsfunktion BF in Funktionswerte FKRGK umgewandelt, wobei die Bewertungsfunktion BF da bei im wesentlichen eine Kehrwertbildung mit geeigne ter Begrenzung der Ausgangswerte leistet.
- c) Das Gewicht GEW wird aus den Funktionswerten FKRGK der Punkte KRG wie folgt bestimmt:
  Jeder Funktionswert FKRGK der Punkte KRG wird mit den entsprechenden Interpolationsgewichten INT- TABL(x) . INTTABK(y) . INTTABM(z) multipliziert, und die Ergebnisse werden aufaddiert.
  Das Endergebnis ist das Gewicht GEW x, y und z stellen den Abstand zwischen dem jeweiligen kartesischen Ra sterpunkt der Punkte KRG und der Stützstelle SP dar.

2. Computertomograph zur Durchführung des Verfahrens nach Anspruch 1, mit einem Rechner (6) zur Rekonstruktion eines Bil des aus den Meßdaten nach einer dreidimensionalen Fourier-Re konstruktionsmethode, bei dem ein spezielles Rechenwerk (VGR- ASIC) zur Bearbeitung des dreidimensionalen Gridding-Algorith mus gemäß A vorgesehen ist, das die Zuschlagsbildung der von den nicht im kartesischen Raster liegenden, random-verteilten Stützstellen SP herrührenden Beiträge auf den kartesischen Frequenzkubus bewirkt.

3. Computertomograph nach Anspruch 2, bei dem die Schnittstellen des VGR-ASICs sind:

A) Eingangsdatenbus A und zugehöriger Adreßbus ADR_A zur Übergabe von folgenden Daten an das VGR-ASIC:
- a) Betriebsmodus (3D-Pre-Gridding oder 3D-Gridding mit schrittweiser Gewichteinterpolation) während der Initialisierungsphase,
- b) Parametrierwerte, die zur Durchführung des dreidimen sionalen Gridding-Algorithmus durch das VGR-ASIC benö tigt werden,
- c) Funktionswerte der Stützwerte SP, deren Beitrag auf den kartesischen Frequenzkubus durch den dreidimensio nalen Gridding-Algorithmus bestimmt werden soll, und
- d) kartesische Koordinaten der i.a. nicht im kartesischen Raster liegenden Stützwerte SP oder von Aufsetzwerten zur selbständigen Generierung der kartesischen Koordi naten der Stützwerte SP durch das VGR-ASIC.
B) Bidirektionaler Datenbus B und zugehöriger Adreßbus ADR_B. Diese dienen zur Zuschlagsbildung der von den Stützstellen SP herrührenden Beiträge entsprechend Anspruch 2 auf den kartesischen Frequenzkubus.
C) Bidirektionaler Datenbus C und zugehöriger Adreßbus ADR_C. Diese dienen zur Zuschlagsbildung der von den Stützstellen SP herrührenden Beiträge entsprechend Anspruch 2 auf den kartesischen Gewichtekubus in einem Speicher SKARTG und zur Ge wichteinterpolation gemäß Anspruch 1 aus den Daten des kar tesischen Gewichtekubus im Speicher SKARTG.

4. Computertomograph nach Anspruch 3, bei dem sich der kartesische Frequenzkubus im Speicher SKART be findet, der an das VGR-ASIC über den Datenbus B und den Adreß bus ADR_B angeschlossen ist, wobei die im VGR-ASIC vorhandenen Rechenwerke so ausgelegt sind, daß alle Berechnungen, die das VGR-ASIC vornehmen muß, hinter den Zugriffen auf den Speicher SKART versteckt werden können und die Rechenleistung des VGR- ASICs so ausgelegt ist, daß die maximale Zugriffsbandbreite auf den Speicher SKART genutzt werden kann.

5. Computertomograph nach Anspruch 2, bei dem das Rechen werk aus einer parallelen Anordnung von mehreren VGR-ASICs mit jeweils zugehörigen Speichern SKART und SKARTG besteht, so daß durch Aufteilung der Stützstellen SP auf die VGR-ASICs die Zu schlagsbildung der von den Stützstellen SP herrührenden Bei träge auf den kartesischen Frequenzkubus durch parallele Abarbeitung beschleunigt werden kann.