Dit essay beschrijft de Graphical Input Language (GRAIL), een systeem ontwikkeld door de RAND Corporation in 1966 met als doel mens-computerinteractie direct en natuurlijk te maken. Gebruikers communiceerden via een speciale RAND tablet en stylus, waardoor ze direct op het scherm konden tekenen en schrijven.
Het technische proces van de handschriftherkenning door Gabriel Groner bestond uit vijf hoofdfases:
- Smoothing: Het gebruik van een filter om kwantiseringsruis te verwijderen en curves vloeiender te maken.
- Thinning: Het weggooien van overbodige datapunten om de dataset te verkleinen zonder vormverlies.
- Kromming: Het reduceren van bewegingen tot vier basisrichtingen (boven, onder, links, rechts).
- Hoekdetectie: Het analyseren van richtingsveranderingen van minstens 90° om visueel gelijkaardige tekens (zoals '5' en 'S') te onderscheiden.
- Kenmerkextractie: Het vastleggen van afmetingen, aspect ratio's en relatieve posities binnen een bounding box.
De uiteindelijke identificatie gebeurde via een beslissingsboom van cascades aan if-statements. De auteur betoogt dat dit vroege werk relevant blijft omdat het tekenen als medium met een hoge bandbreedte een krachtige vorm van interface-design is.
GRAIL Tekstherkenner: Terug naar de toekomst van handschriftherkenning
Vijftig jaar geleden ontwikkelde de RAND Corporation het software-systeem Graphical Input Language (GRAIL). In een memorandum uit 1966 werd het doel van GRAIL als volgt geformuleerd: "Methoden onderzoeken waarmee een gebruiker direct, natuurlijk en eenvoudig met [hun] probleem kan omgaan."
Gebruikers communiceerden met GRAIL via een tablet en een pen-achtig instrument. Het systeem had geen muis, geen toetsenbord, geen knoppen en geen joystick — zaken die we tegenwoordig associëren met moderne computing. Wanneer een gebruiker een kader op het scherm wilde, tekende hij dit. Wanneer er tekst nodig was, schreef de gebruiker deze met de hand. Zelfs vandaag de dag voelt een demo van dit systeem elegant en magisch aan; in veel opzichten is GRAIL een verbetering ten opzichte van bijna al zijn opvolgers.
"Dit herkenningsschema behaalt zijn hoofddoel om elke gebruiker in staat te stellen natuurlijk met een computer te communiceren. Een gebruiker wordt niet afgeleid door operationele mechanica, maar kan zich concentreren op [hun] probleem."
— Gabriel Groner (1966)
In dit essay kijken we terug naar de bijdrage van Gabriel Groner aan het GRAIL-project. Groner ontwikkelde een vernuftig programma dat handgeschreven letters, cijfers, leestekens en geometrische figuren herkende. Het programma was efficiënt genoeg om in real-time te draaien op een IBM System/360 computer en robuust genoeg om 90 procent van de symbolen van beginnende gebruikers correct te identificeren. Groner legde zijn methode vast in een memorandum uit 1966 over de Real-Time Recognition of Handprinted Text.
---
De RAND Tablet
Menselijke interactie met GRAIL verliep via een RAND tablet. Alle input werd met een pen op het oppervlak van de tablet getekend. De tablet, met afmetingen van $10,24" \times 10,24"$, had een resolutie van 100 lijnen per inch, waardoor meer dan een miljoen discrete penposities nauwkeurig gedigitaliseerd konden worden.
In de punt van de pen zat een druksensor. Wanneer de gebruiker de pen tegen het schrijfoppervlak drukte, werd dit geregistreerd als een "pen-down"-actie; wanneer de pen werd opgetild, volgde een "pen-up"-actie. De positie van de stylus werd elke vier milliseconden doorgegeven aan GRAIL als een paar $(x, y)$ coördinaten.
---
Smoothing (Afvlakking)
Omdat de tablet penposities rapporteert op een discreet raster, kunnen zelfs vloeiende curves kleine hobbels en hoeken vertonen ("jaggies"). Dit fenomeen staat bekend als quantization noise (kwantiseringsruis). Om deze ruis te verwijderen, paste Groner een smoothing-methode toe.
De werking van smoothing: Het systeem middelt een nieuw binnengekomen datapunt met het laatst afgevlakte datapunt. Geometrisch gezien gebeurt dit door een rechte lijn te trekken tussen het gekwantiseerde punt en het vorige gesmoothede punt, om vervolgens het nieuwe punt een bepaald percentage richting het vorige punt te verschuiven.
- Effect: Hoe hoger het smoothing-percentage, hoe vloeiender de curve.
- Beperking: Smoothing is een destructief proces; kleine versieringen in het handschrift kunnen hierdoor verloren gaan.
Wiskundig gezien is deze methode een toepassing van een infinite impulse response filter.
---
Thinning (Uitdunning)
Bij het langzaam bewegen van de pen worden veel datapunten gegenereerd die overbodig zijn voor het herkennen van de vorm. Groner gebruikte een eenvoudig thinning-schema om dit aantal te beperken:
- Er wordt een vierkant getekend rond het eerste datapunt.
- Alle volgende punten die binnen dit vierkant vallen, worden weggegooid.
- Het vierkant wordt verplaatst naar het eerste punt dat buiten het huidige vierkant valt.
- Dit proces herhaalt zich voor de rest van de streek.
De grootte van het vierkant bepaalt hoe agressief de uitdunning is. Groner ontdekte dat hij tot wel zeventig procent van de ruwe datapunten kon verwijderen zonder de essentiële vorm van de streek te verliezen.
---
Kromming (Curvature)
Na het afvlakken en uitdunnen krijgt elk datapunt een richting toegewezen. Groner stelde vast dat het voldoende was om alleen de windrichtingen (boven, onder, links, rechts) te gebruiken.
Bepaling van de richting: Er wordt gekeken naar de rechthoek die gevormd wordt door een punt en zijn voorganger:
- Is de rechthoek breder dan hij hoog is? Dan is de beweging links of rechts.
- Is de rechthoek hoger dan hij breed is? Dan is de beweging boven of onder.
Alleen de wijzigingen in richting worden opgeslagen. Hierdoor ontstaat een zeer compacte representatie van de kromming. Een letter 'L' wordt bijvoorbeeld beschreven door twee directionele segmenten: $\text{beneden} \rightarrow \text{rechts}$.
---
Hoeken (Corners)
Sommige symbolen kunnen niet alleen op basis van richting worden onderscheiden. Zo kunnen een "5" en een "S" beide resulteren in dezelfde reeks richtingen ($\text{links} \rightarrow \text{beneden} \rightarrow \text{rechts} \rightarrow \text{beneden} \rightarrow \text{links}$). Om dit op te lossen, detecteert het systeem de aanwezigheid van hoeken.
Hoekdetectie: Voor deze analyse gebruikt Groner "16-richtingen" (een cirkel verdeeld in 16 gelijke sectoren). Een hoek wordt gedetecteerd wanneer:
- De pen twee segmenten in dezelfde 16-richting beweegt.
- Er een richtingsverandering van minstens $90^\circ$ plaatsvindt.
- De pen vervolgens weer twee segmenten in de nieuwe richting beweegt.
Dit stelt het systeem in staat om bijvoorbeeld een "5" (die vaak hoeken heeft) te onderscheiden van een "S" (die meestal vloeiend is).
---
Kenmerken van Grootte en Positie
Elke getekende streek wordt verwerkt in een beschrijving die de belangrijkste kenmerken vastlegt ten opzichte van een denkbeeldige bounding box (omsluitende rechthoek).
Geregistreerde data:
- Afmetingen: Hoogte, breedte en de aspect ratio (verhouding hoogte/breedte). Dit helpt bijvoorbeeld bij het onderscheid tussen een '7' en een '1'.
- Posities: Het startpunt (pen-down) en eindpunt (pen-up), evenals de locaties van hoeken. De omhullende rechthoek wordt verdeeld in een $4 \times 4$ raster, waardoor deze punten relatief aan het symbool worden gecodeerd.
---
Karakterherkenning
De identificatie van een symbool gebeurt via een beslissingsboom bestaande uit een reeks tests (geïmplementeerd als cascades van if-statements).
Het proces:
- Initiële filtering: De herkenner begint met de eerste vier windrichtingen van de streek. Symbolen die niet met deze richtingen beginnen, worden direct geëlimineerd.
- Verfijning: Als er meerdere kandidaten overblijven (bijv. 'O', '2' of '3'), wordt gekeken naar andere kenmerken uit de beschrijving:
- Een '2' wordt herkend als de streek eindigt in de rechterbenedenhoek.
- Een '3' wordt herkend als de streek eindigt in de linkerbenedenhoek.
- Een 'O' wordt herkend als het start- en eindpunt dicht bij elkaar liggen aan de bovenzijde.
Hoewel de originele GRAIL-herkenner ook tekens met meerdere streken kon verwerken, is deze vereenvoudigde versie gericht op single-stroke karakters (tekens die in één beweging worden geschreven).
Vergelijking en context
Het herkennen van Latijnse karakters is uitdagend omdat er geen strikte volgorde van streken is. In tegenstelling hiermee heeft het Chinees schrift wel een canonieke volgorde, waardoor handschriftherkenning daar vroeger al succesvoller was. Groner schreef in 1967 zelfs al over de toepassing van zijn schema voor Chinese taalinput.
---
Slotwoord
Waarom zijn mid-century algoritmen nog relevant? Voor de auteur ligt de waarde niet zozeer in de tekstherkenning zelf, maar in het idee dat mensen via het tekenen — een medium met een hoge bandbreedte — kunnen communiceren met computers. Tekenen is een krachtige vorm van communicatie die als primaire of aanvullende methode voor mens-computerinteractie kan dienen.
Het werk van Gabriel Groner en het GRAIL-team biedt een fascinerend inzicht in de vroege geschiedenis van interface-design, een tijd waarin onderzoekers al experimenteerden met interactieve graphics voor complexe wetenschappelijke systemen.
GRAIL Tekstherkenner: Terug naar de toekomst van handschriftherkenning
Vijftig jaar geleden ontwikkelde de RAND Corporation het software-systeem Graphical Input Language (GRAIL). In een memorandum uit 1966 werd het doel van GRAIL als volgt geformuleerd: "Methoden onderzoeken waarmee een gebruiker direct, natuurlijk en eenvoudig met [hun] probleem kan omgaan."
Gebruikers communiceerden met GRAIL via een tablet en een pen-achtig instrument. Het systeem had geen muis, geen toetsenbord, geen knoppen en geen joystick — zaken die we tegenwoordig associëren met moderne computing. Wanneer een gebruiker een kader op het scherm wilde, tekende hij dit. Wanneer er tekst nodig was, schreef de gebruiker deze met de hand. Zelfs vandaag de dag voelt een demo van dit systeem elegant en magisch aan; in veel opzichten is GRAIL een verbetering ten opzichte van bijna al zijn opvolgers.
"Dit herkenningsschema behaalt zijn hoofddoel om elke gebruiker in staat te stellen natuurlijk met een computer te communiceren. Een gebruiker wordt niet afgeleid door operationele mechanica, maar kan zich concentreren op [hun] probleem."
— Gabriel Groner (1966)
In dit essay kijken we terug naar de bijdrage van Gabriel Groner aan het GRAIL-project. Groner ontwikkelde een vernuftig programma dat handgeschreven letters, cijfers, leestekens en geometrische figuren herkende. Het programma was efficiënt genoeg om in real-time te draaien op een IBM System/360 computer en robuust genoeg om 90 procent van de symbolen van beginnende gebruikers correct te identificeren. Groner legde zijn methode vast in een memorandum uit 1966 over de Real-Time Recognition of Handprinted Text.
---
De RAND Tablet
Menselijke interactie met GRAIL verliep via een RAND tablet. Alle input werd met een pen op het oppervlak van de tablet getekend. De tablet, met afmetingen van $10,24" \times 10,24"$, had een resolutie van 100 lijnen per inch, waardoor meer dan een miljoen discrete penposities nauwkeurig gedigitaliseerd konden worden.
In de punt van de pen zat een druksensor. Wanneer de gebruiker de pen tegen het schrijfoppervlak drukte, werd dit geregistreerd als een "pen-down"-actie; wanneer de pen werd opgetild, volgde een "pen-up"-actie. De positie van de stylus werd elke vier milliseconden doorgegeven aan GRAIL als een paar $(x, y)$ coördinaten.
---
Smoothing (Afvlakking)
Omdat de tablet penposities rapporteert op een discreet raster, kunnen zelfs vloeiende curves kleine hobbels en hoeken vertonen ("jaggies"). Dit fenomeen staat bekend als quantization noise (kwantiseringsruis). Om deze ruis te verwijderen, paste Groner een smoothing-methode toe.
De werking van smoothing: Het systeem middelt een nieuw binnengekomen datapunt met het laatst afgevlakte datapunt. Geometrisch gezien gebeurt dit door een rechte lijn te trekken tussen het gekwantiseerde punt en het vorige gesmoothede punt, om vervolgens het nieuwe punt een bepaald percentage richting het vorige punt te verschuiven.
- Effect: Hoe hoger het smoothing-percentage, hoe vloeiender de curve.
- Beperking: Smoothing is een destructief proces; kleine versieringen in het handschrift kunnen hierdoor verloren gaan.
Wiskundig gezien is deze methode een toepassing van een infinite impulse response filter.
---
Thinning (Uitdunning)
Bij het langzaam bewegen van de pen worden veel datapunten gegenereerd die overbodig zijn voor het herkennen van de vorm. Groner gebruikte een eenvoudig thinning-schema om dit aantal te beperken:
- Er wordt een vierkant getekend rond het eerste datapunt.
- Alle volgende punten die binnen dit vierkant vallen, worden weggegooid.
- Het vierkant wordt verplaatst naar het eerste punt dat buiten het huidige vierkant valt.
- Dit proces herhaalt zich voor de rest van de streek.
De grootte van het vierkant bepaalt hoe agressief de uitdunning is. Groner ontdekte dat hij tot wel zeventig procent van de ruwe datapunten kon verwijderen zonder de essentiële vorm van de streek te verliezen.
---
Kromming (Curvature)
Na het afvlakken en uitdunnen krijgt elk datapunt een richting toegewezen. Groner stelde vast dat het voldoende was om alleen de windrichtingen (boven, onder, links, rechts) te gebruiken.
Bepaling van de richting: Er wordt gekeken naar de rechthoek die gevormd wordt door een punt en zijn voorganger:
- Is de rechthoek breder dan hij hoog is? Dan is de beweging links of rechts.
- Is de rechthoek hoger dan hij breed is? Dan is de beweging boven of onder.
Alleen de wijzigingen in richting worden opgeslagen. Hierdoor ontstaat een zeer compacte representatie van de kromming. Een letter 'L' wordt bijvoorbeeld beschreven door twee directionele segmenten: $\text{beneden} \rightarrow \text{rechts}$.
---
Hoeken (Corners)
Sommige symbolen kunnen niet alleen op basis van richting worden onderscheiden. Zo kunnen een "5" en een "S" beide resulteren in dezelfde reeks richtingen ($\text{links} \rightarrow \text{beneden} \rightarrow \text{rechts} \rightarrow \text{beneden} \rightarrow \text{links}$). Om dit op te lossen, detecteert het systeem de aanwezigheid van hoeken.
Hoekdetectie: Voor deze analyse gebruikt Groner "16-richtingen" (een cirkel verdeeld in 16 gelijke sectoren). Een hoek wordt gedetecteerd wanneer:
- De pen twee segmenten in dezelfde 16-richting beweegt.
- Er een richtingsverandering van minstens $90^\circ$ plaatsvindt.
- De pen vervolgens weer twee segmenten in de nieuwe richting beweegt.
Dit stelt het systeem in staat om bijvoorbeeld een "5" (die vaak hoeken heeft) te onderscheiden van een "S" (die meestal vloeiend is).
---
Kenmerken van Grootte en Positie
Elke getekende streek wordt verwerkt in een beschrijving die de belangrijkste kenmerken vastlegt ten opzichte van een denkbeeldige bounding box (omsluitende rechthoek).
Geregistreerde data:
- Afmetingen: Hoogte, breedte en de aspect ratio (verhouding hoogte/breedte). Dit helpt bijvoorbeeld bij het onderscheid tussen een '7' en een '1'.
- Posities: Het startpunt (pen-down) en eindpunt (pen-up), evenals de locaties van hoeken. De omhullende rechthoek wordt verdeeld in een $4 \times 4$ raster, waardoor deze punten relatief aan het symbool worden gecodeerd.
---
Karakterherkenning
De identificatie van een symbool gebeurt via een beslissingsboom bestaande uit een reeks tests (geïmplementeerd als cascades van if-statements).
Het proces:
- Initiële filtering: De herkenner begint met de eerste vier windrichtingen van de streek. Symbolen die niet met deze richtingen beginnen, worden direct geëlimineerd.
- Verfijning: Als er meerdere kandidaten overblijven (bijv. 'O', '2' of '3'), wordt gekeken naar andere kenmerken uit de beschrijving:
- Een '2' wordt herkend als de streek eindigt in de rechterbenedenhoek.
- Een '3' wordt herkend als de streek eindigt in de linkerbenedenhoek.
- Een 'O' wordt herkend als het start- en eindpunt dicht bij elkaar liggen aan de bovenzijde.
Hoewel de originele GRAIL-herkenner ook tekens met meerdere streken kon verwerken, is deze vereenvoudigde versie gericht op single-stroke karakters (tekens die in één beweging worden geschreven).
Vergelijking en context
Het herkennen van Latijnse karakters is uitdagend omdat er geen strikte volgorde van streken is. In tegenstelling hiermee heeft het Chinees schrift wel een canonieke volgorde, waardoor handschriftherkenning daar vroeger al succesvoller was. Groner schreef in 1967 zelfs al over de toepassing van zijn schema voor Chinese taalinput.
---
Slotwoord
Waarom zijn mid-century algoritmen nog relevant? Voor de auteur ligt de waarde niet zozeer in de tekstherkenning zelf, maar in het idee dat mensen via het tekenen — een medium met een hoge bandbreedte — kunnen communiceren met computers. Tekenen is een krachtige vorm van communicatie die als primaire of aanvullende methode voor mens-computerinteractie kan dienen.
Het werk van Gabriel Groner en het GRAIL-team biedt een fascinerend inzicht in de vroege geschiedenis van interface-design, een tijd waarin onderzoekers al experimenteerden met interactieve graphics voor complexe wetenschappelijke systemen.
Groetjes,