PatentDe  


Dokumentenidentifikation DE102005025578A1 07.12.2006
Titel Verfahren zur Charakterisierung von Objekten
Anmelder Universität Hannover, 30167 Hannover, DE
Erfinder Wolter, Franz-Erich, Prof. Dr., 12207 Berlin, DE;
Reuter, Martin, Dipl.-Math., 30161 Hannover, DE;
Peinecke, Niklas, Dipl.-Math., 30539 Hannover, DE
Vertreter GRAMM, LINS & PARTNER GbR, 38122 Braunschweig
DE-Anmeldedatum 01.06.2005
DE-Aktenzeichen 102005025578
Offenlegungstag 07.12.2006
Veröffentlichungstag im Patentblatt 07.12.2006
IPC-Hauptklasse G06F 17/10(2006.01)A, F, I, 20051017, B, H, DE
IPC-Nebenklasse G06F 17/50(2006.01)A, L, I, 20051017, B, H, DE   
Zusammenfassung Ein Verfahren zur Charakterisierung von Objekten hat die Schritte:
a) Beschreiben eines Objektes mit einem elliptischen, selbstadjungierten Eigenwertproblem zur Bildung eines isometrieinvarianten Modells;
b) Bestimmen von Eigenwerten des Eigenwertproblems und
c) Charakterisieren des Objektes durch die Eigenwerte.

Beschreibung[de]

Es besteht ein großer Bedarf, komplexe technische Objekte eindeutig zu charakterisieren, um beispielsweise im Fertigungsprozess Formabweichungen schnell und einfach erkennen zu können oder Repräsentationen technischer Objekte, insbesondere CAD-Zeichnungen, in einer Datenbank wieder auffinden zu können.

Im modernen Informationszeitalter gewinnt der Informationsaustausch zunehmend an Bedeutung. Wirtschaftsgüter entstehen nicht mehr nur durch Herstellung physikalischer Objekte, sondern bereits anhand der Herstellungsinformationen. Ein gravierender Teil des zur Herstellung eines physikalischen Objektes benötigten Aufwands liegt bereits in der Erstellung eines beschreibenden dreidimensionalen Modells des Objektes.

Herkömmlicherweise werden Flächen und Körper mit Hilfe von CAD-Systemen (Computer-Aided-Design) digital beschrieben. Eine große Vielfalt an Objekten wird in diesem Fall mit Hilfe von NURBS-Flächen (Non-Uniform-Rational-B-Splines) dargestellt. Mittlerweile ist ein wichtiger Teil des Produktionsprozesses die Erstellung eines formbeschreibenden digitalen Datenmodells. Die Erstellung eines solchen digitalen Modells ist häufig ein sehr kostenintensiver Prozess. Die Erstellung des physikalischen Objektes aus den digitalen Daten ist zunehmend automatisiert. Es ist daher von großer Bedeutung, die digitalen Modelle in komplexen Datenbanken in der Hand zu haben und Besitzansprüche an diesen digitalen Modellen sichern zu können.

Da auf digitale Datenmodelle in der Regel vielseitig zugegriffen wird, zum Beispiel bei Präsentationen für mögliche Käufer oder im Design-Prozess von verschiedenen Designern, ist es meist leicht möglich, eine unberechtigte Kopie der Daten zu erlangen. Die immer stärker verbreitete Kommunikation über das Internet steigert die Wahrscheinlichkeit, dass Datenmodelle ausspioniert werden. Hinzu kommt die Möglichkeit, eine komplett andere Repräsentation des Datenmodells zu wählen, oder ein Datenmodell sogar mit Hilfe von Laserscans oder anderen Messungen aus einem physikalischen Objekt zu rekonstruieren, so dass eine unerlaubte Kopie meist kaum nachzuweisen ist.

Es ist daher eine übliche Methode, dem digitalen Modell ein so genanntes „digitales Wasserzeichen" aufzuprägen. So lässt sich der rechtmäßige Besitzer eines Modells im Nachhinein besser identifizieren. Dabei ist allerdings unbedingt notwendig, dass das Wasserzeichen nicht durch Datenkonvertierungen oder durch absichtliche Manipulation zerstört werden kann. Bei digitalen Wasserzeichen wird grundsätzlich zwischen sichtbaren Wasserzeichen unterschieden, die vom Menschen im Modell erkannt werden können, und unsichtbaren Wasserzeichen, die mit Hilfe eines Computerprogramms aus dem Datenmodell extrahiert werden können.

Digitale Wasserzeichen werden insbesondere für Bilddaten, Videodaten und Audiodaten eingesetzt. Viele dieser Techniken sind bei dreidimensionalen Modellen von Objekten allerdings leicht verwundbar, da versteckte Daten, die durch kleine Verschiebungen der Kontrollpunkte oder durch Anbringen von Mustern im Gitternetz aufgeprägt werden, sich häufig zum Beispiel mit Hilfe von Koordinatentransformationen, zufälligem Rauschen oder anderen Aktionen leicht zerstören lassen. Hinzu kommt, dass sich diese Verfahren nicht direkt auf CAD-basierte Datenmodelle übertragen lassen, die üblicherweise in der NURBS oder B-Spline Repräsentation vorliegen. Gerade bei dieser Art von Datenmodellen ist ein Kopierschutz wünschenswert, da diese Datenmodelle die reichste Gestaltvielfalt bei flächenberandeten Frei-Form-Objekten bieten.

