Sketch beautification and completion of partial structured-drawings

A sketch processing system is described herein for assisting a user in producing a drawing. In one implementation, the sketch processing system operates by: receiving ink strokes in response to creation of an original drawing; recognizing components and geometric constraints within the original drawing, to produce a recognized drawing; beautifying the original drawing by modifying at least one aspect of the recognized drawing in accordance with the recognized constraints, to produce a beautified drawing; and recognizing a recurring pattern in the beautified pattern (if any) and using that pattern to produce at least one added component to the beautified drawing.

BACKGROUND

A user may wish to create a drawing having precisely-rendered geometric shapes, as well as precisely-rendered arrangements of those shapes. In one approach, the user can produce the drawing “by hand” by sketching out the geometric figures on a graphics tablet or the like. However, it may be difficult for the user to produce a drawing in this manner with a satisfactory degree of precision.

The research community has proposed various ways of assisting a user in creating a precise drawing, some of which allow the user to convey his or her drawing-related intent by making an initial hand-drawn sketch of the drawing. There is nevertheless room for considerable improvement in such techniques.

SUMMARY

A sketch processing system (SPS) is described herein for assisting a user in producing a drawing. In one implementation, the SPS includes a recognition module for receiving ink strokes in response to creation of an original hand-drawn drawing. The recognition module then recognizes components (e.g., lines and circles) and geometric constraints within the original drawing, to produce a recognized drawing. The sketch processing system also includes a beautification module for producing a beautified drawing which cleanly expresses the geometric constraints recognized in the original drawing. The sketch processing system module also includes a pattern processing module for recognizing a predominant pattern in the beautified drawing (if any). The pattern processing module then uses that pattern to add at least one new component to the beautified drawing.

The recognition module, beautification module, and pattern processing module can be used in combination in the manner summarized above. In addition, these three components can be used separately in other environment-specific contexts.

According to another illustrative aspect, each component that is recognized by the recognition module can be further decomposed into two or more sub-components. The beautification module may then perform its operation by successively resolving unknown sub-components in the recognized drawing. Further, the pattern processing module may perform its operation by identifying transformations between different pairs of sub-components in the beautified drawing. This yields transformation information. The pattern processing module can then use a voting technique to identify one or more predominant transformations in the transformation information. These one or more predominant transformations correspond to a recurring pattern in the beautified drawing.

The above approach can be manifested in various types of systems, components, methods, computer readable storage media, data structures, articles of manufacture, and so on.

The same numbers are used throughout the disclosure and figures to reference like components and features. Series100numbers refer to features originally found inFIG. 1, series200numbers refer to features originally found inFIG. 2, series300numbers refer to features originally found inFIG. 3, and so on.

DETAILED DESCRIPTION

This disclosure is organized as follows. Section A describes illustrative functionality for beautifying sketches and for completing partial structured-drawings. Section B describes illustrative methods which explain the operation of the functionality of Section A. Section C describes illustrative computing functionality that can be used to implement any aspect of the features described in Sections A and B.

As a preliminary matter, some of the figures describe concepts in the context of one or more structural components, variously referred to as functionality, modules, features, elements, etc. The various components shown in the figures can be implemented in any manner by any physical and tangible mechanisms, for instance, by software, hardware (e.g., chip-implemented logic functionality), firmware, etc., and/or any combination thereof. In one case, the illustrated separation of various components in the figures into distinct units may reflect the use of corresponding distinct physical and tangible components in an actual implementation. Alternatively, or in addition, any single component illustrated in the figures may be implemented by plural actual physical components. Alternatively, or in addition, the depiction of any two or more separate components in the figures may reflect different functions performed by a single actual physical component.FIG. 20, to be discussed in turn, provides additional details regarding one illustrative physical implementation of the functions shown in the figures.

Other figures describe the concepts in flowchart form. In this form, certain operations are described as constituting distinct blocks performed in a certain order. Such implementations are illustrative and non-limiting. Certain blocks described herein can be grouped together and performed in a single operation, certain blocks can be broken apart into plural component blocks, and certain blocks can be performed in an order that differs from that which is illustrated herein (including a parallel manner of performing the blocks). The blocks shown in the flowcharts can be implemented in any manner by any physical and tangible mechanisms, for instance, by software, hardware (e.g., chip-implemented logic functionality), firmware, etc., and/or any combination thereof.

As to terminology, the phrase “configured to” encompasses any way that any kind of physical and tangible functionality can be constructed to perform an identified operation. The functionality can be configured to perform an operation using, for instance, software, hardware (e.g., chip-implemented logic functionality), firmware, etc., and/or any combination thereof.

The term “logic” encompasses any physical and tangible functionality for performing a task. For instance, each operation illustrated in the flowcharts corresponds to a logic component for performing that operation. An operation can be performed using, for instance, software, hardware (e.g., chip-implemented logic functionality), firmware, etc., and/or any combination thereof. When implemented by a computing system, a logic component represents an electrical component that is a physical part of the computing system, however implemented.

The phrase “means for” in the claims, if used, is intended to invoke the provisions of 35 U.S.C. §112, sixth paragraph. No other language, other than this specific phrase, is intended to invoke the provisions of that portion of the statute.

The following explanation may identify one or more features as “optional.” This type of statement is not to be interpreted as an exhaustive indication of features that may be considered optional; that is, other features can be considered as optional, although not expressly identified in the text. Finally, the terms “exemplary” or “illustrative” refer to one implementation among potentially many implementations

A. Illustrative Sketch Processing System

FIG. 1shows an illustrative environment100in which a sketch processing system (SPS)102transforms an original hand-drawn drawing into a refined output drawing. The environment100can correspond to any context in which a user wishes to produce a drawing having precise geometric shapes and precise spatial relationships among the geometrical shapes. Without limitation, for example, a user can use the SPS102in an engineering or scientific environment, a business-related environment, an academic environment, and so on. In still other cases, a user can use the SPS102to produce drawings for strictly aesthetic/artistic reasons, and/or as an amusement.

The environment100can include (or can be conceptualized as including) a number of components that perform different functions. These elements will be described below in a generally top-down manner. Later section will provide further details regarding the components inFIG. 1.

