UCF CAP 5937 - Combining geometry and domain knowledge to interpret hand-drawn diagrams

Unformatted text preview:

Combining geometry and domain knowledge to interpret hand-drawn diagramsIntroductionRelated workSystem overviewTechnical detailsSegmentationSketch parsing step 1: enumerating candidate symbolsUsing ink density to locate symbolsUsing differences in segment characteristics to locate symbolsSymbol recognitionSketch parsing step 2: pruning list of candidates based on domain knowledgeAutomatic error correctionEvaluationFuture workConclusionsAcknowledgmentsExample circuits from AC-SPARC user studyReferencesComputers & Graphics ] (]]]]) ]]]–]]]Combining geometry and domain knowledge to interprethand-drawn diagramsLeslie Gennaria, Levent Burak Karaa, Thomas F. Stahovichb,, Kenji ShimadaaaDepartment of Mechanical Engineering, Carnegie Mellon University, Pittsburgh, PA 15213, USAbDepartment of Mechanical Engineering, University of California, Riverside, CA 92521, USAAbstractOne main challenge in building interpreters for hand-drawn sketches is the task of parsing a sketch to locate theindividual symbols. Many existing pen-based systems avoid this problem by requiring the user to explicitly indicate thepartitioning of the sketch with button clicks or pauses in drawing. We have created a parser that automatically locatessymbols by looking for areas of high ink density, and for points at which the characteristics of the pen strokes change.To demonstrate our techniques, we have developed AC-SPARC, a sketch-based interface for the SPICE electric circuitanalysis program. An evaluation of our interface has indicated that, even for novice users, our system can successfullylocate and identify most of the circuit components in hand-drawn circuit diagrams.r 2005 Elsevier Ltd. All rights reserved.Keywords: Pen-based computing; Sketch understanding; Sketch parsing; Symbol recognition; Ink density; Electric circuits1. IntroductionSketching with pencil and paper has always been animportant means of communication and problem-solving for designers and engineers. There are a varietyof reasons for this. For example, sketches are aconvenient tool for examining geometric, temporal,and other similar relationships, which cannot bedescribed easily in words. Similarly, the simplicity andease of creating a sketch allows one to focus on problemsolving rather than the communication medium. Yet,despite the importance of sketches in engineeringpractice, traditional engineering software can do littlewith them. Engineers often find themselves recreatingtheir sketches on the computer in order to takeadvantage of such software. We are working to changethis by creating sketch-understanding techniques thatenable software to work directly from the kinds ofsketches engineers ordinarily draw.To be natural, a sketch-based interface must place fewconstraints on the way a user draws, allowing the samefreedom provided by pencil and paper. For example, theuser should be able to sketch continuously, withoutbeing interrupted by the system, and without having toalter his or her drawing style to fit the constraints of thesystem. We have developed a technique for automati-cally parsing sketches as one means of achieving thiskind of natural interface. Parsing is the task of groupinga user’s pen strokes into clusters representing theintended symbols, without explicit indications from theuser about where one symbol ends and the next onebegins. This is a difficult problem since the number ofpossible stroke groups increases exponentially with thenumber of strokes. Additionally, in many types ofsketches, more than one symbol can be drawn in a singlepen stroke, while conversely there are many otherARTICLE IN PRESSwww.elsevier.com/locate/cag0097-8493/$ - see front matter r 2005 Elsevier Ltd. All rights reserved.doi:10.1016/j.cag.2005.05.007Corresponding author. Tel.: +1 951 827 7719;fax: +1 951 827 2899.E-mail address: [email protected] (T.F. Stahovich).common symbols that are typically drawn with multiplestrokes.To avoid the complications of parsing, many currentsketch interpretation systems require the user toexplicitly indicate the intended partitioning of the ink.This is often done by pressing a button on the stylus orby pausing between symbols [1–4]. Other systems requireeach object to be drawn in a single pen stroke [5,6]. Suchconstraints on the drawing process, however, oftenresult in a less than natural drawing environment.Our approach to parsing begins by segmenting thepen strokes into lines and arcs. A combination ofgeometric and domain-specific knowledge is then used tolocate the symbols. One of our two symbol locatorsidentifies candidate symbols by finding areas with highconcentrations of pen strokes, which we refer to as areasof ‘‘high ink density’’. The other locator identifiescandidates by finding points in the temporal sequenceof segments at which there are changes in the geometriccharacteristics of the segments. Once the candidateshave been enumerated, domain-specific knowledge isused to prune out candidates that are unlikely to besymbols. Our parsing approach allows for multiplesymbols to be drawn in the same stroke, and allowsindividual symbols to be drawn in multiple strokes.Once the parser has located the symbols in a sketch,the next task is to identify them. We have developed ageneral purpose symbol recognizer for this task, but thedetails of this are beyond the scope of this article. Afterthe sketch has been parsed and recognized, our sketchinterpreter examines the internal context of the sketch toautomatically correct typical processing errors. Domainknowledge is used to determine if the interpretations ofthe various pieces of the sketch are consistent with theinterpretation of the sketch as a whole. If not, parsingand recognition are revisited so as to eliminate theinconsistencies.Our system is designed to work for network-likediagrams containing isolated, non-overlapping symbolsthat are linked together. Examples include analogelectric circuits, logic circuits, data flow diagrams,algorithmic flowcharts, and various other graphicalmodels. As an illustration of our system’s capabilitiesand performance, we developed a sketch-based interfacefor SPICE, an electric circuit analysis program. Oursystem is called AC-SPARC for analog circuit sketchparsing, recognition, and error correction.The electric circuit domain was chosen because of thechallenges it presents. For example, in circuit sketchessingle pen strokes often contain multiple symbols.Additionally, when viewed in isolation, an


View Full Document

UCF CAP 5937 - Combining geometry and domain knowledge to interpret hand-drawn diagrams

Documents in this Course
Load more
Download Combining geometry and domain knowledge to interpret hand-drawn diagrams
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Combining geometry and domain knowledge to interpret hand-drawn diagrams and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Combining geometry and domain knowledge to interpret hand-drawn diagrams 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?