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

Description

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

Sujets

• Informatik

Informations

• Publié par: universitat_der_bundeswehr_munchen
• Publié le: 01 janvier 2010
• Nombre de lectures: 28
• Langue: English
• Poids de l'ouvrage: 6 Mo

Extrait

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.......