Distance Transforms

Cellular Automata on Directed Acyclic Networks on a Grid

Richard Scott, CDx Laboratories

Distance Transform Setup

Euclidean                                 X                                            Y

Kernels

({{1, 1, 1}, {1, 0, 1}, {1, 1, 1}})                         ({{2, 1, 2}, {1, 0, 1}, {2, 1, 2}})                        ({{3, 2, 3}, {2, 0, 2}, {3, 2, 3}})                      ({{1, 2, 3}, {8, 0, 4}, {7, 6, 5}})
                        Square                                        Diamond                                        Octagon                                         Spiral

Min (self,  neighbors  +  kernel)

distanceTransformCA[kernel_, 
            size_] := 
CellularAutomaton[{Min[# + 
                      kernel] &, {}, {1, 1}}, {{{0}}, 2*size*Max[kernel]}, 
              size, -1][[1]];

euclideanDistanceTransform[kernel_, 
              size_?AtomQ] := 
CellularAutomaton[
{(Min[
                        Map[euclideanDT, (# + 
                              kernel), {2}]]) &, {}, {1, 1}}, {{{0}}, 
                  2*size*Max[kernel]}, size, -1][[1]];

euclideanDT[
          val_] :=  
BitAnd[val, 2^20 - 1] +  
          2^20 IntegerPart[
              0.5 + 
Sqrt[
                  BitAnd[val, 2^10 - 1]^2 +  
                    BitAnd[IntegerPart[val/(2^10)], 2^10 - 1]^2]]

Directed Acyclic Network

({{1, 1, 1}, {0, x, 0}, {0, 0, 0}})       This kernel propagates distances downward only.

Missing Edges

Properties

Distance transform can generate any acyclic network with suitable kernels

({{kernel[1], kernel[2], kernel[3]}, {kernel[8], x, kernel[4]}, {kernel[7], kernel[6], kernel[5]}}) > 0, = 0 for missing edges

Result independent of update order, asynchronous, parallel or multiple updates ok

Propagation to a fixed point - maximum number of updates required equals the number of points in the image

A distance transform is its own causal network - includes the class of growth rules

Count the Acyclic Orientations

Sloane's on-line encyclopedia of integer sequences: A080690

({{n, 1, 2, 3, 4}, {"orientations without diagonals", 1, 14, 2398, 5015972}, {"approximation: \!\(2\^\(2 \((n - 1)\)\)\)\!\(\((7/2)\)\^\(\((n - 1)\)\^2\)\)", 1.`, 14.`, 2401.`, 5.044200875`*^6}, {"orientations with diagnonals", 1, 24, 19968, 550606848}, {"approximation: \!\(2\^\(2 \((n - 1)\)\)\)(6\!\(\()\^\(\((n - 1)\)\^2\)\)\)", 1.`, 24.`, 20736.`, 6.44972544`*^8}})

Totalistic rule

Least significant bit for the rule
Kernel a multiple of 2
512 possible rules, usually only 32 are different
Eg. rule 416 
- 0, 1 or 3 bits set among directed (smaller) neighbors 
- equivalent to eca 151 and its complement 22 - the only type 3 totalistic eca rule

IntegerDigits[416, 2]

showContours = False;
kernel1 = kernel0 = 2 {0, 0, 0, 0, 1, 1, 1, 0};    
dtTest[0, 416, kernel1, kernel0, 65, 33, {{1, 33, 1}}, 
      False];

showContours = True;
kernel1 = kernel0 = 
          2 {1, 1, 1, 1, 1, 1, 1, 1};
dtTest[0, 416, kernel1,  kernel0, 65, 65, {{1, 1, 1}, {1, 65, 65}}, 
        False];

Same rule, different networks

showContours = True;
dtTest[0, 416, 2 {0, 1, 0, 1, 0, 1, 0, 1}, 
        2 {0, 1, 0, 1, 0, 1, 0, 1}, 65, 65, {{1, 33, 33}}, 
        True]; 
dtTest[0, 416, 2 {3, 2, 3, 2, 3, 2, 3, 2}, 
        2 {3, 2, 3, 2, 3, 2, 3, 2}, 65, 65, {{1, 33, 33}}, 
        True]; 
