Accepted Manuscript
More than Ink — Realization of a Data-Embedding Pen
Marcus Liwicki, Seiichi Uchida, Akira Yoshida, Masakazu Iwamura, Shinichiro
Omachi, Koichi Kise
PII:
DOI:
Reference:

S0167-8655(12)00286-3
http://dx.doi.org/10.1016/j.patrec.2012.09.001
PATREC 5501

To appear in:

Pattern Recognition Letters

Please cite this article as: Liwicki, M., Uchida, S., Yoshida, A., Iwamura, M., Omachi, S., Kise, K., More than Ink— Realization of a Data-Embedding Pen, Pattern Recognition Letters (2012), doi: http://dx.doi.org/10.1016/j.patrec.
2012.09.001

This is a PDF file of an unedited manuscript that has been accepted for publication. As a service to our customers
we are providing this early version of the manuscript. The manuscript will undergo copyediting, typesetting, andreview of the resulting proof before it is published in its final form. Please note that during the production processerrors may be discovered which could affect the content, and all legal disclaimers that apply to the journal pertain.

More than Ink — Realization of a Data-Embedding Pen
Marcus Liwickia , Seiichi Uchidab , Akira Yoshidab , Masakazu Iwamurac ,Shinichiro Omachid , Koichi Kisecab

DFKI, Germany, Email: marcus.liwicki@dfki.de
Kyushu Univ., Japan, Email: uchida@ait.kyushu-u.ac.jpcOsaka Prefecture Univ., Japand
Tohoku Univ., Japan

Abstract
In this paper we present a novel digital pen device, called data-embedding
pen, for enhancing the value of handwriting on physical paper. This pen produces an additional ink-dot sequence along a written stroke during writing.
This ink-dot sequence represents arbitrary information, such as writer’s nameand writing date. Since the information is placed on the paper as an ink-dot
sequence, it can be retrieved just by scanning or photographing the paper.
In addition to the hardware of the data-embedding pen, this paper also proposes a coding scheme for reliable data-embedding and retrieval. In fact, thephysical data-embedding on a paper will undergo various severe errors andtherefore a robust coding scheme is necessary. Through experiments on data
written by two writers, we show that we can embed 32 bits on short andsimple or even on more complex patterns and finally retrieve them with ahigh reliability.
Keywords: data-embedding pen, stroke recovery, handwriting

1

2
3
4
5
6
7
8

1. Introduction
Handwriting is an important modality for writing down information, making annotations, or just marking items. Unfortunately, as soon as the ink ison the paper, many information known during writing is already lost. We
cannot access meta-information about the handwritten pattern from itself;
it is impossible to retrieve who wrote this pattern or when it was written. In
other words, a handwritten pattern on a physical paper is just an ink pattern
and thus cannot provide any information but its shape.
Preprint submitted to Pattern Recognition Letters

September 12, 2012

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

33
34

35
36
37

38
39
40

41
42
43

Digital pens have emerged as a choice to store and retrieve such additional
information. In fact, several digital pens capturing handwriting on normal
paper have been developed. Those pens can store the stroke sequences on acomputer with some additional information. Unfortunately, the digital penscannot increase the value of handwriting on paper; even with the digitalpens, the handwriting left on the paper is still just an ink pattern without
any information.
In this paper, we propose a novel pen device to enrich the handwriting on
the physical paper. The proposed pen device, called data-embedding pen, canembed arbitrary information, such as meta-information, by an additional inkdot sequence along the ink stroke of the handwriting. Each ink-dot represents
an information bit and thus an ink-dot sequence represents a bit-stream of theinformation to be embedded. The information can be retrieved by scanningor photographing the paper and decoding the ink-dot sequence.
The most important property of the data-embedding pen is to increase
the value of handwriting on the physical paper. If we embed the writer ID,
the handwriting on the physical paper itself stores this meta-informationand identifies the writer without using an electronic memory. If we embed
an URL into the handwriting, the handwriting becomes a link between thephysical paper world and the cyber-space, i.e., the Internet. Furthermore, if
we embed any temporal information or hints into the pattern, it is possible
to convert the strokes into the online representation which is helpful to attaina better handwriting recognition accuracy.
The contributions by this paper are summarized as follows.
• The idea of embedding information into handwriting is very novel, as
reviewed in Section 2.
• For this idea, a prototype of the data-embedding pen is implemented
using a special ink-jet nozzle element. Such an implementation has
never been developed before.
• For reliable data-embedding and data-retrieval, image processing techniques and a coding scheme are proposed, both of which are specialized
for the data-embedding pen.
• Experimental results with the prototype proved that arbitrary 32-bit
information can be embedded into, for example, a 5cm-length handwriting pattern and retrieved perfectly from the pattern.
2

46Note that this paper is not only the first compilation of the authors’ pasttrials (Uchida et al., 2006; Liwicki et al., 2010a,b, 2011) but also a new reportof experimental results on a broader set of handwritten patterns.

47

2. Related Work

44
45

48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

