File: rfc199.txt

package info (click to toggle)
doc-rfc 20181229-2
  • links: PTS, VCS
  • area: non-free
  • in suites: buster
  • size: 570,944 kB
  • sloc: xml: 285,646; sh: 107; python: 90; perl: 42; makefile: 14
file content (563 lines) | stat: -rw-r--r-- 18,660 bytes parent folder | download | duplicates (5)
1
2
3
4
5
6
7
8
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
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
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
156
157
158
159
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
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
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
280
281
282
283
284
285
286
287
288
289
290
291
292
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
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
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
456
457
458
459
460
461
462
463
464
465
466
467
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
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
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
557
558
559
560
561
562
563






Network Working Group                                        T. Williams
Request for Comments: 199                                            SDC
NIC: 7151                                                   15 July 1971


        SUGGESTIONS FOR A NETWORK DATA-TABLET GRAPHICS PROTOCOL

Disclaimer

   The work reported herein was supported by the Advanced Research
   Projects Agency of the Department of Defense under Contract DAHC15-
   67-C-0149, ARPA Order No. 1327, Amendment No. 3, Program Code No.
   1D30, and 1P10.

   The views and conclusions contained in this document are those of the
   author and should not be interpreted as necessarily representing the
   official policies, either expressed or implied, of the Advanced
   Research Projects Agency or the U. S. Government.

INTRODUCTION

   The purpose of this document is to add SDC's comments to the
   discussion of a protocol for network graphics within the ARPA Network
   community.  In general, we are concerned with the development of the
   graphics protocol in two areas: non-interactive graphics and data-
   tablet graphics, as opposed to fully interactive graphics.  By non-
   interactive graphics we mean situations in which there is little or
   no requirement for interaction with displays.  Such displays are
   used, for instance, in data retrieval systems using graphics to
   display retrieved information in the form of charts, X-Y graphs,
   histograms, scatter plots, tabular displays, etc.  In these systems,
   each interaction with the system produces an entirely new display.
   The displays themselves have little, if any, structure.  There is no
   necessity to interact with the picture itself other than, perhaps, by
   the use of light buttons.  It is important that non-interactive
   graphics be simple to implement and use on the network.  Therefore,
   we suggest that the graphics protocol design be based upon non-
   interactive graphics systems and that capabilities needed for
   interactive graphics be added as a super-set.  This will ensure that
   the protocol complexities associated with interactive graphics do not
   impose problems for the user of non-interactive graphics, as they
   would if a non-interactive subset were developed from a protocol
   based initially on interactive graphics.  The section of Request for
   Comment (RFC) 177 describing actual display instructions contains a
   good basis for the development of a non-interactive graphics
   protocol.  With it as a starting point, a protocol for the generation
   of a picture can be developed, and the organizational and structural
   information useful for interactive graphics can be developed later.



Williams                                                        [Page 1]

RFC 199          SUGGESTIONS FOR A NETWORK DATA-TABLET      15 July 1971


DATA-TABLET GRAPHIC INPUTS

   Our primary topic of concern is data-tablet graphics.  Though there
   are a variety of data-tablet implementation, their functional
   characteristics are similar enough that they can be treated as a
   single class.

   Data-tablet input consists of a triple of information--X, Y, Z--where
   X is the distance along the abscissa, Y is the distance along the
   ordinate (the two quantities are usually measured to a precision of 1
   in 1024), and Z is the distance above the writing plane.  There are a
   variety of encodings for Z, from a simple binary quantity, on or off,
   to three or more values giving various distances, from on the surface
   to several inches above; for our purposes here, we will consider Z as
   a binary entity.

   Input timing may also vary, depending on the tablet implementation
   and installation interface.  Timing varies from a single shot, where
   only one coordinate point is input for each new time that Z indicates
   that the stylus is on the writing surface; to asynchronous, where the
   tablet input is sampled on demand from the driving program or
   interface logic when certain conditions are met, such as that the pen
   has moved a certain amount from the previous sample or that the
   program is ready for another data sample after a variable amount of
   processing; to clocked synchronous, where a timing pulse provides the
   sampling demand.  Clock rates vary from a few (one or two) samples
   per second to nearly 5000 samples per second.  Some clocks are fixed,
   while others are controlled either by program or external switches.

   Relative to the amount of picture information contained in the data
   stream, in general, the data-tablet input is far more voluminous than
   a similar computer generated image.  Additionally, the data-tablet
   input stream contains temporal information that, in certain cases, is
   vital to the proper processing of the input.  Therefore, ways must be
   found to implement a data-tablet graphics protocol that is flexible
   enough to accommodate a broad spectrum of data volume and that is
   compatible with the protocol for non-interactive display images.