In R. Ohbuchi, H. Masuda, M. Aono: "Watermarking Three-Dimensional Polygonal Models Through Geometric and Topological Modifications", in: IEEE Journal on Selected Areas in Communications, 16 (1998), Nr. 14, Seiten 551 bis 560 ist ein Verfahren zur Einbindung digitaler Wasserzeichen in dreidimensionale Polygonmodelle beschrieben, bei dem die Eckpunkte und die Topologie des 3D-Modells verändert werden. Es werden Informationen in die zur Beschreibung eines 3D-Modells genutzten Dreiecke eingebettet, indem die Verhältnisse der Kanten oder der Winkel entsprechend angepasst werden. Eine zweite Methode nutzt die Verhältnisse von Tetraedervolumen, die unter affinen Transformationen invariant sind, um Informationen zu speichern. Dabei werden wieder Eckpunkte leicht verschoben, um die Volumenverhältnisse anzupassen. Es werden weiterhin Methoden vorgeschlagen, die die topologische Struktur der Triangulierung verändern, indem zum Beispiel sichtbare Änderungen durch Unterteilung einiger Dreiecke eingeführt werden.

In Yeo, B.; Yeung, M.: „Watermarking 3D Objects for Verification", in: IEEE Computer Graphics and Applications 19 (1999), Nr. 1, Seiten 36 bis 45 ist ein Verfahren zum Einbetten von Wasserzeichen in 3D-Modelle beschrieben, bei dem Eckpunkte von Dreiecken derart verschoben werden, dass gewisse Hash-Funktionen der Eckpunkte mit Hash-Funktionen der Zentren der Nachbardreiecke übereinstimmen. Eine unautorisierte Veränderung an einem Original lässt sich dadurch feststellen, dass diese Information zerstört wird.

Aus Benedens, O.: „Geometry-Based Watermarking of 3D Models", in: IEEE Computer Graphics and Applications 19 (1999), Nr. 1, Seiten 46 bis 55 ist ein Verfahren zum Einbetten von Wasserzeichen in die Flächennormalen eines Objektmodells bekannt. Diese Methode, die gruppenähnliche Normale zur Speicherung von Informationen verändert, ist bei einer dichten Ausgangszerlegung resistent gegen Änderungen der Zerlegung, sowie zum Beispiel Polygonvereinfachungen.

In Kanai, S.; Date, N.; Kishinami, T.: „Digital Watermarking for 3D Polygons using Multiresolution Wavelet Decomposition", in: Proceedings of the Sixth IFIP WG 5.2/GI International Workshop on Geometric Modeling: Fundamentals and Applications, 1998, Seiten 296 bis 307 ist ein Verfahren zur Einbindung von Wasserzeichen im Frequenzbereich eines 3D-Modells offenbart. Hierzu werden Wavelet-Transformationen sowie Multiskalendarstellungen genutzt, um die Informationen im Wavelet-Koeffizientenvektor auf einer oder verschiedenen Auflösungsstufen unterzubringen. Abhängig von der Stufe lässt sich die Robustheit des Verfahrens steuern, das resistent gegen affine Transformationen sowie Polygonvereinfachungen ist.

In Fornaro, C.; Sanna, A.: „Public Key Watermarking for Authentication of CSG Models", in: Computer Aided Design 32 (2000), Nr. 12, Seiten 727 bis 735 ist ein Verschlüsselungsverfahren basierend auf öffentlichen Schlüsseln (public key) zur Authentifizierung von Modellen zur Beschreibung von Objekten mit der Soliden-Körper-Geometrie beschrieben. Um Informationen in den Solids zu speichern werden neue Knoten in den so genannten CSG-Baum des Modells eingehängt. Durch Null-Volumen-Objekte, wie zum Beispiel eine Kugel mit dem Radius Null, bleiben die Wasserzeichen unsichtbar. Allerdings ist diese Technik anfällig gegenüber böswilligen Veränderungen durch den Benutzer.

Aus Ohbuchi, R.; Masuda, H.; Aono, M.: „A Shape-Preserving Data Embedding Algorithm for NURBS Curves and Surfaces", in: Proceedings of the International Conference on Computer Graphics, IEEE Computer Society, 1999, Canmor, Canada, June 4 bis June 11, Seiten 180 bis 187 ist für Non-Uniform Rational B-Spline (NURBS) Kurven und Oberflächen das Anbringen von Wasserzeichen mit Hilfe von rationalen linearen Parametrisierungen bekannt. Diese Methode ist einfach anzuwenden und behält die exakte Form des NURBS-Objektes bei, da eine redundante Reparametrisierung genutzt wird. Die Wasserzeicheninformation lässt sich jedoch leicht entfernen, ohne die Qualität der Fläche zu reduzieren, indem zum Beispiel das Objekt neu aproximiert wird.

Durch das Einbetten von Wasserzeichen nach den oben genannten Verfahren können polygonale 3D-Modelle geschützt werden, die zum Beispiel mit der Virtual Reality Modeling Language VRML beschrieben werden. Da in CAD-Konstruktionen die Modelle meist als Frei-Form-Kurven und -Flächen, zum Beispiel B-Splines oder NURBS vorliegen, sind bis auf das letztgenannte Verfahren die Methoden nicht zum Schutz von CAD-Daten geeignet. Da die Benutzung, spezieller CAD-Systeme und die Zusammenarbeit von technischen Konstrukteuren via Internet im Konstruktionsbereich inzwischen sehr verbreitet ist, besteht ein dringender Bedarf, CAD-Daten zu schützen.