First, the environment100includes at least one sketch input device104for inputting an original drawing. In one implementation, the sketch input device104can include any mechanism having a touch-sensitive surface on which the user may draw. For example, the sketch input device104can correspond to a graphics tablet. More specifically, in some cases, the touch-sensitive surface of the sketch input device104may be co-extensive with a display surface of an output device106. This enables the output device106to produce a visible rendering of the user's sketch as the user draws the sketch on the sketch input device104. In another case, the touch-sensitive surface of the sketch input device104can correspond to a surface that is separate from the output device106. In any case, the user can produce the original drawing by manipulating a passive and/or active implement of any type (e.g., a stylus, pen, etc.), and/or with a finger, etc.

In yet another case, the sketch input device104may represent a scanning mechanism which scans in a hard-copy version of an original drawing created by the user or any other user or any other entity. In yet another case, the sketch input device104can represent an interface which receives a previously generated original drawing, obtained from any remote source (e.g., a network-accessible repository of such drawings). Still other implementations of the sketch input device104are possible.

Now referring to the SPS102itself, this functionality can include an input module108for receiving the original drawing supplied by the sketch input device104. The SPS102then proceeds to operate on the original drawing in three main phases. In a first phase, a recognition module110recognizes geometric primitives that may be used to construct higher-order shapes in the original drawing. In the concrete examples featured herein, the geometric primitives correspond to straight lines and circles. However, in other cases, the recognition module110can detect other types of geometric primitives, such as ellipses, arcs, etc. (instead of, or in addition to, the recognition of straight lines and circles).

The recognition module110also detects geometric constraints associated with the components that it has detected. Some of these constraints correspond to characteristics of individual components. Other constraints correspond to geometric relationships between pairs of components (or, more generally, among different groups of components).

As a result of its processing, the recognition module110produces a recognized drawing. That drawing is associated with a set of recognized components and a second of recognized constraints. Section A.2 provides additional details regarding one manner of operation of the recognition module110.

A beautification module112receives the recognized drawing as input, along with its associated set of recognized components and constraints. The beautification module112then refines the recognized drawing to produce a beautified drawing. In one implementation, this refinement entails redrawing the recognized lines and circles as perfectly straight lines and perfectly round circles, respectively. Further, the refinement involves redrawing the components in a manner that conforms to the recognized geometrical relationships among the components (e.g., by drawing two sketched lines that have been inferred as being parallel as two perfectly parallel lines). Generally, the beautification module112produces an output that is referred to herein as a beautified drawing. Section A.3 provides additional details regarding one manner of operation of the beautification module112.

A pattern processing module114receives the beautified drawing as input. The pattern processing module114then attempts to find a predominant pattern in the beautified drawing. In one case, the pattern processing module114can perform this task by identifying transformations between different objects which appear in the beautified drawing. This yields a set of transformations that is generally referred to as transformation information herein. The pattern processing module114can then use a voting technique to identify one or more transformations that appear to be most prevalent within the transformation information. Such one or more transformations describe the predominant recurring pattern in the beautified drawing. The pattern processing module114can then use this pattern as a template to add at least one additional component to the beautified component. Section A.4 provides additional details regarding one manner of operation of the pattern processing module114.

An output module116can present an output drawing that reflects the output of any stage of the above-described processing. The output module116can also include a user interaction module118. The user interaction module118provides various tools that allow a user to modify the drawing at various stages of processing. For example, the user interaction module118can display the constraints that have been detected following the operation of the recognition module110. The user interaction module118can then invite the user to modify or remove any of the constraints that have been detected, and/or to add new constraints. Section A.5 provides further details regarding one manner of operation of the user interaction module118.

The output device106can correspond to an electronic display device of any type. Alternatively, or in addition, the output device106can correspond to any of: a printer; an interface which transmits an output drawing to a destination site; an interface which stores the output drawing, and so on.

In one implementation, the recognition module110, beautification module112, and pattern processing module114can be used together in the manner summarized above. Each of the recognition module110, beautification module112, and pattern processing module114can also be separately used in other contexts, with or without the inclusion of the other two modules. To cite one example, the pattern processing module114can be used to detect recurring patterns in objects which appear in any graph or drawing, where those objects may or may not have been produced by the recognition module110and the beautification module112.

Advancing toFIG. 2, this figure shows one example of the operation of the SPS102ofFIG. 1. In phase202, the user has just completed sketching an original drawing using the sketch input device104. In this particular scenario, the user intended to draw a first straight line L1which is tangent to a circle C1. The user also intended to draw a second straight line L2that is parallel to the first straight line L1. But since the user is sketching this drawing by hand, the geometric components and relationships are only roughly and imprecisely drawn.

After making the original drawing, the user may instruct the SPS102to commence its recognition processing. Alternatively, the user may produce the drawing in piecemeal fashion by toggling between the drawing phase and the recognition/beautification phases. That is, the user can instruct the SPS102to recognize and beautify the original drawing after creating only part of a complete drawing. The user may then add one or more new components to the beautified partial drawing that has been produced.

In phase204, the recognition module110and the beautification module112have processed the original drawing, producing the beautified drawing shown at the bottom ofFIG. 2. The beautified drawing indicates that the recognition module110has correctly interpreted the intent of the user to draw line L1tangent to the circle C1, and line L2parallel to line L1. The beautification module112has then correctly applied the recognized components and constraints to create a “clean” version of the original drawing, e.g., including perfectly straight lines L1and L2, and a perfectly round circle C1. Moreover, the beautification module112has correctly drawn the two lines (L1and L2) so that they are perfectly parallel, and the line L1so that it is perfectly tangent to the circle C1.

FIG. 3shows a second example of the operation of the SPS102. In phase302, the user has completed the original drawing. In this example, the user intended to draw a circle C1having four evenly-spaced spokes (L1, L2, L3, L4). But because the user is drawing by hand, this intent has only been roughly approximated in the original drawing. In phase304, the recognition module110and the beautification module112have correctly produced a formalized version of a circle with even-spaced four spokes. That is, each spoke is separated from its neighboring spoke by the precise angle α (except for the angle between lines L1and L4).

In phase306, the pattern processing module114has discovered that the four spoke lines establish a consistent pattern in the beautified drawing. That is, the pattern is exhibited by the fact that line L2is displaced from line L1by the angle α, line L3is displaced from line L2by the same angle α, and line L4is displaced from line L3by the same angle α. The pattern processing module114then applies the pattern by drawing new lines L5, L6, L7, and L8, each displaced from its predecessor line by the angle α, thereby completing the partial structured-drawing of the second phase304. (Note that the SPS102does not add components to the beatified drawing ofFIG. 2because this drawing does not include a recurring pattern.)

