DE60310226T2

DE60310226T2 - Verfahren zur linearen raumabtastung und vorrichtung zur erzeugung eines numerischen 3d modells

Info

Publication number: DE60310226T2
Application number: DE60310226T
Authority: DE
Inventors: Ali Potomac FARSAIE
Original assignee: Spatial Integrated Systems Inc
Current assignee: Spatial Integrated Systems Inc
Priority date: 2002-06-12
Filing date: 2003-06-12
Publication date: 2007-10-04
Anticipated expiration: 2023-06-13
Also published as: WO2003107276A2; WO2003107276A3; AU2003245483A1; US20040027347A1; ATE347722T1; US7257249B2; DE60310226D1; EP1522051B1; EP1522051A2; AU2003245483A8

Description

HINTERGRUND DER ERFINDUNG
Diese Erfindung bezieht sich allgemein auf die Bilderzeugung und insbesondere auf ein Verfahren und auf eine Vorrichtung zum Verwenden einer bewegten Kamera oder einer festen Sensormatrix für die 3-dimensionale Abtastung eines Objekts.
In vielen Computeranwendungen ist es erwünscht, die Fähigkeit zu haben, eine Datei zu erzeugen, die ein dreidimensionales Objekt beschreibt. Zum Beispiel ist es für die Zurückentwicklung eines mechanischen Teils, für das keine Zeichnungen mehr verfügbar sind, erwünscht, effizient und genau eine digitale Datei erzeugen zu können, die das Teil beschreibt. Ein Verfahren ist das Abtasten des Teils mit einem 3D-Scanner wie etwa mit einer Laserabtastvorrichtung, der/die daraus ein digitales Modell erzeugt. Die Modelle können daraufhin unter Verwendung computergestützter Entwicklungsverarbeitungstechniken/computergestützter Fertigungsverarbeitungstechniken (CAD/CAM-Verarbeitungstechniken) manipuliert werden, um das gewünschte Teil zu reproduzieren. 3D-Scanner werden in einer Vielzahl von Gebieten einschließlich medizinischer Bilderzeugung, Topographie, computergestützter Entwicklung/computergestützter Fertigung (CAD/CAM), Architektur, Rückentwicklung und Computeranimation/Virtual Reality verwendet.
Frühe 3D-Scanner verwendeten mechanische Sonden, die sich über die Oberfläche eines Objekts bewegten. Ein mit der Sonde verbundener mechanischer Arm bewegt sich in Übereinstimmung mit den Umrissen der Oberfläche, und die Armbewegungen werden in Informationen übersetzt, die den Ort der Sonde an mehreren Punkten beschreiben. Diese frühen digitalen Systeme sind langsam, da sie jede Position an dem Objekt, an dem eine Messablesung genommen wird, berühren müssen, und zum Scannen weicher Objekte wie etwa Lehm ungeeignet. Ferner sind sie für die Modellierung großer 3D-Räume oder -Szenen wie etwa des Innern eines Zimmers oder Gebäudes ungeeignet.
In jüngerer Zeit sind optische 3D-Scanner verfügbar geworden. 3D-Scanner dieser Art projizieren auf das Objekt ein Lasermuster und bestimmen unter Verwen dung von Triangulationstechniken den Ort von Punkten auf dem Objekt. Diese Systeme können äußerst kompliziert und somit kostspielig sein. Ferner sind Lasersysteme auf eine monochromatische Lichtquelle beschränkt, was ihre Nützlichkeit beschränkt. Nochmals weiter können einige Materialien bei der Frequenz des Lasers durchsichtig oder durchlässig sein, was ihre Nützlichkeit weiter beschränkt.
EP-A-1 100 048 offenbart ein Verfahren, in dem ein Paar stereoskopischer Bilder aufgenommen wird, wobei die stereoskopische Kamera in einem ersten Schritt kalibriert wird. Darüber hinaus ist aus dem Artikel "A cooperative algorithm for stereo matching and occlusion detection" (XP-000976495) ein stereoskopischer Anpassungsalgorithmus bekannt.
ZUSAMMENFASSUNG DER ERFINDUNG
Es ist die Hauptaufgabe der vorliegenden Erfindung, ein Objekt- und Raumabtastverfahren und eine Objekt- und Raumabtastvorrichtung zu schaffen, die die oben beschriebenen Beschränkungen überwinden.
Es ist eine weitere Aufgabe der vorliegenden Erfindung, ein genaues Objektmodellierungsverfahren und eine genaue Objektmodellierungsvorrichtung zu schaffen, die multispektral sind, Modelle von Nachtszenen liefern können und Farbmodelle liefern können.
Es ist eine weitere Aufgabe der vorliegenden Erfindung, ein genaues Objektmodellierungsverfahren und eine genaue Objektmodellierungsvorrichtung zu schaffen, die ein Minimum an menschlichem Eingriff und menschlicher Einstellung erfordern.
In Übereinstimmung mit der vorliegenden Erfindung werden die obigen Aufgaben durch das Verfahren gemäß Anspruch 1 gelöst. In den Unteransprüchen sind bevorzugte Ausführungsformen angegeben.
KURZBESCHREIBUNG DER ZEICHNUNG
Die Erfindung kann in bestimmten Teilen und Anordnungen der Teile eine physikalische Form annehmen, von der eine bevorzugte Ausführungsform ausführlich in der Beschreibung beschrieben wird und in der beigefügten Zeichnung veranschaulicht ist, die einen Teil davon bildet und in der:
1 ein Ablaufplan ist, der ein bevorzugtes Verfahren der 3D-Modellierung in Übereinstimmung mit Aspekten der vorliegenden Erfindung veranschaulicht.
2 ein Diagramm ist, das eine Parallaxe von zwei Beobachterorten veranschaulicht.
3 eine gemeinsame Menge aus 3 Punkten von zwei Bildsensororten zeigt.
4 zwei Koordinatensysteme vor einer Folge von Operationen zum Ausrichten der Koordinatensysteme zeigt.
5 ein Marching-Cubes-Verfahren veranschaulicht, das zur Verwirklichung von Aspekten der vorliegenden Erfindung geeignet ist.
6 einen Würfel mit einem Eckpunkt innerhalb des Objekts, das modelliert wird, zeigt.
7 einen Würfel mit drei Eckpunkten innerhalb des Objekts, das modelliert wird, zeigt.
8 eine Vorderansicht des Würfels in 7 ist.
9 einen Würfel mit vier Eckpunkten innerhalb des Objekts, das modelliert wird, zeigt.
10 die 15 Fälle von Würfeln gemäß Aspekten der vorliegenden Erfindung zeigt.
11 eine schematische Darstellung eines an einem Schieber gemäß einer Ausführungsform angebrachten Bildsensors ist, der geeignet ist, Aspekte der vorliegenden Erfindung zu verwirklichen.
12 eine Matrix horizontaler Querschnitte von Farbbildern veranschaulicht, die in Übereinstimmung mit einer beispielhaften Ausführungsform der vorliegenden Erfindung erhalten und verarbeitet wurden.
13 einen nahen Punkt und einen fernen Punkt eines Objekts, das modelliert wird, und die entsprechenden horizontalen Querschnittsbilder gemäß 12 zeigt.
14 einen komplizierteren horizontalen Querschnitt zeigt, als er in 13 gezeigt ist.
15 eine Pixelzeile von einem Zentrumsbild von Farbbildern zeigt, die in Übereinstimmung mit einer beispielhaften Ausführungsform der vorliegenden Erfindung erhalten und verarbeitet wurden.
16 eine Farbvarianzgrenze für den Querschnitt aus 15 zeigt.
17 eine Matrix horizontaler Querschnitte von Graustufenbildern veranschaulicht, die in Übereinstimmung mit einer beispielhaften Ausführungsform der vorliegenden Erfindung erhalten und verarbeitet wurden.
18 ein beispielhafter horizontaler Querschnitt von 17 ist.
19 eine Punktwolkenabbildung eines beispielhaften Objekts in Übereinstimmung mit Aspekten der vorliegenden Erfindung zeigt.
20 ein Dreiecksgitter eines beispielhaften Objekts in Übereinstimmung mit Aspekten der vorliegenden Erfindung zeigt.
21 ein photorealistisches Bild eines beispielhaften Objekts in Übereinstimmung mit Aspekten der vorliegenden Erfindung zeigt.
22 einen Einzelsensor-Bilderzeuger mit einer auf einer Bahn beweglichen Kamera zeigt, der für eine Ausführungsform der vorliegenden Erfindung geeignet ist.
23 einen Mehrsensor-Bilderzeuger zeigt, der für eine weitere Ausführungsform der vorliegenden Erfindung geeignet ist.
24 einen Schwenk- und Neigekopfbilderzeuger zeigt, der für eine nochmals weitere Ausführungsform der vorliegenden Erfindung geeignet ist.
25 einen alternativen Bilderzeuger mit einer Matrix fester Sensoren zeigt, der für eine nochmals weitere Ausführungsform der vorliegenden Erfindung geeignet ist.
26 ein Betrachtungs- und Bilderzeugungshilfsmittelfenster gemäß einer Ausführungsform zeigt, die für die Verwirklichung von Aspekten der vorliegenden Erfindung geeignet ist.
AUSFÜHRLICHE BESCHREIBUNG DER BEVORZUGTEN AUSFÜHRUNGSFORM
Aus der folgenden Diskussion wird offensichtlich, dass die hier dargelegten Ausführungsformen der vorliegenden Erfindung zur Verwendung in einer weiten Vielfalt von Objektmodellierungssystemen geeignet sind und ihre Anwendung nicht notwendig auf die veranschaulichten besonderen Systeme beschränkt ist.
Anhand der Zeichnung, in der die Darstellungen zur Veranschaulichung beispielhafter Ausführungsformen der Erfindung und nicht zu deren Beschränkung dienen, ist ein Ziel einer diskreten linearen Raumabtasttechnik (DLSS-Technik) in Übereinstimmung mit Aspekten der vorliegenden Erfindung der Bau eines räumlich genauen photorealistischen Modells eines 3D-Raums. Anhand von 1 wird ein beispielhafter Prozess 10 verwendet, um die photorealistischen Modelle zu bauen. Wie gezeigt ist, besitzt der Prozess 10 mehrere unterscheidbare Schritte wie folgt:
1. Datenerfassung
Unter Verwendung von Bildsensoren werden geeignete Objekt- oder Szenedaten erfasst (12), um digitale Bilder des Objekts oder der Szene zu sammeln.
2. Erzeugung von 3D-Punkten
Aus den digitalen Bildern werden mittels des DLSS-Systems und -Prozesses 3D-Koordinaten erzeugt (14). Zum Beispiel erzeugen das DLSS-System und der DLSS-Prozess durch Analysieren der Daten von einem Sensor, der sich entlang einer horizontalen Basis bewegt, eine Stereosehzone.
3. Ausrichten der 3D-Punkte
Das DLSS-System richtet die Punkte aus und filtert optional automatisch ohne Eingabe von dem Anwender verrauschte oder überflüssige Daten (16).
4. Triangulation
Das DLSS-System baut aus den Daten, die es sammelt, automatisch ein Dreiecksgitter (18).
5. Texturerzeugung
Das DLSS-System klebt automatisch eine Textur (20) von den gesammelten digitalen Bildern auf das 3D-Dreieckgittermodell und erzeugt dadurch ein photorealistisches 3D-Modell des Objekts oder der Szene.
In der folgenden Beschreibung wird eine ausführliche Diskussion eines beispielhaften DLSS-Systems und -Verfahrens gegeben. Zur Klarheit und Vollständigkeit ist die Beschreibung wie folgt in mehrere Unterabschnitte unterteilt:

