toolparameterdirection

A.
Fredetal.
(Eds.
):SSPR&SPR2004,LNCS3138,pp.
104–113,2004.
Springer-VerlagBerlinHeidelberg2004ANovelConstraint-BasedApproachtoOnlineGraphicsRecognitionLuoYan,GuanglinHuang,LiuYin,andLiuWenyinDepartmentofComputerScience,CityUniversityofHongKong83,TatCheeAvenue,KowloonTong,Kowloon,HongKongSAR,China{luoyan,hwanggl}@cs.
cityu.
edu.
hk,{liuyin,csliuwy}@cityu.
edu.
hkAbstract.
Onlinegraphicsrecognitionhasbecomethekeyproblemforpen-baseduserinterfaceonsmallscreendevices,suchasPDAandTabletPC.
Inthispaper,anovelconstraint-basedapproachtoonlinegraphicsrecognitionisproposed.
Thekeyideaofourapproachisthatwhentheuserisdrawingagraphicobject,thesystemcanextracttheconstraintsbetweenprimitivesandbasicshapesfromtheobjectandusetheseconstraintstoretrievesimilargraphicobjectsfromthedatabaseatruntime.
Theusercanthenchoosethestandardob-jectfromtherankedlistofresultstoreplacehissketchesbeforehefinishesdrawingallstrokesoftheobject.
Forthispurpose,wesummarizethreetypesofprimitivesandseveraltypesofbasicshapesasthebasiccomponentsofagraphicobject.
Wealsodefineasetofconstraintsbetweenprimitivesandbasicshapestorepresenttheirstructuralrelations.
Thealgorithmsforonlinecon-straintextractionandgraphicsrecognitionarealsopresented.
Experimentalre-sultsshowthatourapproachisefficientforonlinegraphicsrecognitionandef-fectiveforimprovingtheuser'sproductivity.
1IntroductionRecentlypen-baseddevicessuchasPDAandTabletPChavebecomemoreandmorecommontothegeneralpublic.
Inthesedevices,graphicsisanimportantandusefulmeansforuserstostoreinformation,expressthought,andsketchdesigns.
Manysys-temsweredevelopedtofacilitateuserstodrawgraphics,suchasMicrosoftVisio,SmartDraw,andAutoCAD.
Inthesesystems,theuserisaskedtodrawgraphicsbyselectingtheparticulartypeofgraphicobjectfromlotsoftoolbarbuttonsormenuitems.
Thistaskisverytime-consumingandinconvenient,especiallywhenthenum-berofpredefinedgraphicobjectsinthesystemisverylarge.
Themostconvenientandnaturalwayforhumanbeingstodrawgraphicsshouldbeusingapentodrawsketches,justlikedrawingonarealsheetofpaper.
However,thesketchesdrawninthiswayarenotstandardandclearinappearance,notcompactinrepresentationandstorage,andnoteasyformachinestounderstandandprocess.
Itisnecessarytorec-ognizeandconvertthesketchestotheregularandstandardgraphicobjectsthattheuserintendstodraw.
Moreover,itisevenbetterifwecandorecognitionwhiletheuserissketchingsincetherecognizedpartscanprovideimmediateandusefulfeed-backtotheusersothathecanrealizeerrorsorinappropriatenessearlierandthereforedrawthegraphicsmoreperfectly.
Inmanycases,recognizinggraphicobjectsearlycanalsosignificantlysavetheuser'sinputstrokesandtime.
Hence,onlinegraphicsANovelConstraint-BasedApproachtoOnlineGraphicsRecognition105recognitionhasbecomethekeyproblemforpen-baseduserinterfaceonthesesmallscreendevices.
Moreover,onlinegraphicsrecognitioncanbealsoviewedasaqueryandretrievalproblem.
Theuser'sinputstrokescanbeviewedasaqueryandthesys-temretrievesthesimilargraphicobjectsfromanumberofpredefinedstandardgraphicobjects.
Althoughtheaimsofretrievalandrecognitionaredifferent,theun-derlyingtechnologyiscommoninthatamatchingprocedureisneededtocomparetheinputpatternwitheachknownpattern.
Therefore,thetechniquesforretrievingonlinegraphicsarealsowithinthescopeofonlinegraphicsrecognition.
Inthefollowing,wewillnotdistinguishretrievalfromrecognition.
Thereadersshouldbearinmindthecommonpointsanddifferencesbetweenthem.
Comparedwithofflinegraphicsrecognition,onlinegraphicsrecognitionhassomespecialcharacteristics.
First,theinputgraphicobjectforonlinegraphicsrecognitionisusuallyincomplete,sinceourgoalistorecognizetheuser'ssketchesbeforehefin-ishesthewholegraphicobject,whichcanprovideanimmediateandusefulfeedbacktotheuser.
Thischaracteristicimpliesonlinegraphicsrecognitionhastorecognizetheuserintendedobjectbasedonpartialinformationinmanycases.
Second,thestrokesinthesamegraphicobjectcanbedrawnindifferentordersbydifferentusers.
Hence,theincompleteuser'sinputofthesamegraphicobjectcanbeverydifferentforonlinegraphicsrecognition.
Thatmeansitisnoteasytoapplythetraditionalmatchingmethodsforofflinegraphicsrecognitiontoonlinegraphicsrecognition,sincetherecanbemanydifferentkindsofincompletegraphicobjectsforthesamecompleteoneanditisdifficulttomatchallofthemtothecompleteone.
Third,onlinegraphicsrecognitionneedsmoreefficiencythanofflinegraphicsrecognition.
Thesystemhastoprovidetheimmediatefeedbacktotheuseratruntime;otherwise,itwillbetediousandtime-consuminginsteadofsavingtheuser'sinputstrokesandtime.
Hence,theefficiencyofonlinegraphicsrecognitionisveryimportantforagooduserinterface.
Manyresearchworkshavebeendoneonsuchonlinegraphicsrecognition.
Ze-lezniketal.
[1]haveinventedaninterfacetoinput3Dsketchyshapesbyrecognizingthepredefinedpatternsofsome2Dgraphicobjects.
Jorge'sgroup[2][3]haveimple-mentedanonlinegraphicsrecognitiontoolthatcanrecognizeseveralclassesofsim-pleshapesbasedonglobalareacalculation,whichcanhardlydistinguishambiguousshapessuchaspentagonandhexagonandthereforecannotachievehighrecognitionprecisiongenerally.
SILK[4]isaninformalsketchingtoolthatcombinesmanyofthebenefitsofpaper-basedsketchingwiththemeritsofcurrentelectronictools.
JavaS-ketchIt[5]isanothersystemforthispurpose,whichcangenerateaJavainterfacefromhand-drawngeometricshapes.
SKETCHIT[6]isasystemthatcantransformasinglesketchofamechanicaldeviceintomultiplefamiliesofnewdesigns.
LADDER[7]isalanguagetodescribehowsketcheddiagramsinadomainaredrawn,dis-played,andedited,andusedforonlinegraphicsrecognition.
Therecognitionap-proachisstillnotadequateforarealsoftwaretoolthatcanbeusedforinputtingmostclassesofdiagrams.
Hence,inordertoprovidethecapabilitytoinputmorecomplexdiagrams,itisnecessarytoextendtheonlinegraphicsrecognitionapproachtohandlemorecomplexandcompositeshapes,asdoneinSmartSketchpad[8],whichcaneffi-cientlyandeffectivelyinputcompositegraphicobjectsbysketchingonlyafewcon-stituentstrokes.
106LuoYanetal.
2OurApproachandContributionInthispaper,weproposeanovelconstraint-basedapproachtoonlinegraphicsrecog-nition.
Thekeyideaofourapproachisthatwhentheuserisdrawingagraphicobject,thesystemcanextracttheconstraintsbetweenprimitivesandbasicshapesfromtheobjectandusetheseconstraintstoretrieveorrecognizesimilarstandardgraphicob-jectsfromthedatabaseatruntime.
Theusercanthenchoosethestandardobjectfromtherankedlistofresultstoreplacehissketchesbeforehefinishesdrawingallstrokesoftheobject.
Ourcontributionincludes,1)wesummarizedthreetypesofprimitivesandseveraltypesofbasicshapes;2)wedefinedasetofconstraintsbetweenprimitivesandbasicshapestorepresenttheirstructuralrelations;3)wedevelopedanalgorithmforonlineconstraintextractionfromtheuser'sinputgraphicobject,whichisincompleteinmanycases;4)wedevelopedanotheralgorithmforonlinegraphicsrecognitionbasedontheconstraintsoftheuser'sinputgraphicobject;5)weproposedanalgorithmforcalculatingthesimilaritybetweentheuser'sinputgraphicobjectandthecandidategraphicobjectsfordisplayingtherecognizedresultsinarankedlist.
Fig.
1.
TheflowchartofourapproachFigure1istheflowchartofourapproach.
Theuserbeginshissketchesbydrawingsomebasicstrokes(orprimitives).
Thesystemstartstoextracttheconstraintsbe-tweentheseprimitivesandusestheextractedconstraintstorecognizethesimilarstandardgraphicobjectsinthedatabase.
Byusingourproposedsimilaritycalculationalgorithmthesystemcanthencalculatethesimilaritybetweentheuser'sinputgraphicobjectsandthecandidategraphicobjects,anddisplaytherecognizedresultsinarankedlist.
Iftheuser'sintendedgraphicobjectisdisplayedinthelist,hecanjustchoosethisstandardobjecttoreplacethatincompletesketcheshehasjustdrawn.
Thesystemappliestheseprocedures,suchasconstraintextraction,graphicsrecognition,andsimilaritycalculation,atthesametimeastheuserisdrawingthesketches.
HenceANovelConstraint-BasedApproachtoOnlineGraphicsRecognition107itcanfacilitatetheusertodrawgraphicsbysignificantlysavingtheuser'sinputstrokesandtime.
Inthefollowingofthispaper,wefirstproposeourconstraint-basedapproachtodescribetheuser'sinputgraphicobjectinSection3.
Then,algorithmsforconstraintextractionandgraphicsrecognitionarediscussedinSection4and5,respectively.
Finally,experimentalresultsandconcludingremarksarepresented.
3Constraint-BasedRepresentationofGraphicObjectsAswediscussedabove,ourapproachfocusesontherelativespatialrelationsbetweenprimitivesandbasicshapes.
Hence,weuseconstraintstorepresenttheuser'sinputgraphicobjectinourapproach.
Constraint,orgeometricconstraint,isnotanewcon-cept,whichhasbeenwidelyusedinCADsystems(e.
g.
,[9]).
However,inmanyCADsystems(e.
g.
,[9][10][11]),theconstraintsaredefined,extracted,andspecifiedbyprofessionalandexperiencedusers.
Inourapproach,wedefinedasetofconstraintstodescribethespatialrelationsbetweenprimitivesandbasicshapes.
Thesystemcanextractconstraintswhiletheuserisdrawingthesketchesandusestheseconstraintstorecognizesimilarstandardgraphicobjectsinthedatabaseatruntime.
Thus,ourdefi-nitionofconstraintsshouldbebroadenoughtosupportawiderangeofgraphicob-jects,whileremainingnarrowenoughtobecomprehensible.
Firstofall,wedefinethreetypesofprimitives:Line,Circle,andArc.
AsshowninFigure2,P1andP2aretwoendpointsofaLine.
WecanassumeP1isthestart-pointandP2istheend-pointsuchthatwecandefinethedirectionofaLineisfromP1toP2.
ForaCircleprimitive,italsohastwoattributes,C(center-point)andR(radius).
InthedefinitionofanArc,weuseP1andP2torepresentthestart-pointandend-pointofanArcsincetheuserusuallypaysmoreattentiontothestart-pointandend-pointthanthecenter-point.
ThatmeanstheuserdoesnotcareaboutthecurvingofanArcbutthepositionofanArc.
However,thedirec-tionofthebowofanArcisveryimportantfortheusertodistinguishdifferentgraphicobjects.
Hence,ifwedefineapositivedirec-tionfromP1toP2,likeX-axis,thenwecandefinetheDirectionofthebowofanArc.
Thenwedefinetheconstraintsbetweentheaboveprimitives.
Weanalyzedmorethan300typesofgraphicobjectstosummarizetheconstraints.
Sinceweonlyusethreeparameters(i.
e.
,P1,P2,andDirection)todefineanArcprimitive,wecanimageanArcasaLineplusaDirection.
Hence,wecanjustanalyzetheconstraintsbetweenLineprimitivesandapplytheseconstraintstoArcprimitivesbysimplyaddingaDi-rectionparameter.
Therefore,wefirstdefinefourconstraintsbetweenLineprimitivesandArcPrimitives,includingConnection,Intersection,Parallelism,andPerpendicu-larity.
ForaCircleprimitive,weregarditasabasicshape,whichisdiscussedinthefollowingsection,anddefinetheconstraintsbetweenbasicshapesandprimitivestodescribetheirspatialrelations.
Here,foreasilyunderstanding,weonlyuseLineprimitivestodescribethefourconstraintsbetweenLineandArcprimitives.
ForthecasesincludingArcprimitives,onlyoneadditionalparameter,Direction,isrequired.
LineCircleArcFig.
2.
Primitives108LuoYanetal.
(1)ConnectionConnectionisaconstrainttodescribethattwoprimitivessharethesameend-point,justliketheyareconnectedatoneend.
Figure3illustratesthisconstraint.
Fig.
3.
ConnectionFromtheabovefigure,wecanseethatthereareonlyfourcasesbetweentwoprimitivesthatareconnectedwitheachother,sinceoneLineoroneArchastwoend-points.
Weuseaparametertypetorepresentthisinformationanduseanotherparame-terangletostoretheanglebetweenthetwoprimitives.
|)||/(|)cos(2121LLLLangle==αInthisdefinition,theparameterangleitselfisnotsufficienttofullyspecifythespatialrelationshipoftwointersectedlinessincetheanglehasadirection.
Thus,weuseanotherparameterdirectiontodescribethisinformation.
ConsiderL1(x1,y1,0)andL2(x2,y2,0),whichare2Dvectorsin3Dspace,andtheircrossproduct),0,0(,00,002211212121zLyxyxxxyyLLL==*=12212211yxyxyxyxLz==LisperpendiculartotheplaneformedbyL1andL2,anditsdirectioncomplieswiththeRightHandRule.
ThuswecandeterminethedirectionbythesignofLz.
Inaddi-tion,weusetheparameterlengthtodescribetherelativelengthofL2toL1(length=|L2|/|L1|).
(2)IntersectionIntersectionisaconstrainttodescribethattwoprimitivesareintersectedwitheachother,whichmeanstheysharethecommonpointontheprimitives.
InFigure4,twoLineprimitivesareintersectedwitheachotheratiPoint.
Wedefinefourparameterstodescribethisconstraint.
Thefirsttwoparametersdescribetherela-tivepositionofiPointontwoLineprimitivesasfollows.
1211121iPointiPPPP=2221222iPointiPPPP=Weuseothertwoparameters,angleandlength,todescribetheanglebetweentwoprimitivesandrelativelengthofthemjustlikeConnectionconstraint.
(3)ParallelismSimilartoIntersection,wealsousefourparameterstodescribeParallelismgeometricconstraint.
Thefirstoneisdistance=D(L1,L2)/|L1|,inwhichD(L1,L2)de-notestherealdistancebetweenlineL1andL2.
Thesecondone,direction,isusedtodescribewhetherL2isontheleftorrighttoL1andthecomputingmethodisFig.
5.
ParallelismFig.
4.
IntersectionANovelConstraint-BasedApproachtoOnlineGraphicsRecognition109similartothedefinitioninConnectionconstraint.
Moreover,weusetwootherpa-rameterstospecifytheirrelativepositionandlength.
InFigure5,L1andL2areparalleltoeachother;spandeparetheprojectionsoftheendpointsofL2onL1.
Weset:211121.
.
.
sppoint-startPLPLPL=211121.
.
.
eppoint-endPLPLPL=(4)PerpendicularityForthePerpendicularityrelationshipinwhichtwoprimi-tivesareconnectedorintersected,wecanuseConnectionorIntersectiontorepresentit,respectively.
Here,weonlydefinethePerpendicularitybetweentwoprimitiveswhentheyarenotconnectedorintersected:Length||/||12LL=Per-pointistheperpendicularpointof2Lon1LStart-point||/|.
,point-per|212LPL=End-point||/|.
,point-per|222LPL=Whenwecalculatestart-pointandend-point,wesetasigntothevalueofthem.
Wesetitpositiveifthepointisontheleft-handsideofL1andnegativeontheright-handside.
ThecomputingmethodissimilartocomputingdirectioninConnectionconstraint.
InFigure6,thevaluesofstart-pointandend-pointarebothpositive.
Someprimitivescanconstituteaverycommonandbasicshape,whichisoftenusedbyusersinmanycomplexgraphicobjects.
Especially,theuserusuallydividesthewholesketchintosomebasicshapeswhendrawingacomplexsketch.
Therefore,wealsosummarizedsomebasicshapestorepresenttheuser'sinputgraphicobjectatahigherlevel,asillustratedinFigure7.
Forthesebasicshapes,wealsodefineasetofconstraintstodescribethestructuralrelationsbe-tweenthem.
Forinstance,totheclosedshapes,suchasRectangleandCircle,wedefinedtheInner/Outerconstrainttodescribewhetherotherprimitivesorbasicshapesareinsideoroutsidethem,because,inmanycases,theuserpaysmoreattentiontotheInner/Outerrelationsbetweenshapesthantheprecisepositionororientationoftheseshapes.
Forothernon-closedshapes,wealsodefinedotherconstraints(e.
g.
,relativepositionandorientation)todescribethestruc-turalrelationsbetweenthesebasicshapesandotherprimitives.
4OnlineConstraintExtractionInthissection,wediscussourdevelopedalgorithmforonlineconstraintextraction,whichmeansthatourapproachextractstheconstraintsbetweentheprimitivesandbasicshapeswhiletheuserisdrawingsketches.
ThisalgorithmisdevelopedbasedonFig.
6.
PerpendicularityFig.
7.
Somebasicshapes110LuoYanetal.
ourpreviousworkforofflinegraphicsrecognition[12].
Wedividetheprocedureofrecognizinguser'sdrawingsketchesintothreestages.
1.
Theuserbeginshissketcheswithsimpleprimitives,whichdonotconstituteanybasicshapes.
However,thesimpleprimitivesdocontainusefulinformationabouttheuser'sintention,e.
g.
,theycanbeapartofastandardgraphicobject.
Hence,ouralgorithmextractstheconstraintsbetweentheprimitivesastherepresentationofuser'sinputatthisstageandusestheseconstraintstoretrievethestandardgraphicobjectsthatcontainthesimilarpart.
2.
Whentheusercontinuestodrawsketches,thereareenoughprimitivestoconstituteabasicshape.
Atthisstage,ourapproachusestheconstraintsbetweentheprimi-tivestorecognizethemasabasicshapeandprovidesausefulandimmediatefeed-backtotheuser.
Theusercanacceptthefeedbackoradjusthissketchesatthisstage.
Oncetheuseracceptshiscurrentsketchesasabasicshape,hissketchesarereplacedbythestandardbasicshapeandhecangoonwithhissketches.
Thesys-temwillthenextracttheconstraintsbetweenthenewlydrawnprimitivesuntilanewbasicshapeisrecognized.
3.
Astheusergoesonwithhissketches,theconstraintsbetweenthebasicshapesshouldalsobeextractedsincetheycontainmuchusefulinformationforrecogni-tion.
Hence,atthethirdstage,thesystemextractstheconstraintsbetweenbasicshapesandconstructsahierarchicalconstraint-basedstructureforrecognition.
Forthedetailoftheonlineconstraintextractionalgorithm,seetheCase-basedKnowledgeAcquisitionAlgorithm(CKAA)[12].
5OnlineGraphicsRecognitionTheconstraintsextractedbytheabovealgorithmarestoredinasyntacticaltree.
Weusethistreetoretrieveorrecognizethesimilarstandardgraphicobjects.
Wesearchallthepredefinedgraphicobjectsinthedatabaseforthosethatcontainthesimilarconstraints,i.
e.
,containthesimilargraphicobjecttouser'sinput.
However,wecan-notusethematchingmethodforrecognitionsincetheuser'sinputisusuallyincom-plete.
Therefore,weproposeanewscheme,whichislikeareasoningmethod,forrecognizinggraphicobjectsbasedontheconstraints.
Whenwetestonestandardgraphicobjectforwhetheritcontainsthesimilargraphicobjecttotheuser'sinputornot,wefirsthypothesizethatonestrokeofthestandardgraphicobjectisintheuser'sinput.
Usingtheconstraintsextractedfromtheuser'sinput,wecancalculatethespecificationofanotherprimitiveorbasicshapebasedonthehypothesisstroke.
Thenwesearchthestandardgraphicobjecttoseewhetheritcontainsthisstroke.
Ifthestrokeisfound,wecontinuetracingotherconstraintsuntilallstrokesarefoundinthestandardgraphicobject,whichmeans,thisstandardgraphicobjectcontainsthesimi-largraphicobjecttotheuser'sinput.
Otherwise,weselectanotherstroketorepeatthishypothesizing/testingprocedure.
Thealgorithmpresentedbelowdealswithidealsituations.
Inpractice,thetoleranceshouldbeconsideredandthematchingmeasureshouldbedefined,whicharediscussedinourpreviouswork[12].
ThedetailoftheonlinegraphicsrecognitionalgorithmisshowninAlgorithm1.
ANovelConstraint-BasedApproachtoOnlineGraphicsRecognition111Whentheresultisoutput,thesimilaritybetweentheuser'sinputgraphicobjectandthestandardgraphicobjectiscalculatedfromtwoaspects.
Thefirstisthesimilar-itybetweenprimitives,whichiscalculatedaccordingtothedifferenceoflength,an-gleandpositionbetweenthetwoprimitives.
Thesecondisthesimilarityofcon-straints,whichiscalculatedbythepercentageofexactmatchedprimitivesinthestandardgraphicobject.
Accordingtothesimilarityofthestandardgraphicobjects,weselecttop10objectsinthedatabaseandreturntheminarankedlisttotheuser.
Algorithm1:OnlineGraphicsRecognitionInput:SC:thesetofconstraintsfromtheuser'sinputgraphicobjectDB:thedatabaseconsistsofstandardgraphicobjectsTL:thetolerances,e.
g.
,lengthandnumbertoleranceVariables:CT:thetemporaryconstructedtreeforreasoningprocedureSM:thesetofmarkstoindicateprimitivesthathavebeentestedOutput:RR:therecognitionresult,whichtypethegraphicobjectis1.
SelectastandardgraphicobjectSGfromDB.
Ifallstandardgraphicobjectshavebeensearched,thenstop(failure)2.
SetCTemptyandinitializeSM3.
SelectthenextprimitivePfromSG,whichhasnotbeenmarkedinSM.
AdditintoCTastheroot,andmarkitinSMtoindicatethisprimitivehasbeentested.
IfallprimitiveshavebeenmarkedinSM,gotostep1.
4.
SelectthenextconstraintCfromSC.
Ifallconstraintshavebeentracedthenstop(success)andoutputthecurrentSGasRR5.
CalculatethenewprimitiveorbasicshapeP'usingPandC6.
SearchforaP''inSG,whichissimilartoP'usingthetolerancesinTL.
7.
IfP''isfoundthensetitasachildofPinCTandmarkinSMtoindicateP''hasbeenusedandgotoStep48.
IfP''isnotfoundandthenumberofmissingprimitivesexceedsthetolerancethengotoStep2.
Otherwise,gotoStep46ExperimentalResultsWehaveimplementedaprototypesystemanddoneseveralexperimentsbasedonadatabaseconsistingof345standardgraphicobjects,someofwhichareillustratedinFigure8.
Theuserisaskedtodrawgraphicobjectsandthesystemprovidesimmediaterecognitionresults,fromwhichtheusercanselecthisintendedstandardgraphicobject.
Theaveragerecogni-tionaccuracyis90.
5%sincetheuser'sinputcanbeverydifferent.
Wealsorecordthenumberofstrokesthathavebeensavedfordrawinganobject.
Inourexperiments,thenumberofonestandardobject'sstrokesrangesfrom1to14andtheaverageis10.
32.
Theaveragenumberofsavedstrokesis2.
78,nearly27%.
Wealsoevaluatetheresponsetimeofourapproach.
Theaverageresponsetimetouser'sFig.
8.
Somestandardgraphicobjects112LuoYanetal.
inputiswithin100ms,whichisefficientenoughtogivereal-timeresponseforadata-baseconsistingofseveralhundredsofgraphicobjects.
Fromtheexperimentalresults,wecanseethatourapproachiseffectiveforonlinegraphicsrecognitionandsavingtheuser'sinputstrokesandtime.
7ConclusionandFutureWorkInthispaper,weproposedanovelconstraint-basedapproachtoonlinegraphicsrec-ognition,withwhichthesystemcanextracttheconstraintsbetweenprimitivesandbasicshapesfromtheuser'sinputandusetheseconstraintstorecognizesimilarstan-dardgraphicobjects.
Severalconstraintsaredefinedandtwoalgorithmsaredevel-oped.
Experimentalresultsshowthatourapproachisefficientforonlinegraphicsrecognitionandeffectiveforsavingtheuser'sinputstrokesandtime.
However,someaspectsofourapproachcanbeimproved.
Moretypesofprimitives,basicshapes,andconstraintscanbeaddedintoourapproachinthefuturetosupportmorecomplexandvariousgraphicobjects.
Twoalgorithmsforonlineconstraintextractionandgraphicsrecognitioncanbealsorevisedtoimprovetherecognitionaccuracyandsavetheuser'sinputstrokeandtime.
Wealsoplantoprovidemoregraphicobjectsfromvari-ousdomainstodoexperimentstotestoursystem.
AcknowledgementTheworkdescribedinthispaperwasfullysupportedbyagrantfromtheResearchGrantsCounciloftheHongKongSAR,China[ProjectNo.
CityU1073/02E].
References1.
R.
C.
Zeleznik,K.
P.
Herndon,andJ.
F.
Hughes,"KETCH:AnInterfaceforSketching3DScenes",Proc.
ofSIGGRAPH,NewOrleans,pp.
163-170,1996.
2.
M.
J.
FonsecaandJ.
A.
Jorge,"UsingFuzzyLogictoRecognizeGeometricShapesInterac-tively",Proc.
ofthe9thIEEEConf.
onFuzzySystems,Vol.
1,pp.
291-296,2000.
3.
M.
J.
Fonseca,C.
Pimentel,J.
A.
Jorge,"AnOnlineScribbleRecognizerforCalligraphicIn-terfaces",Proc.
ofAAAISpringSymposiumSeries–SketchUnderstanding,2002.
4.
J.
M.
LandayandB.
A.
Myers,"SketchingInterfaces:TowardMoreHumanInterfaceDe-sign",IEEEComputer,Vol.
34,No.
3,pp.
56-64,2001.
5.
A.
Caetano,N.
Goulart,M.
J.
Fonseca,andJ.
A.
Jorge,"JavaSketchIt:IssuesinSketchingtheLookofUserInterfaces",Proc.
AAAI'02SpringSymposium–SketchUnderstanding.
6.
C.
Calhoun,T.
F.
Stahovich,T.
Kurtoglu,L.
M.
Kara,"RecognizingMulti-StrokeSymbols",Proc.
ofAAAISprintSymposiumSeries–SketchUnderstanding,2002.
7.
T.
HammondandR.
Davis,"Ladder:ALanguagetoDescribeDrawing,Display,andEdit-inginSketchRecognition",Proc.
ofIJCAI'03,2003.
8.
W.
Liu,X.
Jin,andZ.
Sun,"Sketch-BasedUserInterfaceforInputtingGraphicObjectsonSmallScreenDevices",LectureNotesinComputerScience2390,pp.
67-80,2002.
ANovelConstraint-BasedApproachtoOnlineGraphicsRecognition1139.
J.
K.
LeeandK.
Kim,"GeometricReasoningforKnowledge-basedParametricDesignusingGraphRepresentation'",Computer-AidedDesign,Vol.
28,No.
10,pp.
831-841,1996.
10.
S.
Ait-Aoudia,B.
Hamid,A.
Moussaoui,T.
Saadi,"SolvingGeometricConstraintsbyaGraph-ConstructiveApproach",Proc.
ofICIV'1999,pp.
250-255,1999.
11.
I.
Fudos,C.
M.
Hoffmann,"AGraph-ConstructiveApproachtoSolvingSystemsofGeo-metricConstraints",ACMTrans.
onGraphics,Vol.
16,No.
2,pp.
179-216,1997.
12.
Y.
LuoandW.
Liu,"ACase-basedInteractiveApproachtoGraphicsRecognitioninEngi-neeringDrawings",Proc.
ofGREC'2003,pp.
170-181,2003.