Image Processing Reference
In-Depth Information
cells where these collisions occur are those of interest: they are exactly at the middle
of the shortest paths between the seeds. In Fig. 10.10, this happens after the forth
transition. We can see that the distance values in the neighborhood of these middles
is special. Each of the middle cells can actually see that the distance pattern in its
neighborhood can only appear because of the presence of two seeds at opposite
directions.
In Fig. 10.11 theses middle cells are marked in light green. We need to express
the general middle detection rule more precisely of course. For a particular grid, it is
possible to build this rule by enumerating all local distance patterns corresponding
to middles, but expressing this detection rule for general cellular spaces appears to
be the main difficulty in the convex hull construction. So let us pretend that we can
do it and proceed to the final step. We will come back to the middle detection in the
next section.
So if we suppose that we can detect these middle cells, the rest of the evolution
is obtained easily and is depicted in Fig. 10.11. Once the middles are detected, we
can consider the neighbors of the middles. Let us consider one of them and call
it
x
. It has all required information to know if it belongs to the shortest path or
not. Indeed, it knows its distance value
d
(
s
,
x
)=
dist
t
(
x
)
to the nearest seed
s
,the
distance value
d
1.
It can thus determine whether it is between the seed and the middle, i.e. whether it
is on a shortest path joining
s
and
y
,i.e.
x
(
s
,
y
)=
dist
t
(
y
)
of the marked middle
y
, and the distance
d
(
x
,
y
)=
∈
[
s
,
y
]
. The triangle equality
d
(
s
,
y
)=
d
1 in this case. So if
y
is marked as being in the convex hull and this reduced triangle equality is verified,
x
can deduce that it has to belong to the convex hull too. Formally, we obtain the
following transition rule:
(
s
,
x
)+
d
(
x
,
y
)
to be checked is reduced to dist
t
(
y
)=
dist
t
(
x
)+
)
.
(10.4)
A more simple explanation of the behavior is that to go back to the seeds from
the middles, you have to follow the distance value in decreasing order, i.e. the cell
x
takes the mark from the cell
y
if dist
t
(
back
t
+
1
(
x
)=
cent
t
+
1
(
x
)
∨∃
y
∈
N
(
x
)
;dist
t
(
y
)=
dist
t
(
x
)+
1mod3
∧
back
t
(
y
1. Both views are simply
equivalent, they both describe a trajectory along the shortest possible paths back to
the seeds. It is interesting to note that anywhere the notion of shortest path is used,
it can somehow be reduced to the triangle equality. Coming back to Fig. 10.11, we
can see after 4 transition the detection of the middles of distance value 1, and then,
at the next configuration some cells of distance value 0 deduce that they have to be
in the convex hull from the presence of a marked cell in their neighborhood and the
differences in their distance value, and after that, the same thing happens to some
cells of distance value 2 at the next configuration, and so on. It worths checking the
distance values on Fig. 10.10 while consulting Fig. 10.11.
x
)=
dist
t
(
y
)
−
10.4.2.2
Pairwise Hull Construction
We now have a way to construct the convex hull of two seeds using one distance
field and some detections on it. When considering many seeds, we can obviously not
Search WWH ::
Custom Search