Minimizing Spatial Cohesion with Inverted Space Filling Curves

I've been developing a clustering algorithm that happens to be sensitive to the order in which the items to be clustered present themselves. In general, the algorithm works best when items are present in an 'unbiased' order. As part of a general investigation into the algorithm, I've tried using the algorithm to cluster image pixels by colour. Because images generally have a high degree of spatial coherence (meaning in this case that adjacent pixels tend to be similar in colour), I wanted to find a way of sampling all of an image's pixels in an order that would minimize the bias that coherence creates.

Random benchmark

My first approach was to define a totally random order for the pixels in the image. To do this I shuffled the sequence 1, 2, ..., P where P is the number of pixels in the image and presented the pixels in that order. This works, but is unnecessarily inefficient – it requires the generation of P random numbers and storage for P integers.

Nevertheless, it provided a working prototype and I could then turn my attention to finding a better approach. I knew of several space-filling curves that have strong coherence properties, what I needed was something opposite.

Space Filling Curves

There are several well known space filling curves.

The Peano curve, discovered in 1890 by Guiseppe Peano was the first.
The Hilbert curve, published in 1891 by David Hilbert.
The Morton curve (a.k.a. Z curve), published in 1966 by G. M. Morton.
The Dragon Curve, first investigated by Heighway, Banks and Harter. It was popularized by Martin Gardener – I have fond memories of folding these from paper when I was a young boy.

In what follows, the reader is assumed to be familiar with the Morton Z-curve. Follow the links above for more information.

Of these curves, the Hilbert and Morton(Z) curves are perceived as being particularly useful in computer science due to their strong spatial coherence. I chose to concentrate on the Z-curve since it is computationally more efficient to generate. The index of a pixel in the ordering imposed by the Z-curve is simply the interleaving of its digits. That is to say, if x = x₁x₂x₃..x_n and y = y₁y₂y₃..y_n are the binary coordinates of a pixel then its index on the Z-curve is z = y₁x₁y₂x₂..y_nx_n.

In order to actually see the degree of spatial coherence that the Z-curve possesses, I wrote a small program that renders the curve at ever increasing resolutions, painting pixels at the start of the curve black, pixels at the end of the curve white, and smoothly graduating the shades in between. Images for the Z-curve are shown below.

First Order Z-Curve

Third Order Z-Curve

Sixth Order Z-Curve

These images demonstrate that pixels that are close in intensity (and therefore nearby in ordering) are nearby spatially too. As we already knew, the Z-curve has a high degree of spatial cohesion.

Curve Inversion

Recognizing that I needed something opposite to the properties of the Z-curve, I realized that I could use a strongly discontinuous transformation of the Z-curve's coordinate system to convert the curve into what I needed. Strong spatial cohesion in the first coordinate system would necessarily mean strong incohesion in the transformed system.

Reversal of the coordinate digits (binary or otherwise) provides just such a transform, and (beneficially) one that is cheap to compute. The intuition is simple:

Using a place-value system, right-hand digits correspond to small variations in value and left-hand digits large variations. If iterating along a Z-curve typically gives rise to only small changes in position it must change the LH digits of the coordinates infrequently. But since the curve is a bijection, the LH digits must be changing frequently. Swapping the LH and RH digits should therefore cause the Z-curve to make large movements often, resulting in stong incohesion. Since reversal of the coordinate digits is a bijection, the bijective nature of the ordering will be preserved.

None of this reasoning guarantees that the result will actually generate the desired result. So to test the hypothesis, I produced a corresponding set of images for this new curve, which I chose to nickname an A-curve:

First Order A-Curve

Third Order A-Curve

Sixth Order A-Curve

Note that, in one sense, this curve is a dual to the Z-curve, since the coordinate transform is a self-inverse; on which basis, this technique could be applied to any space filling curve.

Conclusion

The A-curve, an inverted Z-curve, has been demonstrated to provide the minimal spatial cohesion that benefits the clustering algorithm that gave rise to it. Whether other space filling curves, or other coordinate transforms provide lower levels of cohesion remains an open question.

Downloads

The source code that generated these images is in the public domain:

ZOrderRenderer.java

August 2009: I've updated this with some corresponding images of the Hilbert curve.

Hilbert Curve Images

Curiosity led me compare the results above with those from a Hilbert curve. Performance of the original clustering algorithm is indistinguishable using either the Z-curve or the Hilbert curve. Here are the corresponding images for the Hilbert curve. I decided to label its inversion the 'Uvyoreg curve'.

First Order Hilbert Curve

Third Order Hilbert Curve

Sixth Order Hilbert Curve

First Order Uvyoreg Curve

Third Order Uvyoreg Curve

Sixth Order Uvyoreg Curve