PROPOSED DATA-TABLET INPUT PROTOCOLS

   Data tablet input can consist of anything from a single point (as
   would occur when something was being pointed at) to literally
   thousands of bytes representing a hand-drawn rendering of a picture
   or a line of text.  In many instances, the raw data-tablet input is
   preprocessed before it is passed to the principal processing program.
   This preprocessing can consist of such things as a variety of
   smoothing algorithms, filtering for thinning and or redundancy
   removal, detection of certain operator actions such as uniquely



Williams                                                        [Page 2]

RFC 199          SUGGESTIONS FOR A NETWORK DATA-TABLET      15 July 1971


   marking each occurrence of placing the pen on the writing surface and
   raising it, and possibly other, more exotic processes such as corner
   detection, fitting straight-line segments, and the like.  Most of
   these latter processes will not be considered for inclusion in the
   protocol, since they are usually unique to a particular investigator
   and his research.

   Therefore, a data-tablet graphic protocol should permit the sender to
   specify, and the receiver to discriminate among, at least four types
   of data-tablet input:

      1)  Single-shot data

      2)  Unpreprocessed (raw) asynchronous data

      3)  Unpreprocessed (raw) synchronous data

      4)  Preprocessed data

   We will define formats for the first three, then discuss the fourth
   in some detail before defining its format.

   To reduce the number of bits transmitted, data-tablet information
   should be transmitted in incremental form:  a first point, followed
   by the difference between each point and its predecessor.  To
   eliminate the trailing zeros that may be required for compatibility
   with the standard network graphics screen, we have included provision
   for a scale factor by which all increments should be multiplied
   before use.

      Single-Shot Data Input Format:

      Byte 0:   Data tablet input op code

      Byte 1:   Type, 0 = single shot

      Byte 2-3: X - Coordinate

      Byte 4-5: Y - Coordinate

            8          8            16             16
      +----------+----------+---------------+---------------+
      | Op code  |     0    |   X - coord.  |    Y coord.   |
      +----------+----------+---------------+---------------+
            0          1         2     3         4     5






Williams                                                        [Page 3]

RFC 199          SUGGESTIONS FOR A NETWORK DATA-TABLET      15 July 1971


   In the following proposal for other protocols, it is assumed that
   each "stroke" of the pen is sent as one entity, a stroke being the
   data generated (and processed) between the time that Z indicates that
   the stylus or pen is on the writing surface and the time it is lifted
   from the surface.

      Unpreprocessed (Raw) Asynchronous Data Input Format:

      Byte 0:     Data tablet input op code

      Byte 1:     Type, 1 = raw asynchronous

      Byte 2:     Flags

      Byte 3:     Scale of deltas

      Byte 4-5:   Number of points

      Byte 6-7:   1st X-coordinate

      Byte 8-9:   1st Y-coordinate

      Byte 10:    delta X1

      Byte 11:    delta Y1

          .
          .
          .

      Byte 2n+10: delta Xn

      Byte 2n+11: delta Yn


 8   8    8     8      16      16      16     8     8        8     8
+--+---+-----+-----+---.---+---.---+---.---+-----+-----+  +-----+-----+
|Op| 1 |Flags|Scale|  N.o  |   .   |   .   |delta|delta|..|delta|delta|
|  |   |     |     |poi.nts| X0.   | Y0.   | X1  | Y2  |  | Xn  | Yn  |
+--+---+-----+-----+-------+-------+-------+-----+-----+  +-----+-----+
 0   1    2     3    4   5   6   7   8   9   10     11     2n+10 2n+11










Williams                                                        [Page 4]

RFC 199          SUGGESTIONS FOR A NETWORK DATA-TABLET      15 July 1971


      Unpreprocessed (Raw) Synchronous Data Input Format:

      Byte 0:     Data tablet input op code

      Byte 1:     Type, 2 = raw synchronous

      Byte 2:     Flags

      Byte 3:     Scale of deltas

      Byte 4:     Sampling rate to the nearest 100 usec

      Byte 5-6:   Number of points

      Byte 7-8:   1st X-coordinate

      Byte 9-10:  1st Y-coordinate

      Byte 11:    delta X1
                          (sign magnitude code)
      Byte 12:    delta Y1
          .
          .
          .

      Byte 2n+11: delta Xn

      Byte 2n+12: delta Yn

 8  8   8     8    8     16      16    16    8     8        8     8
