“Feelable” touchscreens revisited

Tactus have gotten quite a lot of attention recently after demonstrating their new touchscreen technology (pictured above; image source). Their “Tactile Layer” technology raises bubbles on the touchscreen, creating, essentially, physical objects on the touchscreen. I suppose I’ve taken quite an interest in this since it’s similar to something I wrote about 6 months ago: feelable touchscreens.

Here are two amazing and innovative technologies, each taking a different approach towards creating tactile sensations from a touchscreen. Senseg use small electric currents to stimulate the skin, creating edges and feelings of texture, while Tactus actually create something physical.

To the best of my understanding, Tactus’ technology allows bubbles (I’m reluctant to call them buttons; who knows what else interaction designers could do with this!) in pre-determined locations, configured during manufacture. Different configurations are possible, apparently, but from what I’ve read it seems that these are decided at manufacture. Whilst this allows some fundamental improvements to the touchscreen experience (e.g. providing a configuration for a keyboard), it lacks some flexibility as manufacture determines where bubbles can be used.

Senseg’s tech, however, is more flexible and appears to be truly dynamic; application developers can control the precise location where feelings can be experienced rather than this being decided during manufacture.

Having dabbled with Microsoft Surface over the past year I’m pleased to see that both of these technologies apparently scale well to larger displays. Interactive tabletops suffer from the same loss of tactile feedback that touchscreen mobile devices do although this is perhaps less apparent on a large scale device where widgets aren’t crammed into such a small space.

I don’t think it’s fair to ask which of these technologies is better, because they can’t fairly be compared. Although the flexibility of Senseg vs the physical tactility of Tactus is an interesting comparison, I feel that a better question is could these concepts be somehow combined? Imagine a touchscreen which offers complete configuration flexibility, a richer tactile experience like Senseg claim to offer (e.g. feeling texture, not just the presence of something) and the benefits of feeling something physical on the touchscreen. Now that would be awesome.

Multimodal Android Development Part 1

This post is the first of two which gives a brief introduction to creating multimodal interactions in Android applications. I’ll briefly cover some of the SDK features available to you as an Android developer which you can use to create richer interactions in your apps. Example code will be quite concise because I assume you have at least a basic knowledge of Android development. Feel free to leave any comments suggesting how I can better explain these concepts, or to let me know if I’ve made any mistakes or omissions.

What is “multimodal” interaction?

Multimodal interaction, put simply, is interaction involving more than one modality (e.g. multiple senses). For example, an application may provide a combination of visual and haptic (touch) feedback. These types of interaction design provide a number of benefits, for example allowing those with sensory impairment to interact using other senses, or allowing interaction in contexts where one sense may be otherwise occupied.

One of the most ubiquitous examples of a multimodal interaction is the way in which mobile phones combine visual, audible and haptic feedback to inform users of a new text, phone call, etc. This combination of modalities is particularly useful when your phone is, say, in your pocket. Obviously you can’t see the phone, but you will probably feel the phone vibrate or hear your ringtone as new notifications appear.

Haptic feedback in Android

Most handheld Android devices have some sort of rotation motor in them allowing simple haptic feedback. Although not common in tablets (largely due to size constraints), all modern Android phones will have tactile feedback available. You can control the phone vibrator through the Vibrator class. Note that in order to use this, your Manifest must request the following permission: android.permission.VIBRATE

/* Request the device's vibrator service. Remember to check
 * for null return value, in case this isn't available. */
Vibrator vibrator = (Vibrator) getSystemService(Context.VIBRATOR_SERVICE);

/* Two ways to control the vibrator:
 *  1. Turn on for a specific time
 *  2. Provide a vibration pattern */

/* 1. Vibrate for 200ms */
vibrator.vibrate(200);

/* 2. Vibrate for 200ms, pause for 100ms, vibrate for 300ms. */
long[] pattern = new long[] {0, 200, 100, 300};

/* Perform this pattern once only (repeat := -1). */
vibrator.vibrate(pattern, -1);

/* Vibrate for 200ms, followed by indefinite repeat of
 * 100ms pause followed by 300ms vibrate. Setting
 * repeat := 2 tells the vibrator to repeat at offset
 * 2 into the vibration pattern. */
