Chris Doble's Blog

Django, Celery, transactions, and you

When using Celery in a Django project, you need to be mindful of race conditions that can arise between database transactions and tasks. Celery’s user guide recommends that you manually commit transactions before sending tasks, but this is tedious and sometimes isn’t feasible (you can’t safely commit transactions from within a signal handler, for example).

This problem is solved by Bradley Ayers and I with django-celery-transactions. This package provides mechanisms to hold on to tasks until the current transaction is committed (at which point they are sent in the order that they were captured). If the transaction is rolled back—as would happen if a view raises an exception—the tasks are discarded.

See django-celery-transactions on GitHub for more information.

Using Wordnik’s Wordkit framework

I’ve recently been playing around with Wordnik’s API and iOS/Objective-C framework, Wordkit. My first impressions are largely positive: they both seem to be structured well and provide a great deal of functionality. The API’s documentation is beautiful, too!

I did run into a couple of problems getting the framework up and running though—linker and “unrecognized selector” errors (using commit b8c8854). Assuming you’ve added the framework to your XCode project and it’s listed in the “Link Binary With Libraries” build phase, the following steps should fix things up:

1. Link your against libsqlite3.dylib and SystemConfiguration.framework.
2. Add the -ObjC linker flag to your app (Build Settings > Linking > Other Linker Flags).

The second step is necessary because, without the -ObjC flag, the linker doesn’t include object files for categories, resulting in “unrecognized selector” errors. See here for more information.

Is my phone moving? Detecting motion with OpenCV.

In this post I detail a technique I’ve used to determine when a device is stationary using only its camera and OpenCV. The techinque makes extensive use of colour composition histograms; specifically, the differences between them. You can find the source of a simple demo app on GitHub.

Introduction

So, why would you use the camera and (arguably computationally intensive) computer vision algorithms when you have access to raw accelerometer data? I use the output of this technique to supplement accelerometer data and, using a sensor fusion algorithm, I am attempting to calculate my phone’s velocity. While the accelerometer has, so far, proved too inaccurate for this, the technique I’m about to discuss is able to reliably determine when the phone is stationary.

The technique makes use of a video stream from the camera, determining the similarity between successive frames by calculating the absolute difference between their histograms. If the frames are very similar, we say that the device is stationary. In the next two sections I cover the theory behind the technique, followed by the implementation in Objective-C.

The Theory

As mentioned in the introduction, histograms lie at the heart of this technique; their simplicity makes it both easy to implement and fast (compared to, say, phase correlation). In this context, a histogram simply acts as a summary of the colour composition of (a channel of) an image. The following is an example of a histogram:

And what about the difference between two of these histograms? That provides us with a measure of the similarity of the images’ colour compositions. If the two images were exactly the same, for example, the difference would be 0. If we’re comparing images of differing dimensions, it’s also important that we normalise the histograms; that is, divide by the total number of pixels in the image so we’re working with percentages. The following is an example of the difference between two histograms:

Without some logic behind them, histograms aren’t a great metric for image similarity—two images may be composed of pixels of exactly the same colour but still look vastly different. How do we overcome this problem? One way is to split the images into a grid and compare the histograms of corresponding cells. That way, we’re comparing the colour compositions of matching areas of the images: the location of pixels is taken into consideration. The following is an example of such a histogram:

The Code

I use OpenCV to calculate and compare histograms. It doesn’t work with iOS out of the box, but, thankfully, Ievgen Khvedchenia has put together pre-compiled binaries for us! You can find them on his website. While it is powerful, I’ve found OpenCV’s documentation lacking and the libraries themselves are quite big—141MB in total! Luckily we only need to link against 3 of 15 .a files (20MB), but that still makes us exceed the app store’s “over the air” download threshold.

My implementation of this technique (which can be found on GitHub) spans two classes: CDMotionObserver and CDMotionObserverFrame. The former acts as the interface to the technique, working with the device’s camera and providing both calibration and delegation functionality. The latter actually works with video data and histograms thereof, effectively making it the “core”.

Let’s jump straight in and look at the workhorse of CDMotionObserverFrame, differenceFrom:. This method calculates the difference between two frames and is the implementation of the “histogram difference” approach discussed in the previous section. It simply iterates over each cell in the two frames, sums the difference between their histograms, and returns the greatest of these sums; the greater the returned value, the more the images differ.

- (double)differenceFrom:(CDMotionObserverFrame *)frame {
  if (frame == nil) {
    [NSException raise:NSInvalidArgumentException format:@"frame is nil."];
  }

  // The maximum calculated difference.
  double maximum = DBL_MIN;

  for (int i = 0; i < pow(CD_MOTION_OBSERVER_FRAME_GRID_SIZE, 2); i++) {
    // Calculate the absolute difference between the histograms of
    // the two images: the similarity of their colour compositions.
    cv::MatND difference;
    cv::absdiff(*[self histogramAtIndex:i], *[frame histogramAtIndex:i],
                difference);

    maximum = MAX(maximum, cv::sum(difference)[0]);
  }

  return maximum;
}

- (cv::MatND *)histogramAtIndex:(int)index {
  if (index < 0 || index >= pow(CD_MOTION_OBSERVER_FRAME_GRID_SIZE, 2)) {
    [NSException raise:NSInvalidArgumentException
        format:@"index must be between 0 and "
                "(CD_MOTION_OBSERVER_FRAME_GRID_SIZE ^ 2) - 1 inclusive."];
  }

  cv::MatND *histogram = &_histograms[index].matrix;

  // Do we need to create the histogram (lazy loading)?
  if (histogram->size().width == 0) {
    cv::Rect rect = [self rectForIndex:index];
    cv::Mat frame(_frame->matrix, rect);

    // Create a histogram for the frame's grayscale channel with a bin for each
    // of the 256 possible shades and store the result in the histogram pointer.
    int bins[] = {256};
    int channels[] = {0};
    float range[] = {0, 256};
    const float *ranges[] = {range};
    cv::calcHist(&frame, 1, channels, cv::Mat(), *histogram, 1, bins, ranges);
  }

  return histogram;
}

