A Generic Approach to the Recognition and Analysis of Sketched Diagrams Using Context Information [Elektronische Ressource] / Florian Brieler. Mark Minas. Gennaro Costagliola. Universität der Bundeswehr München, Fakultät für Informatik

Description

A Generic Approach to the Recognition and Analysisof Sketched Diagrams Using Context InformationDissertationzur Erlangung des akademischen Grades einesDoktors der Naturwissenschaften (Dr. rer. nat.)vorgelegt vonDipl.-Inf. Florian Brieleram 25. Juni 2009Vorsitzender der Kommission: Prof. Dr. Peter HertlingBetreuer und 1. Berichterstatter: Prof. Dr.-Ing. Mark Minas2. Prof. Gennaro Costagliola1. Prufer:¨ Prof. Dr. Gunnar Teege¨2. Prufer: Prof. Klaus Buchenrieder, Ph.D.Tag der mundlichen¨ Prufung:¨ 08. Februar 2010Universitat¨ der Bundeswehr Munchen¨Fakultat¨ fur¨ InformatikAbstractRecent decades have shown the rise of diagrammatic representation of informa-tion. In computer sciences, for example, general purpose diagrammatic notationslike the UML are an everyday tool nowadays, and can even be considered as com-mon knowledge. Also the advent of domain-specific languages (DSLs) can beobserved. On the other hand, the research field of sketching is becoming pop-ular, due to advances in processing speed and input hardware. Also, fields ofapplication are evident, e.g. drawing of diagrams. The term sketching means tohave a user draw something and have the computer interpret the drawing in someappropriate way. The advantage of sketching over traditional WIMP-based userinterfaces (window, icon, menu, pointing device) is a more natural and intuitiveway of interaction with the computer.This thesis presents DSKETCH, an approach to sketching of diagrams.

Subjects

• Documents
• Knowledge
• Informatik

Informations

• Published by: universitat_der_bundeswehr_munchen
• Published: 01 January 2010
• Reads: 28
• Language: English
• Document size: 6 MB

Exrait

AofSkGenericetchedApproachDiagramstotheUsingRecognitionContextInfandormationAnalysis

DissertationzurErlangungdesakademischenGradeseines
DoktorsderNaturwissenschaften(Dr.rer.nat.)

vorgelegtvon
BrielerFlorianDipl.-Inf.25.am2009Juni

VorsitzenderderKommission:Prof.Dr.PeterHertling
Betreuerund1.Berichterstatter:Prof.Dr.-Ing.MarkMinas
CostagliolaGennaroProf.Berichterstatter:2.1.Pr¨ufer:Prof.Dr.GunnarTeege
2.Pr¨ufer:Prof.KlausBuchenrieder,Ph.D.

Tagderm¨undlichenPr¨ufung:08.Februar2010

Universit¨atderBundeswehrM¨unchen
Fakult¨atf¨urInformatik

Abstract

Recentdecadeshaveshowntheriseofdiagrammaticrepresentationofinforma-
liktion.etheInUMLcomputerareanevsciences,erydayfortoolenoxample,wadays,generalandcanpurposeevenbediagrammaticconsideredasnotationscom-
monobservknoed.Onwledge.theAlsootherthehand,advethentofresearchdomain-specificfieldofsketchinglanguagesis(DSLbecomings)canpop-be
ular,applicationduetoareadveancesvident,ine.g.draprocessingwingofspeeddiagrams.andinputThehardwtermarske.etchingAlso,fieldsmeansofto
haveappropriateauserwdraayw.ThesomethingadvantageandhaofvesktheetchingcomputeroverinterprettraditionaltheWIMPdrawing-basedinsomeuser
winterfayofacesinteraction(window,withicon,themenu,computer.pointingdevice)isamorenaturalandintuitive
ideaisThisthatthesistheuserpresentsfirstDdraSwsKEaTCH,diagram,anandapproachthentoDSskKETetchingCHofderivesdiagrams.thesyntac-The
ticcanandbeusedsemanticforsubsequentinformationconprocessing.veyedinThethedraapproachwing.isThefullysemanticgeneric,i.e.,itinformationisnot
tailoredtoaspecificdiagramlanguage.Thereisaprototypicallyimplemented
systemdiagramwhichfromtheservesUMLas.Theproof-of-concept.systemthenAsderianvesethexample,semanticstheuserofdrathewsadiagram,class
andcreatesskeletonclassfiles.Theusercansubsequentlycreateanactualimple-
eletons.skthesewithmentationReachingthisgoaldependsontwosubsequentstages,appliedaftertheuser
isfinisheddrawing.Thefirstisrecognition,whichmeanstoidentifythesingle
shapesthatmakethecompletediagram.Theotherstepisanalysis,whichmeans
toinspecteachshapeinthecontextofothershapes,thusbeingabletoderivea
muchsyntacticalcurrentstructureresearchfirst,intheandfieldtheofsemasknticsetching.afterwStill,ard.nosatisfyingRecognitionissolutionsubjectcouldto
befoundyet.State-of-the-artapproachesmostlyconstraintheuserandimpose
apointrestrictionswhereregitardingbecomeshowtobearable,draw.butThus,thetheusertaskisofforcedrecognitiontoisconcentratesimplifiedonhisto
ondraskwingetching.style.HowevAnalysis,er,onanalysistheothershouldbehand,anisimportantrarelyaspectdiscussedofinapproachespublicationsto

iii

vi

sketching,astheuserisusuallynotinterestedinrecognizedshapes,butinthe
diagram.theofsemanticsTheapproachpresentedinthisthesismarksimprovements,bothforrecog-
nitionandforanalysis.Thecoreideaoftherecognitionistoavoidafeature-
basedapproachforhigh-levelrecognition,asfeaturesimposesevererestrictions
onwhichdrawingscanberecognized.Instead,asetofindependentmodelsiscre-
ated,allofwhichcontaininformationgainedfromlow-levelprocessing.Further-
more,multiplerepresentationsofthesamestrokeindifferentmodelsarepossible.
Thishasapositiveeffectonrecognition,becauseitremovesthetaskoflow-level
processingtodecideforasuitablerepresentationwithoutanycontextknowledge.
High-levelrecognitionitselfisthenbasedoncompositionofprimitivestocom-
pleteshapes.Ingeneral,thepresentedapproachtorecognitiondoesnotconstrain
theuserinthewaysshownbypreviousworkinthefield.
AnalysisbuildsupontheDIAGENframework,whichallowsforgenerationof
WIMP-baseddiagrameditorsfromspecifications.Thegeneratededitorsallowfor
checkingsyntaxandsemanticsofthediagramscreatedbytheuser.Theconceptof
DIAGENisbasedontheformalapproachofgraphtransformation,whichresults
inapowerfulandreliablediagramanalysis.
Inthisthesisitisshownhowthisapproachcanbetransferredtosketching.
Themostdistinctresultisthatambiguitiescanbereliablysolvedbyextensiveuse
ofcontextinformationgainedfromsyntaxchecking.Ambiguitiesnaturallyarise
fromhand-drawing,whichisinevitablysloppyandimprecise.Furthermore,it
hasprovenvaluabletoexplicitlymodelambiguitiesintheanalysisprocess.Also,
diagramlanguage-specificoutputcanbegeneratedasaresultfromtheanalysisas
motivatedabovewiththeexampleofclassdiagrams.
Theprototypicalimplementationisappliedtosixdifferentdiagramlanguages,
allofwhichexhibitdifferentcharacteristicsregardingvisualappearance,syntax,
andsemantics.AmongthesixlanguagestherearestatechartsfromtheUML,and
aGUIbuilderasarepresentativeofDSLs.Manyfurtherdiagramlanguagesare
conceivableaswell.Anempiricaluserstudyevaluatesrecognitionratesandper-
formanceoftheprototype.Itprovesthatthesystemisbothaccurateandpowerful.
Thecontributionofthisthesisliesbothintherecognizerandtheanalysis.
Therecognizerallowsformultiplerepresentationsofthesamestrokeatthesame
time,andiscapableofidentifyingshapesfromacompletedrawingwithoutprior
assignmentofstrokestoshapes.Theanalysisisbasedonaformalapproach.Am-
biguitiesaresolvedautomaticallybasedonthesyntacticstructureofthediagram
language.Therefore,ambiguitiesareexplicitlymodeledfortheanalysis.

Contents

Abstract

Contents

esFigurofList

ListAlgorithmsof

onymsAcrofList

iii

v

ix

xiii

xv

1oductionIntr11.1KeyAspectsofSketching......................4
1.2ConceptoftheProposedApproach.................9
1.3MainScientificContributions....................18
1.4Outline...............................19

21LanguagesDiagram22.1PetriNets..............................22
2.2Nassi-ShneidermanDiagrams...................23
2.3GUIBuilder.............................25
2.4Statecharts..............................26
2.5BooleanLogicDiagrams......................27
2.6Tic-tac-toe..............................28
2.7ApplicationRangeoftheProposedApproach...........28

31orkWRelated33.1GRANDMA.............................32
3.2LADDER..............................32
3.3SketchGrammars..........................35
3.4InkKit................................37
3.5OtherApproaches..........................39
3.6Comparison.............................42

v

vi

CONTENTS

47ocessingeprPr44.1Concept...............................48
4.2Lines................................50
4.3Arcs.................................52
4.4Links................................55
4.5Circles................................57
4.6Text.................................60
4.7FutureWork.............................61
4.8Summary..............................62

63Recognition55.1ConstraintsandtheSpecificationofShapes............64
5.2SearchPlan.............................66
5.3QueryingtheModels........................71
5.4RecognitionofShapes.......................73
5.5AssigningRatingstoShapes....................78
5.6FutureWork.............................80
5.7Summary..............................81

83ocessingostprP66.1EliminationofDuplicates......................83
6.2IdentificationofConicts......................86
6.3SuppressionofShapesContainingOtherShapes..........86
6.4Summary..............................88

89Modeler77.1AttachmentAreas..........................90
7.2Relations..............................94
7.3Hypergraphs.............................95
7.4CreatingtheHypergraphModel..................96
7.5Summary..............................99

101Reducer88.1GraphTransformation........................101
8.2ReductionRules...........................103
8.3ConictsandNegativeApplicationConditions..........107
8.4FutureWork.............................112
8.5Summary..............................112

CONTENTS

vii

113arserP99.1ProductionRules..........................114
9.2TerminalandNonterminalProductionRules............118
9.3SetProductionRules........................119
9.4EmbeddingProductionRules....................123
9.5ALargerExample..........................125
9.6AttributeEvaluation.........................127
9.7Summary..............................128

129aluationEv1010.1ProcessingTime...........................131
10.2RecognitionRates..........................135
10.3EffectoftheEliminationofDuplicates...............136
10.4EffectoftheSuppressionofShapesContainingOtherShapes...137
10.5Conclusion.............................139

ConclusionandSummary11

141

ASpecificationofDiagramLanguages147
A.1PetriNets..............................148
A.2Nassi-ShneidermanDiagrams...................153
A.3GUIBuilder.............................159
A.4Statecharts..............................166
A.5BooleanLogicDiagrams......................174
A.6Tic-tac-toe..............................180

ConceptCompleteTheB

185

187ExampleDetailedCC.1RecognitionStage..........................188
C.2AnalysisStage...........................191

yBibliograph

195

viii

CONTENTS

esFigurofList

1.1ExampleofasketchedPetrinet...................5
1.2Exampleoftwostrokeswhichhavetobesegmentedandclustered.6
1.3Conceptualoverviewofthefullapproach..............13
1.4Conceptualoverviewoftherecognitionstageandanalysisstage..14
1.5Examplesofshapes,andhowtheyarecomposedofprimitives...16
1.6Inuenceofthespecificationonthesketchingeditor........18
2.1Overviewofclassesofdiagramlanguages..............22
2.2ExampleofaPetrinet........................23
2.3ExampleofaNassi-Shneidermandiagram..............24
2.4Exampleofahand-drawndialogbox................25
2.5Exampleofastatechart........................26
2.6ExampleofaBooleanlogicdiagram.................27
2.7ExampleofaTic-tac-toegame....................28
3.1ArchitectureoftheLADDERsystem[48]..............34
3.2ArchitectureoftheSkGsystem[24].................37
3.3ArchitectureoftheInkKitrecognizer[79]..............38
3.4TwoexamplesketchesforthelimitationsofLADDER.......45
4.1Conceptualoverviewofthepreprocessingstep...........49
4.2Asketchandthefourstrokemodels.................50
4.3Possibleanglesbetweenthreeconsecutivesamplesthataretoo
closetoeachother..........................52
4.4Processingofastrokebythearctransformer............54
4.5Fittinganarcinasub-stroke.....................54
4.6Anarrowdrawninonestroke....................56
4.7Differentcasesoftwostrokesbeingclosetoeachother.......56
4.8Examplesofastrokeandaccumulatedangleγ...........58
4.9Strokesandsuperimposedcircles..................58
4.10Preprocessingstageifadividerwouldbeused...........61

ix

x

FIGURESOFLIST

5.1Examplesofshapeswhicharenotconnected............64
5.2Anintendedarrowandexamplesofarrowswhichfailtosatisfy
theconstraints............................65
5.3Examplesofshapes..........................66
5.4Exampleofanunconnectedshapeanditsconstraints........67
5.5Arectangleandmanyverticallineshamperingtherecognition...67
5.6AnexampleforsharedprimitivesamongtheshapesofNSD....68
5.7AnoptimalsearchplanforNSD...................69
5.8Twodifferentsearchplansforthesameshape............70
5.9Alinemodelandanarcmodel....................72
5.10Conceptualoverviewoftheassembler................74
5.11Extractfromthesearchprocessforastatementinadrawing....77
5.12Twodrawingsandtheircorrespondinglinemodels.........78

6.1Adrawingofarectanglemadewithonestroke,thecorresponding
linemodel,andtworectangleswhicharenoduplicates.......84
6.2NSDsandexamplesoffalsepositives................87

7.1ArchitectureofaneditorgeneratedbyDIAGEN...........90
7.2Examplesofshapesandtheirattachmentareas...........91
7.3Examplesofdeformationsduetohand-drawing...........92
7.4Thegridasanexamplewhereadditionalpointshavetobecomputed.93
7.5Differentcasesoftworelatedcircles.................94
7.6Ahypergraphconsistingofsevenedgesandfournodes.......96
7.7Ahand-drawnPetrinetandinternalmodels.............98

8.1Agraphtransformationruleanditsapplicationtoagraph.....102
8.2TwoapplicationsofreductionrulesandtheresultingRHM.....104
8.3ReductionrulesforPetrinets....................105
8.4TheRHMfortheHMshowninFigure7.7(b)............106
8.5TwoalternativereductionrulesforPetrinets............107
8.6AsketchedPetrinetandHMandRHMcreatedfromthesketch..108
8.7AsketchedPetrinetanditsHMifplacesandtransitionsmay
overlap................................111

9.1ProductionrulesforPetrinets....................115
9.2SetproductionrulesforPetrinets..................116
9.3EmbeddingproductionrulesforPetrinets..............117
9.4Exemplaryderivationtree......................120
9.5Exemplaryderivationtreeaftersomeconictsaresolved......121
9.6GraphGwherethelargestcliqueissearchedfor..........122
9.7AsketchandthegeneratedRHMandderivationDAG.......124

FIGURESOFLIST

9.8

10.110.210.310.410.510.610.7

C.1C.2C.3C.4C.5C.6C.7

xi

RHM,derivationDAG,ratingsandweightedratingsforFigure7.7.126

ATheGUIsixbuilderdiagramssketchusedasfromthemastersuserforstudytheinuserthreestudy..copies.............131130
Totalprocessingtimefordifferentdiagramlanguages........133
Fractionofrecognitionandanalysisstagesoftotalprocessingtime.134
Averagerecognitionrates......................136
Totalprocessingtimewithandwithoutremovalofduplicates...137
ofAverageshapestotalcontainingprocessingothertimeshapes.for.NSD..with...and...without....remo..v.al.138

AContentssimpleofPetrithenetmodelsusedasgeneratedrunningforethexamplesketchinshoAppendixwninC.Figure...C.1..187188
17ofthe26shapesrecognizedfromthemodelsinFigureC.2...189
TheThe13HMforshapestheleftsketchaftershoremownvinalofFigureduplicates.C.1........................191190
TheRHMfortheHMshowninFigureC.5.............192
TheDAGcreatedbytheparserfortheRHMshowninFigureC.6.193

xii

LIST

OF

FIGURES

List

12345

Algorithmsof

Transformationofastrokeintostraightlines............
Filteringofsamplesfromastrokewhicharetooclosetoeachother.
Transformationofastrokeintoacircle...............
Computationofasearchplanfromasetofshapes.........
Recognitionofallshapesfromscratch................

xiii

5153597175

vxi

LIST

OF

ALGORITHMS

ruleproductionsetsideright-handmodelgraphyperhreduced)g/.omg.orhttp://www(GroupManagementObjectdiagramNassi-Shneidermanruleproductionnonterminalconditionapplicationevatigne)g/mda.omg.orhttp://www(ArchitectureenvDriModelsideleft-handModelvoMarkHiddenmodelgraphyperhinteractionHuman-computeraceinterfuserGraphicalruleproductionembeddinglanguagedomain-specificgraphyclicacdirected(parser)-Kasamioungere-YCockxv

onymsAcrof

formList

normalBLD

yCNF

ChomskCYK

GAD

diagramDSL

logicEPR

BooleanGUI

HCI

HM

HMM

LHS

AMD

CNA

NPR

NSD

OMG

RHM

RHS

SPR

vicedepointingmenu,icon,,wwindo)g/uml.omg.orhttp://www(LanguageModelingUnifiedruleproductionterminalxvi

TPR

UML

WIMP

ALGORITHMSOFLIST

1Chapter

oductionIntr

EvDiagramserybodyareuseswidespreaddiagrams:inarchitects,computerengineers,sciences,salesaswellpeople,asinandotherdesigners.disciplines.This
isnosurprise,sinceadiagramnaturallyallowsforrepresentinginformationina
tionvisualwhichmanneris.clearlyThismakarrangedesiteasygraphicallytograspisitsmostlymeaning.moreconvPerceptionenientofandquickinforma-er
thanthatofatextualrepresentation.Especiallyforverycomplexissues,using
diagramscannotbeabstainedfrom.Complexsoftwarecouldnotbebuildwithout
thenot,usecarsofcoulddiagrams,not,devicesconstructionsbasedlikonebuildingsmicro-electronicsorbridgeslikecouldmobilenot.phonescould
Manypopularandwell-knowntypesofdiagramsareusedincomputersci-
encestoday,althoughtheiruseinotherfieldsoutnumbertheusageincomputer
sciencesbyfar.Commontoalldiagramsisthattheyhaveacertainmeaning.
Incomputersciencesthismeaningisusuallydescribed(more)formally,asthis
candisciplinebedescribedhasthebymeansstringnecessarygrammars,athand.diagramsareSimilarrelatedtotetoxtualdiagramlanguageslanguages,which
whichcanbedescribedformallyaswell.Forexample,inversion2oftheUML
theOMGdefinedthemeaningofrespectivediagramsmoreformallyandclearly
asbefore,whichfostersusingandunderstandingofUMLdiagrams.
Havingaclearunderstandingofdiagramsisessentialtotheprocessingofthe
containedinformation.BasedontheUML,theOMGthuscouldestablishMDA
asanewparadigmtotheproductionofsoftware,whichis–initsbasicidea–
completelybasedonmodels.Thesemodelsareusuallyrepresentedgraphically
asdiagrams.Thiswholeconceptwouldfailifdiagramscouldnotbeformally
described.Ofcourse,noteveryvisualrepresentationofinformationisadiagram.Inthis
thesis,weunderstandadiagramalwaysinthecontextofitsdiagramlanguage.
isThesyntaxlanguage,andassemanticssaidofbefore,thedescribesdiagrams,anosetofmatterdiagrams.whetherPitartisofgivthisenformallydescriptionor

1

2

ODUCTIONINTR1.CHAPTER

not.Ifthereisnolanguage,wedonotspeakofdiagrams.
Creatingadiagramcanservetwopurposes.First,analreadyestablishedcir-
cumstanceshouldbeillustrated.Thisisoftenthecase,forexample,whenan
authorwritesabookandusesdiagramstoconveyinformationorfosterunder-
standing,orwhenasoftwareengineerdocumentsthearchitectureorstructureof
softwarewhichisalreadybuilt.
Theotherapplicationofdiagramming–tocreateandusediagrams–isto
supportthecreativeprocesswhichisinevitablewhensomethingnewistobecre-
ated[63].Forexample,designersofsoftwareusuallystartbuildingthesoftware
byworkingwithdraftsfirst,andrefiningthemuntiltheymeetcertaincriteriaof
qualityorcontent.Onlythenthesoftwareisactuallyimplemented.
Forbothpurposesthereexistcountlesstools,bothcommerciallyavailableand
inacademia.ExamplesoftheformerareBorlandTogether,orIBMRational
Rose.ExamplesfromacademiaareDIAGEN[69],DiaMeta[71],VLDesk[26],
AToM3[34],Fujaba[37],Tiger[36],Pounamu[105]andMarama[45].Allof
thesetoolsallowforcreatingdiagramsandprocessingtheminsomeway.The
processingisespeciallyusefulwhentheinformationdescribedbythediagramsis
tobeusedinsubsequentstepsofacomplexprocess.Forexample,muchsource
codecanbegeneratedfromUMLdiagrams,whichis,bytheway,thebasiccon-
.AMDofceptAlthoughcommercialtoolsareusuallymuchmoremature,theyusuallyhavea
similaruserinterfaceliketheresearchprototypes.Usingthemouseandanempty
canvas,diagramcomponentscanbeplacedonthecanvasbyamatterofclicking
buttons.Theuserisgreatlysupportedinthisprocessbyfeatureslikecut-copy-
paste,undoandredo,savingandloading,automaticlayoutofdiagrams,andmuch
more.However,suchinterfacesstillremainartificialinsomeway,andaremore
dictatedbytechnicalaspectsratherthanbytheusersneeds.
Itiswellknownthatmanydesignersprefertousepenandpaperinearlystages
ofdesign,andnotacomputer.Thishasseveralreasons.Firstofall,itiseasier.
Thepaperdoesnotneedanexplicituserinterface,anditprovidestheuserwith
muchexibility.Thisagainfosterscreativity,asnotimeandefforthastobespent
inusingpenandpaper.Evenmore,whenacomputerisused,peopletendtoget
distractedfromtheiractualtask,concentratingonminoraspectslikeanicelayout.
Sketchesmadeonpaperlookinformalandunfinished,whichclearlyindicatesthat
theyaresubjecttochange.Aneatcomputer-generatedlayouthastheopposite
effect.Peoplearemorereluctanttochangesuchdiagrams[14,63,30,79].
Designersusuallybeginwithsomeinformalsketchestotalkaboutthedesign
ofanewcar,forinstance,andsodosoftwareengineers.Aloneorinagroup,
thebasicarchitectureisoftendevelopedintermsofinformalsketches,which
issimplymoreconvenient.Ofcourse,whenusingsketchesinthefirstplacethis
meansthatatsomepointtheyhavetobetransferredtoacomputer,oftenmanually,

3

togainfurthervalue[40].Unfortunately,thisprocessisbothcumbersomeand
error-prone.Furthermoreitisusuallyirreversible[42]asupdatestothetransferred
diagramscanhardlybereectedinthesketches.
Theresearchtopicofsketchingnowdealswithexactlythissituation.Users
areallowedtodraw(orsketch)onacomputer,andthemachineinterpretsthis
inputinsomeway.Thisinterpretationiscrucialandstatesthedifferencetobare
drawingtools.Thebasicideaistogetthebestfrombothworlds:averysimple
andnaturaluserinterfaceasknownfrompenandpaper[91,38,53,4,48,30],but
alsocapabilitiestounderstandthesketches,pluscomfortableeditingcommands
asmentionedabove(load,save,selection,versioning,etc.).
Becauseamouseisnosuitablereplacementforapen(norisatouchpadlike
mostnotebooksareequippedwith),specialhardwareisrequiredforsketching.
Examplesaresmartboardswhichcanbeusedwiththefingeroranyothersuitable
object,computersandnotebookswithtouch-sensitivedisplayswheremostlya
specialstylusisrequired,andpentabletswhichhavenoowndisplay.According
tothisbroadrangeofhardware,pricesalsospanawiderange,startingfromless
than100CforsimpletabletsliketheWacomBamboo1,uptomorethan10.000C
forsmartboardsliketheSMARTTechnologies2000i2.
Suchhardwareisincreasinglypopular,andismoreandmorewidespread
[76,81].Theunderlyingtechnologyenablesacompletelydifferentparadigm
ofinteractionwithcomputers,comparedtoclassicaluserinterfacesrelyingona
mouse,alsoknownasWIMP(window,icon,menu,pointingdevice).Accord-
ingly,usingsuchhardwarealsorequiresdedicatedapplicationswhichfullysup-
portandutilizetheirspecialcapabilities[93,80].Atouch-sensitivedisplay,for
example,isnothingmorethananicegadgetifthereisnosoftwarewhichbenefits
fromthestylus.Understandingofhand-writingissuchanapplication,wherethe
userreallybenefitsfromthestylus.Sketchingisanother.Itisreportedthatusers
prefertouseawhiteboardoratabletPCratherthanatraditionaltool[99].
Inthelasttwodecades,muchprogresshasbeenachievedinthefieldofsketch-
ing.Completesystemshavebeendeveloped,anddedicatedsolutionstospecial
issueshavebeenproposed.However,therecognitionofsketchesisstillnotsolved
satisfactorily,andisconstantlyregardedasadifficulttask,ifnotthehardestchal-
lengeinthefieldofsketching[11,43,91,4,98,16,79].Recognitionmeansto
identifysingleshapes,orentities,fromthesketch.Also,reasoningaboutsketches,
i.e.,furtherprocessingoftheinformationconveyedinasketch,isinitsinfancy,
andisnotconsideredinmanypublications.InthenextsectionandinChapter3
areasonableselectionofthispreviousworkisaddressedanddiscussedinmore
detail.12seehttp://www.wacom.com/
http://smarttech.com/see

4

ODUCTIONINTR1.CHAPTER

Inthisthesiswepresentanovelapproachtotheunderstandingofsketcheddi-
agrams,calledDSKETCH(diagramsketching).Newsolutionstoboththerecog-
nitionandthereasoningaregiven,whichdependoneachother,butcouldalsobe
usedincombinationwithotherapproaches.Fortherecognition,werelyonanew
conceptthatavoidsbydesigncommonproblemsofotherapproaches.Fortherea-
soning,werelyonanexistingframeworkfordiagramanalysis,whichweadopted
tothespecialcharacteristicsofsketching.ThebasicconceptofDSKETCHisex-
plainedinSection1.2.Before,Section1.1definesbasictermsandaspectsof
sketching,anddescribessomeofthecurrentissues.DSKETCHisbrieysumma-
rizedinSection1.3,anditsmajorscientificcontributionsarehighlighted.The
finalSection1.4outlinesthisthesisbysummarizingeachupcomingchapter.

1.1KeyAspectsofSketching
Inforthisthefieldsectionoftheskgeneraletching.termsTheanddesigndefinitionsspaceforareandiscussedapproachtowhichskhavetchingeevisolvex-ed
plained.Asbrieymentionedbefore,sketchingmeanstheunderstandingofa
wing.drahandstylusTheputcentralonthetermsurfinaceskofetchingtheisscreen,thatandofaendsstrokewith.Athestrokliftingebeofginsthewithstylus.the
Justlikeamouse,thecomputertracksthemovementofthestylusbycapturing
(thex,ye,vt)ents(calledgeneratedsamplesfrom)itswheredrivxer.andTyareechnicallya,pairaofstrokeiscoordinatesafinitelistreectingoftuplesthe
screenpositionwherethestyluswas,andtisthetimeelapsedsincethebeginning
ofthestroke,usuallymeasuredinmilliseconds.Someapproachesevenconsider
theaccuracypressure,butexnotercisedeverywithhardwthearestylusisoncapabletheofscreen[72measuring]tothisimprovvealue.recognitionMostly,
pressureisonlyusedtoadjusthowstrokesaredisplayed-thethickerthemore
Thesepressurevaluestherecanwasalewxaysercisedbe[74captured,].Theandleastarecommonassumedbydenominatorvirtuallyaarenyx,yapproach.andt.
Themainissueinasketchingsystemisrecognition,whichmeanstoidentify
fromthestrokesdrawnbytheuserthesingleshapesasketchiscomposedof.For
thatpurposeitmustbespecifiedinadvancewhatshapesaretoberecognized.A
shapeisabasicbuildingblockofasketchthatdependsonthedomainandcannot
bebrokenintosub-parts.Inourcase,asweassumediagramlanguages,theset
offourrelevkindsantofshapesshapesisalwhichwayshavknoetown.beForPetrirecognizednets,fromforethexample,drawing:thereplaces,areonlyto-
kens,transitionsandarrows.Textcanbeusedinordertoaugmentthesketch,
intheSometimes,caseofPetrirecognitionnetsisbybrokdefienningdownweightsintotwofoarrolevwsels,andlow-levelcapacitiesrecoofgnitiontokens.or

1.1.

KEY

ASPECTS

OF

SKETCHING

5

6

CHAPTER

1.

ODUCTIONINTR

ASPECTSKEY1.1.SKETCHINGOF

7

uesgainedfromtrainingtothosecomputedfromthestrokesinthedrawing,and
decideswhichgesture(orshape)isbestrepresentedbyastroke.
Forexample,inordertodistinguishsmallcirclesfromlargecircles,thestroke
lengthcanbeconsideredastheonlyfeature.Fortraining,circlesfrombothgroups
aredrawn,andtherespectivestrokelengthsareaveraged.Then,foreachstroke
inthedrawing,itslengthiscomputed,anditisclassifiedtobeamemberof
thatgroup(smallorlarge)wheretheaveragestrokelengthisclosertotheone
computedforthestrokeinthedrawing.Whilethisapproachisverysimple,itis
notsufficientinpractice;morefeaturesshouldbeused,asthestrokelengthalone
isnotsufficienttodecidewhetherastrokeformsacircleatall,forexample.
Theadvantageoffeature-basedapproachesisthattheycanbeeasilyimple-
mentedandworkquitefast.Therecognitionrate,i.e.,thenumberofstrokes
thatarerecognizedcorrectlycomparedtothenumberofstrokesthataredrawn,
dependsverymuchonthefeaturesandontheclassifier.Variousfurtherpublica-
tionsbyotherauthorspickupthisapproach[79]andimproveitinsomeways,
e.g.,bycomputingotherfeatures[38,76,77].Itisalsotriedtogetridofthe
severelimitationthatashapehastobedrawninonestroke,whichmeansthatat
leastclusteringispossible.However,manyapproachesarenotverysophisticated
indoingso,butratherrelyonverysimplerulestodetectwhenthedrawingofone
shapehasfinishedandthedrawingofanotherbegins.Forexample,aconstant
timethresholdcanbeused,asin[6,43,14].Wheneverthetimepassedbetween
thedrawingoftwoconsecutivestrokesexceedsthisthresholdvalue,thestrokes
areconsideredtocontributetodifferentshapes.Althoughsimpletounderstand,
[99]suggeststhatitisdifficultsettingthethresholdvaluetoavaluethatpleases
differentusers.In[15]theuserhastoexplicitlytellthesystemthatashapeis
completelydrawnbypressingabuttonshownintheUI.
Ingeneral,forfeature-basedapproachesclusteringandsegmentationarevery
hardproblems.Evenmore,theclassicalapproachbyRubinerequirestheuserto
drawthesamestrokeeachtimetobecorrectlyrecognized.Forexample,ifthe
trainingstrokesforarectangleeachbeginintheupperleftcorneroftherectangle,
anddrawtheshapeclockwise,eachlaterstrokethatissupposedtoberecognized
asarectanglemustfollowthisruleexactly.Thisisasevererestrictionintermsof
howshapesareallowedtobedrawn,andisunrealistic[64].Thesamebehavior
canalsobeobservedwithGraffitiusedtorecognizehand-writinggesturesforde-
vicesbyPalm3.Workpublishedwhichsuggeststhatthislimitationcanberelaxed
isusuallybasedonmorecomplexfeatureslikehighcurvature[76],oroncontin-
uousdatalikepenspeed[40].Overcomingtheselimitationsiscrucial,as[53,74]
arguethatpeopleindeeddrawmorethanoneobjectwithonestroke,andthatone
objectisnotalwaysdrawnwithasequenceofconsecutivestrokes.

3.palm.com/http://wwwsee

8

ODUCTIONINTR1.CHAPTER

Theinsightgainedfromfeature-basedapproachesrevealstwocharacteristics
ofsketchingsystems.First,theycanbedistinguishedaccordingtothenumber
andkindofrestrictionsthatareimposedontheuser.Second,andcloselyrelated,
recognizersaresaidtobeeithersingle-strokeormulti-stroketoindicatetheirca-
es.strokclustertopabilityInevitableforhand-drawingisalackofprecision.Manyshapesaredrawn
somewhatmessy,whentheuserisnotverykeentoproduceanexactdrawing.
Thisimprecisionnaturallyleadstoambiguity,i.e.,therecognizeridentifiesdif-
ferentcompetingshapeswhichcannotexistinparallel.Feature-basedapproaches
areusuallymoreforgivingwithsloppysketches,whichisabigadvantage.How-
ever,evenhereambiguitiesmayarise.Mankoffetal.discusshowtoovercome
ambiguities,e.g.,byprovidingtheuserwithalistofpossiblealternativesandlet
himdecide,orbyhavingtheuserrepeattheinput[67].However,anautomatic
decisionwouldbebetter,sothattheuserdoesnothavetobebotheredbythe
shortcomingofthesystemtomakethedecisiononitsown.Automaticresolution
ofambiguitiesusuallyinvolvesexaminingthecontextofashape,i.e.,othershapes
closetotheambiguousshape.Giventhattherearesomebasicruleshowshapes
canbeconnectedtoeachother,some(orevenallexceptone)ambiguousalterna-
tivescanbeexcluded.Asanexample,considerPetrinetsagain.Ifthereisashape
thatcouldeitherbeaplaceoratransition,byexaminingthecontextitmayturn
outthatthisshapeisconnectedtoatransitionbyanarrow.Hencetheambiguous
shapemustbeaplace,becausenotwotransitionsmustbeconnectedbyanarrow
inaPetrinet.Asalreadymentioned,imprecisionandsloppinessisalsothereason
whyrecognitionissodifficult.Ifahundredpeopleareaskedtodrawarectangle,
itishighlyunlikelythatthereareeventwoidenticalstrokes(orsetsofstrokes,in
thecaseofmulti-strokerecognition).However,eachofthehundredrectanglesis
expectedtobecorrectlyrecognized,inspiteofthelargevarianceofinput.
Anotherdesignalternativeforsketchingsystemsiswhethertostartrecogni-
tionaftereverystroke(eagerrecognition),ortorequiretheusertoexplicitlystart
recognition(lazyrecognition).Theformerrequiresaveryfastrecognition,andis
commonformanyfeature-basedapproaches.Theadvantageisthattheusermay
begivenimmediatefeedback,whichhelpshimtocorrectinputthathasnotbeen
recognizedasintended.Also,editingofthesketchcanbecomeeasierifshapes
arealreadyknown[7].Ontheotherhand,itisreportedthatimmediatefeed-
backlikebeautificationdistractstheuserfromhisactualtaskofdrawingasketch
[3,4,39](beautificationdescribesthetaskofreplacingtheuser-drawnshapesby
neatcomputer-generatedones).Furthermore,asdescribedabove,thecontextofa
shapemayberequiredtosolveambiguities.Startingrecognitionaftereverystroke
obviouslymeansthatnocontextispresentfortheshapesdrawnfirst.Theresults
ofthisrecognitionarenotlikelytobevalid.Yetanotherissue,thatofincremental
recognition,islinkedtoeagerrecognition.Recognizingthewholesketcheach