To the authors’ best knowledge, the data-embedding pen is the firsttrial on implementing a new pen device which can embed arbitrary information dynamically into handwriting on a paper. Generally, embedding
data into paper has been done statically by a printer. For example, XEROX
DataGlyph (Hecht, 1994) is a kind of digital watermarks and information isprinted and embedded as a fine texture into font images or photographs.
Digital pens are popular devices to enhance the usability of handwriting.
Various types of digital pen devices are already available. Tablets are themost widely available digital pen-input modality. Wacom tablets1 , for example, capture the pen-tip trajectory by a note-size flat pad with sensor array.
Other digital pens use ultrasonic to capture the pen-tip location. All thosedigital pens are just useful to transfer handwritten patterns to the computer.
In other words, they do not enhance the “function” of the handwriting on
paper itself.
Nowadays, the most famous digital pen seems to be the Anoto pen2 .
Anoto reads the dot pattern printed on the paper surface from its pen-tip
camera and detects its absolute position on the paper by interpreting thepattern. By continuously detecting the position during the pen movement,
Anoto can acquire the online trajectory. Like other digital pens, the Anotopen also has a very different purpose from the data-embedding pen, i.e., justtransferring the pattern to the computer. In fact, the handwritten patternon the paper is just a pattern showing a stroke shape and thus no additional
value. In contrast, the purpose of the data-embedding pen is to enhance thefunction of the handwritten pattern on paper.
12

http://www.wacom.com — last visited: November 2011
http://www.anoto.com — last visited: November 2011

3

(a)

(b)
Figure 1: A prototype of the data-embedding pen (top). (a) Ink-dots (light) nearby a
handwriting stroke (black). (b) After image processing.

72

73
74
75
76
77
78
79
80
81
82
83

3. The Data-Embedding Pen
3.1. Hardware Prototype
The data-embedding pen is a device which comprises a usual ballpoint
pen and an ink-jet nozzle element. Figure 1 (top) depicts a prototype of
this device with the ballpoint pen at the top and the nozzle at the bottom.
Figure 1 (a) is a handwritten pattern generated by the prototype. During
the writing, the nozzle produces small ink-dots alongside the handwritten
stroke. The color of the ink-dots is different from the color of the stroke.
In this paper, yellow is used for the ink-dots for better visibility of the results. Invisible ink is a good alternative for hiding the ink-dot sequence. In
the past we have successfully performed experiments using invisible ink in
combination with an ultraviolet camera (see Liwicki et al. (2010a)).
4

84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

107
108
109
110
111
112
113
114
115
116
117
118
119
120

It is possible to encode arbitrary information as an ink-dot sequence bychanging the number, the timing, and the shape of the ink-dots, as shownin Fig. 1 (a). Very roughly speaking, this coding scheme is similar to Morsecode, where short and long segments and a pause are used and arbitrary
information is represented as their sequence. Our coding scheme is designed
to be more robust and error-tolerant, as described in the later sections.
The ink-dot shape can be controlled by using the high-frequency injection
mode of the nozzle. The nozzle is able to generate up to 2, 000 ink-dots
per second. Under this high-frequency mode, the ink-dots on the paper
are connected and form a line segment. Hereafter, a line produced by nsequential ink-dots is called n-pulse line. If n = 1, the n-pulse line forms asingle ink-dot. The line becomes longer by increasing n.
Note that due to hardware-specific issues the hardware of the actual dataembedding pen differs from the original setup proposed in Uchida et al.
(2006). One crucial aspect is that just one nozzle element is used, since
it was not possible for us to integrate more than one nozzle element intoa practicable device. However, it would be possible to do so by designing
specific nozzle elements in cooperation with printer companies. Thus thecontribution of this paper can be seen as proving that the data-embedding
pen can be realized and therefore motivating printer companies to develop a
hardware which would be able to produce smaller dots and including morethan one nozzle element and thus enabling the pen to be used with smaller
handwriting and to embed even more information.
3.2. Applications
Various kinds of information can be embedded into handwriting by thedata-embedding pen. This means that we can consider various applicationsof the data-embedding pen. In this section, several possible applications
will be shown. All applications make use of the fact that any data encoded
in a binary sequence can be added alongside with the handwritten pattern.
Depending on the length of the pattern, the amount of information varies.
As shown later by the experimental results, the current prototype can embed arbitrary 32-bit information into a 5cm-length handwritten pattern, forexample.
Embedding information relating to the handwritten pattern itself is thesimplest application. For example, writer’s ID, writing date, and writing
Geo-location, are possible candidates. This “meta”-information of the handwritten pattern can be useful for enhancing signature verification and for
5

121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

usage in other forensic applications. In addition, if we know the writer’s ID,
the recognition of the handwriting will become easier because we can apply some character recognition model tuned to the writer. Discrimination ofmultiple writers on a single document is also possible, if the pen embeds thecorresponding writer ID. More details of this application idea as well as theidea of embedding a “handwritten” bar-code linking link between physicalpaper world and the cyber-space are presented in Uchida et al. (2006).
Embedding information on paper opens up new possibilities for diaries
and notebooks. The owner of the book has only the paper documents athand. However, still he or she can always find out when and where theinformation has been written down. Similarly, one can use the pen for writing
an account of one’s journey or a diary. If the pen is equipped with a GPSreceiver, the time and place will be automatically attached to the handwritten
sentences. After scanning the handwritten pages, the information can be
uploaded as a blog or as contributions to a Web 2.0 platform.
If we embed any temporal information by an ink-dot sequence, it is possible to relax the difficulty of the stroke recovery problem (Doermann and
Rosenfeld, 1995; Kato and Yasuhara, 2000; Nel et al., 2005), which is an inverse problem to estimate the original writing order of a handwritten stroke
pattern. This implies that we can convert handwritten images into online
patterns and thus apply online handwriting recognition (Plamondon and Srihari, 2000; Vinciarelli, 2002), which is generally more accurate than offline
recognition. Note that in this paper the writing direction, i.e., a kind of
temporal information, is already embedded into the handwritten pattern for
reliable data-retrieval.
Note that for enabling a pen for such applications it needs to be equippedwith the application-specific hardware. While the realization of such hardware is out of the scope of this paper, we will present some ideas for realization here. As mentioned above, the pen could be equipped with a small
GPS-receiver and an internal clock to deliver time and place information forembedding. For writer authentification a small fingerprint sensor can be attached to the thumb-side of the pen. Furthermore, small motion sensors anda camera can be equipped for online recognition, document retrieval, andtemporal information embedding. The feasability of equipping a pen withsuch sensors has been proven by the development of specific Anoto pens, such