FIG. 4shows a third example of the operation of the SPS102. In phase402, the user has finished sketching an original drawing that resembles a ladder with rungs of increasing widths, where the rungs are equally spaced in the vertical dimension of the drawing. Again, however, the user has conveyed his or her intent in only a rough manner. In phase404, the recognition module110and the beautification module112have correctly produced a ladder having straight line segments that “cleanly” resembles the original drawing.

In phase406, the pattern processing module114has discovered the prevalent pattern exhibited by the ladder shown in phase404. More specifically, in this case, the pattern processing module114has identified two different prevalent transformations in the beautified drawing. The first transformation corresponds to the offset of each rung's left endpoint with respect to its predecessor rung's left endpoint along the line L1. The second transformation corresponds to the offset of each rung's right endpoint with respect to its predecessor rung's right endpoint along the line L2. These two transformations form a higher-order pattern insofar as the first and second transformations are exhibited in two sides of the same rungs. The pattern processing module114has then applied the detected higher-order pattern to produce additional rungs, e.g., rungs L6and L7, etc. Section A.4 will clarify one manner by which the pattern processing module114can achieve the result illustrated inFIG. 4.

FIG. 5shows various implementations of the SPS102introduced inFIG. 1. In a first implementation, local computing functionality502implements all aspects of the SPS102. In a second implementation, remote computing functionality504implements all aspect of the SPS102. The user may gain access to the remote processing functionality504via the local processing functionality502, via a communication conduit506. In a third implementation, the local computing functionality502implements some aspects of the SPS102(as indicated by sketch processing system functionality102A provided by the local processing functionality502), while the remote computing functionality504implements other aspects of the SPS102(as indicated by sketch processing system functionality102B provided by the remote processing functionality504).

In any implementation, the local computing functionality502can correspond to any user device, such as, but not limited to, a personal computer, a computer work station, a tablet computing device, a laptop computing device, a netbook computing device, a game console device, a set-top box device, a smartphone device, a personal digital assistant device, a portable game device, an electronic book reader device, and so on.

The remote computing functionality504can correspond to one or more sever computers and associated data stores, routing functionality, etc. The equipment associated with the remote computing functionality504can be provided at a single site or can be distributed over plural sites.

The communication conduit506can correspond to any local area network, wide area network, or combination thereof. The communication conduit506can include any combination of wireless links and hardwired links, and can be governed by any protocol or combination of protocols.

A.2. Recognition Module

FIG. 6shows one implementation of the recognition module110. The recognition module110includes a component recognition module602that performs the task of recognizing primitive components in the original drawing, such as straight lines and circles. More specifically, the component recognition module602includes recognition logic604for recognizing components, as governed by rules provided in a data store606. The component recognition module602stores information regarding components that it has detected in a data store608. For brevity, this disclosure states that the data store608stores the components (as opposed to information regarding the components).

The component recognition module602can use any approach to recognize primitive components. For example, the component recognition module602can identify cusps in ink strokes drawn by a user. A cusp corresponds to a region of high curvature in a digital ink stroke, e.g., corresponding to an endpoint, a corner, etc. The component recognition module602can then examine each ink stroke that includes two cusps to determine what kind of component it corresponds to. If an ink stroke includes more than two cusps, the component recognition module602can break it up into segments containing two cusps each and then analyze each such segment.

For example, the component recognition module602can determine whether an ink stroke corresponds to a circle by determining whether it satisfies the following representative characteristics: (a) the cusps of the ink stroke (corresponding to its endpoints) are within a prescribed close distance to each other; and (b) the path of the ink stroke has approximately uniform curvature about a centroid. The component recognition module602can determine whether the ink stroke has uniform curvature by measuring the standard deviation of its radius, and then comparing that standard deviation with a threshold. If an ink stroke has been classified as a circle, the component recognition module602can identify the center of the circle as the centroid of the ink stroke. Further, the component recognition module602can identify the diameter of the circle as an average of the width and height of a bounding box which encloses the ink stroke.

The component recognition module602can determine whether an ink stroke corresponds to a straight line by determining a linearity measure for the ink stroke, as in:

In this expression, picorresponds to any point along the ink stroke, where p1is the first point and pnis the last point. In one implementation, the component recognition module602can interpret an ink stroke as straight if Linearity <0.1. The component recognition module602can use any environment-specific rules to formally represent a detected straight line segment. For example, the component recognition module602can identify the slope of a line segment as the slope of the line which connects its endpoints, or the average slope of sub-segments which compose the line segment, and so on.

In addition to classifying each component (e.g., as either a line or a circle), the component recognition module602can store information regarding the relative order in which the component was created in the course of creating the original drawing. The component recognition module602can also store information regarding a canonical order in which the component appears in the original drawing. One such canonical ordering O arranges components from left to right followed by top to bottom, such that a component closest to the upper left-hand corner of the original drawing corresponds to the first entry in the ordering O and the component closest to the lower right-hand corner of the drawing corresponds to the last entry in the ordering O. This ordering O helps ensure that a deterministic view of each diagram emerges, independent of the order in which its components were drawn.

The component recognition module602can also store a probability score for each component that describes a level of certainty at which it has estimated the class of the component. The component recognition module602can form this score by determining how closely the characteristics of an ink stroke match the predetermined canonical characteristics of a line or circle.

The rules stored in the data store606may govern the behavior of the component recognition module602. For example, the rules may govern: (a) the type of components that the component recognition module602attempts to find in the original drawing; (b) the techniques that the component recognition module602uses to find the components; and (c) the parameters (e.g., thresholds) that the techniques use in detecting the components, etc. These rules are both extensible and customizable. They are extensible in the sense that any user (e.g., an end user, a developer, etc.) can add new rules and remove existing rules. They are customizable insofar any user can modify the parameter values and/or other adjustable features of the rules to address any environment-specific objectives.

The recognition module110also includes a constraint recognition module610that performs the task of recognizing geometric constraints associated with the components that have been detected by the component recognition module602. More specifically, the constraint recognition module610includes recognition logic612for recognizing constraints, as governed by rules provided in a data store614. The constraint recognition module610stores information regarding constraints that it has detected in a data store616. For brevity, this disclosure states that the data store616stores the constraints (as opposed to information regarding the constraints). The constraint recognition module610can also store probability scores which reflect the level of confidence at which it has detected each constraint.

