Back to the Future of Handwriting Recognition

An Active Essay Revisiting the GRAIL Handwriting Recognizer Jack Schaedler, 2016 Fifty years ago, RAND corporation developed the Graphical Input Language software system (GRAIL). In a RAND memorandum from 1966, the stated objective of GRAIL was to, “Investigate methods by which a user may deal directly, naturally, and easily with [their] problem.” Users communicated with GRAIL using a pen-like instrument and tablet. GRAIL had no mouse, no keyboard, no buttons, no joystick, and none of the other paraphernalia that we generally associate with modern computing. When the user wanted a box on the screen, they drew the box. When the user wanted text on the screen, they handprinted the text. When you watch a demo of the system today, it still feels elegant and magical. To steal a line from Tony Hoare, GRAIL is in many ways an improvement on nearly all of its successors. “This recognition scheme meets its primary objective of enabling any user to communicate naturally with a computer. A user is not distracted by any operational mechanics but, rather, may concentrate on [their] problem.” - Gabriel Groner (1966) The image above depicts Tom Ellis using the RAND tablet to interact with an onscreen image sometime in the 1960s. Ellis was one of the inventors and project leads for the RAND tablet and GRAIL software system. This, and many other images can be found online at the Computer History Museum. In this active essay, we will revisit Gabriel Groner’s contribution to the GRAIL project. Groner developed a wonderfully clever program which recognized handprinted letters, numbers, punctuation marks, and geometric figures. The program was efficient enough to run in real-time on a IBM System/360 computer, and robust enough to properly identify 90 percent of the symbols drawn by first-time users. Groner documented his method in a 1966 RAND memorandum on the Real-Time Recognition of Handprinted Text. By the end of this essay, you should understand exactly how Groner’s handwriting recognition scheme works. More precisely, you will see how Groner’s method works, and develop an intuitive understanding of its various operations and phases. It’s best if you read this essay as a dynamic companion to Groner’s original memorandum. When Groner describes an algorithm or heuristic, this essay will provide you with an interactive implementation that you can explore. When text is taken verbatim from Groner’s memo, it will be rendered in an alternative font. The recognition scheme described in the original memorandum was capable of recognizing a wide variety of symbols, shapes, numbers, letters, and even punctuation marks. In this essay, I will present a simple version of Groner’s recognizer that can only identify uppercase numbers and letters. All of the source code for this essay is publicly available on Github. Please submit all bugs, typos, and suggestions to the issue tracker. Feel free to contact me on Twitter if you have any questions or comments about this piece. In fact, you can read the source code for Groner’s entire program, which he wrote in IBM 360 Assembly. The RAND Tablet “Present-day user-computer interface mechanisms provide far from optimum communication, considerably reducing the probability that full advantage is being taken of the capabilities of either the machine or of the user... It was felt that exploration of man’s existent dexterity with a free, pen-like instrument on a horizontal surface, like a pad of paper, would be fruitful.” - M.R Davis and T.O. Ellis (1964) Humans interacted with GRAIL using a RAND tablet. All input to the system was drawn onto the surface of RAND tablet using a pen-like instrument. The 10.24" × 10.24" tablet had a resolution of 100 lines per inch, making it capable of accurately digitizing more than one million discrete pen positions. A pressure sensitive switch was installed in the tip of the pen, allowing the user to press the pen against the writing surface whenever they wished to make a mark on the screen. The position of the stylus was reported to GRAIL every four milliseconds as a pair of (x, y) coordinates. Below, you will find a virtual tablet on which you can draw and scribble. Like the RAND tablet, this virtual tablet’s surface is discretized. This means that the writing surface is divided into a grid, and all pen positions are reported as coordinates on this grid. While the RAND tablet had a resolution of 100 lines per inch, our virtual tablet has a considerably lower resolution of around 20 lines per inch. Therefore, it is best to imagine our virtual tablet as a small portion of a RAND tablet scaled up by about 500%. Keep this in mind when writing on the tablet. Draw letters and numbers so that they fill up around 70% of the available tablet height. Draw big! To begin drawing, move your pointer over the tablet and press the mouse button. This simulates the act of pressing the stylus against the surface of the tablet. Without releasing the mouse button, move your pointer across the tablet surface to make a mark. When you’re happy with your mark, release the mouse button. Try to get a feel for working on the tablet by drawing a few numbers (2, 3, 6) and letters (C, M, S) that can be completed without lifting the pen from the surface of the tablet. Once you feel comfortable scribbling and drawing on the virtual tablet, scroll onwards to the next section. “A user communicates with the computer via a RAND tablet in conjunction with a cathode ray tube (CRT) display. The tablet hardware consists of a horizontal 10" square writing surface and pen-like writing instrument... When he presses the pen against the tablet writing surface, a switch in the pen closes, thereby notifying the central processing unit (CPU) of a "pen-down action"... When the pen is lifted, the pen-switch is opened, thereby notifying the CPU of a "pen-up" action... As the pen is moved across the writing surface, the recognition scheme is notified of its position every 4 msec.” This was some seriously cool technology for 1963. You can read RAND’s memorandum on the particulars of the design and implementation here. If you’re interested in more anecdotal information about the RAND tablet, watch this video of Alan Kay discussing the Rand tablet. I’m using some less than optimal terminology here because I have no idea what sort of device you might be using to read this essay. I’m fairly certain that - if they aren‘t already - terms like mouse and click will soon feel as anachronistic as a carriage return. That means that you’ll have to do some on-the-fly translation if you happen to be using something mouse-less like a trackpad, touchscreen, or tablet. Smoothing You might have noticed that the marks you make on the tablet will appear with ugly little perturbations and jaggies when they are displayed on the screen. This occurs because the tablet can only report pen positions which lie on a discrete grid. This means that even smoothly drawn curves will inevitably include little bumps and corners after being captured by the tablet. These jaggies look ugly, but more importantly, they add unwanted noise to the list of pen positions. In order to remove this noise, Groner decided to smooth the tablet’s output. "The scheme smoothes the data by averaging a newly arrived data-point with the previously smoothed data-point, thus reducing the noise due to the discreteness of the pen location as measured by the tablet." What Groner describes as noise due to discreteness, you would probably describe as pixelation. The figure below allows you to get a feel for the effects of pixelation or discretization on a smoothly drawn stroke. Press the Draw button to see the “real” path taken by the pen when drawing a smooth curve. Once the curve is drawn, press the Snap button to see the effect of forcing each point to lie on a discrete grid. Notice how the discretization introduces lots of little bumps, corners, and flat segments in what was previously a smooth curve. Fortunately, we can smooth the tablet’s output to liberate these points from the impositions of a fixed grid. The smoothing operation is performed by averaging the position of each new quantized datapoint with the position of the last smoothed datapoint. We can geometrically perform this averaging by drawing a straight line between each quantized datapoint and the most recently smoothed datapoint. We then slide the quantized point along this line towards the previously smoothed point. The further we slide the point, the more we accentuate the effect of the smoothing. You can develop an intuition for this smoothing algorithm using the visualization below. The quantized datapoints are drawn in blue, and the smoothed points will be drawn in black. The three buttons allow you to specify how far each point should slide along the guideline. Higher percentages will lead to a smoother curve. This simple smoothing scheme allows us to rid the data of unwanted bumps and jaggies while still maintaining the overall gesture of the stroke. Note however, that smoothing is a destructive process. Small flourishes of the pen will be obliterated by smoothing. For this reason, it’s crucially important to choose an appropriate smoothing factor. Draw on the tablet below to see how this smoothing scheme will affect more interesting inputs. You can change the degree to which each stroke is smoothed by dragging the slider to the right of the visualization. Spend some time drawing letters, numbers, and simple shapes onto the tablet. I suggest that you begin by drawing a straight line from the bottom left to the top right of the tablet. Once this is done, slowly drag the slider to see how the stroke is transformed as the amount of smoothing is varied. Smoothing is based on the equations, XSi = XSi-1 + XRi YSi = YSi-1 + YRi XRi,YRi = coordinates of ithraw point XSi,YSi = coordinates of ith smoothed point Smoothing Factor: This sort of noise is referred to as quantization noise. Quantization is the process by whic