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 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
| ||||||||||||||||
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. |