More specifically, in one approach, the data store606can identify a list of known constraints that may be present in the original drawing. Some of these constraints pertain to characteristics of an individual component. Other constraints pertain to geometric relationships between two or more components.

Without limitation, in one implementation, the following constraints may pertain to any line segment in the original drawing: (a) the line segment is a vertical line segment; (b) the line segment is a horizontal line segment; (c) the line segment is collinear with another line segment; (d) the line segment is parallel to another line segment; (e) the line segment is perpendicular to another line segment; (f) the line segment is a member of a group of line segments that are equidistant to each other; (g) the line segment touches another line segment; (h) the line segment intersects with another line segment; (i) the line segment has the same length as another line segment; (j) the line segment has an endpoint that is at the same horizontal level as another line segment; (k) the line segment has an endpoint that is at the same vertical level as another line segment, and so on.

The following constraints may pertain to any circle in the original drawing: (a) the circle shares the same radius as another circle; (b) the circle is concentric with respect to another circle; (c) the circle touches another circle at its circumference; (d) the circle intersects with another circle; (e) the circle has a circumference that passes through the center of another circle, and so on.

The following constraints may pertain to any line in relation to a circle in the original drawing: (a) the line segment is tangent to the circle; (b) the line segment intersects the circle; (c) the line segment passes through the center of the circle; (d) the line segment touches the circumference of the circle with an endpoint; (e) the line segment touches the center of the circle with an endpoint, and so on.

In general, some of the above-described relational constraints are set forth with respect to two components. But, more generally, a constraint can be defined with respect to any number of components.

The constraint recognition module610also identifies the rules that the constraint recognition module610can use to determine whether each constraint is present in the original drawing. For example, consider the following representative rules.

Parallel Line Rule.

The constraint recognition module610can determine whether an angle between two lines is below a prescribed threshold. If so, the constraint recognition module610can conclude that the lines are parallel.

Same Length Rule.

The constraint recognition module610can determine whether the length of a first line segment is within a prescribed tolerance of the length of another line segment. If so, the constraint recognition module610can conclude that these lines are the same length.

Same Radii Circle Rule.

The constraint recognition module610can determine whether the radius of a first circle is within a prescribed tolerance of the radius of another circle. If so, the constraint recognition module610can conclude that these circles have the same radii.

Tangent Line Rule.

The constraint recognition module610can investigate the relationship between a line L and a circle C by drawing a test line from the center of the circle C to the line L, forming a perpendicular with that line L. The constraint recognition module610then determines the distance between the point at which the test line intersects the circumference of the circle C and the line L. If this distance is below a prescribed threshold distance, then the constraint recognition module610concludes that the line L is tangent to the circle C.

The set of rules provided in the data store614is both extensible and customizable. The rules are extensible in the sense that any user can add new rules and/or remove existing rules. By doing so, the user can also instruct the constraint recognition module610to detect new types of constraints, and/or to detect existing types of constraints in a new manner. The rules are customizable insofar as the user can modify the parameter values and/or other adjustable features of the rules to address any environment-specific objectives.

Finally,FIG. 6indicates that a user can add explicit constraints to the data store616to supplement the implicit constraints recognized by the constraint recognition module610. The user can perform this task in at least two ways. In a first approach, the user can add a marking to the original drawing which conveys an explicit constraint. In a second approach, the user can specify an explicit constraint via a separate interface, e.g., in textual form or in some other form. Section A.5 will provide additional details regarding illustrative ways that a user can convey explicit constraints.

FIG. 7shows one implementation of the beautification module112. To review, the beautification module112converts the recognized drawing into a beautified drawing. In doing so, the beautification module112redraws the original drawing so that it “cleanly” conforms to the constraints that have been recognized by the recognition module110.

To begin with, the beautification module112includes a sub-component identification module702that enumerates the sub-components within each component that has been recognized by the recognition module110. A sub-component refers to a descriptive part of a component. For example, a straight line segment is made up of the following sub-components: (a) a slope of the line segment; (b) an intercept of the line segment (that is, a y-intercept of the line segment if the line segment is not vertical; otherwise an x-intercept); (c) the individual x and y coordinates of the line segment's two endpoints; and (d) a length of the line segment. A circle is made up of the following sub-components: (a) the individual x and y coordinates of its center; and (b) its radius. As stated above, other implementations can recognize other primitive components, such as arcs, and ellipses. These components will have their own respective sub-components. For example, the sub-components of an ellipse will also include information regarding its major and minor axes.

The sub-component identification module702stores information regarding the identified sub-components in a data store704. At this point, the beautification module112may simply store all (or most) of these sub-components as variables without determinative values. For example, the sub-component identification module702will record that a particular line L includes two endpoints, but, at this initial stage, the beautification module112may not know the x-y coordinates of those endpoints (corresponding to the placement of the line L in the beautified drawing). In the terminology used herein, these sub-components are said to be “unresolved.” Once the values of the sub-components are known, these sub-components become resolved. Hence, at the outset, the data store704provides a master set (labeled as set A) of the unresolved sub-components.

The beautification module112next goes to work by iteratively discovering the values of the unresolved sub-components in the set A. Once any subset of the sub-components of a component that uniquely determine that component are all resolved, the component itself is said to be resolved. Before that time, the component is said to be unresolved. To perform this iterative operation, the beautification module112relies on three main components: a sub-component derivation module706; a component derivation module708; and a sub-component selection module710. As a point of clarification, note that while a component may be “unresolved” in the context of its eventual placement in the beautified drawing, that component has a known placement in the original drawing (as detected by the recognition module110). As will be clarified in the ensuring description, the beautification module112can leverage this “raw” placement information in various circumstances in the production of the beautified drawing.

Consider first the operation of the sub-component derivation module706. This module includes derivation logic712which works in conjunction with an extensible and customizable set of rules stored in a data store714. In operation, the sub-component derivation logic712first selects a sub-component siwithin the master set (A) of sub-components (stored in data store704) which has yet to be resolved (e.g., meaning that its value(s) are unknown). The sub-component derivation module706will then determine whether this sub-component can be derived based on: (a) information associated with components that are already known (resolved), as stored in another set (B) provided in a data store716; (b) the recognized constraints determined by the recognition module110which affect this sub-component si; and (c) the derivation rules provided in the data store714. If the sub-component sican be derived, the sub-component derivation module706will add a resolved counterpart of the sub-component sito the set B in the data store716.