dtTest[0, 416, 2 {1, 2, 3, 4, 5, 6, 7, 8}, 
        2 {1, 2, 3, 4, 5, 6, 7, 8}, 65, 65, {{1, 33, 33}}, 
        True];

Open dtTestStaticKernel . nb

Dynamic Kernels

Use 2 Kernels  -  
        choose the kernel depending on the least significant bit

IntegerDigits[256, 2, 9]   
showContours = True;
dtTest[0, 128, 2 {1, 1, 1, 1, 1, 1, 1, 1}, 
        200 {1, 1, 1, 1, 1, 1, 1, 1}, 65, 65, {{1, 33, 33}}, 
        True];

Open dtTestDynamicKernel . nb

Circles

IntegerDigits[320, 2, 9]   
showContours = True;
dtTest[0, 320, 2 {3, 2, 3, 2, 3, 2, 3, 2}, 
        2 {1, 1, 1, 1, 1, 1, 1, 1}, 65, 65, 1, True];

Open Circles . nb

8-bit Rotationally Symmetric Rules

List the smaller neighbors,  
      starting from the top left,  going clockwise
Convert to an integer .    Eg:

({{1, 1, 1}, {0, x, 0}, {0, 0, 1}})   ->  {1, 1, 1, 0, 1, 0, 0, 
          0} -> 232

Take all cyclic rotations of the list,
Take the position of the minimum. 
The position of the minimum in the list gives a rotation to normalize the neighborhood

Min[{232, 116, 58, 29, 142, 71, 163, 209}]

Count[
      Table[Ordering[Table[bitRotateRight[nbrcode, n], {n, 0, 7}], 
            1][[1]],  {nbrcode, 0, 255}], 1]

There are 36 different rotationally symmetric neighborhoods
30 if reversals are included
Look at least significant 3 - 
      bits only for rulespace of size 256

Open dtTestStaticKernel8bitRot . nb

Reversible Rules?

IntegerDigits[60, 2, 8] 
showContours = True;
dtTest[1, 60, 2 {3, 2, 3, 2, 3, 2, 3, 2}, 2 {3, 2, 3, 2, 3, 2, 3, 2}, 
        65, 65, {{1, 33, 1}}, False];

Rule 60,  
    complement 195   -  
      Reversibility on some parts of the network  -  
      not one of the 6 reversible ecas.

dtTest[1, 60, 2 {3, 2, 3, 2, 3, 2, 3, 2}, 
        2 {3, 2, 3, 2, 3, 2, 3, 2}, 65, 65, 
        Table[{Random[Integer], i, 1}, {i, 65}], False];

16-bit Rotationally Symmetric Rules

Use smallest 4 - bits of the  lsb pattern,  
      rotated to put the smaller neighbors into the minimum  form
Rulespace size 65536
See dtrot16 random . gif

IntegerDigits[12946, 2, 16]
showContours = True;
dtTest[2, 12946, 2 {3, 2, 3, 2, 3, 2, 3, 2}, 
        2 {3, 2, 3, 2, 3, 2, 3, 2}, 65, 65, 1, False];

Rule 46506  -  Fracture lines

Show[
      RasterGraphics[
        BitAnd[1, 
          distanceTransformGen[2, 46506, 2 {3, 2, 3, 2, 3, 2, 3, 2}, 
            2 {3, 2, 3, 2, 3, 2, 3, 2}, 257, 
            257, {{0, 129, 129}, {0, 128, 129}, {1, 128, 128}}]]]]

Directional Selection

Select the kernel using the  lsb of the opposite pixel  if smaller,  or 0
({{a, b, c}, {d', x, d}, {c', b', a'}})  
Similar totalistic rule behaviour