1. DLSS-Theorie liefert die mathematische Grundlage für die DLSS.
2. Digitaldatenerfassung beschreibt, wie digitale Bildsensoren verwendet werden, um die Szene oder das Objekt zu erfassen, die/das modelliert wird.
3. Erzeugen von 3d-Spels beschreibt, wie die digitalen Bilder als Eingabe verwendet werden, sodass eine Wolke dreidimensionaler Punkte erzeugt werden kann. In der DLSS-Terminologie werden diese Punkte 3d-Spels (dreidimensionale räumliche Elemente) genannt. Diese 3d-Spels bilden ein Punktwolkenmodell des Objekts oder des Raums, das/der modelliert wird.
4. Punktausrichtung beschreibt, wie die 3d-Spels von einem oder von mehreren Bildsensororten korreliert und ausgerichtet werden.
5 Triangulation und Gittererzeugung beschreibt, wie ein dreieckiges Gitter des Objekts oder des Raums erzeugt wird, nachdem die 3d-Spels erzeugt worden sind. Es wird gezeigt, wie die 3d-Spels als Eckpunkte von Dreiecken verwendet werden, die ein Dreiecksgitter des Objekts oder der Szene bilden, das/die modelliert wird.
6. Texturabbildung beschreibt, wie die Textur von der Originalmenge von Bildern identifiziert und auf die Dreiecke in dem Dreiecksgitter "geklebt" wird. In diesem letzten Schritt des 3D-Modellbaus beginnt der Prozess mit dem Gitter und endet mit einem photorealistischen, räumlich genauen Modell des 3D-Objekts oder der 3D-Szene.

1. DLSS-Theorie
In diesem Abschnitt wird eine Diskussion einiger mathematischer Techniken dargestellt, die bei der Erzeugung eines 3D-Modells durch DLSS verwendet werden. Im Wesentlichen beschreibt dieser Abschnitt, wie:

1. unter Verwendung digitaler Bilder räumliche 3D-Koordinaten berechnet werden;
2. Mengen von 3d-Spels in Bezug auf einen gemeinsamen Ursprung ausgerichtet und angezeigt werden;
3. die 3d-Spels so angeordnet werden, dass sie ein dreieckiges Gitter des Raums bilden; und
4. die von den ursprünglichen Bildern erhaltene Textur auf das dreieckige Gitter geklebt wird.

Eine Parallaxe, wie sie hier verwendet wird, ist die Änderung der scheinbaren Position eines Objekts wegen einer Verschiebung der Position eines Beobachters. Die Parallaxe wird allgemein verwendet, um die Entfernungen von Sternen zu ermitteln und um große Entfernungen auf der Erde zu ermitteln, die zu schwierig direkt zu messen sind.
Das "Objekt" ist in der DLSS-Terminologie ein Punkt im Raum. Die zwei Positionen des Beobachters sind einfach zwei Bildsensorpositionen, die eine bekannte Strecke entfernt sind. Zum Beispiel umfasst der Bildsensor optional eine Digitalkamera, die, wie im Gebiet bekannt ist, eine CCD, eine Linse usw. enthält. Alternativ umfasst der Bildsensor eine feste lineare Matrix von Sensoren. Obgleich die verschiedenen Ausführungsformen der vorliegenden Erfindung in Bezug auf bewegliche Kameras diskutiert werden, ist klar, dass feste Matrizen von Sensoren ebenfalls geeignet an den Umfang der vorliegenden Erfindung angepasst werden und in ihm enthalten sind. Diese Anordnung ist in 2 gezeigt. F (22) ist hier die Brennweite der Linse und B (24) die Strecke zwischen den Mitten der zwei Bildsensoren bei den zwei Bildsensorpositionen. Die tatsächlichen Brennpunkte der Bildsensorlinsen sind mit Brennpunkt 1 (26) bzw. Brennpunkt 2 (28) bezeichnet. C1 (30) ist die x-Strecke von der Mitte des Bildsensors 1 zu dem Pixel 32, wo der Punkt erfasst wird. C2 (34) ist ähnlich für den Bildsensor 2 in Bezug auf sein entsprechendes erfasstes Pixel 36 definiert. C1 (30) und C2 (34) werden in der DLSS dadurch erhalten, dass die Pixelbreite mit der Anzahl oder mit den Pixeln, die der Bildpunkt von der Mitte der CCD des jeweiligen Bildsensors versetzt ist, multipliziert wird. D (38) ist die Strecke (z-Koordinate) zu dem Punkt (40) im Raum.
Unter Verwendung ähnlicher Dreiecke ist zu sehen, dass D/F = (B + C1 + C2)/(C1 + C2)und, wenn P als P = (C1 + C2) definiert wird, D/F = (B + P)/Pist.
Umstellen der Terme liefert D = F·(B + P)/P. Gleichung 1.1.1
Es wird angemerkt, dass D tatsächlich die z-Koordinate des Punkts im Raum in Bezug auf einen Ursprung 42 ist, der sich in 2 bei O befindet. Somit kann Gleichung 1 als z = F·(B + P)/P Gleichung 1.1.1ageschrieben werden.
Ähnlich können Ausdrücke für die x- und für die y-Koordinate des Punkts im Raum ermittelt werden. Yoffset bezeichne die tatsächliche Strecke, die das Bild des Punkts von der Mitte jedes Bildsensors versetzt ist. Dann ist x = z·C1/F Gleichung 1.1.2 y = z·Yoffset/F. Gleichung 1.1.3
Aus der obigen Diskussion ist klar, dass dann, wenn sichergestellt ist, dass von den zwei Bildsensorpositionen derselbe Punkt lokalisiert wurde, die räumlichen Koordinaten des Punkts und somit ein 3d-Spel zuverlässig berechnet werden können. Es werden hier mehrere Verfahren gemäß der vorliegenden Erfindung beschrieben, um sicherzustellen, dass ein solcher Punkt lokalisiert worden ist.
Häufig ist es vorteilhaft, mehr als einen Bildsensor oder mehr als einen Bildsensorort zu verwenden, um ein Objekt oder eine Szene genau zu modellieren. In der DLSS werden die verschiedenen Bildsensororte vorzugsweise auf eine von zwei Arten erhalten:

1. (Fall A) Anwendung bekannter Transformationen auf die Bildsensorposition. Eine Transformation, wie sie hier verwendet wird, bedeutet, dass ein Bildsensorort aus einem anderen durch eine bekannte Translation und/oder durch eine bekannte Drehung erhalten wird; oder
2. (Fall B) Anwendung unbekannter Transformationen auf die Bildsensorposition.

Die von verschiedenen Bildsensororten erzeugten 3d-Spels sollten genaue 3D-Koordinaten haben, wobei diese Koordinaten aber in Bezug auf verschiedene Ursprünge sind. Somit werden Mengen von 3d-Spels zu einer einzelnen Menge mit einem gemeinsamen Ursprung kombiniert. Falls die 3d-Spels wie oben im Fall A erzeugt werden, werden die 3d-Spels durch Anwenden der inversen Transformation in ein gemeinsames Koordinatensystem transformiert. Für den obigen Fall B werden die 3d-Spels unter Verwendung von Euler-Winkeln auf einen gemeinsamen Ursprung ausgerichtet.
Für den Fall A werden lineare Transformationen (LT) verwendet, um einen Vektorraum auf einen anderen abzubilden. Lineare Transformationen erfüllen zwei Eigenschaften:

1) T(a + b) = T(a) + T(b) für alle Vektoren a und b
2) T(☐b) = ☐T(b) für irgendeinen Skalar ☐ und irgendeinen Vektor b.

Es gibt ein Theorem aus der linearen Algebra, dass eine LT von einem endlich dimensionalen Vektor auf einen anderen eine Matrixdarstellung besitzt. Falls T eine LT von einem Vektorraum (z. B. X) mit der Dimension m auf einen anderen Vektorraum (z. B. Y) mit der Dimension n ist, gibt es somit eine Matrix A der Größe m × n, sodass T(a) = Aa ist.
Außerdem ist gut bekannt, dass die durch die Matrix A dargestellte Transformation dann und nur dann invertierbar ist, wenn A invertierbar ist. Darüber hinaus ist die Matrixdarstellung der Inversen von T durch A^–1 gegeben.
Eine affine Transformation ist eine solche der drei Grundoperationen der Drehung, der Skalierung und der Translation. Falls diese Operationen als Abbildung des 3-Raums (3-dimensionalen Raums) auf den 3-Raum betrachtet werden, gibt es keine bekannte Matrixdarstellung für die Translation, da sie die zweite Eigenschaft von LTs nicht erfüllt.
Um dies zu beheben, werden homogene Koordinaten verwendet. Um diese Koordinaten zu bilden, wird ein Punkt (x, y, z) im 3-Raum mit dem Punkt (x, y, z, 1) im 4-Raum identifiziert. Unter Verwendung dieser Koordinaten ist es möglich, eine Matrixdarstellung einer LT zu ermitteln, die im 4-Raum wirkt, effektiv aber Punkte im 3-Raum verschiebt. Darüber hinaus ist bekannt, dass irgendeine affine Transformation invertierbar ist, sodass die zugeordnete Matrix ebenfalls invertierbar ist.
In dem gegenwärtigen Kontext ist es nicht notwendig, Punkte zu skalieren, nur, um sie zu verschieben oder zu drehen. Die 4×4-Matrix TR, die Punkte in der x-, y- und z-Richtung in dieser Reihenfolge um Tx, Ty und Tz verschiebt, ist gegeben durch
Die Matrix Rx, die um die z-Achse um einen Winkel ☐ dreht, ist durch
gegeben.
Es ist leicht zu sehen, dass die inverse Matrix für TR(Tx, Ty, Tz) durch TR(–Tx, –Ty, –Tz) gegeben ist und dass die Inverse von Rz(☐) durch Rz(–☐) gegeben ist.
Die Matrizen zum Drehen um die x- und die y-Achse sind ähnlich Rz. Sie sind allgemein durch Rx und Ry bezeichnet.
Es ist bekannt, dass unter Verwendung homogener Koordinaten:

1. die affinen Transformationen Matrixdarstellungen haben;
2. die Transformationen und somit die Matrizen invertierbar sind;
3. die Matrix für eine Folge von Transformationen durch Multiplizieren der Einzelmatrizen miteinander erhalten wird; und
4. die Inverse der Produktmatrix M₁·M₂·M₃· ... ·M_n = M_n ^–1·M_n–1 ^–1· ... ·M₃ ^–1·M₂ ^–1·M₁ ^–1 ist.