6

158

as the livescribe3 . This pen also includes a small display as a user interface
where in the case of the data-embedding pen the user could easily select thekind of data to be embedded.

159

4. Data-Embedding

156
157

160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189

4.1. Basic Coding Scheme
Our coding scheme is based on the combination of three different n-pulse
lines. Specifically, we use n = 1 (a dot), 5 (a short line), and 20 (a long line).
These numbers have been fixed after a set of initial experiments with various
n-pulse lines. The ink-dot sequence of Fig. 1 consists of those n-pulse lines.
The information is converted into a binary (0 and 1) sequence and embedded by using the 1-pulse line as 0 and the 5-pulse line as 1. A short pause
is prepared between each bit information (1-pulse or 5-pulse line). The 20pulse line, hereafter called synchronization blob, is used as an anchor to makesure that a correct position is extracted. The leftmost ink-dot in Fig. 1 is asynchronization blob.
Note that converted binary sequence is not directly embedded into thehandwriting. We also apply an error-tolerant coding scheme for the original
information after deriving the binary sequence. For example, the data “10”is not just converted into “1010”; after this conversion, the data is further
converted into a redundant codeword to be more robust to error. More details
will be given in Section 6.
Using the n-pulse lines, three units, called frame, block, and bit areformed. The bit is the smallest unit and defined by a 1-pulse line or a 5pulse line. Several consecutive bits comprises a block and several consecutive
blocks comprises a frame. A pause which is longer than the pause between
bits is inserted between two consecutive blocks. Each frame begins and ends
at a synchronization blob.
Figure 1 is an example of a single frame. From left to right, the ink-dot
sequence of the frame is comprised of a synchronization blob, 6 blocks, andanother synchronization blob. In each block, 4 bits are encoded and thus in
the frame 24 bits (0110 − 1010 − 1010 − 1010 − 0000 − 1100) are embedded.
The main parameters of the coding scheme are the number of bits per
block (bB) and the number of blocks per frame (bF ). Accordingly, the number of bits per frame becomes bF × bB. In the example of Fig. 1, bF = 6 and3

http://www.livescribe.com

7

190
191
192

bB = 4. Another important parameter is the method for correcting errors
which eventually occur when ink-dots overlap. More details about this issue
follow in Section 6.

209

4.2. Embedding Dynamic Information
One of the difficulties in realizing the data-embedding pen is the stroke
recovery problem. Specifically, since ink-dots are produced and embedded
along the black-ink stroke, the writing order of the stroke has to be estimatedfor retrieving the embedded data. This is the so-called stroke recovery problem (Doermann and Rosenfeld, 1995; Kato and Yasuhara, 2000; Nel et al.,2005) and a well-known difficult inverse problem. For example, no one canalways give the correct writing order of a horizontal line “—”; it may beleft-to-right, but also may be right-to-left. For handwritten patterns withcrossing parts, their writing order becomes more difficult to be estimated.
Fortunately, the ink-dot sequence can be used for relaxing the difficultyof the stroke recovery problem. The idea is to embed the writing direction
by controlling the pause (gap) between consecutive n-pulse lines. This embedding can simply be realized by an additional pause added at the end ofeach frame, or equivalently, before each synchronization blob. Figure 4 in
Section 5.4 shows this idea. Finally, the gap size shows the writing direction,i.e., the smaller gap has been produced after the synchronization blob.

210

5. Data-Retrieval

193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208

211
212
213
214
215
216
217
218
219
220
221
222
223

In this section the main steps for retrieving the information will be summarized. After capturing an image of the data-embedded pattern on paper,
we first apply image processing techniques for extracting the ink-dots as wellas the black-ink stroke. Then the stroke order recovery is performed to realign the ink-dots in their original order Kato and Yasuhara (2000). Finally,
the embedded data is retrieved through Reed-Solomon based error correction
scheme.
We can either use a scanner or a digital camera for image capturing.
Camera-based capturing will introduce many difficulties which do not occur on scanned images: different illuminations depending on the flashlight,
varying sizes for the ink-dots, and different thickness for the strokes depending on the distance between the camera and the paper. In Section 5.1, theimage processing techniques for assessing these problems will be explained.

8

Figure 2: Example of a photographed “@” symbol before image processing (top) and after
white normalization (bottom).

224
225

226
227
228
229
230
231
232
233
234
235
236
237

