Image Processing Reference
In-Depth Information
Voronoï diagram, Delaunay and Gabriel graphs in order to make the full connection
between the Euclidean and the cellular case, and is therefore postponed to Sect. 10.5.
10.4.2.1
Paths Joining Two Distant Seeds
As just explained, to connect two distant seeds, we need to compute some distance
information. The cellular automata framework only allows for a finite number of
state for the cells, so we can not store sets of integers, or even single arbitrarily
large integers. We are reduced to compute at each cell only one distance value, and
to compute it modulo 3: this distance value is the distance of the cell to its closest
seeds. We could have called this the distance rule, but we in fact call this the distance
field .
In the cellular automata case, this distance field corresponds to the computation
of the minimal distance modulo k ,where k depends on properties of the complete
cellular automaton where the distance field is used. It is a very general notion that
can be used to solve many problems and can handle the motion of seeds and asyn-
chronicity to some extent for example. Its full description [10] is out of the scope of
this topic chapter so we present only a reasonable restricted version of it to the case
of synchronous static seeds. In this case the value of k is 3.
In this restricted version, the idea is to begin with the value 0 on the seeds, and
the value 1 anywhere else as shown in the initial configuration of Fig. 10.10. From
this initial configuration, each cell increases its value at each transition until its value
becomes greater than one of its neighbor value 1 . This happens exactly when one of
the neighbors has a different value since all values only increases then stops at some
transition. Formally, the transition function is:
0
if x
P
dist t + 1 (
x
)=
dist t (
x
)+
1mod3
if x
P
∧∀
y
N
(
x
)
;dist t (
y
)=
dist t (
x
)
(10.3)
dist t
(
x
)
if x
P
∧∃
y
N
(
x
)
;dist t
(
y
) =
dist t
(
x
)
The meaning of this transition rule can be observed on Fig. 10.10. After the first
transition, all values are at 2, except the seeds, which kept their value 0, and the
cells around the seeds which kept their value 1 because of the presence of 0 in their
neighborhood. After the second transition, all cells values go to 0, except the seeds
(because they are seeds), the neighbors of the seeds (because of the presence of the
0 in their neighborhood while their value is 1) and the neighbors of the neighbors of
the seeds (because of the presence of 1 in their neighborhood while their value is 2).
So circles of cells of same distance value are constructed, and after some transitions,
the circles coming from different seeds eventually collide at different cells. The first
1
Note that because of the modulo three operation, one should only look at the differences
between values locally, i.e. in the neighborhood of a given cell. If this cell value is 1, then
the order is 0 < 1 < 2, but if this cell value is 0 or 2, the orders are respectively 2 < 0 < 1
and 1 < 2 < 0. So a cell of value v considers, in its local neighborhood, that the value
v 1 mod 3 is less than its value and v + 1 mod 3 is greater than its value. This is the way
the comparisons have to be understood.
 
Search WWH ::




Custom Search