({{({{Ruletype}}), ({{Kernel1}}), ({{Kernel2}}), DirSel, ({{"Interesting Rules"}})}, {({{"totalistic"}}), ({{6, 4, 6}, {4, x, 4}, {6, 4, 6}}), ({{2, 2, 2}, {2, x, 2}, {2, 2, 2}}), "On", ({{128, 160, 320, 336, 352, 400}})}, {({{"totalistic"}}), ({{60, 40, 60}, {40, x, 40}, {60, 40, 60}}), ({{22, 22, 22}, {22, x, 22}, {22, 22, 22}}), "On", ({{192, 208, 320, 336, 400}})}, {({{"totalistic"}}), ({{60, 40, 60}, {40, x, 40}, {60, 40, 60}}), ({{2, 2, 2}, {2, x, 2}, {2, 2, 2}}), "On", ({{160, 288, 304, 320, 336}})}, {({{"totalistic"}}), ({{20, 20, 20}, {20, x, 20}, {20, 20, 20}}), ({{2, 2, 2}, {2, x, 2}, {2, 2, 2}}), "On", ({{128, 160, 208, 320, 336}})}, {({{"totalistic"}}), ({{20, 2, 20}, {20, x, 20}, {20, 2, 20}}), ({{20, 20, 20}, {2, x, 2}, {20, 20, 20}}), "On", ({{160, 192, 288, 320, 352}})}, {({{"totalistic"}}), ({{20, 2, 20}, {2, x, 2}, {20, 2, 20}}), ({{2, 20, 2}, {20, x, 20}, {2, 20, 2}}), "On", ({{150, 256, 320}})}})

Open dtTestEval1 . nb

Direction Selection - 8-bit Rotationally Symmetric Rules

({{({{Ruletype}}), ({{Kernel1}}), ({{Kernel2}}), DirSel, ({{"Interesting Rules"}})}, {({{"8-bit rotational"}}), ({{6, 4, 6}, {4, x, 4}, {6, 4, 6}}), ({{2, 2, 2}, {2, x, 2}, {2, 2, 2}}), "On", ({{5, 13, 20, 21, 28, 29}, {33, 37, 39, 41, 45, 53}, {57, 60, 61, 69, 77, 84}, {85, 86, 87, 90, 92, 101}, {102, 103, 105, 106, 109, 113}, {116, 117, 121, 122, 124, 125}, {126, 133, 146, 147, 173, 177}, {191, 185, 188, 189, 194, 210}, {229, 233, 244, 252, "", ""}})}, {({{"8-bit rotational"}}), ({{6, 6, 6}, {2, x, 6}, {6, 2, 6}}), ({{6, 2, 6}, {6, x, 2}, {6, 6, 6}}), "On", ({{5, 6, 20, 33, 78, 85}, {90, 131, 141, 151, 153, 163}, {166, 169, 173, 185, 201, 213}, {217, 237, 242, 245, "", ""}})}, {({{"8-bit rotational"}}), ({{100, 2, 100}, {100, x, 100}, {100, 2, 100}}), ({{100, 100, 100}, {2, x, 2}, {100, 100, 100}}), "On", ({{0, 1 (hex), 5, 6, 7, 13}, {15, 19, 20, 25, 38, 45}, {52, 57, 61, 85, 99, 105}, {133, 137, 141, 153, 157, 163}, {169, 182, 225, 233, 243, ""}})}, {({{"8-bit rotational"}}), ({{20, 2, 20}, {2, x, 2}, {20, 2, 20}}), ({{2, 20, 2}, {20, x, 20}, {2, 20, 2}}), "On", ({{7, 29, 53, 69, 77, 93}, {121, 137, 145, 146, 150, 163}, {165, 169, 173, 177, 198, 201}, {210, 218, 229, 233, 241, 242}, {249, "", "", "", "", ""}})}})

Do[showContours = True; 
      dtTest[4, rule, {6, 4, 6, 4, 6, 4, 6, 4}, {2, 2, 2, 2, 2, 2, 2, 2}, 65, 
        65, 1, False] , {rule, 116, 116}]
Do[showContours = True; 
      dtTest[4, rule, {6, 4, 6, 4, 6, 4, 6, 4}, {2, 2, 2, 2, 2, 2, 2, 2}, 65, 
        65, 1, False] , {rule, 126, 126}]

Open dtTestEval2 . nb

Hexagonal Snowflake Rules

dtTest[6, 128, 2 {3, 3, 0, 4, 0, 3, 3, 4}, 
      2 {0, 5, 5, 4, 5, 5, 0, 4}, 257, 257, 1, True]