+--+-+-----+-----+----+---.---+---.-+---.-+-----+-----+  +-----+-----+
|Op|2|Flags|Scale|Rate|  N.o  | X0. | Y0. |delta|delta|..|delta|delta|
|  | |     |     |    |poi.nts|   . |   . | X1  | Y1  |  | Xn  | Yn  |
+--+-+-----+-----+----+----------+--+-----+-----+-----+  +-----+-----+
 0  1   2     3    4    5   6  7  8  9  10   11   12      2n+11 2n+12
















Williams                                                        [Page 5]

RFC 199          SUGGESTIONS FOR A NETWORK DATA-TABLET      15 July 1971


PREPROCESSED-DATA INPUT FORMAT

   There are a variety of processes that can be applied to raw tablet
   data before it is transmitted to the requesting program.  For
   instance, when the tablet is "noisy" or jittery, various smoothing
   algorithms may be applied.  The most common of these is some form of
   weighted, clumped or moving average.  At SDC, we have settled on an
   8-point moving average when smoothing is desirable.  Another fairly
   common form of preprocessing is "thinning" or filtering to remove
   unnecessary or redundant data points.  Depending on the end use of
   the data, filter "windows" can have a variety of geometries,
   including square, rectangular, diamond, and circular, and the filter
   may be single or double windowed.  SDC currently uses a single square
   window filter on all tablet input.  The window size is a variable and
   may be set to zero, thus, eliminating the filter.

   Logically, the filter may be described as:

      Take (X,Y) if |Xp - X| >= w or |Yp - Y| >= w is true

   where: (X,Y) is the current data point, (Xp,Yp) is the previously
   accepted data point that either passed the filter or was the first
   point of the stroke, and w is the window size.

      Pictorially, this can be represented as:

         ---- +-------------+-----
          ^   |             |  ^
          |   |             |  |
              |             |  W
          2W  |  Xp, Yp   __|__v__
              |             |
          |   |             |
          v   |             |
         -----+-------------+
              | <-- 2W -->  |

   Any point inside the square will be rejected, any point on the
   boundary or beyond is accepted and becomes (Xp,Yp).  In addition to
   smoothing and filtering, we have found it necessary that our
   character recognition algorithms be able to estimate the velocity
   along the path of the stroke.  Therefore in addition to saving the X,
   Y coordinates that pass the filter (smoothing, if done, precedes
   filtering and is done on the raw points), we count and store the
   number of rejected points between the saved ones.  Since the data-
   tablet input is synchronous, the count times the sampling rate
   divided into the distance between adjacent points is a sufficient
   approximation for our purposes.  Our character-generator also



Williams                                                        [Page 6]

RFC 199          SUGGESTIONS FOR A NETWORK DATA-TABLET      15 July 1971


   requires the rectangle surrounding a stroke (defined by the minimum
   and maximum values of X and Y in the stroke); this information is
   very easy to generate during preprocessing.

   Assuming that other Network nodes wanted to use SDC's tablet graphic
   software--the character recognizer in particular--we would have to
   know what, if any, preprocessing was done to the input data before it
   was sent.  Our suggested format for this from of tablet data, then,
   is:

      Byte 0:     Data tablet op code

      Byte 1:     Type, 3 = preprocessed

      Byte 2:     Flags

      Byte 3:     Scale of deltas

      Byte 4:     Sampling rate if synchronous (as indicated by flag)

      Byte 5:     Window Size

      Byte 6-7:   Number of Points

      Byte 8-9:   1st X-coordinate

      Byte 10-11: 1st Y-coordinate

      Byte 12-13: Minimum value of X in the stroke

      Byte 14-15: Minimum value of Y in the stroke

      Byte 16-17: Minimum value of X in the stroke

      Byte 18-19: Minimum value of Y in the stroke
















Williams                                                        [Page 7]