In der US-2003-0128209 ist ein Verfahren beschrieben, bei dem die Form der Objekte verglichen werden. Hierzu werden die zu vergleichenden Objekte zunächst mit Hilfe von Volumen und Trägheitsmomenten in Deckung gebracht. Anschließend werden die Objekte mit einem schwachen, einem mittleren und einem starken Test verglichen. Der schwache und mittlere Test wird an Knotenpunkten durchgeführt und der starke Test basiert auf Vergleichen von isolierten Nabelpunkten. Aufgrund dieser Tests ist es schließlich möglich eine Aussage darüber zu treffen, ob es sich bei einem der Objekte um eine eventuell illegale Kopie des Originals handelt. Nachteilig müssen die Objekte erst aufwendig in Deckung zueinander gebracht werden, um den Vergleich durchzuführen.

Aufgabe der Erfindung ist es daher, ein verbessertes Verfahren zur Charakterisierung von Objekten zu schaffen, das insbesondere zum Schutz von technischen CAD-Zeichnungen und Auffinden konstruierter technischer Objekte in einer komplexen CAD-Zeichnungsdatenbank genutzt werden kann.

Die Aufgabe wird mit dem gattungsgemäßen Verfahren gelöst durch die Schritte:

  • a) Beschreiben eines Objektes mit einem elliptischen, selbstadjungierten Eigenwertproblem zur Bildung eines isometrieinvarianten Modells;
  • b) Bestimmen von Eigenwerten; und
  • c) Charakterisieren des Objektes durch die Eigenwerte.

Durch die Charakterisierung des Objektes anhand der Eigenwerte eines elliptischen, selbstadjungierten Eigenwertproblems ggf. mit Randbedingungen ist ein Vergleich von Objekten durch Vergleich der Eigenwertsequenz eines Objektes möglich, ohne dass die Lage des Objektes im Raum, insbesondere eine Rotation den Vergleich beeinflusst. Das Verfahren ist unabhängig von der Darstellung der Objekte, insbesondere von der Parametrisierung. So ist es möglich, mit unterschiedlichen Modellen, z. B. NURBS, triangulierte Flächen, Höhenfunktionen, beschriebene Objekte unmittelbar ohne Modelltransformation miteinander zu vergleichen. Damit das Eigenwertproblem isometrieinvariant ist, hängt der Operator nur von der Metrik ab, d. h. der Entfernung von je zwei Punkten auf der Fläche zueinander. Dies hat den Vorteil, dass Flächenverformungen den Vergleich nicht beeinträchtigen, sofern bei den Flächenverformungen die geodätische Entfernung jeweils zweier beliebiger Punkte zueinander nicht geändert wird.

Die Berechnung von elliptischen, selbstadjungierten Eigenwertproblemen auf Objekten beispielsweise mittels der Finite-Elemente-Methode ist an sich hinreichend bekannt. Die theoretischen Grundlagen derartiger elliptischer Differentialgleichungen sind in Bronstein, Semendjajew: „Taschenbuch der Mathematik", BSB Teubner, 1987, Seite 478 beschrieben. Darüber hinaus werden die Eigenwerte nunmehr als charakteristische Werte zur Beschreibung des Objektes genutzt.

Besonders vorteilhaft ist es, wenn das Difterentialgleichungssystem einen Laplace-Beltrami-Operator aufweist. Es hat sich herausgestellt, dass mit diesem Laplace-Beltrami-Operator eine für die oben genannten Zwecke besonders brauchbare Charakterisierung möglich ist. Insbesondere kann die Wirkung einer uniformen Skalierung auf die Eigenwerte wieder rückgängig gemacht werden.

Das Differentialgleichungssystem kann beispielsweise eine Helmholtz-Differentialgleichung nach der Formel &Dgr;f = – &lgr;f mit dem Operator &Dgr; den Eigenfunktionen f und den Eigenwerten &lgr; sein. Eine solche Helmholtz-Differentialgleichung hat den Vorteil, dass sie in an sich bekannter Weise zur Bildung eines isometrieinvarianten Modells eines technischen Objektes führt.

Die Charakterisierung der Objekte wird vorzugsweise auf eine Basisskalierung normiert durch Division der Eigenwerte durch den ersten Wert ungleich Null, der nach Größe der Eigenwerte sortierten Sequenz von Eigenwerten.

Eine Normierung der Charakterisierung der Objekte auf eine Basisskalierung kann aber auch erfolgen durch die Schritte:

  • a) Bestimmen einer Ausgleichsfunktion f(n) = c nd/2 durch eine festgelegte Anzahl N von Eigenwerten beginnend vom Anfang der Sequenz mit dem Skalierungsfaktor c, der Position n des Eigenwertes in der Sequenz und der Dimension d des Objektes; und
  • b) Skalieren der Eigenwerte mit so gewähltem Skalierungsfaktor, dass die Ausgleichsfunktion auf eine festgelegte Normfunktion abgebildet wird, z. B. indem die Eigenwerte durch den Skalierungsfaktor c dividiert werden.

Bei der Charakterisierung der Objekte mit einer Sequenz von Eigenwerten nach dem beschriebenen Verfahren führt eine Vergrößerung/Verkleinerung des Objektes zu einer Veränderung sämtlicher Eigenwerte einer Sequenz um den gleichen Skalierungsfaktor. D. h., dass eine Normierung durch die Schritte a) bis c) eine unmittelbare Vergleichbarkeit der Eigenwertsequenz zweier Objekte unabhängig von ihrer Größe ermöglicht.