More specifically, each derivation rule provided in the data store714specifies how to determine the value of some sub-component from values of some other sub-component(s) under some appropriate constraint(s). For example, suppose that it has been determined that a line L is tangent to a circle C. A first rule can leverage this constraint by stating that the radius of the circle can be computed based on the center of the circle C, the slope of the line L, and the intercept of the line L. In particular, the radius can be computed as the perpendicular distance between the center of the circle and the line L (where the path of line L is determined by its slope and its intercept). Another rule that is applicable to this constraint states that the intercept of the line L can be computed from the slope of the line L, the center of the circle C, and the radius of the circle C.

Now advancing to the sub-component selection module710, this module is invoked whenever the sub-component derivation module706determines that it is unable to find any sub-components that can be resolved in the above-described manner, e.g., based on the previously resolved sub-components in the set B, the applicable constraints, and the rules in the data store714. This may happen at any point in the processing of the recognized drawing. For example, at the beginning of its analysis, the beautification module112may not have enough concrete information to determine the values of any sub-component. This may also happen at any point in the processing of a drawing that includes separate parts that are isolated from each other. In any event, the sub-component selection module710breaks such an impasse by finding an unresolved sub-component that is deemed most worthy to resolve. The sub-component selection module710then determines the value of this selected sub-component based on drawing information extracted directly from the original drawing.

FIG. 8elaborates on one illustrative composition of the sub-component selection module710. This module710includes ranking logic802for examining all sub-components that have yet to be fully resolved. The ranking logic802then selects the sub-component that is considered the most appropriate to resolve.

In one example, the ranking logic802can rank the sub-components by performing lexicographic ordering using the following formula:

From a high-level perspective, this formula assigns a rank to each unresolved sub-component s under consideration. The sub-component s belongs to a particular parent component C. The formula has three parts. The first part assigns a score to the component C based on its assessed suitability for resolution. The second part (O(C)) assigns a score to the component C based on the order in which the component C appears in the original drawing, e.g., by making reference to the canonical ordering. The third part assigns a score to the particular sub-component s under consideration.

In operation, the beautification module112uses the first part of the ranking formula to find the component Cwinthat is deemed most appropriate to resolve. If two or more components have the same score, the beautification module112can use the second part of the formula to select a single component Cwinfrom among this set of same-score components. For example, the beautification module112can pick the component that has the lowest order in the canonical ordering (O(C)) of components. Having selected the top-ranking component Cwin, the beautification module112can then use the third part of the ranking formula to select the unresolved sub-component swinof the component Cwinthat is considered most appropriate to be resolved (if, in fact, there are more than one unresolved sub-component in Cwin). As will be described below in greater detail, the beautification module112will then extract the value of swinfrom its “raw” value in the original drawing, and store this value in the set B of known sub-components in the data store716.

Consider the first part of the ranking formula in greater detail. In this expression, each S refers to a minimal set of sub-components of the component C (where, as said, C is the “parent” of the component s) that uniquely determine the component C. That is, there can be multiple different combinations of sub-components which uniquely determine the same component C; therefore, there can be multiple sets S. Each member of a set S is denoted as s′. The numerator of the expression identifies a sum that is formed based on the known sub-components of a particular set S. In one implementation, the elements of that sum are provided by applying some weighting function W (s′). The denominator of the expression identifies a sum that is formed based on all of the sub-components in the particular set S, regardless of whether they are known or unknown. Again, the elements of that sum are provided by applying the weighting function W(s′). The expression as a whole finds a maximum value by considering different sets (S) that can be used to uniquely determine C.

In one implementation, the weighting function W(s′) maps each sub-component to some score between 0 and 1. Hence, this weighting function can be used to assert the relative importance of knowing some sub-component over another sub-component. More specifically, recall that the overall purpose of the ranking formula is to identify the winning sub-component swin(which belongs to the winning component Cwin) that is considered the most appropriate sub-component to resolve by using a “raw” value extracted from the original drawing. Some sub-components are more effective to resolve in this empirical manner than others for various reasons. For example, an inconsistency in the slope of a line may be more visually discernible than the length of the line; this makes the length of the line more preferable to resolve based on empirical evidence compared to the slope. In addition, or alternatively, errors in the placement of some sub-components may be easier to later resolve compared to errors in other sub-components. The weighting function assigns weights to sub-components that reflect these types of considerations. For example, for a line, in one merely illustrative case, the weighting function can assign the scores of: 0.5 to each endpoint; 0.5 to the length; 0.75 to the intercept; and 1.0 to the slope. For a circle, the weighting function can assign the scores of: 0.5 to each endpoint; and 1.0 to the radius.

In the context of the first part of the ranking formula, the weighting function acts to bolster the score of components which have strongly-weighted sub-components that are already known. In the context of the third part of the ranking formula, the weighting function disfavors strongly-weighted unknown sub-components. For example, consider a component in which the slope is known. The first part of the ranking formula can identify this component as a good candidate to resolve because a strongly-weighted sub-component (i.e., slope) is already known. The beautification module112can then leverage the third part of the ranking formula to identify the unknown sub-component swinof this component that is least problematic to resolve based on empirical evidence.

The weighting function can also be enriched by taking into consideration a level of confidence at which a sub-component is considered to be known. For example, the beautification module112may have obtained the value of a sub-component, in part, by applying a relationship defined by a particular constraint. Further, the recognition module110may have detected that constraint with a certain confidence, as expressed by a probability score. The weighting function can take the probability score into account when weighting that particular sub-component. In addition, or alternatively, the weighting function can take into account the confidence at which the recognition module110has recognized the particular component.

In yet another variation, the weighting function assigns all sub-components a weight of 1.0. This effectively removes any role the weighting function may have in selectively promoting some sub-components over other sub-components. That is, with this weighting option, the summation in the numerator sums up the number of known sub-components in S, while the summation in the denominator sums up an entire number of sub-components in S, without respect to whether they are known or unknown.

The above manner operation is set forth by way of example, not limitation. More generally, the operation of the ranking logic802can be determined by extensible and customizable rules provided in a data store804. The rules can specify the factors that are taken into account when ranking sub-components, the equation (s) to be used to rank the sub-components, the values of parameters to be used in the equation (s), and so on.

