UCF CAP 5937 - Constellation Models for Sketch Recognition

Unformatted text preview:

EUROGRAPHICS Workshop on Sketch-Based Interfaces and Modeling (2006)Thomas Stahovich and Mario Costa Sousa (Editors)Constellation Models for Sketch RecognitionD. Sharon and M. van de PanneUniversity of British Columbia†AbstractSketch-based modeling shares many of the difficulties of the branch of computer vision that deals with single imageinterpretation. Most obviously, they must both identify the parts observed in a given 2D drawing or image. We drawon constellation models first proposed in the computer vision literature to develop probabilistic models for objectsketches, based on multiple example drawings. These models are then applied to estimate the most-likely labelsfor a new sketch. A multi-pass branch-and-bound algorithm allows well-formed sketches to be quickly labelled,while still supporting the recognition of more ambiguous sketches. Results are presented for five classes of objects.1. IntroductionA large-class of sketch-based modeling systems, specificallythose involving drawings of objects, diagrams, or maps,must solve a recognition problem. What did the user drawand what does each stroke correspond to? In many cases,this is solved with the help of domain knowledge, such asknowing that a sailboat has a mast and a hull. This recogni-tion problem has a strong parallel with the goals of single-image interpretation in computer vision, an area which hasseen significant progress over the past few years.We apply a constellation or ‘pictorial structure’ model tothe recognition of strokes in sketches of particular classesof objects. The model is designed to capture the structureof a particular class of object and is based on local fea-tures, such as the shape or size of a stroke, and pairwisefeatures, such as distances to other known parts. We learna probabilistic model from example sketches with knownstroke labelings. The recognition algorithm determines amaximum-likelihood labeling for an unlabelled sketch bysearching through the space of possible label assignmentsusing a multi-pass branch and bound algorithm. Our tech-nique supports flexible object structure by allowing for op-tional parts. By applying a recognition threshold, extraneousstrokes can also be readily identified.Figure 8 shows an example result for the recognition ofparts in face sketches. A subset of the training examples are†email: dsharon,[email protected], along with a set of successfully labeled free-formsketches and trace-over sketches. A specific contribution ofour method is to cope with objects that exhibit considerablevariability in the way they are drawn and that allow a vari-able number of part instantiations.The output of our algorithm is a set of labels assigned tothe strokes. This can then be utilized by a variety of appli-cations. Labelled strokes can be used to construct parame-terized 3D models as in [YSvdP05]. Furthermore, they canhelp to instance models in a 2D or 3D scene, or serve as apartial interpretation of a larger sketched diagram. Sketchescan also be used to retrieve images or 3D models from adatabase and can, in general, provide an intuitive alternativeinterface to models with complex internal parameterizationssuch as faces [fac].Our system makes two particularly strong assumptions.First, it assumes that similar parts are drawn with similarstrokes. For example, a flowerpot that is drawn with fourseparate strokes instead of one stroke is not easily modelledas part of the same object class. Second, object parts whichare deemed mandatory in a sketch must have exactly oneinstance in the sketch. Optional parts may have multiple in-stances in a given sketch.The remainder of the paper is organized as follows. Sec-tion 2 gives an overview of related work. Section 3 describesthe details of the probabilistic constellation model. Sec-tion 4 then describes our algorithms for finding maximum-likelihood interpretations of images using the model. Resultsare presented and discussed in Section 5, including variousc The Eurographics Association 2006.D. Sharon & M. van de Panne / Constellation Models(a)(b)Figure 1: (a) Face sketch training examples. The manda-tory labels are head, left-eye, right-eye, mouth, nose; theoptional labels are left-pupil, right-pupil, left-ear, right-ear, left-eyebrow, right-eyebrow, left-eyelash, right-eyelash,moustache, beard. (b) Face sketches recognized using oursystem..modes of use and examples of failure cases. Lastly, Section 6provides conclusions and future work.2. Related WorkIn this paper we address the problem of understanding com-pleted sketches with a known stroke structure and an un-known stroke ordering. Stroke information is assumed to becollected at the time of drawing creation or it can be ex-tracted using image analysis of a raster drawing using mor-phology methods (erosion/dilation) and smooth continuationmethods.Recognizing single strokes in isolation is perhaps the sim-plest version of sketch understanding and can be used to sup-port interfaces that use pen gestures as commands [Rub91].Recognizing multi-stroke visual structure is significantlymore complex, given that the interpretation of strokes is de-pendant on its local context. Many algorithms use some typeof ‘parse tree’ to search through the space of possible strokelabelings in order to find the most consistent interpretation ofa given set of strokes. For applications that involve diagraminterpretation, the search is often anchored by first findingwell-defined symbols, such as drawn characters or electri-cal component symbols [KS04]. The search is then furtherconstrained by exploiting the known structure of the givenapplication domain or object classes.Matching can be treated as a graph isomorphism prob-lem [MF02], where it is applied to the recognition of humanstick figures using a known model of connectivity. The workof [YSvdP05] applies a flexible form of hierarchical graphmatching. For example, it first looks for the best subgraphrepresenting a cup body before then proceeding to look foroptional parts such as cup handles. Curve shape feature vec-tors are used to quantify the best match and stochastic searchis used to explore the space of possible matches. Both ofthese graph-based models rely heavily on connectivity be-tween parts. They are thus weak at recognizing drawingswith disjoint parts, such as a nose or an airplane window.A probabilistic approach to sketch stroke interpretation isproposed in [AD04]. This uses domain-specific libraries of‘Bayesian network fragments’


View Full Document

UCF CAP 5937 - Constellation Models for Sketch Recognition

Documents in this Course
Load more
Download Constellation Models for Sketch Recognition
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 Constellation Models for Sketch Recognition 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 Constellation Models for Sketch Recognition 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?