Es kann aber auch eine Normierung der Charakterisierung der Objekte auf einen Einheitsflächeninhalt oder ein Einheitsvolumeninhalt durch Multiplikation der Eigenwerte mit dem Wert des Flächeninhalts (A) oder dem Volumeninhalt hoch 2/3 (V2/3) erfolgen.

Besonders vorteilhaft ist es, wenn eine Skalierung der Charakterisierung der Objekte durch Multiplikation der Eigenwerte mit einem Skalierungsfaktor s2 durchgeführt wird, wobei s der Skalierungsfaktor für das Objekt ist. Bei bekanntem Skalierungsfaktor wird damit die Tatsache ausgenutzt, dass sämtliche Eigenwerte der Sequenz von zur Charakterisierung eines Objektes dienender Eigenwerte um den gleichen Skalierungsfaktor angepasst werden.

Bei Volumenkörpern ist es vorteilhaft, das Spektrum des Körpers sowie das Spektrum der Hülle des Körpers (des 2-dimensionalen Randes) zu berechnen und für das Eigenwertproblem zu nutzen. Damit ist eine noch genauere Charakterisierung möglich.

Die Charakterisierung der Objekte kann dazu genutzt werden, die Formähnlichkeit von Objekten durch Bestimmen der Ähnlichkeit der Eigenwertsequenzen bzw. skalierten Eigenwertsequenzen der zu vergleichenden Objekte zu vergleichen. Dieser Vergleich kann genutzt werden, um beispielsweise Repräsentationen von Objekten in Datenbanken aufzufinden, d. h. beispielsweise Datenbanken mit CAD-Zeichnungen anhand der Eigenwertsequenzen zu durchsuchen. Weiterhin kann der Formähnlichkeitsvergleich genutzt werden, um Urheberrechte an Objektrepräsentationen zu sichern. Weiterhin kann in der Produktion von Waren der Formähnlichkeitsvergleich ausgenutzt werden, um durch automatische Formerfassung der produzierten Objekte (z. B. durch Kameraaufnahmen oder Laserscans), durch Transformieren der Objekte in ein 2D-/3D-Modell und durch Bestimmen der Eigenwertsequenzen für dieses Modell Formabweichungen zu erkennen.

Die Formähnlichkeit kann beispielsweise durch Bestimmen des euklidischen Abstands d(&lgr;, &mgr;)n der Eigenwertsequenzen für zwei Objekte nach der Formel erfolgen, wobei &lgr;i die ggf. normierten Eigenwerte für ein erstes Objekt, &mgr;i die Eigenwerte für ein zweites Objekt und n die Anzahl der Eigenwerte einer jeweiligen Sequenz ist.

Es ist aber auch möglich, andere geeignete Metriken zum Vergleich der ggf. normierten Eigenwertsequenzen zu verwenden. Dabei ist es vorteilhaft, die Korrelation zwischen den Eigenwerten der Sequenz eines ersten Objektes und den Eigenwerten der Sequenz eines zweiten Objektes zu bestimmen. Diese Methode hat den Vorteil, dass die Korrelation unabhängig von der Skalierung ist.

Vorteilhaft ist es auch, den sogenannten Hausdorff-Abstand zu berechnen, bei dem jeder Wert der Eigenwerte einer Sequenz mit jedem anderen Eigenwert der Sequenz des Vergleichsobjektes verglichen wird. Die Position der Eigenwerte spielt daher keine Rolle.

Aus der Sequenz der Eigenwerte eines Objektes können vorteilhafterweise geometrische Daten für das Objekt extrahiert werden, wie zum Beispiel der Flächeninhalt der Fläche, das Volumen des Körpers, die Länge des Randes und/oder der Flächeninhalt der Randfläche des Objektes. Durch Bestimmen der Euler-Charakteristik aus der Sequenz von Eigenwerten kann auch eine Ermittlung der Anzahl von Löchern in einer planaren Fläche mit glattem Rand oder des Genus einer geschlossenen Fläche erfolgen.

Zur Charakterisierung von Grauwertbildern ist es vorteilhaft, diese in Höhenfunktionen umzuwandeln, indem jedem Punkt des Bildes eine seinem Grauwert entsprechende Höhe zugewiesen wird. So entsteht eine in den dreidimensionalen Raum eingebettete zweidimensionale Fläche, für die die Eigenwerte nach dem oben beschriebenen Verfahren bestimmt werden können. Für Farbbilder kann analog eine verallgemeinerte Höhenfunktion erstellt werden, die jedem Bildpunkt drei Höhenwerte in Abhängigkeit von den jeweiligen Farbkomponenten (z. B. rot, blau, grün oder Luminanz, Chrominanz-rot, Chrominanz-blau) zuordnet. Es entsteht so eine in den fünfdimensionalen Raum eingebettete zweidimensionale Fläche, für die die Eigenwerte bestimmt werden können. Alternativ lässt sich auch jeder Farbkanal als unabhängige Höhenfunktion auffassen, so dass drei separate Spektren zu charakterisieren sind.

Das Verfahren kann vorzugsweise aus Performancegründen als Hardware oder als Computerprogramm mit Programmcodemitteln implementiert werden, die das vorstehend beschriebene Verfahren ausführen, wenn das Computerprogramm auf einem Rechner ausgeführt wird.

Die Erfindung wird nachfolgend anhand der beigefügten Zeichnungen beispielhaft näher erläutert. Es zeigen:

1 Flussdiagramm eines Verfahrens zur Charakterisierung von Objekten, Extrahieren von geometrischen Daten und Vergleichen der Formähnlichkeit von Objekten;

2a bis c B-Spline-Darstellung von zwei Ansichten des Rückens einer Schaufensterpuppe A und des Rückens einer zweiten Schaufensterpuppe B.

Die 1 lässt ein Flussdiagramm des Verfahrens zur Charakterisierung von Objekten erkennen.

In einem ersten Schritt CALC EW wird eine Sequenz von Eigenwerten eines elliptischen, selbstadjungierten Differentialgleichungssystems berechnet, mit dem das Objekt beschrieben wird. Hierzu wird beispielsweise die Helmholtz-Differentialgleichung &Dgr;f = – &lgr;f gelöst. Dies ist auch als Laplacesches Eigenwertproblem bekannt. Dabei ist &Dgr; der Laplace-Beltrami-Operator. Die abzählbar vielen Lösungen f der Helmholtz-Differentialgleichung werden Eigenfunktionen und &lgr; Eigenwerte genannt. Diese Eigenwerte &lgr; sind positiv und bilden das so genannte Spektrum des Objektes. Es ist möglich, die Helmholtz-Differentialgleichung für 2D-Flächen (planare oder gekrümmte Flächen im Raum) und auch für 3D-Körper zu berechnen. Die Darstellung des Objektes spielt hierbei keine Rolle, da sich die numerische Berechnung der Helmholtz-Differentialgleichung mit gleichen Ergebnissen für die Eigenwerte prinzipiell bei verschiedensten Darstellungsformen durchführen lässt, wie zum Beispiel bei parametrisierten Flächen (z. B. NURBS), facettierten Flächen und Körpern, implizit gegebene Flächen, Höhenfunktionen (z. B. abgeleitet aus Bildern) usw.

Die Berechnung der Sequenz von Eigenwerten &lgr; (Spektrum) erfolgt mit Hilfe numerischer Verfahren zur Lösung der Helmholtz-Differentialgleichung. Dies kann zum Beispiel mit Hilfe der Finiten-Elemente-Methode durchgeführt werden, die aufgrund ihrer Flexibilität sowohl bei Flächen als auch bei Körpern angewendet werden kann. Alternative Methoden zur schnelleren oder genaueren Berechnung der Eigenwerte &lgr; sind in Sonderfällen (z. B. bei planaren Polygonen) verfügbar, bei denen gewisse Kenntnisse über die Lösungen der Helmholtz-Differentialgleichung ausgenutzt werden.

In dem Schritt CALC EW werden die Eigenwerte &lgr; so genau wie möglich berechnet, um für einen anschließenden Vergleich der Eigenwertsequenzen (Fingerabdrücke) von Objekten störende Rechenungenauigkeiten zu vermeiden. Zur möglichen Extraktion von geometrischen Daten ist zudem eine große Anzahl von Eigenwerten &lgr; erforderlich.

Das Spektrum eines Objektes wird somit durch die Eigenwerte &lgr; charakterisiert, die als Sequenz von positiven Zahlen der Größe nach sortiert sind. Dabei ist der erste Eigenwert A genau dann Null, wenn das Objekt nicht berandet ist. Da das Spektrum eine Isometrie-Invariante ist, sich also unter isometrischen Transformationen nicht verändert, ist das Spektrum unabhängig von Position (Translation und Rotation) und Darstellung des Objektes (insb. Parametrisierungsunabhängigkeit).

In einem nächsten Schritt „ID?" wird entschieden, ob nach der Ähnlichkeit von mindestens zwei Objekten oder nur die Identität eines Objektes geprüft werden soll. In beiden Fällen wird anschließend bestimmt, ob die Eigenwertsequenzen normiert werden sollen. Dies erfolgt im Schritt „Norm?".

Die Normierung kann beispielsweise nach den folgenden Verfahren erfolgen:

  • a) Die Eigenwertsequenzen werden nach dem ersten Eigenwert der Sequenz normiert. Hierzu wird jeder Eigenwert &lgr; der Sequenz durch den ersten Eigenwert &lgr; der Sequenz dividiert, der größer als Null ist.
  • b) Bei dem Normierungsverfahren „Gerade" wird eine Ausgleichsgerade durch die ersten N Eigenwerte &lgr; berechnet. Anschließend wird die Sequenz der Eigenwerte &lgr; so skaliert, dass die Steigung der Ausgleichsgeraden einem definierten Wert, z. B. eins, entspricht. Es kann aber auch allgemein eine Ausgleichsfunktion so skaliert werden, dass sie auf eine Normfunktion abgebildet wird. Dies ist z. B. bei höheren Dimensionen nötig.
  • c) In einem dritten Verfahren wird zunächst der Flächeninhalt A aus den Eigenwerten &lgr; berechnet („CALC AREA"). Anschließend werden im Schritt „Fläche" die Eigenwerte A einer Sequenz mit dem Flächeninhalt A multipliziert. Optional kann aber auch eine Bestimmung des Volumens V bei Körpern berechnet werden und eine Multiplikation der Eigenwerte &lgr; mit V2/3 erfolgen.
  • d) In einem optionalen Verfahren „Fläche EXT" kann auch eine Normierung der Eigenwerte A bezüglich des tatsächlichen Flächeninhalts A oder Volumens V2/3 des Objektes erfolgen.