Having selecting a sub-component swinthat is deemed most appropriate, a sub-component extraction module806determines the value of this sub-component from information extracted from the original drawing. For example, suppose that the winning sub-component swincorresponds to the x coordinate of an end-point of a line segment. The sub-component extraction module806will consult the original drawing to determine the x coordinate of this endpoint of the line segment.

In the above explanation, the beautification module112invokes the sub-component selection module710whenever it reaches an impasse in deriving sub-components based on the set B of known sub-components. But in another implementation, the beautification module112can using a ranking operation each time that it attempts to resolve an unknown sub-component, regardless of whether an impasse has been reached. That is, the beautification module112can identify a sub-component that is deemed most worthy of resolution, and then attempt to resolve it.

Returning toFIG. 7, having successfully determined a sub-component (either by inference or by reading it from the drawing), the beautification module112next invokes the component derivation module708. The component derivation module708includes derivation logic718which works in conjunction with an extensible and customizable set of rules stored in a data store720. In operation, the component derivation module708determines whether it can now fully resolve the parent component C to which the sub-component s that has just been determined belongs. For example, suppose that the sub-component derivation module706has determined the x coordinate of one end-point associated in a line L. The component derivation module708asks whether it can now fully determine this line. The component derivation module708can make this determination based on: (a) information associated with sub-components that are already known (resolved), as stored in the set (B) provided in the data store716; and (b) the derivation rules provided in the data store720. If the component C can be fully resolved, the component derivation module708will resolve it and all of its sub-components and store them in the data store716.

Consider the following representative rules that may be stored in the data store720. A first rule states that a line is uniquely determined from the x-y coordinates of the two endpoints, or even from its slope, intercept, and y coordinates of its two endpoints (if the slope is not vertical). Another rule states that a circle is uniquely determined if all of its sub-components are known.

As a closing general observation, note that there may be multiple ways that the beautification module112can successfully derive a particular sub-component or a particular component. This characteristic is advantageous because it allows the beautification module112to robustly resolve sub-components within the drawing, even though certain constraints were not correctly recognized by the recognition module110.

To illustrate the above point, consider the example in which the user sketches a square having a left line segment and a right line segment that are each roughly vertical, and a top line segment and a bottom line segment that are roughly horizontal. The SPS102will ideally infer the following constraints between the four recognized line segments: (1) Two line segments are horizontal and two are vertical; (2) The horizontal line segments are parallel, and are both perpendicular to the vertical line segments; (3) The vertical line segments are parallel, and are both perpendicular to the horizontal line segments; (4) All the line segments in the sketch form a connected path, and are all equal in length; (5) The perpendicular distance between horizontal line segments is the same as that between vertical line segments.

Beautification may proceed as follows. After computing the slope of all the line segments, the algorithm reads off the x-y coordinates of the top-left corner and the y-coordinate of the bottom-left corner from the sketch and then beautifies the left line segment. Next, the algorithm computes the y coordinate of the top-right corner from the y coordinate of the top-left corner (based on the top line segment having the horizontal slope constraint), and then the x coordinate of the top-right corner from the two left corners (based on the equal length constraint between the top and left line segments), and then beautifies the top line segment.

In a manner similar to the previous operation, the algorithm computes the y coordinate of the bottom-right corner from the y coordinate of the bottom-left corner (based on the bottom line segment having the horizontal slope constraint), and then the x coordinate of the bottom-right corner from the two left corners (based on the equal length constraint between the bottom and left line segments), and then beautifies the bottom line segment.

However, suppose that the SPS102failed to infer any equal length constraint involving the bottom line segment. The algorithm can still compute the x coordinate of the bottom-right corner from the x coordinate of the top-right corner (based on the right line segment having the vertical slope constraint). Next suppose that the SPS102also failed to infer the vertical slope constraint for the right line segment. The algorithm can still compute the slope of the right line segment from the slope of the top line segment (based on the perpendicular constraint between the top and right line segments), followed by computing the intercept of the right line segment from the x coordinate of the top-right corner. The algorithm can then compute the x coordinate of the bottom-right corner from the two top corners (based on of the equal length constraint between the right and top line segments). These instances of missing constraints highlight the robustness of the beautification algorithm, which is able to make up for the missing constraints by making effective use of other (logically equivalent) constraints.

A.4. Pattern Processing Module

FIG. 9shows one implementation of a pattern processing module114that can be used in the SPS102ofFIG. 1. As previously stated, the pattern processing module114determines whether there are any repeating patterns in the beautified drawing. If so, the pattern processing module114invites the user to add one or more new components to the beautified drawing using the detected pattern.

The pattern processing module114includes a transform extraction module902which receives, as input, all of the sub-components associated with the beautified drawing (which have all been resolved at this stage). The transform extraction module902processes each pair of the sub-components to determine a transformation that will convert the first member of the pair into the second member (or vice versa). This yields a plurality of transformations. That is, in the case in which there are n sub-components, the transform extraction module902produces O(n2) transformations. Collectively, this set of transformations is referred to as transformation information herein.

A voting module904then determines at least one transformation that is most common in the transformation information. This transformation(s) corresponds to a repeating pattern in the beautified drawing. A drawing extension module906then uses the determined pattern to add one or more new components to the beautified drawing.

A data store908provides an extensible and customizable set of rules which determine the manner of operation of the transform extraction module902and the voting module904. For example, the rules can determine the way that the transform extraction module902expresses the transformation between the members of each pair of sub-components. In some implementations, for instance, the transformation extraction module902determines an affine transformation between the members of each pair of sub-components. The rules can also determine the type of voting technique that is used by the voting module904to assess the commonality of each detected transformation. In some implementations, the voting module904can form an un-weighted or weighted sum of the number of equivalent transformations that are encountered. In addition, the rules can define various parameter values used by the transform extraction module902and/or the voting module904to perform their respective functions.

FIG. 10shows an example of the operation of the pattern processing module114ofFIG. 9, corresponding to the scenario introduced inFIG. 4. In phase1002, the pattern processing module114can determine a plurality of transformations (e.g., transformations T1-T6) between pairs of endpoints in the ladder, where each endpoint is defined by x-y coordinates. More generally, the pattern processing module114can generate a transformation between any pair of sub-components (or any pair of sub-component-combinations) of any type (that is, not just endpoints defined by x-y coordinates). For example, the pattern processing module114can form a transformation based on intercept information, slope information, and so on (although the slope information will not yield meaningful information in the ladder example because the rungs have the same slope). In addition, although not illustrated, the pattern processing module114can consider any pair of endpoints in which the first endpoint is taken from the left side of the ladder and the second endpoint is taken from the right side of the ladder.