vibrator.vibrate(pattern, 2);

 

Touchscreen gestures

Using touchscreen gestures to interact with applications can be fun, efficient and useful when users may be unable to select a particular action on the screen. For example, it can be difficult to select a button on-screen when running or walking. A touch gesture, however, is a lot easier and requires less precision from the user. The disadvantage with touch gestures is that if not used sparingly, there may be too much for the user to remember!
Creating a set of gestures for your application is simple: create a gesture library on an Android Virtual Device using the Gesture Builder application (available on the AVD by default) and add a GestureOverlayView to your activity layout. In your activity, you just have to load the gesture library from your resources and implement an OnGesturePerformedListener.

 

private GestureLibrary mLibrary;

public void onCreate(Bundle savedInstanceState) {
  ...
  /* 1. Load gesture library from the res/raw/gestures file */
  mLibrary = GestureLibraries.fromRawResource(this, R.raw.gestures);

  if (!mLibrary.load())
    /* Error: unable to load from resources! */
    ...

  /* 2. Find reference to the gesture overlay view */
  GestureOverlayView gov = (GestureOverlayView) findViewById(R.id.gestureOverlay);

  /* 3. Register callback for gesture input */
  gov.addOnGesturePerformedListener(this);
}

The callback method for gesture performance receives a Gesture as an argument. This can be used to obtain a list of predictions: which gestures in your library that Android thought the gesture was. With these predictions, you can use the prediction score (or contextual information) to determine which gesture the user was most likely to have performed. I find it useful to define a threshold for gesture acceptance, so that you can reject erroneous or inaccurate gestures. The best way to choose this threshold value is through trial and error: see what works for you and your gestures.

private static final double ACCEPTANCE_THRESHOLD = 10.0;

public void onGesturePerformed(GestureOverlayView overlay, Gesture gesture) {
  /* 1. Get list of gesture predictions */
  ArrayList predictions = mLibrary.recognize(gesture);

  if (predictions.size() > 0) {
    /* 2. Find highest scoring prediction */
    Prediction bestPrediction = predictions.get(0);

    for (int i = 1; i < predictions.size(); i++) {
      Prediction p = predictions.get(i);
      if (p.score > bestPrediction.score)
        bestPrediction = p;
    }

    /* 3. Decide if we'll accept this gesture */
    if (bestPrediction.score > ACCEPTANCE_THRESHOLD)
      gestureAccepted(bestPrediction.name);
  }
}

private void gestureAccepted(String gestureName) {
  /* Respond appropriately to the gesture name */
  ...
}

 

Saving map images in Android

Recently I’ve been working on a little Android project and wanted to save thumbnail images of a map within the application. This post is just sharing how to do exactly that. Nothing too complicated. 

public class MyMapActivity extends MapActivity {
    private MapView mapView;

    ...

    private Bitmap getMapImage() {
        /* Position map for output */
        MapController mc = mapView.getController();
        mc.setCenter(SOME_POINT);
        mc.setZoom(16);

        /* Capture drawing cache as bitmap */
        mapView.setDrawingCacheEnabled(true);
        Bitmap bmp = Bitmap.createBitmap(mapView.getDrawingCache());
        mapView.setDrawingCacheEnabled(false);

        return bmp;
    }

    private void saveMapImage() {
        String filename = "foo.png";
        File f = new File(getExternalFilesDir(null), filename);
        FileOutputStream out = new FileOutputStream(f);

        Bitmap bmp = getMapImage();

        bmp.compress(Bitmap.CompressFormat.PNG, 100, out);

        out.close();
    }
}

In the getMapImage method, we’re telling the map controller to move to a particular point (this may not matter to you, you may just want to take the image as it appears) and zooming in to show a sufficient level of detail. Then a Bitmap is created from the map view’s drawing cache. The saveMapImage method is just an example of how you may want to save an image to the application’s external file directory.

Virtual keyboards and "feelable" touchscreens

Senseg made a splash recently when they revealed their touchscreen technology which allows you to actually “feel” objects on-screen. By manipulating small electric charges, users can actually feel texture as they interact with a touchscreen. It’d be too easy to dismiss this as a gimmick, however I think this type of technology has the potential to make a positive impact on mobile devices.

