Friday, February 10, 2012

Extending convolution

I propose a new operator which is like convolution so I'll call it covolution for the sake of this discussion:
C = B * M where * is the covolution operator.

The base data B is a set of detail levels of single-bit tensors; grid trees of any dimension, so an example in one dimension:

Additionally you have the mask that applies the change to the base data. This is a mapping from each possible permutation of the local neighbourhood to a new bit value for the centre of the mask. For example for the red 1 in the above diagram, an example local neighbourhood is:

The red position takes into account the three nearby higher level bits, the two neighbouring bits on its level, plus itself, and the two lower level bits below it, then maps this to a new bit value for the red position. This same mapping is applied to every bit in the base data B, resulting in the new covolved data C.
In the example above, there are 8 bits in the neighbourhood, therefore 2^8 permutations to map to 0 or 1. i.e. it is a 256 to 2 mapping which can be stored as simply the set of patterns that result in a 1. Neighbourhoods of any size are allowed, since the operator 'covolves' two arbitrary datas of this structure.

For 2d base data, the higher levels can be thought of as coarser resolution images:
A neighbourhood in 2d may choose the 4 nearest parents, the 9 'Moore' neighbours and the 4 immediate children, requiring a mapping of 2^17 to 2.
You may have noticed that this is similar to Conway's life game, which is a convolution of such a 2d grid with a 3x3 neighbourhood mask. With covolution we can do Conway's life, but the extra detail levels mean that it is continuous spatially, rather than a grid:
This example uses a 3x3 parent neighbourhood only, and the mapping acts to smooth corners and remove some cells that are completely enclosed. It is a covolution applied multiple times to base data with initially only the highest level 4 pixels set to 1. Note that the patterns exist at all scales but don't repeat themselves in a simple way, due to the cellular automata nature of the operation.


Covolution can also apply to real values rather than bits, much as convolution usually is applied to real values. You replace the mapping with simply scaling each neighbour value by the mask value and summing, just as with convolution, much like is done with 'soften' and 'sharpen' filters in image packages.

Further, covolution can apply to any data structure rather than bits or reals, and the mapping can be chosen as any function that maps the neighbourhood to a new value of the data structure.

These are not actually different operations, they all are derivable from the bit version, which is ultimately the most general definition.

Continuous Time Covolution
The covolution operator acts instantaneously. It would be tempting to create an animated set by repeated covolutions: B = B*M, but this is not right, since the 1 dimension of time can't be built from multiple 0 dimensional covolutions. Instead we include scale symmetry to time also:
Just like with space, time is also broken into shorter sections for the higher detailed grid levels (like level 1). This leads to an order in which to individually apply the covolution for each level:
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,....

So a covolution applied in this order is called a covolving system. It is continuous in space and time, and means that the fine details change faster than the larger shapes on the coarser levels, producing true dynamic fractals as seen here:
Various covolving systems, simply by adjusting the mapping.
The only difficulty is finding interesting mappings. Since there are 2^17 neighbourhood patterns, there are 2^(2^17) possible mappings, which is a large search space.
The trick with finding interesting mappings is to use different constraints to search families of mappings. For example, a simple constraint is to map just the total number of neighbours onto the boolean output. Even with this simple constraint there are still 2^16 possible mappings, here is an interesting bacteria-like result:

No comments:

Post a Comment