Multi-scale integral invariants for robust character extraction from irregular polygon mesh data

PDF, English Download (285MB) | Terms of use

Abstract

Hunderttausende von antiken Dokumenten in Keilschrift befinden sich in Museen, und täglich werden weitere bei archäologischen Grabungen gefunden. Die Auswertung dieser Dokumente ist wesentlich für das Verständnis der Herkunft von Kultur, Gesetzgebung und Religion. Die Keilschrift ist eine Handschrift und wurde in den Jahrtausenden vor Christi Geburt im gesamten alten Orient benutzt. Der Name leitet sich von den keilförmigen Eindrücken eines Schreibgriffels in den weichen Beschreibstoff Ton ab. Das Anfertigen von Handzeichnungen und Transkriptionen dieser Tontafeln ist eine langwierige Aufgabe und verlangt nach Unterstützung mittels automatisierter rechnergestützter Verfahren. Das Ziel dieser Arbeit ist die präzise Extraktion von Schriftzeichen mit variablen Formen in 3D. Die für die Merkmalsextraktion aus 2D-Mannigfaltigkeiten in 3D entscheidenden Schritte sind Kantenerkennung und Segmentierung. Robuste Techniken in der Signalverarbeitung und dem Shape Matching benutzen hierfür Integralinvarianten in 2D. In aktuellen Arbeiten werden die Integralinvarianten grob geschätzt, um wenige prägnante Merkmale zu finden, mit denen sich zerbrochene 3D-Objekte zusammensetzen lassen. Mit dem Ziel der exakten Bestimmung der 3D-Formen von Zeichen, wurde die aus der Bildverarbeitung und Mustererkennung bekannte Verarbeitungskette an 3D-Modelle angepasst. Diese Modelle bestehen aus Millionen von Messpunkten, die mit optischen 3D-Scannern aufgenommen werden. Die Punkte approximieren Mannigfaltigkeiten durch ein irreguläres Dreiecksnetz. Verschiedene Typen von integralinvarianten Filtern in mehreren Skalen führen zu verschiedenen hochdimensionalen Merkmalsräumen. Faltungen und kombinierte Metriken werden auf die Merkmalsräume angewandt, um Zusammenhangskomponenten zu bestimmen. Diese Komponenten stellen die Zeichen genauer als die Messauflösung dar. Parallel zum Design der Algorithmen werden die Eigenschaften der verschiedenen Integralinvarianten analysiert. Die Interpretation der Filterergebnisse sind von großem Nutzen zur Bestimmung von robusten Krümmungsmaßen und zur Segmentierung. Die Extraktion von Keilschriftzeichen wird mit einer Voronoi basierten Berechnung von minimalen normalisierbaren Vektordarstellungen vervollständigt. Diese Darstellung ist eine wichtige Grundlage für die Paläographie. Weitere Abstraktion und Normalisierung der Darstellung führt zur Zeichenerkennung. Die Einbettung der Algorithmen in das neu entworfene mehrschichtige GigaMesh Software Framework erlaubt eine Vielzahl von Anwendungen. Die Algorithmen nutzen den Speicher effektiv und die Verarbeitungskette ist parallelisiert. Die konfigurierbare Verarbeitungskette hat nur einen relevanten Parameter, nämlich die maximale Größe der zu erwartenden Merkmale. Die vorgestellten Verfahren wurden an Hunderten von Keilschrifttafeln, so wie weiteren realen und synthetischen Objekten getestet.Repräsentative Ergebnisse sowie Aufwands- und Genauigkeitsabschätzung der Algorithmen werden gezeigt. Ein Ausblick auf künftige Erweiterungen und Integralinvarianten in höheren Dimensionen gegeben.

Translation of abstract (English)

Hundreds of thousands of ancient documents with cuneiform script are known to be in museum collections and are found on a daily basis at archaeological excavations. Analyzing these documents is essential to understand the origins of civilization, legislation and religion. This script is a handwriting and was used for several millennia in the ancient Middle East. Its name is derived from the Latin word for wedge, which is the 3D-shape left by an ancient scribe's stylus, when it was pressed into the soft surface of a clay tablet. Manually drawing and transcribing these tablets is a laborious and tedious task and assistance by an automated and computerized system is highly demanded. The aim of this thesis is extracting these handwritten characters, i.e. 3D-shapes with high variability. The crucial steps for feature extraction from 2D-manifolds in 3D-space are reliable edge detection and segmentation. This can be achieved using integral invariant filtering, a robust technique known from signal processing and shape matching in 2D-space. In 3D-space the state-of-the-art systems roughly estimate integral invariants for determining small numbers of highly distinctive features to solve puzzles of fractured objects. In order to precisely determine 3D-shapes of characters the pipeline known from image processing and pattern recognition is adapted for 3D-models. These models have millions of vertices, which are acquired by optical 3D-scanners. The vertices approximate manifolds with an irregular triangular mesh. Different types of integral invariant filtering in multiple scales lead to different high-dimensional feature spaces. Convolutions and combined metrics are applied to the feature spaces to determine connected components i.e. characters with sub-triangle accuracy within a manifold. Concurrently with the design of novel algorithms, the properties of the integral invariants are investigated. Understanding these properties is highly relevant for robust curvature measures and segmentation. The extraction of characters is completed with a Voronoi inspired method resulting in a minimal meaningful vector representation. This representation is an important basis for paleography. Further abstraction and normalization lead to character recognition. The embedment of the proposed methods in the novel and layered GigaMesh software framework enables a wide variety of applications. Memory efficiency and parallel processing were taken into account in the design of the configurable mesh processing pipeline. The pipeline has only one relevant parameter, which is the maximum size of the expected features. The proposed methods were tested on hundreds of cuneiform tablets as well as on other objects including synthetic datasets. Representative results are shown and an evaluation regarding accuracy and performance of the algorithms are given. Finally observations about integral invariants in higher dimensions are shown and an outlook is given.