Note that the same procedures can also be applied on scanned documents.
However, there they would have only minor effects which are negligible.
5.1. Image Processing
The results of the individual image processing steps for camera captured
images are depicted in Fig. 2. There, an example of a photographed “@”symbol is given on the top. Next to it, two example regions which are partof the “@” symbol are illustrated to visualize the behavior of the algorithm.4
As stated above, we can not assume the same illumination for all thephotographs. The situation is even worse when we have inhomogeneous
illumination, because usually, the center is more exposed by the flashlight.
Simply using a global threshold for color extraction would fail under thesecircumstances. Therefore, as a first processing step, we use a low-resolution
grid motivated from work in related areas (Jain, 1989; Simon et al., 2000)
and determine the brightest point in each sub-region. This is then used as
4

The authors of this paper are aware that the yellow ink-dots in are hardly visible on
a grayscale-printout. We have done this intentionally for several reasons. First, we did
not want to alter the original image in order to show the difficulties for the algorithm.
Second, the extracted ink-dots will be marked in blue for all processed images, e.g., Fig. 3(d). Finally, in the electronic version of the publication one can see the yellow ink.

9

(a)

(b)

(c)

(d)

(e)

(f)

Figure 3: Two loops with ink-dots and vizualization of the image processing steps on anintersection part of the loops. See text for details.

238
239
240
241
242
243
244
245
246

a reference for white in this sub-region and the color values are normalizedaccording to this value. This process is called white normalization. The
result of white normalization in Fig. 2 (top) can be seen in Fig. 2 (bottom).
The size of the sub-region was set to 50 × 50 pixels to make sure that at least
one target white pixel is occurring in this region. Note that this method
also works on homogeneous background colors. We have performed small
tests which proved that it also works on blue and even yellow background.
Experiments on non homogeneous background might fail, however, if invisible
ink was used, the method would be successful again.

10

247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267

268
269
270
271
272
273
274
275
276
277
278
279

5.2. Ink Extraction
The second image processing step is the ink-dot extraction by a simple
thresholding operation to identify the black ink stroke and yellow ink-dots.
Subsequently, noise removal is performed, because the extracted black ink
stroke image includes many noisy pixels, as shown in Fig. 3 (b). Thus, erosionand dilation are applied. Figure 3 (c) shows the result. Similar operations
are also applied to the ink-dot image (Fig. 3 (d)). Note that the parameters
for those operations can be optimized on a small training set.
The third step is a special treatment of ink-dots occluded by the black ink
stroke. Fortunately, those yellow ink-dots are still visible on the stroke, they
just appear to be a bit darker. Thus, after extracting the pixels of the black
ink stroke, another thresholding operation is performed on those pixels with alower threshold to recover dark yellow ink-dots. In the following experiments
it turned out that about 50% of those ink-dots could be recovered by thisapproach.
The fourth step is a thinning operation on the black ink stroke. Figure 3 (d) shows the result of an orthodox thinning method. Then, after
removing many small loops and short spurious edges by unifying neighboring branches, the final thinning result is obtained as shown in Fig. 3 (e). Up
to here, the image processing methods are state-of-the-art methods (Nguyen
and Blumenstein, 2010).
5.3. Information Ink Assignment
In order to make use of the embedded information, the n-pulse lines
are assigned to the corresponding strokes5 . The algorithm for finding these
correspondence is described in this section.
As shown in Fig. 3 (f), the basic idea of establishing the correspondence
is to find the closest point on the stroke for each ink-dot. A simple nearest
neighbor, however, cannot always provide a correct result because an ink-dot
and its corresponding point might be a bit distant due to the pen tilt. Thus,
at each ink-dot k, we first calculate the minimum distance dk,θ to the strokefor each θ of 36 angles with 10◦ interval. Then, we select the angle θ withminimum variance, i.e., θ = argminθ Var{d1,θ , . . . , dK,θ }. This angle is themost stable angle and thus represents a projection of the actual pen angle
5

Note that a stroke is seen as the sequence of points between a pen-down movement
and consecutive pen-up movement.

11

writing direction

Figure 4: An additional pause is used to determine the initial writing direction (top),
this can be observed by the larger gap on the left side of the big synchronization blob.
Illustration of the stroke direction recovery process (bottom).

280
281
282
283

284
285
286
287
288
289
290
291
292

and tilt during writing. Finally, for each ink-dot k, the corresponding point
is determined as the closest point when using angle θ. If many ink-dots were
not assigned to a stroke, this process is repeated, because it might be thatthe tilt has been changed during writing.
5.4. Stroke Recovery
Having the correspondence between the information ink and the strokeat hand, an estimation of the writing directions of the strokes is performed.
In the following, an entire algorithm of the stroke recovery is explained using
Fig. 4 as an example. This handwriting pattern can be seen as a graph where
each crossing point on the stroke is a node. The algorithm is comprised ofthree major steps.
First, the direction is estimated by using the gaps around the synchronization blobs. As noted in Section 4.2, the stroke direction is embedded as
12

293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329

