Export (0) Print
Expand All
Add Support for Digital Ink to Your Windows Applications
Power to the Pen: The Pen is Mightier with GDI+ and the Tablet PC Real-Time Stylus
Expand Minimize

Reflowable Ink: Simple Reflow

 

Steve Dodge
Microsoft Corporation

January 2005

Applies to:
   Microsoft Tablet PC Platform SDK

Summary: This paper explains a technique that can be used with off-the-shelf components in the Microsoft Windows XP Tablet PC Edition Development Kit 1.7 to accomplish, for Ink, the word-wrapping behavior that word processors and standard text-based controls provide to ensure that text automatically wraps to fill available space. (18 printed pages)

Click here to download the code sample for this article.


Contents

Introduction
The Basics
Putting It All Together
Conclusion

This article is the first in a series that will explore adding reflow capability to Ink. In this article I will explore the use of the InkDivider object to analyze an Ink object for the identification of paragraphs, lines, and words; calculate a new layout for the Ink, given available horizontal space; and render the Ink using this new layout.

Future articles will expand on this idea, exploring real-time reflow calculation, mechanisms for inserting writing space within a paragraph, Ink Reflow as a RealTimeStylus plug-in, a Reflow Edit control, and other topics.

Introduction

Since text was moved from hard paper into the realm of software with the advent of the word processor, users of computer applications have come to expect that text will automatically flow to the next Line when there is not adequate space for text on a Line, and that this reflow will be recalculated when the window's size is changed so text remains visible to the viewer.

In 2002, Microsoft introduced through the Tablet PC Platform a fundamental kind of information to the software world: Ink. The intended purpose of Ink varies more widely than text (drawings, tables, notes), but it is harder to make reflow behavior happen automatically in Ink-enabled applications.

There are scenarios where reflow would be useful, however, including instant messaging and handwritten prose. Ink Reflow is relevant anywhere that handwriting is to be perceived as text by the user and application.

For example, consider a hypothetical Ink-based instant messenger. One user might write on a window that looks like the one shown in Figure 1:

Figure 1. Hypothetical instant message as seen by the sender

The recipient user might have a window with a different size or shape, however, as in Figure 2:

Figure 2. Hypothetical instant message as seen by the recipient

Clearly, this is less than desirable. Using techniques described in this article, software can apply Reflow to the Ink to achieve a much friendlier presentation of the instant message, as in Figure 3:

Figure 3. Fully visible instant message as seen by the sender after Ink Reflow

The Basics

First we'll assemble the concepts we need to accomplish Ink Reflow.

The basic idea to reflowing ink is the same as that for text:

  • Analyze the ink to identify paragraphs and constituent words.
  • Walk through the words in each paragraph, positioning them left to right, and wrapping to the next Line when needed.

Analyzing the Ink

It's easy for text: paragraphs are separated with carriage return (and linefeed) characters, and words are separated with spaces. It's not so easy for Ink which appears as a flat collection of Strokes (which are themselves collections of connected coordinate pairs). Fortunately, the InkDivider object (first introduced in the Microsoft Windows XP Tablet PC SDK version 1.5) is designed to provide exactly the analysis we need.

Feeding the Divider

InkDivider needs the following key bits of information to do its job:

  • Strokes: The Ink that will be analyzed.
  • RecognizerContext: Allows InkDivider to include a language model while analyzing Ink.
  • LineHeight: Guideline to help InkDivider determine where Lines break.

The following code shows how InkDivider is initialized.

Divider inkDivider = new Divider();
inkDivider.RecognizerContext = recognizerContext;
inkDivider.LineHeight = lineHeight;
inkDivider.Strokes = theStrokes;

Note   InkDivider and RecognizerContext internally use unmanaged resources that are not released by the Microsoft .NET garbage collector, so it's important to remember to Dispose of the Inkdivider object when it is no longer needed.

Calling All Words and Paragraphs

The Divide method of InkDivider is used to identify and retrieve paragraphs and words.

DivisionResult divisionResult = inkDivider.Divide();

The DivisionResult object is the entry point into the analysis results in InkDivider. The ResultByType method is used to retrieve analysis results.

DivisionUnits paragraphs = divisionResult.ResultByType(InkDivisionType.Paragraph);
DivisionUnits words = divisionResult.ResultByType(InkDivisionType.Segment);
DivisionUnits drawings = divisionResult.ResultByType(InkDivisionType.Drawing);