It’s all well and good to calculate some “difference” value for successive frames in the video stream, but what does this value actually mean? At what point can we say that the device is stationary? This is where calibration comes in. If we hold the phone still for a short amount of time, we can calculate the average difference between frames: a “stationary threshold”. If the difference between successive frames is less than or equal to this threshold, we say that the device is stationary.

The following is a snippet from CDMotionObserver’s frame processing code, specifically, the calibration logic.

// difference is the difference between the previous and current frames.
self.calibrationMean = self.calibrationMean + difference;
self.calibrationRemaining = self.calibrationRemaining - 1;

// We're done! Mark the instance as calibrated, update values
// accordingly and stop the session (it'll start when start is called).
if (self.calibrationRemaining == 0) {
  self.calibrationMean = self.calibrationMean / CD_MOTION_OBSERVER_CALIBRATION_FRAMES;
  self.calibrated = YES;
  self.lastFrame = nil;
  [self.captureSession stopRunning];

  // Notify the delegate that calibration is complete.
  SEL selector = @selector(motionObserverDidFinishCalibration:);
  [self.delegate performSelectorOnMainThread:selector
                                  withObject:self
                               waitUntilDone:NO];

  return;
}

After calibrating, we can call start and the delegate will be notified whenever it appears that the device is stationary.

Discussion

I’ve found this technique to be quite accurate; it works well as a secondary source of data, complementing raw accelerometer readings. There are, however, a couple of improvements that could be made if the technique was to be used in production.

• The device’s accelerometer/gyroscope should be monitored during calibration to ensure that it is kept relatively still. The routine should fail if the device moves too much.
• The dependency on OpenCV could be removed by re-implementing the histogram functionality. This would greatly reduce the compiled .app’s size.

Be sure to leave a comment or make a pull request on GitHub if you make any improvements!

Low-power location updates

In this post I detail a technique I’ve used to generate accurate location updates in iOS using as little power as possible. A use case for this technique is to allow an app to track the device’s location while running in the background. You can find a simple demo app here.

Introduction

As of iOS 4.0, CLLocationManager provides methods to track the device’s location at a specific accuracy level (startUpdatingLocation), or when its location changes significantly (startMonitoringSignificantLocationChanges). The former chews through battery, and the latter doesn’t generate particularly accurate updates. So what do we do? We want accurate updates, but we don’t want the device to die before we can use them. The technique that I’m about to detail uses significant location updates to prompt accurate location updates—we save power by turning the GPS off when we don’t need it, but we still receive frequent, accurate updates.

This technique won’t always be an appropriate solution. With its dependence on significant location updates, there can be large distance/time gaps between successive updates (see this excellent write up about significant location updates for more information). Simply put, this approach isn’t for you if your app is to be used over small distances (e.g. walking); just use the GPS.

The Technique

At a high level, the technique is quite simple:

1. Start monitoring significant location updates.
2. When we receive a significant location update, turn the GPS on.
3. When we receive an accurate location update, notify the delegate and turn the GPS off.
4. Go to 2.

I’ve created a class, CDLocationManager, that implements this technique. You can find a simple demo app here. Let’s look at the core of the class: the update processing logic.

- (void)locationManager:(CLLocationManager *)manager
    didUpdateToLocation:(CLLocation *)newLocation
           fromLocation:(CLLocation *)oldLocation {
  // Reject old updates unless this is the first update. If this is the first
  // update, it doesn't matter if it's old because we'll turn the GPS on anyway.
  if (ABS([newLocation.timestamp timeIntervalSinceNow]) >
      CD_LOCATION_MANAGER_LIFETIME && !self.isFirstUpdate) {
    return;
  }

  self.firstUpdate = NO;

  if (self.isAccurateUpdate) {
    // Have we got an accurate location update or timed out?
    BOOL finished = NO;
    BOOL timedOut = ABS([self.accurateUpdateStarted timeIntervalSinceNow]) >=
        CD_LOCATION_MANAGER_TIMEOUT;

    // Is the location update accurate enough?
    if (newLocation.horizontalAccuracy <=
        CD_LOCATION_MANAGER_MINIMUM_ACCURACY) {
      finished = YES;
      [self.delegate locationManager:self didUpdateToLocation:newLocation];
    }

    if (finished || timedOut) {
      self.accurateUpdate = NO;
      self.accurateUpdateStarted = nil;
      [self.locationManager stopUpdatingLocation];
    }
  } else {
    // We got a significant location update, so fire up the GPS.
    self.accurateUpdate = YES;
    self.accurateUpdateStarted = [NSDate date];
    [self.locationManager startUpdatingLocation];
  }
}

This is the implementation of steps 2–4 above with the addition of: rejecting old location updates, rejecting inaccurate location updates, and timing out if we wait too long for an accurate update. Hopefully the comments will make the code self-explanatory.

Discussion

I’ve used this technique successfully in one of my own apps, with all of the processing being done in the background. Unfortunately, as I mentioned earlier, there can be a large distance/time between successive updates.

A slightly different approach would be to monitor a region around the device using CLLocationManager’s startMonitoringForRegion:desiredAccuracy:. When the device exits that region, determine its location, set up another region, and repeat. While I haven’t tried this, I suspect it will behave similarly but will have the added flexibility of variable region sizes. If anyone implements this, please let me know how it goes!