menpo/menpo — pull request #425 by jabooth (2014-09-03 08:43:57+00:00)
Title: PiecewiseAffine cleaner, Cython varient demoted

PWA was written a long time ago in Menpo's development. We wanted something that was fast for the case in AAMs where source points remain the same as only target points change, but we couldn't compromise on the central API for transforms - that this sequence of operations should be completety supported by a transform:
```python
pwa = PiecewiseAffine(source, target)
pwa.apply(some_points)
pwa.apply(some_other_points)
pwa.set_target(some_new_target)
pwa.apply(some_points)
```
in AAM's the pattern looks like this:
```python
pwa = PiecewiseAffine(source, target)
pwa.apply(points)
pwa.set_target(some_new_target)
pwa.apply(points)
pwa.set_target(another_new_target)
pwa.apply(points)
...
```
if you are expecting this pattern you can go a lot faster by caching the calculation of the barycentric coordinates in the source domain once, and then re-using them.

Our solution 1 year ago was to add a C hashmap variant of PWA. This maintained a hashmap in C of all the points that had been provided to this transform. When a new point was brought in, it was checked against the hash. If we already had calculated the barycentric coordinates the cached value was returned - if not, we recalculated. This approach was nice for a number of reasons:

1. It solves the above problem.
2. If points are passed in a different order, or only a subset of the points have been previously calculated, you still got the cache benefit
3. The cache could grow in subsequent runs

but it has some negatives:

1. It's Cython, and not just an algorithm, but a data structure. We need to be able to save out PWA transforms, so we have to have special case code for Pickle, Copyable and HDF5able.
2. It's Cython - so it requires a compilation step at install.

As we start to think about extracting a clean 'core' toolset from Menpo having a Cython data structure in there is a little messy, so I started to wonder if it's avoidable.

As an alternative, I simplified the PWA package (pulling out much of the functionality as simple functions). I removed the unused `DiscreteAffinePWA`, and replaced it with a version of PWA that calculates target points just as the Cython PWA always has done, but has a pure Python approach for calculating barycentric coordinates. Of course, this version (currently called `PythonPWA`) is much slower than `CythonPWA` - the version of PWA we use in Menpo.

A simple subclass of `PythonPWA` is added called `CachedPWA` however, which simply caches the barycentric result for the last points used. This pure Python solution **outperforms** the Cython one.

This is not that surprising as `CachedPWA` only hits it's cache if the **exact** same points in the same order are provided to the function. This does not have the flexibilty of `CythonPWA`. However, for our use cases, this is not a problem, and we get a nice speedup with much cleaner code.

Note that this PR does not remove the CythonPWA, it just demotes it from being the default choice.

Demonstration and timings:
http://nbviewer.ipython.org/gist/jabooth/8b96a5849712a0222e07