Touchscreens are becoming increasingly ubiquitous in mobile devices, leading to the demise of the hardware keyboard. A glance at the list of all HTC phones in their current line-up shows only two of seventeen phones with a hardware keyboard. Samsung again only offer two phones with a hardware keyboard. While touchscreens offer the ability to eliminate hardware keyboards and other unsightly buttons for the sake of sleek aesthetics, they’ve so far failed (in my opinion) to provide a suitable replacement for hardware keys.

Yes, touchscreen keyboards are flexible and can offer a variety of layouts, however they still don’t give sufficient physical feedback to allow fast touch typing. One reason we’re better at typing on physical keyboards is because we “know” where our fingers are. The edges of keys (and the raised bumps often found on some keys) provide reference to other locations on the keyboard. Without looking at the keyboard, an experienced typist can type upwards of 100 words per minute. On a touchscreen, without proper physical feedback, you can expect just a small fraction of those speeds.

One argument against that could be the screen size, however tablets suffer from the same problems. The 26 character keys on my keyboard are of comparable size to the virtual keyboard on my 10-inch tablet. A popular approach to providing feedback for a mobile devices is to vibrate upon key press, however this provides little information other than “you’ve pressed a key”. An alternative approach to making touchscreen keyboards easier to use has been patented by IBM; a virtual keyboard that adjusts itself to how users type on-screen. Auto-correct is another feature which has risen to aid the use of virtual keyboards, yet addresses the symptoms rather than the cause.

Enter touchscreens you can “feel”. Actually being able to feel (something which resembles) the edges of keys on a virtual keyboard is likely to make it much easier to type on touchscreen devices. If technology becomes available which allows effective representation of edges (which Senseg claims their technology can), touchscreen devices will be able to offer what is, in my opinion, an improvement to virtual keyboards. I think this could be of particularly great benefit on tabletop computers which, by nature, allow a more natural typing position than handheld devices. Or perhaps this is all just wishful thinking because I go from 110WPM at my desktop to around 5WPM on my phone.

Left-recursion in Parsec

Lately I’ve been using the Parsec library for Haskell to write a parser and interpreter for a university assignment. Right-recursive grammars are trivial to parse with combinatorial parsers; tail recursion and backtracking make this simple. However, implementing a left-recursive grammar will often result in an infinite loop, as is the case in Parsec when using basic parsers. 

Parsec does support left-recursion however. Unsatisfied with the lack of good tutorials when I googled for advice, I decided to write this. Hopefully it helps someone. If I can make this better or easier to understand, please let me know!

Left recursive parsing can be achieved in Parsec using chainl1.

chainl1 :: Stream s m t => ParsecT s u m a -> ParsecT s u m (a -> a -> a) -> ParsecT s u m a

As an example of how to use chainl1, I’ll demonstrate its use in parsing basic integer addition and subtraction expressions.

First we’ll need an abstract syntax tree to represent an integer expression. This can represent a single integer constant, or an addition / subtraction operation which involves two integer expressions.

data IntExp = Const Int
            | Add IntExp IntExp
            | Sub IntExp IntExp

If addition and subtraction were to be right-associative, we’d parse the left operand as a constant, and attempt to parse the right operand as another integer expression. Upon failing, we’d backtrack and instead attempt to parse an integer constant. Reversing this approach to make the expressions left-associative would cause infinite recursion; we’d attempt to parse the left operand as an integer expression, which attempts to parse the left operand as an integer expression, which tries to… you get the point.

Instead we use chainl1 with two parsers; one to parse an integer constant, and another which parses a symbol and determines if the expression is an addition or subtraction.

parseIntExp :: Parser IntExp
parseIntExp =
  chainl1 parseConstant parseOperation

parseOperation :: Parser (IntExp -> IntExp -> IntExp)
parseOperation =
  do spaces
     symbol <- char '+' <|> char '-'
     spaces
     case symbol of
       '+' -> return Add
       '-' -> return Sub

