DE3831428C2

DE3831428C2 -

Info

Publication number: DE3831428C2
Application number: DE3831428A
Authority: DE
Inventors: Hitoshi Utsunomiya Tochigi Jp Sato
Original assignee: Toshiba Corp
Current assignee: Toshiba Corp
Priority date: 1987-09-18
Filing date: 1988-09-15
Publication date: 1992-08-06
Also published as: US4947347A; JPH0528873B2; JPS6476374A; DE3831428A1

Description

Die Erfindung betrifft ein Verfahren und eine Vorrichtung zum Erzeugen einer Tiefenkarte gemäß dem Oberbegriff des Anspruchs 1 beziehungsweise dem Oberbegriff des Anspruchs 5.

Stehen aus einem bildgebenden Abtastverfahren, zum Beispiel aus einer Kernspinresonanz-Abtastung oder einer Röntgenstrahl-Abtastung, dreidimensionale Bilddaten zur Verfügung, so kann man mit diesen Bilddaten eine perspektivische oder pseudo-dreidimensionale Anzeige des abgetasteten Objekts bilden. Man kann beispielsweise vorab eine Blickrichtung festlegen und eine senkrecht zur Blickrichtung verlaufende Projektionsebene definieren, um jeweils die Entfernung von einem der Punkte der Projektionsebene zu dem - in Blickrichtung gesehen - nächsten Punkt der Oberfläche des Objekts zu ermitteln.

Die US 36 02 702 zeigt in Übereinstimmung mit dem Oberbegriff des Anspruchs 1 beziehungsweise des Anspruchs 5 ein Verfahren und eine Vorrichtung zum Erzeugen einer Tiefenkarte. Diese Tiefenkarte ist eine pseudo-dreidimensionale Anzeige eines dreidimensionalen Objekts. Bei diesem Stand der Technik werden die dreidimensionalen Bilddaten jeweils als Satz von Polygonen betrachtet, wobei jedes Polygon beispielsweise dargestellt wird durch einen Satz von Koordinatenwerten. Die Beziehung zwischen der Projektionsebene und dem dreidimensionalen Objekt wird innerhalb eines dreidimensionalen Raums berechnet anhand der Datensätze, die die einzelnen Polygone definieren. Anhand der so gewonnenen Beziehungen wird die Tiefe des Objekts, von der Projektionsebene aus gemessen, bestimmt. Dieser Vorgang ist einheitlich in dem Sinn, daß lediglich ein einziges spezielles Verfahren angewendet wird, um die einzelnen Datenwerte für die Tiefenkarte zu ermitteln.

Ändert man die Blickrichtung, um eine andere Ansicht des dreidimensionalen Objekts zu gewinnen, so muß der gesamte Berechnungsvorgang erneut durchgeführt werden.

Die Erzeugung einer Tiefenkarte mit Hilfe eines für allgemeine Zwecke verwendbaren Rechners (generell-purpose computer) nimmt üblicherweise beträchtliche Zeit in Anspruch. Um die Verarbeitungszeit herabzusetzen, werden üblicherweise speziell ausgelegte Prozessoren eingesetzt, die für die hier interessierende Art der Bildverarbeitung ausgelegt sind. Doch auch mit Hilfe derartiger Spezialprozessoren werden mehrere Sekunden für die Datenverarbeitung benötigt, so daß man von einer gewünschten Echtzeitverarbeitung weit entfernt ist.

Der Erfindung liegt die Aufgabe zugrunde, ein Verfahren und eine Vorrichtung zum Erzeugen einer Tiefenkarte anzugeben, wobei die Arbeitsgeschwindigkeit beträchtlich heraufgesetzt ist.

Diese Aufgabe wird durch die in den Ansprüchen angegebene Erfindung gelöst.

Im folgenden werden Ausführungsbeispiele der Erfindung anhand der Zeichnungen näher erläutert. Es zeigen:

Fig. 1 und 2 Diagramme zum Veranschaulichen des grundlegenden Prinzips einer Ausführungsform der Erfindung, und

Fig. 3 ein Blickdiagramm einer Einrichtung zum Erzeugen einer Tiefenkarte gemäß einer Ausführungsform der Erfindung entsprechend dem in Fig. 1 und 2 veranschaulichten Prinzip.

Fig. 1 und 2 veranschaulichen das der Erfindung zugrundeliegende Arbeitsprinzip.