Each DivisionUnits object is a collection of DivisionUnit objects, each of which in turn contains a Strokes object corresponding to the Ink Strokes that make up the DivisionUnit. So the words collection ultimately maps to a Strokes object for each word, from which we'll use the BoundingBox to lay out each word. We'll use the paragraphs collection to keep the words together in each paragraph. The drawings collection tells us where the user has drawn something that is not text.

The next task is to connect the words and paragraphs collections and figure out which words are in which paragraph. To do this we'll build a Hashtable to create an association between words and paragraphs.

// Walk through the division results and reconstruct a bottoms-up tree of ink.
Hashtable wordsToParagraphs = new Hashtable(words.Count); 

// Walk once through the words.
foreach (DivisionUnit word in words)
{
   // Look for this word in each paragraph.
   foreach (DivisionUnit paragraph in paragraphs)
   {
      // If the paragraph contains the first stroke of this word, we've found it.
      if (paragraph.Strokes.Contains(word.Strokes[0]))
      {
         // Add the pair to the hash table and go to the next word.
         wordsToParagraphs.Add(word, paragraph);
         break;
      }
   }
}

This algorithm creates a tree from the branches down to the trunk. The algorithm assumes that there will be more words than paragraphs, and thus minimizes the number of iterations through the words collection.

Analysis Performance Considerations

Once InkDivider is initialized, it is capable of performing its analysis in the background while Ink is being collected. By simply adding new Strokes to the InkDivider Strokes collection as they are collected, InkDivider will automatically determine what parts of the Ink need to be re-analyzed. When the Divide method is called later, InkDivider will be ready with the results more quickly.

This incremental analysis is beyond the scope of this article, but will be an important part of future articles that cover real-time reflow.

Laying It All Out

The next step is straightforward. Words in a given paragraph need to be laid out in order from left to right. When there is not enough horizontal space for a given word, the heuristic needs to begin again, at the left but on a new Line.

// Track the current location as we lay out the ink
Point location = new Point(WordPadding, LineHeight);

We utilize the location variable to keep track of the position for the next word as we proceed with the layout. The wordPadding variable contains a value that corresponds to the width of a space. The lineHeight variable contains the same value passed earlier to the InkDivider LineHeight property.

Next we proceed through another N^2 algorithm, this time walking up the tree from paragraphs to words. We arrange words in the paragraph, skipping words that are in other paragraphs.

// Rearrange the paragraphs.
foreach (DivisionUnit paragraph in paragraphs)
{            
   // Rearrange the words in this paragraph.
   foreach (DivisionUnit word in words)
   {
      // Skip words that aren't in the current paragraph.
      if (wordsToParagraphs[word] != paragraph)
      {
         continue;
      }

We'll need the BoundingBox for the current word in order to figure out where to move it.

      Rectangle wordRectangle = word.Strokes.GetBoundingBox();

Here's where we decide whether there is enough space for the word on the remainder of the current Line. If there's not enough space, we reset and update the location variable.

      // Determine whether to wrap to the next line.
      if (location.X > WordPadding && 
         (location.X + wordRectangle.Width + WordPadding) > ReflowRectangle.Width)
      {
         location.X = WordPadding;
         location.Y += LineHeight;
      }

When people write on a Line, they don't always write exactly on the Line. Also, some of the letters descend below the baseline (like "g" and "y"). To maintain the vertical position of a word relative to the rest of the Line, we can calculate a baseline offset. Rectangle.Bottom gives us the vertical position of the bottom of the rectangle, as opposed to its height. The modulus of the bottom of the rectangle and the lineHeight will give us the distance between the bottom of the rectangle and the nearest baseline.

      // Maintain the baseline offset for this word.
      int baselineOffset = wordRectangle.Bottom % lineHeight;

While a small value for baselineOffset corresponds to a word that was written slightly below the baseline; a large value corresponds to a word that was written slightly above the baseline, where the offset will actually be nearly the value of lineHeight.

      // Determine whether this word is above or below the baseline.
      if (baselineOffset > (lineHeight - baselineOffset))
      {
         baselineOffset -= lineHeight;
      }

Next we move the word, taking the baseline offset into account. The Strokes.Move method requires us to pass the relative distance to move the strokes.

      // Position the word relative to current position.
      word.Strokes.Move(
         location.X - wordRectangle.Left, 
         location.Y - wordRectangle.Bottom + baselineOffset);

Finally, a little housekeeping.

      // Update the horizontal position for the next word.
      wordRectangle = word.Strokes.GetBoundingBox();
      location.X += wordRectangle.Width + WordPadding;
   }

Having exhausted the list of words, we'll update location for the next paragraph and proceed through the list of words again.

   // Reset the horizontal position, and add a blank line between paragraphs.
   location.X = WordPadding;
   location.Y += 2 * LineHeight;
}