In der DLSS wird die Verwendung von Transformationen und ihren Inversen angewendet, wenn eine Bildsensorposition durch bekannte Translationen und/oder Drehungen aus einer anderen erhalten wird. Es wird angenommen, dass die Bildsensorposition B aus der Bildsensorposition A durch eine Transformation T erhalten wird, die eine Folge von n Translationen und/oder Drehungen ist. T hat dann die Form: T = T1 • T2 • T3 • ... • Tn,wo • die Funktionszusammensetzung bezeichnet.
Aus dem Obigen ist die Matrix für T durch M = M1·M2·M3· ... ·Mn gegeben, wobei M_i die Matrixdarstellung für T_i ist.
Um die vom Bildsensorort B erhaltenen Punkte auf jene auszurichten, die am Ort A erhalten wurden, wird auf die 3d-Spels von B die inverse Transformation angewendet. Das heißt, für jedes 3d-Spel S, das am Ort B gesammelt wurde, kann das 3d-Spel S auf ein 3d-Spel S' am Bildsensorort A für B durch S' = Mn –1·Mn–1 –1 ... ·M3 –1·M2 –1·M1 –1 Gleichung 1.2.1ausgerichtet werden.
Als ein einfaches Beispiel wird angenommen, dass der Bildsensorort B durch Drehen des Bildsensororts A um 60 Grad um die y-Achse und Verschieben um 0, 0 und 10 in dieser Reihenfolge in der x-, y- und z-Richtung erhalten wird. Ein Punkt S bei B kann auf einen Punkt S' bei A ausgerichtet werden, indem um –60 Grad um die y-Achse gedreht und um –10 in der z-Richtung verschoben wird. Unter Verwendung der Matrixschreibweise ist M₁ = TR(0, 0, 10) und M₂ = Rz(60). Folglich ist die Matrixdarstellung für T Rz(60)·TR(0, 0, 10). Aus der obigen Diskussion ist das Inverse von M1 TR(0, 0, –1) und das Inverse von M2 Rz(–60). Anwenden von Gleichung 1.2.1 liefert S' = TR(0, 0, –10)·Rz(–60)·S.
In einigen Fällen ist nicht genau bekannt, wie ein Bildsensorort aus einem anderen erhalten wird. In diesem Fall, dem obigen Fall B, nutzt die DLSS ein anderes Verfahren zum Ausrichten der Punkte. Dieses Verfahren beruht auf der folgenden Tatsache: Das Ausführen einer Translation und von 3 Drehungen kann zwei beliebige Koordinatensysteme ausrichten.
In DLSS-Ausführungsformen werden die zwei Koordinatensysteme dadurch festgesetzt, dass dieselbe Menge aus 3 Punkten an zwei getrennten Bildsensororten lokalisiert wird. Wie zuvor beschrieben wurde, werden anhand von 3 die drei Punkte 44, 46, 48 bei jeder Bildsensorposition lokalisiert und werden ihnen 3D-Koordinaten gegeben.
Aus den 3 Punkten 44–48 und aus dem durch N bezeichneten Normalenvektor 54 zu der Ebene, wie sie durch Bilden des Kreuzprodukts von V1 mit V2 gebildet wird, N = V1 × V2, Gleichung 1.2.2werden die zwei mit V1 und V2 bezeichneten Vektoren 50, 52 gebildet.
Die durch N dargestellte Richtung wird zu der positiven y-Achse für das neue Koordinatensystem. Einer der Vektoren V1 oder V2 wird als die Richtung der positiven x-Achse ausgewählt. Diese Vektoren sind senkrecht zu N, aber nicht notwendig zueinander. Die positive z-Achse wird durch Kreuzen von N mit dem für die x-Achse ausgewählten Vektor bestimmt.
Eine normierte, wechselweise orthogonale Menge von Vektoren, die eine Basis für das neue Koordinatensystem bilden, ist durch (V1/||V1||, (V1 × N)/||V1 × N||, N/||N||)gegeben, wobei || || die Vektornorm bezeichnet.
Dieser Prozess wird bei allen verbleibenden Bildsensorpositionen wiederholt. Nachdem die bei jeder Position gesammelten Punkte zu einer Menge von 3d-Spels kombiniert worden sind, können daraufhin alle Koordinatensysteme ausgerichtet werden. Nunmehr anhand von 4 ist die Folge von Transformationen, die zwei Koordinatensysteme 56, 58 von zwei Bildsensorpositionen ausrichten, dieselbe Folge von Transformationen, die zum Ausrichten der Mengen von 3d-Spels verwendet wird, die bei diesen Bildsensorpositionen gesammelt worden sind.
Um ein Koordinatensystem auf ein anderes auszurichten, schreibt die oben beschriebene Prozedur vor, dass eine Translation ausgeführt wird, die den Ursprung 60, O' = (O'x, O'y, O'z), in den Ursprung 62, O = (Ox, Oy, Oz), verschiebt. In der Matrixschreibweise wird dieser Schritt durch TR(Ox – O'x, Oy – O'y, Oz – O'z) Gleichung 1.2.3beschrieben.
Bei dem Koordinatensystem 56 am dem Ursprung O' mit den durch x' (64), y' (66) und z' (68) bezeichneten Achsen und bei dem Koordinatensystem 58 mit dem Ursprung O mit den durch x (70), y (72) und z (74) bezeichneten Achsen werden alle Punkte in der Weise um die y-Achse gedreht, dass die z'-Achse des Systems mit dem Ursprung O' in die xy-Ebene des Systems mit dem Ursprung O gedreht wird. In der Matrixschreibweise wird dieser Schritt durch Ry(☐1) Gleichung 1.2.4beschrieben, wobei ☐1 der erste Euler-Winkel ist.
Durch Drehen der Punkte um die x-Achse in der Weise, dass die z'-Achse in der xz-Ebene liegt, wird veranlasst, dass die z'- und die z-Achse ausgerichtet werden. In der Matrixschreibweise ist Rx(☐2) Gleichung 1.2.5wobei ☐2 der zweite Euler-Winkel ist.
Es wird nun eine Drehung um die z-Achse ausgeführt, sodass die x'- und die x-Achse sowie die y'- und die y-Achse ausgerichtet werden. In der Matrixschreibweise ist Rz(☐3) Gleichung 1.2.6wobei ☐3 der dritte Euler-Winkel ist.
Wenn die obigen Transformationen an den 3d-Spels mit einem Ursprung bei O' ausgeführt worden sind, werden die 3d-Spels auf die Punkte mit einem Ursprung bei O ausgerichtet. In der Praxis ist das Verfahren von Euler allgemeiner als das Verfahren inverser Transformationen. Das letztere Verfahren kann als ein Spezialfall des Ersteren behandelt werden.
In Ausführungsformen eines DLSS-Triangulationssystems kann bei jedem 3D-Punkt auf der Oberfläche des Objekts eine Tangentialebene festgesetzt werden. Diese Tangentialebenen werden bei der Triangulation verwendet, wobei der Normalenvektor zu jeder Ebene in der Weise zugewiesen wird, dass seine Punkte von der sichtbaren Oberfläche weg weisen, da die Textur auf die sichtbare Oberfläche geklebt wird. Dies verhindert, dass die Textur auf die Innenoberfläche des Objekts geklebt wird, das modelliert wird.
Für jeden Punkt (x, y, z) auf der Oberfläche wird die Ebene der kleinsten Quadrate konstruiert. Diese Ebene dient als die Tangentialebene. An allen Punkten in einer Umgebung des Punkts (x, y, z) erfolgt eine Kurvenanpassung. Die Größe der Umgebungen kann variieren, um die Anzahl der Ebenen größer oder kleiner zu machen.
Unter Verwendung aller Punkte aus der Umgebung wird die Erfassungsmatrix C erzeugt. Diese Matrix ist als die Summe aller inneren Produkte von Vektoren der Form (v – 0) mit sich selbst definiert, wobei:

a. v in der Umgebung von (x, y, z) liegt; und
b. 0 der Schwerpunkt der Punkte in der Umgebung von (x, y, z) ist.

Aus der Statistiktheorie ist bekannt, dass C eine positiv definite Matrix ist und dass ein Eigenvektor N, der dem größten Eigenwert von C entspricht, ein Normalenvektor zu der Regressionsebene ist. Allerdings ist nicht bekannt, welcher Vektor, N oder –N, von der sichtbaren Oberfläche weg weist.
Zur Bestimmung der richtigen Orientierung des Normalenvektors wird ein Minimal-Spanning-Baum gebaut. Ein Minimal-Spanning-Baum ist für eine Menge von Kanten und Eckpunkten wie etwa jene, die durch DLSS gesammelt worden sind, einfach ein Graph, in dem die Summe der Länge der Kanten minimal ist und der alle Eckpunkte enthält.
Es wird erwartet, dass ein Normalenvektor während eines Durchlaufens des Minimal-Spanning-Baums ähnlich wie der für benachbarte Tangentialebenen orientiert ist. Zum Beispiel wäre allgemein nicht zu erwarten, dass ein Cluster von 10 Ebenen 9 Normalenvektoren hat, die in eine Richtung weisen, während der 10-te in die entgegengesetzte Richtung weist. Ein Normalenvektor wird anhand von Schwellenwerten anhand seiner Nachbarn negiert.
Zur Visualisierung der Oberfläche eines 3D-Objekts wird ein Oberflächenermittlungsalgorithmus realisiert, der als Marching Cubes bekannt ist. Der Marching-Cubes-Algorithmus wurde 1987 von Lorensen und Cline entwickelt {W. E. Lorensen und H. E. Cline, Marching cubes: A high resolution 3D surface reconstruction algorithm. Computer Graphics, 21 (4): 163–169, Juli 1987.}. Er verwendet zur Bestimmung der zu rendernden Oberfläche einen bestimmten Schwellenwert. Die Grundidee beruht auf dem folgenden Prinzip: "Falls ein Punkt innerhalb des gewünschten Volumens einen Nachbarpunkt außerhalb des Volumens hat, muss die Iso-Oberfläche zwischen diesen Punkten liegen."
5 veranschaulicht den Prozess für den zweidimensionalen Fall. Die Figur links, 80, wird abgetastet, um zu bestimmen, welche Rechtecke 82 geschnitten werden; in zwei Dimensionen ist ein Würfel ein Rechteck. Falls ein Schnitt stattfindet, wird der Mittelpunkt der Kante, wo der Schnitt stattfindet, gekennzeichnet. Durch Verbinden aufeinander folgender Mittelpunkte wird eine Näherung der Originaloberfläche vorgenommen. In dem veranschaulichten Fall ist die Näherung 84 verhältnismäßig grob, kann aber durch Erhöhen der Auflösung der Rechtecke verbessert werden.
Der dreidimensionale Fall funktioniert analog, ist aber erwartungsgemäß komplizierter. Es ist beobachtet worden, dass eher als Rechtecke Würfel die Grenze der Oberfläche annähern. Es wird angemerkt, dass es wichtig ist zu wissen, ob ein Punkt innerhalb oder außerhalb der Oberfläche liegt. Dies wird unter Verwendung der zuvor beschriebenen vorzeichenbehafteten Entfernung ausgeführt. Es wird daran erinnert, dass eine vorzeichenbehaftete Entfernung zu der Oberfläche die Entfernung von dem Punkt zu der Oberfläche mit einem angebrachten negativen Vorzeichen ist, falls der Punkt innerhalb der Oberfläche ist, und mit einem angebrachten positiven Vorzeichen ist, falls der Punkt außerhalb der Oberfläche ist.
Anhand von 6 gibt es (bis auf Isomorphismus) 16 Möglichkeiten dafür, wie keiner, einer oder mehrere der Eckpunkte eines Würfels 86 innerhalb der Oberfläche liegen können, die sie anzunähern versuchen. Im einfachsten nicht trivialen Fall kann ein Eckpunkt 88 des Würfels innerhalb der Oberfläche liegen. In diesem Fall wird wie gezeigt ein Dreieck 90 aus den Mittelpunkten der 3 Kanten gebildet, die den Eckpunkt enthalten. In diesem Diagramm ist festgestellt worden, dass der einzelne durch den Punkt angegebene Eckpunkt 88 innerhalb der Oberfläche liegt. Alle anderen Eckpunkte liegen außerhalb. Eine einfache Möglichkeit, ein Dreieck zu bilden, ist, die Mittelpunkte aller auf den inneren Eckpunkt auftreffenden Kanten zu verwenden. Dieses Dreieck 90 ist durch die dicke punktierte Linie angegeben. Falls eine lineare Interpolation verwendet wird, wird eine höhere Genauigkeit erhalten.
In 7 ist ein weiterer der 16 Fälle gezeigt. In diesem Fall wird festgestellt, dass 3 der Eckpunkte 92, 94, 96 innerhalb der Oberfläche liegen, die modelliert wird, während die verbleibenden 5 Eckpunkte außerhalb liegen. In diesem Fall werden die 3 Dreiecke 98, 100, 102 zu der Menge der Eckpunkte hinzugefügt. Das erste, 98, wird dadurch erhalten, dass der Eckpunkt, der nicht in derselben Fläche wie die zwei verbleibenden liegt, durch das oben beschriebene Verfahren hinzugefügt wird.
Für die anderen zwei Eckpunkte werden zwei Dreiecke 100, 102 hinzugefügt. Das erste hinzugefügte Dreieck 100 hat als eine Basis die Kante zwischen den zwei Eckpunkten, von denen bekannt ist, dass sie innerhalb der Oberfläche liegen. Der dritte Eckpunkt 104 wird als der Mittelpunkt einer der Kanten auf der gegenüberliegenden Fläche gewählt. Das zweite hinzugefügte Dreieck 102 wird mit seiner Basis als die Mittelpunkte 104, 106 der zwei Kanten auf der gegenüberliegenden Oberfläche und mit seinem Eckpunkt 96 als einer der 2 Eckpunkte, von denen bekannt ist, dass sie in dem Würfel liegen, gewählt. Dies erzeugt im Wesentlichen eine Ebene, die durch die zwei Eckpunkte 94, 96 und durch die Mittelpunkte 104, 106 der gegenüberliegenden Fläche geht. In 7 ist eine Seitenansicht des Prozesses veranschaulicht, während 8 eine Vorderansicht desselben Prozesses veranschaulicht.
Nunmehr anhand von 9 ist ein weiterer Fall gezeigt. Hier gibt es 4 Eckpunkte 108–112, wobei ermittelt wird, dass keiner auf derselben Kante innerhalb der Oberfläche liegt. In diesem Fall wird jeder der Eckpunkte so behandelt, als ob er der einzige Eckpunkt wäre, der innerhalb des Würfels liegt. Somit werden zu der Menge von Dreiecken 4 Dreiecke 114–120 hinzugefügt, die durch die Eckpunkte und Mittelpunkte benachbarter Kanten gebildet sind.
Nunmehr anhand von 10 und weiter anhand der 6–9 sind alle 15 Fälle 124 einschließlich der oben beschriebenen Fälle gezeigt. Die Vektoren 126 geben die Normalen zu jedem Dreieck an.
Die Texturabbildung oder Musterabbildung ist der Prozess, durch den eine Textur oder ein Muster in einer Ebene auf ein 3D-Objekt abgebildet wird. In DLSS-Ausführungsformen ist das Ziel, die Textur oder das Muster von einer Teilmenge einer 2D-Bitmap auf dasjenige Dreieck abzubilden, das diese Teilmenge im 3-Raum repräsentiert.
Das 3D-Modellierungsverfahren beginnt mit den Pixelkoordinaten von einer Menge von 2D-Bildern. Diese Pixel werden einem Prozess ausgesetzt, der ihnen 3D-Koordinaten zuweist. Darüber hinaus wird ein 3d-Spel mit den Pixelkoordinaten verbunden, aus denen es hervorgegangen ist. Wenn der Triangulationsprozess ein Dreieck bildet, ist es somit möglich, aus einer Bitmap, die dem 3D-Dreieck entspricht, einen Dreieckbereich zu bestimmen. Daraufhin kann die Textur von der Bitmap auf das 3D-Modell übertragen werden.
2. Digitaldatenerfassung
Der erste Schritt in einer bevorzugten Ausführungsform des DLSS-Prozesses ist die Digitaldatenerfassung. Üblicherweise werden die Daten von mehreren Bildsensorpositionen oder von mehreren Bildsensoren erfasst und durch die zuvor beschriebenen Verfahren kombiniert.
Wie in 11 gezeigt ist, ist der Bildsensor geeignet an einem Schieber 130 der Länge L angebracht. Der Bildsensor wird in diskreten Schritten 132, sämtlich von der Länge ☐L, vom linken Rand des Schiebers zum rechten Rand verschoben. In jedem Schritt 132 wird ein digitales Bild der Szene oder des Objekts 134 aufgenommen, die/das modelliert wird. Somit ist unter der Annahme, dass die Basis die Länge L hat und N + 1 Bilder gesammelt werden, jeder Bildsensorort um ☐L Einheiten von dem vorherigen Ort verlagert. Der Bildsensor bewegt sich an einem Schieber (der Basis) und hält an Punkten an, die L/N(☐L) voneinander entfernt sind, um ein digitales Bild zu sammeln. Nachdem der Bildsensor die gesamte Basis durchlaufen hat, ist zur Analyse eine Sammlung von N Bildern verfügbar, die um L/N gegeneinander versetzt sind. In den meisten Fällen wird vorzugsweise ein weiteres Bild von der Mitte des Schiebers aufgenommen, das für die Texturabbildung zu verwenden ist.
In ausgewählten DLSS-Ausführungsformen werden die folgenden Annahmen gemacht:

1. Es gibt keine Änderung des y-Wertes eines Punkts, während sich der Bildsensor entlang der Basis bewegt.
2. Der Bildsensor ist parallel zu der Richtung, in der der Bildsensor gleitet.

Diese Voraussetzungen werden gemacht, damit die zuvor beschriebenen Parallaxenverfahren angewendet werden können.
In der folgenden Beschreibung wird gezeigt, wie DLSS-Ausführungsformen diese Bilder und einen von zwei Punktalgorithmuskandidaten verwenden, um 3d-Spels zu erzeugen. Einer dieser Algorithmen nimmt an, dass die Bilder Farbbilder sind. Der andere nimmt nur an, dass das für die Texturabbildung verwendete Bild ein Farbbild ist.
3. Erzeugen von 3d-Spels
Das Erzeugen von 3d-Spels umfasst 2 Schritte. Der erste Schritt ist das Ermitteln desselben Punkts in zwei der Bilder, die in dem Datenerfassungsschritt gesammelt wurden. Das heißt, dass zunächst Paare von Pixeln, eines vom Bild 1 und eines vom Bild n, ermittelt werden, die demselben Punkt im Raum entsprechen. Diese Punkte werden als 3d-Spel-Kandidaten bezeichnet. Die 3d-Spel-Kandidaten werden anhand der im Folgenden beschriebenen Kriterien akzeptiert oder zurückgewiesen. Der zweite Schritt ist das Berechnen der Koordinaten für einen akzeptierten 3d-Spel-Kandidaten durch die zuvor in dem Abschnitt über die DLSS-Theorie beschriebenen Verfahren. Wie in diesem Abschnitt angegeben ist, ist die Berechnung der Koordinaten (x, y, z) unkompliziert, sofern ein richtiger Punkt lokalisiert wird. Um genaue 3D-Modelle sicherzustellen, ist allerdings Sorgfalt nötig, um sicherzustellen, dass die Pixel im Bild 1 und im Bild n tatsächlich denselben Punkt im Raum repräsentieren.
DLSS-Ausführungsformen verwenden geeignet optional eines von zwei Verfahren, um 3d-Spel-Kandidaten zu erzeugen und sie als tatsächliche 3d-Spels zu akzeptieren oder zurückzuweisen. Ein Verfahren beruht auf dem Farbdifferential in dem Zentralbild. Dieses Verfahren wird Farbdifferentialanalyse (CDA) genannt. Das zweite Verfahren beruht auf der Rändererfassung durch Graustufenbilder und wird Graustufendifferentialanalyse (GDA) genannt. Es wird hier für jedes Verfahren eine Beschreibung gegeben.
Wie in 12 gezeigt ist, ist der erste Schritt in der CDA das Bilden einer dreidimensionalen Matrix aus der Folge von Bildern 140, die zuvor erzeugt worden sind. Wenn die Matrix E genannt wird, repräsentiert E(m, n, N) die Farbe oder Intensität des Pixels in der Zeile m und in der Spalte n des N-ten Bildes.
Faktoren, die von dem Farbdifferential- und von dem DLSS-Verfahren für den 3D-Spel-Kandidaten-Ort verwendet werden, sind die Querschnitte 142 der Matrix von Bildern. Diese Querschnitte 142 sind einfach y-Schnitte der Matrix E, die die Punkte in den Bildern repräsentieren, die sich bei einem festen y-Wert im Raum befinden. Nun ist offensichtlich, weshalb die Annahme gemacht wurde, dass es keine Änderungen der y-Werte für ein Objekt gibt, während sich der Bildsensor während des Datenerfassungsschritts entlang des Schiebers bewegt. Da die Analyse an horizontalen Querschnitten erfolgt, folgt, dass die y-Werte vom Bild 0 bis zum Bild N gleichbleibend sein sollten.
In 13 ist eine erste Szene 144 (links) gezeigt, die einen nahen Punkt 146 und einen entfernteren Punkt 148 enthält. In der mittleren Szene 150 sind die Positionen des nahen und des entfernten Punkts 146, 148 in jedem der Bilder 0, 1, 2, ..., N gezeigt. Diese Figur kann als die oben beschriebene Matrix E vorgestellt werden. In der rechten Szene 152 ist ein horizontaler Querschnitt von E, wie von oben gesehen, gezeigt. Da der nahe Punkt dem Bildsensor näher ist, bewegt er sich weiter als der ferne Punkt, während sich der Bildsensor von links nach rechts bewegt.
Die meisten Querschnitte sind nicht so einfach wie der obige. Ein typischer Querschnitt 154 kann eher wie der in 14 gezeigte aussehen. Aus diesem Diagramm ist zu sehen, dass es schwierig sein kann, Pixel in dem ersten Bild an jene in dem letzten Bild anzupassen. Zum Beispiel sind irgendwelche der nahen Pixel in dem hinteren Bild 156 (Bild N) Kandidaten für die Anpassung an irgendeines der fernen Pixel in dem vorderen Bild 158 (Bild 0). Dasselbe kann auch von den Zwischenpixeln gesagt werden.
Die CDA passt Pixel an, indem sie zuerst in dem oben erwähnten Zentralbild nach dem Farbdifferential sucht. Mit Farbdifferential ist eine plötzliche Änderung der Farbe gemeint, die sich für einen festen y-Wert über eine Menge von Pixeln bewegt. Der Pfeil 160 in 15 gibt die Pixel an, die dem Zentralbild in einem festen horizontalen Querschnitt entsprechen. Die Kreise 162 identifizieren Punkte, wo ein erhebliches Farbdifferential ermittelt wird, während die Pixel von links nach rechts geprüft werden. Diese werden zu den Kandidatenpunkten für 3d-Spels.
Im nächsten Schritt prüft die CDA eine Familie von Linien 164, die durch die Punkte des Farbdifferentials verlaufen und die von dem ersten Bild 166 bis zu dem letzten 168 verlaufen. Eine solche Familie 170 ist in 16 mit Strichlinien veranschaulicht.
Für alle solche Linien in der Folge wird die Streuung oder Farbvarianz der Pixellinie berechnet. Geeignet ist sie einfach die Änderung der Rot-, Grün- und Blau-Komponente der Pixel entlang der Linie. Aus dem Diagramm ist zu sehen, dass die minimale Varianz auf der Linie liegt, die eine bestimmte Grenze 172 zwischen Objekten verschiedener Farbe repräsentiert. Tatsächlich wäre die Varianz entlang einer solchen Linie null, falls kein Rauschen (z. B. wegen Aliasing, ungenauer Beleuchtung oder Instrumentenfehler) vorhanden wäre. Für Punkte nicht auf der Grenzlinie 172 ist die Farbvarianz von null verschieden.
In dem CDA-Verfahren wird die Linie mit der minimalen Farbvarianz geprüft. Falls die Varianz entlang der Linie mit minimaler Farbvarianz einen im Voraus festgelegten Schwellenwert übersteigt, wird der Punkt zurückgewiesen und geht die Analyse zu dem nächsten Punkt über. Falls die Varianz unter einem bestimmten Schwellenwert liegt, wird der Punkt als ein 3d-Spel akzeptiert. Es ist leicht zu sehen, dass die benötigten Pixelversätze, falls ein Punkt ausgewählt wird, so ermittelt werden können, dass die Koordinaten (x, y, z) des Punkts wie zuvor beschrieben berechnet werden können.
Außer der oben beschriebenen CDA-Analyse identifizieren DLSS-Verfahren außerdem 3d-Spel-Kandidaten durch ein zweites Verfahren, das eine Graustufendifferentialanalyse an Graustufenbildern ausführt. Dieses Verfahren ermöglicht beträchtliche Leistungsgewinne gegenüber der CDA, indem es einfachere Verfahren zum Lokalisieren von 3d-Spel-Kandidaten und zum Suchen verwendet.
Während der Bildsensor horizontal entlang gleitet, nimmt der Bilderfassungsprozess eher Graustufenbilder als die von der CDA verwendeten Farbbilder auf. Diese Bilder werden zunächst durch einen Rändererfassungsalgorithmus geleitet. Die Rändererfassung nimmt den Platz der Analyse von Pixelzeilen in dem Zentralbild ein. Das Ergebnis des Rändererfassungsprozesses ist eine zweite Reihe von Graustufenbildern. Der Intensitätswert in diesen Bildern gibt den Grad der "Stärke" oder "Härte" des Rands, z. B. 0 für keinen Rand und 255 für eine Unstetigkeit, an.
Wie in 17 gezeigt ist, werden die Bilder mit erfassten Rändern ebenso in einer 3-dimensionalen Matrix angeordnet, wie es bei den Farbbildern in der CDA der Fall war. Ebenso wie in der CDA werden horizontale Querschnitte 174 dieser Matrix analysiert. Wie in 18 gezeigt ist, enthält jeder Querschnitt 174 dieselbe vertikale Zeile von Ränderstärken 176 von jedem der Bilder.
Falls es möglich ist, eine Linie von Rändern durch einen Querschnitt zu ermitteln, bedeutet dies die Existenz eines 3d-Spels, dessen Entfernung von dem Bildsensor durch die zuvor beschriebenen Verfahren berechnet werden kann. Ebenso wie in der CDA ist die Anzahl der Pixel, die sich der Punkt von dem ersten Bild 178 bis zu dem letzten 180 bewegt, leicht verfügbar und bestimmt die Entfernung bis zu dem Punkt.
Um 3d-Spels zu ermitteln, werden Ränder 176 ermittelt, die verfolgt werden können, während sie sich durch die von benachbarten Bildsensoren aufgenommenen Bilder bewegen. Der Prozess des Ermittelns aller Linien in allen Querbildern ist eine rechentechnisch sehr aufwändige Aufgabe. Um die für diese Berechnungen benötigte Zeit zu minimieren, versucht der Suchalgorithmus, die Suchzeit zu minimieren und den Suchraum zu verkleinern. Das Hauptmittel, die Liniensuche zu minimieren, ist, in der unteren Zeile 178 nach einem starken Rand zu suchen, und, wenn einer ermittelt worden ist, zu versuchen, einen Rand in der obersten Zeile 180 zu ermitteln, der an ihn angepasst ist. Falls eine solche Anpassung ermittelt wird, ist ein 3d-Spel-Kandidat lokalisiert worden, wobei ein Versuch unternommen wird, den Rand durch die anderen Bilder zu verfolgen.
Der Grad der Anpassung wird dadurch gemessen, dass alle Pixel auf der Linie 176 ermittelt werden, die zwischen starken Rändern gezeichnet sind, die in dem obersten und in dem untersten Bild identifiziert sind. Falls alle Pixel auf der Linie einen bestimmten Schwellenwert überschreiten und falls alle annähernd dieselbe Stärke haben, wird gefolgert, dass die Linie einen Punkt im 3-Raum repräsentiert.
Daraufhin kann aus dem Bild wie zuvor beschrieben der Ort (x, y, z) des Punkts bestimmt werden.
Wenn nunmehr anhand von 19 entweder der CDA-Prozess oder der GDA-Prozess abgeschlossen wird, ist eine Punktwolke 182 verfügbar, die die 3D-Szene von einem einzelnen Bildsensorort repräsentiert.
4. Punktausrichtung
Nachdem die 3d-Spels an allen Bildsensorpositionen berechnet worden sind, werden sie zu einem einzigen Datensatz von 3d-Spels mit einem gemeinsamen Ursprung gemischt. Dies ermöglicht eine Punktwolkenerzeugung des gesamten Raums oder Objekts.
Wie zuvor beschrieben wurde, kann eine Bildsensorposition aus einer anderen erhalten werden durch:

(Fall A) eine bekannte Reihe von Transformationen, die eine Translation oder Drehung enthalten; oder
(Fall B) eine unbekannte Transformation.

Falls der Fall A zutrifft, wird für jede Transformation in der bekannten Reihe die inverse Transformation angewendet. Zum Beispiel wird angenommen, dass die Bildsensorposition B aus einem Bildsensorort durch Verschieben der Punkte um +10 Einheiten in der y-Richtung und Drehen um 45 Grad um die y-Achse erhalten wird. Um die Punkte vom Bildsensor B auf den Ursprung für den Bildsensorort auszurichten, wird die Transformation angewendet, die um –45 Grad um die y-Achse dreht und um –10 in der y-Richtung verschiebt.
Falls der Fall B zutrifft, verwenden die DLSS-Verfahren Routinen, die dieselben drei Punkte sowohl in der Kamera A als auch in der Kamera B lokalisieren. Geeignet wird von jeder der Kamerapositionen dieselbe Menge aus 3 Punkten lokalisiert. Optional ist dieser Schritt von der tatsächlichen Datenerfassung von einem gegebenen Kameraort getrennt. Die DLSS-Ausführungsformen unter Verwendung der zuvor zusammengefassten Techniken verlaufen wie folgt:

a. Verwendung der 3 Punkte zum Konstruieren eines Koordinatensystems für jede Kamera; und
b. Kombinieren der Daten durch Umsetzen eines Koordinatensystems in das andere.

Wenn die Punktausrichtung abgeschlossen ist, ist eine 3D-Wolke von Punkten für den gesamten Raum oder für das gesamte Objekt verfügbar.
5. Triangulation und Gittererzeugung
Der nächste Schritt in der bevorzugten DLSS-Ausführungsform ist der Bau eines Gitters, insbesondere eines dreieckigen Gitters, aus der Menge von 3d-Spels, die wie oben beschrieben gesammelt wurden. Nachdem die Punkte in eine geeignete Datenstruktur geladen wurden, werden sie gefiltert.
Es gibt mehrere Gründe, weshalb der Filterungsschritt bevorzugt ist. Zunächst erzeugt das 3d-Spel-Erzeugungsprogramm eine große Anzahl von Punkten, häufig weitaus zuviel, um zu ermöglichen, dass die Triangulationsprozedur effizient arbeitet. In anderen Technologien wie etwa der Lasertechnologie sind die Anzahl und der näherungsweise Ort der 3D-Punkte durch den Anwender steuerbar. Optional sind in der DLSS alle durch die CDA oder durch die GDA identifizierten 3d-Spels enthalten. In Flächen mit hohem Kontrast oder in Flächen, in denen reichlich Ränder vorhanden sind, können viele zusätzliche oder überflüssige Punkte erzeugt werden.
Um die Effizienz des Triangulationsalgorithmus zu verbessern, sucht der Filterungsalgorithmus einen einzelnen, repräsentativen Punkt, um Punkte, die "zu nahe" beieinander sind, zu ersetzen. Mit "zu nahe" ist gemeint, dass die Punkte alle bei einer Kugel vom Radius R liegen, wobei R ein Eingabeparameter in das Triangulationsteilsystem ist. Während R zunimmt, werden immer mehr Punkte entfernt. Umgekehrt wird die Anzahl erhaltener Punkte erhöht, während R abnimmt. Die Größe von R betrifft eindeutig die 3D-Endauflösung der Oberfläche.
Ein weiteres Problem ist, dass einige 3D-Spels einfach Rauschen sein können. Wegen der Beleuchtung, Reflexionen, Schatten oder anderen Anomalien werden Punkte erzeugt, die nicht Teil der Oberfläche sind. Diese Punkte werden vorzugsweise lokalisiert und entfernt, sodass die Oberfläche richtig modelliert wird. Rauschpunkte sind allgemein dadurch charakterisiert, dass sie "fern von irgendwelchen Stützpunkten sind", d. h., dass sie innerhalb einer Kugel sehr dünn verteilt sind.
In einer bevorzugten Ausführungsform erfolgt die Konstruktion des dreieckigen Gitters selbst durch das Marching-Cubes-Verfahren. Marching Cubes sind eine gut dokumentierte Möglichkeit, aus einer Menge von Punkten ein dreieckiges Gitter zu erzeugen. Das Marching-Cubes-Verfahren wurde 1987 von Lorensen und Cline entwickelt und ist seither erweitert worden, um Tetraeder und andere Volumenmodelle zu enthalten. Die Eingaben in diesen Algorithmus sind die gefilterte Menge von Punkten und eine vorzeichenbehaftete Entfernung von dem Objekt, das modelliert wird, zu jedem der Punkte.
Die Idee der vorzeichenbehafteten Strecke und eine Zusammenfassung der Marching Cubes sind zuvor beschrieben worden. Diese Konzepte ermöglichen zusammen die Erzeugung von Dreiecken. Wie der 3d-Spel-Erzeugungsprozess ist der Dreieckerzeugungsprozess einer der rechentechnisch aufwändigsten Schritte in dem DLSS-Prozess.
Um das dreieckige Gitter zu erzeugen, wird über die Menge der 3d-Spels eine Menge von Würfeln mit steuerbarem Volumen gelegt. Steuerbares Volumen bedeutet einfach, dass die Länge einer Kante des Würfels ein Eingabeparameter in das Triangulationsteilsystem ist. Es ist leicht zu sehen, dass die Oberfläche näher modelliert wird, während die Volumina der Würfel abnehmen.
Von den Marching-Cubes-Verfahren werden Dreiecke verwendet. Somit werden diejenigen Würfel identifiziert, die 3d-Spels im Innern sowie eng benachbarte 3d-Spels außerhalb des Würfels haben. Die Dreiecke werden gemäß den durch den Marching-Cubes-Algorithmus spezifizierten und in den Diagrammen aus 10 veranschaulichten 16 Möglichkeiten gebildet.
Außer der Bestimmung der Eckpunkte der Dreiecke wird jedes Dreieck orientiert, d. h. die sichtbare Fläche des Dreiecks bestimmt. Unter Verwendung der vorzeichenbehafteten Strecke und der Eckpunkte des Dreiecks ist es möglich, zu jedem Dreieck einen Normalenvektor zu bestimmen, der von der sichtbaren Seite des Dreiecks weg weist. Der Orientierungsschritt wird ausgeführt, da die Textur der Oberfläche auf die sichtbare Seite des Dreiecks geklebt wird. Eine falsche Orientierung würde zu einer teilweise oder vollständig invertierten Oberfläche führen. Wenn der Triangulationsprozess abgeschlossen ist, ist es möglich, das Objekt oder den Raum, das/der modelliert wird, wie in 20 gezeigt ist, als ein Drahtmodell oder Drahtgitter 184 anzuzeigen.
6. Texturabbildung
Der letzte Schritt in dem bevorzugten DLSS-Verfahren ist das Abbilden einer Textur auf jedes der in dem Triangulationsprozess erzeugten Dreiecke. Die Eingabe in diesem Schritt ist

a. die Menge der Dreiecke von dem Triangulationsschritt;
b. die in der Datenerfassung gesammelten Bilder, die für die Texturabbildung bestimmt waren; und
c. einen Index, der angibt, aus welchem Bild ein Dreieck gekommen ist.

Da die DLSS-Verfahren mit Pixeln beginnen und mit 3d-Spels enden, ist es möglich, diesen Prozess umzukehren und die Pixel zu ermitteln, aus denen ein 3d-Spel erzeugt wurde. Unter Verwendung der obigen Eingangsdaten wird jedes der 3d-Spels, die die Eckpunkte eines Dreiecks bilden, in Pixelkoordinaten umgesetzt. Darüber hinaus ist das Bild bekannt, aus dem das Dreieck erzeugt wurde.
Unter Verwendung dieser Pixelkoordinaten kann an einen Dreieckbereich in dem Bild ein Dreieck mit 3d-Spels als Eckpunkte angepasst werden. Darüber hinaus ist bekannt, welchem Bild das Dreieck entnommen wurde. Folglich kann der Dreieckbereich aus diesem Bild, der dem gegebenen Dreieck entspricht, extrahiert und aufgeklebt werden.
Nachdem die Texturabbildung fertig ist, ist ein vollständiges photorealistisches räumlich genaues Modell 186 des Raums verfügbar, wie es in 21 gezeigt ist.
Alternative Konfigurationen für DLSS-Systeme
Unter Verwendung der in den vorherigen Abschnitten beschriebenen Prozesse werden jetzt drei beispielhafte Ausführungsformen von DLSS-Systemen und/oder -Verfahren offenbart. Die ersten zwei modellieren hauptsächlich Objekte oder Mengen von Objekten, während die dritten hauptsächlich zum Modellieren großer Räume verwendet werden. Im Folgenden wird eine Beschreibung jeder Ausführungsform gegeben.
Einzelsensor-Bilderzeuger
Der Einzelsensor-Bilderzeuger ist für die Modellierung der seitlichen Oberflächen eines Objekts oder von Objekten, das/die auf einem Drehtisch angeordnet ist/sind, geeignet. Eine typische Einzelsensoranordnung 188 ist in 22 gezeigt.
Um den beispielhaften Einzelbildsensor-Objektmodellierer zu verwenden, spezifiziert der Anwender drei Parameter:

1.) Der erste Parameter R spezifiziert, wie viele Ansichten des Objekts 190 hergestellt werden oder äquivalent, wie viele diskrete Halte der Drehtisch 192 ausführt. Zum Beispiel kann der Objektraum bei 12 Positionen 194 betrachtet werden, die 30 Grad auseinander sind, oder kann er bei 8 Positionen betrachtet werden, die 45 Grad auseinander sind.
2.) Der zweite Parameter N bestimmt, wie viele Bilder (N + 1) bei jeder Drehposition des Drehtischs genommen werden. Diese Eingabe ist dieselbe Größe N, die in dem Abschnitt zum Erzeugen von 3d-Spels beschrieben wurde.
3.) Der dritte Parameter B spezifiziert die Länge der Schieberbasis 196, an der die Kamera 197 gleitet. Diese Größe steuert die äußerste linke und die rechte äußere Position des Bildsensors an dem Schieber und besagt, wie weit sich der Bildsensor zwischen dem ersten und dem N + 1-ten Bild bewegt.

