Read anywhere, anytime
Description
Subjects
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
dictatedbytechnicalaspectsratherthanbytheusersneeds.
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,theusersstrokescan
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,butusuallymakescertainassumptionsontheusersstyleof
drawing.Accordingly,webelievethatsuchapproachesshouldbeabstainedfrom,
atleastingeneral.Forspecialcases,however,feature-basedrecognitionmaybe
considered.beshouldandusefulAcentralissueoffeature-basedrecognitionisthatclustering,andevenmore
sosegmentation,areveryhardchallenges.However,bothmustbepossiblefor
asketchingapproachinordertonotrestricttheuserwhiledrawing.Therefore,
thesixthimplicationistoallowforautomaticclusteringandsegmentationofthe
es.stroksuserTheseventhandfinalimplicationistosolveambiguitiesautomatically.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.GUIwhereFromhethecanuserdrawstheperspectiskvetch,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,wheretheusersstrokesarepreserved.
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
ofabeautifiedvisualappearancethatreplacestheusersstrokesaftersuccessful
recognition.ThesetwoaspectsaredifferentfromDSKETCH,butsuitthephilos-
ophyoftheproposedrecognizerverywell(seebelow).Groupsofshapescanbe
defined,buttheironlyuseisforeditingoperations.Apossibleimprovementin
termsofrecognitionrates,drivenbyatop-downapproach,isconsidered,butis
notimplemented.Thedescriptionofshapesevensupportsabstractshapesand
inheritance,inspiredbytheconceptsofobject-orientedprogramminglanguages.
Acompletedescriptionofthelanguageanddetailedexamplescanbefoundinthe
appendixofHammondsPhDthesis[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,
inmanyofthegroupspublications,stilltheolderjournalarticle[48]iscited.
Shapescanbespecifiedtobefinal;wheneverafinalshapeissuccessfully
constructed,thefactsrepresentingtheshapesprimitivesareremoved.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-basedresearchinrecognizerHammondbysSezgingroup.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,inandLADDERseemsandlikeservanesimasproanvementalternatiovveretopreviousSezginwsork.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-implementinterfacetoutilizeInkKitandembeditinonesownap-
plications.Furthertopicsaddressedarebeautification[80]andswitchingbetween
38
CHAPTER3.RELATEDWORK
Figure3.3:ArchitectureoftheInkKitrecognizer[79].
differentlevelsofformality[101].
Thefocusoftheresearchliesmoreonhigh-levelaspects,andlessonlow-
leveltechnicalaspects.Forrecognition,theybasicallyrelyonRubinesapproach,
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(similaroftoInkKitSections2.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.AcentralaspectofInkKitsuserinterfaceistoallowfordifferentsketches
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.InkKitsperformanceisalsonotreported.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
angleabciscomparedto180◦.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←p1Rwillcontaintheresult
pa3:1←2i4:←5:whilei<ndo
6:ifEUCLIDEANDIST(a,pi)≥tdistthen
7:R←RpiappendpitoR
pa8:i←ifend9:10:i←i+1
whileend11:12:R←Rpnpreservelastsample
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,andtheenclosedangleabcis
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))←COMsPUisTEtheFEAinputTUREstrokS(s)e,theresultis(x,y,r)ornil
3:ifnotbcontains(x,y)thenboundingboxcontainscenterofcircle
4:5:endrifeturnnil
6:ifγ<300◦then
nilneturr7:ifend8:9:ifw≤40andh≤40thencheckifthestrokeissmall
10:ifw>3∙horh>3∙wthenboundingboxnottoohighorwide
12:11:endrifeturnnil
◦14:13:lifl←<γ0/.18075∙l∙r∙thenπthelengthstrokeofmustanotperfectbetoocirclelongwithaccu.comparedangletolγ
16:15:endrifeturnnil
18:17:elseifw>2∙horh>2∙wthenthestrokeisnotsmall
20:19:endrifeturnnil
21:l←γ/180◦∙r∙π
22:ifl<0.9∙lthen
nilneturr23:ifend24:25:ifHASSHARPBENDS(s)thenckechedonlyforstrokesnotsmall
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.LetSbethesetofshapesthatsharep.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←CREATEEMPTYSTATEsisastate
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∈Pdo
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,aswellasinDIAGENs,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.TheRHMshowninFigure8.2comprisesallobjectsfromthe
respectiveRHSsRandR.Althoughruleapplicationsareindependentofeach
other,edgesx’andx”areequalintheRHM,becausetheyoccurbothintheLHS
andtheRHSoftherule,andbecausetheyarematchedbythesameedgeinthe
HM.Asimilarobservationholdsfornodesy’andy”,sothesetwoarealsoequal
intheHM.Theedgesnamedd’andd”,andthetwouniquenodestheyvisit,only
occurintheRHSsRandRoftheruleapplications,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
bothrulesRHSs.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
betweentheedgesaddedfrombothrulesRHS.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
studysparticipantstendedtodrawarrows(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.Thisbenefitshouldnotbemitigatedbyconstrainingtheusers
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,featuresifisthethatyaretheynotrestrictchosenthewiselyusers.
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
Therecognitionstagesfinalstepispostprocessing.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(IJCAIofthe01),17thpagesIn-
2001.August1365–1374,
[4]C.AlvaradoandR.Davis.SketchREAD:amulti-domainsketchrecogni-
tionInterfaceengine.SoftwarInPreandoceedingsTecofhnolothegy17th(UISTAnnual04),ApagesCM23–32,SymposiumNewonYUserork,
NY,USA,2004.ACM.
[5]C.AlvaradoandR.Davis.Dynamicallyconstructedbayesnetsformulti-
JointdomainConfersketchenceonunderstanding.ArtificialInIntelligPrenceoceedings(IJCAIof05)the,19thpagesInternational1407–1412.
2005.,CenterBookProfessional
[6]A.shapes:Apte,anV.eVo,xperimentalandT.eD.vKimualuation.ra.InPrRecognizingoceedingsofthemultistrok6theAnnualgeometricACM
121–128,SymposiumNeonwYUserork,NY,InterfaceUSA,Softwar1993.eAandCM.Technology(UIST93),pages
[7]J.draArvwnographs.andK.InPrNovins.oceedingsofthe3rAppearance-preservingdInternationalConfermanipulationenceofonCom-hand-
AsiaputerGr(GRAPHITEaphicsand05),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(UISTAnnual08),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(IWFHR9th04),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-
W01),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/HCC06),pages73–80,
Washington,DC,USA,2006.IEEEComputerSociety.
[17]G.Casella,V.Deufemia,andV.Mascardi.Amulti-agentsystemforhand-
ferdrawnenceondiagramDocumentrecognition.AnalysisPrandoceedingsRecognitionofthe(ICD9thAR07)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:SIGCHIagenericNewdesZealandigntoolChaptforerthes
pagesInternational29–30,NeConferwYork,enceNYon,USA,Computer2005.A-humanCM.Interaction(CHINZ05),
[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(ICDAR05),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/HCC06),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(GREC07),vol-
ume5046ofLectureNotesinComputerScience,pages157–168.Springer,
2007.September
[25]G.Costagliola,V.Deufemia,andM.Risi.Usinggrammar-basedrecog-
nizersforsymbolcompletionindiagrammaticsketches.InProceedingsof
the9thInternationalConferenceonDocumentAnalysisandRecognition
198
BIBLIOGRAPHY
(ICDAR07),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(SEKE02),pages327–334,NewYork,NY,USA,2002.
CM.A[27]G.Costagliola,A.D.Lucia,andS.Orefice.Towardsefficientparsingof
diagrammaticlanguages.InProceedingsoftheWorkshoponAdvanced
VisualInterfaces(AVI94),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
(VL00),pages103–110,Washington,DC,USA,2000.IEEEComputer
.Society[30]A.Coyette,S.Kieffer,andJ.M.Vanderdonckt.Multi-fidelityprototyping
ofuserinterfaces.InProceedingsofthe13thInternationalConferenceon
Human-ComputerInteraction(INTERACT07),volume4662ofLecture
NotesinComputerScience,pages150–164.Springer,September2007.
[31]A.CoyetteandJ.M.Vanderdonckt.Asketchingtoolfordesigninganyuser,
anyplatform,anywhereuserinterfaces.InProceedingsofthe12thInter-
nationalConferenceonHuman-ComputerInteraction(INTERACT05),
pages550–564.SpringerVerlag,2005.
[32]A.Coyette,J.M.Vanderdonckt,andQ.Limbourg.SketchiXML:Adesign
toolforinformaluserinterfacerapidprototyping.InProceedingsofthe
3rdInternationalWorkshoponRapidIntegrationofSoftwareEngineering
Techniques(RISE06),pages160–176.Springer,September2006.
[33]J.Davis,M.Agrawala,E.Chuang,Z.Popovi´c,andD.Salesin.Asketching
interfaceforarticulatedfigureanimation.InProceedingsofthe2003ACM
SIGGRAPH/EurographicsSymposiumonComputerAnimation(SCA03),
pages320–328,Aire-la-Ville,Switzerland,Switzerland,2003.Eurograph-
Association.ics
BIBLIOGRAPHY
199
[34]J.deLaraandH.Vangheluwe.AToM3:Atoolformulti-formalismand
meta-modelling.InProceedingsofthe5thInternationalConferenceon
FundamentalApproachestoSoftwareEngineering(FASE02),pages174–
188,London,UK,2002.Springer.
[35]P.DomingosandM.Pazzani.Beyondindependence:Conditionsforthe
optimalityofthesimplebayesianclassifier.InProceedingsofthe13th
InternationalConferenceonMachineLearning(ICML96),pages105–
112.MorganKaufmann,1996.
[36]K.Ehrig,C.Ermel,S.H¨ansgen,andG.Taentzer.Generationofvisual
editorsaseclipseplug-ins.InProceedingsofthe20thIEEE/ACMInter-
nationalConferenceonAutomatedSoftwareEngineering(ASE05),pages
134–143,NewYork,NY,USA,2005.ACMPress.
[37]T.Fischer,J.Niere,L.Torunski,andA.Z¨undorf.Storydiagrams:Anew
graphrewritelanguagebasedontheunifiedmodelinglanguageandjava.
InSelectedPapersfromthe6thInternationalWorkshoponTheoryandAp-
plicationofGraphTransformations(TAGT98),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(AUIC07),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(UIST96),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(ICSE07),
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(ASE06),pages25–36,Washington,DC,USA,2006.IEEE
.SocietyComputer[46]T.HammondandR.Davis.Ladder:Alanguagetodescribedrawing,dis-
play,andeditinginsketchrecognition.InProceedingsofthe18thIn-
ternationalJointConferenceonArtificialIntelligence(IJCAI03),pages
2003.August461–467,[47]T.HammondandR.Davis.Automaticallytransformingsymbolicshape
descriptionsforuseinsketchrecognition.InThe19thNationalConference
onArtificialIntelligence(AAAI04),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.OSullivan.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(UIST00),pages63–72,NewYork,
NY,USA,2000.ACM.
BIBLIOGRAPHY
201
[53]H.HseandA.R.Newton.Sketchedsymbolrecognitionusingzernike
moments.InProceedingsofthe17thInternationalConferenceonPattern
Recognition(ICPR04),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
(UIST02),pages91–100,NewYork,NY,USA,2002.ACM.
[57]T.Igarashi,S.Matsuoka,andH.Tanaka.Teddy:asketchinginterfacefor
3Dfreeformdesign.InProceedingsofthe26thAnnualConferenceon
ComputerGraphicsandInteractiveTechniques(SIGGRAPH99),pages
409–416,NewYork,NY,USA,1999.ACMPress/Addison-WesleyPub-
Co.lishing[58]P.Isokoski.Performanceofmenu-augmentedsoftkeyboards.InProceed-
ingsoftheSIGCHIConferenceonHumanFactorsinComputingSystems
(CHI04),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(CHI95),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(SBIM06),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(UIST98),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(GraBaTs02),volume72ofElectronic
NotesinTheoreticalComputerScience,pages102–111,Amsterdam,2002.
ElsePublishers.Sciencevier[71]M.Minas.Generatingmeta-model-basedfreehandeditors.InElectronic
CommunicationsoftheEASST(GraBaTs06),September2006.
[72]M.Nakai,T.Sudo,H.Shimodaira,andS.Sagayama.Penpressurefeatures
forwriter-independenton-linehandwritingrecognitionbasedonsubstroke
HMM.InProceedingsofthe16thInternationalConferenceonPattern
BIBLIOGRAPHY
203
Recognition(ICPR02),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(SBIM4th07)Eur,ogrpagesaphics131–138,WorkshopNewonYork,SketcNYh-,
Press.CMA2007.USA,
[76]B.PaulsonandT.Hammond.PaleoSketch:accurateprimitivesketch
ConferrecognitionenceonandIntelligentbeautification.UserInInterfacesProceedings(IUI08)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/HCC08),pages57–63,Septem-
ber2008.https://www.cs.auckland.ac.nz/research/conferences/skekchws/
.proceedings.html
[78]K.Perlin.Quikwriting:continuousstylus-basedtextentry.InProceed-
Tingsecofhnolothegy11th(UISTAnnual00),ApageCMs215–216,SymposiumNeonwYUserork,NY,InterfaceUSA,Softwar1998.eACMand
Press.
[79]B.PlimmerandI.Freeman.Atoolkitapproachtosketcheddiagramrecog-
nition.InProceedingsofthe21stBritishHCIGroupAnnualConference
(HCI07),pages205–213,September2007.
[80]B.tent:PlimmerissuesandandeJ.xperiences.Grundy.InPrBeautifyingoceedingsskoftheetching-based6thAustrdesignalasiantoolUsercon-
InterfaceAustralia,2005.ConferenceAustralian(AUIC05)Computer,pagesSociety,31–38,Inc.Darlinghurst,Australia,
204
BIBLIOGRAPHY
[81]P.RajanandT.Hammond.Frompapertomachine:Extractingstrokes
fromimagesforuseinsketchrecognition.InProceedingsofthe5thEuro-
graphicsWorkshoponSketch-basedInterfacesandModeling(SBIM08),
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(UIST03),pages213–216,NewYork,
NY,USA,2003.ACM.
[86]P.Schmieder,B.Plimmer,andJ.Vanderdonckt.Cross-domaindia-
gramsketchrecognition.InWorkshoponSketchToolsforDiagramming
(VL/HCC08),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.Mastersthesis,MassachusettsInstitute
ofTechnology,DepartmentofEECS,Cambridge,MA,USA,May2001.
[90]T.M.SezginandR.Davis.HMM-basedefficientsketchrecognition.In
Proceedingsofthe10thInternationalConferenceonIntelligentUserInter-
faces(IUI05),pages281–283,NewYork,NY,USA,2005.ACM.
[91]T.M.Sezgin,T.Stahovich,andR.Davis.Sketchbasedinterfaces:early
processingforsketchunderstanding.InProceedingsofthe2001Workshop
BIBLIOGRAPHY
205
onPerceptiveUserInterfaces(PUI01),pages1–8,NewYork,NY,USA,
CM.A2001.
[92]P.TaeleandT.Hammond.Hashigo:Anext-generationsketchinteractive
systemforjapanesekanji.In21stInnovativeApplicationsArtificialIntel-
ligenceConference(IAAI09),July2009.
[93]E.TapiaandR.Rojas.Recognitionofon-linehandwrittenmathematical
ConferformulasenceinontheE-ChalkDocumentSystem.AnalysisInandPrRecooceedingsgnitionofthe(ICD7thAR03),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-
tionalGRAPHConfer04),encepageson424–431,ComputerNeGrwYaphicsork,andNY,InterUSA,active2004.TecACM.hniques(SIG-
[97]E.Turquin,M.-P.Cani,andJ.F.Hughes.Sketchinggarmentsforvirtual
characters.InProceedingsofthe1stEurographicsWorkshoponSketch-
basedInterfacesandModeling(SBIM04),pages175–182,August2004.
[98]P.A.C.Varley,R.R.Martin,andH.Suzuki.Canmachinesinterpretline
drawings?InProceedingsofthe1stEurographicsWorkshoponSketch-
basedInterfacesandModeling(SBIM04),pages107–116,2004.
[99]P.end:Wais,UserA.Wperceptionolin,andofC.interfAlvacearado.elements.DesigningInPraskoceedingsetchofrecognitionthe4thEurfront-o-
grpagesaphicsW99–106,orkshopNewYonork,SketcNY,h-basedUSA,2007.InterfacesACM.andModeling(SBIM07),
[100]L.Wenyin.On-linegraphicsrecognition:State-of-the-art.InProceed-
ingsAdvancesontheand5thPerInternationalspectivesW(GRECorkshop03),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(OZCHI07),pages311–317,NewYork,NY,USA,2007.ACM.
Z.Yuan,H.Pan,andL.Zhang.Anovelpen-basedowchartrecognition
ing,systemReforvisedSelectedprogrammingPapersteachi(WBLng.In08),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(CHI03),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(CAiSE05),
Access to the YouScribe library is required to read this work in full.
Discover the services we offer to suit all your requirements!