Xelular sets
A new framework for modelling deformable objects

A network of mortar-channels branches:


So should a model of it.


So does the white fur on a giraffe:


So should a model of it.

So does a river network in a satellite photo, or a pattern of arteries or cell walls, or the contrast-detected edges in an image.

So should a model of any of these.

The shape of things

Numerical 'objects' with shapes are most often modelled as a lot of moving points and 'finite elements' between them: straight links, cubic curves, NURBS, triangles,….

The way they join up is defined before they start to move. 
The smarter the elements, the more complex their connections,
and the harder it is to rearrange their topology. 

A lot of physical structures (arteries, soap films, cracks, domain boundaries,…) change connections as they grow and shrink.

So should virtual objects (active contours or 'snakes', and 3D analogues) that self-adjust to fit images.  These are mainly loops,
     
like this one from Sekhar et al, which nicely fits itself to the wall of one cell… in an image with many cells.  (It is a bit too rounded at the corners, because snakes resist cornering: this spoils the fit where three boundaries meet.)
Topology Adaptive Snakes divide and merge, but they never branch, let alone change branch topology from to , as an adaptive network must when topology is not known in advance.

A shape may be mathematically a set of points, and change by changing which it includes, but mathematicians' curved sets are infinite: unlistable on a computer.  They can be finitely specified by an implicit equation, like using
f (x, y) = x2 + y2 - r2 = 0
rather than give (x(
s), y(s)) = (cos(s), sin(s)) with a continuous s analogous to the index i above.  This leads to the powerful technique of level sets, replacing f (x,y) by functions created on the fly.  These are topologically more flexible, with for instance blob outlines merging naturally, but unlike parametrised curves (where branching is merely difficult), they can never stably handle triple branches at all.  If the area left of is negative, both upper right and lower right must be positive for the to be level-0 boundaries with it: but then, what gives the part?
Similarly, level sets work well on minimal surfaces, but only as long as these don't include the triple curves where bubbles meet. 

We prefer a scheme with explicit finite sets, but these are not sets of moving points: they are changing sets, like the set of locations passed through by a moving surface. There is so much internal diffusion in a soap film or cell membrane that giving its points a persistent identity is ontologically and dynamically misleading.



Pages here and there

Home
Where I've been
Publications
Patents
Anarkik3D (external)
Nordic River (external)
Therataxis (external)
Xelular sets (1st look)
Tensegrities (1st look)
Freedom by degrees
Ultrasound hotspots
2×2
Walk to NIAS
Fiction
Sculpture
Joy of Ignorance
To keep the sets we work with finite, we tile space with 'xels', and allow at most one point per xel.
Unlike a cellular automaton with just a few allowed states per cell, a xel has floating-point coordinates
(x, y) or (x, y, z) for the point (if any) it holds.  Unlike a coupled map lattice, xels can be empty.
To avoid the multiple kinds of neighbour among square or cubical tiles, we use a honeycomb of xels in 2D and in 3D a tiling by truncated octahedra, centred on points of a body-centred cubic lattice. 

'Intrinsic' forces move points to compress sets to smooth curves, allowing triple junctions.  A point that moves in a xel persists, but one that moves into a neighbour may merge with its occupant. If points in neighbouring xels move to have a xel between them, that xel becomes occupied, to avoid fragmentation.  To grasp how they behave, it is better to interact with the applet below than to read about them.
Left-click anywhere in the box at right, and you make a mobile red dot.

Right-click anywhere, and you make a draggable yellow dot.

Try making curves with fixed ends,
crossings, and blobs with fixed points.

Drag the yellow ends of an
      
and connections change.

The "S" key starts and stops motion.
You can add points when it is stopped.
Reload the page to clear.

On most machines this Java version, created by Badal Yadav, shows the set movement at a convenient viewing speed.  CUDA code on 240 cores converges too fast to watch live.


'Extrinsic' forces can come from images, as in active contours, from pressure difference as in soap bubbles, and so on, for a wide range of applications.

We need no starting assumptions about the topology of the curve network; indeed for image analysis we do not start with curves, but with a 'blob' that shrinks to fit the data.  We do need, in images like the bricks and giraffe above, to puncture the blob at places distant from the target, to create holes that expand over the segments between the target structure.

Even when triple points are not an issue, xelular sets converge much more easily than snakes to a target with concavities, as in this example: they can move by a simple gradient of target intensity, rather than the more complicated Gradient Vector Field dynamic.  They do not stick where a curve gets stuck, as they are not yet curves: they are blobs, which contract inward to the cavity.  Bridging behaviour over gaps is also much better than for most snake variants.

This approach is computationally intensive, but very parallelism-friendly, and takes very effiicient advantage of the hundreds of cores in a graphics processing unit (GPU).  This will be particularly important in planned applications such as mapping arteries, modelling the folding of brains and leaves, and finding boundary surfaces.


This is a first step to a Web write-up of work by Tim Poston and Raghu Raghavan, with a lot of help from a lot of students:
Notably Vivek N, Badal Yadav, Rahul Suresh and Ajay Harish, though many others have added interesting work and insights [add list].
We are working on a bells-and-whistles version which will include theory, animated gifs of convergence, an account of the code in 2D and 3D, and a range of applications.       But for now, all that is still
pregnancy image, words 'under construction'