the difference in the widths of the gaps. Thus for the edges including one
or more synchronization blobs it is possible to estimate the corresponding
writing direction. The blue arrows in Fig. 4 indicate the initial estimation of
the directions. Some short lines may have no synchronization blob and thus
no guess is assigned on these edges.
Second, we estimate the direction of the remaining edges. As an example,
we consider the edge between Node 1 and Node 2, where no estimation result
is given by the first step. The direction of this edge is determined as theoutbound direction of Node 1. This is because among the other three edgesof Node 1, two have an inbound direction and one has an outbound direction.
Since the number of the inbound edges should be equal to the number of theoutbound edges, the direction of the edge between Nodes 1 and 2 has to beoutbound as well. This is furthermore confirmed by the situation at Node 2.
By propagating the detected directions, many directions of unassigned edges
can be determined using this strategy. The red arrows in Fig. 4 show therecovered directions after applying the second direction estimation step.
Third, since the direction of edges of looping strokes and double traced
edges still cannot be determined by using the first two steps, some special
operations are performed on the remaining edges. Double traced edges aredetected by counting the degree of the two nodes of the edge. If one orboth nodes have an odd-number degree (Node 5 in Fig. 4) and the directionis unknown, the edge is treated as a double traced edges. All the edges
identified as double traced are then duplicated. By this duplication, all nodes(except for the ending nodes) have an even-number degree. The duplicatedlines are indicated by purple double-arrows in Fig. 4.
The direction of loop edges are determined by a simple strategy calledbasic trace algorithm(BTA) (Kato and Yasuhara, 2000). According to BTA,
when we arrive at an intersection node (i.e., a node with degree 4), we willtake the center path. For example, when coming from Node 1 to Node 2 inFig. 4 we take the center path and go to the top-right direction. The green
arrows in Fig. 4 represent the directions finally detected.
As a result of these steps we obtain the direction information of all edges.
Now we start to trace the lines at the top-left edge with an end-node of
degree 1 and an outbound direction. When arriving at a node of degree > 3
during tracing, we go into the direction of a loop and also consider the BTA
in tied situations. After reaching an end, the next untraced edge with an
end-node of degree 1 is taken into account, etc.

13

345

5.5. Data Decoding
Since we have a sequence of the embedded ink-dots by the above processes,
we now decode the sequence to retrieve the embedded information. The decoding process starts with the recovery of the bit information, i.e., 1-pulse
and 5-pulse lines and synchronization blobs, of every ink-dot, just by checking its size. The sequence is separated into frames using the synchronization
blobs. Larger gaps are detected within each frame and assumed as the gaps
between block.
Next, a plausibility control is performed on the extracted data. For eachblock, the number of bits (bB) is confirmed. Sometimes a block has spurious
bits, resulting from a wrong mapping or just from noise. In this case, thoseadjacent bits whose distance deviates too much from the mean distance aredeleted. If the number of bits and blocks do not correspond to the values bB
and bF , the frame is rejected.
For detecting and correcting errors, the Reed-Solomon error correction ischosen. Details follow in the next section.

346

6. Error Correction

330
331
332
333
334
335
336
337
338
339
340
341
342
343
344

347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365

The process of embedding the ink next to the handwritten stroke is always
accompanied with several errors. First, the black ink sometimes overlaps with
the information ink (Fig 5 (b)). Second, several ink-dots might overlap atturning points or stopping points (Fig 5 (c)). Finally, the consecutive inkdots on double traced strokes (Fig 5 (d)), are missed because we discardedthem.
In order to recover from the errors, some redundant information has tobe added. Simple and intuitive ideas would be to apply repetition and parity
check (Liwicki et al., 2010a). However, these encodings show some limitations, especially when it comes to more complicated handwritten patterns
like signatures or handwritten words with many crossings and double strokes.
In this paper we use Reed-Solomon error correction (MacWilliams andSloane, 1977; Reed and Solomon, 1960) for reliably recovering from the occurring errors. The idea is to oversample a polynomial f (x) = a1 + a2 · x1 +. . . + ak · x(k−1) from the data with more points aj than needed. This makes
the polynomial overdetermined. Therefore it is not needed to recover all
points correctly as long as enough points are present. The only drawback ofthis encoding is that the position j of each point aj needs to be known for areliable decoding. In this paper we design each frame to be comprised of two
14

(a)

(b)

(c)

(d)

Figure 5: (a) Example of a difficult pattern. (b)–(d) Specific regions of the pattern.

366
367
368
369
370
371
372
373
374
375
376
377
378
379
380

blocks, the first block for the position of the point and the second block for
its value. While the details of Reed-Solomon codes can be found in Reed andSolomon (1960), in this paper only the important parameters and propertiesof this encoding scheme are given.
The first parameter of Reed-Solomon encoding is the base m bits for the
points. In this paper we have set m = 4. This choice of this value is based on
the observation that previous experiments have shown that shorter frames
have a higher probability of being correctly decoded. Each frame consists of
8 bit; 4 bit for the position and 4 bit for the value.
The next parameter is the length n of the code (including data and error
correction bits). Typically this value is set to its maximum value n = 2m − 1(the values have to be non-zero). This code is divided into k data points (thedata to be encoded) and n − k points for error correction. Given the k data
points a1 , . . . , ak (a message to be encoded), the other values a(k+1) , . . . , anof the polynomial are determined and all n points are encoded (sent).6 If the6

The determination of the values is based on the primitive element of the finite field

15

381

handwritten patterns are long enough, the code is repeatedly embedded.
In the decoding phase, not all n points need to be correctly recovered.
Assuming that c points were correctly recovered, s points are missing (erasures) and e points are erroneous, the code can still be correctly decoded if
the following equation holds:
2e + s ≤ n − k