In phase1004, the pattern processing module114identifies two prevalent transformations. A first transformation Taindicates that each endpoint on the left side of the ladder can be produced from its lower-adjacent neighbor by moving up a prescribed distance, and then over to the left a prescribed distance. Similarly, a second transformation Tbindicates that each endpoint on the right side of the ladder can be produced from its lower-adjacent neighbor by moving up a prescribed distance, and then over to the right a prescribed distance. The horizontal displacement specified by Tamay differ from the horizontal displacement specified by Tb. The pattern processing module114can also determine that these two transformations are part of the same higher-order pattern because they pertain to endpoints on either side of the same rungs.

In phase1006, the pattern processing module114applies the two transformations (Taand Tb) to add at least one new component line L6to the ladder. Note that each transformation (Taand Tb) can be separately expressed as an affine transformation, yet the progression in the width of the rung lines cannot be expressed with a single affine transformation. This example demonstrates that the pattern processing module114provides a versatile mechanism for determining different types of patterns within the beautified drawing; at the same time, the pattern processing module114can still leverage the efficiency and power of the affine transformation.

Other patterns can be expressed as a single transformation, such as the pattern exhibited in by the regular angular displacement of spokes inFIG. 3.

More generally stated, the principles described above can be applied to any objects within any drawing, originating from any source. In the above-described case, the objects happen to correspond to the sub-components within a beautified drawing produced by the recognition module110and the beautification module112.

A.5. User Interaction Module

FIG. 10shows one implementation of a user interaction module118. The user interaction module118can include a recognized drawing modification module (RDMM)1102for making changes to the original drawing and/or the recognized drawing. The user interaction module118also includes a beautified drawing modification module (BDMM)1104for making changes to the beautified drawing. The user interaction module118can also include a pattern modification module1106for guiding the pattern processing module114in the selection of a pattern and in the placement of new components based on the selected pattern.

FIG. 12shows a user interface presentation1202that may be presented by the RDMM1102. This user interface presentation1202can include a first display section1204for presenting a depiction of the original drawing as hand-drawn by the user. That drawing corresponds to the scenario ofFIG. 2. That is, the drawing includes a line L1which is intended to be parallel to another line L2; the line L1is also intended to be tangent to a circle C.

The user interface presentation1202also includes a display section1206that displays all of the constraints that the recognition module110has recognized (illustrated inFIG. 12in only generic form). This display section1206allows the user to review the accuracy of the constraints and modify the constraints in any manner. For example, the user can conclude that a constraint has been recognized that he or she did not intend. In response, the user can remove that constraint by clicking on its check box in the display section1206(in one merely illustrative user interface example).

In addition, or alternatively, a user can activate an “add constraint” command1208to add a new explicit constraint to the list of implicitly-recognized constraints. For example, the user can perform this task by selecting one or more components in the original or revised drawing. The user can then access a contextual menu which identifies a set of possible constraints that can be defined for this particular component or combination of components. The user can then select a desired constraint from that menu. Alternatively, the user can express a new constraint in entirely textual form, e.g., by expressing the components and constraints with appropriate symbols. The user can also modify any existing constraint in the same manner, e.g., by modifying its textual description.

In addition, or alternatively, the user can annotate the original drawing itself with markings that convey explicit constraints. For example, when creating the original drawing, the user has added a pair of arrow heads1210to lines L1and L2. This marking indicates that these lines are intended to be parallel. The user has added another marking1212to indicate that the length of line L2is 3 cm, e.g., by writing the text “3 cm” so that it is aligned in parallel with L2. These markings are described by way of example not limitation; other implementations can adopt other markings to convey other types of constraints. In any event, the recognition module110can include functionality for recognizing these hand-drawn explicit constraints. The recognition module110can then add these constraints to the list of implicitly-recognized constraints.

The user interface presentation1202can also include various commands (1214,1216,1218) that instruct the SPS102to commence (or repeat) different phases of analysis, such as the recognition phase, the beautification phase, and the pattern recognition phase. At this stage, the pattern recognition option is currently disabled because the user has not yet formed the beautified drawing. In an alternative implementation, the SPS102can automatically commence the beatification phase for each component once it deems it possible to fully resolve the sub-components in this component.

Although not shown, the user can also interact with a user interface presentation that is similar to that shown inFIG. 12when creating the original drawing, that is, prior to any recognition being performed. For example, the user can use such a user interface presentation to add explicit constraints in any of the ways described above.

FIG. 13shows a user interface presentation1302that may be presented by the BDMM1104. This user interface presentation1302can include a first display section1304for presenting a depiction of the beautified drawing that corresponds to the original drawing shown inFIG. 12. At this stage, the BDMM1104may allow the user to adjust various aspects of the components in the beautified drawing. For example, the display section1304can display edit points (1306,1308,1310,1312, etc.). The user can adjust the positions of these edit points (e.g., by dragging on them) to make corresponding desired changes to the components. Although not shown, the user can also modify constraints associated with the beautified drawing in same the manner described above with respect toFIG. 12.

FIG. 14shows a user interface presentation1402that may be presented by the pattern modification module1106. This user interface presentation1402can include a first display section1404for presenting a depiction of a beautified drawing, in this case, corresponding to a ladder with increasing-width rungs introduced inFIG. 4. The user interface presentation1402also indicates that it has detected a pattern in the drawing that, when applied, will produce at least one new line L6. The pattern processing module114draws the line L6on top of the line L5based on the order in which the user has drawn lines L3-L5. That is, assume that the user drew L3first, followed by line L4, followed by line L5. Based on this progression, the pattern processing module114can assume that the user intends to add a rung above line L5, not below line L3.

The pattern processing module114can also present a dialog box1406which asks the user to confirm that the indicated line L6represents an instance of a correctly-detected recurring pattern in the drawing. The dialog box1406also invites the user to specify how many times that the pattern is to be applied to create new components. In this case, the user has instructed the pattern processing module114to add three new rungs.

FIGS. 15-19show procedures that explain one manner of operation of the sketch processing system (SPS)102ofFIG. 1. Since the principles underlying the operation of the SPS102have already been described in Section A, certain operations will be addressed in summary fashion in this section.