Fig. 1 zeigt ein Objekt 13, eine dreidimensionale oder 3D- Zone 11, die das Objekt einschließt und bei der es sich z. B. um einen Kubus handelt, und eine Projektionsebene 12 für eine gewünschte Blickrichtung. Der Kubus 11 besitzt sechs Flächen C1 bis C6, wie aus Fig. 2 hervorgeht.

In den dargestellten 3D-Koordinaten (x, y, z) ist Ld eine Normale, gezogen von einem Punkt Ps (x, y, z) auf der Projektionsebene 12 in Richtung auf den Kubus 11, und C (x, y, z) ist der Kreuzungspunkt zwischen Ld und einer Seite C1 des Kubus 11. Zd soll der Abstand zwischen dem Punkt PS (x, y, z) und dem Punkt C (x, y, z) sein. Qs (x, y, z) sei der Kreuzungspunkt zwischen dem Objekt 13 und einer Linie Ld1, bei der es sich um eine Verlängerungslinie von C (x, y, z) aus handelt. Zc sei der Abstand zwischen C (x, y, z) und diesem Punkt Qs (x, y, z). In diesem Fall liegt das Objekt 13 auf der Linie Ld1, jedoch nicht auf Ld. Beim Erzeugen einer Tiefenkarte in 2D-Koordinaten (x′, y′) auf der Projektionsebene 12 wird also, wenn erst einmal die Blickrichtung (ϕ, R) festgelegt ist, der Abstand Z (x′, y′) zwischen Ps (x′, y′) auf der Projektionsebene 12 oder Ps (x, y, z) und Qs (x, y, z) folgendermaßen ausgedrückt:

Z (x′, y′) = (Länge von Ld) + (Länge von Ld1)
= Zd + Zc (1)

Das Obige gilt auch für den Fall, daß der Kreuzungspunkt zwischen der Normalen Ld von Ps (x, y, z) und dem Kubus 11 auf einer anderen Seite als C1 liegt (d. h. auf irgendeiner der Seiten C2 bis C6). Abhängig von der Blickrichtung (ϕ, R) existieren gleichzeitig mehr als ein Kreuzungspunkt C (x, y, z) auf der Projektionsebene 12 in bezug auf drei oder weniger Seiten C1 bis C6. Es gibt acht Typen von Kreuzungspunkten, die drei Seiten betreffen:

C1 (x, y, z), C5 (x, y, z), C 6 (x, y, z)
C1 (x, y, z), C2 (x, y, z), C3 (x, y, z),
C2 (x, y, z), C3 (x, y, z), C4 (x, y, z),
C4 (x, y, z), C5 (x, y, z), C6 (x, y, z),
C1 (x, y, z), C2 (x, y, z), C5 (x, y, z),
C1 (x, y, z), C3 (x, y, z), C6 (x, y, z),
C3 (x, y, z), C4 (x, y, z), C6 (x, y, z), und
C2 (x, y, z), C4 (x, y, z), C5 (x, y, z).

Bei zwei Seiten gibt es zwölf Typen von Kreuzungspunkten:

C1 (x, y, z), C2 (x, y, z),
C1 (x, y, z), C3 (x, y, z),
C1 (x, y, z), C5 (x, y, z),
C1 (x, y, z), C6 (x, y, z),
C2 (x, y, z), C3 (x, y, z),
C2 (x, y, z), C4 (x, y, z),
C2 (x, y, z), C5 (x, y, z),
C3 (x, y, z), C4 (x, y, z),
C3 (x, y, z), C6 (x, y, z),
C4 (x, y, z), C5 (x, y, z),
C4 (x, y, z), C6 (x, y, z), und
C5 (x, y, z), C6 (x, y, z).

Bei einer Seite gibt es sechs Typen von Kreuzungspunkten:

C1 (x, y, z),
C2 (x, y, z),
C3 (x, y, z),
C4 (x, y, z),
C5 (x, y, z), und
C6 (x, y, z).

Ist erst einmal die Blickrichtung (ϕ, R) bestimmt, so wird der Abstand Zd genau bestimmt, und außerdem wird der Kreuzungspunkt C (x, y, z) zwischen Zd und dem Kubus 11 bestimmt. In jedem der obigen Fälle braucht der Strahlverfolgungsprozeß nur für den Abstand Zc ausgeführt zu werden, und wenn der Wert Zc erhalten ist, erhält man den Abstand Z (x′, y′) aus der Gleichung (1).