(1)

391

This important property makes the Reed-Solomon codes very useful for applications where burst errors occur. In our case usually the a whole block canbe either recognized or not, i.e., it rarely occurs that just one bit is missing(even if only one bit is missing, we do not know the position of the bit).
Since we encode the positions of the points in the frame, the positionsof the missing points are known before decoding. In the extreme case, up
to n − k points can be missing and still it would be possible to decode theinformation correctly. In the other extreme case, i.e., if there is no missing
point, up to (n − k)/2 errors are allowed to occur, which means for eacherroneous point, one more correct point should be at hand.

392

7. Experiments and Results

382
383
384
385
386
387
388
389
390

393
394
395
396
397
398
399

400
401
402
403
404
405

The aim of our experiments is to prove that the concept of the dataembedding pen can be applied to real data and works on patterns with various complexity. Therefore, after optimizing the system on a few patterns
written by one writer and testing them on an independent set of patterns
contributed by the same writer, we asked second, independent writer to write
down several patterns. This makes sure that there is no bias between thesystem and the handwriting of one writer.
7.1. Data
Three sets of data-embedded handwriting were collected using the current pen prototype. The first set (Set1) contains 50 horizontal straight lines
with a length of 20 cm. All lines have been drawn with approximately thesame velocity, i.e., the usual writing speed. Experiments with varying velocity appear in Liwicki et al. (2010a). The second set (Set2) contains patterns
α and finding a function f (x) for which holds f (α(i−1) ) = ai , for i = 1, . . . , k and thenapplying f (x) to the remaining αi , i = k, . . . , n − 1.

16Figure 6: Example images of Set2.

406
407
408
409
410
411
412
413
414

which might appear in a real world scenario, i.e., 12 “@” symbols, 12 checkmarks, 12 simulated signatures, and 12 instances of the handwritten word
“Clever”. The former two symbols have sizes of 3 × 3 cm at maximum, thelatter symbols have a size of 4×3 cm. Examples for these patterns are shownin Figs. 5 and 6.
The third set contains significantly more data contributed by the second
writer. This writer contributed with 80–120 samples for each of the following patterns (the sizes mentiond in brackets correspond the height of therespective pattern):

415• straight lines (5cm) in all four directions (right, left, up, down)

416• “@” symbols (sizes: 3 cm and 5 cm)

417• checkmarks (sizes: 3 cm and 5 cm)

418• the word “Clever” (height 4 cm)

419• closed circles (diameters: 5 cm and 3 cm)

420• “X” (sizes: 3 cm and 5 cm)

421• Cursive “ll” (sizes: 3 cm and 5 cm)
17

422
423
424
425
426
427
428
429
430
431
432

433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455

All examples have been written by the second person who was not awareof the processing methods. Note, however, that the writer was asked towrite the patterns quite fast (using usual writing speed), because there has
to be some distance between consecutive ink-dots in order to make themdistinguishable.
We intentionally asked the writer to write lines in both orientations inhorizontal and vertical direction (resulting in four categories), as well as
circles and “X”-shapes, because it is not possible to perfectly recover the
trajectory information for these patterns if no information ink is available.
Note, that for these patterns the original stroke-recovery method of Katoand Yasuhara (2000) would fail.
7.2. Reed-Solomon Encoding
For the Reed-Solomon encoding, the Shifra Open Source error correctingcode library was used7 . We used a Galois field polynomial of the order 4. The
code length was fixed to 15 points (24 − 1), each point being a hexadecimal
number (4 bit).
One aspect of our experiments is to estimate a useful value for the parameter k, i.e., the number of data points, as introduced in Section 6. We
have varied k from 1 to 15. In order to overcome needless calculations,
we applied the following strategy. First, we set k = 1 with a1 = 1 andcomputed the other values ai for this setting. The resulting code word is1, 9, 13, 15, 14, 7, 10, 5, 11, 12, 6, 3, 8, 4, 2. If we now set k = 2 and a2 = 9, thesame values for aj |j > 2 would be estimated, and so on. This means that
only the encoding of this code is needed and during decoding we can choose
the actual value for k. This makes the full use of all collected data, i.e., it is
not needed to write down new patterns for each value of k. Note that using
this strategy also eliminates side-effects like more noise in some patterns,
because always the same patterns are used for the evaluation.
In the experiments on Set1 we wanted to find out how much information
can be embedded in a straight line. In this experiments only very few decoding errors occur on the frame level since there are no crossings. Figure 7
provides an example for the extraction result of a 5 cm long part of a straightline where no errors occurred. The only problem were some overlapping inkdots due to a slow pen-movement. This happened in about 10 % of the7

Available at http://www.schifra.com/ — last visited: November 201118

Table 1: Correctly recovered patterns for Set1 (varying line lengths) and Set2 in %# data points (k) # bits
1
4
8
32
9
36
10
40
11
44
12
48
13
52
14
56
15
60

5 cm
100
100
94
72
56
20
0
0
0

10 cm
100
100
100
100
100
100
100
100
92

hook
100
100
83
75
58
50
17
17
0

@ Meyer Clever
100
100
100
100
100
100
100
75
100
92
50
100
83
33
100
50
0
83
8
0
42
0
0
0
0
0
0

(a)

