Image Processing Reference
In-Depth Information
of interval-based computations; (ii) an analysis of the application of interval-based
computations to measure and compare the sensitivity of the signals in the frequency
domain; and (iii) an analysis of the application of interval-based techniques to the Monte-
Carlo method. Finally, Section 4 concludes this work.
2. General overview of interval-based computations
2.1 Interval arithmetic
Since its formalization in 1962 by R. Moore (Moore, 1962), Interval Arithmetic (IA) has
been widely used to bound uncertainties in complex systems (Moore, 1966). The main
advantage of traditional IA is that it is able to obtain the range of all the possible results of
a given function. On the other hand, it suffers from three different types of problems
(Neumaier, 2002): the dependency problem, the cancellation problem, and the wrapping
effect.
The dependency problem expresses that IA computations overestimate the output range of
a given function whenever it depends on one or more of its variables through two or more
different paths. The cancellation problem occurs when the width of the intervals is not
canceled in the inverse functions. In particular, this situation occurs in the subtraction
operations (i.e., given the non-empty interval I 1 - I 1 0 ), what can be seen as a particular
case of the dependency problem, but its effect is clearly identified. The wrapping effect
occurs because the intervals are not able to accurately represent regions of space whose
boundaries are not parallel to the coordinate axes.
These overestimations are propagated in the computations and make the results inaccurate,
and even useless in some cases. For this reason, the Overestimation Factor ( OF ) (Makino &
Berz, 2003; Neumaier, 2002) has been defined as
OF = (Estimated Range - Exact Range) / (Exact Range), (1)
to quantify the accuracy of the results. Another interesting definition used to evaluate the
performance of these methods is the Approximation Order (Makino & Berz, 2003;
Neumaier, 2002), defined as the minimum order of the monomial C S (where C is constant,
and   [0,1]) that contains the difference between the bounds of the interval function and
the target function in the range of interest.
2.2 Extensions of interval arithmetic
The different extensions of IA try to improve the accuracy of the computed results at the
expense of more complex representations. A classification of the main variants of IA is given
in Figure 1.
According to the representation of the uncertainties, the extensions of IA can be classified in
three different types: Extended IA (EIA), Parameterized IA and Centered Forms (CFs). In a
further division, these methods are further classified as follows. In the first group, Directed
Intervals (DIs) and Modal Intervals (MIs); in the second group, Generalized IA (GIA); and in
the third group, Mean Value Forms (MVFs), slopes, Taylor Models (TMs) and Affine
Arithmetic (AA). A brief description of each formulation is given below.
DIs (Kreinovich, 2004) include the direction or sign of each interval to avoid the cancellation
problem in the subtraction operations (I 1 + - I 1 + = 0), which is the most important source of
overestimation (Kaucher, 1980; Ortolf, Bonn, 1969).
Search WWH ::




Custom Search