Starting withFIG. 15, this figure illustrates a procedure1500that provides an overview of one manner of operation of the SPS102ofFIG. 1. In block1502, the SPS102receives ink strokes in response to creation of an original drawing. In block1504, the SPS102recognizes components and constraints in the original drawing, to provide a recognized drawing. In block1506, the SPS102beautifies the recognized drawing to produce a beautified drawing. In block1508, the SPS102recognizes a pattern in the beautified drawing and adds a new component by applying this pattern. In block1510, the SPS102provides an output drawing which reflects the processing performed in any of the preceding processing stages illustrated inFIG. 15.FIG. 15also indicates that the SPS102can interact with a user to control various aspects of the operation of the SPS102, e.g., by repeating one or instances of the drawing operation, the recognition operation, the beautification operation, and the pattern-processing operation, etc.

FIG. 16is a procedure1602that describes one manner of operation of the recognition module110ofFIG. 6. In block1602, the recognition module110receives ink strokes and any explicitly-stated constraints specified by the user. In block1604, the recognition module110recognizes components (e.g., lines and circles) in the original drawing. In block1606, the recognition110recognizes geometric constraints associated with the components that were detected in block1604. Blocks1604and1606can rely on rules provided in an extensible and customizable set of rules. In block1608, the recognition module110stores the recognized components and constraints. In block1610, the recognition module110can optionally receive and respond to the user's modification of the constraints and/or other features of the original drawing, e.g., using the functionality illustrated inFIG. 12.

FIG. 17is a procedure1700that describes one manner of operation of the beautification module112ofFIG. 7. In block1702, the beautification module112populates a set A to identify all of the unresolved sub-components associated with the recognized drawing. In block1704, the beautification module112identifies a next (or first) unresolved sub-component to resolve. The beautification module112then resolves it if possible using inference, e.g., based on the previously resolved sub-components in the set B, the rules in the data store716, etc. In block1706, the beautification module112asks whether an unresolved sub-component has in fact been found and resolved in block1704using inference. If not, the beautification module112invokes the procedure ofFIG. 18(described below) to resolve a sub-component based on empirical information extracted from the original drawing. In block1708, the beautification module112stores the sub-component that has been resolved (either by the operation of block1706or the procedure ofFIG. 18) in a set B of resolved components.

In block1710, the beautification module112determines whether it is possible to fully resolve a component C which is the parent of the sub-component s that has been just resolved. If this is possible, the beautification module112resolves the component C and each of the remaining unresolved sub-components of C. Upon a successful resolution (as assessed in block1712), in block1714, the beautification module112then updates the set B in the data store716.

FIG. 18shows a procedure1800that represents one manner of operation of the sub-component selection module710ofFIG. 8, which is part of the beautification module112. In one implementation, the sub-component selection module710is invoked when the beautification module112cannot find a sub-component that can be resolved based on the set B of previously-resolved sub-components (together with the constraints, and rules in the data store714). In block1802, the sub-component selection module710ranks unresolved sub-components based on the various factors described in Section A, to identify a selected sub-component swinthat is considered most suitable for resolution. In block1804, the component sub-selection module710extracts the value of the unresolved sub-component swinfrom the original drawing itself.

FIG. 19is a procedure1902that describes one manner of operation of the pattern processing module114ofFIG. 9. In block1902, the pattern processing module114receives the beautified drawing from the beautification module112. In block1904, the pattern processing module114identifies a recurring pattern in the beautified drawing. More specifically, the pattern processing module114can perform block1902by determining transformations between pairs of sub-components in the beautified drawing (in block1906). This, in general, yields transformation information. Then, in block1908, the pattern processing module114uses a voting mechanism to identify the most common transformation or transformations in the transformation information.

In block19010, the pattern processing module114optionally invites the user to authorize and direct the manner in which the pattern processing module114will modify the beautified drawing based on the detected pattern. In block1912, the pattern processing module114adds at least one component to the beautified drawing based on the pattern that has been detected, and based on any user guidance provided in block1910.

C. Representative Computing functionality

FIG. 20sets forth illustrative computing functionality2000that can be used to implement any aspect of the functions described above. For example, the computing functionality2000can be used to implement any aspect of the sketch processing system (SPS)102, e.g., as implemented in any of the implementations set forth inFIG. 5. In one case, the computing functionality2000may correspond to any type of computing device that includes one or more processing devices. In all cases, the computing functionality2000represents one or more physical and tangible processing mechanisms.

The computing functionality2000can include volatile and non-volatile memory, such as RAM2002and ROM2004, as well as one or more processing devices2006(e.g., one or more CPUs, and/or one or more GPUs, etc.). The computing functionality2000also optionally includes various media devices2008, such as a hard disk module, an optical disk module, and so forth. The computing functionality2000can perform various operations identified above when the processing device(s)2006executes instructions that are maintained by memory (e.g., RAM2002, ROM2004, or elsewhere).

More generally, instructions and other information can be stored on any computer readable medium2010, including, but not limited to, static memory storage devices, magnetic storage devices, optical storage devices, and so on. The term computer readable medium also encompasses plural storage devices. In all cases, the computer readable medium2010represents some form of physical and tangible entity.

The computing functionality2000also includes an input/output module2012for receiving various inputs (via input modules2014), and for providing various outputs (via output modules). One particular output mechanism may include a presentation module2016and an associated graphical user interface (GUI)2018. The computing functionality2000can also include one or more network interfaces2020for exchanging data with other devices via one or more communication conduits2022. One or more communication buses2024communicatively couple the above-described components together.

The communication conduit(s)2022can be implemented in any manner, e.g., by a local area network, a wide area network (e.g., the Internet), etc., or any combination thereof. The communication conduit(s)2022can include any combination of hardwired links, wireless links, routers, gateway functionality, name servers, etc., governed by any protocol or combination of protocols.

Alternatively, or in addition, any of the functions described in Sections A and B can be performed, at least in part, by one or more hardware logic components. For example, without limitation, illustrative types of hardware logic components that can be used include Field-programmable Gate Arrays (FPGAs), Application-specific Integrated Circuits (ASICs), Application-specific Standard Products (ASSPs), System-on-a-chip systems (SOCs), Complex Programmable Logic Devices (CPLDs), etc.

In closing, the description may have described various concepts in the context of illustrative challenges or problems. This manner of explanation does not constitute an admission that others have appreciated and/or articulated the challenges or problems in the manner specified herein.