RFC 199          SUGGESTIONS FOR A NETWORK DATA-TABLET      15 July 1971


   Two forms follow from here, depending upon another flag:

        Counts included         and       Counts deleted

        Byte 20:       delta X1           Byte 20:         delta X1

        Byte 21:       delta Y1           Byte 21:         delta Y1

        Byte 22:       rejected point count1

        Byte 3n+20:    delta Xn           Byte 2n+20:      delta Xn

        Byte 3n+21:    delta Xn           Byte 2n+21:      delta Yn

        Byte 3n+22:    RPCn

8  8   8     8     8     8      16    16   16   16    16    16    16
--+-+-----+-----+-----+------+------+----+----+-----+-----+-----+-----+
  |3|Flags|Scale|Rate |Window|  #   | X0  | Y0 |Xmin|Ymin |Xmax |Ymax |
  | |     |     |     | Size |points|     |    |    |     |     |     |
--+-+-----+-----+-----+------+------+----+----+-----+-----+-----+-----+
 0 1   2     3     4     5     6  7  8 9 10 11 12 13 14 15 16 17 18 19


  8     8     8        8     8     8
-----+-----+-----+-//-----+-----+-----+
delta|delta| RCP1| //delta|delta| RCPn|
X1   |Y1   |     |    Xn  | Yn  |     |
-----+-----+-----+-//-----+-----+-----+
 20    21    22       20     21    22

                       Counts Included



















Williams                                                        [Page 8]

RFC 199          SUGGESTIONS FOR A NETWORK DATA-TABLET      15 July 1971


8  8   8     8     8     8      16    16   16   16    16    16    16
--+-+-----+-----+-----+------+------+----+----+-----+-----+-----+-----+
Op|3|Flags|Scale|Rate |Window|  #   | X0 | Y0 |Xmin |Ymin |Xmax |Ymax |
  | |     |     |     | Size |points|    |    |     |     |     |     |
--+-+-----+-----+-----+------+------+----+----+-----+-----+-----+-----+
 0 1   2     3     4     5     6  7  8 9 10 11 12 13 14 15 16 17 18 19


  8     8     8        8     8
-----+-----+-----+   +-----+-----+
delta|delta|delta|...|delta|delta|
X1   |Y1   |  X2 |   |Xn   |Yn   |
-----+-----+-----+   +-----+-----+
 20    21    22       2n+20 2n+21

                       Counts deleted


   The flags in this format not only indicated whether or not the data
   is synchronous and whether the counts are present, but may also be
   used to indicate whether or not the data was smoothed and the type of
   filtering.

CHARACTER SETS AND CHARACTER GENERATION

   Our work in character recognition impacts the proposed protocols in
   one other area, that of character sets and character generation.
   Figure 1 shows the displayable characters presently available.  We
   have planned extensions that will bring the set to 192 characters.
   The availability and use of our and others' extended character sets
   must be provided for in the protocol.

   The character-set problem, though, is the easy one.  We have found
   that when dealing with hand-printed input, the computer-generated
   output must be flexible enough to retain the geometry of the user's
   input--at least temporarily.  This requires that we be able to
   generate characters in a large variety of sizes, with variable aspect
   ratios (independently specified sizes for X and Y).  Since this is
   not an available hardware function, all of our characters are program
   generated.  We currently specify character size and ratios in terms
   of X and Y multipliers applied to a character prototype.  The
   character prototype is constructed on a 5" x 7" grid (extended, if
   necessary to handle the long tails on p's, q's, etc.), where the
   grid-line spacing is 2^-10 times the screen size.  The important
   point is that network transmission must be capable of specifying
   those types of characteristics when needed.





Williams                                                        [Page 9]

RFC 199          SUGGESTIONS FOR A NETWORK DATA-TABLET      15 July 1971


   We propose, then, that a message format that specifies:

   o Character code
   o Character position
   o Character height and width

   As an inside, we would rather that the character origin be the left-
   hand baseline point rather than the center--primarily because the
   center is ill-defined unless the character space is specified to
   include vertical extensions in both directions but also because it is
   difficult to take advantage of variable spacing to justify characters
   that are of unequal width (an aesthetic consideration of relevance in
   some displays).

   Figure 1: SDC EXTENDED CHARACTER SET (see PDF file)

Endnote

   Subscript notation is inline.  See the PDF file for a complete view
   of this document.


         [This RFC was put into machine readable form for entry]
         [into the online RFC archives by Lorrie Shiota, 10/01]



























Williams                                                       [Page 10]