Durch das Normieren der Eigenwerte &lgr; gemäß Verfahren a) können Skalierungen ignoriert werden. Eine leichte Deformation eines Objektes führt zudem zu sehr ähnlichen Eigenwerten &lgr;, da die Eigenwerte &lgr; stetig von der Form der Fläche des Körpers abhängen. Es lassen sich auch leicht deformierte Objekte identifizieren.

Für den Fall der Ähnlichkeitsuntersuchungen kann das erste Normierungsverfahren a) oder die drei weiteren Normierungsverfahren b), c) oder d) ausgewählt werden „Modus?"1,2,3,4.

Die Normierung der Eigenwerte &lgr; mit V2/3 ist durch das Weylsche asymptotische Verteilungsgesetz begründet, nach dem sich die Eigenwerte &lgr;n eines d-dimensionalen Objektes wie c(d)·n2/d/V2/d verhalten, wobei c(d) eine dimensionsabhängige Konstante, n die Nummer des Eigenwertes A in einer nach Größe der Eigenwerte A geordneten Eigenwertesequenz und V das d-dimensionale Volumen des Objektes ist. Im Fall d = 2 ist V z. B. der Flächeninhalt. Um die Spektren auf eine vom Volumen und damit von der Skalierung unabhängige Form zu bringen ist es also nötig, die Eigenwerte mit dem Faktor V2/d zu multiplizieren. Für zwei-dimensionale Objekte ist das einfach der Flächeninhalt und für drei-dimensionale Körper das Volumen V2/3.

Vor der Normierung kann in einem Schritt „CROP" vorzugsweise nach der Flächenberechnung „CALC AREA" eine Kürzung der Sequenz von Eigenwerten auf etwa 10 bis 100 Eigenwerte A erfolgen, die für die Normierung und Ähnlichkeitsberechnung in der Regel ausreichen.

Es ist bekannt, dass eine asymptotische Entwicklung der so genannten „Hegt Trace Z(t)" (der Spur des Heat-Kernels) existiert, wobei Z(t) nur von Eigenwerten &lgr; und einem Zeitparameter t abhängt. Die ersten Koeffizienten dieser asymptotischen Entwicklung sind durch das Volumen des Körpers (bzw. Flächeninhalt), den Randflächeninhalt (bzw. Randlänge) und in einigen Fällen durch die Euler Charakteristik des Objektes festgelegt. Um diese Größe numerisch zu berechnen kann die Heat Trace Z(t) in eine neue Funktion X(x) durch Substitution von x: =√(t) und Multiplikation mit xd umgeformt werden, so dass bei hinreichend vielen Eigenwerten die Berechnung einiger Stützstellen von X und damit eine Extrapolation für t→0 möglich ist. Auf diese Weise ist es möglich, die geometrischen Größen aus einem Spektrum bei begrenzter Anzahl von Eigenwerten zu extrahieren und für die Normierung bzw. Klassifizierung heranzuziehen. Zumeist reichen hierfür die ersten ca. 500 Eigenwerte der nach Größe sortierten Eigenwertsequenz aus.

Die Normierung bzw. Skalierung der Eigenwerte &lgr; ist nur dann notwendig, wenn Vergleichsobjekte nicht in einem absoluten Maßstab gespeichert sind und bei einem Vergleich die Größe des Objekts unberücksichtigt bleiben soll. Dieser Fall tritt zum Beispiel dann auf, wenn ein vermeidlich gestohlener Datensatz mit dem Original verglichen werden soll. Es kann dann durchaus vorkommen, dass sich die beiden Objekte stark in Ihrer Größe unterscheiden, aber bezüglich ihrer Form nach einer Skalierung wieder identisch sind.

In einem nächsten Schritt „DIST?" erfolgt ein Vergleich der Formidentität zweier Objekte. Hierzu werden die Eigenwerte &lgr; einer ersten Sequenz für ein erstes Objekt mit den Eigenwerten &mgr; einer zweiten Sequenz für ein zweites Objekt miteinander verglichen. Durch die vorhergehende Skalierung der Eigenwerte &lgr;, &mgr; ist ein Vergleich unabhängig von der Größe der Objekte möglich.

Der Formähnlichkeitsvergleich kann beispielsweise durch die Bestimmung des euklidischen Abstands zweier Sequenzen von Eigenwerten &lgr; = (&lgr;1, &lgr;2,..., &lgr;n) und &mgr; = (&mgr;1, &mgr;2,..., &mgr;n) erfolgen („EUKLID"). Der euklidische Abstand d(&lgr;, &mgr;)n berechnet sich nach der Formel:

Je formähnlicher die beiden verglichenen Objekte sind, umso kleiner wird der euklidische Abstand d(&lgr;, &mgr;)n.

Es ist aber auch möglich, den sogenannten Hausdorff-Abstand zu berechnen. Hierzu wird jeder Eigenwert &lgr; der ersten Sequenz für das erste Objekt mit jedem Eigenwert &mgr; der zweiten Sequenz für das zweite Objekt verglichen. Dabei spielt insbesondere die Position der Eigenwerte &lgr;, &mgr; keine Rolle. Dieses Verfahren ist als „Hausdorff" in der 1 skizziert.

Eine weitere Möglichkeit ist die Berechnung der Korrelation zweier Eigenwertsequenzen („Korrelation"). Eine Extraktion geometrischer Daten und Skalierung der Eigenwerte ist dann nicht erforderlich, da die Korrelation unabhängig von der Skalierung ist. Die Korrelation kann allerdings bei sehr unterschiedlichen Objekten unter Umständen relativ hoch sein, so dass Korrelationswerte sehr eng beieinander liegen können, obwohl keine Formähnlichkeit vorliegt. Das Verfahren ist daher nicht immer eindeutig.

Die 2a) und 2b) lassen eine Modelldarstellung des Rückens einer ersten Schaufensterpuppe A in zwei unterschiedlichen perspektivischen Ansichten A) und B) erkennen. Das Objekt A ist als B-Spline-Patch modelliert. Die Darstellung in 2b) sieht zwar vollkommen anders als die beiden anderen Darstellungen aus, zeigt jedoch die identische Schaufensterpuppe A nach Rotation, Verschiebung, Skalierung und Graderhöhung der Bezierfunktionen.