(b)
Figure 7: (a)Extraction result (after thinning) of a 5 cm long line of Set1 (enlarged). (b)A problematic case where the information ink is smudged by the ballpoint pen.
456
457
458

459
460
461
462
463
464
465
466
467

frames. Note that these frames were rejected during the frame decoding steppresented in Section 5.5, resulting in missing points for the Reed-Solomon
error correction.
7.3. Results for Set1
As stated above, the straight lines had a length of 20 cm. Since the code
was repeated, no errors occurred on these long lines. We decided to measure
the results on shorter lines. Therefore we cut the line first into 10 cm partsand finally into 5 cm parts.
The results of the experiments on Set1 appear in Table 1. This tableshows the percentage of samples where the information could be correctly
recovered by using the Reed-Solomon error correction. Up to a number ofk = 8 the codeword was always correctly recovered even for straight lines as
19

468
469
470
471
472
473
474
475
476
477
478
479
480
481

482
483
484
485
486
487
488
489

490
491
492
493
494
495
496
497
498
499
500
501
502
503

short as 5 cm. For larger k value, the performance decreases, because only alimited number of frames appear in a 5 cm line. (In Fig. 7 (a), for example,
10 points (frames) appear.) For the length 10 cm there were only problems
if no error correction point appears, i.e., it occured 8 times that there was a
missing point which could not be recovered.
In order to investigate the influence of using Reed-Solomon error correction we have performed experiments without using this correction scheme.
Alternatively, parity bits were used for each frame (Liwicki et al., 2010a).
The advantage of using parity bits is that more data could be embedded
into each frame; the disadvantage, however, is that it is harder to recoverfrom burst errors. For both line lengths the recovery rate of the parity-bit
method was only half of the Reed-Solomon based error correction (Liwicki
et al., 2010b). Therefore we conclude that using Reed-Solomon encoding is
the superior strategy.
7.4. Results for Set2
Table 1 presents the results of the experiments on Set2 on the rightcolumns. On all patterns, codes of length 32 could be correctly recovered.
It is a very interesting result that even on the more complicated patterns
the correct information could be decoded. The main reasons for unsuccessful
decoding are either missing points (for short sequences like the hook) or someerrors, e.g., a 1-bit was interpreted as a 0-bit if it was partially occluded byblack ink (first frame of Fig 5 (b)).
7.5. Results for Set3
In our experiments on Set3 we first evaluated the performance of thestroke recovery methods. A method without taking advantage of the stroke
direction embedded into the ink-dot sequence, i.e., the approach of Katoand Yasuhara (2000), has been used as a reference system. The accuracy isdefined as the number of edges with a correctly identified direction divided
through the number of all edges.
The results of the trajectory recovery appear in Table 2. As can be seen,
the algorithm of Kato and Yasuhara (2000), denoted as “System 1”, performs
already good on many patterns. However, it has some complications withclosed circles, lines which go against the more common direction, and twostroke patterns.
Using the embedded information significantly increases the performance.
Our method, denoted as “System 2”, works perfect on most patterns. Only20

Table 2: Performance comparison on Set3

Systemcircleslines
3 cm 5 cm down right up left
Direction detection accuracy in %1. Kato and Yasuhara (2000)
—
—
100
100
0
0
2. Proposed
100
100
100
100 100 100
3. With post-processing
100
100
100
100 100 100
Number of embedded bits if 100% information recovery rate is desired
3.
40
40
32
32
32
32
System

“x”
“ll”
hooks
clever3 cm 5 cm 3 cm 5 cm 3 cm 5 cm
Direction detection accuracy in %
1.
50
50
100
100
100
100
80
2.
79
98
45
100
100
100
95
3.
79
98
100
100
100
100
96
Number of embedded bits if 100% information recovery rate is desired
3.
16
36
20
44
12
32
40
504
505
506
507
508
509
510
511
512

513
514
515
516
517
518
519

small patterns introduce some complications. An idea for post-processing
is to apply the method of Kato and Yasuhara (2000) if only a single edge
is available and no direction could be determined. The row indicated with
“System 1” shows the performance if this strategy is applied. The final
method performs with 100 % on 10 out of 13 patterns.
The retrieval results for Set3 are shown in the last row of Table 2. Thisrow shows the maximum amount of encoded bits if a perfect retrieval of allembedded information is desired. Note that the value for large patterns (size5cm) is at least 32. This result is similar to the results obtained on Set2.
7.6. Failure Analysis
An analysis of the failures shows that during acquisition some of the inkdots were overlapping the pen-stroke. Specifically, when the tip of the ballpoint pen touches already existing information ink-dots, the ink is smudged
by the pen. Our algorithm is not able to recover the correct information(Fig. 7 (b)). In future we will try to tackle this problem by improving theimage processing technologies.
21

520

521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556

