Concepts and solutions for efficient handling of the digital ink [Elektronische Ressource] / Khaireel A. Mohamed

Khaireel A. Mohamed

Sujets

• Informatik

Informations

• Publié par: albert-ludwigs-universitat_freiburg
• Publié le: 01 janvier 2010
• Nombre de lectures: 20
• Langue: Deutsch
• Poids de l'ouvrage: 13 Mo

Extrait

Concepts and Solutions for E cient
Handling of the Digital Ink
Khaireel A. Mohamed
Dissertation zur Erlangung des Doktorgrades (Dr.-Ing.)
Technische Fakult at, Albert-Ludwigs-Universit at Freiburg
Dekan: Prof. Dr. Hans Zappe
Referenten: Prof. Dr. Thomas Ottmann (1. Gutachter)
Prof. Dr. Heinrich Muller (2. Gutachter)
Datum der Disputation: 25. M arz 2009iiTo the loving memory of my late father.
Ahmad Bambong
(1945 { 2007)ivTo my most special friend and con dant,
who stuck steadfastly by me through thick and thin,
whose strong words of encouragement ring honest and true.
An inspiration to all things positive.
A most respectable and reliable man.
A brother who I love and fully trust.
Tobias Langner
\The proper o ce of a friend is to side with you when you are in the wrong.
Nearly anybody will side with you when you are in the right."
Mark Twain, 1898.viZusammenfassung
Wir pasr entieren in dieser Arbeit einen neuartigen Ansatz zum Gl atten digi-
taler Handschrift und zum Rendern der daraus resultierenden mathematischen
Kurven. Dieser Prozess kann bereits durchgefuhrt werden, bevor der komplette
Digitalisierungsvorgang auf dem Transducer (signalgebendes Eingabeger at) ab-
geschlossen ist. Die Vorteile dieses Verfahrens ergeben sich in zweierlei Hinsicht:
Einerseits wird die visuelle Ruc kmeldung w ahrend des Schreibens aufrechter-
halten, 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 oglicht die Verwendung
der von uns konzipierten sehr e zienten L osungen, die verfugbaren Rechnerres-
sourcen fur andere rechenaufw andige Aspekte einer multimodalen Anwendung
zu verwenden.
Im ersten Teil dieser Arbeit illustrieren wir verschiedene Konzepte, welche
verwendet werden k onnen, um eine gegebene Menge von Punkten in der Ebene
mittels sorgf altig platzierter Kurven zu verbinden. Bei der Nutzung klassischer
Interpolationsmethoden nimmt man an, dass die Punkte einer wohlde nierten,
zweifach di erenzierbaren Funktion mit bestimmtem Grad entstammen. Im
Verlaufe dieser Arbeit werden wir schlie lich diese Annahme fallen lassen und
unsere eigenen Ans atze miteinbeziehen, die es erm oglichen, durch eine Kombi-
nation von Interpolation und Regression eine Menge von unregelm a ig verteil-
ten Punkten mit einer wunschenswerten N aherung der ursprunglic hen Kurve zu
verbinden (die hier genannte wunsc henswerte N aherung genugt dabei dem Ap-
proximierungssatz von Weierstrass). Eine solche unregelma ige Verteilung der
Punkte ist schlie lich eine der inharenten Eigenschaften einer handgeschriebenen
Spur, wie sie von einem Transducer geliefert wird. Um die Gultigk eit unseres
Ansatzes und die Korrektheit der Behauptungen nachzuweisen, zeigen wir, dass
die geglatteten Versionen der Spuren ausschlie lich durch Abschnitte konischer
Funktionen, genauer gesagt Ellipsen, nachgebildet werden k onnen, die an den
Endpunkten jeweils harmonisch ineinander ub ergehen. Diese charakteristischen
Eigenschaften, die eine sehr aufw andige Berechnung mit sich bringen, veran-
lassten uns dazu, verschiedene signi kante Aspekte quadratischer Splines zu un-
tersuchen. Dabei entdeckten wir, dass anstatt einer linearen Anzahl von Berech-
nungen pro Punkt (mit mindestens vier Quadratwurzeloperationen pro Berech-
nung) eine konstante Anzahl genugt. Diese Ergebnisse begrunden schlie lich das
Herzstuc k unseres Active-Smoothing-Algorithmus’.
Im zweiten Teil erl autern wir die Struktur von handgeschriebenen Spuren
im Hinblick auf deren wesentliche Eigenschaften, die wiederum die Grundla-
viiviii
gen der Erkennung von Gesten-Befehlen darstellen. Ein Gesten-Befehl ist das
Ergebnis einer gestenartigen Eingabe mit dem Stift, die dem Zeichnen einer
speziellen Form ahnelt, und dem Ausfuhren der mit dieser Geste verbundenen
vorde nierten Befehle.
Bezieht man die zeitlichen Komponente einer Spur mit ein, sind wir mit un-
seren Techniken in der Lage, aus denaumlicr hen und zeitlichen Eigenschaften der
Eingabe auf einer einzigen Schreib ache zwischen Handschrift (und Zeichnungen)
und Gesten zu unterscheiden. Die aumlicr hen Eigenschaften von Gesten weisen
im Bezug auf den Schwerpunkt au allige Eigenschaften auf, die eine { von uns
als Disorientierung bezeichnete { aur mliche Zuordnung der Gesten erm oglichen.
Das bedeutet nun, dass man bei der Verwendung eines Tabletops mittels eines
linearen Diskriminators feststellen kann, von welcher Seite des Ger ates eine bes-
timmte Geste ausgefuhrt wurde { ohne die Verwendung zus atzlicher externer
Tracking-Mechanismen.
Die Anwendung der Ergebnisse beider Teile ermogl icht es uns somit nicht nur
mit digitaler Tinte e zient umzugehen, sondern auch darub erhinaus in intuitiver
Weise mit der Arbeitsumgebung zu interagieren.Abstract
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; rstly, the visual impact while writing, is sus-
tained, without compromising on the integrity of the ‘style’ and ‘ air’, and any
of the other features within, that may be lost to the rigid and perfunctory sam-
pling routine between the hardware and the software. And, more importantly,
the second repercussion, through the conceived e ciencies of our combined and
simpli ed underlying methods together, alleviates on what limited resources that
are available and enables other routines handling other computationally demand-
ing aspects of a multi-modal application access to more processor time.
The rst 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 di erentiable at every
single point, and that the points are part of an unknown but well-de ned math-
ematical 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 approxima-
tion 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 con uent 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 con-
stant. Essentially, these propositions are what constitute our active-smoothing
algorithm. The symbolically represented curves and the delayed rendering pro-
cedure 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 e ects 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 com-
mand recognition. A gesture command is the result of invoking gesture-like
ixx
movements with the pen, that resemble special shapes drawn in a certain dis-
tinctive way, recognised as certain prede ned 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 gestur-
ings, 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 rami cations of the results from both these parts combined, we
not only get the solutions necessary to e ciently handle the digital ink, but also
to consistently interact with it in its appropriate environment.
Keywords: Digital ink, active-smoothing, spline curves, pen gestures
CR Categories: A.2, I.7.2