Direkt zum Inhalt | Direkt zur Navigation

Eingang zum Volltext

Lizenz

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:bsz:25-opus-73617
URL: http://www.freidok.uni-freiburg.de/volltexte/7361/


Mohamed, Khaireel Ahmad

Concepts and solutions for efficient handling of the digital ink

Neuartiger Ansatz zum Glätten digitaler Handschrift und zum Rendern

Dokument1.pdf (14.213 KB) (md5sum: dc920dbc9afc41c6e30483f53b1ab975)

Kurzfassung in Deutsch

Wir präsentieren in dieser Arbeit einen neuartigen Ansatz zum Glätten digitaler Handschrift und zum Rendern der daraus resultierenden mathematischen Kurven. Dieser Prozess kann bereits durchgeführt werden, bevor der komplette Digitalisierungsvorgang auf dem Transducer (signalgebendes Eingabegerät) abgeschlossen ist.
Die Vorteile dieses Verfahrens ergeben sich in zweierlei Hinsicht: Einerseits wird die visuelle Rückmeldung während des Schreibens aufrechterhalten, ohne dass charakteristische Merkmale der Schrift wie der Stil und das Flair aufgrund der Natur der Digitalisierung in Mitleidenschaft gezogen werden.
Andererseits -- und dies ist viel entscheidender -- ermöglicht die Verwendung der von uns konzipierten sehr effizienten Lösungen, die verfügbaren Rechnerressourcen für andere rechenaufwändige Aspekte einer multimodalen Anwendung zu verwenden.

Im ersten Teil dieser Arbeit illustrieren wir verschiedene Konzepte, welche verwendet werden können, um eine gegebene Menge von Punkten in der Ebene mittels sorgfältig platzierter Kurven zu verbinden.
Bei der Nutzung klassischer Interpolationsmethoden nimmt man an, dass die Punkte einer wohldefinierten, zweifach differenzierbaren Funktion mit bestimmtem Grad entstammen.
Im Verlaufe dieser Arbeit werden wir schließlich diese Annahme fallen lassen und unsere eigenen Ansätze miteinbeziehen, die es ermöglichen, durch eine Kombination von Interpolation und Regression eine Menge von unregelmäßig verteilten Punkten mit einer wünschenswerten Näherung der ursprünglichen Kurve zu verbinden (die hier genannte wünschenswerte Näherung genügt dabei dem Approximierungssatz von Weierstrass).
Eine solche unregelmäßige Verteilung der Punkte ist schließlich eine der inhärenten Eigenschaften einer handgeschriebenen Spur, wie sie von einem Transducer geliefert wird.
Um die Gültigkeit unseres Ansatzes und die Korrektheit der Behauptungen nachzuweisen, zeigen wir, dass die geglätteten Versionen der Spuren ausschließlich durch Abschnitte konischer Funktionen, genauer gesagt Ellipsen, nachgebildet werden können, die an den Endpunkten jeweils harmonisch ineinander übergehen.
Diese charakteristischen Eigenschaften, die eine sehr aufwändige Berechnung mit sich bringen, veranlassten uns dazu, verschiedene signifikante Aspekte quadratischer Splines zu untersuchen.
Dabei entdeckten wir, dass anstatt einer linearen Anzahl von Berechnungen pro Punkt (mit mindestens vier Quadratwurzeloperationen pro Berechnung) eine konstante Anzahl genügt.
Diese Ergebnisse begründen schließlich das Herzstück unseres Active-Smoothing-Algorithmus'.

Im zweiten Teil erläutern wir die Struktur von handgeschriebenen Spuren im Hinblick auf deren wesentliche Eigenschaften, die wiederum die Grundlagen der Erkennung von Gesten-Befehlen darstellen.
Ein Gesten-Befehl ist das Ergebnis einer gestenartigen Eingabe mit dem Stift, die dem Zeichnen einer speziellen Form ähnelt, und dem Ausführen der mit dieser Geste verbundenen vordefinierten Befehle.