Ein Anwender kann sich dafür entscheiden, auf das Objekt, das modelliert wird, ein Gitter von Linien oder Punkten zu projizieren. Dies bewirkt die Einführung künstlicher Ränder und/oder künstlicher Punkte des Farbdifferentials. Unter Verwendung dieser künstlich erzeugten Ränder können mehr 3d-Spel-Kandidaten an dem Objekt lokalisiert werden, wobei das Modell folglich genauer ist.
Wenn der Anwender mit dem Aufbau zufrieden ist, wird der folgende Prozess befolgt:

a. für jede der R Bildsensorpositionen werden eine Menge von N Bildern aufgenommen;
b. diese Bilder werden verarbeitet und an jeder Position wird eine Menge von 3d-Spels erfasst;
c. die 3d-Spels werden zu einem 3D-Modell kombiniert; und
d. die 3d-Spels werden trianguliert und es wird eine Textur abgebildet, sodass ein photorealistisches 3D-Modell des Objekts verfügbar ist.

Wie oben angegeben wurde, ist der beispielhafte Einzelbildsensor-Objektmodellierer geeignet, seitliche Ansichten eines Objekts zu liefern. Wegen der festen Position des Bildsensors ist es möglich, dass die Oberseite oder die Unterseite eines Objekts unzureichend modelliert wird. In dem nächsten Abschnitt wird ein DLSS-Aufbau beschrieben, der ein Objekt von mehreren Bildsensorpositionen modellieren kann.
Mehrsensor-Bilderzeuger
Der Mehrsensor-Bilderzeuger ist eine Erweiterung des Einzelbildsensor-Modellierers. Tatsächlich ist jeder einzelne Bildsensor in dem Mehrsensor-Bilderzeuger einfach ein Beispiel eines Einzelsensor-Bilderzeugers 198. Der Zweck der Hinzufügung weiterer Bildsensoren ist das Erfassen von Daten von Bereichen wie etwa der Oberseite oder der Unterseite des Objekts, das modelliert wird.
In 23 ist ein beispielhafter Zweibildsensoraufbau 200 gezeigt. Der zweite Bildsensor wird verwendet, um Daten von der Oberseite des Objekts zu erfassen.
Allerdings wird angemerkt, dass die Methodik nicht auf zwei Bildsensoren beschränkt ist. Es können so viele Bildsensoren wie notwendig verwendet werden.
Um das Mehrsensorsystem zu verwenden, richtet der Anwender zunächst die verschiedenen Bildsensorpositionen aus, d. h., setzt der Anwender einen Ursprung fest, der für die von jedem Bildsensor gesammelten Daten gemeinsam ist. Dies erfolgt dadurch, dass in jedem Sensor dieselben drei Punkte lokalisiert werden und die zuvor beschriebenen Koordinatentransformationen angewendet werden.
Nachdem die Koordinatensysteme ausgerichtet worden sind, spezifiziert der Anwender in der beispielhaften Ausführungsform die oben beschriebenen Parameter R, N und B. Diese Parameter können für jeden Bildsensor variieren oder ihnen können allen gemeinsame Werte zugewiesen sein. Wie im Einzelbildsensorfall kann sich der Anwender dafür entscheiden, auf das Objekt ein Gitter zu projizieren, um künstliche Ränder und Punkte des Farbdifferentials einzuführen.
Wenn der Anwender mit dem Aufbau zufrieden ist, werden