parseConstant :: Parser IntExp
parseConstant =
  do xs <- many1 digit
     return $ Const (read xs :: Int)

Here, parseOperation returns either the Add or Sub tag of IntExp. Using GHCi, you can confirm the type of Add as:

Add :: IntExp -> IntExp -> IntExp

So, we have a parser which will parse a constant and a parser which will parse a symbol and determine what type of operation an expression is. In parseIntExp, chainl1 is the glue which brings these together. This is what allows left-associative parsing without infinitely recursing.

A complete code sample is available here. The abstract syntax tree has been created as an instance of the Show typeclass to print in a more readable format, which shows that the grammar is indeed left-associative.

ghci>  run parseIntExp "2 + 3 - 4"
((2+3)-4)

Finding maximum zero submatrix with C#

After spending most of this evening attempting to solve this problem, it only feels right that I share my solution.

Suppose you have a binary matrix and you wish to find the largest zero submatrix, i.e. the largest rectangle of zeroes in the matrix (see below, highlighted in orange).

1 1 0 0 0 1 0
1 0 0 0 0 1 1
1 1 0 1 0 1 1
1 1 1 0 1 1 0

The brute-force approach to this problem isn’t particularly efficient, with complexity O(n2m2). It involves looking at every position in the matrix, taking that position as an arbitrary point of the submatrix (e.g. the top-left point) and then testing all possible rectangles which originate at that point (e.g. all possible bottom-right points).

This algorithm finds the largest zero submatrix by looking at each position in turn and attempting to “grow” the submatrix up, to the left, and to the right. A dynamic programming approach is used and it keeps track of where the value 1 occurs. Array d contains the previous row where a 1 was found for each column. Array d1 contains the position of the left borders, and d2 contains the position of the right borders.

A complete code snippet for this program is available here. This has code to output the results and shows how to make use of the values calculated in this function.

static void MaxSubmatrix(int[,] matrix)
{
 int n = matrix.GetLength(0); // Number of rows
 int m = matrix.GetLength(1); // Number of columns

 int maxArea = -1, tempArea = -1;

 // Top-left corner (x1, y1); bottom-right corner (x2, y2)
 int x1 = 0, y1 = 0, x2 = 0, y2 = 0;

 // Maximum row containing a 1 in this column
 int[] d = new int[m];

 // Initialize array to -1
 for (int i = 0; i < m; i++)
 {
  d[i] = -1;
 }

 // Furthest left column for rectangle
 int[] d1 = new int[m];

 // Furthest right column for rectangle
 int[] d2 = new int[m];

 Stack stack = new Stack();

 // Work down from top row, searching for largest rectangle
 for (int i = 0; i < n; i++)
 {
  // 1. Determine previous row to contain a '1'
  for (int j = 0; j < m; j++)
  {
   if (matrix[i,j] == 1)
   {
    d[j] = i;
   }
  }

  stack.Clear();

  // 2. Determine the left border positions
  for (int j = 0; j < m; j++)
  {
   while (stack.Count > 0 && d[stack.Peek()] <= d[j])
   {
    stack.Pop();
   }

   // If stack is empty, use -1; i.e. all the way to the left
   d1[j] = (stack.Count == 0) ? -1 : stack.Peek();

   stack.Push(j);
  }

  stack.Clear();

  // 3. Determine the right border positions
  for (int j = m - 1; j >= 0; j--)
  {
   while (stack.Count > 0 && d[stack.Peek()] <= d[j])
   {
    stack.Pop();
   }

   d2[j] = (stack.Count == 0) ?  m : stack.Peek();

   stack.Push(j);
  }

  // 4. See if we've found a new maximum submatrix
  for (int j = 0; j < m; j++)
  {
   // (i - d[j]) := current row - last row in this column to contain a 1
   // (d2[j] - d1[j] - 1) := right border - left border - 1
   tempArea = (i - d[j]) * (d2[j] - d1[j] - 1);

   if (tempArea > maxArea)
   {
    maxArea = tempArea;

    // Top left
    x1 = d1[j] + 1;
    y1 = d[j] + 1;

    // Bottom right
    x2 = d2[j] - 1;
    y2 = i;
   }
  }
 }
}