Bezieht man die zeitlichen Komponente einer Spur mit ein, sind wir mit unseren Techniken in der Lage, aus den räumlichen und zeitlichen Eigenschaften der Eingabe auf einer einzigen Schreibfläche zwischen Handschrift (und Zeichnungen) und Gesten zu unterscheiden.
Die räumlichen Eigenschaften von Gesten weisen im Bezug auf den Schwerpunkt auffällige Eigenschaften auf, die eine -- von uns als Disorientierung bezeichnete -- räumliche Zuordnung der Gesten ermöglichen.
Das bedeutet nun, dass man bei der Verwendung eines Tabletops mittels eines linearen Diskriminators feststellen kann, von welcher Seite des Gerätes eine bestimmte Geste ausgeführt wurde -- ohne die Verwendung zusätzlicher externer Tracking-Mechanismen.

Die Anwendung der Ergebnisse beider Teile ermöglicht es uns somit nicht nur mit digitaler Tinte effizient umzugehen, sondern auch darüberhinaus in intuitiver Weise mit der Arbeitsumgebung zu interagieren.


Kurzfassung in Englisch

We present a novel approach that smooths digital handwritings and renders the resultant high quality, symbolically represented curves, while the primitive-resolution sampling process from the transducer device is still ongoing. The repercussion from this is two-fold; firstly, the visual impact while writing, is sustained, without compromising on the integrity of the style' and flair', and any of the other features within, that may be lost to the rigid and perfunctory sampling routine between the hardware and the software. And, more importantly, the second repercussion, through the conceived efficiencies of our combined and simplified underlying methods together, alleviates on what limited resources that are available and enables other routines handling other computationally demanding aspects of a multi-modal application access to more processor time.

The first part of the thesis canvases the various concepts of passing a set of well-placed curves through a set of given points on the 2D plane. The classical interpolation methods assume that the curves are twice differentiable at every single point, and that the points are part of an unknown but well-defined mathematical function of a certain degree. As we progress through the thesis, we eventually lift this assumption and incorporate our techniques, which includes a combination of interpolation and regression methodologies, to desirably estimate a set of indeterministically scattered points -- which is an apparent and inherent characteristic of a typical handwritten trace that comes out of the transducer device. A desirable estimate is one that adheres to the Weierstrass approximation theorem. To prove the validity of our approach and the correctness of our propositions, we show that the smoothed versions of these traces can entirely be made up of conic sections, particularly the ellipses, joined together at their endpoints in confluent harmony. These formative and computationally expensive grounds, when viewed collectively, led us to discover certain imperative aspects of the quadratic spline curves that reduce linear time calculations per input point, involving at least four square-root operations per calculation, down to a constant. Essentially, these propositions are what constitute our active-smoothing algorithm. The symbolically represented curves and the delayed rendering procedure ensure that we maintain linear space storage complexity with respect to the number of original points in the trace. Our results show that this form of representation has no adverse effects on random access navigation, which is a process of active visible scrolling".

In the second part, we expound the composition of handwritten traces in observance of their intrinsic features that are the fundamentals of gesture command recognition. A gesture command is the result of invoking gesture-like movements with the pen, that resemble special shapes drawn in a certain distinctive way, recognised as certain predefined instructions that are to be carried out. We show that our temporal techniques applied on the traces and involving their spatial features can distinguish writings (and drawings) apart from gesturings, on a common, non-segregated ink environment. The spatial features, we found, when concentrated about their centre of gravities, exhibited conspicuous properties that allow, what we term as, the dis-orientation' of the gestures; that is, when exploiting the tabletop environment, the linear discriminator is able to determine whether a gesture came from a person who is seated at the northern, southern, eastern, or western edge of the table, without the help of external tracking devices.

With all the ramifications of the results from both these parts combined, we not only get the solutions necessary to efficiently handle the digital ink, but also to consistently interact with it in its appropriate environment.


SWD-Schlagwörter: Algorithmische Geometrie , Kurve
Freie Schlagwörter (englisch): Digital ink , active-smoothing , spline curves , pen gestures
Institut: Institut für Informatik
Fakultät: Technische Fakultät (bisher: Fak. f. Angew. Wiss.)
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Erstgutachter: Ottmann, Thomas (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 25.03.2009
Erstellungsjahr: 2009
Publikationsdatum: 23.03.2010
Indexliste