1. die 3d-Spels von jedem Bildsensor und von jeder Bildsensorposition gesammelt;
2. die Punkte ausgerichtet; und
3. die Punkt trianguliert und wird eine Textur abgebildet, um die photorealistischen Modelle zu bilden.

Dieses Modell ist geeignet für die Modellierung von Objekten, die in der Mitte von Bildsensoren sind, die sich an verschiedenen Positionen befinden, oder die von solchen Bildsensoren umgeben sind. Da es die Möglichkeit zulässt, zusätzliche 3d-Spels zum Modellieren der Oberseite oder Unterseite eines Objekts zu sammeln, ist es eine Verbesserung gegenüber dem Einzelbildsensorverfahren.
Schwenk- und Neigekopf-Bilderzeuger
Anhand von 24 ist ein beispielhafter Schwenk- und Neigekopf-Bilderzeuger 202 dadurch gebaut, dass ein Bildsensor 198 auf eine Plattform 204 platziert ist, die schwenken (sich in der horizontalen Ebene um die y-Achse drehen) und/oder neigen (sich in der vertikalen Ebene um die x-Achse nach oben und unten drehen) kann. Die Anfangsposition des Modellierers ist nicht wichtig, wobei aber allgemein betrachtet wird, dass sie um jede Achse um null Grad gedreht ist.
Das Schwenk- und Neigekopf-Bilderzeugerverfahren unterscheidet sich von den anderen zwei Verfahren auf verschiedene Weise:

1. Der Brennpunkt der Bilderzeuger-Sensorlinse wird als der Ursprung der Szene betrachtet, die modelliert wird.
2. Das System ist besser geeignet für die Modellierung einer Szene, z. B. des Innern eines Zimmers oder des Innern eines anderen geschlossenen Raums.

Um den beispielhaften Schwenk- und Neigekopf-Modellierer zu verwenden, spezifiziert der Anwender, welche Teilmenge des Raums abgebildet werden soll. Wegen der sich ändernden Entfernungen zu den Grenzen des Raums kann sich das Blickfeld ändern. Zum Beispiel bestimmen die Entfernung zu den Umhüllungsgrenzen und die Größe der Bildsensorlinse das Blickfeld, falls sich der Bildsensor z. B. in seiner Anfangsposition befindet. Falls der Bildsensor daraufhin nach oben oder unten geneigt wird oder nach links oder rechts gedreht wird, kann sich die Entfernung zu der Grenze ändern. Falls die Entfernung zunimmt, wird das Blickfeld größer. Falls die Entfernung abnimmt, wird das Blickfeld kleiner.
Um an die Änderung des Blickfelds anzupassen, bestimmt das DLSS-System automatisch eine Folge von Schwenks und Neigungen, die den gesamten zu modellierenden Bereich abdecken. Die Folge, die das Modell erzeugt, ist hier gegeben:

1. Der Anwender wählt den zu modellierenden Bereich aus einer Direktansicht oder aus zuvor aufgenommenen digitalen Bildern aus.
2. Das DLSS-System berechnet eine Folge von Schwenks und Neigungen – (p_i, t_i) i = 1, 2, ... M, die die Abdeckung des Raums sicherstellen.
3. Für jedes Paar (p_i, t_i) werden durch die zuvor beschriebenen Verfahren 3d-Spels gesammelt.
4. Die Mengen von 3d-Spels werden durch das Verfahren der inversen Transformation kombiniert.
5. Triangulation und Abbilden einer Textur erzeugen das endgültige photorealistische 3d-Modell, wie es in 21 gezeigt ist.