Der Grund dafür, daß die Erzeugung einer Tiefenkarte in herkömmlichen Anlagen beträchtliche Zeit in Anspruch nimmt, besteht darin, daß sämtliche Abstände von der Projektionsebene 12 zu dem Objekt 13 ausschließlich auf der Grundlage eines Strahlverfolgungsalgorithmus erhalten werden, ohne daß unterschieden wird zwischen einem Bereich, in welchem das Objekt 13 vorhanden ist, und einem Bereich, wo das Objekt nicht vorhanden ist. Im Gegensatz dazu wird erfindungsgemäß der Strahlverfolgungsalgorithmus oder Strahlverlaufsalgorithmus nur bezüglich des Abstands Zc von einer Seite des Kubus 11 bis auf die Oberfläche des Objekts 13 durchgeführt, während der Abstand Zd zwischen der Projektionsebene 12 und dem Kubus 11 durch eine einfache Koordinatenberechnung ermittelt werden kann. Deshalb läßt sich eine Tiefenkarte mit hoher Geschwindigkeit erstellen.

Im folgenden soll eine Vorrichtung zum Erzeugen einer Tiefenkarte gemäß der Erfindung beschrieben werden.

Wie in Fig. 3 gezeigt ist, enthält die Vorrichtung zum Erzeugen einer Tiefenkarte gemäß der Erfindung einen 3D- Adreßgenerator 1, einen Bilddatenspeicher 2, einen Detektor 3, einen Zähler 4, einen Tiefenkarten-Speicher 5, einen 2D- Adreßgenerator 6, einen Addierer 7, einen Zd-Speicher 8 und eine Arithmetisch-Logische-Einheit (ALU) 9. Der Adreßgenerator 1, der Detektor 3 und der Zähler 4 bilden einen Strahlverfolgungsprozessor 10.

Der Bilddatenspeicher 2 speichert 3D-Bilddaten, die aus einer Anzahl benachbarter Schichtbilder oder Voxels eines Zielkörpers bestehen und die von einem bildgebenden Gerät bereitgestellt werden, z. B. von einem Röntgenstrahl-CT- Gerät oder einem Kernspinresonanz-Gerät, wobei die Daten in Form binärer Daten "0" oder "1" vorliegen, abhängig davon, ob ein Objekt vorhanden ist oder nicht. Die 3D-Bilddaten, die normalerweise aus Gradationsdaten für jedes Voxel bestehen, werden mit einem gegebenen Gradationswert als Schwellenwert in Binärdaten umgesetzt. Der 3D-Adreßgenerator 1 erzeugt eine 3D-Adresse zum Auslesen der Inhalte des Bilddatenspeichers 2. Der Zähler 4 zählt ein Taktimpulssignal CPO, und der Detektor 3 gibt ein Signal zum Anhalten des Zählvorgangs des Zählers 4 aus, wenn die aus dem Bilddatenspeicher 2 ausgelesenen Daten den Wert "1" annehmen. Der aus dem Adreßgenerator 1, dem Detektor 3 und dem Zähler 4 bestehende Strahlverfolgungsprozessor ermittelt den Abstand Zc zwischen einer Seite der 3D-Zone (z. B. des Kubus) 11, welche zum Einschließen des Objekts 13 eingestellt wurde, und der Oberfläche des Objekts 13 (siehe Fig. 1).

Die ALU 9 führt eine Koordinatenberechnung durch, um den Abstand Zd zwischen der Oberfläche des Kubus 11 und der Projektionsebene 12 zu berechnen, die durch die Blickrichtung (ϕ, R) vorgegeben ist. Der berechnete Abstand Zd wird dann in den Zd-Speicher 8 eingeschrieben. Der Zd-Wert im Speicher 8 kann mit Hilfe des Adreßdatenwerts D (x′, Y′) entsprechend den 2D-Koordinaten (x′, y′) auf der Projektionsebene 12 ausgelesen werden.

Der Addierer 7 addiert das Zähler-Ausgangssignal Zc des Zählers 4 und das Ausgangssignal Zd des Zd-Speichers 8. D. h.: Der Addierer 7 führt die Berechnung gemäß Gleichung (1) durch. Der Ausgangswert Z (x′, y′) des Addierers 7 wird dann in den Tiefenkarten-Speicher 5 eingeschrieben; eine Schreibadresse für diesen Speicher 5 wird von dem 2D-Adreßgenerator 6 in Form von 2D-Koordinaten (x′, y′) erzeugt. Der Zähler 4, der mit einem Maximumwert voreingestellt ist, der genügend größer ist als Z (x′, y′) für das Objekt 13, beendet den Zählvorgang, wenn der Detektor 3 auch dann keine "1" feststellt, wenn der Zählerstand den Maximalwert erreicht hat, und dann wird der Maximalwert direkt (ohne über den Addierer 7 zu laufen) in den Tiefenkarten-Speicher 5 eingeschrieben.