1.2.CONCEPTOFTHEPROPOSEDAPPROACH

9

timefromscratchdegradesperformanceandhinderseagerrecognition.However,
withincrementalrecognitionavailable,eagerrecognitionbecomespossible.
Regardinguserinterfacesthereisacleardistinctionbetweenmode-lessand
canbemode-basedperformedapproaches.atanytimeOtherinatasksthanmode-lessskenetchingvironment.itself,e.g.,Foreeditingxample,adiagram,shapes
canbeerasedatanytimebyscribblingzigzaglinesoverthem.Ontheotherhand,
inmode-basedapproachesthereistheneedtoexplicitlychangethecurrentmode
first,Whenfortheeuserxamplehasfromfinishedsketchingerasing,toheeditingmust.Onlyswitchthenbackatoshapetheskcanetchingbeerased.mode
priorbiguitiestoincontinvolvueeddrainwing.whetheraWhilestrokthiseisseemssupposedmoretocontribcomplicated,utetoittheavskoidsetchanyitself,am-
orifalthoughittherepresentsysimplifyaneditingrecognition.operation.Generally,modesaretobeavoided[85],
eitherRegtheardingoptiontext,toallowhichwisforverywritingimportantdirectlyinonmanythecandiagramvas,whichlanguages,iseasythereandis
natural,ortorequiretheusertoindicatewriting,whichagainismode-based.
andDirectgraphics,writing,howhichweviser,stillinvanolvesopentheissuedif[ficult75,10task,79of].distinguishingbetweentext

1.2ConceptoftheProposedApproach

Theapproachtosketching,DSKETCH,discussedinthisthesisfollowstwomain
goals.Alldesigndecisionsandkeyfeaturesoriginatefromandcanbemotivated
bythesetwogoals.Thefirstistocreateasketchingsystemfortheunderstanding
ofhand-drawndiagrams.Theimportanceofdiagramsanddiagrammaticrepre-
sentation,especiallyinthecontextofdomain-specificlanguages(DSLs),hasal-
readybeenhighlightedabove.Thereforewethinkthatunderstandinghand-drawn
diagramsisavaluabletaskthatwarrantsresearcheffort.Thesecondmajorgoalof
DSKETCHistoallowfornaturalandunrestricteddrawing.Sketchingis,byitself,
anaturalinputmetaphor.Thiskeyattributemustnotbeviolatedorcompromised
byartificialrestrictions;otherwisethewholeideaofsketchingisundermined.As
mentionedbefore,themajorissueofsketchingisthatofrecognition.Totackle
thischallenge,allexistingapproachesmakeassumptionsaboutcertainaspectsof
thesketchingprocess.Iftheseassumptionsgotoofar,orareunrealistic,theybe-
comerestrictionsorevenlimitations.Theuserinterfacenolongerfeelsnatural,
andtheuserhastofocusonhisstyleofdrawing,ratherthanonthedrawingitself.
Thisalsopreventssketchingsystemsfrombeingusedasmainstreamtechnology
[76].Asaconsequence,theremustbemadeacarefultrade-offbetweentheas-
sumptionsandrecognitioncapabilities[4].Otherauthorsalsoadmittheneedfor
drawinginanunrestrictedmanner[91].

10

ODUCTIONINTR1.CHAPTER

BasedonthesetwomajorgoalsofDSKETCH,theremainderofthissection
firstexaminestheirimplicationsontheoveralldesignoftheapproach,andthen
outlinesoursolutionaspresentedinthisthesis.
sis.TheTherefirstaretwoconcernsrelatedtheGUIissuesofawhichskareetchingneithereditor.solvInedordernortodiscussedsupportinthethisnaturalthe-
wayrespectiofveinteractionfunctionalityintroducedwhichbyskseamlesslyetching,intethegratesGUIwithshouldthisprowayvideoftheuserinteraction.with
vForokingexample,commandstherelikeshouldloadnotandbesavane,yorgapeditingfortheusercapabilities.betweenInskgeneral,etchinganddesigningin-
asigngoodandUIevisdifaluationficultof[a12],GUIandisisnotresearchdiscussedtopicinofthisthethesis.HCIThecommunitysecond.Theissuede-is
onthehisskseparationetch.ofThentextthefromsystemgraphics.Inautomaticallytheidealdiscase,tinguishestheuserstrokcaneswriteterepresentingxtright
tenotxtsolvfromedstroksatisfesactorilyrepresentingyet,asgraphics.describedaboHovwee.verW,ethisassumetaskisthatvteeryxtdifandficult,graphicsand
arealreadyseparatedbysomeway,e.g.,byamode-basedGUI.

goalsmajorthebyImplicationsThissubsectionfirstdiscussestheimplicationsofthemajorgoalofunderstanding
hand-drawdiagrams,andthendoessofortheothergoalofnatural,unrestricted
wing.draThefirstimplicationofhavinghand-drawndiagramsistouseon-linerecog-
nition.Thegoalistoreplacetraditionalwidget-basededitorsandtheirpoint-and-
clickinputmetaphorbyasketchingapproach.Accordingly,theusersstrokescan
bedirectlycaptured,andinformationonindividualstrokesandtimingispresent.
Thesecondimplicationistodesignanapproachthatisfullygeneric.The
adventofDSLsisacentralmotivation,sotheapproachmustbecapableofunder-
standingdiagramsfromdifferentdomains.Furthermore,forthefieldofclassical
diagramlanguagesliketheUML,orotherexamplesmentionedabove,onlya
genericapproachcanbeusedinordertounderstandtheverydifferentdiagrams
entail.languagestheseThethirdimplicationalsoliesinthenatureofdiagramming.Nobodydraws
diagramsforitsownsake;thereisalwaysthedesiretoconveyinformationwitha
diagram.Thepowerofdiagrammaticrepresentationstemsfromtheinformation
containedindiagrams[42].Evenmore,whenacomputerisusedasdrawingtool,
thereisusuallytheintentiontomakethecomputerunderstandthediagram,and
usethecontainedinformationforsometask.Forexample,whendrawingaPetri
netonacomputer,theusermaywanttoexecutethenettoseeifitmatcheshis
understandingoftheproblemhemodeled.Accordingly,usingDSKETCHitmust
bepossibletocomputeadomain-dependentoutputastheresultofprocessinga

1.2.CONCEPTOFTHEPROPOSEDAPPROACH

11

hand-drawndiagram.Theneedforaexibleoutputisalsomentionedin[79].
Thesethreeimplicationsareduetothegoalofunderstandingsketcheddia-
grams.Thenextfourimplicationsresultfromtheothermajorgoal,naturaland
wing.draunrestrictedThefourthimplicationistosupportmulti-strokeshapes.Dependingonthe
diagramlanguage,shapesmayhaveacomplexvisualappearance,whereitis
bothersometodrawsuchshapesinonestroke.Besides,eveniftheshapesare
simple,itismoreconvenienttodrawtheminasmanystrokesasonedesires.
Thefifthimplicationregardsthetechniqueusedforrecognition.Theprevious
sectionhasdiscussedtheprosandconsoffeature-basedrecognition.Itcanbe
easilyimplemented,butusuallymakescertainassumptionsontheusersstyleof
drawing.Accordingly,webelievethatsuchapproachesshouldbeabstainedfrom,
atleastingeneral.Forspecialcases,however,feature-basedrecognitionmaybe
considered.beshouldandusefulAcentralissueoffeature-basedrecognitionisthatclustering,andevenmore
sosegmentation,areveryhardchallenges.However,bothmustbepossiblefor
asketchingapproachinordertonotrestricttheuserwhiledrawing.Therefore,
thesixthimplicationistoallowforautomaticclusteringandsegmentationofthe
es.stroksuserTheseventhandfinalimplicationistosolveambiguitiesautomatically.Am-
biguitiescannotbeavoided,sotheymustbedealtwith.Ifthisinvolvestheuser,
e.g.,byaskingforthecorrectinterpretationofanambiguousshape,naturalnessis
lost,andtheinterfacebecomesmorecumbersomeandartificial.
Inordertoconcludethissubsection,thefollowingenumerationlistsallseven
designimplications.Keepinmindthatthefirstthreeareduetothegoalofun-
derstandinghand-drawndiagrams,whilethelastfourareduetothegoalofunre-
etching.skstrictedonrecognition-line(i)approachcgeneria(ii)resultscdomain-specifi(iii)(iv)multi-strokerecognition
(v)nodependencyonafeature-basedapproachingeneral
(vi)automaticclusteringandsegmentation
(vii)automaticresolutionofambiguities
ThenextsubsectiondiscussesthedesignofDSKETCHinordertomeetthese
implications.

12

ODUCTIONINTR1.CHAPTER

Derivingdesignfromtheimplications
ThissubsectiongivesaconceptualoverviewofDSKETCH.Theapproachitselfis
designedinawaythatallimplicationsoutlinedaboveareconsidered.
Implication(ii)requiresdesigninganapproachthatisgeneric,i.e.,nottailored
toaapproachspecificinorderdiagramtoadaptlanguage.ittoaInstead,diagramitmustlanguage.beThispossibletocustomization,customizewhichthe
hastobedonebyalanguagedesigner,mustbespecifiedinsomeway.Sothe
keytoagenericapproachistohavespecificationsthatdescribeallnecessary
customization.Ofcourse,theapproachmustalsobeequippedwithaninterface
wherethespecificationisentered.Moredetailsonspecificationsarediscussedin
.wbelosubsectionaImplications(iv)through(vi)demandmulti-strokerecognition,nodepen-
dencyonfeatures,andsupportforautomaticclusteringandsegmentation.All
oftheseissuesconcerntherecognizer.Ontheotherhand,ambiguities(vii)can-
notbesolveduntilallshapesarerecognized,andaprocessingresult(iii)cannotbe
analysiscomputed.beforeConsequentlyallshapes,thereareknomustwn.beaBothsecondtaskscanstagebefollowingsummarizedthebytherecognitionterm
analysis.thisperformswhichFigure1.3showsthebisectionintorecognitionstageandanalysisstage,and
thespecification.Processingstepsareshownasrectangularboxes,datastructures
areshownasroundedboxes.Solidarrowsdenoteowofinformation;thedashed
isarroawskdenotesetchingtheeditorinuencethatproofthevidesaspecification.GUIwhereFromhethecanuserdrawstheperspectiskvetch,e,therewhile
theoutputoftheeditoristhedomain-dependentresult(iii).Internally,theGUI
capturesthestrokesdrawnbytheuser,asrequiredbyimplication(i),andcaptures
thetextwrittenonthecanvas,andfeedstherecognitionwiththestrokesandtext.
text,Then,andthetherecognitionanalysisstagestageidentcomputesifiestheallfinalshapesresultbasedrepresentedonthebytheshapes.strokTheesfulland
processiscustomizedbythespecification.

analysisandRecognitionFortherecognitionweproposeanarchitecturethatdoesnotsolelyrelyonfea-
tures.Instead,adifferentarchitectureisused,asshowninFigure1.4.Whenever
astrokeisdrawnonthecanvas,itisunknownwhatthisstrokeissupposedto
represent.Also,segmentationandclusteringareunknown.Toaccountforthis
uncertainty,allstrokes(andtext)arefirstfedintotransformers,whichperform
low-levelpreprocessing.Thereasonforhavingmorethanonetransformerwillbe
.wbeloxplainedeTheresultsofthetransformersarestoredinmodels.Eachtransformerisas-

1.2.

CONCEPT

OF

THE

OPOSEDPR

CHAOAPPR

13

14

CHAPTER

1.

ODUCTIONINTR

1.2.CONCEPTOFTHEPROPOSEDAPPROACH

15

performsbottom-uphypergraphparsing,usingtheedgesintheRHMasterminal
symbols.Thetaskoftheparseristoidentifyasyntacticallyandsemantically
correctsubsetofallshapesidentifiedbytherecognizer.Thederivationstructures
obtainedbytheparsingprocessareusedtocomputethefinalresultofdiagram
processing,describedbyimplication(iii).HypergraphsareusedbyDIAGENas
datastructure,astheyareverysuitableforthepurposeandallowforaneasy,in-
tuitivemodelingofdiagrams.Accordingly,boththereducerandtheparserare
controlledbyrules,andworksimilartoexistinggraphtransformationsystems.
Theexistenceofananalysisstagesuggestsabstainingfromeagerrecogni-
tion;instead,lazyrecognitionshouldbepreferred.Theanalysisheavilyexploits
contextinformation,thusitisnotmeaningfultostartprocessingasketchbefore
drawinghasfinished.Onlytheuserknowswhenthisisthecase,soheistheone
todecideaboutwhentoprocesshissketch.Asimilarapproachistakenby[42].

languagediagramaSpecifyingAsmentionedabove,DSKETCHisnotlimitedtoaspecificdiagramlanguage
ordomain.Instead,itisgenericandcanbecustomizedusingaspecificationofa
diagramlanguagetounderstandexactlythislanguage.Thespecificationiswritten
byalanguagedesigner.Itcontainsalltheinformationrequiredtounderstanda
sketch.Thisincludesthevisualappearanceofshapes,howtheycanberelated
toeachother,andfurtherinformationdescribingsyntaxandsemantics,whichis
requiredbyDIAGEN.Syntaxisdescribedbyreductionrulesforthereducer,and
evproductionaluationrulesappliedfortothethederiparserv,ationwhilestructuresemanticsobtainedarebyspecifiedthebyparserrules.forattribute
Whenprocessingasketch,shapesarerecognizedfirst,andthenanalyzed.
Eachofthesetwostagesiscomprisedofthreesteps.Thereby,thespecification
onlydescribeshowtheindividualprocessingstepsareapplied,butnotiftheyare
applied.Factis,eachprocessingstepisalwaysapplied,andneverleftout.
ThevisualappearanceofshapesisacentralissueforDSKETCH.Sincethe
wholeconceptisgeneric,thereisalsoaneedforagenericframeworkthatallows
forspecifyingshapesfromdifferentdomains.Thebasicidea,similartootherap-
proaches,istoconstructshapesfromprimitives.Primitivesarethebasicbuilding
blocksforshapes.Theydonotdependonanydiagramlanguageordomain.In
ordertoidentifyareasonablesetofprimitiveswehaveexaminedvariousdiagram
languages,e.g.,theUML.Wefoundoutthatabroadrangeofshapescanbebro-
kendowntoasmallsetofprimitives.Thesemustbekeptverysimpleinorder
tobenottoospecific.Intotalweidentifiedfourdifferentprimitivessuitingour
purpose.Thesearestraightlines,arcs,linksandtext.Examplesofshapesand
primitivesareshowninFigure1.5.
Straightlinesarethemostoftenusedprimitive.Arectangle,forexample,

16

CHAPTER

1.

ODUCTIONINTR

1.2.CONCEPTOFTHEPROPOSEDAPPROACH

17

thelinkprimitivedoesnotdescribesuchrestrictions,butismoregeneral.
Thesethreeprimitiveshaveincommonthattheyeachconnecttwopoints.
Thisisanimportantobservationforthespecificationofshapes.Fortherectangle,
eachlines.ofThethetipfourofthecornersarrowisisaapointpointthatwhereisbothconnectedthelinestofortwotheotherarrowpointsheadbybetwgin,o
byandatwhereleasttwtheoshaftprimitibevesgins.Wjunctionecallpointssuchtopointsindicatethatarethattwoconnected(ormore)tootherprimitipointsves
arejointatthesepoints.Figure1.5showsexamplesofshapesandhowtheyare
arenocomposedjunctionofprimitipointsves.areshoJunctionwnaspointsunfilledareshocircles.wnasWefilledcallcircles.thesepointsPointswhichsimple
.pointsstraintsOfwecourse,canprimitifurthervesspecifyaloneareprimitinotves.sufForficientexampltoe,specifythearroshapes.wheadUsinghastocon-be
constrainedinsuchamannerthatnoteverytwolinesandonelinkconnectedat
onejunctionpoint(thearrowtip)formanarrow,butonlyiftheanglesenclosed
habyvethethelinessameofthelength,headandandifthetheshaftshaftareisnottooconsiderablylarge,andlongerifthethanlinestheoflinestheofheadthe
head.Thefourthprimitive,text,representstextstringsthathavebeenwrittenonthe
canvas.Internally,thetextprimitiveischaracterizedbythestringitselfandthe
boundingboxdescribingwherethetextislocatedonthecanvas.Tospecifyhow
therelatedtexttoprimitijunctionveispointsrelatedandtosimpleotherpointsprimitiofves,thesetheotherboundingprimitivboxes.ofthetextis
itsSincecontent.textForconeveysxample,parttheofthecapacitymeaningofaofplaceaskinaetch,Petriitisnetoftenisdescribedrestrictedbyin
anumber,andnotbyletters(cf.Figure1.1).Therefore,foranimplementation
itmaydictionarybe,ausefulstringtoprogrammarvide,ormeaansretogularedescribexpression.thecontentsofatext,e.g.,bya
recognitionDuetothesestage.fourThiswprimitiay,veacheswetransformerproposetocanuseprocessdifferentstrokesfromtransformersadifinferentthe
andpointyetofvieanotherw.Oneforlinks.transformerThisalloonlywsforlookssforeparationstraightoflines,concerns;anotherhoweonlyver,fortherearcs,is
noneedforaone-to-onecorrespondentbetweenprimitivesandmodels.Finally,
furtherapplyingdiftransformersferentcanalgorithms.beintegrated,e.g.,toimprovelow-levelrecognitionby

Adifferentpointofview
TheconceptofDSKETCHcanbeillustratedfromadifferentpointofviewthanthe
onetechniquetakentoinincludeFigurethe1.3.Insteadspecificationofcanfocusingbeonhighlighted.theconceptItwoforkstheintheapproach,followingthe

18

CHAPTER

1.

ODUCTIONINTR

OUTLINE1.4.

19

dencgenericyonaapproach,feature-baseddomain-specificrecognitioninresults,general,multi-strokautomaticerecognition,clusteringnoanddepen-seg-
mentation,andautomaticresolutionofambiguities.
Theoverallcontributionofthisthesisismanifold.Allofthefollowingbenefits
havebeenachievedwiththeproposedapproach.Theyareexplainedindetail
thesis:thethroughoutTherecognitionprocessusesanew,powerfularchitecture.Itreliesonin-
dependenttransformersandmodels,whichallowforparallelinterpretation
ofthesamestroke.Anautomaticallycomputedsearchplandeterminesthe
searchorderinwhichindividualshapesareidentifiedandassembled.
Theproposedrecognizerismodular.Itsdesignallowsforeasyintegration
ofnewprimitivesandconstraints.
Thererecognition.isaclearLow-leveldistinctionrecognizersbetweenfromlow-leothervelresearchrecognitiongroupsandcanhigh-lebevinte-el
grated.Thereautomaticallyisananalysisresolvestage,ambiguitieswhichinusesarerulesliablegivenandbyrobtheustway.specificationForthisto
purpose,ambiguitiesareexplicitlymodeledintheanalysisstage.
beTheveryanalysiusefulsstageforisthisbasedpurpose.ongraphThereisnotransformation,othergenericwhichhasapproachprovweenareto
awareofthatdoesso.
Bothrithms,theleadingrecognitiontoagoodstageandperformancetheanalysisofthefullstageapproach.compriseefficientalgo-
Theactualrecognitionratesoftheapproacharegood,evenforsketches
domains.ferentdiffrom

Outline1.4Thestructureofthisthesisisimposedbythetwostagesofdiagramprocessingwe
haveestablished,asshowninFigure1.4.Thesixstepsinvolvedarediscussedin
.9through4ChaptersInChapter2someexamplesofdiagramlanguagesaregiven:Petrinets,Nassi-
Shneidermandiagrams,aGUIbuilder,Booleanlogicdiagrams,Tic-tac-toe,and
statecharts.Allofthesediagramlanguageshavebeenspecifiedandtestedwith
DSKETCH.Furthermore,thechaptercharacterizesdiagramlanguagesDSKETCH
to.appliedbecan

20

ODUCTIONINTR1.CHAPTER

closelyAnrelatedin-depthapproachesdiscussionisofrelatedillustratedwinorkismoregivendetail:intheChapterwork3.ofAHselectionammondetof
isal.discussed.(LADDER),FurtherCostagliolaapproachesetal.(SkareetchaddressedGrammaasrs),well.andAPlimmercomparisonetal.of(InkKit)the
approachpresentedinthisthesisandthethreeexplicitlymentionedrelatedap-
en.vgiisproachesthroughThe6.threeChaptersteps4involvdiscussesedinthethelow-levrecognitionelprocessingstagearewhichillustratedisinperformed.ChaptersHere,4
strokesandtextareprocessedbytransformers,resultinginindependentmodels.
Chapter5explainstheactualsearchprocessbytheassembler,usedinorderto
identifyshapes.Thesearchplan,whichdeterminesthesearchorder,isexplained
indetail.ThisstepisfollowedbypostprocessingdescribedinChapter6,where
theresultsfromtheprevioussteparefilteredandsomeextrainformationisadded
ambiguities.ardinggreTheanalysisstageisalsocomposedofthreesteps,discussedinChapters7
shapesthrough9.identifiedChapterby7thedealsrecognizerwith.theInthiscreationstep,ofthespatialhyperrelationsgraphbetmodelweenfromshapesthe
areestablished.Processingofthehypergraphmodelbythereducerisillustrated
inmodel,Chapterand8.toItsdiscardpurposeinvisalidtoreducepatterns.theFinallynumber,ofChapteredgesa9ndenodesxplainsinthetheparsergraph,
whichverifiessyntaxandestablishessemanticsbasedonthederivationstructure,
andgeneratesthefinalresultofdiagramprocessing.
Chapter10discusseslessonslearnedfromseveralcasestudiesconductedwith
DSKETCH,andevaluatesboththeperformance(processingtime)andtherecog-
nitionratebymeansofauserstudy.Thethesisisconcludedwithasummaryin
.11ChapterguagesAppendixfromAChaptergives2.theAppendixcompleteBshowsaspecificationsfigureofthecontainingeallxampleprocessingdiagramstepslan-
andlustratesdataastructurescompleteofethexamplecompleteofthesketchprocessingofunderstandingadiagram,process.usingAppendixreal-lifeCdatail-
implementation.thefromentak

2Chapter

LanguagesDiagram

Thischapterdiscussessomeexamplesofdiagramlanguages,allofwhichcanbe
specifiedinandprocessedbyDSKETCH.Thismeansthatthevisualappearance
oftheshapes,thesyntax,andthesemanticsofeachoftheselanguagescanbe
weredescribedselectedinDSdueKEtoTCHtheir,withcharacteristsuitableicnature;specifications.theyTheserepresentadiagramwiderangelanguagesof
languages.diagramAclassificationofdiagramlanguagesisgivenin[28].Themaindistinctionis
between(i)connection-basedclassesand(ii)geometric-basedclasses,eachde-
scribingahierarchyofsingleclasses(cf.Figure2.1).Furthermore,thereexisthy-
bridlanguages.(i)ischaracterizedbygraphicalshapeswhichareinter-connected
insomeway,e.g.,bylines,orbyarrows.Itstwosub-classesareGraphandPlex,
whichbothrepresentgraph-likelanguages,butthelatterisrestrictedtosuchlan-
guageswhereeachshapeisconnectedtoafixednumberofothershapes.An
exampleofclassGrapharePetrinets(Section2.1).AnexampleofclassPlexare
Booleanlogicdiagrams,whicharediscussedinSection2.5.Furthermore,this
languageservesasagoodexample,becausethemeaningofanoperatorshapeis
determinedbyanattribute(inthiscase,textwritteninsidetheshape).Amongthe
presentedselectionofdiagramlanguages,thisappliestoBooleanlogicdiagrams
.onlyForgeometric-basedclasses(ii)thespatialarrangementoftheshapesofthe
languageconveysnecessaryinformation.Accordingly,relationsbetweenshapes
canrefertoadjacency,inclusion,orintersection,forexample.Themostgeneral
classwithin(ii)iscalledBox.Shapesoflanguagesinthisclassarecharacter-
izedshape.bySimilartheirisboundingclassIconicbox,,butwhichitdoesrequiresnotfixedneedsizestohaforvetheafixedboundingsizeforboxeseachof
shapes.Finally,thereisclassString,whichcontainsalltextuallanguages.These
arediagramsnot(subjectNSDs),toourwhichwareork.AndescribeedxampleinofSectionclass2.2.BoxAnearexampleofNassi-ShneidermanclassIconic

21

22

CHAPTER

2.

GRAMDIA

LANGUGESA

2.2.

ASSI-SHNEIDERMANN

GRAMSDIA

23

24

CHAPTER

2.

GRAMDIA

GESALANGU

2.3.

GUI

BUILDER

25

26

CHAPTER

2.

GRAMDIA

GESALANGU

2.5.

BOOLEAN

LOGIC

GRAMSDIA

27

28

CHAPTER

2.

GRAMDIA

GESALANGU

2.7.APPLICATIONRANGEOFTHEPROPOSEDAPPROACH

29

context-freelanguagescanbedescribed,andthereisanextensionwhichalso
alloarrowswsinfordescribinggraph-basedcertainlanguagesaspectslikePetriwhichnets,arenotstatechartsconte,xt-free.orFautomataorecanxample,be
diagramsembeddedhavthiseaway.tree-likDetailsewillstructure,begive.g.,eninBLD,Chaptercan9be.Notespecifiedthatlawithnguagescontewhosext-free
.onlyrulesThesecondlimitingfactoristheexpressivepowerofthespecificationof
itivshapes.escanThebeintegraphicalgratedinprimitithevgiesveliknelinesconcept,orifarcsarenecessary.predefined,Howevber,utthefurtherspecifica-prim-
vtionariabilityassumes.Forthateshapesxample,eaxhibitrectangleafixedalwvisualaysconsistsappearanceoffourthatisstraightfreeoflines,structuralcon-
nectedattheirendpoints.Whilearectanglecanbedrawnfreely,forexample,
valweryaysthinconsistsormoreofliktheseeafoursquare,straightandlinesin–onethestrokestructureorinissefixved.eral,therectangle
Toconcludethissection,DSKETCHcanbeappliedtodiagramlanguagesfrom
allclassesillustratedintheintroductiontothischapter,giventhattheirsyntaxcan
bevisualdescribedstructureconteofthext-freeshapes(orisusingfixed.thementionedextension),andgiventhatthe

30

CHAPTER

2.

GRAMDIA

GESALANGU

3Chapter

orkWRelated

ThereApproachesarethosetoskapproachesetchingcanwhichbeaimgroupedattheunderstaaccordingndingtooftheirovtechnicaleralldraobjectiwings,ve.
likewedo,andthereareotherapproaches,e.g.,formodeling,foranimation,or
arefordesign.discussedTheinfirstthisgroupchapteris.stronglyApproachesrelatedfromtotheourwsecondork,andgrouprelatedhaveadifapproachesferent
scope,andarementionedbrieyforthesakeofcompletenessonly.
lowsAnfordraapproachwingto3D3DmodelsmodelingofisfreeformTeddy,objectsforelikexample,stuffedbyIganimalsarashi[et57]al.byIt2Dal-
sketches.Anotherapproachto3DdesignbysketchingisILoveSketchbyBae
etal.,whichallowsprofessionaldesignerstocreate3Dmodels[8].Thistaskis
aidedwithdedicatedfunctionalitylikemirroringstrokes,e.g.,tocreatetwoiden-
ticalwingsofanairplanebyjustdrawingonewing.
Foranimation,MotiondoodlesbyThorneetal.allowforfirstsketchinga
alongcharacterusingsimilaronetostrokae[stick96].figureThe,shapeandofthenthisstrokdescribingeisapathinterpretedthistocharacterdecidetravwhenels
thecharactergoesforwardandbackward,whentojump,orwhentorun.Davis
etal.[33]alsoallowforcreationofstickfigures.Animationsaredescribedby
sketchingannotatedkeyframesoftheanimation.
Turquinetal.allowfordrawinggarmentsinteractively.Theuserdrawsthe
frontorthebackofthegarment,andthesystemautomaticallydressesafigure
withthatgarment[97].Igarashietal.alsoallowforplacing2Dclothingon3D
modelsbyrequiringtheusertoplaceidenticalmarksonboththeclothingand
themodel[56].Thesystemthenplacestheclothingonthemodelbyoverlapping
marks.identicalThegroupofapproachescloserrelatedtoourresearcharethosewheretech-
nicaldrawingsareprocessed.Inthefollowingsections,fourapproachesaredis-
cussed:GRANDMAinSection3.1,LADDERinSection3.2,SketchGrammars
inSection3.3,andInkKitinSection3.4.Thesefourapproachesareconsid-

31

32

CHAPTER3.RELATEDWORK

eredindetail,becausewefindthemeitherimportantandinuential,orbecause
oftheirfurtherobjectiveisapproaches.similartoSectionours.3.6Sectiondraws3.5abrieycompariilsonlustratesbetweenaDbroaderSKETCHselectionand
GRANDMA,LADDER,SketchGrammarsandInkKit.

GRANDMA3.1

AsalreadymentionedinSection1.1,theworkofDeanRubine,publishedinthe
earlynineties,hadagreatimpact[83,84].Basedontheobservationthatitis
difcallyficulttogeneratingcreatearecognizers.hand-codedTothisrecognizerend,a,heframewtackledorkthecalledproblemGRANDMAofautomati-(Ges-
tureRecognizersAutomatedinaNovelDirectManipulationArchitecture)was
edevxampleseloped.ofItallogestures.wsforAbout15automaticexamplesgenerationperofgesturearerecognizersreportedbasedtobeonsuftrainingficient
forareliablerecognizer.Recognitionisbasedon13featureswhichwereselected
duetosomereasonablecriteria:smallchangeintheinputshouldresultinsmall
changeinthefeatures,andforreasonsofefficiencythenumberoffeaturesshould
notreliablybe.tooForhigh,eachbutinputhighstrokeenougheachsoofthatthedif13ferentfeaturesisgesturescomputedcanbeanddistinguishedclassified
byalinearfunctionthatcomputestheweightedsumofthefeatures.Eachgesture
hasitsownsetofweights.Thestrokeisinterpretedtobethegesturewhichyields
thegreatestweightedsum.Theweightsaredeterminedbyexaminingthetraining
samples.Rubinegivestworeasonsforusingsingle-strokegestures.First,hewantsto
avoidtheissueofsegmentation.Second,single-strokegesturescanbememorized
aremoremeanteasilyto.Forrepresentthesecondcommands.aspect,theAfterafocusgestureonhasgesturesbeenisprocessed,important.itsGesturesrepre-
sentingstrokeisremovedfromthescreen.Thisisacontrasttoother,morecurrent
approacheslikeourown,wheretheusersstrokesarepreserved.
Usingdifferentsetsofgestures,recognitionratesexceeding96%arereached,
thefor30highergesturesthetosmallerthedistinguish.numberEvenofdifbackferentin1991,gesturestheis.Peakperformancevaluesofarethereachedimple-
mentationwasverygood,withlessthan10msfortheclassificationofthese30
gestures.

LADDER3.2

InthecourseofherPhD,TracyHammondhasdevelopedagenericapproachto
sketchingcalledLADDER(LanguageforDescribingDrawing,Display,andEdit-

LADDER3.2.

33

inginRecognition)[48,46,47].Theapproachistwo-fold.Ontheonehand,it
consistsofahigh-leveldescriptionlanguagewhichallowsforaneasyspecifica-
tionofwhatkindsofshapesaretoberecognized.Ontheotherhand,thesystemis
equippedwithagenericrecognizerthatiscustomizedbythespecificationtorec-
ognizethedescribedshapes.ThesetwoprinciplesareverysimilartoDSKETCH.
However,unlikeourapproachLADDERcompletelylacksananalysisstage.The
generalideaistoprovideaneasy-to-use,butpowerfulsystemtoallowexpertsin
adomaintocreatesketchingeditors,eveniftheyhaveonlylittleunderstandingof
thetechnicalaspectsofsketching.
Thedescriptionlanguagecanbeusedtodescribethevisualappearanceof
shapesintermsofprimitiveslikepoint,path,straightline,curve,arc,spiral,el-
lipseortext.Recognitionofprimitivesisalsoguidedbyconstraints,whichare
eitherhardorsoft:Forsuccessfulrecognition,hardconstraintshavetobesat-
isfied,whilesoftconstraintsshouldbesatisfied,butdonothavetobe.Also,
thedescriptionlanguageallowsforthespecificationofeditingoperations,and
ofabeautifiedvisualappearancethatreplacestheusersstrokesaftersuccessful
recognition.ThesetwoaspectsaredifferentfromDSKETCH,butsuitthephilos-
ophyoftheproposedrecognizerverywell(seebelow).Groupsofshapescanbe
defined,buttheironlyuseisforeditingoperations.Apossibleimprovementin
termsofrecognitionrates,drivenbyatop-downapproach,isconsidered,butis
notimplemented.Thedescriptionofshapesevensupportsabstractshapesand
inheritance,inspiredbytheconceptsofobject-orientedprogramminglanguages.
Acompletedescriptionofthelanguageanddetailedexamplescanbefoundinthe
appendixofHammondsPhDthesis[49].TwoadvantagesofLADDERarethe
expressivepowerofthelanguageandtherecognitionratesofitsrecognizer,which
areverygoodevenfordifferentdomainslikeJapaneseKanji[92],orconstraint
networkdiagrams[50].
Primitivesarerecognizedbythefeature-basedlow-levelrecognizerofTevfik
Sezgin[91,89].Here,foreachstrokecurvatureandspeeddataarecombinedto
obtainapolylinerepresentationofthestroke.Inthesecondstep,segmentsofthat
polylinearereplacedbyBeziercurvestobetterfitcurvedparts.Finally,using
simplefeatures,primitivesarerecognized.Toassembleshapesfromtheserecog-
nizedprimitives,arule-basedsystemisused.Thespecificationistransformedinto
rulesforthesystem,therecognizedprimitivesareaddedasfacts.Fromthesefacts
shapesareconstructedaccordingtotherules.Thecompleterecognizerworksin-
crementally.Partialfindingsoftherulesystemarekept.Afternewstrokesare
drawn,newprimitivesarerecognizedandaddedasfacts.Thesystemthentriesto
continuethepartialfindingswiththenewfacts.
Aseveredrawbackofthisrule-basedrecognitionisitsruntimeperformance.
HammondadmitsinherPhDthesisthattheruntimemayexceedonehourif
thereare30ormorelinesonthecanvasthathavenotbeenusedforhigh-level

34

CHAPTER3.RELATEDWORK

Figure3.1:ArchitectureoftheLADDERsystem[48].

shapes[49].Accordingly,sheproposesanotherrecognitionapproachthatcom-
binesprimitivesinanon-deterministicmanner.Inordertoachieveacceptable
runtimeperformance,allprimitivesareindexedfirst,inawaythateachsubse-
quentaccesscanbeperformedveryquickly.Thisavoidstheextremeruntimes
thatmayhappenwiththerulebasedsystem.Thenewrecognizernowhasfully
replacedtheoldone,andisthebasisforallfurtherresearchinhergroup;however,
inmanyofthegroupspublications,stilltheolderjournalarticle[48]iscited.
Shapescanbespecifiedtobefinal;wheneverafinalshapeissuccessfully
constructed,thefactsrepresentingtheshapesprimitivesareremoved.Asacon-
sequence,onceafinalshapeisrecognized,itisfixedandcannotbeundonelater,
eveniftherewouldbeabetterinterpretation.Ifashapeisnotfinal,itsprimitives
arepreservedandcanbeusedagain,butthishasanegativeeffectontheruntime.
Contextishardlyconsidered;however,thepresenceofothershapescanbespec-
ifiedtoinuencetherecognitionresult;forexample,acirclecanberecognized
asapinjointifitisplacedontwoclosedshapes(thebodiesitconnects).Dueto
theeager,incrementalrecognitionitisreasonabletospecifyeditingoperations,
e.g.,movingtheheadofanarrow,whilekeepingitstailfixed.Iftherewereno
eagerrecognition,suchoperationscouldnotbeapplied.Theoverallarchitecture
ofLADDERisshowninFigure3.1.
Similartoourexperience,theoverallrecognitionratestronglydependson