Alternate kernels on rows :            Even Rows                              Odd Rows
                                                                              ({{3, 3, 0}, {4, x, 4}, {3, 3, 0}})                   ({{0, 5, 5}, {4, x, 4}, {0, 5, 5}})  
Kernel selected using bit 2
Rule runs on bit 1 as before
Distances in bits 4 and up

showContours = False;
dtTest[6, 128, 2 {0, 9, 9, 6, 9, 9, 0, 6}, 
        2 {3, 3, 0, 6, 0, 3, 3, 6}, 65, 65, 1, True];

showContours = True;
dtTest[6, 128, {0, 10, 10, 6, 10, 10, 0, 6}, 
        2 {5, 5, 0, 10, 0, 5, 5, 10}, 65, 65, 1, True];

Open Snowflakes . nb

Worm Rules

Turn left or right from the smallest neighbor direction
Update the first larger neighbor found

showContours = False; dtTest[7, 432, 
      2 {1, 1, 1, 1, 1, 1, 1, 1}, 2 {1, 1, 1, 1, 1, 1, 1, 1}, 65, 65, 0, 
      False]

showContours = False; dtTest[7, 472, 
      2 {1, 1, 1, 1, 1, 1, 1, 1}, 2 {1, 1, 1, 1, 1, 1, 1, 1}, 65, 65, 0, 
      False]

Open Worms . nb

Timing, Implementation

25                     81                  289                1089                  4225              16641                 66049

CellularAutomaton[]  vs .  distanceTransformGen[]

Use of Heap to find minimum pixel on current boundary  -  O (log (n))

Conclusion

Distance transforms can be defined as cellular automata on directed acylic
\(networks\ on\ a\ grid . 


          They\ are\ useful\ for\ modeling\ patterns\ where\ growth\ occurs\ along\ a\ front\)
which sweeps across an area,  
      leaving a fixed pattern behind .  Examples
include the time evolution of 1  D cellular automata,  
      and more general cases
where the network connections and shape of the front are generated by the
\(rule . 


          An\ efficient\ algorithm\ for\ distance\ transforms\ runs\ in\ O \((n\ logn)\)\ time\ where\)
n is the number of grid points,  
      which compares to worst case O (n squared) run
\(time\ when\ using\ a\ standard\ 2\ D\ cellular\ automaton\ implementation . 


          Please\ see\ my\ forum\ post\ on\ the\ subject\ where\ I\ investigated\ the\ kinds\)
patterns generated by some of these rules .

http://forum . wolframscience . com/showthread . php?s=80303  b93bda13100205404f0a3a62317 & threadid = 379

Rule Type Summary

({{"Type", \(Rule\ Description \*"""\), "Number of Rules"}, {0, ({{"Totalistic rule for update of lsb;"}, {"distance increments to larger neighbors updated"}, {"with one of 2 kernels, selected using lsb"}}), 512}, {1, ({{"8-bit rotationally symmetric rule for update of lsb;"}, {"rule uses lower 3 bits of rotated border pattern"}}), 256}, {2, ({{"16-bit rotationally symmetric rule using"}, {"lower 4 bits of rotated border pattern"}}), 65536}, {3, ({{"Totalistic rule with directional selection of kernel;"}, {"kernel selected using lsb of opposite neighbor"}, {"instead of lsb of center pixel"}}), 512}, {4, ({{"8-bit rotationally symmetric rule using"}, {"lower 3 bits of rotated border pattern"}, {"with directional selection of kernel"}}), 256}, {5, ({{"16-bit rotationally symmetric rule using"}, {"lower 4 bits of rotated border pattern"}, {"with directional selection of kernel"}}), 65536}, {6, ({{"}, {\(kernel\ selected\ using\ bit2, \ bits\ 2, 
                    3\ used\ for\ rounding; \*"""\)}, {"supports hexagonal snowflake rule"}}), 512}, {7, ({{"totalistic worm: updates the distance of the first,"}, {"larger neighbor to the left or right of the smallest,"}, {"neighbor, turning left for lsb=0, right for lsb=1"}}), 512}})