25 zeigt einen alternativen Bilderzeuger 206 für den Bilderzeuger 198 aus 22. Das alternative Bild 206 hat eine Matrix fester Sensoren 208, die die bewegliche Kamera 197 und den Schieber 196 ersetzen. Vorteilhaft können die festen Sensoren 208 zum gleichzeitigen Aufnehmen mehrerer Bilder bei festen Versätzen konfiguriert werden, ohne dass irgendeine Verzögerung erlitten wird, indem veranlasst wird, dass sich eine Kamera zwischen aufeinander folgender Bildern an einer Schieberbasis bewegt. Die Entfernung zwischen den Endsensoren der Matrix fester Sensoren entspricht der Länge der Schieberbasis 196 des Sensors mit einer beweglichen Kamera.
Betrachtungs- und Bilderzeugungshilfsmittel für DLSS-3D-Modelle
Die bevorzugten DLSS-Ausführungsformen modellieren Objekte oder Szenen (Räume) und erzeugen räumlich genaue photorealistische 3D-Modelle der Objekte oder Räume. Somit ist es vorteilhaft, ein Betrachtungshilfsmittel zum Untersuchen und Manipulieren der erzeugten 3D-Modelle zu haben.
26 zeigt ein beispielhaftes Betrachtungs- und Abbildungshilfsmittelfenster 210, das zur Verwendung mit DLSS-3D-Modellen geeignet ist. Das Betrachtungs- und Abbildungshilfsmittel zeigt die erzeugten 3D-Punktwolkendaten oder die texturierten 3D-Modelle 212 an, während es gleichzeitig Navigationshilfsmittel bereitstellt, die die Betrachtung der Modelle unter jedem möglichen dreidimensionalen Winkel ermöglichen. Das Hilfsmittel kann verwendet werden, um texturierte 3D-Modelle vor dem Export der Modelle in andere Anwendungen zu untersuchen, zu messen und ihre Qualität sicherzustellen.
Das Betrachtungshilfsmittel hat Datei-Menü-Auswahlen 214 zum Öffnen von 3D-Modellen, zum Öffnen von 3D-Punktwolken, zum Importieren anderer 3D-Modelltypen, zum Exportieren in andere 3D-Modelltypen und zum Verlassen des Betrachters. Es sind Editieren-Menü-Auswahlen 216 zum Kopieren ausgewählter Mengen von Punkten, zum Ausschneiden ausgewählter Mengen von Punkten, zum Einfügen von Mengen von Punkten von vorherigen Kopier- oder Ausschneideoperationen und zum Löschen von Mengen von Punkten vorgesehen. Außerdem ist eine Auswahl zum Einstellen von Anwenderpräferenzen vorgesehen. Ein Betrachten-Menü 218 stellt Auswahlen zum Einstellen einer Navigationsbetriebsart, zum Einstellen des Blickfelds, zum Zentrieren des betrachteten Modells in dem Betrachtungsbereich und zum Auswählen verschiedener Standpunkte bereit. Außerdem können Vorkehrungen für das Einstellen des Betrachtungsbereichs auf eine Vollbildschirmbetriebsart, zum Anzeigen entweder in einer Drahtmodellbetriebsart oder in einer Betriebsart mit abgebildeten Texturen, zum Zeigen der X-, Y- und Z-Achse oder zum Zeigen der X-, Y- und Z-Ebene in dem Betrachtungsbereich vorgesehen sein. Außerdem können optionale Symbolleisten 220 und Statusleisten 222 vorgesehen sein.
Obgleich diese Übersicht des Betrachtungs- und Abbildungshilfsmittels eine Grundbeschreibung des Hilfsmittels gibt, ist sie keine erschöpfende Beschreibung, wobei bei dem Hilfsmittel zusätzliche Merkmale und Menüs vorgesehen sein können, wie sie im Gebiet gut bekannt sind.
Navigationsbetriebsarten
Das beispielhafte Betrachtungs- und Bilderzeugungshilfsmittel stellt vier Möglichkeiten zum Betrachten von 3D-Modellen bereit. Eine Flugbetriebsart stellt eine flexible Navigation in dem Betrachtungsbereich bereit. Diese Betriebsart ist ähnlich den interaktiven Betriebsarten, die in vielen interaktiven Videospielsystemen verwendet werden. Eine Drehbetriebsart, die Vorgabebetriebsart, ermöglicht das Drehen des 3D-Modells 212 in dem Betrachtungsbereich um jede seiner Achsen, sodass das Modell unter irgendeinem Winkel gesehen werden kann. Eine Schwenkbetriebsart ermöglicht, dass der Anwender in dem Betrachtungsbereich um das 3D-Modell 212 schwenkt. Eine Zoom-Betriebsart stellt das Heranzoomen an das 3D-Modell 212 oder das Wegzoomen von dem 3D-Modell 212 bereit. Obgleich die oben erwähnten Betriebsarten die wesentlichen Anforderungen für die Betrachtung von 3D-Modellen bereitstellen, ist der Umfang des Betrachtungs- und Bilderzeugungshilfsmittels nicht auf diese Betriebsarten beschränkt, wobei weitere Betriebsarten bereitgestellt werden können.
Obgleich bestimmte Ausführungsformen beschrieben worden sind, können einem Anwender oder einem anderen Fachmann auf dem Gebiet Alternativen, Änderungen, Abwandlungen, Verbesserungen und wesentliche Äquivalente einfallen, die derzeit nicht vorhergesehen werden oder nicht vorhergesehen werden können. Dementsprechend sollen die beigefügten Ansprüche, wie sie eingereicht worden sind und geändert werden können, alle diese Alternativen, Änderungen, Abwandlungen, Verbesserungen und wesentlichen Äquivalente umfassen.

Claims