Mit der oben beschriebenen Ausgestaltung der Vorrichtung wird, wenn einmal die Blickrichtung (ϕ, R) bestimmt ist, der von der ALU 9 erhaltene Abstand Zd in den Zd-Speicher 8 entsprechend 2D-Koordinaten (x′, y′) eingeschrieben, um so eine Zd-Tabelle im Speicher 8 zu erstellen. Da in dem Raum zwischen der Oberfläche des Kubus 11 und der Projektionsebene 12 kein Teil des Objekts vorhanden ist, läßt sich die Zd-Tabelle mit hoher Geschwindigkeit und durch einfache Koordinatenberechnung erstellen, ohne daß dazu ein Strahlverfolgungsalgorithmus notwendig wäre.

Der 3D-Adreßgenerator 1 arbeitet synchron mit dem Taktimpulssignal CPO. Mit Cs (x, y, z) als Startadresse des Anfangswertes und v (Δx, Δy, Δz) als 3D-Vektorkomponente (Einheitsvektor) in Blickrichtung läßt sich der Ausgangswert (x, y, z) des 3D-Adreßgenerators 1 wie folgt ausdrücken:

R (x, y, z) = Cs (x, y, z) + n, v (Δx, Δy, Δz) (2)

wobei Cs (x, y, z), v (Δx, Δy, Δz) und R (x, y, z) Binärdaten und n eine natürliche Zahl entsprechend der wiederholten Anzahl von Taktimpulsen CPO ist.

Die Koordinaten (X, Y, Z) des Bilddatenspeichers 2 entsprechend R (x, y, z) lassen sich wie folgt ausdrücken:

X = Cs (x) + nΔx,
Y = Cs (y) + nΔy, und
Z = Cs (z) + nΔz

wobei Cs (x), Cs (y) und Cs (z) die x-, y- und z-Koordinaten der Startadresse sind.

Daten werden aus dem Bilddatenspeicher 2 durch den 3D- Adreßgenerator 1 ausgelesen. Wenn der ausgelesene Datenwert "1" ist (was bedeutet, daß das Objekt erreicht ist), gibt der Detektor 3 ein Zähl-Sperrsignal aus, das den Zähler 4 veranlaßt, mit dem Zählen des Taktimpulssignals CPO aufzuhören. Der Abstand zwischen C (x, y, z) und Qs (x, y, z) wird folgendermaßen ausgedrückt:

Auf der Grundlage der 2D-Adresse D (x′, y′) entsprechend den 2D-Koordinaten (x′, y′) der Projektionsebene 12 wird der zugehörige Wert Zd aus dem Zd-Speicher 8 ausgelesen und im Addierer 7 auf das Ausgangssignal Zc des Zählers 4 addiert, und das Ergebnis wird in den Tiefenkarten-Speicher 5 eingeschrieben. Wird von dem Detektor 3 keine "1" festgestellt, so wird, wie oben erwähnt wurde, der vorgegebene Maximalwert in den Tiefenkarten-Speicher eingeschrieben. Der oben beschriebene Vorgang wird für jeden Punkt Ps (x′, y′) = Ps (x, y, z) auf der Projektionsebene 12 durchgeführt, um so eine Tiefenkarte auf der Projektionsebene 12 in dem Tiefenkarten-Speicher 5 zu erstellen.

Überflüssig zu sagen, daß die Erfindung in keiner Weise auf das oben beschriebene Ausführungsbeispiel beschränkt ist, sondern zahlreiche Modifikationen möglich sind.

Beispielsweise kann es sich bei der das Objekt 13 einschließenden 3D-Zone 12 um ein Parallelepiped, eine Kombination aus mehreren benachbarten Kuben, anderen mehrflächigen Körpern oder aus einer Kugel und einem Kubus handeln. Da es effizient ist, die das Objekt 13 einschließende 3D- Zone so klein wie möglich einzustellen, ist es wünschenswert, daß die 3D-Zone das Objekt 13 umschreibt. Das Einstellen der 3D-Zone und die Berechnung seitens der ALU 9 können dadurch erleichtert werden, daß man aus 3D-Zonen unterschiedlicher und vorbestimmter Größen solche auswählt, die das Objekt 13 passend umschließen. Der im Zähler 4 für den Fall eingestellte Maximalwert, daß das Detektorsignal des Detektors 3 nicht eintrifft oder die Linie der Strahlverfolgung nicht das Objekt kreuzt, läßt sich bestimmen durch die Koordinaten der Rückseite der 3D-Zone. Wenn der Zählerstand den Maximalwert übersteigt, wird ein einem voreingestellten Hintergrund entsprechender Wert in den Tiefenkarten- Speicher 5 eingeschrieben.