Special Considerations

The heuristic described in the previous section is powerful yet simple, and does not address many special cases that occur in real-world user handwriting. Here are some thoughts on how to handle some of these special cases. The sample code provided with this article does not address these considerations.

Drawings

A simplistic interpretation of the InkDivider heuristic for parsing drawings might be that Divider recognizes drawings as groups of Strokes whose BoundingBox height exceeds a multiple of lineHeight greater than 3 or 4. In such a case, InkDivider will categorize these groups of Strokes as drawings rather than words or paragraphs.

If the user-input scenario for an application includes drawings, it is necessary to decide how to include drawings in the reflow layout. One implementation might be to "lock" drawings in place and flow words around them. Another might be to align drawings with the nearest margin and flow words between the drawing and the opposite margin. Other implementations can easily be inspired from the reflow options available for text around pictures in your favorite word processing or desktop publishing software.

The sample code provided with this article does not implement a solution for reflow around drawings. It effectively locks the drawings in place by simply not moving them during layout. It also colors drawings red to make them easily identifiable.

Depending on their height, drawings can sometimes be confused with tall words. This leads us into a discussion of lineHeight.

LineHeight

The layout heuristic discussed in the previous section makes a potentially flawed assumption: it assumes that all of the handwriting is the same height. Words that are taller than a single Line are bottom-aligned according to the code that maintains the "baseline offset," but this code assumes that a word is approximately as tall as a Line. When this is not the case, the top of the word overlaps the previous Line, with somewhat unexpected results.

The solution is straightforward: calculate the maximum wordHeight for an entire Line prior to moving any of the words, and then adjust the baseline (location.Y, for example) down by a multiple of lineHeight (according to the maximum wordHeight for the Line).

The algorithm provided in the sample code accompanying this article does not include a solution to this case. Instead, words whose BoundingBox height exceeds 1.5*lineHeight are colored blue to help make them visible.

Maintaining the Baseline

The heuristic used in the previous section to determine the location for the baseline takes a shortcut: It simply maintains the relative position of what the user originally wrote. An alternative approach would be to use the RecognitionString on the word, split the Strokes for the word to locate the descender Strokes (or sub-Strokes), then analyze those Strokes to locate the true baseline for what the user wrote. This is a complex analysis operation, however, and RecognitionString corresponds to the top recognition alternate, which may be incorrect and lead to detecting the wrong letter as a descender, which in turn could throw off the baseline calculation.

Reliability

The layout heuristic discussed earlier will permanently change the position of the Ink, and repeated analysis using this technique with the same Ink can lead to errors in the layout (due to the parser in Divider repeatedly re-analyzing the Ink). Hence, this technique should only be used once on a given set of Strokes.

Repeated reflow requires more careful tracking of changes to the Ink both automatic in nature (for example, the reflow heuristic described in the previous section) and manual in nature (for example, selection-based manipulation by the user, using the InkOverlay editing modes). Such tracking is beyond the scope of this introductory article. Future articles will explore this aspect in more detail.

Tuning

Ink is given a margin on the left and right of width wordPadding. This works well for the demo, but you may want to modify the algorithm to use a smaller margin value, or modify the packaging to allow client code to separately specify margin from white space size.

Languages, Words, Characters, and Segments

This article uses InkDivisionType.Segment to divide the Ink into words. When a language recognizer is used, InkDivider relies on the recognizer to provide a meaningful segmentation of the Ink.

Language recognizers come in multiple varieties. Most are "word" recognizers, but some are "character" recognizers. Such character recognizers would result in each individual character treated as a separate "word," resulting in uniform space between letters and words, and reflow mid-word. When selecting a recognizer to use with the algorithm, be sure to consider whether the recognizer is word-based or character-based. There is no entry in RecognizerCapabilities that indicates this behavior, so an easy way to find out whether a given recognizer is word-based is to try it with the InkReflow class and see where the reflow happens: per-character or per-word.

Putting It All Together

Now we'll assemble the pieces to make the Ink flow.