Verfahren zum Abtasten eines diskreten linearen Raums, um digitale 3D-Modelle aus einer erfassten Mehrzahl digitaler Bilder eines Subjekts von einer entsprechenden Mehrzahl von Bildsensorpositionen in der Nähe eines Bildsensorortes zu erzeugen, wobei das Verfahren umfasst: Identifizieren von 3d-Spel-Kandidaten (14), wobei jedes 3d-Spel ein Bildpixel ist, das einem gemeinsamen Punkt auf dem Subjekt entspricht; Zurückweisen von 3d-Spel-Kandidaten (14) anhand einer Differentialanalyse der 3d-Spel-Kandidaten, wobei die verbleibenden 3d-Spels eine Menge akzeptierter 3d-Spels bilden, wobei die Differentialanalyse eine Farbdifferentialanalyse umfasst, die enthält: Bilden einer dreidimensionalen Farbmatrix aus den mehreren digitalen Bildern (140); Suchen in der dreidimensionalen Farbmatrix nach Punkten eines Farbdifferentials (164), das durch plötzliche Farbänderungen identifiziert wird; Bestimmen einer Familie von Linien (170), die durch die Punkte des Farbdifferentials verlaufen; und für jeden 3d-Spel-Kandidaten Bestimmen einer Linie mit maximaler Farbvarianz (172) und Verwerfen des 3d-Spel-Kandidaten, falls die minimale Farbvarianz einen im Voraus festgelegten Schwellenwert übersteigt; und Berechnen von 3D-Koordinaten für jedes akzeptierte 3d-Spel (16), wodurch eine Punktwolke (182) des Subjekts gebildet wird.
Verfahren nach Anspruch 1, das ferner umfasst: Organisieren der erfassten digitalen Bilder in einer dreidimensionalen Pixel-Matrix (140), die mehrere Zeilen und mehrere Spalten besitzt, wobei jede Zeile und jede Spalte einer zweidimensionalen Pixelposition für jedes der Bilder entsprechen, wobei jedes Bild eine entsprechende Position in der dritten Dimension der Matrix einnimmt und wobei jede Position in der dreidimensionalen Matrix wenigstens einen Pixelwert für die entsprechende Pixelposition enthält.
Verfahren nach Anspruch 2, bei der die Zurückweisung auf einer Differentialanalyse des wenigstens einen Pixelwertes für die jeweilige Pixelposition, die jedem 3d-Spel-Kandidaten entspricht, beruht.
Verfahren nach Anspruch 3, das ferner umfasst: Erzeugen eines geometrischen Gitters (18) der Szene oder des Objekts anhand der akzeptierten 3d-Spels einschließlich des Bestimmens einer sichtbaren Fläche jeder geometrischen Entität, die das geometrische Gitter enthält; Abbilden einer Textur (20) auf das geometrische Gitter einschließlich des Bestimmens, welchem der mehreren erfassten digitalen Bilder jede geometrische Entität entspricht, und des Bestimmens eines ausgewählten geometrischen Bereichs des entsprechenden digitalen Bildes für jede geometrische Entität; und Kleben der Textur (20) auf das geometrische Gitter einschließlich des Klebens digitaler Bilddaten aus jedem ausgewählten geometrischen Bereich auf die sichtbare Fläche der geometrischen Entität des geometrischen Gitters.
Verfahren nach Anspruch 4, bei dem das geometrische Gitter ein dreieckiges Gitter ist und die geometrische Entität ein Dreieck ist.
Verfahren nach Anspruch 3, das ferner das Filtern der akzeptierten Menge von 3d-Spels enthält, das umfasst: Ersetzen mehrerer akzeptierter 3d-Spels innerhalb einer Kugel mit einem ersten vorgegebenen Kugelradius durch ein einziges repräsentatives 3d-Spel; und Entfernen akzeptierter 3d-Spels, die als Rauschen bestimmt werden und/oder innerhalb einer Kugel mit einem zweiten vorgegebenen Kugelradius als dünn bevölkert bestimmt werden.
Verfahren nach Anspruch 1, das ferner umfasst: Wiederholen des Erfassens, Identifizierens, Zurückweisens und Berechnens für einen oder mehrere weitere Bildsensororte in Bezug auf das Subjekt, wodurch mehrere Mengen digitaler Bilder und mehrere Mengen von 3d-Spels geschaffen werden; und gegenseitiges Ausrichten der 3d-Spels der mehreren Mengen von 3d-Spels, wodurch eine gemischte Menge aus 3d-Spels mit einem gemeinsamen Ursprung erzeugt wird.
Verfahren nach Anspruch 7, das ferner umfasst: Organisieren der erfassten mehreren Mengen digitaler Bilder in mehrere Mengen dreidimensionaler Pixel-Matrizen, wobei jede Matrix mehrere Zeilen und mehrere Spalten besitzt, wobei jede Zeile und jede Spalte einer zweidimensionalen Pixelposition für jedes der Bilder entsprechen, wobei jedes Bild eine jeweilige Position in der dritten Dimension der Matrix einnimmt und wobei jede Position in der dreidimensionalen Matrix wenigstens einen Pixelwert für die jeweilige Pixelposition enthält.
Verfahren nach Anspruch 8, bei dem das Zurückweisen auf einer Differentialanalyse des wenigstens einen Pixelwertes für die jeweilige Pixelposition, die jedem 3d-Spel-Kandidaten entspricht, beruht.
Verfahren nach Anspruch 9, das ferner umfasst: Erzeugen eines geometrischen Gitters (18) der Szene oder des Objekts anhand der gemischten Menge akzeptierter 3d-Spels einschließlich des Bestimmens einer sichtbaren Fläche jeder geometrischen Entität, die das geometrische Gitter umfasst; Abbilden einer Textur (20) auf das geometrische Gitter einschließlich des Bestimmens, welchem der mehreren erfassten digitalen Bilder jede geometrische Entität entspricht, und des Bestimmens eines ausgewählten geometrischen Bereichs des entsprechenden digitalen Bildes für jede geometrische Entität; und Kleben der Textur (20) auf das geometrische Gitter einschließlich des Klebens digitaler Bilddaten von jedem ausgewählten geometrischen Bereich auf die sichtbare Fläche der geometrischen Entität des geometrischen Gitters.
Verfahren nach Anspruch 10, bei dem das geometrische Gitter ein dreieckiges Gitter ist und die geometrische Entität ein Dreieck ist.
Verfahren nach Anspruch 9, das ferner das Filtern der gemischten Menge von 3d-Spels enthält, das umfasst: Ersetzen mehrerer der 3d-Spels der gemischten Menge von 3d-Spels innerhalb einer Kugel mit einem ersten vorgegebenen Kugelradius durch ein einziges repräsentatives 3d-Spel; und Entfernen von 3d-Spels der gemischten Menge von 3d-Spels, die als Rauschen bestimmt werden und/oder die innerhalb einer Kugel mit einem zweiten vorgegebenen Kugelradius als dünn bevölkert bestimmt werden.
Verfahren nach Anspruch 7, bei dem das gegenseitige Ausrichten das Anwenden bekannter Transformationen auf die Bildsensororte umfasst.
Verfahren nach Anspruch 13, bei dem das Anwenden bekannter Transformationen das Bestimmen homogener Koordinaten und das Anwenden affiner Transformationen umfasst.
Verfahren nach Anspruch 7, bei dem das gegenseitige Ausrichten das Anwenden unbekannter Transformationen auf die mehreren Bildsensor-Koordinatensysteme umfasst.
Verfahren nach Anspruch 15, bei dem das Anwenden unbekannter Transformationen umfasst: Bestimmen einer ersten Menge aus drei Punkten von einem ersten Bildsensorort und einer zweiten Menge aus drei übereinstimmenden Punkten von einem zweiten Bildsensorort; Ausrichten entsprechender Bildsensor-Koordinatensysteme entsprechend der ersten und der zweiten Menge aus drei übereinstimmenden Punkten; und Wiederholen der Bestimmungs- und Ausrichtungsschritte an verbleibenden Bildsensororten.
Verfahren nach Anspruch 7, bei dem die weiteren Bildsensororte weitere Bildsensoren enthalten.
Verfahren nach Anspruch 7, das ferner das Drehen des Subjekts umfasst.
Verfahren nach Anspruch 1, das ferner das Projizieren eines vorgegebenen Gitters oder einer vorgegebenen Menge von Linien auf das Subjekt umfasst.
Verfahren nach Anspruch 1, bei dem der Bildsensor eine Kamera ist, die längs einer geradlinigen Achse beweglich ist.
Verfahren nach Anspruch 1, bei dem der Bildsensor eine feste geradlinige Anordnung aus Sensoren ist.
Verfahren nach Anspruch 1, bei dem das Subjekt wenigstens ein Objekt ist.
Verfahren nach Anspruch 1, bei dem das Subjekt eine Szene oder ein Raum ist.
System zum Erzeugen digitaler 3D-Modelle aus einer erfassten Mehrzahl digitaler Bilder eines Subjekts von einer entsprechenden Mehrzahl von Bildsensorpositionen in der Nähe eines Bildsensorortes, wobei das System umfasst: Mittel zum Identifizieren von 3d-Spel-Kandidaten (14), wobei jedes 3d-Spel ein Bildpixel ist, das einem gemeinsamen Punkt auf dem Subjekt entspricht; Mittel zum Zurückweisen von 3d-Spel-Kandidaten (14) anhand einer Differentialanalyse der 3d-Spel-Kandidaten, wobei die verbleibenden 3d-Spels eine Menge akzeptierter 3d-Spels bilden, wobei die Zurückweisungsmittel Farbdifferentialanalyse-Mittel umfassen, die enthalten: Mittel zum Bilden einer dreidimensionalen Farbmatrix aus den mehreren digitalen Bildern (140); Mittel zum Suchen in der dreidimensionalen Farbmatrix nach Punkten eines Farbdifferentials (164), das durch plötzliche Farbänderungen identifiziert wird; Mittel zum Bestimmen einer Familie von Linien (170), die durch die Punkte des Farbdifferentials verlaufen; und Mittel zum Bestimmen einer Linie mit minimaler Farbvarianz (172) für jeden 3d-Spel-Kandidaten und Verwerfen des 3d-Spel-Kandidaten (16), falls die minimale Farbvarianz einen im Voraus festgelegten Schwellenwert übersteigt; und Mittel zum Berechnen von 3D-Koordinaten für jedes akzeptierte 3d-Spel, wodurch eine Punktwolke (172) des Subjekts gebildet wird.
System nach Anspruch 24, das ferner umfasst: Mittel zum Organisieren der erfassten digitalen Bilder in einer dreidimensionalen Pixel-Matrix (140), die mehrere Zeilen und mehrere Spalten besitzt, wobei jede Zeile und jede Spalte einer zweidimensionalen Pixelposition für jedes der Bilder entsprechen, wobei jedes Bild eine jeweilige Position in der dritten Dimension der Matrix einnimmt und wobei jede Position in der dreidimensionalen Matrix wenigstens einen Pixelwert für die jeweilige Pixelposition enthält.
System nach Anspruch 25, bei dem das Zurückweisen auf einer Differentialanalyse des wenigstens einen Pixelwertes für die jeweilige Pixelposition, die jedem 3d-Spel-Kandidaten entspricht, beruht.
System nach Anspruch 26, das ferner umfasst: Mittel zum Erzeugen eines geometrischen Gitters (18) der Szene oder des Objekts anhand der akzeptierten 3d-Spels einschließlich Mitteln zum Bestimmen einer sichtbaren Fläche jeder geometrischen Entität, die das geometrische Gitter enthält; Mittel zum Abbilden einer Textur (20) auf das geometrische Gitter einschließlich des Bestimmens, welchem der mehreren erfassten digitalen Bilder jede geometrische Entität entspricht, und einschließlich Mitteln zum Bestimmen eines ausgewählten geometrischen Bereichs des entsprechenden digitalen Bildes für jede geometrische Entität; und Mittel zum Kleben der Textur (20) auf das geometrische Gitter einschließlich des Klebens digitaler Bilddaten von jedem ausgewählten geometrischen Bereich auf die sichtbare Fläche der geometrischen Entität des geometrischen Gitters.
System nach Anspruch 27, bei dem das geometrische Gitter ein dreieckiges Gitter ist und die geometrische Entität ein Dreieck ist.
System nach Anspruch 26, das ferner Mittel zum Filtern der akzeptierten Menge von 3d-Spels enthält, die umfassen: Mittel zum Ersetzen mehrerer akzeptierter 3d-Spels innerhalb einer Kugel mit einem ersten vorgegebenen Kugelradius durch ein einziges repräsentatives 3d-Spel; und Mittel zum Entfernen akzeptierter 3d-Spels, die als Rauschen bestimmt werden und/oder die innerhalb einer Kugel mit einem zweiten vorgegebenen Kugelradius als dünn bevölkert bestimmt werden.
System nach Anspruch 28, das ferner umfasst: Mittel zum Wiederholen des Erfassens, Identifizierens, Zurückweisens und Berechnens für einen oder mehrere weitere Bildsensororte, wodurch mehrere Mengen digitaler Bilder und mehrere Mengen von 3d-Spels geschaffen werden; und Mittel zum gegenseitigen Ausrichten der 3d-Spels der mehreren Mengen von 3d-Spels, wodurch eine gemischte Menge von 3d-Spels mit einem gemeinsamen Ursprung erzeugt wird.
System nach Anspruch 30, das ferner umfasst: Mittel zum Organisieren der erfassten mehreren Mengen digitaler Bilder in mehrere Mengen dreidimensionale Pixel-Matrizen, wobei jede Matrix mehrere Zeilen und mehrere Spalten besitzt, wobei jede Zeile und jede Spalte einer zweidimensionalen Pixelposition für jedes der Bilder entspricht, wobei jedes Bild eine jeweilige Position in der dritten Dimension der Matrix einnimmt und wobei jede Position in der dreidimensionalen Matrix wenigstens einen Pixelwert für die jeweilige Pixelposition enthält.
System nach Anspruch 31, bei dem das Zurückweisen auf einer Differentialanalyse des wenigsten einen Pixelwertes für die jeweilige Pixelposition, die jedem 3d-Spel-Kandidaten entspricht, beruht.
System nach Anspruch 32, das ferner umfasst: Mittel zum Erzeugen eines geometrischen Gitters (18) der Szene oder des Objekts anhand der gemischten Menge akzeptierter 3d-Spels einschließlich Mitteln zum Bestimmen einer sichtbaren Fläche jeder geometrischen Entität, die das geometrische Gitter enthält; Mittel zum Abbilden einer Textur (20) auf das geometrische Gitter einschließlich Mitteln zum Bestimmen, welchem der mehreren erfassten digitalen Bilder jede geometrische Entität entspricht, und zum Bestimmen eines ausgewählten geometrischen Bereichs des entsprechenden digitalen Bildes für jede geometrische Entität; und Mittel zum Kleben der Textur (20) auf das geometrische Gitter einschließlich des Klebens digitaler Bilddaten aus jedem ausgewählten geometrischen Bereich auf die sichtbare Fläche der geometrischen Entität des geometrischen Gitters.
System nach Anspruch 33, bei dem das geometrische Gitter ein dreieckiges Gitter ist und die geometrische Entität ein Dreieck ist.
System nach Anspruch 32, das ferner Mittel enthält, um die gemischte Menge von 3d-Spels zu filtern, die umfassen: Mittel zum Ersetzen mehrerer 3d-Spels der gemischten Menge von 3d-Spels innerhalb einer Kugel mit einem ersten vorgegebenen Kugelradius durch ein einziges repräsentatives 3d-Spel; und Mittel zum Entfernen von 3d-Spels aus der gemischten Menge von 3d-Spels, die als Rauschen bestimmt werden und/oder innerhalb einer Kugel mit einem zweiten vorgegebenen Kugelradius als dünn bevölkert bestimmt werden.
System nach Anspruch 30, bei dem die Mittel zum gegenseitigen Ausrichten Mittel umfassen, die bekannte Transformationen auf die Bildsensororte anwenden.
System nach Anspruch 36, bei dem das Anwenden bekannter Transformationen das Bestimmen homogener Koordinaten und das Anwenden affiner Transformationen umfasst.
System nach Anspruch 30, bei dem die Mittel zum gegenseitigen Ausrichten Mittel umfassen, die unbekannte Transformationen auf die mehreren Bildsensor-Koordinatensysteme anwenden.
System nach Anspruch 38, bei dem die Mittel zum Anwenden unbekannter Transformationen umfassen: Mittel zum Bestimmen einer ersten Menge aus drei Punkten von einem ersten Bildsensorort und einer zweiten Menge aus drei übereinstimmenden Punkten von einem zweiten Bildsensorort; Mittel zum Ausrichten jeweiliger Bildsensor-Koordinatensysteme in Übereinstimmung mit der ersten und der zweiten Menge aus drei übereinstimmenden Punkten; und Mittel zum Wiederholen der Bestimmungs- und Ausrichtungsschritte an verbleibenden Bildsensororten.
System nach Anspruch 30, das ferner mehrere Bildsensoren umfasst, wobei jeder Bildsensor so konfiguriert ist, dass er eine entsprechende Mehrzahl digitaler Bilder des Subjekts von einem entsprechenden Bildsensorort erfasst, wobei jedes Bild der entsprechenden Mehrzahl digitaler Bilder von einer Position erfasst wird, die zu den verbleibenden Positionen in der Nähe des entsprechenden Sensorortes versetzt ist.
System nach Anspruch 30, das ferner ein Mittel zum Drehen des Subjekts umfasst.
System nach Anspruch 24, das ferner Mittel zum Projizieren eines vorgegebenen Gitters oder einer vorgegebenen Menge von Linien auf das Subjekt umfasst.
System nach Anspruch 24, bei dem der Bildsensor eine Kamera ist, die längs einer geradlinigen Achse beweglich ist.
System nach Anspruch 24, bei dem der Bildsensor eine feste geradlinige Anordnung aus Sensoren ist.
System nach Anspruch 24, bei dem das Subjekt wenigstens ein Objekt ist.
System nach Anspruch 24, bei dem das Subjekt eine Szene oder ein Raum ist.
Verfahren nach Anspruch 1, bei dem die Differentialanalyse eine Graustufen-Differentialanalyse umfasst, die enthält: Bilden einer dreidimensionalen Graustufenmatrix aus den mehreren digitalen Bildern; Erfassen von Punkten, die Rändern in der dreidimensionalen Graustufenmatrix entsprechen; Bestimmen einer Familie von Linien, die durch die Punkte des Farbdifferentials verlaufen; Bestimmen eines starken Randes in einer ersten Zeile der dreidimensionalen Graustufenmatrix; Bestimmen eines starken Randes in einer letzten Zeile der dreidimensionalen Graustufenmatrix, die dem starken Rand in der ersten Zeile entspricht; Verfolgen von Punkten, die einem Rand entsprechen, der den starken Rand in der ersten Zeile mit dem starken Rand in der letzten Zeile verbindet; und Verwerfen von 3d-Spel-Kandidaten in der dreidimensionalen Graustufenmatrix, für die ein starker Rand in der letzten Zeile nicht bestimmt werden konnte.
System nach Anspruch 24, bei dem die Zurückweisungsmittel ein Graustufendifferentialanalyse-Mittel umfassen, das enthält: Mittel zum Bilden einer dreidimensionalen Graustufenmatrix aus den mehreren digitalen Bildern; Mittel zum Erfassen von Punkten, die Rändern in der dreidimensionalen Graustufenmatrix entsprechen; Mittel zum Bestimmen einer Familie von Linien, die durch die Punkte des Farbdifferentials verlaufen; Mittel zum Bestimmen eines starken Randes in einer ersten Zeile der dreidimensionalen Graustufenmatrix; Mittel zum Bestimmen eines starken Randes in einer letzten Zeile der dreidimensionalen Graustufenmatrix, der dem starken Rand in der ersten Zeile entspricht; Mittel zum Verfolgen von Punkten, die einem Rand entsprechen, der den starken Rand in der ersten Zeile mit dem starken Rand in der letzten Zeile verbindet; und Mittel zum Verwerfen von 3d-Spel-Kandidaten in der dreidimensionalen Graustufenmatrix, für die ein starker Rand in der letzten Zeile nicht bestimmt werden konnte.