Claims

1. Verfahren zum Erzeugen einer Tiefenkarte, bei dem Voxel-Daten für ein dreidimensionales Objekt gespeichert werden, und zur Erzeugung einer zweidimensionalen Darstellung des Objekts eine gewünschte Blickrichtung festgelegt wird, bevor die Entfernungen zwischen allen der Blickrichtung entsprechenden Punkten auf der Objektoberfläche und einer senkrecht zur Blickrichtung verlaufenden Projektionsebene ermittelt werden, dadurch gekennzeichnet, daß eine das Objekt umhüllende, dreidimensionale Zone festgelegt wird,
erste Abstände zwischen der Projektionsebene und der Oberfläche der Zone durch Koordinatenberechnung bestimmt werden,
zweite Abstände zwischen der Oberfläche der Zone und der Oberfläche des Objekts mittels Strahlverfolgungsalgorithmus bestimmt werden, und
für jedes Bildelement die ersten und die zweiten Abstände addiert werden.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß die dreidimensionale Zone als ein das Objekt einschließendes Parallelepiped gebildet wird.

3. Verfahren nach Anspruch 1, bei dem die dreidimensionale Zone als ein das Objekt einschließender Kubus gebildet wird.

4. Verfahren nach Anspruch 1, bei dem die dreidimensionale Zone als eine das Objekt einschließende Kugel gebildet wird.

5. Vorrichtung zum Erzeugen einer Tiefenkarte, umfassend:
eine Bilddaten-Speichereinrichtung (2) zum Speichern von Voxel-Daten, die repräsentativ für ein dreidimensionales Objekt sind,
eine Verarbeitungseinrichtung, die Entfernungen ermittelt zwischen allen Punkten auf der Oberfläche des dreidimensionalen Objekts einerseits und einer Projektionsebene, die senkrecht zu einer gewünschten Blickrichtung verläuft, um eine Tiefenkarte zu erzeugen, welche die zweidimensionale Verteilung der Abstände zwischen der Projektionsebene und einer Oberfläche des dreidimensionalen Objekts repräsentiert, und
einen Tiefenkarten-Speicher (5) zum Speichern der Tiefenkarte, dadurch gekennzeichnet, daß die Verarbeitungseinrichtung aufweist:
eine Einrichtung zum Bestimmen einer dreidimensionalen Zone, welche das dreidimensionale Objekt umschließt, wodurch die Abstände jeweils unterteilt werden in einen ersten Abschnitt, der zwischen der Projektionsebene und der Oberfläche der dreidimensionalen Zone liegt, und einen zweiten Abschnitt, der definiert ist zwischen der Oberfläche der dreidimensionalen Zone und der Oberfläche des dreidimensionalen Objekts,
eine erste Einrichtung (8, 9) zum Bestimmen einer Länge des ersten Abschnitts zd durch Koordinatenberechnung bezüglich jedes Bildelementes auf der Projektionsebene,
eine zweite Einrichtung (10) zum Bestimmen einer Länge des zweiten Abschnitts zc durch Strahlverfolgung in Bezug auf jedes Bildelement auf der Projektionsebene, und eine Addiereinrichtung (7), die die Längen des ersten und des zweiten Abschnitts für jedes Bildelement addiert und die sich daraus ergebenden Daten in den Tiefenkarten-Speicher (5) einschreibt.

6. Vorrichtung nach Anspruch 5, dadurch gekennzeichnet, daß die zweite Einrichtung (10) eine Einrichtung enthält, die einen gegebenen Abstandswert für ein Bildelement der Tiefenkarte unter Verzicht auf eine Verarbeitung seitens der Addiereinrichtung einschreibt, wenn das Objekt in einem gegebenen Umfang der Strahlverfolgung nicht erreicht wird.

7. Vorrichtung nach Anspruch 6, dadurch gekennzeichnet, daß die zweite Einrichtung (10) den gegebenen Bereich der Strahlverfolgung nach Maßgabe der Lage einer Rückseite der von der Einrichtung zum Bestimmen einer dreidimensionalen Zone eingestellten Zone bestimmt.