SKETCH3.3.GRAMMARS

35

therecognitionrateofthelow-levelrecognizer.Ifprimitivesaremissedatthis
lethisvel,noconcernsrecovtheeryistransformerspossiblelater(cf.,theSectionprimiti4.1ves).areIninethecasvitablyeoflost.InLADDER,ourcase,the
cusoffeature-basedresearchinrecognizerHammondbysSezgingroup.isafBrandonfected,Pandaulsonimprovsuggestsementsanearewloinw-lethevfo-el
recognizercalledPaleoSketch[76],whichisalsobasedonfeatures.Hismaincon-
tribbinedutionwithisathedeliberateintroductionchoiceoftwofoenewxistingfeaturesfeatures.basedonSupportedthedirectionprimitivesgraphincludecom-
thatline,eachpolylineprimiti,cirvecleis,draellipsewn,inarc,onecurvestrok,e.spirIfal,sevanderalhelixprimiti.Thevesbasicaredrawnassumptionbyoneis
stroke,thestrokeistriedtobesplit.However,thisfunctionalityisverybasicin
itscurrentstate,andisplannedtobethesubjecttofuturework.Therecognition
ratesubjectofwasprimitivrequiresisedtoreportedalwaystoedrawxceedone98%.primitiHovweeviner,oneintheirstroke,testwithsetting,onlyeachone
exception,wheretwogivenprimitivesweretobedrawninonestroke.Thisis
averystrongrestriction,whichisnotverynatural.Nevertheless,PaleoSketchis
isveryintegratedpromising,inandLADDERseemsandlikeservanesimasproanvementalternatiovveretopreviousSezginwsork.PrecognizeraleoSk.etch

GrammarsetchSk3.3AnapproachdrivenbyformalconsiderationsisthatofSketchGrammars(SkG)
byGennaroCostagliolaetal.[21,23,20].SkGextendstheformalismofExtended
PositionalGrammars(XPG)[29],whichitselfisverypowerfulandallowstode-
scribelanguagesfromallclassesillustratedintheintroductiontoChapter2.SkG
allowsfordescribingboththevisualappearanceofsymbols(calledinkgrammar),
andthesyntacticalaspectsandsemanticsofadiagramlanguage(calledlanguage
grammar)inthesameformalism.Theinkgrammarfollowsthesameideaas
LADDER.Primitivesarecombinedbyrelationsthatallowforpreciselyexpress-
inghowtheprimitivesarerelated,e.g.,wheretheyintersect,orwhichangletwo
linesenclose.Actions,whichareattachedtotherules,describehowtheattributes
oftheshapesarecomputed.Furthermore,relationscanalsobetemporal,e.g.,to
indicatewhenasecondprimitivehastofollowitspredecessor.Thisisespecially
usefulfordescribingeditinggestures,whichcanalsobeachievedbySkG.Tem-
poralrelationsarenotusedbythelanguagegrammar.Theinkgrammarandthe
languagegrammartakenasawholedescribeavisuallanguage.
Forthelanguagegrammaritisnecessarytodescribehowshapescanberelated
toeachother.Thisisaccomplishedviaattachmentregions,thesameconceptwe
alsorelyon(cf.Section7.1).Thesearedefinedforeveryshape,e.g.,bothends
ofanarrow,ortheoutlineofarectangle.Thenthelanguagegrammarrefers

36

CHAPTER3.RELATEDWORK

totheseregionsanddescribestheir1connectionintermsofrelations,whichare
independentofthevisuallanguage.
Processingasketchfollowsthedistinctionbetweeninkgrammarandlanguage
grammar.Threestepsareinvolved,showninFigure3.2.Thefirstistherecogni-
tionoftheprimitiveshapes,whereSkGreliesontheSATINtoolkit[52].Inthe
secondstep,allprimitivesareconsideredasterminalsymbolsfortheinkgram-
mar.AsSkGextendsXPG,whichitselfextendsstringgrammars(mainlyby
addingmoregeneralrelationsbetweensymbolsthanjustconcatenation),anLR-
parsingapproachcanusedforparsingtheinputaccordingtotheinkgrammar,i.e.,
forrecognizingshapes.Theresultisasetofshapes,andasetofstrokesthatcould
notbematchedyet.Inthethirdstep,therecognizedshapesareconsideredinturn
asterminalsymbolsforthelanguagegrammar.Asthelanguagegrammarfollows
thesameformalismastheinkgrammar,thesameparsingapproachcanbeused.
Theparserthustriestoderivethestartsymbolinabottom-upmanner.However,
theresultisnotaderivationtree,butaforestoftrees.Eachtreeintheforestde-
scribesavalidinterpretationofthesketch,i.e.,aninterpretationthatsatisfiesall
rulesfromthespecification.Inordertocomparethetrees,rankingvaluesfortheir
rootsarecomputed.Thesevaluesareultimatelybasedonconfidencevaluesfor
theprimitives,andtherelationsusedwhenparsingtheinputinordertorecognize
shapes.Thefullapproachworksincrementally,andapplieseagerrecognition,which
isclearlyfavoredbytheauthors.Eachnewstrokeisimmediatelyprocessedto
recognizeprimitives.Whenparsingtheinput,thesystemnotonlyrecognizes
completeshapes,butalsokeepstrackofshapesthatareonlypartiallymatched.
Newprimitivesareusedtotryandcompletethesepartialshapes.Havingrecog-
nizednewshapes,thelanguagegrammarisconsideredagain,andtheresulting
interpretationisshowntotheuserasvisualfeedback.
Parsingtheshapesaccordingtothelanguagegrammarmeanstoanalyzethe
shapesandtheircontext,andtogenerateasyntacticallyandsemanticallymean-
ingfulinterpretation,somethingthatLADDERdoesnotdo.TheauthorsofSkG
alsorelyoncontexttoresolveambiguities.Thereforeithasbeendecidedfora
grammar-basedapproach.SimilartoSkG,inDSKETCHwealsoexploitcontext,
butuseadifferentformalismfordescribingsyntaxandsemantics,andadifferent
parser.WhatisveryappealinginSkGisthatbothshapesandthelanguageitself
(andeveneditinggestures)aredescribedbythesameformalism.
MorerecentdevelopmentofSkGinvolvestraining[22],errorrecoverytech-
niques[24]andautomaticshapecompletion[25].Trainingisusedtodetermine
reasonablevaluesforthresholdsinvolvedinprimitiveshaperecognitionandpars-

1Notethatwehaveadifferentnotionofthetermrelation(cf.Section7.2),asweuseittode-
scribetheactualrelationsbetweenlabeledattachmentregions,dependingonthevisuallanguage.

INKKIT3.4.

Figure3.2:ArchitectureoftheSkGsystem[24].

37

ing.Inuserstudies,thetrainedrecognizeralwaysoutperformstheuntrainedone.
Errorrecoveryispossiblebecauseincompleteshapesarealsokept.Itallows
forovercomingmissingprimitivesandincorrectlyrecognizedprimitives.Shape
completionassiststheuserindrawingcomplexshapesbysuggestingautomatic
completion;thereforeitisevenconsideredhowtheuserdrewsuchshapesbefore.

InkKit3.4

Understandingthatsketchingisanapplicationdomaininitself,BerylPlimmer
andhergroupattheUniversityofAuckland,NewZealandstartedworkingon
InkKit[19,79].Itisdesignedtobeatoolkitforcreatingsketch-basedappli-
cations.Accordingly,InkKitprovidesprogrammerswithusefulfunctionalityto
developsuchapplications.Thisincludesagenericrecognitionapproach,aGUI,
andaneasy-to-implementinterfacetoutilizeInkKitandembeditinonesownap-
plications.Furthertopicsaddressedarebeautification[80]andswitchingbetween

38

CHAPTER3.RELATEDWORK

Figure3.3:ArchitectureoftheInkKitrecognizer[79].

differentlevelsofformality[101].
Thefocusoftheresearchliesmoreonhigh-levelaspects,andlessonlow-
leveltechnicalaspects.Forrecognition,theybasicallyrelyonRubinesapproach,
whichtheyhaveimprovedinsomeway.First,thefeaturesbasedonabsolutesize
werereplacedbyfeatureswhichonlymeasureratios.Thisallowsformoreex-
ibilityindrawingandisreportedtoimproveaccuracyoftherecognizer.Second,
ajoinercombinestwostrokesifbothstrokesdonotformclosedshapesandhave
theirmulti-strokendepointssymbolsclose.toUsingeachthisother.approach,Thisenablesprimitivestheir(whisystemchheretoalsoarecalledaccountbasicfor
shapes)arerecognizedinagenericfashion.Thedomain-dependentrecognition
so,thennoidentifiessourcecodeshapesis(calledrequiredbythecomponents)programmerfrom,thesebutonlyprimitieves.xamplesInofordertoshapes.do
Theprimitivesfoundintheexamplesareexaminedfortheirrelations(intersect-
ing,enclosing,etc.)andtheirrelativepositionstoeachother.Ambiguitycan
occuramongtheprimitives.Fortherecognitionofshapes,allprimitivesarefirst
examinedprobabilitiesforandtheliksameelihood,relationstheandshapespositionsarefound.asintheTheecontexamples.xtofaThen,shapebased(givenon
byothershapes)isnotconsideredfortheresolutionofambiguities.Figure3.3
ofshoUIwsthediagramsarchitecture(similaroftoInkKitSections2.3processing)theauthorsapproach.claimInantoreachinformalaevrecognitionaluation
95%.aboutofrateTextandgraphicsmaybeplacednexttoeachotherwithoutanymodechange.
Inordertodistinguishtheonefromtheother,thestrokesarefirstpassedtoa
ognizerdividerforfromrecognition.MicrosoftWStrokindoeswsTfoundablettoPCbetextEdition,arewhichrecognizedworksbythereliablytext.rec-All
otherstrokesareconsideredtobegraphics,whereshapesarerecognizedasde-
scribedabove.Forthedivider,firsttheonedeliveredaspartoftheMicrosoft

3.5.OTHERAPPROACHES

39

TabletSDKwastried,butdidnotproducesatisfyingresults.Asimprovement,a
owndividerhasbeenimplemented,whichsubstitutestheMicrosoftdividerand
performsmuchbetter.However,thetopicisstillunderinvestigation[75].
Thefundamentalgoaloftheprojectistosimplifythecreationofsketching
applications.Forthisreason,recognitionofshapesisnotdescribedbysource
code,butbyexamples,whichareeasiertosupply,andsavelinesofcode.For
thesamereason,considerableeffortisspentonincludingmorefunctionalityin
InkKittofurtherreducetheamountofdomain-specificcode.In[39],forexample,
connectorslikelinesandarrows,whichareverycommontomanysketches,are
examinedinthreeexemplarydomainsinordertoidentifycertaincharacteristics.
Basedonthefindings,connectorswereintegratedintothecorefunctionalityof
InkKit.AcentralaspectofInkKitsuserinterfaceistoallowfordifferentsketches
fromthesamedomainatthesametime.Thesinglesketchescanbelinkedwith
eachothertocreateonelogicalunit,whichistranslatedasawhole.Themeaning
ofthesketches,thelinksbetweenthesketches,andtheresultofthetranslation
processhavetobehand-codedbyaprogrammerwhowantstouseInkKitwithina
certaindomain.UnlikeDSKETCH,noformalapproachistakenherewhichallows
forspecifyingtheseaspects.Ontheotherhand,hand-codingallowsforgreat
exibilityandfreedom,thusenablingabroadrangeoffieldsofapplications.In
recentwork,theapproachhasbeenextendedtosupportevensketchesofdifferent
domainsatthesametime[86].However,thereisnoformaltreatmentofsyntax
semantics.or

oachespprAOther3.5Besidesthefourapproachesillustratedindetailintheprevioussections,there
giarevenmaninythisothersection.approachesItcontainstoskvariousetchingasapproacheswell.Aonloselectionw-leveloftheserecognitionworksandis
agents,high-levelgraphrecognition,transformation,whichorareallHiddenguidedMarkbyovdifModelsferent(ideasHMMands).concepts,e.g.,
reportedAnotherbyZanibbiutilizationetal.of[103graph].Usingtransformationagiventosetskofetchingsymbols(likthateDhaSvKeETCHalready)is
beenrecognized,theirapproachanalyzesmathematicalexpressions.Thesymbols
asincludeonesymbol;numbers,theoperators,equalstokandenisletters.givenTheastwsumosymbols,operator,forbotheshortxample,ishorizontalgiven
knolineswn.ofForapproximatelyanalysis,aequalthree-steplength.approachTheissizeproandposed,locatiwhichonofiseachroughlysymbolsimilaris
totooureachotheranalysisarestage.established.First,allEvensymbolsaresuperscriptexamined,andandsubscriptstheirarerelatiregvearded.positionsThe

40

CHAPTER3.RELATEDWORK

resultisatree-likestructure.Second,tokenscomprisedofmorethanonesymbol,
likeequals,orfunctionnames,arecomposed.Treetransformationsareusedhere,
whicharespecifiedbyrules.Third,theresultingstructureistransformedinto
LATEXcoderepresentingtheoriginalmathematicalexpression.Ambiguitieslike
whetheratokenisaboveanothertoken,orasuperscript,forexample,aretreated.
Ambiguityinthesymbolsdrawnbytheuserisnotconsidered.
Thelow-levelrecognizerCALIbyFonsecaetal.[38]isbasedonfeatures,
butexhibitstwointerestingproperties.Allfeaturesarebasedontheconvexhull
ofallstrokesthatbelongtooneshape.Asaresult,therecognizeriscompletely
invarianttostrokeorder,direction,orcount,butpriorknowledgeaboutwhere
individualshapesarelocatedisrequired.Forclassification,fuzzysetsareused
whichallowforabettermodelingofambiguities.Therecognizerisnottrainable,
butonlycapableofrecognizingapredefinedsetofprimitiveshapesliketriangles,
rectangles,wavylines,etc.Thereportedrecognitionrateisabout95%.Usinga
naiveBayesclassifierfollowing[35],insteadoffuzzylogic,wasalsoproposed,
whichcanbetrainedtovariousshapes.JavaSketchItbyCaetanoetal.[14]is
ahigh-levelsketchingsystemforuserinterfacesbasedonCALI.Itallowsfor
constructionofUIwidgetsfromthepredefinedprimitivesbybasicspatialand
relationships.yadjacencCasellaetal.proposeaconceptuallyinterestinggenericframeworkforsketch
understandingbasedonagents[16,17,18].Theycanincludearbitrarysymbol
recognizers,buttheirorganizationisquitedifferentfromDSKETCH.Thereisan
individualagentforeachavailablekindofshape,calledanSRA(symbolrecog-
nitionagent).TheSRAsautonomouslysearchforshapes,butmaycommunicate
whicheachothertoexchangecontextinformation.Acentralagentmaysolvecon-
ictsbetweentheSRAs.UsecasediagramsfromtheUMLserveasanexample.
UsingaJava-basedimplementation,goodrecognitionratesarereported.Similar
toourfindings,thisisclearlyduetotheuseofcontextinformation.
AgentsarealsousedinSketchiXMLbyCoyetteetal.[31,32].Theirfocuslies
onuserinterfacedesignonly,asthisdomainbenefitsgreatlyfromasketch-based
approach.Theircontributionliesinhigher-levelaspects,e.g.,theoutputformat
ofthesystemisindependentofhardwareandoperatingsystem,soitsupports
multipleplatforms.Furthermorethebehaviorofthesystemcanbeadjustedtothe
specificneedsofindividualusers.Forrecognition,theCALIapproachisused.
High-levelrecognitionbasedongraph-matchingisinvestigatedbyLeeetal.
[64].Individualshapesarerepresentedasattributedrelationalgraphswhichcom-
prisebothgeometryandtopologyoftheshape.Thesegraphsarelearnedauto-
maticallyfromtrainingsamples.Giventhatindividualshapeshavealreadybeen
located,thecorrespondinggraphforashapeiscreatedfirst.Then,thebestin-
terpretationischosenbymatchingthisgraphwiththegraphsprecomputedfor
thetrainingsamples.Fourdifferentapproachestothisdecisionprocessarecom-

3.5.OTHERAPPROACHES

41

pared,allofthemguidedbyasimilaritymeasure.Agreedyapproachperforms
bestintermsofrecognitionrateandprocessingtime.Themainadvantageofthe
approachisthatitisinvarianttodrawingorderordirection.
AexibleapproachissuggestedbyGennarietal.[40].Itallowsforrecogni-
tionofindividualshapesfromacompletedrawing.Thestrokesarefirstapproxi-
matedbycurvesandstraightlines.Then,usingtwodifferentapproaches,single
shapesarelocated.Afterrecognitionoftheseshapes,e.g.,asin[64],usingsimple
scoressomeshapesareprunediftheyoverlapwithothershapes.Finally,hand-
codedrulesadddomaininformation.Inthisarticle,thedomainareelectronic
circuits.Theonlyassumptionsmadebytheapproacharethateachshapeisdrawn
oneafteranother,andnotinterspersed,andthat2to14strokesareusedforeach
shape.TheapproachbyGrundyetal.,MaramaSketch[44],addsanadditionallayerto
theEclipse-basedtoolkitMarama[45]fromthesamegroup.Maramaallowsfor
thegenerationofeditorsforvisuallanguagesbasedonspecifications.Marama-
SketchusesexistinginterfacestoextendMaramaeditorsbysupportforsketched
input.Theonlyextrainformationrequiredaretrainingsamplesfortheshapes.
Forrecognition,theHHReco[53]toolkitbyHseetal.isused.Itsproperties
aresimilartothoseofCALI.Multi-strokeinputissupported,butsegmentation
isnotpossible;instead,itisassumedthatthestrokescomprisingashapeare
known.ThefocusofMaramaSketchliesonhigher-levelaspectsofsketching.
Theirtoolsupports(amongotherthings)lazyandeagerrecognition,informaland
formalrepresentation,andexplicituserinteractionforambiguityresolution.Toa
certainextent,evencontextcanbeconsideredfordisambiguation,butnodetails
reported.areAlvaradoetal.presentanapproachcalledASSIST,whichislimitedtomechan-
icaldevices[3].Specialemphasisisputonambiguityresolution.First,arecog-
nizerdetectsprimitiveshapeslikebodies,springsorpinjoints.Then,theshapes
arescoredbysomebasicrules,whicharedomain-dependentandhard-coded.
Thefinalstage,resolution,selectsthefinalinterpretationforthesketchaccording
tothescores.Thisway,contextisconsideredandambiguitiesareresolved.In
laterwork,thegroupchangedtheirapproachtobedomain-independent[4,5]by
usingtheLADDERlanguagetodescribeshapes,andanincrementalhigh-level
recognizerbasedonBayesnetsinsteadofthehard-codedscoringschemes.Us-
ingBayesnets,itbecomespossibletoevenidentifyshapesdrawnonlypartially.
However,theapproachcannotperformsegmentationofstrokescontributingto
differentshapes,andisverylimitedinitsabilitytodescribecontextbetween
shapes;syntaxandsemanticscannotbedescribedatall.Althoughaimedtobe
appliedinreal-time,processingasinglestroketakessecondsinmanycases,as
theBayesnetsgrowquickly[2].
Thewell-knownBackofanEnvelopebyGrossetat.[43]extendsprevious

42

CHAPTER3.RELATEDWORK

workofthesamegroup,theElectronicCocktailNapkin[42].Therecognizeris
feature-based,clusteringofsymbolsisdonebyatime-outthreshold,andsegmen-
tationisnotsupported.Aninterestingfeatureitusesisa3x3grid,whichrecords
forthegridcellstheorderinwhichtheywerevisitedbythestrokes.Amulti-
levelclassificationprocedureassignscertaintyvaluesfrom0to5torecognized
shapes.Toaccountforautomaticresolutionofcontext,configurationsdescribe
whichshapesarerelatedtowhichothershapesintermsofsimplegeometriccon-
straintslikecontainsorleft-of.Configurationscanalsobedefinedrecursively,
whichallowsforamoreexpressivedefinitionofcontext.Severalexamplesin-
dicatethatarbitraryoutputispossibleasresultofthesketchprocessing,butno
technicaldetailsaregiven.Recognitionratesarenotreported.
Sezginetal.developedanapproachthatreliesonHiddenMarkovModels
(HMMs)[90].Itisbasedontheobservationthatdifferentusersalwaysdraw
shapesusingthesameoraverysimilarorderingoftheirstrokes.Thisobservation
isbackedbyauserstudy.TheadvantageofHMMsisthatthedrawingstyleof
usersdoesnothavetoberestricted.Duringtraining,foreachuser,andeachclass
ofshapes,aHMMiscomputed.Thentheanalysisofacompletesketchconsist-
ingofmanyshapesissolvedbyfindingtheshortestpathinagraph.Reported
recognitionratesaregood,andtheperformanceoftheapproachexcelsthatofa
baselinemethodusingfeatures.OtherapplicationsofHMMtorecognitionare
reportedbyHuetal.[54,55],andYuanetal.[102].
Furtherapproachestosketchingarediscussedandcomparedin[100,13].

Comparison3.6

Inordertoconcludethischapter,andtohighlightthevalueofourcontribution,
thissectioncomparesDSKETCHtothosefourapproachesthathavebeenillus-
tratedindetailbefore:GRANDMA,LADDER,SketchGrammars,andInkKit.

Similaritieswithanddifferencestootherapproaches
Commontoallfiveapproachesisthattheyarenottiedtoaspecificdomain,but
generic.However,GRANDMAhasbeendesignedwiththegoalofgesturerecog-
nition,whiletheotherfourapproacheshavebeendesignedforsketches.Ac-
cordingly,GRANDMAreliesonsingle-strokerecognition,whichsuitsgestures,
whiletheotherfourhavemulti-strokerecognizerswhicharemoreconvenient
whendrawingshapes.Allfiveapproachesrelyonon-linerecognition.
LADDER,SkG,InkKitandDSKETCHhavebeendesignedwithdifferent
goals.LADDERisageneral-purposeshaperecognizer,anditsspecialcontri-
butionisthepowerfulspecificationlanguage.SkGandDSKETCHaimatunder-

ARISONCOMP3.6.

43

standingsketchesbasedonsyntaxandsemantics.LADDER,SkG,andDSKETCH
alsoallowforunrestrictedsketching.Finally,InkKitisatoolkitthatprovidesfea-
turesandmethodsforbuildingownsketchingapplications.LADDER,SkGand
DSKETCHhaveincommonthatshapesarespecifiedusingsomeformalism.In
contrast,GRANDMAandInkKitrelyontrainingsamples.
AllowingtheusertodrawfreelyandunrestrictedisfundamentaltoDSKETCH.
AsstatedinSection1.2,wehavemulti-strokerecognitioncapableofautomatic
clusteringandsegmentation.Thismeansthatonestrokemaycontributetodif-
ferentshapes,orseveralstrokesmaycontributetooneshape.Furthermore,low-
levelprocessingofstrokesalsoconsidersambiguityandallowsfordifferentin-
terpretationsofthesamestrokeinparallel(cf.Chapter4).Asmentionedbefore,
GRANDMAandInkKitbothrelyontrainingsamplesfortheirrecognizers,which
indicatesadependencyonthedrawingstyleoftheuserwhocommittedthetrain-
ingdata.However,inthisrespectInkKitiscertainlysuperiortoGRANDMA,
andallowsformoreexibility,mostprominentlyduetomulti-strokerecognition.
SkGreliesontheSATINframeworkforlow-levelrecognition,andiscapableof
constructingshapesfromprimitives,whichallowsformulti-strokerecognition.
However,veryfewdetailsarepublished.
ExceptforGRANDMA,allapproachesarecapableofproducingdomain-
dependentresults.GRANDMA,withitsfocusongestures,obviouslyinterprets
strokesonlyasgestures.Thereisnoneedforanyfurtheroutput.SkGand
DSKETCHsupportthegenerationofoutputbytwofactors.First,asbothap-
proachesrelyonaparser,derivationstructuresaregeneratedwhichexpressthe
contentofthesketch.Second,thesederivationstructuresdescribeonlysyntacti-
callycorrectsketches,incorrectinterpretationsareomitted.Incontrast,LADDER
andInkKitgivelesssupportforoutputgeneration,andonlyprovideprogramming
interfaceswhichcanbeusedtoaccesstherecognizedshapes.
Differencesbetweentheapproachescanalsobeobservedregardingtheissue
ofruntimeperformance.GRANDMAcertainlyisveryfast,whichisalsodocu-
mentedinliterature.TheperceivedperformanceofLADDERisalsoverygood.
Itsrecognizerworksincrementally,whichalsosuggestsagoodperformance.SkG
alsoworksincrementally,butnodetailsarepublishedonactualruntimeperfor-
mance.InkKitsperformanceisalsonotreported.Regardingourownapproach,
performanceisfastaswell,however,notintherangeofGRANDMAandLAD-
DER.Theevaluation(cf.Chapter10)showsthatthisisduetoourrecognizer,
whichdoesnotworkincrementally.Accordingly,forlargersketchescompris-
ingmorestrokes,runtimeincreases.However,asDSKETCHappliesananalysis
stagewhich,exceptforSkG,theothersdonot,performancecannotbecompared
.directly

44

CHAPTER3.RELATEDWORK

DetaileddifferencesbetweenDSKETCHandSkG
Theferencespreareviousintheparagraphsdetails.shoForwthatshapeDSKETrecognition,CHfolloinwsSkGsimilarshapesideasarelikespecifiedSkG.withDif-
thesameformalismasthesubsequentparsingprocess.Thissimplifiesprocessing.
Incontrast,shapespecificationsforDSKETCHaredifferentfromtheformalism
usedtodescribeparsing.Anadvantageofthisisthat,similartoLADDER,our
shapespecificationscanbeunderstoodandwritteneasily.
fromTheLRparserparsersusedforbystringSkGusesgrammars.aneOnthextensionofcontrary,well-knoweusewnahypertechniquesgraphknoparserwn.
Ourparsersolvesambiguitiesautomatically.Therefore,ambiguities(calledcon-
DictsSK,ETcf.CHandSectionSkG6.2is)aretheusemodeledofemeta-rules.xplicitly.WhileAnotherweavoidinterestingsuchdetailrulesinaboutthe
parsercation,ofSkGtheseprunesrulesinsearchtermsofaccordingrecognitiontotworatesmeta-rules.andruntiThemeeffectperformanceoftheisappli-not
reported.

DetaileddifferencesbetweenDSKETCHandLADDER
AnoveralldifferencebetweenourapproachandLADDERisthephilosophyof
thetwoapproaches.LADDERperformsanincremental,eagerrecognition,which
isfastinpractice.Immediatefeedbackaboutrecognizedshapescanbeshownto
theuser.Contextishardlyconsidered,recognitionerrorsduetotheincremental
recognitionmayhappenandareaccepted.Incontrast,inDSKETCHweperform
lazyrecognition.Thisallowsustoavoidrecognitionerrorsastheymayoccur
inLADDER.Accordingly,recognitionstartsfromscratcheachtime,inorderto
notmissanyshapedrawnbytheuser.Context,consideredintheanalysisstage
succeedingrecognition,isveryimportant.Byusingasearchplan,DSKETCH
exploitssub-shapescommontodifferentkindsofshapes;inLADDER,thishas
tobemanuallyspecifiedusingtheinheritancemechanisms.Commontoboth
approachesisthatintersperseddrawingisfullysupported,i.e.,itdoesnotmatter
ifshapesarecompletedbeforeothershapesaredrawn.
UsingtheexampleofNSDsomelimitationsofLADDERcanbeshown,which
DSKETCHdoesnothave.Figure3.4showstwosketcheswhereLADDERdoes
notproducethedesiredresult.In(a),theloopwillnotberecognizedbecauselines
arenotsplit,soitcannotbedeterminediftheshownendpointandlinecoincide.
In(b),ifstatementsarespecifiedasfinal,onlyoneofthethreestatementswillbe
recognized,asinthiscaseprimitivesareremovedfromtherecognitionprocessas
soonasashapeisfoundwhichconsistsoftheseprimitives.InthecaseofNSD,
thisisasevereissue;ouruserstudyhasshownthatnouserrepeatedthestrokes
dissectingtwostatements(orothershapes)fromeachother.Ifthestatementsare

3.6.

ARISONCOMP

45

46

CHAPTER

3.

TEDRELA

ORKW

Chapter4

ocessingeprPr

Thischaptermarksthefirststepintherecognitionstageofprocessingasketch.
Preprocessingisperformedbyasetofindependentpreprocessors,whichare
calledtransformers(cf.Figure1.4).Inputforthetransformersarethestrokes
drawnbytheuser,outputispreprocessedinformationintheformofmodels.In
general,preprocessing(sometimesalsoreferredtoaslow-levelprocessing)isan
importantstepforasketchingsystem.Forseveralreasons,inputstrokesalways
exhibitnoisewhichmustbefiltered.Noiseincreasestheloadonthesystemand,
therefore,processingtime.Additionally,laterrecognitionisimpededbynoise.
Therearedifferentsourcesofnoise.Oneisdigitization;asheetofpaper
whichcontainsadrawingmustbescannedtobedigitized.Here,threeeffects
ifcanitisoccurdra.wnFirst,withthejustonescannedpen,imagesayaisnotpencil.likItelyistovbeerylikelymonochromethattheonly,digitizedeven
imagewillcontainseveralshadesoftheoriginalcolorthepencilhad.Second,
thedustandscanner,othermeaningparticlesthatonthetheywillsurfbeaceofrepresentedthepaperaswillpixelsbeonthecapturedimage.aswellThird,by
thescannedlinesmayhavedifferentwidths,becauseapencilneverhasthesame
widthallthetimewhendrawing.Becauseweassumenoscannedimages,but
anon-linesketchingapproachusingdedicatedhardware,noiseduetodigitization
cannotoccur.However,thereareothersourcesofnoiseaswell.Whendrawing
withastylus,theusercangeneratenoiseaccidentally,byslippingofffromthe
thestylus,hardworbyarecanpressingfailbtouttonstrackonthethemovstylus,ementthusofthegeneratingstylus,difandferenteintroducevents.errorsAlso,
ornoiseinthedata.Becausenoiseduetohardwareorduetotheuserisrather
unlikely,weneglecttheseaspects.Besides,apracticalsystemcansolvethese
issueseasilywithanappropriateuserinterface,providingundo/redofunctions,
xample.eforBesidesnoise,therearefurtherreasonsforpreprocessing,whichapplyfor
DSKETCH.Onesuchreasonistopreparetheinputdatafortherecognitionpro-

47

48

OCESSINGPREPR4.CHAPTER

cessbytransformingitintoaformatorrepresentationmoresuitableforthistask.
Atrade-offbetweenprecisionandamountofdatahastobeagreedon.Aninput
strokeisveryprecisebutalsoratherverbose.Reducingtheamountofdatafor
laterprocessingreducestheprecision,butdecreasestheloadonthesubsequent
steps.processingAnotherreasonforpreprocessingistoapplysomeabstraction.Ingeneral,
losingprecisiondoesnotneedtobeabadthing.Forlaterprocessing,abstracted
(oraggregated)datacanbemuchmoreconvenient.Thechallengeistoapplyas
muchabstractionaspossible,whilenotlosingimportantdetails.Asanexample
considerastrokethatisverystraight;itcanconsequentlyberepresentedbyits
twoendpointsonly(giventhattiminginformationisofnointerest).Thismeans
agreatreductionintheamountofdata,butpreservesallnecessarydetails.
Toconclude,therearethefollowingreasonsforpreprocessing:dealingwith
noise,andgettingridofunnecessaryinformationwhilepreservingessentialin-
formation.Noiseisdiscarded,asdescribedabove.Whatremainsistoapply
abstraction,whichisdescribedinthefollowingsections.Section4.1explains
theoverallconceptandtheideasbehindthepreprocessingarchitecturewepro-
pose.Sections4.2through4.6describehowstrokesarepreprocessedaslines,
arcs,links,circlesandtext.Furtherworkrelevanttothetopicofpreprocessingis
giveninSection4.7.Section4.8summarizesthechapter.

Concept4.1

Asmentionedintheintroductiontothischapter,theinputdatamustbetrans-
formedintoaformatsuitableforlaterprocessing,i.e.,therecognitionstepper-
formedbytheassembler.Thisstepdependsonwhatastrokeissupposedto
isthatrepresent.theHowevpreprocessinger,thisstepinformationdoesnotisnotrecognizeknowncompleteinitially.shapes,Accordinglybut,primitithevideaes
onlyinput,strokwithoutesareanyconteprocessedxt(ortrinformationansformedor)ininterpretationparallelatbysehand.veralTherefore,transformers,the
Fsuchorethatxample,eachastrokpossibleecouldlaterrepresentinterpretationalineisoralink.representedBothinofthethesetransformedinterpretationsdata.
aregeneratedduringpreprocessing,andarestoredinparallelfortheassembler.
straightInSectionlines,1.2arcs,thelinks,fourandtypestext.ofTextprimitiisvesprocessedwedifassumeferentlyhave,andbeenwillbedescribed:cov-
eredlater.Whenaninputstrokeisdrawnbytheuser,itisunknowntothesystem
whichofthethreeprimitivesline,arc,orlinkitissupposedtorepresent.Even
astraightcombinationlineandofansevarceralconnectedprimitivestoistheline.possible,e.g.,Accordinglyastrok,eeachthatinputrepresentsstrokeisa
processedinparallelbythreedifferenttransformers:onetransformerextractsonly

4.1.

CONCEPT

49

50

CHAPTER

4.

PREPROCESSING

LINES4.2.

51

Algorithm1Transformationofastrokes=p1...pnintostraightlines.
1:procedureLINES(s)Thestrokes=p1...pn
2:L←∅Lwillcontainallstraightlinesegments
pa3:←4:b←p21
5:fori∈3...ndo
pc6:i←7:if|abc−180◦|>tanglethen
8:L←L∪{(a,b)}anewstraightlinesegmentisfound
ba9:←ifend10:cb11:←orfend12:13:L←L∪{(a,pn)}preservelaststraightlinesegment
eocedurprend14:

linescouldbeimprovedifthelineswereshorter.However,thisisnotnecessary,
asthereisnoneedtocloselyapproximatethecirclebystraightlines.Itisthearc
modelandthecirclemodelwhicharesupposedtoeventuallymatchthecircle.
Thelinetransformerprocesseseachstrokeindependentlybysplittingitinto
segmentswhicharenearlystraight.Tofindthesamplesofthestrokewherethis
splittingmustoccur,theanglesenclosedbythreesamplesa,b,cofthestrokeare
examined.a,b,careinitializedtothefirstthreesamplesofthestroke.Then,the
angleabciscomparedto180◦.Ifthedifferenceexceedsathresholdtangle=25◦,
astraightlineisfoundfromatob,anda,b,careassignednewvalues.abecomes
b,bbecomescandcbecomesthesubsequentsampleofthestroke.Ifthedifference
oftheanglesdoesnotexceedthethreshold,thenbisreplacedbycandcbecomes
thesubsequentsample.Algorithm1liststhisprocedure1.Finally,thelinemodel
containsasetofstraightlines,representedbytheirendpoints.Notethatthevalue
forthementionedthresholdtangle,asallothervaluesforthresholds,isdetermined
.empiricallyThelinetransformerperformsadditionaltaskswhicharenotshownintheal-
gorithm.Toavoidclutterinthelinemodel,thoselinesegmentswhicharevery
shortarediscarded.Also,thetransformerdiscardsalllinesegmentswhosedirec-
tiondoesnotmatchatleastonelineprimitiveinthespecification,astheselines
willneverbequeriedlater.Forexample,noshapefromtheGUIbuilderusesa
1Notethatitistheoreticallypossibletoconstructastrokeformedlikeaspiralwithincreasing
asradiusonewherestraightthisline,andalgorithmnothingconsiderselse.theHoweverconnection,thisnevbetweenerhappensthefirstinandpractice,lastandsampledoesofthenotstrokmeane
algorithm.theoflimitationa

