Smoother Signatures

July 20, 2012

In a previous post, we described how Square makes signatures appear smooth on Android devices. In the latest release of Square Card Reader, we've made signing on Android devices even smoother, more beautiful, and more responsive. The three major changes are an improved splining algorithm, variable stroke width rendering, and the addition of bitmap caching.

Splining

As you move your finger across the signature sheet, Android delivers a sequence of touch events to the Square client, each of which contains a single (x,y) coordinate. To create a signature image, the client needs to reconstruct the line segments between these sampled touch points. The process of calculating line segments to connect a sequence of discrete points is called spline interpolation.

The most straightforward spline interpolation strategy is to connect pairs of touch points with straight lines. This is the strategy previously employed by the Square client.

Even with enough touch points to approximate the curves of the signature, the linear interpolation technique has the effect of making shapes appear blocky and flattened. If you focus on the curve of the shape above, you will notice corners around the touch points, and a general flattening of what should be a convex J shape.

The problem is that the signer's finger did not move in straight lines from point to point when tracing out this shape. Rather, our touch points are sampled from a full curve that the signer's finger traced on the touchscreen. While we can't know the original shape between the sampled points Android gave us, straight lines are not the best guess.

A better interpolation of the signature shape can be obtained by fitting curves between the touch points instead of straight lines. Cubic Bezier curves are an ideal choice for the interpolation curve. Bezier control points let us precisely specify curved shapes, and there are well-known algorithms for efficiently drawing Beziers.

The Bezier drawing algorithm requires as input a set of control points which are used to generate the curve. However, we are not given the Bezier control points here. Instead, all we have are some sample points along the curve itself! Our spline interpolation thus boils down to calculating a set of control points that, when fed into the Bezier drawing algorithm, result in a curve that passes through the sampled touch points.

The mathematics behind interpolating smooth cubic curves is too involved to describe here. Interested readers should consult resources like these helpful notes from Kirby Baker's Mathematics of Computer Graphics course at UCLA for a deeper discussion.

While the difference is subtle, switching from linear to cubic spline interpolation gives us a noticeably smoother and rounder shape.

Variable Stroke Width

If you study a pen-and-paper signature, you will quickly notice that the widths of the strokes in the signature are not uniform. Instead, the stroke width fluctuates as the speed and pressure on the pen change. While Android provides an API for tracking touch pressure, we have not found the results to be sensitive or consistent enough for generating signatures. Keeping track of the stroke speed is easily accomplished, however. All we need to do is tag each touch point with the time it was sampled, and we can start calculating point-to-point velocities.

public class Point {
  private final float x;
  private final float y;
  private final long timestamp;
  // ...

  public float velocityFrom(Point start) {
    return distanceTo(start) / (this.time - start.time);
  }
}

As we draw each Bezier curve of the signature, we incrementally vary the stroke width up or down along the curve depending on the velocity between the curve's start and end point.

lastVelocity = initialVelocity;
lastWidth = intialStrokeWidth;

public void addPoint(Point newPoint) {
  points.add(newPoint);
  Point lastPoint = points.get(points.size() - 1);
  Bezier bezier = new Bezier(lastPoint, newPoint);

  float velocity = newPoint.velocityFrom(lastPoint);

  // A simple lowpass filter to mitigate velocity aberrations.
  velocity = VELOCITY_FILTER_WEIGHT * velocity
      + (1 - VELOCITY_FILTER_WEIGHT) * lastVelocity;

  // The new width is a function of the velocity. Higher velocities
  // correspond to thinner strokes.
  float newWidth = strokeWidth(velocity);

  // The Bezier's width starts out as last curve's final width, and
  // gradually changes to the stroke width just calculated. The new
  // width calculation is based on the velocity between the Bezier's
  // start and end points.
  addBezier(bezier, lastWidth, newWidth);

  lastVelocity = velocity;
  lastWidth = strokeWidth;
}

We hit a difficulty, however, when it comes time to actually draw the Bezier. The problem is that Android's canvas API has no method for drawing a Bezier with a stroke width that varies over the length of the curve. This means that we must draw the curve ourselves by plotting individual points with the desired widths.

/** Draws a variable-width Bezier curve. */
public void draw(Canvas canvas, Paint paint, float startWidth, float endWidth) {
  float originalWidth = paint.getStrokeWidth();
  float widthDelta = endWidth - startWidth;

  for (int i = 0; i < drawSteps; i++) {
    // Calculate the Bezier (x, y) coordinate for this step.
    float t = ((float) i) / drawSteps;
    float tt = t * t;
    float ttt = tt * t;
    float u = 1 - t;
    float uu = u * u;
    float uuu = uu * u;

    float x = uuu * startPoint.x;
    x += 3 * uu * t * control1.x;
    x += 3 * u * tt * control2.x;
    x += ttt * endPoint.x;

    float y = uuu * startPoint.y;
    y += 3 * uu * t * control1.y;
    y += 3 * u * tt * control2.y;
    y += ttt * endPoint.y;

    // Set the incremental stroke width and draw.
    paint.setStrokeWidth(startWidth + ttt * widthDelta);
    canvas.drawPoint(x, y, paint);
  }

  paint.setStrokeWidth(originalWidth);
}

Varying the stroke width in this way gives the signature a more realistic character.

Responsiveness

Another crucial ingredient for a pleasant signature experience is responsive input. With pen and paper, there is no latency between when the pen moves across the paper and the shape appears. While our lower bound on latency is limited by the touchscreen hardware, we should do our best to minimize the time between when a signer's finger traces a shape on the screen and when the shape appears.

One rendering strategy would be simply to paint all Bezier curves in the onDraw() method of our signature View.

@Override protected void onDraw(Canvas canvas) {
  for (Bezier curve : signature) {
    curve.draw(canvas, paint, curve.startWidth(), curve.endWidth());
  }
}

Recall that each Bezier curve's draw method will result in many calls to canvas.drawPoint(...). Redrawing each curve is ok for small signatures, but quickly becomes slow for signatures with many curves. Even if we are intelligent about invalidating specific regions of the signature view, drawing overlapping lines will still kill the responsiveness of our signature.

Instead of drawing every Bezier on each onDraw() call, we should paint each Bezier to an in-memory Bitmap when the curve is first added to the signature. Then, our onDraw() method can simply paint the bitmap without rerunning the Bezier drawing algorithm for every curve in the signature.

Bitmap bitmap = null;
Canvas bitmapCanvas = null;

private void addBezier(Bezier curve, float startWidth, float endWidth) {
  if (bitmap == null) {
    bitmap = Bitmap.createBitmap(getWidth(), getHeight(),
        Bitmap.Config.ARGB_8888);
    bitmapCanvas = new Canvas(bitmap);
  }
  curve.draw(bitmapCanvas, paint, startWidth, endWidth);
}

@Override protected void onDraw(Canvas canvas) {
  canvas.drawBitmap(bitmap, 0, 0, paint);
}

This technique keeps drawing responsive for a signature with any number of curves.

The Final Product

Putting it all together, we have cubic spline interpolation making our signature smooth, velocity-based stroke width variance giving our signature character, and bitmap caching making our drawing responsive. The result is a delightful experience and a beautiful signature.

Software Engineer

Comments

Get support help at squareup.com/support. We'll delete off-topic comments.