Die 2c) zeigt hingegen einen modifizierten Rücken einer zweiten Schaufensterpuppe B mit engerer Taille und schmaleren Schultern. Die B-Spline-Patches A und B sind sehr ähnlich, aber nicht identisch.

Für die B-Spline-Patches der Darstellungen aus der 2a), b) und c) wurden die Eigenwerte A der Helmholtz-Differentialgleichung unter Verwendung eines Laplace-Betrami-Operators berechnet. Weiterhin wurden die Einheitswerte A für ein Einheitsquadrat Q berechnet. Die ersten zehn Eigenwerte sind in der folgenden Tabelle unnormiert aufgeführt:

Die Distanz 100 zu A ist der euklidische Abstand der auf 100 Werte reduzierten Sequenz von Eigenwerten &lgr;i zur Sequenz von Eigenwerten &lgr; für die Fläche A.

Es ist erkennbar, dass sich die Sequenzen von Eigenwerten der Darstellung aus 2c) von der Darstellung aus 2a) weniger unterscheidet, als die Darstellung aus 2b) von der Darstellung aus 2a), obwohl die 2a) und 2b) das identische Objekt A beschreiben. Der Grund hierfür ist, dass bei einer Skalierung des Objektes auch die Eigenwerte A skaliert werden. Um diesen Effekt auszugleichen, werden die Eigenwerte &lgr;; der Sequenzen daher so skaliert, dass jeweils der erste Eigenwert &lgr; übereinstimmt.

In der nachfolgenden Tabelle sind die entsprechend normierten Eigenwerte &lgr;i der Sequenzen sowie die euklidischen Abstände zum B-Spline-Patch A aufgeführt.

Es ist erkennbar, dass eine sehr große Formähnlichkeit zwischen den B-Spline-Patches A und A' vorliegt, d. h. der euklidische Abstand der 100 kleinsten Eigenwerte × lediglich 0,0031 beträgt, obwohl A' durch Translation, Rotation, Skalierung und Graderhöhung aus A hervorgegangen ist und eigentlich vollkommen unähnlich zu A aussieht. Weiterhin wird deutlich, dass, obwohl das Objekt B dem Objekt A stark ähnelt, die euklidische Distanz von 4,7462 hat und damit nicht identisch zu dem Objekt A ist. Im Vergleich zum Einheitsquadrat Q, dass mit einer Distanz von 98 relativ weit von dem Objekt A entfernt liegt, kann zudem noch der Grad der Ähnlichkeit objektiv bestimmt werden.

Eine weitere Möglichkeit des Vergleichs von Eigenwertsequenzen besteht darin, die Ausgleichsgeraden der ersten Eigenwerte &lgr;1, &lgr;2,..., &lgr;n zu berechnen und dann die Steigungen der Ausgleichsgeraden anzupassen. Dies ist in der nachfolgenden Tabelle für die Objekte A, A', B und dem Einheitsquadrat Q aufgeführt, wobei die Ausgleichsgeraden jeweils die Steigung 4&pgr; haben.

Es ist erkennbar, dass die Identität der Objekte A und A' mit einer Distanz von 0,0681 nicht mehr so eindeutig wie bei der Normierung der Einheitswerte gemäß Tabelle 2 ist. Das Verfahren ist jedoch gut geeignet, um Ähnlichkeiten zu erkennen.

Durch das Verfahren zur Charakterisierung von Objekten ist eine Identifikation und ein Vergleich von Flächen und Körpern mit Hilfe der Eigenwertsequenzen möglich, um zum Beispiel Objekte in großen Datenmengen aufzufinden oder um ein Kopierschutzverfahren für parametrisierte Flächen und Körper zu erhalten. Dabei ist ein Vergleich möglich, ohne dass eine räumliche Deckung der Objekte (Translation, Rotation, Skalierung) erforderlich ist und ohne dass eine gemeinsame Repräsentation der Daten notwendig ist.


Anspruch[de]
Verfahren zur Charakterisierung von Objekten mit den Schritten:

a) Beschreiben eines Objektes mit einem elliptischen, selbstadjungierten Eigenwertproblem zur Bildung eines isometrieinvarianten Modells;

b) Bestimmen von Eigenwerten (&lgr;) des Eigenwertproblems; und

c) Charakterisieren des Objektes durch die Eigenwerte (&lgr;).
Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass das Eigenwertproblem einen Laplace-Beltrami-Operator (&Dgr;) aufweist. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass das Eigenwertproblem eine Helmholtz-Differentialgleichung nach der Formel: &Dgr;f = – &lgr;f mit dem Operator &Dgr;, den Eigenfunktionen f und den Eigenwerten &lgr; ist. Verfahren nach einem der vorhergehenden Ansprüche, gekennzeichnet durch Normieren der Charakterisierung der Objekte auf eine Basisskalierung durch Division der Eigenwerte (A) durch den ersten Wert ungleich Null, der nach Größe der Eigenwerte (&lgr;) sortierten Sequenz von Eigenwerten (&lgr;); Verfahren nach einem der Ansprüche 1 bis 3, gekennzeichnet durch Normieren der Charakterisierung der Objekte auf eine Basisskalierung durch

