scikit-image/scikit-image — pull request #666 by jni (2013-07-24 15:04:59+00:00)
Title: Fix scaling (`ratio`) parameter in SLIC

Hey guys,

A little bit more fiddling with SLIC. The next thing on my plate for SLIC is to allow different voxel spacing along each axis. As I was coding that up, and with some help from @amueller, I noticed that the ratio parameter in this implementation was in fact *not* the same as in the original SLIC implementation, despite Andy's best efforts.

Let's assume for simplicity that there's one spatial dimension, `x`, and one color, `a`. The weighting between `x` and `a` in the k-means step is computed from the input parameter `C` (compactness) and the step, `S`. In the [original implementation](https://github.com/amueller/slic-python/blob/master/SLIC.cpp#L569), we have:

```python
dx = (x - x_0)**2
da = (a - a_0)**2
D = da + dx * (C/S)**2
```

Now, Andy was being clever in noticing that, rather than multiplying at every iteration, you can scale the `a` array at the start. However, what he slipped up with is that you *shouldn't* square the weight:

```python
# Andy's implementation
as = a * (S/C)**2
dx = (x - x_0)**2
das = (as - as_0)**2
# = (a * (S/C)**2 - a_0 * (S/C)**2)**2
# = (a - a_0)**2 * (S/C)**4
Ds = dx + das
# = da * (S/C)**4 + dx
# no linear relationship to original D
```

If we scale `a` by `(S/C)` instead of `(S/C)**2`, we get what Andy intended:

```python
das = (as - as_0)**2
# = (a * (S/C) - a_0 * (S/C))**2
# = (a - a_0)**2 * (S/C)**2
Ds = dx + das
# = dx + da * (S/C)**2
# = (S/C)**2 * (da + dx * (C/S)**2)
# = (S/C)**2 * D
# a constant multiplicative factor with the original distance.
```

This doesn't really change much for usage but I think it's useful being consistent with the reference implementation. Also, Andy reckons this scaling reduces the sensitivity of the parameter to image size.

As a heads up, another difference from the reference implementation is that the reference does some cleanup afterwards to ensure supervoxels are connected and meet a minimum size requirement. I don't think this is a high priority, since the Gaussian smoothing Andy introduced dramatically reduces the occurrence of disconnected supervoxels, but it's something that might come up in the future.

Finally, I would like to ask people: in the original implementation, `ratio` is actually called `compactness`, which I think is much more descriptive. Therefore, I would like to deprecate the `ratio` keyword in favour of `compactness`. There could be a period during which both are accepted, to avoid breaking the interface.