52

CHAPTER

4.

OCESSINGPREPR

53ARCS4.3.Algorithm2Filteringofsamplesfromastrokes=p1...pnwhicharetooclose
toeachother.Thefirstandlastsamplefromsarepreserved.Thefilteredstroke
returned.is1:functionFILTER(s)Thestrokes=p1...pn
2:R←p1Rwillcontaintheresult
pa3:1←2i4:←5:whilei<ndo
6:ifEUCLIDEANDIST(a,pi)≥tdistthen
7:R←RpiappendpitoR
pa8:i←ifend9:10:i←i+1
whileend11:12:R←Rpnpreservelastsample
Rneturr13:functionend14:

appendpitoR

samplelastepreserv

AsFigure4.4illustrates,eachstrokeisprocessedinthreestepstoidentifythe
arcsitdescribes.AgainfunctionFILTER(Algorithm2)isappliedtothestrokeas
prerequisite.Then,thestrokeissplitatitsinectionpoints,suchthattheresulting
sub-strokesareeachbentcompletelyleftorright,withoutchangesinbetween(cf.
Figure4.4(b)).Straightlinesegmentsinthestrokearefilteredout.Inorderto
decideaboutstraightnessandbending,similartothelinetransformer,eachthree
consecutivesamplesa,b,cof◦thestrokearetaken,andtheenclosedangleabcis
computed.Ifthisangleis180,thestrokeisstraightbetweenaandc;otherwise
itisbenteithertotheleft,ortotheright.
Inthesecondstep,sub-strokesareapproximatedbyarcsinthefollowingway.
Foreachtwoconsecutivesamplesofasub-stroketheangleenclosedwitharefer-
encelineiscomputed.Thereferencelinecanbechosenarbitrarily,butmustbe
thesameforeachangle.Aseachsub-strokeisalwaysbenttoonesideonly,the
changeoftheseanglesismonotone.Then,byexaminingtheencounteredangles
itcanbedeterminedwhichquadrantorquadrantsarecoveredbythesub-stroke.
Anexampleforanarcinquadrant2isillustratedinFigure4.5.Thehorizontal
linewaschosenasreferenceline.Accordingly,anglesbetween90◦and0◦fall
inquadrant2.Thefigureshowsforeachsampleofthestroketheangleenclosed
withthesubsequentsampleandthereferenceline.Itisassumedthattheshown
sub-strokehasbeendrawnclockwise.Itcanbeseenthatthesamplelabeleda
isthefirstofthearcinquadrant2,asitsassignedangleisthefirstbelow90◦.
Likewise,thesamplelabeledbisthelastoneofthisarc,asitsassignedangleis

54

CHAPTER

4.

OCESSINGPREPR

LINKS4.4.

55

thearcnomorethan5◦.Figure4.4(d)showstheresult.Allidentifiedarcsare
thenstoredinthearcmodelbytheirtwoendpointsandthequadrant(1to4)they
to.belong

Links4.4

Alinkisanarbitrarilybentorcurvedconnectionbetweentwopoints.Sincethis
istrueforeverystroke,eachstrokeisconsideredtobealink.Theonlyexceptions
areforstrokesformingnearlyclosedshapeslikecirclesorpolygons,becausethe
twopointsconnectedbythelinkaresupposedtobedifferentfromeachother.
Thislinks,e.g.,approachintersisvectingeryshaftssimpleofandarroefws,ficient.areAeasilydirectandbenefitreliablyisthatdetected,andintersectingnot
approachconfused.alsoThishasallotwwsoaforws:an(i)aunrestrictedstrokemaydrawingcontribstyleutetforosetheveraluser.Hoprimitiwevves,er,notthis
tojustonelink,and(ii)itmaybenecessarytoclusterseveralstrokestomakeone
link.Thefirstawmentionedbecameobviousintheuserstudy.Itfrequentlyhap-
penedthatparticipantsdrewarrowsinonestroke,i.e.,alinkfortheshaftand
straightlinesforthearrowhead.Ifstrokescannotbesplitaccordingly,theeffect
wwhichouldisbeverythatinconusersvwereenient.forcedAsatoalsolution,waysdrastrokwesarroarewsplitshaftsatinthoseaseparatesamplesstrokwheree,
Ftheorthislocalcurvpurpose,atureisvprocedureeryLhigh,INEi.e.,Swhere(Algorithmthe1)strokiseappliedclearlyagain,changeshoweitsver,direction.using
ahere.muchFiguregreater4.6githresholdvesanforextangleemplary,astherearrowisdranownneedinforoneanestrokxacte,whichapproximationisvery
similartotheonesfromtheuserstudy.Thearrowheadismadebystraightlines,
whiletheshaftissupposedtobealink.Consequently,thestrokemustbesplitby
thelinktransformer,inordertoproperlyassignalinktotheshaftonly,leaving
outalgorithmtheheaddoesofthenotarrocheckw.forOfanycourse,theinterpretationheaditself(likeisarroalsow-head)splittwatothistimes,point.asthe
cannotThebesecondsolvedeissuexhaustivmentionedelyinabovreasonablee–time,clusteringbecauseofstroktheestonumberformofalinkcombi-–
nationsheuristicsbetweenmustbestrokesapplied.isFmuchortooeachlartwgeotostrokbeeshaenumeratedvingoneofcompletelytheir.endHencepointsa
closetoeachotherwecombinethesetwo,if(andonlyif)thereisnootherstroke
nearby(cf.Figure4.7).Thisprocessisappliedrecursivelyinordertobeableto
combinemorethanjusttwostrokes.Allothercasesoftwostrokesclosetoeach
itsotherend,likepoints,anendortwopointofaintersectingstrokestrokclosees,toareanothernotstrokcombined.e,butInnotFigureclose4.7to,one(a)isof
notcombinedbecauseitisastrokeformingaclosedshape;(b)isnotcombined

56

CHAPTER

4.

OCESSINGPREPR

4.5.CIRCLES

57

Actually,combiningstrokesisnotperformedbythelinktransformer,butwill
bemodel.doneTheonreasondemandislaterthat,therewhenistheaassemblerconsiderablequerieshighnumberinformationofpossiblefromthecombi-link
benationsqueriedofatstrokall.es(evHence,enwithitisthenotmentionedreasonableresttorictions),precomputemostallofofwhichthesewillpossiblenever
linksinthetransformer,butrathertodosoondemandfromtheassembler.Just
likethelinemodel,inthelinkmodelonlytheendpointsoflinksarestored.Be-
maycausebethecombinedoriginalstrokwhenesarequeriedalsobythestored,itisassemblerpossible.todecidewhethertwolinks

clesCir4.5

circles.CirclesareNevcomposedertheless,ofthefouradditionarcs.ofaTherefore,circlethearctransformertransfisaormerworthwhilealreadyedetectsxten-
sion.Ascirclesarecommontomanydifferentdiagramlanguages(forexample,
fromthesixdiagramlanguagesmentionedinChapter2,fiveusecircles),using
thecircletransformerthereliabilityofpreprocessingstepcanbeincreased.Be-
sides,theadditionofthistransformer(anditsmodel)isanexampleforhowtwo
differenttransformerscanprocessthesameprimitives.
circles.IncontrastBasedtoonthetheotherassumptionstransformers,thata(i)eachfeature-basedcircleisdraapproachwninisexactlysuitableonefor
stroke,andthat(ii)thisstrokedoesnotcontributetoanyotherprimitive,several
featuresofeachstrokecanbecomputedandevaluated.Bothassumptionsholdfor
ofeach(i)andcircle(ii)draiswnthatinthetheusercirclestudyastransformerdescribedmustinneitherSectioncope10.5.withTheseimplicationgmentation
norwithclustering,whichbothposeproblemsforfeature-basedrecognition.The
considered:arefeatureswingfolloLengthlofthestroke.
Centerpointp=(x,y),radiusrandaccumulatedangleγ.Thesefourval-
uesareobtainedbyaparameterestimation(describedbelow).γisdefined
astheanglecomputedbyaccumulatingtheabsolutedifferencebetween
eachthreeconsecutivesamplesofthestrokeand180◦(seeFigure4.8).
Boundingboxb(withheighthandwidthw).
basedFirst,onthethestrokparameterses.Ax,ysimple,randsolutionγofwaouldpossiblebetocirclecomputehavethetoavbeerageestimatedcoor-
dinatesofallsamplesfromstofindxandy.Then,rgetstheaverageEuclidean
distanceofeachsamplefrom(x,y).γcanbecomputedaccordingtoitsdefini-
tion,i.e.,byaccumulatingtheabsolutedifferencebetweeneachthreeconsecutive

58

CHAPTER

4.

PREPROCESSING

59CIRCLES4.5.Algorithm3Transformationofastrokesintoacircle.
2:1:(functionl,x,yC,Ir,RγC,Lh,E(sw))←COMsPUisTEtheFEAinputTUREstrokS(s)e,theresultis(x,y,r)ornil
3:ifnotbcontains(x,y)thenboundingboxcontainscenterofcircle
4:5:endrifeturnnil
6:ifγ<300◦then
nilneturr7:ifend8:9:ifw≤40andh≤40thencheckifthestrokeissmall
10:ifw>3∙horh>3∙wthenboundingboxnottoohighorwide
12:11:endrifeturnnil
◦14:13:lifl←<γ0/.18075∙l∙r∙thenπthelengthstrokeofmustanotperfectbetoocirclelongwithaccu.comparedangletolγ
16:15:endrifeturnnil
18:17:elseifw>2∙horh>2∙wthenthestrokeisnotsmall
20:19:endrifeturnnil
21:l←γ/180◦∙r∙π
22:ifl<0.9∙lthen
nilneturr23:ifend24:25:ifHASSHARPBENDS(s)thenckechedonlyforstrokesnotsmall
27:26:endrifeturnnil
ifend28:29:return(x,y,r)
functionend30:

theyhavetobedistinguishedsomehow.Wedefinethatastrokeissmallifneither
heightdeterminednorwidthempirically).oftheThen,boundingtheboxdecisionexceedawhethervalueagiofven40strok(anothereisacirclethresholdis
madeindicatebythatafunctionstrokCeIRisCaLEcircle,(Algorithmotherwise3),nil.whichIfastrokcomputeseisthefoundtripleto(bex,ay,rcircle,)to
thefeaturesx,yandrareusedtodescribethecircleandare,thus,storedinthe
model.circleInthealgorithm,thefeaturesdescribedabovearecomputedfirst(cf.line2).

60

OCESSINGPREPR4.CHAPTER

Then,evaluationtakesplace.Forsmallcircles,theratiobetweenwidthandheight
oftheboundingboxisusuallynotascloseto1asforlargercircles(cf.line10).
Thesameholdsforthedifferenceoftheactualstrokelengthlandthelengthofa
perfectlyprecisecircularlinewithradiusrandaccumulatedangleγ(cf.line14).
Finally,ifthestrokeisnotsmall,wesearchforsharpbendsinthestroke,whichare
notsupposedtooccurforacircle(cf.line25).Asharpbendisdefined◦asthree
consecutivesamplesofthestrokeenclosingananglelessthan110orgreater
than250◦.AgainfunctionFILTER(Algorithm2)isappliedforthismeasureto
beappliedproperly.Themeasureisnecessarytodistinguishcirclesfromsquares,
whichotherwisearesometimesmisinterpretedascircles,too.Forsmallstrokes,
thismeasuredoesnotyieldvalidresults,asthedescribedangleeasilybecomes
toosharpforthreesamples,eveniftheintentionwastodrawacircle.

extT4.6

Asstatedintheintroductiontothischapter,textishandledcompletelydifferent
fromstrokes.Thismeansthattheuser,whiledrawingthediagram,hastoindicate
whentextisenteredandwhengraphicsaredrawn.Thewaythisindicationisdone
dependsontheuserinterface.Analternativeistoautomaticallyseparatetextfrom
graphics,whichisdonebyaprocessingunitcalledadivider.However,thisisa
verychallengingissuewhichisneitherdiscussednorsolvedinthisthesis,but
tackledinrelatedworksuchas[75,10].Usingadivider,thesystemarchitecture
showninFigure4.1wouldchangetotheoneshowninFigure4.10.Oneway
oranother,themodelswouldcontainthesamedata(giventhatthedividerworks
reliably).Hencethereisnoeffectonsubsequentprocessingsteps.
Manuallyindicatingtheenteringoftexthastheadvantagethatspecialhard-
warecanbeused(e.g.,aregularkeyboard,orThumbscript2),orapproachesthat
requireaspecialGUI(e.g.,anon-screenkeyboard,menu-augmentedsoftkey-
boards[58],Fitaly3,SHARK[104],Quikwriting[78],orCirrin[66]).Itremains
anopenquestionwhatispreferredbyusers,andwhatapproachorapproaches
leadtothemostreliableinput.Afurtherinvestigationoftextinputapproachesfor
sketchingsystemsisgivenin[88].
Sincetextisnotdirectlywrittenonthecanvas,ishastoberenderedusing
somedefaultfont.Textisassumedtobewrittenalwayshorizontally,andsois
thespaceitrequiresassumedtoberectangularandaxis-parallel.Thesizeofthis
rectangledependsonthetext,thefontface,thesizeofthefont,andthefont
style(forexample,italicorbold).Theonlythingthetexttransformertherefore
23seeseehttp://wwwhttp://www.fitaly.com/.thumbscript.com/

4.7.

FUTURE

ORKW

61

62

Summary4.8

PREPR4.CHAPTEROCESSING

Inthischapter,ourapproachtolow-levelprocessinginDSKETCHhasbeende-
parallel.scribed.TheTherekeisynoideaconteisxttoinformatigenerateondifavferentailableatthisinterpretationspointtoofeachdecidestrokabouteina
cessreasonableastrokeaccordinginterpretation.toitsEvoerywnview.transformerIndoingworksso,ontheabest-efinformationfortconbasisvetoyedpro-by
thestrokesgetsabstractedtoacertainextent,whichisaneffectivewaytodeal
withnoiseandimprecision.Eachtransformerisfreetodiscardcompletestrokes
orFpartorofeachstrokofestheifthethreeyhappengraphicaltobeprimitioutsidevesof(lines,itsviearcs,w.links)thereisaninde-
textpendentandonefortransformercircles.(andmodel),Additionalandtheretransformers,aretwoeitherfurtherfornewtransformers,graphicaloneprimi-for
tiveasilyes,.orEachforspecialmodelisshapesupdatedwhichexhiimmediatelybitaaftercomplicatedastrokeisstructure,drawn.canbeintegrated
hasOfbeencourse,illustratedapproachesinChaptertolo3.w-levelExamplesprocessingarePhaaleoSkvebeenetch[76],publishedthebefore,recognizeras
bySezgin[91],andtheSATINframework[52].Thetransformerswehavepre-
infsentedavorinofthisourchaptersolution:areanalternativetothoseapproaches.Therearetwopoints

Thetransformersareveryefficientandtakevirtuallynotime,astheuser
studyshows.Infact,theaveragetimetotransformasinglestrokebyall
transformersrangesbelow0.5ms(cf.Section10.1).

Unlikeconsequenceotheristhatapproaches,eachourtransformertransformerscanarespliteachcompletelystrokedifindependent;ferently,andthe
tenthereforedonotcandoso,butapproximatesplittthehestrokstrokeeatmorethesamepreciselypoints.forOtherallprimitiapproachesves.of-

Nevertheless,theconceptofthepreprocessingstepsallowsforintegratinglow-
levelrecognizersfromothergroupsaswell,bywrappingthemintoadditional
transformers.

5Chapter

Recognition

ofAseverymentionedapproachintoChaptersk1etching.,Inrecognitionourisonearchitecture,oftheshomostwninchallengingFigure1.4,issuesthe
assembleristhecentralcomponentthatperformstheactualrecognition.Based
onsingletheprimiticontentsvesofintothecomplemodelsxobtainedshapes.byTherefore,preprocessing,thetheassemblerassemblerhastoquerycombinesthe
models.Thekeyideaisthattheassemblertreatseverymodelinthesameway.It
hasnospecificinformationonanymodelregardingwhatprimitivesarestoredin
thisThisismodel.crucialtoAccordinglytheinte,thegrationofassemblernewalwaystransformersqueriesandeachmodels,modelasforitarequiresprimitivnoe.
changesintheassembleratall.
TheactualrecognitionprocessisdiscussedinSection5.4.Before,twopre-
requisiteshavetobeexplained.Thefirstishowqueriesoftheassemblertothe
modelslooklike,andhowtheresultstothesequeriesaredetermined.Thisis
istoillustrateddetermineinSectiontheorder5.3.inThewhichotherprimitivprerequisiteesareisthesearchedsearcforhbyplan.theItsassemblerpurpose.
Ontheonehand,thesearchplanguaranteesthatthesingleprimitivesofashape
areconnectedtoeachotherasindicatedbythespecificationoftheshape.On
theprimitiotherveshand,sharedthebydifsearchferentplanshapesdeterminesarethesearchedsearchfororderconjointlyin.suchThisawimproayvthates
performance.ThesearchplanisdiscussedinSection5.2.
suffice.WhenForespecifyingxample,usingshapes,onlytheeprimitixpressivesvitepocannotwerofbeprimitispecifiedvesthatalonethedoeswidthnotof
arectangleshouldbegreaterthanitsheight.Toaddexpressivepower,constraints
areusedinadditiontoprimitives.Section5.1describesconstraints,andhow
shapescanbespecifiedusingtheseconstraintsandprimitives.
Section5.5discussesanapproachtorateshapes.Thisisnecessaryinorder
toargueaboutthequalityofshapes.ThefinaltwoSections5.6and5.7ofthis
chapterdealwithfutureworkandprovideasummary.

63

64

CHAPTER

5.

RECOGNITION

5.1.

CONSTRAINTS

AND

THE

TIONSPECIFICA

OF

SHAPES

65

66

CHAPTER

5.

RECOGNITION

5.2.

SEARCH

PLAN

67

68

CHAPTER

5.

RECOGNITION

5.2.

SEARCH

PLAN

69

70

CHAPTER

5.

RECOGNITION

5.3.QUERYINGTHEMODELS71
Algorithm4ComputationofasearchplanfromasetSofshapes.Returnvalue
.nnodeais1:functionSEARCHPLAN(S)
2:n←NEWNODE
3:n.partial←{s|s∈S,snotyetcompleted}
4:n.complete←{s|s∈S,scompleted}
tialn.parS5:←6:whileS=∅do
7:(p,S)←SELECTBEST(S)selectbestremainingprimitivep
8:n←SEARCHPLAN(S)recursivelycomputechildnode
9:ADDCHILD(n,p,n)addchildnode
10:S←S\S
whileend11:nneturr12:functionend13:

treatedseparately.Anodehastwodisjointsetsthatcannotbothbeempty(cf.the
tableinFigure5.7).Onesetcontainstheshapesforwhichthenoderepresentsa
partialfinding;theothersetcontainstheshapeswhicharecompletelyidentified
atthisnode.Therootnoderepresentsallshapesasapartialfinding,asitdoes
notcontainanyprimitives.ForagivensetofshapesS,thealgorithmfirstselects
thatprimitivepaccordingtothetwocriteriadescribedinthepreviousparagraph
(line7).pmustnothavebeenselectedbefore,asinthiscase,pwouldoccur
twiceinthesearchplan.LetSbethesetofshapesthatsharep.Second,anew
nodeiscreatedrecursivelyfortheshapesinS(line8).Thisnodeisaddedas
achild(line9).Ifthereareothershapeswhichdonotusetheprimitivep,the
processisrepeateduntileverypartialfindingisrepresentedinachildnode.The
functionSEARCHPLANisinitiallycalledwiththesetofallshapesofthediagram
language,andyieldstherootnodeofasearchplan.

ModelstheQuerying5.3Recallthattheassemblerqueriesthemodelsforprimitives.Beforethedetailsof
thisprocessaredescribedindetailinthenextsection,thissectionfirstexplains
whatkindsofqueriesarepossible,andwhattheresultsofthequerieslooklike.
Therearefourkindsofprimitivesqueriedbytheassembler:lines,arcs,links
andtext.Wediscusseachofthemseparately.Whenqueryingforastraightline,
theassembleroptionallyspecifiesastartpoint,anendpoint,andadirection.If
specified,thedirection(assumedfromthestartpointtotheendpoint)servesas
afilterdiscardingalllinesfromtheresultthathaveanotherdirection.Itcanbe

72

CHAPTER

5.

RECOGNITION

SHAPESOFRECOGNITION5.4.

73

thesefromtw(150o,points20)to(once(425,ag25)aintheyieldslinenomodelresult.allowsAlthoughforsomethereisaimprecision),linethisconnectingline
ishorizontal,anddoesnotgodownright.
Queryingthearcmodelisverysimilar.Aqueryforanarcinquadrant1,clock-
wise,startingfrompoint(151,63),yieldsoneresult,namelythearcto(188,127).
Thesamequerywithacounter-clockwiseorientationyieldsnoresult(thearcfrom
(128links,,no64)etoxample(71,is107)shoiswn.notinTheywquadrantorkas1,blines,ut4,excepthenceforitisthenovaliddirection.result).For
point,Finallypol,yline,textispolygon,queriedorinatermscombinationofalocation.thereof(seeThelocationAppendixisAfordescribedexamples,bya
e.g.,AppendixesA.2.2throughA.2.4fortheshapesofNSD).Itisintersectedwith
theboundingboxofeachtext.Iftheresultisnotempty,thetextisreturned,oth-
inerwiseSectionitis7.1not..IfNotenothatlocationthisisconceptspecified,isequieachvtealentxttomaybeattachmentreturned,areas,regardlessdescribedof
whereitiswrittenonthecanvas.

ShapesofRecognition5.4Theassemblerperformstheactualrecognitionofshapes(cf.Figure5.10).Itboth
accessesthemodelsandthesearchplanthathasbeencomputedfromthespeci-
fication.Theassembleryieldstheshapesthatcanbeidentifiedfromthesedata.
Determinedbythesearchplan,theassemblerqueriesthemodelsforprimitives,
ashasbeendescribedintheprevioussections.Theassemblerthencombines
eachresultfromeverymodelwiththecurrentpartialfinding,andcontinuesthe
searchwitheachcombinationindependently.Thedetailsareexplainedbelow.
Asmentionedintheintroductiontothischapter,theassemblertreatseverymodel
equally,andhasnospecificinformationabouttheprimitivescontainedinamodel.
Accordingly,eachmodelisqueriedforeachprimitive.Forexample,eachmodel
isqueriedforstraightlines,althoughonlythelinemodelwillreturnresults.
Notethathavingdifferentindependentmodelsisjustamatterofrepresenta-
tion;conceptuallyitisequivalenttohaveonlyonemodelthatistheunionofthe
independentmodels,i.e.,itcontainsallprimitivesfoundbyeachtransformer.
Thesearchprocessisbasedonstates,whicharecreatedandmanagedbythe
assembler.Eachstatescorrespondstoanodeinthesearchplan,denotedby
s.node.Accordingly,eachstatecontainsa(partial)shapefromthesketchthat
correspondstothe(partial)shapesinitssearchplannode.Thesetofshapesthat
arecompletelyidentifiedinastatesaredenotedbys.complete.Ifsrepresents
onlyapartialstate,s.completeisempty.
Algorithm5describesthesearchprocessperformedbytheassemblerindetail.
ItyieldsthesetShofallshapesthatcanberecognizedfromthemodels(the

74

CHAPTER

5.

RECOGNITION

SHAPESOFRECOGNITION5.4.

75

Algorithm5Recognitionofallshapesfromscratch,asperformedbytheassem-
bler.Recognitionisbasedonthesearchplanandthemodels.Returnvalueisa
setofshapesSh.
1:functionRECOGNIZE
2:Sh←∅Shwillcontaintheresult
3:s←CREATEEMPTYSTATEsisastate
4:St←{s}Stisthesetofstatesthatstillhavetobeprocessed
5:whileSt=∅do
6:s←REMOVEARBITRARYSTATEFROM(St)
7:Sh←Sh∪s.complete
8:forall(p,n)∈GETALLCHILDREN(s.node)do
9:pisaprimitive,nisanode
10:P←QUERYALLMODELSFOR(p)
11:forallp∈Pdo
12:s←CREATESTATE(s,p,n)
13:ifNOHARDCONSTRAINTSVIOLATED(s)then
14:St←St∪{s}
ifend15:orfend16:orfend17:whileend18:19:returnSh
functionend20:

ThetransitioninthesearchplanfromtheroottonodeAistriggeredbya
bythehorizontalfourline.figuresinQueryingFigurethisline5.11(a)leadsthroughtofour(d).resultsTheneinxtthelinetransitionmodel,intheindicatedsearch
firstplandemandshorizontalavlineertical(indicatedlinegoingbyadoinwn,thestartingsearchfromplan).theInleft(b),endnopointsuchoflinetheis
intheimmediatelymodel,hencediscarded.theTheresultsameoftheholdsqueryfor(c)is.Inempty(a),,andsuchathelinepartialcanbefindingfound,is
whichgoingright,endsinstarting(411,at233)this.point.TheneNoxtsuchtransitionlinecanthenbefound,demandssothisapartialhorizontalfindingline
isfound.discardedItendsasinwell.point(112What,221)remain.sTheis(d)second.vHere,erticaltheline,firstvgoingerticalrightlinefromcanthisbe
inpoint,theneleadsxtstep,totwasoalthereternatiisnoves.verticalThefirstlineis(269connecting,232),thiswhichpointtomust(422be,25).discardedThe
otherwell.Thenalternatitheveisstatement(411,is233).fullyIntheidentifiedlaststep,(apartthefromfourthtext,linewhichcanbewouldidentifiednowbeas
queriedbytheassembler),andaddedtotheresultoftheassembler.Thetransitions

76

RECOGNITION5.CHAPTER

tonodesFandLcannotbefoundinthelinemodel.
facthasFinally,alreadyitisbeennecessarymentionedthatlinesinareSectionsplitat4.2,butintersectionsnotexplainedwitheachsofarother..AgThisain
folloidentifiedwinginthe(a)ifsearchpointplaniisinnotFigurepresent5.7,inintheFigure5.12correspondingthelinestatementmodelcannot(inthisbe
example,lettersdenotepoints,insteadofcoordinatesasbefore).Thereasonis
andthatthegoinglineright.fromHocwetovder,isfromidentifiedpointdasnotheverticalonlylinechoiceforconnectingalinethisstartingpointtoinbc
canlinebefromfound,ctosoiistheavalidstatementalternatiisnotve,andrecognized.finally,Bysincei-bintersectingisindeedc-dvandertical,b-e,thethe
identified.isstatementonlyForoption,(b)theandtheresituationstillisisnosimilarline.Ifgoingpointup,iisstartingnotpresent,frompointagaind.Aslineac-dissolution,the
thethispointprojectioninorderoftopointobtaineontwlineolinesc-dmustinstead,benamelycomputed,c-iandandi-dc-d.mustStartingbeinsplitpointat
itheverticallinee-bcanthenbefound,whichcompletesthestatement.

complexityRuntimeLetpbethenumberofallprimitivesinallmodels,letxbethenumberofprimi-
tivesoftheshapeswithmostprimitives,andletcbethenumberofallconstraints
usedforshapes.Notethatallthreevariablesp,xandcareindependentofthe
proposedrecognitionalgorithm;thevalueofpdependsontheactualsketch,and
thevaluesofxandcdependonthespecification.Thentheworst-caseruntime
complexityofthesearchprocesscanberoughlyestimatedbyO(px∙(c+1)),
becauseforeachofthexprimitivesoftheshapespecificationthereareuptop
primitivesfromthesketch,andineachcasetheconstraintsarechecked;allcon-
straintscurrentlysupported(cf.Section5.1)canbecomputedinconstanttime.
Allothershapesinthespecificationhaveequalorfewerprimitivesthanshas,
thustheircomplexityisequalorless.Notethat(c+1)isusedintheestimation,
andnotc,sincetheremaybenoconstraintsspecified.
Althoughthisestimationispolynomial(candxarefixedforagivenlanguage),
inpracticetheruntimeisroughlylinear(cf.Section10.1).Thisisduetoseveral
reasons:Inpractice,thenumberofprimitivesmatchingaqueryismuchsmallerthan
p.Forexample,ifahorizontallineisqueried,lineswithanotherdirection,
arcs,linksandtextarenotconsidered.
Givenashapewithnprimitives,therearen!possibleorderingstoassemble
theshape.Thesearchplanallowsonlyoneofthem,independentofn,

5.4.

RECOGNITION

OF

SHAPES

77

78

CHAPTER

5.

RECOGNITION

5.5.ASSIGNINGRATINGSTOSHAPES

79

shapeisComputationthehigherofisitsratingsrating.isdriAvenshapebyistwomorekeycompleideas.x(i)thethemoremoreprimiticomplevesxandthe
identifyconstraintsmoreitisprimitimadevesof.foraThemorerationalecomplexbehindshape,thisandisthatthatthetheseprimitiassemblerveshasmustto
shapesatisfyismorehighertheconstraints,morewhichpreciselymakitesisthedrawn.shapeHere,morethevideaaluable.isto(ii)rethewardratingpreciseofa
drawingThesestyletwowithrequirementshigherharatings,veseandveraltoconspenalizeequences.sloppydraOnewnshapes.consequenceisthat
twthatotheyshapesareofdrathewnswithamekind,equale.g.,precision,twoarrobecausews,musttheygareainthemadeofsametherating,samegivnum-en
berprecision,ofprimitithatvesonegandainstheconstraints.higherIfratingtwothatarroiswsdraarewnnotmoredrawnpreciselywith.theAnothersame
consequenceisthatratingsarenotnormalizedtosomefixedvalue,asthiswould
(i).violateWspecificationesettheoftheuppershape.boundThisforthecompleratingxityisofadefinedshapeastothetheweightedcomplesumxityofthe

np×wp+nhc×whc+nsc×wsc
wherenpisthenumberofprimitivesoftheshapespecification(withweightwp),
nhcisthenumberofhardconstraints(withweightwhc),andnscisthenumberof
softconstraints(withweightwsc).Allweightsarepositive.Obviously,themore
primitivesorconstraintsashapespecificationexhibits,thegreateritscomplexity
is.Incasethatashapeisdrawnwithperfectprecision,itsratingisequaltoits
specificationcomplexity.Otherwise,theratingisreducedinordertofactorinthe
precision.oflackForthethreeweightswesuggesttosetwp=1.5,whc=1.0andwsc=0.75.
Thisfavorsprimitivesoverconstraintsandhardconstraintsoversoftconstraints.
Giventheseweights,considertheshapesdefinedinAppendixA.1asexamples.
Thearrowhasacomplexityof14.25,becauseitconsistsoffourprimitives(4×
1.5),sixhardconstraints(6×1.0),andthreesoftconstraints(3×.75).Likewise,
thecomplexityoftheplaceis9.0,thecomplexityofthetransitionis7.5,andthe
complexityofthetokenis6.0.
Asmentionedabove,theratingofashapeisequaltoitscomplexityonlyifit
isperfectlydrawnandsatisfieseveryconstraint.However,animprecisedrawing
styleisinevitableinhand-drawing,andtheassemblermustallowforthresholds
toalsorecognizeshapesnotdrawnwithperfectprecision.Accordingly,theactual
ratingofsuchshapesisdecreased,astheimprecisedrawingstyleispenalized.
Thisisdoneinthefollowingway.Theactualratingofashapeiscomputedas
sumofallindividualratingsforallprimitivesandallconstraints.Theseareeach
ratedbytheirweight,ifperfectlysatisfied;otherwisetheirratingisreduced.For

80

RECOGNITION5.CHAPTER

primitives,textandlinksarealwaysratedwithwp,optionaltextthatisnotpresent
with0.Theratingofalineisdecreasedthemorethedirectionofthelinediffers
fromthespecifieddirection,whichcanalwaysbegivenbymappingthepossible
isdirectiondecreasedtoifprecisethevanglealues(e.g.,spannedrightby→the0◦,arcrightisupless→than45◦,.90.◦.,).Fwhichorarcs,maythehappenrating
ofdueatoconstraintimpreciseisdrawing.computedFordependingconstraintsonathesimilarkindofapproachcomparisonistaken.specifiedTheratingfor
thethemoreconsthetraint.respectiThevemoreratingtwo(vgivaluesenbydifwferhc,orwhichwsc)areisdecreased.constrainedIftotwbeovequal,alues
areconstrainedtobenotequal,oronegreaterthantheother(lessthan,resp.),
theratingoftheconstraintisreducedthemorethetwovaluesareequal.Soft
aregiconstraints,veninwhichAppendixarenotC.2.satisfied,areratedby0.Examplesforpracticalratings
Evenifaconstraintispoorlysatisfied,itissatisfiedanyway.Accordingly,
beweequalsuggestbytothecomputefollowingtheactualformula(ratingdisfortheaabsoluteconstraintdifcferencerequiringbetweentwovthealuestwtoo
values,thisthemaximumallowedabsolutedifferencebetweenthetwovalues
suchthattheconstraintisstillsatisfied,andwistheweight,eitherwhcorwsc)
drating(c)=(1−2∙th)×w
Noweveniftheconstraintispoorlysatisfied,theconstraintisstillratedby0.5of
itsweight.Ifitisperfectlysatisfied,itisratedbyitsweight.Nohigherorlower
valuesarepossible.Iftheconstraintcrequirestwovaluestobenotequal,orone
asgreaterbefore,thanwhileorlessthisthanthetheothermaximum,weallosuggestwedtheabsolutefollodifwingferenceformulabetween(dandthewtwareo
valuestostillcountthemasequal)
wifd≥th,
rating(c)=(0.5+d)×wotherwise
th∙2Usinggreaterthisthanorformula,equalatotheconstraintthreshold;isratedotherwibyseitstheweightratingifisthelinearlyactualdecreaseddistancetois
weight.itsof0.5

orkWeFutur5.6Aworthwhileextensiontotheapproachpresentedinthischapterwouldbeto
havetherecognitionprocessworkincrementally.Then,eitherafteranewstroke
isdrawn,orwhenexplicitlyinvokedbyuserinteraction,recognitiondoesnot

YSUMMAR5.7.

81

havetostartfromscratcheachtime,butcanreusepreviouslyidentifiedshapes.
However,manychallengesareinvolvedinthisapproach.First,eachtransformer
andmodelalsomustworkincrementally,andmustbeabletodistinguishbetween
olddatathathasbeenusedforrecognitionbefore,andnewdata,whichhasnot
beenusedsofar.Second,theassemblermusteitherstoreallpartialfindings,
whichisverycostly,astherearemanyingeneral,ortheassemblermustapply
someotherapproachtocompletepartialfindingswhichcouldnotbecompleted
beforeduetomissingprimitives.Third,datacanalsobedeletedfromthedrawing,
andthusfromthemodels,whichmustalsobecopedwith.Theseconsiderations
showthattheincrementalrecognitionapproachoutlinedaboverequiressomenon-
eeping.bookkvialtriAsalternative,orinadditiontothisincrementalapproach,recognitioncould
beparallelized.Allpartialfindingsarerepresentedbysearchstates,whichare
completelyindependentfromeachother.Informaltestingwiththesketchestaken
fromtheuserstudy(cf.Chapter10)hasshownthatthetotalnumberofsearch
statesforonerunoftheassembleristypicallyinthethousands,whiletheaverage
numberofsearchstateswaitingforprocessingisinthehundreds.Accordingly,
processingthesestatesinparallelonamulti-processormachine,whichisvery
commonhardwarenowadays,couldimproveruntimeperformancesignificantly.

Summary5.7

Inthischaptertherecognitionprocesshasbeendiscussedindetail.Theassembler
queriesmodelsforprimitivesbasedonthepreprocessingillustratedinChapter4.
Thecomputedorderoffromthethequeriesisspecification.dictatedBybyusingthethesearchsearchplan,plan,whichandisbyevautomaticallyaluating
tionconstraintsprocessascansoonbeasalldiscardednecessaryassoonasinformationpossible,isandidentified,unnecessarystatesoftheprocessingrecogni-is
avoided.Theassemblerdoesnotdistinguishbetweendifferentmodels,butasks
evgrated.erymodelEachforshapeaisprimitiratedve.basedNewonitstransformerscompleandxity,andmodelsonhocanwbepreciselyeasilyitinte-is
drawn.Shapesdonothavetobeconnected.Iftheyarenot,usingconstraintsit
canbespecifiedhowthesinglepartsarerelatedtoeachother.
tionAn3.3).interestingTherecognizerissueisintheSkGwrelationshiporksbetweenincrementallyDSKEandTCHmustandthusSkGbe(cf.ableSec-to
usercontinuedraws.partiallyTheorderinrecognizedwhichshapesprimitivesarenon-deterministicallyaddedtopartialaccordingshapesistonotwhatfixtheed.
Technically,thisisdoneusinganevolutionofextendedpositionalgrammars
from(XPG)andscratch.aThisrespectiisvedoneparserina.Indeterministiccontrast,inDSmanner;KETCHdetermiwenismrecognizeisachieallvedshapesby

nonterminalsymbols.Thisway,

suitable

RECOGNITION

5.CHAPTER

82

a

search

plan

can

be

directly

transformed

into

a

identifiedtiallyareshapes

ourapproachtothatofpositional

map

to

possible

is

it

,ervweHo

plan.searchthe

].27[grammars

Inthiscase,primitivesaretakenasterminalsymbols,whilepar-

non-linear

.grammar

6Chapter

ocessingostprP

Theresultfromtheassemblerisasetofshapes,whicharecompletelyunrelated
easxactlyyet.Thesuchasetanalysisofstashapes.ge,Rewhichgisardlesstheoftopicthis,oftwoChaptersreasons7makethrougha9,postprocess-requires
ingsteprightaftertheassembler(cf.Figure1.4)valuable.First,thenumberof
tionshapes6.1.canThebelessreducedshapeswithoutthatarelosingpassedcrucialtotheinformation,analysisasstage,ethexplainedlessintimeSec-is
consumed.Thesecondreasonforpostprocessingistodeducesomeextrainfor-
themationanalysis,whichandcanwhichlaterbetouseddiscard.todecideThisiswhichsubjectshapesoftoSectionaddto6.2.thefinalFinallyres,ultbasedof
onthediagramlanguagesdescribedinChapter2,afurtherconfigurationoptionis
ontheidentified,diagramwhichallolanguage,wsforwhichsomeisdiscussedoptimizationinofSectionthe6.3processi.Noteng.thatItsusethisdependschapter
describesthesinglepostprocessingstepsintheorderinwhichtheyareapplied,
soandthetheeremoxvecutionalofoftheduplicatesisconfigurationfirst,theoptiondeductionisthird.ofeThextrachapterinformatiisonissummarizedsecond,
.6.4Sectionin

DuplicatesofElimination6.1

Atypicalresultoftherecognitionapproachexplainedinthepreviouschapter
areactualduplicatesshape,drawni.e.,andtwoorintendedmorebytherecognizeduser.shapesDuplicateswhichoccurrepresentwhenthethesamesame
drationwnpoints.shapeFisalsepositiidentifiedvesmoreoccurthanamongonce,theeachjunctiontimewithpointsslightlymostlydifduetoferentthejunc-line
transformer(Section4.2).Thistransformertendstosplittheinputstrokesmore
inoftenFigurethan6.1(a)necessaryandin(b).orderInsteadnotoftofourmissanstraightimportantlinespoint.whichAnwereexampleintendedisbyshothewn

83

84

CHAPTER

6.

OCESSINGPOSTPR

6.1.ELIMINATIONOFDUPLICATES

85

.othertheofduplicateTodecidewhethertwoshapesareduplicates,threeconditionsarechecked.If
oneisfoundtobesatisfied,weassumeoneofthetwoshapestobeaduplicateof
theother.Then,thatshapeisdiscardedwhichexhibitsthelowerrating,because
thisshapeisassumedtobedrawnwithlessprecision(cf.Section5.5).Although
comparingeachtwoshapesexhibitsO(n2)complexity,wherenisthenumber
ofshapes,thegainintermsofoverallprocessingspeedcertainlywarrantsthis
expenditure,astestsmadewiththeprototypicalimplementationclearlyshow(cf.
).10.3SectionThefirstofthethreeconditionsregardsthedistanceofthepointsofthetwo
shapestoeachother.Thespecificationassignseachpointofashapeaunique
identifier,whetheritisajunctionpointorasimplepoint.Ifthepointsfromboth
shapeswiththesameidentifierareallclosertoeachotherthanacertain,very
smallthreshold(like10pixel,orless),theconditionissatisfied.Thiscondition
mayaccidentallyholdiftwodifferentshapesaredrawnveryclosetoeachother
(cf.Figure6.1(c)).Ifthisfrequentlyhappens,thethresholdmustbedecreased.
Thesecondconditionreferstothestrokesorsub-strokesusedtodrawashape.
Thisconditionholdsifexactlythesamestrokesorsub-strokesareusedforboth
shapes,nomatterhowthesearerelatedtothesingleprimitives.Obviously,it
isnecessarytoknowthosestrokesorsub-strokesusedtodrawashapetode-
cideaboutthiscondition.Thisinformationispreservedbythetransformers,and
reectedinthemodels.Thepostprocessingstepcansubsequentlyaccessthis
informationandcheckwhethertheconditionholds.
Thethirdandfinalconditionmakesuseoffullyconnectedprimitives.Afully
connectedprimitiveisastraightline,anarc,oralinkwherebothendpointsare
junctionpoints,i.e.,bothendpointsareconnectedtootherprimitives.Fromthe
twoexamplesofshapesshowninFigure5.3,thearrowhasnofullyconnected
primitives,aseachlinehasonlyonejunctionpoint.Forthegrid,onlythefour
innerlines(i1-i2,i2-i3,i3-i4,andi4-i1)arefullyconnectedprimitives.Nowifthe
strokesorsub-strokesusedtodrawthefullyconnectedprimitivesofoneofthe
twoshapesareasubsetofthestrokesorsub-strokesusedtodrawthefullycon-
nectedprimitivesoftheothershape,thefirstshapeisregardedasduplicate,andis
removed,nomatterwhichshapehasthehigherrating.Theideabehindthiscon-
ditionisthatfullyconnectedprimitivesaremoresignificantforashape,usually
describingthelocationandextentoftheshapebetter,becausebothendpointsare
notdependingononeprimitiveonly,butseveralprimitives.Accordingly,thereis
lesschoiceintheidentificationoffullyconnectedprimitives.
Evaluatingthesethreeconditionsrevealedthatthefirstandthethirdalready
removemostoftheduplicates,evenifappliedsolely.However,insomecasesit
isthesecondcondition,oracombinationofallthreeconditionsthatremovemore
duplicates,soitisvaluabletoalwaysapplyallofthem.

86

OCESSINGPOSTPR6.CHAPTER

Theremovalofduplicatesdoesnotharmthelateranalysisstageintermsof
losingvaluableinformation.Asoneshapeisalwayskept,andonlyitsduplicates
areremoved,theessentialdataispreserved.

ConictsofIdentification6.2Dependingonthediagramlanguage,onestrokeorsub-strokemayonlycontribute
tooneshapeatthesametime,andnottotwoormore.Consequently,whenever
thesamestrokeorsub-strokeisusedfordifferentshapes,onlyoneoftheshapes
canbecorrect,andtheothersarefalsepositives.Thisistruenomatterwhether
theshapesinquestionhavethesamespecification,ornot.
Manydiagramlanguagesexhibitthedescribedbehavior.Fromthesixexam-
plesgiveninChapter2,itistrueforallbutNassi-Shneidermandiagrams.For
NSDs,almosteachstrokeorsub-strokeissharedbetweentwoshapes,exceptfor
thosestrokesorsub-strokesformingtheveryoutlineofadiagram,andforthe
diagonallinesusedinconditions.Intheotherfivediagramlanguageseachstroke
orsub-strokemayonlybelongtooneshape.
Iftwoshapesarefoundtousethesamestrokeorsub-strokethisiscalleda
conict.Thefinalresultofprocessingasketchhastobefreeofconictingshapes.
Conictscannotbesolvedinthepostprocessingstep,buttheycanbedetectedin
thisstep.Asolutionisnotpossible,becausenocontextinformationisavailable
asyet.Thesolutioncouldonlybebasedonmeta-rules,whichisavoidedasmuch
aspossibleinDSKETCH.Thesubsequentanalysisstageestablishescontextof
shapesandthushasthenecessarymeanstosolvetheconicts.
Asmentioned,theexistenceofconictsdependsonthediagramlanguage.
Hence,thespecificationofadiagramlanguagealsohastodefineifconicts
shouldbedetected,ornot.Ifyes,theresultcanbeexpressedasabinarysym-
metricrelationbetweenshapes,whereeachtupleintherelationreferstotwo
shapes.conicting

6.3SuppressionofShapesContainingOtherShapes
Neshapes,xttoathefurtheroptionconfigurationintroducedintheoption,preveryviousspecifisectionctoregNSDarding,isconictreasonable.sbetweenThe
drawngraphicalnexttoappearanceeachotherof.allManyshapesfalseispositibasedvesonareblocks,recognized,andsuchaseachblockstwoareneigh-also
boringblockscanberecursivelycombinedtoalargerblock.Asforthedupli-
sufcates,ferstheseverelyanalysis.ThestageNSDcanshodealwnwithinthisFigurecircums6.2(c)tance,consistsbutofagnineainshapes:performanceone

6.3.

SUPPRESSION

OF

SHAPES

AININGCONT

THERO

SHAPES

87

88

OCESSINGPOSTPR6.CHAPTER

theretifiestenare.stForatementsthree(cf.consecuti(b)),veforfourstatementsconsecuti(cf.veFigurestatements6.2(a)),20theareassembleridentified.iden-In
general,fornconsecutivestatementsO(n2)statementsareidentified.
sionAgofainthostheeshapessolutionwhichisbasedcompletelyonacontainmeta-rule.anotherTheoptionshape,noallowsmatterforwhatsuppres-the
rightshapesthingare.toThisdowhere,ay,asonlyallfthealsesmallestpositivesshapescombinearetwpreservoored,morewhichsmallerisexactlyshapes.the

Summary6.4

Theneedforapostprocessingstepisshowninthischapter.Itsthreegoalsare
toremoveduplicates,identifyconicts,andsuppressshapescontainingother
shapes.Removalofduplicatesminimizesloadfortheanalysisstage,conicts
canbesolvedbytheanalysisstage,butcanbeidentifiedduringpostprocessing,
andsuppressingofshapescontainingothershapesallowsfortuningtheapproach
forthecharacteristicsofdiagramlanguageslikeNSD.
Eachoftheoptionsisdeducedfromobservationsofdiagramlanguagesand
howDSKETCHworkswiththeselanguages.Oneoftheoptionscontrolstheiden-
tificationofconicts,whiletheotherisbasedonameta-rule,withthegoalof
minimizingtheloadforanalysis.Althoughafairselectionofdiagramlanguages
hasbeenexamined(cf.Chapter2),itcannotbeexcludedthatfurtherdiagram
languagesimposeaneedforfurtheroptions.

7Chapter

Modeler

inAnothisverviechapterwof,isthetheanalysisfirstofstagethreeisshostepswninintheFigureanalysis1.4.Thestageofmodeler,processingdescribeda
sketch.Itcreatesagraphmodelfromtheshapesidentifiedintherecognition
stage.Thetwostepsfollowingthemodelerarethereducerandtheparser,which
areexplainedinthenexttwochapters.
ThecompleteanalysisstageisbasedonDIAGEN[69,68].DIAGENisatool
togenerateeditorsforvisuallanguagesfromspecifications.Infact,thisalsode-
scribesDSKETCH,withtheonlyexceptionthattheeditorsgeneratedbyDIAGEN
donotsupportsketching.Also,asmentionedinSection1.2,thegeneratededitors
providesupportforfree-handediting,whichisnecessaryforthecombinationwith
skgeneratedetching.byAccDIAGordinglyEN,eDIxhibitAGEtheNmakesarchitecturetheperfectshownstartinforFigureDSK7.1E.TCHData.Editorsstruc-
turesareshownasrectangles,processingunitsareshownasroundedboxeswith
aGUIunderlying,thedrshadoawingw,andtool,arrowswherehedenotecanowcreateofacontrol.diagramTheinuseraisprotraditionalvidedwithpoint-
and-clickfashion.Processingthediagramisthensplitintofoursteps:modeler,
reducer,parser,andattributeevaluation.Themodelerfirstcreatesahypergraph
modelrepresentingallcomponentsthediagramconsistsof(whatwerefertoas
shapes),andthespatialrelationsbetweenthecomponents.Resultisthehyper-
graphmodel,whichisthenreduced.Goalofthisstepistodecreasethesizeofthe
ducedmodel,hyperandtographdiscardmodelsome.Thehypersyntacticallygraphinvparseralidcreatespatterns.aThisderivstepationyieldsstructuretherbye-
applyingabottom-upparser,takingtheedgesinthereducedmodelforterminal
symbols.Finally,attributesofthederivationstructurecanbeevaluatedinorderto
producethesemanticrepresentationasfinalresult.Thesesteps,beginningwith
themodeler,arecompletelyadoptedinDSKETCH.Thischapterexplainsthemod-
elerindetail,andthemodificationsthatwerenecessaryinordertofulfilltheneeds
ofDSKETCH.Thenexttwochaptersdosoforthereducerandtheparser(attribute

89

90

CHAPTER

7.

MODELER

7.1.

ATTACHMENT

AREAS

91

92

CHAPTER

7.

MODELER

7.1.

ACHMENTATT

AREAS

93

94

CHAPTER

7.

MODELER

HYPERGRAPHS7.3.

95

clearlymeanttoconnectthetransitiontotheplace,althoughitneithertouchesthe
placeshapesnorwillthenevertransition.beneatlyObviouslyaligned,whensomedrathresholdwnbyhashand.tobeTheallolargerwedthefor,thresholdbecause
is,themoreforgivingthesystemisintermsofsloppilyconnectedshapes.Onthe
otherhand,atokeninsideaplacedoesnotneedanythreshold.Evenwhendrawn
byhand,thetokencanbeeasilyplacedinsidetheplace.Evenmore,ifsome
thresholdisapplied,atokendrawnnexttoaplacewouldalsoberecognizedas
insidetheplace,accordingtotherelationtypecontainsfromabove.Thismeans
isthathaforrmfulsomeandallorelationwsfortypesaawrongthresholdisinterpretation.absolutelyThelaternecessarykind,ofwhilerelationforotherstypeitis
calledrigidtoindicatethatnothresholdisconsidered,whiletheformerkindof
relationtypeisnotrigid.Whetherarelationtypeismeanttoberigidornotcan
tobebeallospecifiedwedasfor,partasofthetheinputiscondition.muchInDmoreIAGENprecise.,nosuchAccordinglylarge,thethresholdsnotionneedof
.necessarynotisrigid

graphsHyper7.3Asmentionedintheintroductiontothischapter,bothshapesandrelationsare
representedinahypergraph[9]inDIAGEN.Ahypergraphislikearegulargraph,
buteachedgemaybeconnectedtoanarbitrarynumberofnodes.Whenspeaking
ofahypergraph,anedgeissaidtovisitnodes.Eachedgeandnodemaybelabeled,
althoughinDIAGENonlyedgesarelabeled,nodesarenot.Thearityofanedge,
i.e.,thenumberofnodesitvisits,dependsonthelabeloftheedge.Inthissense,
aregulargraphcanbeseenasahypergraphwherethearityofeachedgeis2.
Inahypergraph,edgesarecalledhyperedges,andnodesarecalledhypernodes.
Nevertheless,thetermsedge,nodeandgraphwilloftenbeusedifitisclearfrom
thecontextthattheyrefertoahypergraph.Hyperedgeswithanarityof1are
calledunary;hyperedgeswithanarityof2arecalledbinary.
Hypergraphsarewellsuitedforagraphicalrepresentation.Figure7.6shows
ahypergraphconsistingofsevenedgesandfournodes.Nodesareshownasfilled
circles.Edgesareshownasboxeswiththelabeloftheedgewritteninside.Some-
times,asfortheedgelabeledcinthefigure,edgesarenotshownasboxes,butas
polygons.Eachnodevisitedbyanedgeisconnectedtothatedgebyaline,called
atentacle.Todistinguishthenodesvisitedbyanedge,thetentaclesarenumbered.
Forunaryedges,thisisnotnecessary.Edgesandnodesmaybegivenaunique
nametodistinguishthemfromotheredgesandnodes.Inthecaseofnodes,the
nameiswrittennexttothenode.Inthecaseofedges,thenameiswritteninside
theedge,separatedfromthelabelbyacolon,e.g.n1:a.Forbinaryedgesthereis
aspecialnotation.Theycanbedrawnasboldarrowsfromthefirstvisitednode

96

CHAPTER

7.

MODELER

7.4.CREATINGTHEHYPERGRAPHMODEL

97

ai,1≤i≤niseitherapoint,apolyline,orapolygon.Let{b1,...,bj,...,bm}
betheconstituentsofattachmentareab.Thenthedistancebetweenaandbisthe
minimumofalldistancesbetweeneachaiandeachbj,so
dist(a,b):=min{dist(ai,bj)|1≤i≤n∧1≤j≤m}
Points,polylinesandpolygonscanallbeseenas(possiblyinfinite)setsof
points.ThedistancebetweenaiandbjthenistheminimumofallEuclidean
distancesbetweeneachtwopointsfromthesetwosets,so
dist(ai,bj):=min{s−t|s∈ai,t∈bj}
Usingalgorithmicgeometry,dist(ai,bj)canbecomputed.
ForthecreationoftheHM,themodelerrepresentseachshapeasedgelabeled
withthenameoftheshape,e.g.,placeortransitioninthecaseofPetrinets.These
edgesarecalledshapeedges.Allattachmentareasofallshapesarerepresentedby
auniquenodeeach.Eachshapeedgevisitsexactlythosenodeswhichrepresent
itsattachmentareas,andthenodesarevisitedintheorderinwhichtheattachment
areasarespecifiedfortheshape.Asaresult,eachnodeisvisitedbyexactlyone
shapeedgeintheHM.
Relationsbetweenshapesarerepresentedasbinaryedges,whicharecalled
relationedges.Thelabelofthecorrespondingrelationtypeisalsousedaslabel
fortherelationedge.Inthegraphicalnotation,thespecialnotationwiththebold
arrowsisusedtorepresentrelationedges.Relationedgesalwaysvisitthetwo
nodesrepresentingtheattachmentareaswhicharerelated.Theattachmentarea
whichisspecifiedfirstfortherelationtypeisvisitedfirst,too.Intheexample
fromSection7.2theattachedTorelationalwaysvisitsthenoderepresentingthe
objectareafirstandthenoderepresentingthearrowEndareasecond.
AdrawingofaPetrinetwithonetransition,twoplaces,twoarrowsandone
tokenisshowninFigure7.7(a),alongwithtwoHMs,giventhatthereareno
duplicates.ThefirstHM(b)istheonethatisactuallyintended.Thesixshapes
fromthedrawingarerepresentedbyoneshapeedgeeach,andfiverelationedges
attachthetwoarrowstotheirsourcesandtargets,andthetokeninsidetheleft
place.NotethatthedirectionofthearrowsinthedrawingcanbeseenintheHM
bythenumberingofthetentacles.Thesourceofthearrowsisalwaysnumbered
with1,thetargetwith2.
However,becauseacircleisdefinedastheshapeforbothaplaceandatoken,
fromthethreecirclesinthedrawingthreeplacesandthreetokensarerecognized,
andmustberepresentedintheactualmodel(c).HM(b)isasubsetof(c);itisstill
valid,butgrayedouttoputemphasisontheextrainformation.Thedashedlines
indicatetheconictswhichwerefoundinthepostprocessingstep,becauseatoken
andaplacerecognizedfromthesamecircleusethesamestroke(cf.Section6.2).

98

CHAPTER

7.

MODELER

YSUMMAR7.5.

99

Twoshapeedgesarecalledconictingiftheshapestheyrepresenthaveaconict.
Thiscircumstanceisalwaysshownbydashedlines.
Asmoreshapesarefound,themodeleralsoidentifiesmorerelationsbetween
those.Whatsurprisesinitially,butisneverthelesscorrect,isthataplacealways
containsthetokenwhichisrecognizedfromthesamestroke,althoughtherespec-
tiveshapeedgesareconicting.Whileshowninthefigureforthesakeofclarity,
themodeleractuallydoesnotregardrelationsbetweenconictingshapes,and
doesnotcreaterespectiverelationedgesintheHMforthoserelations.Recallthat
aconictbetweenshapesmeansthatonlyoneofthemcanbecorrect,andoneis
definitelyfalse,sorelationsareofnointerestbetweenconictingshapes.Allthe
extrainformationin(c)isnotintendedandwillbedealtwithinthenexttwosteps
ofanalysis,thereducerandtheparser.
Shapeedgesareattributedbasedontheshapestheyrepresent.Foreachtext
primitiveintheshape(definedinthespecification),anattributeisgeneratedau-
tomatically,withthenameofthetextasnameoftheattribute,andtheactualtext
asvalueoftheattribute.Thesameisdonefortheratingoftheshape,whichis
representedasanattributenamedrating.Otherattributescannotbegenerated
automatically,buthavetobespecified.Theyarealwaysbasedoncomputations
onthe(junction)pointsoftheshape.Takeaplace,forexample,wherecenter
andradiuscanbecomputedandstoredasattributesoftherespectiveshapeedges.
Theseattributescanthenbeusedbythereducerandtheparser.
Themodelerasdescribedinthissectiondiffersonlyindetailsfromtheorigi-
nalDIAGENmodeler.Ourapplicationofthemodeleradditionallyconsidersde-
formedattachmentareasandconictsbetweenshapes,andautomaticallyadds
attributesrepresentingthevaluesoftextprimitivesandtherating.

Summary7.5

Basedonattachmentareasofshapes,andrelationtypesspecifiedbetweenthese,
themodelercreatesahypergraphmodelcalledHM.Thismodelisusedbythe
subsequentprocessingstepstocompleteanalysis.IntheHM,eachshapeisrepre-
sentedasashapeedge,andeachrelationisrepresentedasabinaryrelationedge.
Theidentificationofrelationsdependsonthekindofattachmentareas,whichcan
beacombinationofpoints,polylinesandpolygons.Relationtypescanhavean
optionalcondition.Usingthisconditionitcanbespecified,forexample,whether
arelationtypeisrigidornot,i.e.,whetherathresholdmaybeallowedforthe
identificationofanactualrelation.ConictsarealsorepresentedintheHM,as
wellasattributes,whichcanbeattachedtoedges.Themodelerassuresthatno
relationbetweenconictingedgesisrepresentedintheHM.
ComparedtotheoriginalmodelerfoundinDIAGEN,DSKETCHmakesthe

100

MODELER7.CHAPTER

followingadditionsandchanges(allotheraspectsareleftunchanged):attach-

mentareasmaybedeformedinDSKETCH,alargerthresholdisappliedforthe

identificationofrelations,relationtypesmayberigid,conictsareconsidered,

andsomeattributesandtheirvaluesarecomputedandaddedautomatically.This

thethatmeans

types,relation

DIAGEN.

notionofattachmentareas,relations,relation

and

using

a

hgraphyper

representation

evha

forconditionstypes,

already

been

part

of

8Chapter

Reducer

Inthesecondstepoftheanalysisstage,theHMyieldedbythemodelerisreduced
tothereducedhypergraphmodel(RHM).TheRHMisthenprocessedbythe
parserasfinalstepintheanalysisstage,asshowninFigure1.4.Theparseris
discussedinthenextchapter.
Theneedforareducer,explainedinthischapter,stemsfromtwoconsidera-
tions:(i)amodelwithlessnodesandedgescanbeexpectedtobeprocessedmore
efficiently,and(ii)theremaybesyntacticallyinvalidpatternswhichcanbeeasily
identifiedandremoved.Ofcourse,byremovinginvalidpatterns,thesizeofthe
graphdecreasesautomatically.FurthermorethestructureoftheHMisgenericin
thateachedgeiseitherashapeedgeorarelationedge,nomatterwhatthedomain
is.Usingspecificknowledgeofthedomain,amorecompactrepresentationofthe
HMcanbeachieved.ThestructureoftheRHMisnolongergeneric,butdepends
domain.theonThereductionprocessisguidedbyreductionrules.Thesearepartofthe
specificationofadiagramlanguage.Becausetheapplicationofreductionrules
isrelatedtographtransformation,Section8.1givesabriefintroductionintothis
topicfirst.Then,Section8.2explainsreductionrulesandtheirapplicationin
detail.InSection8.3someissuesareinvestigatedthatareemergingfromour
applicationoftheDIAGENsystemtosketching.Aquickglanceatfutureworkis
giveninSection8.4.Finally,Section8.5summarizesthechapter.

ormationransfTGraph8.1GraphtransformationmeanstomodifyagivengraphGbytheapplicationof
graphtransformationrules.Inourcase,aswellasinDIAGENs,wedealwith
hypergraphs,whichhavebeenintroducedinSection7.3.Agraphtransformation
ruleisgivenbyaleft-handside(LHS)Landaright-handside(RHS)R,bothof

101

102

CHAPTER

8.

REDUCER

ULESRREDUCTION8.2.

applied.areruleswhich

103

RulesReduction8.2Theruleapplicationperformedbythereducerisdifferentfromthegeneralap-
proachtographtransformationdescribedintheprevioussection.Reductionrules
alsohaveanLHSandRHS(andmore,seebelow),andmatchesfortheLHSare
searchedforintheHM,buttheHMisnotmodifiedbythereducer.Instead,a
differentmodel,thereducedhypergraphmodel(RHM)ismodified.Initially,it
isempty.ForeachmatchofanLHSintheHMallobjectsinthecorrespond-
ingRHSareaddedtotheRHM.TheeffectisthatthesameobjectintheHM
canbematchedbydifferentLHSs,evenifitisnotinthecorrespondingRHSs.
Thiswouldnotbepossiblewithgraphtransformationasdescribedintheprevious
section.Also,noobjectiseverdeletedinthisprocess.Anexampleisshownin
Figure8.2.WeassumethesameruleasinFigure8.1,withtheexceptionthatthe
nodenamedznowisdifferentinLandR.TherearetwomatchesfortheLHSof
theruleintheHM.TheRHMshowninFigure8.2comprisesallobjectsfromthe
respectiveRHSsRandR.Althoughruleapplicationsareindependentofeach
other,edgesx’andx”areequalintheRHM,becausetheyoccurbothintheLHS
andtheRHSoftherule,andbecausetheyarematchedbythesameedgeinthe
HM.Asimilarobservationholdsfornodesy’andy”,sothesetwoarealsoequal
intheHM.Theedgesnamedd’andd”,andthetwouniquenodestheyvisit,only
occurintheRHSsRandRoftheruleapplications,butnotintheLHSs,sothey
arenotequalintheRHM.See[68]foradetaileddescriptionofthesemanticsof
theDIAGENreducer.
Thereducerappliesreductionrulesinthedescribedwayforeachmatchofan
LHSofareductionrule.AsthenumberofnodesandedgesintheHMisfinite,
andthenumberofreductionrulesisalsofinite,thisprocesscertainlyterminates.
Notethattheparser(cf.Chapter9)workswiththeRHMonly,soanynecessary
informationwhichisnottransformedbyasuitableruleislost.Byconvention,
labelsusedfortheedgesintheRHMaredifferentfromthelabelsusedforedges
.HMtheinAreductionruleconsistsoffiveparts,(i)anLHS,(ii)aRHS,(iii)anoptional
condition,(iv)anoptionalaction,and(iv)a(possiblyempty)setofnegativeap-
plicationconditions(NACs).(i)and(ii)havebeendescribedabove.Ifamatch
foranLHSisidentified,theruleisapplied,andtheaction(iv)isprocessed,if
thereisone.ActionsareusedtosetattributesoftheedgesintheRHS.Ifthere
isacondition(iii),itmusthold;otherwisetheruleisnotapplied.Finally,rules
mayhaveattachedoneormoreNACs,whereeachmayhaveanowncondition.A
NACisagainagraph,anditrestrictstheapplicationofarule.Ifamatchforthe

104

CHAPTER

8.

REDUCER

8.2.

REDUCTION

ULESR

105

106

CHAPTER

8.

REDUCER

8.3.

CONFLICTS

AND

NEGATIVE

TIONAPPLICA

CONDITIONS

107

108

CHAPTER

8.

REDUCER

8.3.CONFLICTSANDNEGATIVEAPPLICATIONCONDITIONS109

processeddifferently.Insteadofprohibitingtheapplicationofareductionruleif
aNACismatched,therulehastobeappliedanyway.Inordertonotrenderthe
NACsuseless,respectiveinformationaboutthematchedNAChastobeaddedto
theRHM.Thisinformationcanbeexpressedbyconicts,whichisshownbelow.
ThedesiredresultofthischangedbehaviorofNACsisshownin8.6(d)(notethat
thereis,for(c)aswellasfor(d),nottokenedgegenerated,asintheHMin(b)
thetokenedgeconictswiththeplaceedge,whichmustnotbethecasefora
matchoftheLHS,asdiscussedabove).
ConictsintheRHM,liketheoneshowninFigure8.6(d),mustbederived
automaticallyfromsatisfiedNACs.Informallyspeaking,ifedgesmatchaNAC
inoneapplicationofareductionrule,andmatchanLHSintheapplicationof
anotherrule,thenthereisaconictintheRHMbetweentheedgesaddedfrom
bothrulesRHSs.IntheexamplefromFigure8.6(b)thereweretwoapplications
ofreductionruleswhereaNACwasmatched.WiththechangedbehaviorofNACs
thefollowinghappens.TherulefromFigure8.3(a)isappliedwhichreducesthe
placeptoanedgelabeledtplace,namedp’inthefigure.ThetouchTPrelation
andtransitiontsatisfyaNACforthisapplication(cf.Figure8.6(e)).Thesituation
isverysimilarfortheotherrulethatisapplied,theonefromFigure8.3(b).It
reducesthetransitionttoanedgelabeledttrans,namedt’inthefigure.The
touchTPrelationandplacepsatisfyaNACforthisapplication.Followingthe
informalstatementmadeinthebeginningofthisparagraph,bothedgest’andp’
musthaveaconictintheRHM,andthisisthecaseshowninFigure8.6(d).
InbothruleapplicationsthetouchTPrelationedgewasnecessarytomatcha
NAC.However,thisedgeisnotinthematchforanLHSofoneoftherules.Still,
aconictemergesintheRHM.Accordingly,relationedgesarenotrelevantwhen
computingconictsintheRHM,onlyshapeedgesare.
Inthegeneralcasetherecanbemorethanjustoneshapeedgeinthematchfor
anLHSandNAC.Then,itismoredifficulttodetermineaconictintheRHM.To
expressthiscircumstanceprecisely(andinpreparationofthenextchapterabout
theparser),twoadditionalattributesarerequiredforedgesaddedtotheRHM,
theattributesshapeedgesandnacs.Thevaluesoftheseattributesaresetbased
ontheruleapplications.Theyworkinthefollowingway.Lettherebearule
whererapplicationL={l1,l2,...}isthesetofedgesinthematchfortheLHSofr
R={r1,r2,...}isthesetofedgesinthematchfortheRHSofr
A={A1,A2,...}isthesetofallmatchesofallNACsofr
whereeachAi∈AisthesetofalledgesinonematchofoneNACofr

110

CHAPTERREDUCER8.

Inordertosimplifythelaterdefinitionofconictsafunctionshapeisrequired.
LetSbeasetofedgesfromtheHM.Then
shape(S):={s|s∈S∧sisashapeedge}
denotesthatsubsetofScontainingallshapeedgesinS.Thenforallri∈Rthe
valuesofthetwonewattributesaresetasfollows.
ri.shapeedges=shape(L)
ri.nacs={shape(A1),shape(A2),...}
ForanedgeeintheRHMbothattributesdescribewhichshapeedgeswerere-
quiredtocreatee,andwhichothercombinationsofshapeedgeswereactually
supposedtopreventthis.Usingtheseattributes,conictsintheRHMcanfinally
bedefined.Lettherebetwoedgeseande’intheRHM.Then
eande’areconicting⇔
(∃N∈e.nacs:N⊆e’.shapeedges)∨(∃N∈e’.nacs:N⊆e.shapeedges)
ThelastissuediscussedinthissectionagainreferstoconictsintheHM.In
thefollowingitisassumedthatthedifferenttouchXXrelationtypesintroduced
inSection8.2areleftoutfromthespecification,aswellasallNACsrequiring
theserelationtypes.Giventhatbothatransitionandaplace(atoken,respec-
tively)arerecognizedinthesketchshowninFigure8.7(a),themodelercreates
theHMshowninFigure8.7(b).BecausetherearenoNACsforthereduction
rules,theconictingedgespandtarenowvalidmatchesforLHSsofreduction
rules,resultinginatplaceedgeandattransedgeintheRHM.Indoingso,
theoriginalconictfromtheHMwouldbelost(cf.Figure8.7(c)).Consequently,
theoriginalconictfromtheHMmustberepresentedintheRHM,andagainthis
canbeaccomplishedwithconictsintheRHM(cf.Figure8.7(d)).Informally
speaking,ifthereisamatchfortheLHSinanapplicationofareductionrule,
andedgesconictingwiththeedgesfromthismatcharethemselvesinamatch
fortheLHSintheapplicationofanotherrule,thenthereisaconictintheRHM
betweentheedgesaddedfrombothrulesRHS.Usingtheconceptestablished
above,thiscaneasilybeexpressedwiththeadditionalattributenacsdefinedfor
edgesintheRHM.Asbefore,lettherebearuleapplicationrwhere
L={l1,l2,...}isthesetofedgesinthematchfortheLHSofr
R={r1,r2,...}isthesetofedgesinthematchfortheRHSofr
A={A1,A2,...}isthesetofallmatchesofallNACsofr

8.3.

CONFLICTS

AND

TIVENEGA

TIONAPPLICA

CONDITIONS

111

112

REDUCER8.CHAPTER

theratingofanedgetintheRHMas
rating(t):={rating(e)|e∈t.shapeedges}
NACs,conditionsandrelationedgesdonotinuencetheratingoft.

orkWeFutur8.4

InterpretingNACsinawaythattheydonotpreventapplicationofreductionrules,
buthaveextrainformationgeneratedintotheRHMasexplainedinSection8.3,
hasRHMproareventoconsideredbevbyaluabletheforparserDSKtoETCH.computeTheonlyconictssyntacticallywhicharevalidaddedderitovationthe
structures.However,regulardiagrameditorsnotbasedonsketching,butontra-
ditionaluserinterfaces,mayalsobenefitfromthischangedinterpretation.The
DIAGENsystemisanexample.TheactualgainspossiblebyinterpretingNACs
difshowferentlymorehaveprecisetobeerrorinvestigmessagesated.Aincasepossibleofbenefitsyntacticallymaybethaterroneousthesystemdiagrams.could

8.5Summary

BasedontheHMcreatedbythemodeler,thereducercreatestheRHM.Itis
usuallysmallerthanitspredecessorintermsofnumberofedgesandnodes.This
allowsforamoreefficientparsing.InvalidpatternsintheHMareignoredbythe
reducer,anddonothavetobetakenintoaccountbytheparser.Thestructure
oftheHMisnolongerdomain-independentastheHMwas,butdependsonthe
domain.Thereducedhypergraphcontainsinformationaboutconictsbetweenedges.
Thisinformationisgeneratedeitherfromconictsbetweenedgesofdifferent
matchesintheHM,orbytheapplicationofNACs.ThekeyideaofNACsis
toapplyrulesevenifmatchesforNACswouldactuallypreventthis.Then,the
parsercanusetheidentifiedconictswhenprocessingtheRHM.

9Chapter

Parser

TheRHMfinal(cf.stepFigurein1.4the).Thisprocessingallowsofabothforhand-drawncheckingdiagramtheissyntaxtheoftheparsingofdiagramthe
andforgeneratingaderivationstructurewhichcanthenbeusedtodeterminethe
thesemanticsedgesinofthetheRHMdiagram.asterminalTheappliedsymbols.parserForisthisareasonbottom-uptheparsernamesofwhichalledgestreats
intheRHMstart,byconvention,withttoindicatetheirrole.Accordingtothe
grammaranditsproductionrulesgiveninthespecification,theparsertriesto
dradeducewingthecanstartbeevsymbolaluatedofthebasedgraonmmarthe.deriIfvthisationsucceeds,structure.theIfsemanticsdeductionofofthethe
startsymbolisnotpossible,nosemanticscanbecomputed,andthedrawingis
foundtobeincorrect.Theparserworksonabest-effortbasis.Ifitisnotpossible
todeducethestartsymbolusingallterminalsymbols,asubsetisconsidered,while
theremainingsymbolsareignored.Thesubsetischosenbasedontheratingsof
theeitheraterminaltree,orasymbols.directedTheacderiyclicvationgraph(DstructureAG).is,dependingontheproductions,
TheparserworkssimilartoaCocke-Younger-Kasami(CYK)parser[1]for
stringgrammars.Consequently,thehypergraphgrammarmustbetransformed
intoChomskynormalform(CNF).Theconsequencesofthisapproachareinves-
tigatedinSection9.1.Asstatedinthepreviouschapter,theparsermustregardthe
conictsfoundbetweenedgesintheRHM.Thisisnecessaryforeverydeduction
isstep,toandforbiddefinesthethedeductiondifofferencenontetotherminaloriginalsymbolsDIAGifENthisinvapproach.olvesTheusingbasicconict-idea
ingterminalsymbols.Thedetaileddiscussionofthisideaissplitaccordingto
thedifferentkindsofproductionrules,andcanbefoundinSections9.2through
9.4.AlargerexampleillustratingtheinterplayoftherulesisgiveninSection9.5.
SemanticsbasedonattributeevaluationareexplainedinSection9.6,alongwith
anillustrationofwhichdiagramischosenifthereisaselectionofseveralpossible
diagrams.Finally,Section9.7summarizesthechapter.

113

114

ARSERP9.CHAPTER

ProductionruleshaveanLHSandanRHS.Inthefollowingwesaythat
productionrulesareapplied.Theapplicationofaproductionruleisaproduction.
TheLHSofaproduction(rule)issaidtobederivedintotheRHS,ortheLHSis
saidtobededucedfromtheRHS,whichmeansthesame,butreectsbetterthat
bottom-up.orkswparserthe

RulesoductionPr9.1

ACYKparserallowsforparsingstringsaccordingtoacontext-freestringgram-
formar.conteAsaxt-freepremise,thegrammarsifgrammarandmustonlyifbetheemptytransformedstringintoisCNFnot,inwhicthehislanguagepossibleof
thegrammar.DIAGENadoptsthisapproach,andallowsforparsingcontext-free
diagramlanguagessimilartoCYK.Thedifferenceliesintherelationbetween
terminalsymbols.Instringgrammars,terminalsymbolsaregivenasasequence,
eachhavingonepredecessor(exceptforthefirstone),andonesuccessor(except
foredges),thedolastnotone).formInadiagramsequence.Eachlanguages,terminalterminalsymbolsymbolsisrelated(retopresentedafixedashnumberyper-
ofotherterminalsymbolsbyvisitingthesamenodes(theactualnumberdepends
onthelabeloftheterminalsymbol).Itisnotmeaningfultospeakofapredecessor
orasuccessorinthiscase.
Ashasbeenshownin[68],context-freehypergraphgrammarscanalsobe
meanstransformedthatthereintoareCNFonl,yandtwothedifferentCYKkindsapproachofcanproductionbeappliedrulestobesimilarly.considered:This

Anonterminalsymbolthatisderivedintotwononterminalsymbols(anon-
terminalproductionrule,abbreviatedNPR).

Anonterminalsymbolthatisderivedintoaterminalsymbol(aterminal
productionrule,abbreviatedTPR).

Weomitruleswherethestartsymbolisderivedintotheemptydiagram.The
productionrulesforPetrinetsareshowninFigure9.1,beforethetransformation
toCNF.Herebyitisassumedthattokensarerepresentedexplicitlybyedgesin
theRHM(asinFigure8.3).Productionrulesforarrowsarenotdiscussednow,
.wbeloutbEdgesfromtheRHMarecalledterminalsinthefollowing.Nonterminalsym-
bols,whicharehyperedgesaswell,arecallednonterminals.Thelabelsofnon-
terminalsbeginwithanuppercaseletter,againbyconvention.Furthermore,Fig-
ure9.1showsnonterminalsymbolsasroundedrectangles,andsoallfollowing
do.willfigures

9.1.

ODUCTIONPR

ULESR

115

116

CHAPTER

9.

ARSERP

9.1.

ODUCTIONPR

ULESR

117

118

ARSERP9.CHAPTER

9.2TerminalandNonterminalProductionRules

Inthissectionandthefollowingtwoitisdiscussedhowconictsaretreatedby
theparser.Firstsomedefinitionsarerequired.Twonon-emptysetsAandB
ofterminalsymbolsaresaidtobeconictingortohaveaconictifthereisa
terminalinAthatconictswithaterminalinB.Furthermore,eachterminalor
nonterminaleisassignedasetofterminals,referredtoasterm(e).Foraterminal
ewedefineterm(e):={e},foranonterminalewedefinethatterm(e)contains
exactlythoseterminalswhicharederivedfromeinoneormoreproductions.
Finally,twoterminalsornonterminalseande’areconictingifterm(e)and
conicting.arem(e’)terThegeneralprinciplewhichmustholdforallkindsofproductionrulesforthe
deductionofnonterminalsisthefollowing:nononterminalmustbededucedfrom
twoconictingsymbolsinthematchforRHSofaproductionrule.Thedirect
consequenceofthisrequirementisthateverynonterminalisalwaysderivedinto
asetofterminals,wherenotwoterminalsinthesetareconicting.Hence,this
alsoholdsforthestartsymbol,whichmeansthatindeedonlylegaldiagramsare
derivedfromastartsymbol,i.e.,diagramswithoutconicts.Theonlyconicts
thatmayoccur(anddoinpractice)arethosebetweenterminalswhicharenot
derivedfromthesamenonterminal.
Forterminalandnonterminalproductionrules(TPRsandNPRs)thesituation
issimple.ATPRmayalwaysbeappliedifitsconditionholds.Asthereisonly
oneedgeintheRHSoftherule,noconictscanarise.
ForNPRswithtwononterminalsrandr’intheRHS,theconditionoftherule
musthold,andrandr’mustnotbeconicting.Thiscanbecheckedeasily,given
thatterm(r)andterm(r’)areknown,whichisjustamatterofbookkeeping:Let
lbethenonterminalintheLHSoftheproductionrulederivingrandr’.Then
term(l)isdefinedastheunionofterm(r)andterm(r’).ForTPRswithterminal
eintheRHS,wherelisagainthenonterminalintheLHS,term(l)isgivenby
.m(e)terForNPRs,thereisanotherissuewhichmustbechecked.Forthetwonon-
terminalsrandr’intheRHSofanNPR,term(r)andterm(r’)mustbedisjoint,
becausenoterminalmustbederivedfromtwodifferentnonterminals.Thiscon-
ditionisknownfromstringgrammarsaswell.Therefore,thenotionofaconict
betweennonterminalsisextended,andtwononterminalsrandr’arecalledcon-
ictingifeitherterm(r)andterm(r’)arenotdisjoint,orifterm(r)andterm(r’)
conicting.are

9.3.SETPRODUCTIONRULES

RulesoductionPrSet9.3

119

Asdescribedbefore,asetproductionrule(SPR)derivesanonterminalintheLHS
toanunorderedsetof(non)terminalsintheRHS[70].EachedgeintheRHShas
thesamelabeland,ifspecified,visitscertainnodes.Aminimumnumberofedges
requiredinthesetcanbespecified,whichpreventsderivationoftheLHSifthis
numberisnotsatisfied.Likeallotherproductionrules,asetproductionrulemay
alsohaveacondition.
DeductionofanSPRissimilartothatofanonterminalproductionrule.The
parseridentifiesalledgesmatchingtheRHSoftheSPR.Ifthenumberofthese
edgesexceedstherequiredminimum,andiftheconditionoftheruleholds,the
rulemaybeapplied.Asshownfornonterminalproductionrulesintheprevious
section,notwononterminalsmaybededucediftheyareconicting.Thiscrucial
conditionmustbesatisfiedaswellwhenapplyinganSPR.Theconsequence
isthatofeachtwoconictingedgesinthesetintheRHS,onemustbeleftout.
However,ingeneraltherearefurtherdeductionsnecessarybeforethestartsymbol
isreached.Leavingoutthewrongoneofthetwoedgescanleadtounforeseeable
steps.latertheinconsequencesAsanexampletakeaPetrinetwithseveralplaces,twoofwhichareconict-
ing.Oneofthem,p1,hasanarrowattachedtoatransition,theother,p2,has
not.p1seemstobemorevaluableinthiscase,andshouldnotbeleftout.Ifit
would,thearrowcouldnotbeembedded.However,asembeddingproductions
areappliedlast,theparserdoesnotknowaboutanyembeddingproductionswhen
deducingthesetproductionrule.Thesameistrueforconictswhichmayarise
inlaterapplicationsofnonterminalproductionrules.
Thesolutionistopostponethedecisionaboutleavingoutedgesfromtheset
untilthestartsymbolhasbeendeduced.Thissolvestheaforementionedissue
(evenforembeddingproductionrules,whicharediscussedinthenextsection).
Afterthestartsymbolhasbeendeduced,allcontextinformationintermsofsyn-
tacticstructureisobtained,andreasonabledecisionsaboutleavingoutsymbols
canbemade.Undercertaincircumstances,however,edgescanactuallybeleft
outbeforethis.Figure9.4showsanexemplaryderivationtree,andliststheap-
pliedproductions.Thetextwritteninsideeachedgeisnotalabel,butaunique
name;thelabelsoftheedgesareofnointerestinthisexample.Nodesarenot
shown.Setproductionsareencircled,twoarrowsleavinganedgeandendingin
nootheredgemeanthatthederivationtreecontinueshere,whichisalsoofno
interestfortheexample.Asbefore,conictsareshownbydashedlines.
AfterA3hasbeendeducedfromBandF,itcanbeseenthatB3mustbe
immediatelyremovedfromitsset,asitconictswithF.Fcannotbeleftout,as
itisinnoset.Thisisthesimplestcasewhenanedgeinasetcanbeleftouteven
beforethestartsymbolisdeduced.Accordingly,afterDhasbeendeducedfrom

120

CHAPTER

9.

ARSERP

9.3.

SET

PRODUCTION

ULESR

121

122

CHAPTER

9.

ARSERP

9.4.EMBEDDINGPRODUCTIONRULES

123

theweightedratingsoftheotheredgesare2/3,soC1isdiscardedfirst,andthe
obtained.isresultoptimalGiventhattheratingofC1is2.9,andtheratingsofA2,A4,andC2are1.0,
theweightedratingofC1is29/30,andtheweightedratingsoftheotheredges
are10/29,sooneofthemisremovedfirst.TheratingofC1changesto29/20,and
againoneoftheotheredgesisremoved.Finally,thethirdofthoseisremoved,
too,andonlyC1remains.Thisisnottheoptimalsolution,butstillaverygood
one,accordingtotheratings(2.9comparedto3.0).
Toconcludethissection,conictswithinsetsobtainedbysetproductionsare
ignoredfirst.Conictsbetweenedgesinsetsandedgesnotinsetscanbesolved
immediately.Afterthestartsymbolisdeduced,theremainingconictsarealso
solvedbasedonaheuristic.

RulesoductionPrEmbedding9.4Embeddingproductionrules(EPRs)arenotconsideredbeforethestartsymbol
hasbeendeduced.Then,forallEPRsthecontextsaresearchedforinthederiva-
(astiontree.indicatedForbyeachthematchrule),ofifathereconteisxt,atherespectirespectiveveedgeedgeispresent.FembeddedorEPRinsthewheretree
theembeddededgeisnotaterminal,butanonterminal,thisnonterminalisre-
gardedasstartsymbolfortheEPRanddeducedliketheregularstartsymbolof
thegrammar.Thisway,theembeddededgeisalwaysvalid,asthereisnoconict
initsembeddedterminalisthatedges.eeisnotWhatconictingremainstowithbethecheckstartedifsymbolanedgeoftheeederiwhichvationistotreebe
(whichincludesthatthereisnoconictwiththecontextoftheembeddededge,
andhappens,thateethatisnotedgewhichconictinghaswiththeanyhigherotherratingedgeispreservembeddeded,andbefore).theIfotherthelatteredge
isdiscarded.Byembeddingedgesinthederivationtree,thetreebecomesadi-
rectedacyclicgraph(DAG).Theratingofthestartsymbolisincreasedforevery
embeddededgebytheratingofthatedge.
Obviouslythisapproachcanalsobeappliedwhensetproductionsarepresent.
However,whenconictsinsetsareresolvedbytheheuristicexplainedinthe
previoussection,additionalcarehastobetakenfortheembeddingofedges.A
ee.conictingIfcisedgeremocvised,moreeevcanaluablenoiflongeritisbepartofembeddedaconteandxttforheanratingembeddeofthededgestart
symboldecreases.Accordingly,thecomputationoftheweightedratingofan
edgemustbemodifiedinordertoalsopreferthoseedges(iv)whicharepartofa
contextforanembeddededge,orwhichhaveachildthatispartofsuchacontext.
of(i)–(iii)allembeddedremainasedgesdescribedwhereebefore.oraLetchildebeofeanisedge,partofandtheircontecontext(ext.)beThenthesetthe

124

CHAPTER

9.

ARSERP

EXAMPLELARGERA9.5.

125

Inanotherexamplecalculationdifferentratingsareassumedfortheterminals,
edgeswhichinleadsthetoRHMaeachconfigurationhaveathatratingofrequires3.0,andthebacktrackingtwo.otherGivenedgesthatinthethettrRHMans
haveweightedaratingratingof1of.0,Pthebecomesweighted(1.0+rating1.0)of/3.T0=becomes2/3.3As.0/1this.0=rating3,iswhilelowerthe,
Pnowillmoreberemochildren,vedsototheresolvremoevalthemustconict.beHoundone,weverand,thistheedgeresultswithintheSPhasecondving
lowestweightedratingisremoved,whichisT.

ExamplegerLarA9.5InoneFiguretransition,7.7(a)andasktwoetchedarrows.PetrinetThehasHMbeengeneratedshownforwiththistwosketchplaces,isoneshowntoken,in
Figure7.7(c).WeassumethereductionrulesinFigure8.3.Usingthesereduc-
tionrules,theRHMshowninFigure9.8(a)isobtained.Therearetwoconicts
betweenterminals.Theconictbetweenp1andtokemergesfromtheconict
intheHM,andtheconictbetweenp1andp2emergesfromthefactthatthe
correspondingplacesaretouching(notshowninFigure7.7(c)).Notethattokens
notcontainscontainedrelationinplacesedgeinareFigurenot7.7(c)reduced.,nottokFurthermore,enedgeforisthereduced,onlyasthenon-omittedtoken
hasalargerradiusthantheplace,whichcontradictstheconditionofthereduction
.8.3(c)FigureinruleingtheFigureproduction9.8(a)alsorulesshowstheestablishedderivationthroughoutDAGthisgeneratedchapterby(thetheonesparser,shownassum-in
andFigurethee9.1(a),mbedding(b),(c),(h)production,thesetrulesshoproductionwninrulesFiguresho9.3(a)wn,in(b)).FigureExcept9.2(a)for,P4(b),,
allthesamePlaceedgesterminalarep2.Theconicting.twoP2otherandP3conictsareemerconictinggefromasthetheyareconictsderivedbetweeninto
theterminals.Fora1therearetwocontextspossible,TRandP2,orTRandP3.
Fora2thereisonlyonecontext,TRandP4.Notethatthetwocontextsfora1
couldalsobeavoidedbyusingtheterminaledgesascontexts,asopposedtothe
nonterminalsasin(cf.Figure9.3).
Usingtheweightedratingsandtheheuristic,theconictsbetweenP1,P2,
andprocess,P3areaseachresolvhased.aObconictviouslywithonlyeachoneotherof.theTheethreexpectednonterminalssurvivorissurviP2v,esasthisthis
nonterminalrepresentstheoutercirclebeingaplace,andtheinnercirclebeinga
token,andallowsforembeddingofa1.
ratingsExamplefortheratingsnonterminals.oftheBasedterminalsonaretheseshownratings,intheFigureweighted9.8(b),asratingswellforasthethe
threeconictingnonterminalscanbecomputed,allofwhichareinthesameset.

126

CHAPTER

9.

ARSERP

9.6.ATTRIBUTEEVALUATION

127

Figure9.8(c)showstheseinitialweightedratings,andupdatedweightedratings
afternonterminalsareremoved.Eachrowinthetablerepresentstheremovalof
onenonterminal,untilindeedP2remains.

aluationEvuteAttrib9.6

WjustithlikeoneitminordoeseinDIxceptionAGEN.(seeWhenbelow),specifyingattributeethevaluationgrammarw,orkseachinDSKnonterminalETCH
maybegivenattributes,dependingonthelabelofthenonterminal,justlikethe
ofattribtheutesterofminalsthesetshapebytheedgesreducerused.byThethestartmodelersymbol(cf.isChapterrequired7to),haandveattribonedis-utes
roottinguishedalwaysisattribaute,startthesymbol.semanticThefinalattribvutealue.GiofventheaderisemanticvationDattribAGute(orofthetree),rootits
istributedconsideredgrammaras.theJustliksemanticseforofthereductionDAG.rulesIt,folloeachwsthatproducttheiongrammarrule,noisanmatterat-
whatnal(s)inkind,thehasLHSanbasedactiononwthehichattriballowsutesforofthesettingedgestheinattribtheutesRHSof.theExamplesnontermi-for
actionsofproductionrulescanbefoundinAppendixA.
reason,IfthethenvaluetheofshapesthesemanticrepresentedattribbyutetheofDAtheGrootarecannotsyntacticallybeevaluatedcorrect,bforutsomecon-
sideredsemanticallywrong.HencethisDAGisnovalidinterpretationforthe
sketch(orpartofthesketch).
DependingonthegrammartheremaybedifferentderivationDAGsdeduced
bytheparser.ForPetrinetsthiscannothappen,butforNSD,forinstance,itcan.
UnlikeDIAGEN,inthiscasethatDAGischosentorepresentthesketchwherethe
DrootAGshasarethehighestdiscarded.ratingTheandrationalethesemanticbehindthisattributeprocedurecanbeisevthealuated.following:Alltwothero
difoccurferentbecauseDAGsdifalwferentayssetsofrepresentderivtwoationsdifledferenttothestartinterpretationssymbol.ofFortheeskxample,etch,andthe
inparserthetriessametoderiderivvationethestructstarture,symbolofcourse.witheachAlso,ofwetwohaveconictingestablishededges,thataalbeithighernot
moreratingcomplemeansxabettersymbols,orinterpretation,morepreciselyeitherdrawnbecauseitsymbols,containsoramorecombinationsymbols,oftheor
three.rating.IftheAccordinglysemantic,itmakattribesutesensecannottodiscbeeardvallaluatedDAGforbutanytherootoneofwiththetheDAGs,greatestthe
sketchinturncannotbeinterpreted.Anexampleforattributeevaluationisgiven
.C.2Appendixin

128

Summary9.7

ARSERP9.CHAPTER

ThischapterhasdescribedhowsyntaxcanbecheckedbasedontheRHM,and
howparsing.semantTheicsdericanvationbestructuredeterminedisbasedusuallyonaDtheAGderiduevtoationembeddingstructureobtainedproductions.by
TheCNF.parserConteworksxt-freenessbottom-upisobtainedandbyrequirestheavtheailablegrammarkindstoofbeconteproductionxt-freerules,andthein
rulesCNF(canTPRbes)andcomputednonterminalautomaticallyproduction.Nextrulesto(theNPRobs),viousthereareterminalsetproductionproduction
cientrules(SPRparsings),ifandasetofembeddingedgeswithproductionthesameruleslabel(isEPRtos).beSPRderisved,allowandforthemoreordereffi-of
theedgesdoesnotmatter.EPRsallowfordescribingruleswhicharenotcontext-
free.deducingSettlementnonterminalsofconictswhichinthearederiRHMvedisintoassuredconictingforeveryterminals.productionForsetbypro-not
DAGductions,isdeducethisd.conditionThen,caanheuristiconlybeisusedestablishedwhichaftersolvestheavrootariantoftheofthederivcliqueation
problem,directedbyratingsofedges.

10Chapter

aluationEv

isAnobpossiblevioustogiquestionveaaboutformaleveryproofofapproachcorrectness.isitsIncorrectness.thecaseInofsomethisthesis,fieldsita
formalproofcannotbegiven.Itisimpossibletoshowthattheapproachproduces
theproducedresultatall.intendedAnotherbythewayuserto.arEvgueenaboutmore,itcorrectnessmayhappenisanthatempiricalthisevresultisaluation,not
whichisperformedinthischapter.Itfollowstwogoals.Thefirstistotellabout
theactualrecognitionrate,i.e.,

recognitionrate:=##ofofcorrectlyshapesintendedrecognizedbyusershapes

Thehigherthisrateis,themoreoftenthecorrectshapeisrecognized,andthe
morerarelytheuserhastomanuallycorrecthisinput.Arecognitionrateof100%
Evmeanserythatapproacheverytoskshapeetchingstriintentionallyvestodragetwnasbyclosethetouserthisisvaluecorrectlasypossible,recognized.how-
everThetherealsecondwaysgoalwillofbetheevmisrecognizedaluationinthisshapes.chapteristoassesstheperformance
oftheimplementation.Thefastertheactualresultiscomputed,thebetterthe
andsystemshouldislikbeelyavtooidedbebyperceivedbyimplementations.theuser.Alongwaitingperiodisbothersome,
tation,Inaorderusertostudylearnwasaboutconducted.recognition16rateandparticipants,performanceallcomputerofthescientistsimplemen-or
studentsofcomputerscience,eachdrewoneexamplesketchofeachofthesix
terdiagramdiagramwlanguagesasshowntodiscussedtheinChaptparticipants,er2.Fwhichorhadeachtodibeagramcopied.languageThisaassuredmas-
thattheresultsfromthedifferentparticipantsarecomparable,aseachparticipant
copiedthesamemaster.Figure10.1showsallsixmasterdiagrams.Theseare
equaldiagramtothethanethexampleoneshodiagramswninfromFigure2.4Chapterwas2;used.onlyfortheGUIbuilderasimpler

129

130

CHAPTER

10.

TIONAALUEV

TIMEOCESSINGPR10.1.

131

Figure10.2:AGUIbuildersketchfromtheuserstudyinthreecopies.Thecopies
areidenticalandhavebeenplacednexttoeachotherautomaticallyinorderto
linearlyincreasetheloadonthesystem.

Thestructureofthischapterisasfollows.Thenexttwosectionsdiscusspro-
96cessingsketchestimesobt(Sectionained10.1from)theanduserrecognitionstudy.ratesThetwo(Sectionaspects10.2)eforxplainedthe6in×16Sec-=
tion6.1andSection6.3(eliminationofduplicates,andsuppressionofshapes
measuredcontainingasotherthenumbershapes)ofhaveshapesbeen,byintendedremotovingminimizshapeseinthetheloadonpostprocessingtheanalysis,step
isoftheachieved,recognitionbymeansstage.ofselectedSectione10.3xamples.and10.4Sectiondiscuss10.5towhichconcludesextentthethischaptergoal.

imeTocessingPr10.1Foreachofthe96sketchesobtainedbytheuserstudy1itwasmeasuredhowlong
stableprocessingresults,took.eachAntestwordinaryasPCrepeatedwastenusedtimes,ashardwandthearea.vInerageordervtoaluewobtainastakmoreen.
Furthermore,toevaluatehowtheimplementationperformswhentheinputsizeis
increased,thecompleteprocedurewasrepeatedninetimesforeachsinglesketch,
eachtimewithoneadditionalcopyoftheoriginalsketchtobeprocessed.Each
efcopyfects.wasThisplacedway,withbothatheinputconsiderable(counteddistanceastonumberallofotherstrokcopiesesandtoavnumberoidsideof
texts)andthenumberofrecognizedshapesgrewlinearly.Oneoftheparticipants
sketchesoftheGUIdialogboxwithtwoadditionalcopiesisshowninFigure10.2.
sketches.TheavTheeragedresultsvaluescanforbeeachseeninsingleFiguresketch10.3,werewhichaveragedshowsagtheainformentionedall16
1ThePCranUbuntuLinux8.1064bit(kernelversion2.6.27),andwasequippedwithanIntel
quad(64bit,bcoreuildCPU1.6.0at10-b33).2.66GHzHoandwev4GBer,ofonlyphoneysicalCPUmaincorememoryanda,andmaximumJavaSEof2GBruntimeofenmainvironmentmemory
havebeenallocatedforthetests.

132

CHAPTER10.EVALUATION

averageprocessingtimedependingonthenumberofcopies(1to10).Standard
deviationisshownasverticalblacklinesforeachaveragedvalue.Figure10.4
showsthefractionofbothstages(recognitionandanalysis)ofthetotalprocessing
time,againbrokendownbythenumberofcopies.
Forallreportedvalues,preprocessingisnotincluded.Thereasonisthatpre-
processingisperformedincrementallyanddoesnotaddtotheperceivedperfor-
manceofthesystem.Forevaluatingtheperformanceofpreprocessingsingle
strokesandtext,thetimeforpreprocessingwasmeasuredforthecaseoften
copiesofeachdiagram.Theaveragetimeforpreprocessingasinglestrokewas
0.36ms,theaveragetimeforpreprocessingtextwas0.04ms.Thesevaluesindicate
thattheperformanceimpactofpreprocessingcanindeedbeneglected,whetherin
not.orsettingincrementalanWhatbecomesapparentfromtheactualmeasuredvalues(notshown)isthat
mostofthetimeisspenteitherbytheassembler,orbytheparser.Accordingly,
performancefortheassemblerandpostprocessingareaggregatedinFigure10.4,
andsoaremodeler,reducer,andparseraggregatedfortheanalysis.Themaximum
aggregatedfractionofpostprocessing,modeler,andreducerofthetotalprocessing
timeforallsketchesfor1through10copiesneverexceeded5%.Anexceptionto
thisruleismadebytheGUIbuilder,wherethemodelerconsumesrelativelymore
time,andtheaggregatedfractionofpostprocessing,modelerandreducerthus
increasestoabout15%.Still,theaggregationofvaluesasdescribedisjustified.
Forallsixdiagramlanguagestheprocessingtimegrowsroughlylinearwith
theinputsize.OnlyforPetrinets(cf.Figure10.3(a))andforstatecharts(cf.
Figure10.3(d))aslightlygreaterincreasecanbeobserved.Theimplementedal-
gorithmsarenotallinO(n),butinhighercomplexityclasses.Thisisespecially
trueforassemblerandparser.Theassembler,forexample,takesconsiderably
moretimeformorecompactsketches,becausetheinputbecomesmoreambigu-
ousthisway.Theperformanceoftheparserdependsonthenumberofterminals,
andontheproductionrules.Iftherulesarenotwiselyspecified,e.g.,bynot
usingsetproductions,complexityincreases.See[68]formoredetails.Despite
theover-linearcomplexity,thementionedroughlylineartimeconsumptioncanbe
observed,whichshowsthatthepracticalimpactofthesealgorithmsisnotsevere.
Fromtheaveragetotalprocessingtime,theaverageprocessingtimecanbe
computedforasingleshapedrawnbytheuser.Theresultisshowninthefollow-
ingtable,dissectedbythesixdiagramlanguages.
PetrinetsNSDGUIbuilderStatechartsBLDTic-tac-toe
10ms23ms4ms28ms3ms3ms
NSDandstatechartsshowthehighestvalues.Thereasonisthatthetotalprocess-
ingtimeoftheselanguagesisalsohigh,comparedtotheGUIbuilder,Tic-tac-toe
andBLD.Petrinetsalsoshowalowaverageprocessingtimepershape,although

10.1.

OCESSINGPR

TIME

133

134

CHAPTER

10.

ALUEVTIONA

TESRARECOGNITION10.2.

135

RatesRecognition10.2Asmentionedintheintroductiontothischapter,theotherrelevantaspectnextto
processingtimearetherecognitionratesoftheimplementation.Tobeginwith,
thesearesometermsweuseinthefollowing.
atruepositiveisashapethattheuserhasdrawnintentionally,andthatis
correctlyrecognized.Forexample,eachofthethreetransitionscontained
inthePetrinetmaster(cf.Figure10.1)hasbeendrawnintentionally.
afalsepositiveisashapethatisrecognized,butwhichhasnotbeenintended
bytheuser.Falsepositivesmayhappenduetotolerancesappliedbythe
recognizer,orduetomisleadingdiagramsyntax(forexample,NSD,cf.
).6.2Figureafalsenegativeisashapethattheuserhasdrawnintentionally,butwhich
ismissedbytherecognizer,forexample,becauseithasbeendrawntoo
.sloppilyUsingthe96sketchesfromtheparticipants,thenumberoftruepositivesisdi-
videdbythenumberofintendedshapes(asgivenbythemasterofeachofthe
sixdiagramlanguages)inordertoobtaintherecognitionrateforasinglesketch.
Theserecognitionratesareaveragedforthesixdiagramlanguages.Figure10.5
showstheresult.ExceptforPetrinetsandstatecharts,recognitionratesrange
around90%.Forthetwoexceptions,recognitionratesarelowerbecausetheuser
studysparticipantstendedtodrawarrows(whichoccuronlyinthesetwodia-
gramlanguagesamongthesix)sloppily,whichledtomanyfalsenegatives.Also,
rectangles,eitherusedtoexpresstransitions,ortoexpressstates,weredrawncon-
imprecise.moresiderablyForthefinalresult,obtainedbytheanalysisstage,thefollowingobservations
holdforeachofthe96sketches.
Eithertheresultwasasintendedbytheuser,i.e.,itcontainedonlytrue
positivesandnofalsenegatives,
ortheresultcontainedonlyintendedshapes(truepositives),butwasincom-
pleteduetoshapesmissedbytherecognizer(falsenegatives),
orfalsepositiveswereincludedintheresultinordertoobtainasyntacti-
callycorrectresultatall,whichwouldnothavebeenpossiblewiththetrue
.onlyesvpositiThethirditemisveryimportant.Itmeansthat,innocase,afalsepositive
wasincludedinthefinalresultofprocessinginfavorofatruepositive.Thisfact

136

CHAPTER

10.

TIONAALUEV

10.4.EFFECTOFTHESUPPRESSIONOFSHAPESCONTAININGOTHERSHAPES137

forFigureone10.6:copyAofvtheeragetotaldiagrams,processingstackedbytimetimewithforandrecognitionwithoutremoandvalofanalysis.duplicates

Thebarsarestackedbytimeforrecognitionandanalysis.Asexpected,recogni-
tiontime(whichincludespostprocessingwhereduplicatesareremoved)remains
nearlyconstant,whileanalysistimeincreasesbynotremovingduplicates.Com-
weremontonotallaffecteddiagramsbyisremothatvaltheofrecognitduplicates.ionratesreportedintheprevioussection
onlyForshowsPetrianets,smallforimpact.statecharts,ForNSDand,forforTtheic-tac-toe,GUIbuilderand,forremoBLDval,ofanalysisduplicatestime
increasesconsiderablyifduplicatesarenotremoved.InthecaseofNSDthe
avNSDerageisthattotalsomeprocessingofthe16timeskevetchesengroshowswtoahighabout18numberseconds.ofduplicates.TheproblemIftheseof
duplicatesarenotremoved,theimposedloadontheanalysisissignificant.If
duplicateswerenotremoved,forthethreesketcheswiththehighestnumberof
recognizedshapeswhichwerepassedtoanalysis,theaveragenumberofthese
shapesshapeswforas147.analysisInofthecontrast,sameifthreeduplicatessketcheswereisonlyremov10.ed,theaAccordinglyverage,thenumberspeed-of
forupforBLD,NSDtheachiespeed-upvedbyisnotremoasvalhighofasforduplicatesNSD,isbvuterystillhigh.FremarkablyorT.ic-tac-toe,and

10.4EffectoftheSuppressionofShapes
ShapesOtherContaining

Section6.3hasexplainedtherationalebehindtheremovalofshapescontaining
othershapes.Nowitisinvestigatedwhethertheseconsiderationsholdforthe
implementation.Ifthe16NSDsketchesareprocessedagain,withoutshapescon-

138

(a)

CHAPTER

10.

TIONAALUEV

CONCLUSION10.5.

139

moved,thefractionoftheanalysisstageonthetotalprocessingtimeincreased
fromabout30%toabout85%.
Likeinthesectionbefore,therecognitionrateisnotaffectedbytheoption.
Consequently,theassumptionmadefortheremovalofshapescontainingother
shapesisvalidinthistestsetting.

10.5Conclusion

Inatedthisbasedchapteron,auserperformancestudy.Theandoverallrecognitionresultofratestheofevthealuationimplementisthatationtheareeapproachvalu-
isthatfast,thewitharecognitionverageratesprocessingaregood,timeswithperaboutshape90%rangingforfourfromof3msthetosix28ms,diagramand
languages.Themeasuresarrangedtoimproveprocessingtime(eliminationofdu-
theplicates,onehand,suppressiontheygreatlyofshapesimprovecontainingperformance,otherbutshapes)ontheallwotherorkashandtheintended.ydonotOn
rates.recognitioninuenceBothTtheakingaperformancecloserlookandatthetheevrecognitionaluationratesresultsrestronglyvealsdependinterestingontheintricacies.diagram
language.Thisdependencyisanimportantaspect,becausetheapproachpre-
sentedlanguages.inthisHowethesisver,isthegeneric,sixeandxamplehasbeenlanguagesdesignedweretocarefullyhandledifchosenferentinorderdiagramto
berepresentativeforabroadrangeofdiagramlanguages(cf.Chapter2).
tionSkratesetchesarenotwhereasgoodprocessing(worseisthannotasthefaastv(werage),orsenearlythanthealwavayseerage),xhibitorarecogni-certain
draTherewingisastyle.clearThetendencstyleycanthatbethelesscharacterizedspaceabysktheetchskcoetchverssizeonandthethecanvas,precision.the
stage.higheritsAllrespectiprocessingvetimethresholdis.Thisvaluesisduearetothegenerouslytolerancessetinusedorderintotheallowrecognitionforan
easystudy.andIfsketchesunconstrainedaredradrawnwivng,eryandsmall,remainthefixedthresholdforveachaluesareparticipanttoohigh,oftheresult-user
inginmuchmorecombinationsofprimitives,andultimatelyinmoreshapesthat
recognized.arenitionLikeratewise,is.Athelesstypicalprebehacisionviortishattoisdrawappliedcorners,bythee.g.,user,fromthealowerrectangle,therecog-more
roundedthanangular.Similar,mostusersdrewtheopen-headarrowsfromPetri
thenetsarroandwheadstatechartsinabysecondfirstdrastroke.wingHere,theashaftsiminilaroneobservstroke,ationandcouldthenbedramade:wing
thehand,arrodrawwingheadwasstraightlinessometimes,e.g.,draforwnliketransitionsanarc,ofandPetrinotnets,angled.orforOnNSDthe,orotherfor
BLD,wasrarelyaproblem.Circles,usedinPetrinets,Tic-tac-toe,BLD,and

140

CHAPTER10.EVALUATION

statecharts,werealwaysdrawninonestroke,withoutanyexception.Still,the
individualrecognitionratesforcirclesdiffernoticeablybetweenthefourdiagram
languages.ForPetrinets(92%)andTic-tac-toe(95%)therecognitionratesare
good,whileforstatecharts(79%)andBLD(72%)thevaluesarelower.Itcould
beobservedthatcircleswereoftendrawnquitesmallinthesketchesofthesetwo
languages.diagramTwofinalaspectshavetobeconsideredinordertoassesstherecognitionrates
reportedinthischapter.Thefirstisthattheapproachrecognizesindividualshapes
fromcompletesketches.Segmentationandclusteringareperformedautomati-
callybytheassemblerstep,basedonthemodeldata.Thereisnootherindication
giventodecideabouttheseissues.Thisway,thedrawingprocessismorecom-
fortableandnaturalfortheuser,butrecognitionbecomesmoredifficult.Theother
aspectinuencingtherecognitionrateisthattheparticipantswerenotshownany
feedbackabouttherecognitionbeforetheywerefinisheddrawing.Hence,thein-
dividualdrawingstylecouldnotbeadaptedtothesystem.Withoutthisstringent
precondition,higherrecognitionratescanbeexpected.Theaforementionedis-
suesofsmallsketches,sloppycornersandsloppyarrowheadswouldbereduced.
Despitethesetwoaspects,theimplementationaccomplisheditstaskwell,bothin
termsofperformanceandrecognitionrate.
Futureworkcanbederivedfromtheconclusion.Thementionedissuesof
imprecisearrowsandcornersofrectanglescouldbedealtwithbymoresophisti-
catedtransformers,whichtaketheseissuesintoaccount.Then,recognitionrates
wouldcertainlyimprove.Forexample,thelinetransformercouldelongatetwo
perpendicularlinesinordertofindtheirpointofintersectionasthecornerpoint
thatismissedduetothesloppydrawingstyle.
Amoresophisticatedapproachtosloppydrawingstylecouldbetheintro-
ductionoftop-downaspects.Thecompletesketchprocessingchaindescribedin
thisthesisworksbottom-up.Ifthereare(sub-)strokesthatdonotcontributeto
anyshape,thesystemignoresthese(sub-)strokes.Butifweassumethattheuser
intendsallofhisstrokestorepresentsomethingmeaningful,these(sub-)strokes
shouldnotbediscarded.Accordingly,aftertheassemblerhasfinished,allun-
used(sub-)strokes(andmaybeotherstrokesintheirdirectspatialneighborhood)
couldbeextractedandsearchedagainforshapes,butwithrelaxedthresholds.The
ratingsoftheadditionalshapesthatarerecognizedthiswaycouldbereducedin
ordertomaketheanalysisstagepreferthoseshapeswhichhavebeenfoundinthe
firstrunoftheassemblerwheretheregularthresholdsareapplied.
AlsoanopenquestionishowDSKETCHisperceivedbyusersoveralonger
periodoftime.Long-termobservationsofuserscouldhelptoimproveboth
DSKETCHanditsuserinterfaceinordertomeetexpectationsandrequirements
ofusers.Thereby,alsothequestioncouldbeansweredofhowmuchrecognition
ratesimproveiftheuserisusedtothesystemandhaslearnedaboutitsbehavior.

11Chapter

ConclusionandSummary

ThisthesishasexplainedDSKETCH,agenericapproachtotheunderstandingof
hand-drawndiagrams.Usingspecificationsitcanbetailoredtospecificdiagram
languages.Understandingadiagramcomprisestwostages,recognitionandanal-
ysis.stageThethenreanalyzescognitionthestageshapesinidentifiestheirtheconteshapesxttodraresolvwnbyetheambiguities.user.TheThisanalysispro-
cessisbasedonsyntaxandsemanticsofthediagramlanguage.Eachofthetwo
stagesismadeofthreesubsequentsteps.
Thefirststepoftherecognitionispreprocessingofstrokesandtext,whichis
performedbyindependenttransformers.Eachtransformerhasacertainviewand
straightprocesseslines,databutdoesaccordinglynot.reFgorardeotherxample,primtheitilineves.transformerTherebydatamapsgetsthestrokabstracted,esto
whichsimplifieslaterprocessing,anddecreasestheamountofdata.Eachtrans-
formercreatesonemodelwherethepreprocessingresultisstored.Theadvantage
ofprocessedthisbyprocedureeachisthattransformerthere,aresevseeralveralmodelsinterpretationsinofparallel.astrokAseallmaystrokcoeesxistarein
differentmodels.Thereisnoneedatthispointtodecideforoneinterpretation
(whichisnotevenpossibleyet,asthereisnoinformationtoguidethisdecision).
Itisample,acompletelytransformeruptocanthetryandtransformersmapthewhatinputdatapreprocessingtoonethekindyofperform.primitiFvore,easx-
thelinetransformerdoes.Atransformercouldalsomaptheinputdatatodifferent
cankindsevofenbeprimitimoreves,thanalthoughonenotransformertransformerforoneinDkindSKEofTCHprimitidoesve,so.asitisFinallythe,therecase
forthearctransformerandthecircletransformer.
intheThemodels,assemitblerisidentifiesthesecondshapes.stepTheintheoriginalrecognitioninputdata,stage.i.e.,Basedstrokesonandthetedataxt,
arenotpresenttotheassembler.Therationalebehindthisisthatthemodelsonly
containhighlyabstracteddata.Consequently,theassemblercomputesitsresult
veryefficientlyifitlooksatthemodelsonly,andnotattheverboseinputdata.

141

142

CHAPTER11.SUMMARYANDCONCLUSION

Thismeansthatallrelevantdatamustbeprocessedbytransformers,otherwiseit
islost.Theassembleridentifiesshapesbyqueryingprimitivesfromthemodels,
andcombiningtheseprimitives.Asearchplan,automaticallygeneratedfromthe
specificationofshapes,guidesthisprocessanddefinestheorderinwhichprim-
itivesaresearchedfor.Thisallowsforsearchingprimitivessharedbydifferent
shapesfirst,whichmakesthewholeprocessmoreefficient.Forexample,places
andtokensfromPetrinets,bothdrawnascircles,areidentifiedinparalleland
donothavetobesearchedforasecondtime.Animportantaspectoftheassem-
bleristhatithasnospecificinformationonanymodel.Ifaprimitiveissearched
for,everymodelisqueried,andtheresultsfromallmodelsareusedtocontinue
thesearchprocess.Thisisacrucialaspecttotheextensibilityoftherecogni-
tionstage.Newtransformersandassignedmodelscaneasilybeadded,andthe
assemblerdoesnothavetobechangedinanyway.
Thethirdstepoftherecognitionstageisthepostprocessing.Thesetofshapes
identifiedbytheassemblerisfirstexaminedforduplicates.Duetothetolerances
appliedbythetransformersandtheassembler,itfrequentlyhappensthatthesame
shapeisidentifiedmorethanonce,eachtimeslightlydifferent.Theseduplicates
arecorrectlyhandledbytheanalysisstage,i.e.,thisstageneverincludesdupli-
catesinthefinalresult.However,removalofduplicatesduringpostprocessing
improvestheperformanceoftheanalysisstage.Usingafurtherconfigurationop-
tion,setinthespecification,thepostprocessingstepcanremoveevenmoreshapes
toincreaseperformance.Thisoption,motivatedbyNSD,allowsforsuppression
ofshapescontainingothershapes.Itmustbeoptional,becauseitsusedependson
theshapespecificationsandthusitcannotbeappliedingeneral.Moreover,the
postprocessingidentifiesambiguitiesbetweenshapes.Anambiguitymeansthat
onlyoneoftwoshapescanbecorrect.Ambiguitiesareexplicitlymodeledasso-
calledconictsfortheanalysisstage,whichhasshowntobeavaluableapproach
totheirresolution.Finally,allshapesthathavenotbeenremovedarerated.The
ratingislaterusedtodecideforoneoftwoshapes,oroneoftwosetsofshapes,
incasethatthecontextinformationdoesnotsufficetomakethisdecision.
Withthepostprocessingsteptherecognitionstageisover.Thesubsequent
analysisstagecomputesasyntacticallyandsemanticallycorrectsubsetoftherec-
ognizedshapes,andrespectstheconictsidentifiedearlier.Forthispurpose,the
completestageisbasedontheDIAGENtool,andadoptsthreeofitssteps.The
firststepisthemodeler.Itidentifiesrelationsbetweenshapesandcreatesahyper-
graphmodelrepresentingallshapesandallrelations.Thespecificationdescribes
attachmentareasdefiningwhichpartsofshapescanberelatedtopartsofother
shapesatall.Themodelertakesintoconsiderationthattheseattachmentareas
canbedeformedforactualshapes,duetotheimprecisenessofhand-drawing.
Thesecondstepoftheanalysisstageisthereducer,whichreducesthehy-
pergraphmodelproducedbythemodelerinordertoyieldanothergraphmodel,

143

thereducedhypergraphmodel.Thisreductionprocessisguidedbyrules.The
keyideabehindthereduceristodecreasethesizeofthehypergraphmodelby
replacingpatternswithsimplerpatterns,comprisedoflessedgesandnodes.In
doingso,invalidpatternsareignored,i.e.,notreduced,andthusneednotbedealt
withlater.AnexampleforaninvalidpatternisanarrowinaPetrinetconnecting
twoplaces.Duringthereductionprocessitisassuredthatconictsbetweenthe
shapesarestillpresentinthereducedmodel.Furthermore,negativeapplication
conditionsareasecondsourceofconicts.Thesespecialconditionsareusedto
constraintheapplicationofreductionrules.Inourcase,thechallengeisthatrule
applicationsmustnotbeomittediftheseconditionsaresatisfiedbymisrecognized
shapes.Asasolution,ruleapplicationsareneveromitted,butconictsaregen-
eratedformatchedapplicationconditionsaswell.AnadvantageofDSKETCH
isthatconictsbetweenshapesandconictsduetotheseapplicationconditions
arerepresentedbythesameconceptinthereducedmodel,whichsimplifiesthe
step.processingsubsequentThefinalstepintheanalysisstage,andinunderstandingthecompletesketch
therewith,istheparser.Controlledbyproductionrulesdefinedinthespecifica-
tion,itcreatesaderivationstructureinabottom-upmanner.Theedgesinthere-
ducedhypergraphmodelareusedasterminalsymbols.Theproductionrulesare
essentiallycontext-free.However,thereareembeddingproductionruleswhich
allowforthespecificationofnotcontext-freelanguageconstructs.Furthermore,
therearesetproductionruleswhichcanbeusedtosignificantlyimprovetheper-
formanceoftheparsingprocess.Fortheapplicationofeachproductionrule,the
parserrespectsconictsbynotusingtwoterminalornonterminalsymbolsinthe
RHSofanapplicationofarulewherethesymbolsareconicting.Theresultof
theparsingprocessisaderivationDAG,orasetofDAGs.Inthelattercase,that
DAGischosenwhichexhibitsthehighestrating.Then,semanticsofthesketch
arecomputedonthebasisofthisDAG.Thesemanticsisdefinedasthevalueof
onedesignatedattributeofthestartsymbol.Thevalueofthisattributeisthefinal
processing.etchskofresultThecompleteapproachhasbeenthoroughlyevaluated,basedonauserstudy.
16participantseachdrewsixsketchesfromdifferentdomains.Performanceand
recognitionrateshavebeenevaluatedusingaprototypicalimplementation.This
evaluationhasshownthatbotharesatisfying.Ageneralruleofthumbcannotbe
givenonhowtoestimatebothmeasures,astheydependonthediagramlanguage,
butalsoontheactualsketch.Theevaluationhasalsoshownthattheassumptions
underlyingtheremovalofduplicatesandthesuppressionofshapescontaining
othershapesappliedbythepostprocessor(toreducethenumberofshapes)are
valid,becausetheiruseimprovesprocessingtimeconsiderably,anddoesnotde-
rates.recognitiongradeThetwocentralaspectsDSKETCHisdesignedforaretheunderstandingof

144

CHAPTER11.SUMMARYANDCONCLUSION

sketcheddiagrams,whilepreservinganaturalandexiblewayofdrawingforthe
user.Theapproachcombinesthefollowingattributes,whichmakeituniqueand
illustratethescientificrelevance.

eGenericxible.–Usingtheapproachspecificatisions,nottailoringcustomizedcantobeaachiespecificved.Ondiagramtopoflanguage,this,balsout
thefinalresultofdiagramprocessingcanbecustomizedtodomain-specific
needs.

Twostages–diagramprocessingiscomprisedoftherecognitionstageand
theanalysisstage.Therecognitionstagereliesontransformersandmodels,
andisveryexibleandextensible.Theanalysisstageisbasedonthepow-
erfulDIAGENframework,andperformsdiagramunderstandingbycreating
result.processingfinalthe

Multi-strokerecognition–animportantbenefitofsketchingisitsnatural
wayofinput.Thisbenefitshouldnotbemitigatedbyconstrainingtheusers
style.wingdra

On-linerecognition–basedonthemotivationthatsketchingeditorsreplace
traditionalpoint-and-clickeditors,on-linestrokeinformationispresentand
xploited.ebecan

shape.AutomaticAccordinglclusteringy,DandSKseETCHgmentationrecognizes–diagramsshapesincomprisecompletedmoreskthanetches,one
andperformsallnecessarystrokeclusteringandsegmentationautomati-
.cally

proaches,Geometry-basedshapesarespecificatiospecifiednbyandprimitirecognitionvesandoftheirshapes–geometriclikeinotherrelations.ap-

Nolimitationsbyfeatures–thearchitectureoftherecognizerdoesnotrely
ondrawingfeaturesstyleiningeneral.orderAtodramatchwbacktheoffeatures,featuresifisthethatyaretheynotrestrictchosenthewiselyusers.
Ouronlyapplicationoffeaturesisforthecircletransformer.

Notraining–asshapesarespecified,andasrecognitionisnotbasedon
features(apartfromthecircletransformer)notrainingsamplesarerequired,
whichdecreasesstart-uptimefortheuser.

Automaticresolutionofambiguities–ambiguitiesaresolvedautomatically,
notbasedoninexiblemeta-rules,butbasedondiagramlanguage-specific
describingrulessemantics.andsyntax

145

Lazyrecognition–becauseonlytheuserknowswhenadiagramisfinished,
andbecausecorrectsyntaxandsemanticsarecrucial,itistheuserwhohas
toexplicitlyinvokerecognition.
Checkingofsyntaxandsemantics–automaticresolutionofambiguitiesis
interwovenwithcheckingsyntaxandsemantics.Usingthischeckingitis
possibletocomputeaprocessingresultthatcanbeusedimmediatelyin
anotherapplication,whichisatypicalscenarioforsketching.
Goodperformanceandrecognitionrates–shownbyauserstudy,perfor-
manceandrecognitionratesaregood.
Thepresentedthesishasidentifiedseveralstartingpointsforfurtherwork,
whichhavebeenillustratedintheircontextintherespectivechapters.Foreach
suchchapter,asinglesectionhasbeendevotedexclusivelytofurtherwork.Ac-
cordingly,wegiveonlyabriefoverviewhere,withoutdelvingintoallthedetails
thathavebeendiscussedbefore.
Forthepreprocessingstep,theuseofadividerhasbeendiscussed,which
wouldallowformode-lesswritinganddrawingnexttoeachotheronthe
canvas(Section4.6).
Coupledwiththeissueofadivideristoevaluatewhichtextinputmetaphor
ismoreconvenienttotheuser,differentalternativesareconceivable(Sec-
).4.6tionMorekindsofprimitivescouldbeuseful,forexample,hatchedandfilled
regions,ordashedanddottedlines(Section4.7).Also,repetitivepatterns
likespiralsorhelicescanneitherbespecifiednorrecognized.
Low-levelrecognizersfromotherresearchgroupscanbeintegratedinto
DSKETCHasanindependenttransformer,whichcouldincreaseoverall
).4.7(SectionratesrecognitionTheevaluationrevealedfurtherissuesofsloppydrawnarrowsandcorners
thatcouldbehandledduringthepreprocessingstep,orevenbetterbya
top-downapproach(Section10.5).
Theassembler,andallsubsequentprocessingsteps,couldbenefitfroman
incrementalapproach,asthiscanbeexpectedtogreatlyincreaseperfor-
mance.Otherapproachesthatdohaveincrementalprocessingareusually
veryefficient,whichsupportsthisassumption(Section5.6).

146

CHAPTER11.SUMMARYANDCONCLUSION

Asanalternativetoanincrementalapproach,orinaddition,recognition
couldbeparallelized,asallsearchstatesinvolvedinrecognitionareinde-
pendentofeachother(Section5.6).

Forthereducer,thisthesissuggestsadifferentmechanismtoapplynegative
applicationconditions.Thismechanismmayalsobeusefulforrespective
theuserdiagrammingabettertoolsfeedbackwhichindothenotcaserelyofonanskerroneousetching,asitdiagrammayhelp(Sectionto8.4giv).e

interfAacemoreofourgeneralskissueetchingforfurtherapplication.work,Thenotfocusdiscussedofthissofthesisar,reonlygardsliestheinuserthe
usertechnicalinhiswaspectsorkisofskcrucialetching.totheHoovweveraller,asuccessmatureofuserskinterfetching.aceThisthatincludes,supportsforthe
eandxample,whatthetheuserquestioninterfacewhichprovidestypicalinworderorkotowsenableoccurinsuchawskorkoetchingwsinaeapplication,xible
andinterfacesnaturalformannerpen-based.ThisissuecomputersisandtightlyHCI.coupledwiththeresearchfieldofuser

AppendixA

DiagramofSpecificationLanguages

ThislanguageschaptershoillustratedwstheinChaptercomplete2.Forspecificationseachdiagramforallsixlanguageeisxamplesshownofthediagramspec-
ofificationTheshapes,comprisingprimitives(cf.Section1.2),constraints(cf.Sec-
tion5.1),andattachmentsareas(cf.Section7.1).
Thesettingsfortheconfigurationoptionsapplicableinthepostprocessing
step(cf.Sections6.2and6.3).
Therelationtypes(cf.Section7.2).
Theterminalandnonterminalsymbols.
Thereductionrules(cf.Section8.2).
Theproductionrules(cf.Sections9.1through9.4),andrulesforattribute
evaluation(cf.Section9.6).
Agraphicalrepresentationofthespecificationischosenwhereappropriate.
Fortextprimitives,thereissometimesgivenaregularexpressionwhichfurther
describesthetext.Forthespecificationofconstraintsthereisachoicebetween
allomorewmoreconstraints,freedomwhichindraleadwingtoashapes.moreWpreciesetendshape,touseandlessfewerconstraintsconstrinaints,orderwhichto
notover-constraindrawing.
Theshaperepresentedbyashapeedgeeisdenotedase.self().Forattribute
eHovwevaluationer,theremeaningfulareoftennamesarefunctionchosencallstoused,assurewhichareunderstandabilitynotfurther.Byeconxplained.ven-
tion,labelsofalledgesrepresentingterminalsymbolsstartwitht,whilelabels
ofalldistinguishedgesthenodesrepresentingvisitedbynonterminalanedgearesymbolsomittedstartifwiththeirn.Themappingnumbersisobusedvious.to

147

148

A.1

APPENDIXA.SPECIFICATIONOFDIAGRAMLANGUAGES

PNetsetri

ThissectionshowsthespecificationforPetrinets(cf.Section2.1).Thefinalresult

ofsketchprocessingisamodelofthesketchedPetrinet,ifsuchamodelcanbe

found.NotethattheexamplesgiveninChapters7through9sometimesdiffer

fromthespecificationinthissection,

aspects

of

the

approach

which

ouldw

whichhasbeennecessarytobetter

otherwise

not

become

vious.ob

describe

NETSPETRIA.1.

easarattachmentpolylineline1-line2-line3-line4,labeltrans

enokTShapeA.1.3esvprimitiarcarcfromfromtoptoptotorleftight,,quadrantquadrant2,1,counterclockwise,-clockwise,uniqueiduniquetopridighttopleft
arcarcfromfrombottombottomtotorleftight,,quadrantquadrant3,4,counterclockwise,-clockwise,uniqueiduniquebottomidleftbottomright

easarattachmentpolygontopleft-topright-bottomright-bottomleft,labeltoken

wArroShapeA.1.4esvprimitilinefromheadtosideA,arbitrarydirection,uniqueidlineA
linefromheadtosideB,arbitrarydirection,uniqueidlineB
linkfromheadtotail,uniqueidshaft
textatpolylineshaft,optional,regex\d+,uniqueidcost

constraintsdistancehead-tailgreaterthan80,softconstraint
distancehead-sideAgreaterthan50,softconstraint
distancehead-sideBgreaterthan50,softconstraint
distancehead-sideAlessthandistancehead-tail,hardconstraint
distancehead-sideBlessthandistancehead-tail,hardconstraint
anglesideA-head-tailgreaterthan20◦,hardconstraint
anglesideA-head-taillessthan70◦,hardconstraint
angletail-head-sideBgreaterthan20◦,hardconstraint
angletail-head-sideBlessthan70◦,hardconstraint

attachmenteasarpointhead,labelarrowEnd
pointtail,labelarrowEnd

ocessingostprPA.1.5uetr:=conflictsidentifyremovelargershapes:=false

149

150

A.1.6

fromfromA.APPENDIX

TRelationypes

place

TIONSPECIFICA

fortoktotoken,rigid,labelhastoken

,anstrtowEndarroatlabelrigid,not

fromarrowEndtoplace,notrigid,

A.1.7

terminal

arserP

symbols

Symbols

label

at

anstr

place

place

OF

GRAMDIA

GESALANGU

A.1.

PETRI

NETS

151

152

APPENDIX

A.

TIONSPECIFICA

OF

GRAMDIA

GESALANGU

A.2.

A.2

NASSI-SHNEIDERMAN

GRAMSDIA

Nassi-Shneiderman

Thissectionshowsthespecificationfor

The

final

result

of

etchsk

processing

is

Diagrams

arewhichs,NSD

the

pseudocode

illustrated

represented

in

Section

by

the

153

2.2.

etch.sk

154APPENDIXA.SPECIFICATIONOFDIAGRAMLANGUAGES

easarattachmentpoint1,labelcorner
point2,labelcorner
point3,labelcorner
point4,labelcorner

WhileShapeA.2.3esvprimitilinefrom1to2,horizontalright,uniqueidtop
linefrom1to5,verticaldown,uniqueidleft
linefrom5to6,horizontalright,uniqueidbottom
linefrom2to4,verticaldown,uniqueidright
linefrom3to4,horizontalright,uniqueidhori
linefrom3to6,verticaldown,uniqueidvert
textwithinclosedpolygontop-right-hori,uniqueidcondition

easarattachmentpoint1,labelcorner
point2,labelcorner
point3,labelcorner
point4,labelcorner
point5,labelcorner
point6,labelcorner

UntilShapeA.2.4esvprimitilinefrom1to2,horizontalright,uniqueidtop
linefrom1to5,verticaldown,uniqueidleft
linefrom5to6,horizontalright,uniqueidbottom
linefrom2to3,verticaldown,uniqueidvert
linefrom3to4,horizontalright,uniqueidhori
linefrom4to6,verticaldown,uniqueidright
textwithinclosedpolygonhori-right-bottom,uniqueidcondition

easarattachmentpoint1,labelcorner
point2,labelcorner
point3,labelcorner
point4,labelcorner

A.2.

pointGRAMSDIAASSI-SHNEIDERMANN

,5nercorlabel

point6,labelcorner

PA.2.5ocessingostpr

alsef:=conflictsidentify

removelargershapes:=true

ypesTRelationA.2.6

fromcornertocorner,notrigid,

A.2.7

terminal

arserP

symbols

Symbols

label

connect

155

156

A.2.8

APPENDIX

Reduction

A.

Rules

TIONSPECIFICA

OF

DIAGRAM

GESALANGU

A.2.

ASSI-SHNEIDERMANN

A.2.9

oductionPr

Rules

GRAMSDIA

157

158

APPENDIX

A.

TIONSPECIFICA

OF

GRAMDIA

GESALANGU

A.3.

A.3

GUI

UILDERB

BuilderGUI

Thissectionshowsthespecification

The.2.3Section

etchedsk

control

resultfinal

elements.

of

etchsk

for

the

GUI

processing

,uilderb

is

an

which

actual

is

dialog

159

illustrated

ainingcont

in

all

160APPENDIXA.SPECIFICATIONOFDIAGRAMLANGUAGES

linefromtrtobr,verticaldown,uniqueidright
textwithinpolygontop-left-bottom-right,uniqueidcaption

pointtlattachment,labelarelementeas

extfieldTShapeA.3.3

esvprimitilinefromtltotr,horizontalright,uniqueidtop
linefrombltobr,horizontalright,uniqueidbottom
linefromtltobl,verticaldown,uniqueidleft
linefromtrtobr,verticaldown,uniqueidright

pointtlattachment,labelarelementeas

xkboChecShapeA.3.4

esvprimitilinefromtltotr,horizontalright,uniqueidtop
linefrombltobr,horizontalright,uniqueidbottom
linefromtltobl,verticaldown,uniqueidleft
linefromtrtobr,verticaldown,uniqueidright
textatpolylinetextline,uniqueidlabel

computationpointpointwherewherexxisis22**trbr.x.x--btl.xl.x,,yyisistrbr.x,.x,uniqueuniqueididcctrbr
linefromctrtocbr,uniqueidtextline

constraintsdistancetl-bllessthan100,hardconstraint
distancetl-brlessthan100,hardconstraint

pointattachmenttl,labelarelementeas

BGUIA.3.UILDER

uttonRadiobShapeA.3.5esvprimitiarcfromtoptoleft,quadrant2,counter-clockwise,uniqueidtopleft
arcarcfromfromtopbottomtortoight,left,quadrantquadrant1,3,clockwise,clockwise,uniqueuniqueididtoprbottomightleft
arcfrombottomtoright,quadrant4,counter-clockwise,uniqueidbottomright
textatpointright,uniqueidlabel
constraintsdistanceleft-rightlessthan100,hardconstraint
pointattachmentleft,labelareaselement

xComboboShapeA.3.6esvprimitilinefromtltotm,horizontalright,uniqueidtopleft
linefromtmtotr,horizontalright,uniqueidtopright
linefrombltobm,horizontalright,uniqueidbottomleft
linefrombmtobr,horizontalright,uniqueidbottomright
linefromtltobl,verticaldown,uniqueidleft
linefrommltoml,verticaldown,uniqueidmiddle
linefromtrtobr,verticaldown,uniqueidright
textwithinpolygontopleft-middle-bottomleft-left,uniqueidcaption
pointtlattachment,labelareaselement

HorizontalSliderShapeA.3.7esvprimitilinefromtltotr,horizontalright,uniqueidtop
linefrombltobr,horizontalright,uniqueidbottom
linefromtltoml,verticaldown,uniqueidtopleft
linefrommltobl,verticaldown,uniqueidbottomleft
linefromtrtomr,verticaldown,uniqueidtopright
linefrommrtobr,verticaldown,uniqueidbottomright
linefrommltol,horizontalleft,uniqueidlefttrack
linefrommrtor,horizontalright,uniqueidrighttrack

161

162APPENDIXA.SPECIFICATIONOFDIAGRAMLANGUAGES

textatpointl,optional,uniqueidlabelMin
textatpointr,optional,uniqueidlabelMax

constraintsdistancetl-trlessthandistancetl-bl,hardconstraint

pointattachmenttl,labelarelementeas

erticalSliderVShapeA.3.8esvprimitilinefromtltotm,horizontalright,uniqueidtopleft
linefromtmtotr,horizontalright,uniqueidtopright
linefrombltobm,horizontalright,uniqueidbottomleft
linefrombmtobr,horizontalright,uniqueidbottomright
linefromtltobl,verticaldown,uniqueidleft
linefromtrtobr,verticaldown,uniqueidright
linefromtmtot,verticalup,uniqueidtoptrack
linefrombmtob,verticaldown,uniqueidbottomtrack
textatpointb,optional,uniqueidlabelMin
textatpointt,optional,uniqueidlabelMax

constraintsdistancetl-bllessthandistancetl-tr,hardconstraint

pointtlattachment,labelarelementeas

ocessingostprPA.3.9uetr:=conflictsidentifyremovelargershapes:=false

ypesTRelationA.3.10fromcontainertoelement,rigid,labelcontains

SymbolsarserPA.3.11symbolsterminal

A.3.

GUI

UILDERB

163

164

.shapew

:=

.captionw

APPENDIX

.self()s

:=

.captions

A.

TIONSPECIFICA

OF

GRAMDIA

GESALANGU

A.3.

GUI

UILDERB

165

166

A.4

APPENDIX

Statecharts

A.

TIONSPECIFICA

Thissectionshowsthespecificationfor

resultetchskof

can

be

found.

processing

is

a

model

of

OF

DIAGRAM

Section(cf.hartsstatec

the

etskched

statechart,

GESALANGU

).2.4

if

finalThe

such

a

model

A.4.TSTECHARAST

arcfrombottomtoleft,quadrant3,clockwise,uniqueidbottomleft
arcfrombottomtoright,quadrant4,counter-clockwise,uniqueidbottomright
arcfromttol,quadrant2,counter-clockwise,uniqueidtl
arcfromttor,quadrant1,clockwise,uniqueidtr
arcfrombtol,quadrant3,clockwise,uniqueidbl
arcfrombtor,quadrant4,counter-clockwise,uniqueidbr

constraintst.ythanless.ytopl.xthanlessleft.xright.xgreaterthanr.x
.ybthangreaterbottom.y

easarattachmentpolylinetopleft-topright-bottomright-bottomleft,labelborder

ransitionTShapeA.4.4

esvprimitilinefromheadtosideA,arbitrarydirection,uniqueidlineA
linefromheadtosideB,arbitrarydirection,uniqueidlineB
linkfromheadtotail,uniqueidshaft
textatpolylineshaft,optional,uniqueidlabel

constraintsdistancehead-tailgreaterthan80,softconstraint
distancehead-sideAgreaterthan50,softconstraint
distancehead-sideBgreaterthan50,softconstraint
distancehead-sideAlessthandistancehead-tail,hardconstraint
distancehead-sideBlessthandistancehead-tail,hardconstraint
anglesideA-head-tailgreaterthan20◦,hardconstraint
anglesideA-head-taillessthan70◦,hardconstraint
angletail-head-sideBgreaterthan20◦,hardconstraint
angletail-head-sideBlessthan70◦,hardconstraint

easarattachmentpointhead,labeltrans
pointtail,labeltrans

167

168

APPENDIXA.SPECIFICATIONOFDIAGRAMLANGUAGES

ocessingostprPA.4.5

uetr:=conflictsidentifyremovelargershapes:=false

ypesTRelationA.4.6

fromarea(s1)toborder(s2),rigid,labelcontains,
wheres2.width>s1.widthconditions1.widthiss1.tr.x-s1.tl.x,
s2.widthiss2.tr.x-s2.tl.xifs2isastate,
s2.widthiss2.right.x-s2.left.xifs2isaninitial
fromtranstoborder,notrigid,labelat

arserPA.4.7Symbols

symbolsterminal

chartstaterepresentedtheforuteattribsemanticchart,staterepresentedtheforstatesrepresentedtheforstatesrepresentedtheforstaterepresentedtheforstaterepresentedthefor169

TSTECHARASTA.4.

attributesofthenonterminalsymbols

.statestaten

.statestatenestn

statesn.states

.statesstatesnestn

tt.charcharn

tt.charchar

nestn

A.4.8

Reduction

Rules

170

APPENDIX

A.

SPECIFICATION

OF

GRAMDIA

GESALANGU

A.4.

ASTTSTECHAR

171

172

APPENDIX

A.

TIONSPECIFICA

OF

DIAGRAM

GESALANGU

A.4.

TSTECHARAST

173

174

A.5

A.APPENDIX

TIONSPECIFICA

DiagramsLogicBoolean

Thissectionshowsthespecificationfor

The

final

result

of

etchsk

processing

is

OF

GRAMDIA

ALANGUGES

illustratedarewhichs,BLD

a

boolean

logic

expression.

in

Section

.2.5

GRAMSDIALOGICBOOLEANA.5.

bleBubShapeA.5.3esvprimitiarcarcfromfromtoptoptotorleftight,,quadrantquadrant2,1,counterclockwise,-clockwise,uniqueiduniquetopridighttopleft
arcarcfromfrombottombottomtotorleftight,,quadrantquadrant3,4,clockwise,counter-clockwise,uniqueiduniquebottomidleftbottomright

easarattachmentpointleft,labelbubbleInput
pointright,labeloutput

LinkShapeA.5.4esvprimitilinkfromatob,uniqueidshaft
textatpointa,optional,regex[a-zA-Z].*,uniqueidnameA
textatpointb,optional,regex[a-zA-Z].*,uniqueidnameB

easarattachmentlinkEndlabel,apointpointlinkEndlabel,b

ocessingostprPA.5.5uetr:=conflictsidentifyremovelargershapes:=false

ypesTRelationA.5.6fromlinkEndtoinput,notrigid,labelinputLink
fromoutputtolinkEnd,notrigid,labeloutputLink
fromoutputtobubbleInput,notrigid,labelhasBubble

SymbolsarserPA.5.7symbolsterminal

175

176

nonterminalAPPENDIX

symbolsA.

(startTIONSPECIFICA

symbolisn

star

t

)OF

GRAMDIA

LANGUGESA

A.5.

BOOLEAN

LOGIC

GRAMSDIA

177

178

APPENDIX

A.

TIONSPECIFICA

OF

GRAMDIA

GESALANGU

A.5.

BOOLEAN

LOGIC

GRAMSDIA

179

180

A.6

APPENDIX

ic-tac-toeT

A.

TIONSPECIFICA

Thissectionshowsthespecificationfor

result

of

etchsk

processing

is

a

statement

OF

GRAMDIA

GESALANGU

Tic-tac-toe(cf.Section2.6).

about

the

etchedsk

ameg

The

situation.

final

C-TATIC-TA.6.OE

GridShapeA.6.3esvprimitilinelinefromfromcurcultotocurcdr,,verticalhorizontalright,down,uniqueuniqueidlcuidlcr
linefromcdrtocdl,verticalleft,uniqueidlcd
linefromcdltocul,horizontalup,uniqueidlcl
linefromcultoul,horizontalup,uniqueidlul
linelinefromfromcurcdltotodlur,,horizontalhorizontaldoup,wn,uniqueuniqueididlurldl
linefromcdrtodr,horizontaldown,uniqueidldr
linefromcultolu,verticalleft,uniqueidllu
linefromcdltold,verticalleft,uniqueidlld
linefromcurtoru,verticalright,uniqueidlru
linefromcdrtord,verticalright,uniqueidlrd

computationpointwherexislu.x,yisul.x,uniqueidcul
pointwherexisru.x,yisur.x,uniqueidcur
pointwherexisld.x,yisdl.x,uniqueidcdl
pointwherexisrd.x,yisdr.x,uniqueidcdr
linefromurtocur,uniqueidcuru
linefromdrtocdr,uniqueidcdrd
linefromdltocdl,uniqueidcdld
linefromultocul,uniqueidculu

easarattachmentboardlabel,lul-lcu-lurpolygonpolygoncuru-lur-lru,labelboard
polygonlru-lcr-lrd,labelboard
polygonlrd-ldr-cdrd,labelboard
boardlabel,ldr-lcd-ldlpolygonpolygonlld-ldl-cdld,labelboard
boardlabel,llu-lcl-lldpolygonpolygonculu-lul-llu,labelboard
boardlabel,lcu-lcr-lcd-lclpolygon

ocessingostprPA.6.4uetr:=conflictsidentifyremovelargershapes:=false

181

GESALANGU

GRAMDIA

OF

TIONSPECIFICA

A.

APPENDIX

182

ypesTRelation

A.6.5

at

boardtokmar

Symbols

arserP

A.6.6

terminal

symbols

labelrigid,,from

A.6.

TIC-TOEC-TA

183

184

APPENDIX

A.

TIONSPECIFICA

OF

GRAMDIA

GESALANGU

ppendixA

B

CompleteThe

Concept

Thefigureonthenextpageshowsallprocessingunitsanddatastructurescom-

prisingthecompleteprocessingchain.Thismeansthatitmergesallfiguresthat

showonlypartiallytheprocessingchain.Notethatthespecificationisshowntwo

times

for

the

esak

of

a

simpler

layout

.only

185

186

APPENDIX

B.

THE

COMPLETE

CONCEPT

CppendixA

ExampleDetailed

Thischaptergivesanimpressionofhowarealsketchisprocessedbytheimple-
mentation.FigureC.1showsasimplePetrinetwhichisusedasrunningexample.
Thefollowingtwosectionsdescribetheprocessingresultsobtainedbytherecog-
nitionstageandtheanalysisstage.Notethatallfiguresinthischapterareeither
screenshotsfromtheimplementation,orexactreproductions.

FigureC.1:AsimplePetrinetusedasrunningexample.

187

188

StageRecognitionC.1

AILEDDETC.APPENDIXEXAMPLE

Thefirststepintherecognitionstageispreprocessingbythetransformers.They
yieldthefivedifferentmodelsillustratedinChapter4.FigureC.2showsthefive
models.

modelline(a)

modellink(c)

modelxtte(e)

modelarc(b)

circle(d)model

FigureC.2:ContentsofthemodelsgeneratedforthesketchshowninFigureC.1.
Thesketchitselfisgrayedout.

C.1.

RECOGNITIONGEAST

189

Theassemblerrecognizes26shapesfromthedatacontainedinthemodels:

twotransitions,nineplaces,ninetokens,andsixarrows.

26shapes.However,aseachcircleisrecognizedasboth

figureonlyshowsplacesinorder

places,

do

not

consist

of

yan

xt.te

to

be

less

cluttered

up.

thesewsshoC.3Figure

aplaceandatoken,the

Note

that

ens,tok

eunlik

190

AILEDDETC.APPENDIXEXAMPLE

Therecognitionstagesfinalstepispostprocessing.Ithastwotasksinthecase

ofPetrinets:removalofduplicatesandidentificationofconicts.Theresultof

thisstepisshowninFigureC.4.Asbefore,dashedlinesindicateconicts.Itcan

beseenthattheremovalofduplicatescutsthenumberofshapesinhalf,resulting

in13shapesthatarepassedontotheanalysisstep.Comparedtothenineshapes

thatmaketheoriginalsketch,13isagoodfigure.Thefourextrashapesare

alselyf

en.tok

recognized

,warro

otw

enstok

similar

to

places,

and

one

place

similar

one

to

a

C.2.

C.2

ANALYSISSTAGE

StageAnalysis

Inthefirststepoftheanalysisstage,

ure

the

C.5.Thefigureadditionallyshows

sfigure

structure

is

eryv

similar

to

191

themodelercreatestheHMshowninFig-

attribtheallofutes

that

of

Figure

.C.4

shape

edges.

,viouslyOb

192

EXAMPLEAILEDDETC.APPENDIX

ThereducerthenprocessestheHMandproducestheRHMshowninFig-

ureC.6.Indoingso,thenumberofedgesisreducedfrom23toten,andthe

numberofnodesisreducedfrom21tofive.InsteadofsixconictsintheHM,

thereisonlyoneintheRHM.Thereasonisthatsomeoftheconictingedgesare
notreduced.ThetokenTo2isnotreducedbecauseitisnotcontainedina(larger)
place,andsoisTo3.ArrowA5isnotreducedbecauseitdoesnotconnectaplace

notplace,reduced.andsoisTheTo3tok.

and

a

transition.

notisA5

notis

reducednot

reducedbecause
reduced

becauseitis
because

notit

not
containeddoes

containednot

containedina
connect

(lara

(larger)
place

C.2.ANALYSISSTAGE

193

conictFigurebetweenC.7shop3wsandthetoderiisvcarriedationoDvAerGtothatN1isandN2computed.Afterbythethestartparser.symbolThe
N8isconsiderablyreached,lessN1thanistheremovedweightedfromtheratingsetofN2,production,astheaslatteitsrhasaweightedgreaterratingratingis
andoneofitschildrenispartofthecontextoftwoembeddededges(a1anda2).
Accordingly,theratingsofN6andN8donotincludetheratingofN1.ForN8
thevaluesinparenthesesincludethefourembeddedarrows.

194

EXAMPLEAILEDDETC.APPENDIX

bolN8Basedisevonthealuated.DAGThisshowncaninbeFigureaccomplishedC.7thebysemanticthefolloattribwinguteeofvthealuationstartorder:sym-

N3.modelN2.model:=:=createPlaceWithTcreatePlace(p2.shape)oken(p1.shape)
N5.modelN4.model:=:=createTcreateTrransition(t2.shape)ansition(t1.shape)
N6.set:={N2,N3}
N7.set:={N4,N5}
N7.set)createNet(N8.set,:=N8.net

addArroaddArrow(t1.shapew(p1.shape,,a1.shapea2.shape,,p1.shape)t2.shape)
addArroaddArrow(t2.shapew(p2.shape,,a4.shapea3.shape,,p2.shape)t1.shape)

netcouldDependingbeonobtained.howAthetextualillustratedrepresentationfunctionsmaycallslookwork,likeathis:modelofthePetri

Petrinet,2places,2transitions
====================Place”placeA”,capacity5,containsatoken
”placeB”PlaceansA””transitionrTansB””transitionrTArrowfrom”transB”to”placeA”
Arrowfrom”placeA”to”transA”
Arrowfrom”transA”to”placeB”,cost2
Arrowfrom”placeB”to”transB”,cost3
====================

Bibliography

[1]A.V.AhoandJ.D.Ullman.TheTheoryofParsing,Translation,and
Compiling,VolumeI:Parsing.PrenticeHall,1972.

[2]C.sachusettsAlvarado.InstituteofMulti-DomainTechnologySk,etchCambridge,UnderstandingMA,.USA,PhD2004.thesis,Mas-

[3]C.AlvaradoandR.Davis.Resolvingambiguitiestocreateanatural
computerternationalJ-basedointskConferetchingenceenonvironment.ArtificialInIntelligPrenceoceedings(IJCAIofthe01),17thpagesIn-
2001.August1365–1374,

[4]C.AlvaradoandR.Davis.SketchREAD:amulti-domainsketchrecogni-
tionInterfaceengine.SoftwarInPreandoceedingsTecofhnolothegy17th(UISTAnnual04),ApagesCM23–32,SymposiumNewonYUserork,
NY,USA,2004.ACM.

[5]C.AlvaradoandR.Davis.Dynamicallyconstructedbayesnetsformulti-
JointdomainConfersketchenceonunderstanding.ArtificialInIntelligPrenceoceedings(IJCAIof05)the,19thpagesInternational1407–1412.
2005.,CenterBookProfessional

[6]A.shapes:Apte,anV.eVo,xperimentalandT.eD.vKimualuation.ra.InPrRecognizingoceedingsofthemultistrok6theAnnualgeometricACM
121–128,SymposiumNeonwYUserork,NY,InterfaceUSA,Softwar1993.eAandCM.Technology(UIST93),pages

[7]J.draArvwnographs.andK.InPrNovins.oceedingsofthe3rAppearance-preservingdInternationalConfermanipulationenceofonCom-hand-
AsiaputerGr(GRAPHITEaphicsand05),InterpagesactiveT61–68,ecNehniqueswYinork,AustrNY,alasiaUSA,and2005.SouthACM.East

[8]S.-H.possibleBae,skR.etchingBalakrishnan,systemforandcreatingK.3dSingh.curveILomvodels.eSketch:InProceedingsas-natural-as-of

195

196

BIBLIOGRAPHY

othegy21st(UISTAnnual08),ApagesCM151–160,SymposiumNeonwYUserork,NYInterface,USA,Softwar2008.eAandCM.Technol-

[9]C.Berge.GraphsandHypergraphs.NorthHolland,Amsterdam,the
1973.Netherlands,

[10]C.M.Bishop,M.Svensen,andG.E.Hinton.Distinguishingtextfrom
WgraphicsorkshopinonFon-linerontiersinhandwrittenHandwritingink.InPrRecooceedingsgnitionofthe(IWFHR9th04),Internationalpages
142–147,Washington,DC,USA,2004.IEEEComputerSociety.

[11]D.Blostein.Generaldiagram-recognitionmethodologies.InSelectedPa-
persfromthe1stInternationalWorkshoponGraphicsRecognition.Meth-
odsandApplications,pages106–122,London,UK,1996.Springer-Verlag.

[12]D.linediBlostein,agramE.Lank,recognition.A.InRose,andSelectedR.PaperZanibbi.sfromUserthe4thinterfacesInternationalforon-
W01),orkshoppagesonGr92–103,aphicsLondon,RecoUK,gnition2002.AlgorithmsSpringer-Vanderlag.Applications(GREC
¨[13]VC.erBonggleich.artz.UnivUbersichtersit¨at¨deruberSkBundeswehretching:M¨aktuelleunchen,Ans¨2008.atzeundDiplomaSystemethesis,im
UniBwM-ID14/2007,onlyavailableinGerman.

[14]A.sketchingCaetano,theN.lookGoulart,ofuserM.Finterfonseca,aces.InandPJ.aperJorsfrge.omJavtheaSk2002etchIt:AAAIIssuesSpringin
SymposiumonSketchUnderstanding,pages9–14,MenloPark,CA,USA,
Press.AAAI2002.

[15]C.Calhoun,T.F.Stahovich,T.Kurtoglu,andL.B.Kara.Recognizing
multi-strokesymbols.InPapersfromthe2002AAAISpringSymposiumon
SketchUnderstanding,pages15–23.AAAIPress,MenloPark,USA,2002.

[16]G.Casella,G.Costagliola,V.Deufemia,M.Martelli,andV.Mascardi.
Anagent-basedframeworkforcontext-driveninterpretationofsymbolsin
diagrammaticsketches.InProceedingsoftheIEEESymposiumonVisual
LanguagesandHuman-CentricComputing(VL/HCC06),pages73–80,
Washington,DC,USA,2006.IEEEComputerSociety.

[17]G.Casella,V.Deufemia,andV.Mascardi.Amulti-agentsystemforhand-
ferdrawnenceondiagramDocumentrecognition.AnalysisPrandoceedingsRecognitionofthe(ICD9thAR07)International,2:739–743,Con-
2007.September

BIBLIOGRAPHY

197

[18]G.Casella,V.Deufemia,V.Mascardi,G.Costagliola,andM.Martelli.
Anagent-basedframeworkforsketchedsymbolinterpretation.Journalof
VisualLanguages&Computing,19(2):225–257,2008.

[19]R.tabletChung,PC.InP.PrMirica,oceedingsandB.ofthePlimmer6thA.CMInkKit:SIGCHIagenericNewdesZealandigntoolChaptforerthes
pagesInternational29–30,NeConferwYork,enceNYon,USA,Computer2005.A-humanCM.Interaction(CHINZ05),

[20]G.Costagliola,V.Deufemia,G.Polese,andM.Risi.Aparsingtechnique
forsiumskonetchVisualrecognitionLanguagessystems.andInHumanProceedingsCentricoftheComputing2004IEEE(VL/HCCSympo-04),
pages19–26,Washington,DC,USA,2004.IEEEComputerSociety.

[21]G.Costagliola,V.Deufemia,andM.Risi.Sketchgrammars:Aformalism
fordescribingandrecognizingdiagrammaticsketchlanguages.InPro-
ceedingsofthe8thInternationalConferenceonDocumentAnalysisand
Recognition(ICDAR05),pages1226–1231,Washington,DC,USA,2005.
.SocietyComputerIEEE

[22]G.Costagliola,V.Deufemia,andM.Risi.Atrainablesystemforrecog-
nizingdiagrammaticsketchlanguages.InProceedingsofthe2005IEEE
SymposiumonVisualLanguagesandHuman-CentricComputing(VL/HCC
05),pages281–283,Washington,DC,USA,2005.IEEEComputerSoci-
.ety

[23]G.Costagliola,V.Deufemia,andM.Risi.Amulti-layerparsingstrat-
egyforon-linerecognitionofhand-drawndiagrams.InProceedingsof
theIEEESymposiumonVisualLanguagesandHuman-CentricComputing
(VL/HCC06),pages103–110,Washington,DC,USA,2006.IEEECom-
.Societyputer

[24]G.Costagliola,V.Deufemia,andM.Risi.Usingerrorrecoverytechniques
toimprovesketchrecognitionaccuracy.InW.Liu,J.Llad´os,andJ.-M.
Ogier,editors,Proceedingsofthe7thInternationalWorkshoponGraphics
Recognition.RecentAdvancesandNewOpportunities(GREC07),vol-
ume5046ofLectureNotesinComputerScience,pages157–168.Springer,
2007.September

[25]G.Costagliola,V.Deufemia,andM.Risi.Usinggrammar-basedrecog-
nizersforsymbolcompletionindiagrammaticsketches.InProceedingsof
the9thInternationalConferenceonDocumentAnalysisandRecognition

198

BIBLIOGRAPHY

(ICDAR07),volume2,pages1078–1082,Washington,DC,USA,2007.
.SocietyComputerIEEE[26]G.Costagliola,R.Francese,M.Risi,G.Scanniello,andA.D.Lucia.A
component-basedvisualenvironmentdevelopmentprocess.InProceedings
ofthe14thInternationalConferenceonSoftwareEngineeringandKnowl-
edgeEngineering(SEKE02),pages327–334,NewYork,NY,USA,2002.
CM.A[27]G.Costagliola,A.D.Lucia,andS.Orefice.Towardsefficientparsingof
diagrammaticlanguages.InProceedingsoftheWorkshoponAdvanced
VisualInterfaces(AVI94),pages162–171,NewYork,NY,USA,1994.
CM.A[28]G.Costagliola,A.D.Lucia,S.Orefice,andG.Polese.Aclassification
frameworktosupportthedesignofvisuallanguages.JournalofVisual
Languages&Computing,13(6):573–600,2002.
[29]G.CostagliolaandG.Polese.Extendedpositionalgrammars.InPro-
ceedingsofthe2000IEEEInternationalSymposiumonVisualLanguages
(VL00),pages103–110,Washington,DC,USA,2000.IEEEComputer
.Society[30]A.Coyette,S.Kieffer,andJ.M.Vanderdonckt.Multi-fidelityprototyping
ofuserinterfaces.InProceedingsofthe13thInternationalConferenceon
Human-ComputerInteraction(INTERACT07),volume4662ofLecture
NotesinComputerScience,pages150–164.Springer,September2007.
[31]A.CoyetteandJ.M.Vanderdonckt.Asketchingtoolfordesigninganyuser,
anyplatform,anywhereuserinterfaces.InProceedingsofthe12thInter-
nationalConferenceonHuman-ComputerInteraction(INTERACT05),
pages550–564.SpringerVerlag,2005.
[32]A.Coyette,J.M.Vanderdonckt,andQ.Limbourg.SketchiXML:Adesign
toolforinformaluserinterfacerapidprototyping.InProceedingsofthe
3rdInternationalWorkshoponRapidIntegrationofSoftwareEngineering
Techniques(RISE06),pages160–176.Springer,September2006.
[33]J.Davis,M.Agrawala,E.Chuang,Z.Popovi´c,andD.Salesin.Asketching
interfaceforarticulatedfigureanimation.InProceedingsofthe2003ACM
SIGGRAPH/EurographicsSymposiumonComputerAnimation(SCA03),
pages320–328,Aire-la-Ville,Switzerland,Switzerland,2003.Eurograph-
Association.ics

BIBLIOGRAPHY

199

[34]J.deLaraandH.Vangheluwe.AToM3:Atoolformulti-formalismand
meta-modelling.InProceedingsofthe5thInternationalConferenceon
FundamentalApproachestoSoftwareEngineering(FASE02),pages174–
188,London,UK,2002.Springer.
[35]P.DomingosandM.Pazzani.Beyondindependence:Conditionsforthe
optimalityofthesimplebayesianclassifier.InProceedingsofthe13th
InternationalConferenceonMachineLearning(ICML96),pages105–
112.MorganKaufmann,1996.
[36]K.Ehrig,C.Ermel,S.H¨ansgen,andG.Taentzer.Generationofvisual
editorsaseclipseplug-ins.InProceedingsofthe20thIEEE/ACMInter-
nationalConferenceonAutomatedSoftwareEngineering(ASE05),pages
134–143,NewYork,NY,USA,2005.ACMPress.
[37]T.Fischer,J.Niere,L.Torunski,andA.Z¨undorf.Storydiagrams:Anew
graphrewritelanguagebasedontheunifiedmodelinglanguageandjava.
InSelectedPapersfromthe6thInternationalWorkshoponTheoryandAp-
plicationofGraphTransformations(TAGT98),pages296–309,London,
.Springer2000.UK,[38]M.J.Fonseca,C.Pimentel,andJ.A.Jorge.CALI:anonlinescribble
recognizerforcalligraphicinterfaces.InPapersfromthe2002AAAISpring
SymposiumonSketchUnderstanding,pages51–58,MenloPark,CA,USA,
Press.AAAI2002.[39]I.J.FreemanandB.Plimmer.Connectorsemanticsforsketcheddiagram
recognition.InProceedingsofthe8thAustralasianUserInterfaceCon-
ference(AUIC07),pages71–78,Darlinghurst,Australia,Australia,2007.
Inc.,SocietyComputerAustralian[40]L.Gennari,L.B.Kara,T.F.Stahovich,andK.Shimada.Combininggeom-
etryanddomainknowledgetointerprethand-drawndiagrams.Computers
&Graphics,29(4):547–562,2005.
[41]M.C.Golumbic.AlgorithmicGraphTheoryandPerfectGraphs,Second
Edition(AnnalsofDiscreteMathematics,Vol.57).North-HollandPublish-
ingCo.,Amsterdam,theNetherlands,2004.
[42]M.D.GrossandE.Y.-L.Do.Ambiguousintentions:apaper-likeinterface
forcreativedesign.InProceedingsofthe9thAnnualACMsymposiumon
UserInterfaceSoftwareandTechnology(UIST96),pages183–192,New
York,NY,USA,1996.ACM.

200

BIBLIOGRAPHY

[43]M.D.GrossandE.Y.-L.Do.Drawingonthebackofanenvelope:a
frameworkforinteractingwithapplicationprogramsbyfreehanddrawing.
Computers&Graphics,24(6):835–849,2000.
[44]J.GrundyandJ.Hosking.Supportinggenericsketching-basedinputof
diagramsinadomain-specificvisuallanguagemeta-tool.InProceedings
ofthe29thInternationalConferenceonSoftwareEngineering(ICSE07),
pages282–291,Washington,DC,USA,May2007.IEEEComputerSoci-
.ety[45]J.Grundy,J.Hosking,N.Zhu,andN.Liu.Generatingdomain-specific
visuallanguageeditorsfromhigh-leveltoolspecifications.InProceedings
ofthe21stIEEE/ACMInternationalConferenceonAutomatedSoftware
Engineering(ASE06),pages25–36,Washington,DC,USA,2006.IEEE
.SocietyComputer[46]T.HammondandR.Davis.Ladder:Alanguagetodescribedrawing,dis-
play,andeditinginsketchrecognition.InProceedingsofthe18thIn-
ternationalJointConferenceonArtificialIntelligence(IJCAI03),pages
2003.August461–467,[47]T.HammondandR.Davis.Automaticallytransformingsymbolicshape
descriptionsforuseinsketchrecognition.InThe19thNationalConference
onArtificialIntelligence(AAAI04),MenloPark,CA,USA,July2004.
Press.AAAI[48]T.HammondandR.Davis.LADDER,asketchinglanguageforuserinter-
facedevelopers.Computers&Graphics,29(4):518–532,2005.
[49]T.A.Hammond.RecognizingFree-formHand-sketchedConstraintNet-
workDiagramsbyCombiningGeometryandContext.PhDthesis,Mas-
sachusettsInstituteofTechnology,Cambridge,MA,USA,2007.
[50]T.A.HammondandB.OSullivan.Ladder:aperceptually-basedlanguage
tosimplifysketchrecognitionuserinterfacedevelopment.InEurographics
Ireland,pages67–74,December2007.
[51]R.Heckel.Graphtransformationinanutshell.ElectronicNotesinTheo-
reticalComputerScience,148(1):187–198,February2006.
[52]J.I.HongandJ.A.Landay.SATIN:atoolkitforinformalink-basedap-
plications.InProceedingsofthe13thAnnualACMSymposiumonUser
InterfaceSoftwareandTechnology(UIST00),pages63–72,NewYork,
NY,USA,2000.ACM.

BIBLIOGRAPHY

201

[53]H.HseandA.R.Newton.Sketchedsymbolrecognitionusingzernike
moments.InProceedingsofthe17thInternationalConferenceonPattern
Recognition(ICPR04),volume1,pages367–370,Washington,DC,USA,
.SocietyComputerIEEE2004.[54]J.Hu,M.K.Brown,andW.Turin.HMMbasedon-linehandwritingrecog-
nition.IEEETransactionsonPatternAnalysisandMachineIntelligence,
1996.18(10):1039–1045,[55]J.Hu,S.G.Lim,andM.K.Brown.Writerindependenton-linehandwriting
recognitionusinganHMMapproach.PatternRecognition,33(1):133–147,
2000.[56]T.IgarashiandJ.F.Hughes.Clothingmanipulation.InProceedingsofthe
15thAnnualACMSymposiumonUserInterfaceSoftwareandTechnology
(UIST02),pages91–100,NewYork,NY,USA,2002.ACM.
[57]T.Igarashi,S.Matsuoka,andH.Tanaka.Teddy:asketchinginterfacefor
3Dfreeformdesign.InProceedingsofthe26thAnnualConferenceon
ComputerGraphicsandInteractiveTechniques(SIGGRAPH99),pages
409–416,NewYork,NY,USA,1999.ACMPress/Addison-WesleyPub-
Co.lishing[58]P.Isokoski.Performanceofmenu-augmentedsoftkeyboards.InProceed-
ingsoftheSIGCHIConferenceonHumanFactorsinComputingSystems
(CHI04),pages423–430,NewYork,NY,USA,2004.ACM.
[59]J.A.Jorge,M.J.Fonseca,andF.M.G.Pereira.Visualsyntaxanalysisfor
calligraphicinterfaces.In13◦EncontroPortuguesdeComputacaoGrafica,
2005.October[60]R.Karp.Reducibilityamongcombinatorialproblems.InR.Millerand
J.Thatcher,editors,ComplexityofComputerComputations.PlenumPress,
1972.ork,YwNe[61]J.A.Landay.InteractiveSketchingfortheEarlyStagesofUserInterface
Design.PhDthesis,CarnegieMellonUniversity,Pittsburgh,PA,USA,
1996.December[62]J.A.LandayandB.A.Myers.Interactivesketchingfortheearlystages
ofuserinterfacedesign.InProceedingsoftheSIGCHIConferenceon
HumanFactorsinComputingSystems(CHI95),pages43–50,NewYork,
NY,USA,1995.ACMPress/Addison-WesleyPublishingCo.

202

BIBLIOGRAPHY

[63]J.A.LandayandB.A.Myers.Sketchinginterfaces:Towardmorehuman
interfacedesign.Computer,34(3):56–64,2001.
[64]W.Lee,L.B.Kara,andT.F.Stahovich.Anefficientgraph-basedsymbol
recognizer.InProceedingsofthe3rdEurographicsWorkshoponSketch-
basedInterfacesandModeling(SBIM06),pages11–18,NewYork,NY,
CM.A2006.USA,[65]J.Lin,M.W.Newman,J.I.Hong,andJ.A.Landay.DENIM:findinga
tighterfitbetweentoolsandpracticeforwebsitedesign.InProceedings
oftheSIGCHIConferenceonHumanFactorsinComputingSystems(CHI
00),pages510–517,NewYork,NY,USA,2000.ACM.
[66]J.MankoffandG.D.Abowd.Cirrin:aword-levelunistrokekeyboardfor
peninput.InProceedingsofthe11thAnnualACMSymposiumonUser
InterfaceSoftwareandTechnology(UIST98),pages213–214,NewYork,
NY,USA,1998.ACM.
[67]J.Mankoff,G.D.Abowd,andS.E.Hudson.OOPS:atoolkitsupporting
mediationtechniquesforresolvingambiguityinrecognition-basedinter-
faces.Computers&Graphics,24(6):819–834,2000.
[68]M.Minas.SpezifikationundGenerierunggraphischerDiagrammeditoren.
Shaker-Verlag,Aachen,Germany,2001.ProfessorialdissertationatUni-
versit¨atErlangen-N¨urnberg,2000.
[69]M.Minas.Conceptsandrealizationofadiagrameditorgeneratorbasedon
hypergraphtransformation.JournalofScienceofComputerProgramming,
SpecialIssueonApplicationsofGraphTransformations,44(2):157–180,
2002.[70]M.Minas.Specifyinggraph-likediagramswithDiaGen.InT.Mens,
A.Sch¨urr,andG.Taentzer,editors,Proceedingsofthe1stInternational
WorkshoponGraph-BasedTools(GraBaTs02),volume72ofElectronic
NotesinTheoreticalComputerScience,pages102–111,Amsterdam,2002.
ElsePublishers.Sciencevier[71]M.Minas.Generatingmeta-model-basedfreehandeditors.InElectronic
CommunicationsoftheEASST(GraBaTs06),September2006.
[72]M.Nakai,T.Sudo,H.Shimodaira,andS.Sagayama.Penpressurefeatures
forwriter-independenton-linehandwritingrecognitionbasedonsubstroke
HMM.InProceedingsofthe16thInternationalConferenceonPattern

BIBLIOGRAPHY

203

Recognition(ICPR02),volume3,page30220,Washington,DC,USA,
.SocietyComputerIEEE2002.

[73]I.NassiandB.Shneiderman.Flowcharttechniquesforstructuredprogram-
ming.SIGPLANNotices,8(8):12–26,August1973.

[74]M.Oltmans,C.Alvarado,andR.Davis.ETCHAsketches:Lessonslearned
andfromNaturcollectingal(AAAIsketchFalldata.InSymposium)Making,Ppagesen-Based134–140,InterMenloactionPark,IntelligCA,ent
Press.AAAI2004.OctoberUSA,

[75]R.Patel,B.Plimmer,J.Grundy,andR.Ihaka.Inkfeaturesfordiagram
basedrecognition.InterfacesInPrandoceedingsModelingofthe(SBIM4th07)Eur,ogrpagesaphics131–138,WorkshopNewonYork,SketcNYh-,
Press.CMA2007.USA,

[76]B.PaulsonandT.Hammond.PaleoSketch:accurateprimitivesketch
ConferrecognitionenceonandIntelligentbeautification.UserInInterfacesProceedings(IUI08)of,thepages13th1–10,NewInternationalYork,
NY,USA,2008.ACM.

[77]B.Paulson,P.Rajan,P.Davalos,R.Gutierrez-Osuna,andT.Hammond.
What!?!norubinefeatures?:usinggeometric-basedfeaturestopro-
ducenormalizedconfidencevaluesforsketchrecognition.InWorkshop
onSketchToolsforDiagramming(VL/HCC08),pages57–63,Septem-
ber2008.https://www.cs.auckland.ac.nz/research/conferences/skekchws/
.proceedings.html

[78]K.Perlin.Quikwriting:continuousstylus-basedtextentry.InProceed-
Tingsecofhnolothegy11th(UISTAnnual00),ApageCMs215–216,SymposiumNeonwYUserork,NY,InterfaceUSA,Softwar1998.eACMand
Press.

[79]B.PlimmerandI.Freeman.Atoolkitapproachtosketcheddiagramrecog-
nition.InProceedingsofthe21stBritishHCIGroupAnnualConference
(HCI07),pages205–213,September2007.

[80]B.tent:PlimmerissuesandandeJ.xperiences.Grundy.InPrBeautifyingoceedingsskoftheetching-based6thAustrdesignalasiantoolUsercon-
InterfaceAustralia,2005.ConferenceAustralian(AUIC05)Computer,pagesSociety,31–38,Inc.Darlinghurst,Australia,

204

BIBLIOGRAPHY

[81]P.RajanandT.Hammond.Frompapertomachine:Extractingstrokes
fromimagesforuseinsketchrecognition.InProceedingsofthe5thEuro-
graphicsWorkshoponSketch-basedInterfacesandModeling(SBIM08),
NewYork,NY,USA,June2008.ACM.
[82]G.Rozenberg,editor.HandbookofGraphGrammarsandComputingby
GraphTransformation,VolumeI:Foundations.WorldScientificPublishing
Co.,Inc.,RiverEdge,NJ,USA,1997.
[83]D.Rubine.Specifyinggesturesbyexample.Proceedingsofthe18thAn-
nualConferenceonComputerGraphicsandInteractiveTechniques(SIG-
1991.25(4):329–337,,91)GRAPH[84]D.H.Rubine.Theautomaticrecognitionofgestures.PhDthesis,Carnegie
MellonUniversity,Pittsburgh,PA,USA,1992.
[85]E.SaundandE.Lank.Stylusinputandeditingwithoutpriorselection
ofmode.InProceedingsofthe16thAnnualACMSymposiumonUser
InterfaceSoftwareandTechnology(UIST03),pages213–216,NewYork,
NY,USA,2003.ACM.
[86]P.Schmieder,B.Plimmer,andJ.Vanderdonckt.Cross-domaindia-
gramsketchrecognition.InWorkshoponSketchToolsforDiagramming
(VL/HCC08),pages64–73,September2008.https://www.cs.auckland.
.ekchws/proceedings.htmlac.nz/research/conferences/sk[87]A.Schramm.¨UbersichtundKlassifizierungvonFeaturesf¨urFeature-
basierteErkennungssysteme.Universit¨atderBundeswehrM¨unchen,2008.
Bachelorthesis,UniBwM-IS02/2008,onlyavailableinGerman.
[88]M.Schramm.VergleichverschiedenerTexteingabem¨oglichkeitenf¨ur
Sketchingsysteme.Universit¨atderBundeswehrM¨unchen,2008.Bache-
lorthesis,UniBwM-IS03/2008,onlyavailableinGerman.
[89]T.M.Sezgin.Featurepointdetectionandcurveapproximationforearly
processingoffree-handsketches.Mastersthesis,MassachusettsInstitute
ofTechnology,DepartmentofEECS,Cambridge,MA,USA,May2001.
[90]T.M.SezginandR.Davis.HMM-basedefficientsketchrecognition.In
Proceedingsofthe10thInternationalConferenceonIntelligentUserInter-
faces(IUI05),pages281–283,NewYork,NY,USA,2005.ACM.
[91]T.M.Sezgin,T.Stahovich,andR.Davis.Sketchbasedinterfaces:early
processingforsketchunderstanding.InProceedingsofthe2001Workshop

BIBLIOGRAPHY

205

onPerceptiveUserInterfaces(PUI01),pages1–8,NewYork,NY,USA,
CM.A2001.

[92]P.TaeleandT.Hammond.Hashigo:Anext-generationsketchinteractive
systemforjapanesekanji.In21stInnovativeApplicationsArtificialIntel-
ligenceConference(IAAI09),July2009.

[93]E.TapiaandR.Rojas.Recognitionofon-linehandwrittenmathematical
ConferformulasenceinontheE-ChalkDocumentSystem.AnalysisInandPrRecooceedingsgnitionofthe(ICD7thAR03),Internationalpages
980–984,Washington,DC,USA,2003.IEEEComputerSociety.

[94]R.Thierjung.ErkennungundRepr¨asentationschraffierterundausgemal-
terFl¨acheninStrichzeichnungen.Universit¨atderBundeswehrM¨unchen,
2008.Diplomathesis,UniBwM-ID1/2008,onlyavailableinGerman.

[95]R.filledreThierjung,gionsFin.Brielerhand-dra,andwings.M.InMinas.WorkshopOn-lineonSkrecognitionetchRecoofgnitionhatched(IUIand
09),February2009.http://srl.csdl.tamu.edu/workshops/2009/iui/schedule.
.html

[96]M.Thorne,D.Burke,andM.vandePanne.Motiondoodles:aninter-
faceforsketchingcharactermotion.InProceedingsofthe31stInterna-
tionalGRAPHConfer04),encepageson424–431,ComputerNeGrwYaphicsork,andNY,InterUSA,active2004.TecACM.hniques(SIG-

[97]E.Turquin,M.-P.Cani,andJ.F.Hughes.Sketchinggarmentsforvirtual
characters.InProceedingsofthe1stEurographicsWorkshoponSketch-
basedInterfacesandModeling(SBIM04),pages175–182,August2004.

[98]P.A.C.Varley,R.R.Martin,andH.Suzuki.Canmachinesinterpretline
drawings?InProceedingsofthe1stEurographicsWorkshoponSketch-
basedInterfacesandModeling(SBIM04),pages107–116,2004.

[99]P.end:Wais,UserA.Wperceptionolin,andofC.interfAlvacearado.elements.DesigningInPraskoceedingsetchofrecognitionthe4thEurfront-o-
grpagesaphicsW99–106,orkshopNewYonork,SketcNY,h-basedUSA,2007.InterfacesACM.andModeling(SBIM07),

[100]L.Wenyin.On-linegraphicsrecognition:State-of-the-art.InProceed-
ingsAdvancesontheand5thPerInternationalspectivesW(GRECorkshop03),onvGrolumeaphics3088ofRecoLecturgnition.eNotesRecentin
ComputerScience,pages291–304.Springer,July2003.

206

[101]

[102]

[103]

[104]

[105]

BIBLIOGRAPHY

L.Yeung,B.Plimmer,B.Lobb,andD.Elliffe.Levelsofformality
indiagrampresentation.InProceedingsofthe2007Conferenceofthe
Computer-humanInteractionSpecialInterestGroup(CHISIG)ofAustralia
onComputer-humanInteraction:Design:Activities,ArtifactsandEnvi-
ronments(OZCHI07),pages311–317,NewYork,NY,USA,2007.ACM.

Z.Yuan,H.Pan,andL.Zhang.Anovelpen-basedowchartrecognition
ing,systemReforvisedSelectedprogrammingPapersteachi(WBLng.In08),2ndvWolumeorkshop5328ofonLecturBlendedeNotesLearn-in
ComputerScience,pages55–64.Springer,August2008.

R.Zanibbi,D.Blostein,andJ.R.Cordy.Recognizingmathematicalex-
pressionsusingtreetransformation.IEEETransactionsonPatternAnalysis
andMachineIntelligence,24(11):1455–1467,November2002.

S.ZhaiandP.-O.Kristensson.Shorthandwritingonstyluskeyboard.In
ProceedingsoftheSIGCHIConferenceonHumanFactorsinComputing
Systems(CHI03),pages97–104,NewYork,NY,USA,2003.ACM.

N.designZhu,toolsJ.C.withGruandy,visualandJ.languageG.Hosking.meta-tool.InConstructingProceedingsofdomain-specificthe17th
CAiSEConferFenceorumon.AdvancedCEUR-WS.org,InformationJune2005.SystemsEngineering(CAiSE05),