Jean-Laurent Mallet. Geomodeling
Подождите немного. Документ загружается.
188
CHAPTER
4.
DISCRETE SMOOTH INTERPOLATION
with:
According
to
equation
(4.49),
each
of
these
n
constraints
generates
the
follow-
ing
terms
f
y
c
(j,p)(
a
ii...i
n
)
and
^
c
(j,p)(
a
ii...i
n
\f}
m
the
local
form
of the
DSI
equation
at
each node
Q;^...^
of the
n-cell
containing
the
point
p:
For
simplicity's sake,
it is
convenient
to
gather these
n
constraints
{c(j,
p)}
into
one
single composite constraint c(p)
defined
as
follows:
4.7.3
Generalized
fuzzy
Control-Point
Interpolating
over
a
region
of 0
Let
.M
n
(Q,
Af,
</?,C)
be a
discrete model representing
a
geometrical object
for
which
the
location
x(a)
of
each node
a 6
£7
in the 3D
space
is now
assumed
to be a
given:
Let
Q*
be a
subset
of
nodes corresponding
to a
"region"
of
Q
4.7.
THE
FUZZY
CONTROL-POINT
PARADIGM
189
and let
{A
a
(p)
: a £
O*}
be a set of
associated continuous (real valued)
weighting
functions,
9
defined
on the 3D
space
JR
and
verifying
the
three
following
"cardinal" properties:
Thanks
to the two first
cardinal properties
of the
weightings
(A
Q
(p)},
we can
be
sure
that,
for any
point
p €
M
3
,
the
function
</3(p)
defined
as
follows
interpolates
the
values
{v(ot)
:
a €
£2*}:
Moreover,
the
third cardinal property guarantees
that
this interpolation
is not
"biased:"
Definition
Let
dp
be the
interpolation
of
(p
defined above,
and let fl
p
(-) be a
family
of
linear operators indexed
by p €
M
3
and
transforming
the
vectorial
function
(p
into
a
real number
Q
p
((f>}
in
such
a way
that
where
{a
p
,...,
a™}
are
assumed
to be
linear operators.
The aim is to
install
a
DSI
constraint
on
each node
a 6 fi*
specifying
that
0>
p
(<f>)
should
be
equal
to a
given value
6
P
for a
given point
p 6
1R
3
with
a
given
certainty factor
-cu
p
:
DSI
constraint
: are
given
By
definition,
such
a
constraint
will
be
called "Generalized
fuzzy
Control-
Point" attached
to
point
p.
Due to the
linear representation
of
<fi(p)
in
function
o
we
have:
9
It
should,
of
course,
be
noted
that
these
functions
can
correspond
to
barycentric coor-
dinates,
but
they
may
also consist
of
nonlinear blending functions.
190
CHAPTER
4.
DISCRETE SMOOTH INTERPOLATION
It is
easy
to see
that
the
associated
DSI
constraint
c —
c(p)
can
then
be
formulated as
follows:
with:
4.8 The
fuzzy
Control-Node paradigm
The
notion
of
fuzzy
Control-Node (FCN),
has
already been introduced
(see
page 164):
it
consists
of a DSI
constraint
c
v
a
specifying
that
the
component
if>
v
(oi]
of
<p(a)
should
be
equal
to a
given
value
$
v
a
with
a
given certainty
factor
w
c
v
a
\
We
have already seen (see equation
(4.53))
that
such
a
constraint yields terms
T
v
cV
(a\(p)
and
7^
(a)
denned
by
equation (4.53):
The
notion
of FCN is the
simplest
soft
DSI
constraint imaginable.
This
section
shows
• how to
transform
a
constraint
c 6
C~
into
a
series
of FCN
constraints,
and
• how the DSI
solution
is
sensitive
to the
location
of the FCN
constraints.
4.8.1
Equivalent dynamic
fuzzy
Control-Node
In
this section,
we
show
that
any
constraint
c G
C~
is
equivalent
to a set of
Dynamic
fuzzy
Control-Node constraints
{c
v
a
a
e
f2£,
v =
1,...,
n}
associated
with
a set of
values
{0al
a
^
^c>
v
=
1>
• •
•,
^}
to be
updated
at
each
step
of
the
iterative
DSI
algorithm.
Definition
Let
A
c
and
b
c
be the
parameters
that
define
a
constraint
c
belonging
to
C~
and let
Sl
v
a
be the
subset
of
0
defined
by
4.8.
THE
FUZZY CONTROL-NODE PARADIGM
191
We
will
note
as
{c
v
a
\a
e
0^,^
=
l,...,n}
the set of
fuzzy
Control-Nodes
associated with
the
constraint
c and
denned
by
where
the
increment
A^(a|<^)
is
defined
by
Theorem
associated Dynamic
fuzzy
Control-Nodes.
Proof
If
we
compare
the
equation
(4.52),
and
(4.53)
with equation (4.51), then
it is
easy
to
check
that
c has the
same contribution
to the
terms
7^
(a)
and
T
v
(a\(p]
denned
by
equation
(4.48)
as the set of
constraints
{c
v
a
\a
e
0^,
v =
1,...,
n}.
As
a
consequence,
c and the set
{c^|ct
6
W
c
,v
=
l,...,n}
have
the
same
contribution
to the
equation
(4.46)
used
to
update
^(ot)
in the
DSI
iterative
algorithm.
4.8.2
Pseudo-distance
to
data
This section addresses
the
problem
of
building
a
scalar
function
d(a\(p)
mea-
suring
a
"pseudo-distance"
of
node
a
relative
to the
location
of
Control-Nodes
(CN)
and
fuzzy
Control-Nodes (FCN)
set on the
components
of a
function
(p.
It is
important
to
mention
that
the
proposed approach
is
purely pragmatic
and has no
theoretical claim.
Definition
of
d(a\Q*)
Let us
consider
a
discrete model
A^
1
(il,
TV,
(p,Cp)
and let
O*
be the
sub-
set of
O
to
which
the CN and FCN
constraints
defined
by
C^
are
attached.
By
definition,
we
call "pseudo-distance
to CN and
FCN"
or,
more simply,
"pseudo-distance
to
data,"
the
function
d(a\fl*)
equal
to the
smallest number
of
steps
that
one has to
take
from
a
e
f2
on the
graph
Q(£l,N)
before
reaching
a
node
a*
£
fi*.
Building
d(a\W]
In
practice,
the
function
d(a\£l*)
defined
above
can be
built using
the
following
algorithm, where
N(/3)
is
assumed
to
consist
of all the
nodes
that
can be
reached
from
/3
6 fi in one
step
on the
graph
G(£l,
N):
Any constraint
is equivalent to the set
of its
192
CHAPTER
4.
DISCRETE
SMOOTH
INTERPOLATION
//—
Building
pseudo-distance
to
data
//—
initializations
let
S[-]
be an
array
of 2
empty
stacks
for_all(
a
<E
to )
d(a\Sl*)
<—
(-1)
;
for_all(
a* €
17*
) {
d(a*|£T)
<—
0 ;
5[0].push(a*)
;
}
i
<—
0 ;
dist
«—
1 ;
//-
computing
d(a|fl*)
do
{
while(
5^].not-empty()
) {
£<—S[t].pop()
;
for_all(
aeJV(/3)
) {
if(
d(a|Q*)
== -1 ) {
d(a|Q*)
<—
dist
;
S[l
-
i].push(a)
}
}
}
%
<—
(1 - i) ;
dist
<—
(dist
+ 1) ;
}
while(
5[i].not-empty()
) ;
If
the
geometry
x(ai)
of the
nodes
of
G(£l,
N]
is
known
for all a G 17, and if the
edges
of
£(17,
N)
are of
about constant length, then
d(o:|17*)
is
approximately
a
geodesic distance (see section
(5.3))
between
a and the
closest node
a
€
17*
holding
a CN or an
FCN.
As
shown
in
figure
(4.8),
if
smooth variations
of
d(a\£l*)
on
17
are re-
quired, then
the
smoothing technique
presented
on
page
167 can be
applied
to
d(a\tt*).
DSI
variance
of
estimation
Let us
consider
a
discrete model
A
/
(
1
(17,
AT,
</?,C
v
).
The DSI
interpolation
yields
no
more than
an
estimate
<p(a)
of the
true unknown value
<£>(a:),
and
the
square error
of
estimation
is,
on
average,
an
increasing
function
of the
pseudo-distance
d(a\fi*)
to the
data.
By
definition,
the
"DSI variance
of
estimation"
(T^(a\<f>,£l*)
of
(p
at
node
a €
17
and
relative
to the set
17*
of CN and FCN
consists
of the
function
where
6 is the
average length
of the
edges
of the
graph
C?(17,
N),
while
7^0
is
the
estimated
variogram
of
<f>
(see definition
(9.49)).
The DSI
variance
of
estimation
so
defined
demonstrates behavior
and nu-
merical
values close
to
those
of the
variance
of
estimation
of the
"Simple
4.9.
FROM
A
DISCRETE
TO A
CONTINUOUS
MODEL
193
Figure
4.8 An
example
of
geological
horizon
interpolating
nine
well-markers
and
associated
grey
scale
representation
of the
pseudo-distance
d(o:|Q*)
to
these
well-markers.
Kriging"
interpolator presented
in
section (9.7.3).
In
practice,
the
function
cr|,(a|(/?,
fJ*)
can be
considered
as an
approximation
of the
average
of the
square error
S^(a\(p,
£7*)
defined
by
equation (4.79).
Example
Figure (4.8) gives
an
example
of a
geological horizon whose geometry
is
con-
trolled
by
nine
FCN
called
"well-markers,"
which correspond
to the
intersec-
tions
of
this
horizon with wells.
The
pseudo-distance
to
these
FCN is
color
coded
on the
surface according
to a
given grey scale.
4.9
From
a
discrete
to a
continuous
model
This
section
describes
how any
discrete
function
</?,
defined
on the finite set
17
of
the
nodes
of a
given graph
G(£l,
A/"),
can be
transformed into
a
continuous
function
<p(u)
defined
on a
continuous parametric domain
D.
4.9.1
Global
parameterization
ofQ(£l,N)
Definition
Let
us
assume
that
the
graph
fy(i7,7V)
models
an
object
A
whose topological
dimension
is
equal
to d. By
definition,
we
will
say
that
A is
"globally param-
eterized"
if
there
is a
cellular
partition
10
P(D)
of a
closed region
D of
lR
d
such
that
10
See
section
(2.3).
194
CHAPTER
4.
DISCRETE SMOOTH INTERPOLATION
Figure
4.9
Global
parameterization
of
a
2-dimensional
graph
Q(£l,
N).
• D has the
same topological dimension
as the
object
A
dim(D)
=
dim(A)
= d
•
There
is a
vectorial
function
u
from
£1
to D
denning
a
one-to-one mapping
between
the
edges
and the
vertices
of
<5(fi,
N) and the
edges
and the
vertices
ofP(D),
respectively:
Any
function
u
honoring
the
above constraints (4.81)
is
called
a
"global
pa-
rameterization"
of A, and D is
called
the
"parametric domain" associated
with this parameterization.
As
suggested
in
figure
(4.9),
such
a
parameteri-
zation
u(a)
is a
vectorial
function
having
d
components
defined
on
O.
These
components
are
called "parameters"
of the
parameterization
u:
Examples
of
global
parameterizations
It is
easy
to see
that
the
global parameterization
of an
object
A
associated
with
a
graph
(?(fi,
N) is not
unique.
In
practice, such
a
parameterization
can
be
defined
in
many
different
ways, depending
on the
nature
of
C/(£],JV);
for
example:
• If
<?(Q,
N)
corresponds
to a
curvilinear regular 3-grid
A
such
as the one
shown
in
figures
(1.5)-D
and
(10.1), then
d — 3 and it is
natural
to
choose
the 3
curvilinear
coordinates
(u,v,w)
of the
nodes
in the
grid
for
u(a):
• If
£7(Q,JV)
corresponds
to a set A of
adjacent tetrahedra such
as the one
shown
in figure
(1.5)-B,
then
d = 3 and it is
natural
to
choose
the 3
Cartesian
coordinates
(x,
y,
z]
of the
nodes
in the 3D
space
for
u(a):
4.9. FROM
A
DISCRETE
TO A
CONTINUOUS MODEL
195
• If
£?(fi,
TV)
corresponds
to a
polygonal
curve
A
such
as the one
represented
in
figure
(1.5)-C,
then
d — 1 and it is
natural
to
choose
the
curvilinear
abscissa
s
of the
nodes
on the
curve
for
u(a):
• If
£/(Q,
TV)
corresponds
to a
2-dimensional
triangulated
surface
A
such
as the
one
shown
in figure
(4.9),
then
d = 2 and we
will
see in
section
(6.5) that
it
is
possible
to use the
DSI
method
for
interpolating
on
SI
a
pair
of
parameters
(u
l
,u
2
)
that
play
the
role
of
2-dimensional
parametric
coordinates
for the
surface.
In
this
case,
it is
natural
to use
these parameters
to
define
u(a):
4.9.2
Continuous model
Global
continuous
interpolation
Any
function
(p
denned
on
f2
appears
as the
sampling
of a
continuous
function
<£(u)
defined
on D in
such
a way
that
By
definition,
any
continuous function
</5(u)
honoring
the
above constraint
(4.82)
is
called
a
"global interpolation"
of (p.
When there
is no
possible
confusion,
we
will
use the
following
simplified notation:
Global
continuous
linear
interpolation
Among
the
many possible interpolations
<^(u),
linear interpolants with
the
following
form
are
certainly
the
most frequently used
in
interpolation prob-
lems:
In
this
definition
of
v?(u),
we
assume
that
{A
a
(u)
: a
e
17}
is a set of
continu-
ous
(real-valued)
weighting functions
denned
on the
d-dimensional
parametric
domain
D and
honoring
the
three
following
"cardinal" properties similar
to
those already introduced
in
section (4.7.3):
Thanks
to the two first
cardinal properties given above,
we are
sure
that,
for any
point
u £ D, the
function
<p(u)
continuously interpolates
the
values
{(p(oi)
:
a € fi} of any
discrete
function
(p
defined
on 0.
Moreover,
the
third
cardinal property guarantees
that
this interpolation
is not
"biased:"
196
CHAPTER
4.
DISCRETE
SMOOTH
INTERPOLATION
For
example,
the
"Ordinary
Kriging"
interpolant
presented
in
section
(9.7)
is
based
on
weighting functions
{A
a
(u)}
honoring
constraints
(4.83).
Global
piecewise
continuous
linear
interpolation
Let
C(u)
be the rf-cell of
P(D]
containing
u.
Among
the
many
possible
choices
for the
functions
{A
a
(u)},
the
most
interesting
ones
are
those
that
involve
only
the
subset
0(u)
of
Q
consisting
of the
nodes
a
such
that
u(a)
is
a
vertex
of
C(u):
For
example,
the
barycentric
interpolant
presented
in
sections
(4.7.3),
and
(6.1.3)
is a
local
interpolant
that
honors
the
constraints
(4.83)
and can be
written
according
to the
above
equation
(4.84).
4.10 Conclusions
In
practice,
the
DSI
method
has
proven
to be a
very
efficient
modeling
method.
The
main
reasons
for
this
success
are the
following:
•
This method enables
us to
interpolate
the
geometry
and the
properties
of
curves,
surfaces,
and
solids using
the
same
software.
This amazing
flexibility
is
due to the
fact
that
the DSI
method does
not
need
to
know
the
topological
dimension
of the
object described
by the
graph
Q(^i,N).
Furthermore,
it
is
even possible
to
apply
DSI to
discrete models
of
non-uniform dimension,
which
are
locally
isomorphic
to a
curve,
a
surface,
or a
solid;
for
example,
this
is
the
case
for a
"high permeability region"
in a 3D
layer, which
is
locally
a
micro
channel
(= a
curve) connected
to a
permeable
fault
(= a
surface)
and
itself
intersecting
a
permeable lens
(= a
solid).
•
Potentially,
it is
possible
to
account
for any
type
of
data provided
that
these
data
can be
turned into linear constraints.
• In the
parts
of an
object
.M
n
(fi,
N,
<p,C)
where
the
constraints
c €
C~
are
contradictory,
these constraints behave
in a
least square sense
and the
asso-
ciated certainty factors
w
c
control their behavior.
For
example,
if a
part
of a
surface
is
attracted
by two
data
points
PI
and
P-z
located
on two
sides
of
this
surface,
then
the
surface
will
pass between
the
points
PI
and
P^
and
will
be
closer
to
PI
if the
certainty factor
of
PI
is
greater than
that
of
PI
.
• In the
parts
of an
object
.M
n
(r2,]V,
<p,C)
where
the
constraints
c G
C~
are
consistent, these constraints
are
respected almost perfectly
and
behave
as if
they were "hard" constraints. This
is
surprising when
we
remember that,
from
a
mathematical point
of
view,
the
constraints
are
taken into account
in
a
least square sense.
• It is
extremely easy
to
account
for
discontinuity:
we
have only
to
build
the
topological model
(?(fl,
N)
in
such
a way
that
it
respects these discontinuities.
•
Anisotropies
can
also easily
be
taken into account. This
can be
achieved
in
two
different
ways: either
by
defining
the
weighting
coefficients
{v(a,(3)}
in
such
a way
that they integrate this anisotropy
or by
introducing some special
constraints
modeling
it
(see page 554).
It is
also important
to
note
that
the
4.10. CONCLUSIONS
197
anisotropy
can be
heterogeneous
and can
change
from
one
node
a € fi to
another.
• The
iterative algorithm converges very fast and, even
for
models having several
thousands
of
nodes,
the
solution
can be
obtained
in
real time
on
most
of the
current workstations. Moreover,
the
more constraints there are,
the
more
rapidly
the
method converges;
in the
end, given enough consistent constraints,
the
method
may
even converge
in one
iteration.
•
Last,
but not
least,
the
DSI
method
is
numerically very stable, even when
the
data
are
strongly clustered.
From
a
theoretical point
of
view,
the
most interesting
aspect
of DSI is
certainly
the
fact
that
this generic interpolation method
is
completely independent
of
the
data:
DSI
sees only constraints induced
by the
data
and not the
data
themselves. This means
that
any
existing
software
based
on DSI
does
not
have
to be
changed each time
a new
type
of
data
is
added
to
enrich
the
modeling process.
This
is
very important
for the
future
because
it
allows
an
incremental approach
to
software
development dedicated
to DSI
constraints.