8. Conclusions and Ideas for Further Research
In this paper we have presented a successful realization of the dataembedding pen. This pen makes it possible to augment handwritten patterns
with additional information like the time of writing, the writer ID, and otherapplication-dependent data. The main idea is to encode the desired information in an ink-dot sequence plotted nearby the writing strokes. The hardware
design as well as the methods for embedding and recovering information havebeen also described.
We proposed the use of the Reed-Solomon error correction scheme for successfully encoding and recovering the meta-information. The Reed-Solomoncorrection scheme uses an overdetermined polynom for encoding the data.
During decoding only as many correct points are needed as the number ofdata points, disregarding their position. Other missing points do not damage the result. For each erroneous point one more correct points is needed
to recover from the error.
In our experiments we have shown that the Reed-Solomon error correction
scheme is very useful if applied as proposed in this paper. In a first set ofexperiments, using a stroke length of just 5cm, 32 bits of information could
be successfully embedded and recovered from straight lines.
In the second set of experiments we have used more complex patterns,
ranging from symbols to handwritten words. Even in this setup we could
always recover 32-bit of information. Note that 32 bit is enough to distinguish
232 people. This implies that if a company uses this tiny marks for showingthat a certain employee has checked a document, it is possible to identify
which employee has checked the document. Also note that small read/write
RFID-cards usually allow to store the same amount of information (32 bit).
These results have been confirmed on patterns contributed by anotherwriter in a third data set. On this set, we have furthermore shown, that thedirection recovery was improved by using the properties of the information
ink-dots. In most cases, the directions of all edges have been correctly identified. Only short edges in complicated patterns were sometimes not correctly
recovered. However, this did not harm the information retrieval process as
Reed-Solomon error correction has been applied.
An interesting property of the data-embedding is that the shape of then-pulse lines could be used to retrieve even more information about the
dynamics. The speed information, for example, can be derived from theblocks within the frames. Since a new n-pulse line starts every 10 ms, the22

Figure 8: Different length of the n-pulse lines depending on the velocity. (top: low velocity,bottom: high velocity)

563

actual distances between the n-pulse lines encode the speed. Furthermore,
longer n-pulse lines would correspond to faster writing (Fig. 8). Another idea
is to estimate the tilt of the pen by using the correspondence informationfrom the ink-dots to the line (see Section 5). Note that a shorter distancewould indicate a smaller tilt angle if the nozzle is mounted on the pen as inFig. 1 (top). Experimenting the accuracy of these algorithms is left to future
work.

564

References

557
558
559
560
561
562

565
566
567

Doermann, D. S., Rosenfeld, A., 1995. Recovery of temporal information fromstatic images of handwriting. International Journal of Computer Vision15 (1-2), 143–164.

570

Hecht, D. L., 1994. Embedded data glyph technology for hardcopy digital
documents. In: Color Imaging: Devide-Independent Color, Color Hardcopy and Graphic Arts III. Vol. 2171. pp. 341–352.

571

Jain, A., 1989. Fundamentals of Digital Image Processing. Prentice-Hall.

568
569

572
573

574
575

Kato, Y., Yasuhara, M., 2000. Recovery of drawing order from single-stroke
handwriting images. IEEE Trans. Pat. Anal. Mach. Intell. 22 (9), 938–949.
Liwicki, M., Akira, Y., Uchida, S., Iwamura, M., Omachi, S., Kise, K.,
Sep. 2011. Reliable online stroke recovery from offline data with the data23

576
577

578
579
580

581
582
583
584

585
586

587
588
589

590
591
592

593
594
595

596
597
598

599
600

601
602
603
604

605
606

embedding pen. Proc. 11th International Conference on Document Analysis and Recognition (ICDAR 2011), 1384–1388.
Liwicki, M., Uchida, S., Iwamura, M., Omachi, S., Kise, K., 2010a. Dataembedding pen — augmenting ink strokes with meta-information. In: 9th
Int. Workshop on Document Analysis Systems.
Liwicki, M., Uchida, S., Iwamura, M., Omachi, S., Kise, K., 2010b. Embedding meta-information in handwriting — Reed-Solomon for reliable error
correction. In: 12th International Conference on Frontiers in Handwriting
Recognition. pp. 51–56.
MacWilliams, F. J., Sloane, N. J. A., 1977. The Theory of Error-Correcting
Code. New York: North-Holland Publishing Company.
Nel, E.-M., du Preez, J. A., Herbst, B. M., 2005. Estimating the pen trajectories of static signatures using hidden markov models. IEEE Trans. Pat.
Anal. Mach. Intell. 27 (11), 1733–1746.
Nguyen, V., Blumenstein, M., 2010. Techniques for static handwriting trajectory recovery: a survey. In: Proceedings of the 9th IAPR International
Workshop on Document Analysis Systems. pp. 463–470.
Plamondon, R., Srihari, S. N., 2000. On-line and off-line handwriting recognition: a comprehensive survey. IEEE Trans. Pat. Anal. Mach. Intell. 22 (1),63–84.
Reed, I. S., Solomon, G., 1960. Polynomial codes over certain finite fields.
Journal of the Society for Industrial and Applied Mathematics 8 (2), 300–
304.
Simon, M., Behnke, S., Rojas, R., 2000. Robust real time color tracking. In:
RoboCup-2000. pp. 239–248.
Uchida, S., Tanaka, K., Iwamura, M., Omachi, S., Kise, K., 2006. A DataEmbedding Pen. In: Tenth International Workshop on Frontiers in Handwriting Recognition.
URL http://hal.inria.fr/inria-00103878/en/
Vinciarelli, A., 2002. A survey on off-line cursive script recognition. Pattern
Recognition 35 (7), 1433–1446.
24

Highlights> A pen device for embedding meta-information in offline handwriting> Reliable Stroke Recovery using SotA-methods and additional ink> Error-tolerant data-decoding by using Reed-Solomon Codes> 32 bits embedding is possible allowing for various applications