Building a Reflow Engine

To use the reflow algorithm, we package it in the InkReflow utility class. The public members of this class are described in figure 4.

Figure 4. InkReflow utility class

Using the InkReflow class

The InkReflow class is designed to be simple to use. Here are four easy steps:

1. Instantiate the object

Initialize the InkReflow class by using its constructor.

theInkReflow = new InkReflow(inkLineHeight, inkWordPadding, theInkOverlay.Ink.Strokes, theRecognizerContext);

2. Maintain the Strokes

If the user is actively laying down Ink in your application (as in the demonstration application provided with this article), use code like this in the handler for an InkOverlay Stroke event.

theInkReflow.Strokes.Add(e.Stroke);

If the Ink is coming from a file or stream (for example, from a network as in the hypothetical instant message), use code like this just prior to display.

theInkReflow.Strokes.Add(theInk.Strokes);

3. Set the Reflow Rectangle

The ReflowRectangle is assumed to be in Ink coordinates. The following code uses Point objects from an array previously passed through the InkRenderer PixelToInkSpace conversion.

theInkReflow.ReflowRectangle = new Rectangle(points[0], new Size(points[1]));

4. Generate the Layout

Call the Reflow method to apply the layout heuristic to the Strokes.

theInkReflow.Reflow();

Public methods and properties
Dispose
public void Dispose (  )

Disposes of unmanaged resources that are used internally by the InkReflow class (like InkDivider).

InkReflow

public InkReflow ( System.Int32 lineHeight , System.Int32 wordPadding , Microsoft.Ink.Strokes strokes , Microsoft.Ink.RecognizerContext recognizerContext )

Initializes a new instance of the InkReflow class. The passed-in parameters are used to initialize the private members so that the Reflow method can respond as quickly as possible when needed.

lineHeight: The amount of space assumed that each Line requires. This should roughly correspond to the height of the user's handwriting. Units are himetric.

wordPadding: The amount of space to be applied between words during layout. Units are himetric.

strokes: Strokes to be included in Reflow analysis and layout.

recognizerContext: Used for language-based analysis of Ink.

Reflow

public void Reflow (  )

Calculates and applies a new layout to the Ink. This function encapsulates the reflow heuristic described earlier.

ReflowRectangle

public System.Drawing.Rectangle ReflowRectangle [  get,  set ]

Gets or sets the rectangle in which Ink will reflow. Units are himetric.

Strokes

public Microsoft.Ink.Strokes Strokes [  get  ]

This property gets a reference to the Strokes that will be reflowed. The property is a simple wrapper for the Strokes property on the member instance of the Divider class.

The internal parser in Divider is designed for incremental updates:

  • If the ink is ready to be reflowed at the time the InkReflow class is initialized, pass a reference to the Ink in the InkReflow constructor.
  • If the Ink is being collected in real-time, use the Strokes property as a means of adding each Stroke as it is collected. The ReflowDemoForm class (discussed in the following "Demonstrating Reflow" section) does this in the Stroke event of InkOverlay, and the result is that the Reflow command executes very quickly.
  • Otherwise, use the Strokes method to add the Strokes to InkReflow just before calling the Reflow method.

Private Member Variables

divider: An instance of InkDivider used to analyze the Ink. By maintaining a single Divider instance throughout the lifetime of the InkReflow class, the responsiveness of the Reflow method on subsequent layout operations is dramatically improved.

lineHeight: The amount of space assumed that each Line requires. This value is provided during instantiation through the constructor.

wordPadding: The amount of space to be applied between words during layout. This value is provided during instantiation through the constructor.

reflowRectangle: The rectangle in which Ink will reflow. This value is provided through the public ReflowRectangle property.

Demonstrating Reflow

The sample code provided with this article includes the InkReflow utility class, as well as a demonstration User Interface (UI) that provides a surface for laying down Ink, and menu commands for refreshing the layout of the Ink on the page.

Figure 5. ReflowDemoForm class

The ReflowDemoForm class is a straightforward form, containing a menu bar with a few useful commands and an InkOverlay attached to the form's surface. Lines are drawn on the form when it is painted, corresponding to the lineHeight that is provided to InkDivider for parsing.

To use the demo application:

  • Run the application.
  • Write on the Lines
  • Tap the Reflow menu command to trigger layout of the Ink.
  • Resize the window (narrower or wider).
  • Tap the Reflow menu command again.