a) Bestimmen einer Ausgleichsfunktion f(n)=c nd/2 durch eine festgelegte Anzahl N von Eigenwerten (A) beginnend vom Anfang der Sequenz mit dem Skalierungsfaktor c, der Position n eines Eigenwertes in der Sequenz und der Dimension d des Objektes; und

b) Skalieren der Eigenwerte (&lgr;) mit so gewähltem Skalierungsfaktor, dass die Ausgleichsfunktion f(n) auf eine festgelegte Normfunktion abgebildet wird.
Verfahren nach einem der vorhergehenden Ansprüche, gekennzeichnet durch Normieren der Charakterisierung der Objekte auf eine Einheitsfläche oder ein Einheitsvolumen durch Multiplikation der Eigenwerte (A) mit dem Wert des Flächeninhalts (A) oder des Volumens (V2/3). Verfahren nach einem der vorhergehenden Ansprüche, gekennzeichnet durch Skalieren der Charakterisierung der Objekte durch Multiplikation der Eigenwerte (&lgr;) mit einem Skalierungsfaktor s2, wobei s der Skalierungsfaktor für das Objekt ist. Verfahren nach einem der vorhergehenden Ansprüche, gekennzeichnet durch Vergleichen der Formähnlichkeit von Objekten durch Bestimmen der Ähnlichkeit der Eigenwertsequenzen (&lgr;1,..., &lgr;n) oder skalierten Eigenwertsequenzen (&lgr;1,..., &lgr;n) der zu vergleichenden Objekte. Verfahren nach Anspruch 8, gekennzeichnet durch Bestimmen des Euklidischen Abstands d(&lgr;, &mgr;)n der Eigenwertsequenzen (&lgr;1,..., &lgr;n; &mgr;1,..., &mgr;n) oder skalierten Eigenwertsequenzen (&lgr;1,..., &lgr;n; &mgr;1,..., &mgr;n) für zwei Objekte nach der Formel: wobei &lgr;i die Eigenwerte für ein erstes Objekt, &mgr;i die Eigenwerte für ein zweites Objekt und n die Anzahl der Eigenwerte einer jeweiligen Sequenz ist. Verfahren nach Anspruch 8, gekennzeichnet durch Bestimmen des Hausdorff-Abstandes mit einem Vergleich der Eigenwerte (&lgr;) oder skalierten Eigenwerte (A) der Sequenz eines ersten Objektes jeweils mit jedem Eigenwert (&mgr;) der Sequenz eines zweites Objektes. Verfahren nach Anspruch 8, gekennzeichnet durch Bestimmen der Korrelation zwischen den Eigenwerten (&lgr;) der Sequenz eines ersten Objektes und den Eigenwerten (&mgr;) der Sequenz eines zweiten Objektes. Verfahren nach einem der vorhergehenden Ansprüche, gekennzeichnet durch Ermitteln einer Höhenfunktion aus den Grauwerten eines gespeicherten Bildes oder einer verallgemeinerten Höhenfunktion aus den Farbwerten eines gespeicherten Bildes und Charakterisieren des Bildes anhand der Eigenwerte (&lgr;) des Eigenwertproblems für die Höhenfunktion. Verfahren nach einem der vorhergehenden Ansprüche, gekennzeichnet durch Berechnen sowohl der Eigenwerte eines Körpers als auch der Eigenwerte der Hülle des Körpers. Verfahren nach einem der vorhergehenden Ansprüche, gekennzeichnet durch Suchen von in mindestens einer Datenbank gespeicherten Repräsentationen von Objekten durch Vergleichen der Eigenwertsequenzen (&lgr;1,..., &lgr;n) oder skalierten Eigenwertsequenzen (&lgr;1,..., &lgr;n) der gespeicherten Repräsentationen mit einer Eigenwertsequenz (&mgr;1,..., &mgr;n) eines gesuchten Objektes. Verfahren nach einem der Ansprüche 8 bis 14 zur Identifikation von digitalen Repräsentationen von Objekten, Schutz vor Raubkopien und/oder Qualitätskontrolle. Verfahren nach einem der vorhergehenden Ansprüche, gekennzeichnet durch Extrahieren von geometrischen Daten für das Objekt, zum Beispiel des Flächeninhalts der Fläche, des Volumens des Körpers, der Länge des Randes oder des Flächeninhalts der Randfläche des Objektes aus der Sequenz von Eigenwerten (&lgr;). Verfahren nach Anspruch 16, gekennzeichnet durch Bestimmen der Euler-Charakteristik aus der Sequenz von Eigenwerten (&lgr;) zur Ermittlung der Anzahl der Löcher in einer Planaren Fläche oder des Genus einer geschlossenen Fläche. Computerprogramm mit Programmcodemitteln zur Durchführung des Verfahrens nach einem der vorhergehenden Ansprüche, wenn das Programm auf einem Computer abläuft. Schaltungsanordnung mit Rechenmitteln, die zur Durchführung des Verfahren nach Anspruch 1 bis 17 ausgebildet sind.






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com