Ada Lovelace Day 2021 Special Feature: From ink to digital diagrams

Imagine if you could hand-draw a diagram, and your computer could automatically understand the ideas you were trying to convey.  What if your computer could then automatically translate your sketch to code, or assist you with editing, beautification, and animation?  How many hours in front of your computer could this save you? 

Diagrams are a critical means of communication in many areas including design, technical documentation, and education, allowing a visual and unconstrained representation of information. While computer-supported diagramming is superficially attractive, current technology needs significant improvement before it will really be useful.

There are several important processes that are required for computers to automatically infer the meaning of digital ink sketches (i.e. develop a conceptual model). This requires grouping of sketched strokes into components, followed by definition of individual components of the sketch, to gain a high-level understanding.  Current approaches often require input from experts, which is time-consuming and very tedious, and lack effectiveness and scalability.

Marsden Fund Fast-Start awardee, Dr Rachel Blagojevic (Massey University) has worked with a team of researchers to develop a sketch recognition system that can recognise and group digital ink components accurately and efficiently.  The purpose was to develop a system that is not constrained to a particular type of diagram or an individual’s sketching style. Building on this, she is investigating how the overall meaning of a diagram can be automatically inferred to complete the conceptual model of a sketched diagram.

Hand-drawn diagram of how the sketch recognition system functions (Supplied).

Dr Blagojevic and team's novel system is composed of several components. The first algorithm groups strokes from a sketched diagram into individual components. This ‘grouper’ works in a continuous interaction with a ‘recogniser’, in a manner not attempted previously. Evaluations showed that the grouper can perform the grouping task efficiently, and that the interactions between the grouper and recogniser produces accurate results. The recognition step also involves a ‘rejection’ system that uses novelty detection techniques to identify invalid shape candidates. They tested several different approaches for rejecting invalid shape candidates and identified the best approach. This approach used a method based on the proximity of components to the training set and can deal with incomplete shapes.  The use of such novelty detection techniques has not been researched extensively in sketch recognition previously. Finally, any remaining unrecognised strokes are passed to a unique ‘connector recognition’ system developed by this team, which, unlike other systems does not place restrictions on how directed connectors should be drawn.

Once a computer has identified the shape groups and their classification, it is possible to construct a conceptual model of the diagram. The grouping and recognition steps provide information about the components, but not relationships between them or constraints on them. To address this, the researchers investigated how relationships between shapes (via connectors) could be automatically detected to create a spatial map of the diagram. With such knowledge, advanced functions can be added, such as validation of meaning and structure based on a diagram’s form, backtracking in the grouping and recognition process to deal with unrecognized strokes, and added capabilities in sketching applications (e.g. intelligent editing, auto-correction or automatic shape completion).

Domain patterns are combinations of shapes that are likely to occur in diagrams. Past systems have hard-coded this information, but what if computers could progressively learn domain patterns? The researchers have investigated this by focussing on connected diagrams, specifically flow charts/process diagrams. To begin with, relationships were observed manually, but more recently they have been working on automating relationship detection and identifying frequently observed relationships. A feature set has been devised to represent the characteristics of these relationships. Dr Blagojevic’s ongoing research is working towards predicting unknown relationships in flowcharts with this feature set, using data-mining techniques. Together with the simultaneous grouping and recognition system, this work could result in an automated system for recognising diagram components and relationships, which is a step further automating the recognition of sketched diagrams.

Additional Info:

Dr Blagojevic's Massey University page and Google Scholar profile

Additional Info:

Ada Lovelace and Ada Lovelace Day