To experiment further:

  • Use the Clear menu-command to erase the Ink on the form so that you can start over.

I'll summarize the key utilities and functionality later. See the demo code for the full details.

Member Variables

lineHeight, wordPadding

These variables contain pixel equivalents for their namesakes in the InkReflow class. The values in the sample are hard-coded, but it is straightforward to expose the UI to manipulate these values or make them otherwise user-specific.

Note that if you extend the sample to allow the user to modify the lineHeight value, the InkReflow instance will need to be recreated when the lineHeight value changes (or you will need to extend the InkReflow class itself to better support this). This is because its internal InkDivider instance does not allow its lineHeight value to be changed after Strokes have been assigned to the Divider.

theInkOverlay

This member variable holds the instance of InkOverlay that is attached to the form.

theInkReflow

This member variable holds the instance of InkReflow that is used to recalculate the layout of the Ink.

theInkRenderer and theRecognizerContext

The remaining Tablet PC Platform SDK objects are maintained as member variables because they wrap unmanaged objects and require Dispose() to be called. These objects' lifetimes are managed with that of the form itself to reduce the amount of CoCreateInstance happening behind the scenes.

Utility Routines

CalculateWritingMetrics

This routine uses the InkRenderer PixelToInkSpace method to convert lineHeight and wordPadding into himetric so that InkReflow can be initialized correctly.

RefreshReflowRectangle

This routine uses the InKRenderer PixelToInkSpace method to convert the current client rectangle of the form into himetric so that the ReflowRectangle property in InkReflow can be initialized correctly. The demo application uses the client rectangle of the form to govern the reflow space. This is done out of convenience and simplicity for the demo itself.

Event Handlers

Menu Item Handlers

Clear—The Clear menu-item simply clears the inking surface, and allows the user to lay down new Ink.

Reflow—the Reflow menu-item simply calls the InkReflow.Reflow() method.

Form_Paint

The form's Paint handler renders Lines as a writing guide.

InkOverlay_Stroke

This handler adds each new Stroke as it is collected to the InkReflow Stroke property (which passes it through to InkDivider). By doing this for each Stroke, InkDivider is able to parse the Ink incrementally, and have its internal parse structure in place by the time Reflow is requested.

Extending the Sample

One of the first extensions you may wish to make will be to enable the InkOverlay selection and editing functionality to allow the user to erase Strokes and rearrange words. This is a straightforward extension to the sample, as it simply requires adding UI to control the value of InkOverlay.EditingMode. There are a few additional considerations that may not be as apparent, however.

Eraser and Lasso Strokes Trigger the InkOverlay Stroke Event

As already discussed, the sample code adds each new Stroke to the InkDivider collection during the handler for the InkOverlay.Stroke event.

While erasing Strokes or lassoing, moving, or resizing a selection, InkOverlay internally collects and analyzes a Stroke to do its work, which results in the Stroke event being raised when the tablet pen is lifted at the end of the operation. The Stroke reference passed through to the event handler is then internally deleted, and this vaporized Stroke can be very confusing to InkDivider.

To account for this, just ensure the InkOverlay.EditingMode is InkOverlayEditingMode.Ink prior to passing the Stroke through to the InkReflow class.

Keep the Strokes Updated While Erasing and Moving/Resizing

While erasing, Strokes are deleted. InkDivider needs to be notified of the deleted Strokes. Be sure to sink the Ink.InkDeleted event and remove the deleted Strokes from the InkReflow Strokes property (you'll have to search for them by their Stroke.ID).

Similarly, while moving or resizing selected Strokes, sink the InkOverlay.SelectionMoved and SelectionResized events, and update the InkReflow.Strokes property. In this case, you'll need to invalidate the Strokes by first removing them from InkReflow.Strokes and then re-adding them.

PointErase

The InkOverlay PointErase mode introduces the greatest complexity, as it splits Strokes as the eraser passes over them. The best way to detect changes while erasing points is to sink Ink.InkAdded and Ink.InkDeleted events and update InkReflow.Strokes, as discussed earlier.

Conclusion

Thanks to analysis tools that are built into InkDivider, it is possible to duplicate in Ink the word-wrapping behavior with which we are familiar in text. This article shows how to use InkDivider to analyze Ink, extract paragraphs and words, create a mapping between words and paragraphs, and use that mapping to determine how words and paragraphs should be laid out to best use the space available.

Show:
© 2014 Microsoft