Inverse distance weighting
Inverse distance weighting (IDW) is a type of deterministic method for multivariate interpolation with a known scattered set of points. The assigned values to unknown points are calculated with a weighted average of the values available at the known points.
The name given to this type of methods was motivated by the weighted average applied, since it resorts to the inverse of the distance to each known point ("amount of proximity") when assigning weights.
Contents
1 Definition of the problem
2 Shepard's method
2.1 Historical reference
2.2 Basic form
2.3 Example in 1 dimension
2.4 Łukaszyk–Karmowski metric
2.5 Modified Shepard's method
3 References
4 See also
Definition of the problem
The expected result is a discrete assignment of the unknown function u{displaystyle u} in a study region:
- u(x):x→R,x∈D⊂Rn,{displaystyle u(x):xto mathbb {R} ,quad xin mathbf {D} subset mathbb {R} ^{n},}
where D{displaystyle mathbf {D} } is the study region.
The set of N{displaystyle N} known data points can be described as a list of tuples:
- [(x1,u1),(x2,u2),...,(xN,uN)].{displaystyle [(x_{1},u_{1}),(x_{2},u_{2}),...,(x_{N},u_{N})].}
The function is to be "smooth" (continuous and once differentiable), to be exact (u(xi)=ui{displaystyle u(x_{i})=u_{i}}) and to meet the user's intuitive expectations about the phenomenon under investigation. Furthermore, the function should be suitable for a computer application at a reasonable cost (nowadays, a basic implementation will probably make use of parallel resources).
Shepard's method
Historical reference
At the Harvard Laboratory for Computer Graphics and Spatial Analysis, beginning in 1965, a varied collection of scientists converged to rethink, among other things, what we now call geographic information systems.[1]
The motive force behind the Laboratory, Howard Fisher, conceived an improved computer mapping program that he called SYMAP, which, from the start, Fisher wanted to improve on the interpolation. He showed Harvard College freshmen his work on SYMAP, and many of them participated in Laboratory events. One freshman, Donald Shepard, decided to overhaul the interpolation in SYMAP, resulting in his famous article from 1968.[2]
Shepard’s algorithm was also influenced by the theoretical approach of William Warntz and others at the Lab who worked with spatial analysis. He conducted a number of experiments with the exponent of distance, deciding on something closer to the gravity model (exponent of -2). Shepard implemented not just basic inverse distance weighting, but also he allowed barriers (permeable and absolute) to interpolation.
Other research centers were working on interpolation at this time, particularly University of Kansas and their SURFACE II program. Still, the features of SYMAP were state-of-the-art, even though programmed by an undergraduate.
Basic form
A general form of finding an interpolated value u{displaystyle u} at a given point x{displaystyle x} based on samples ui=u(xi){displaystyle u_{i}=u(x_{i})} for i=1,2,...,N{displaystyle i=1,2,...,N} using IDW is an interpolating function:
- u(x)={∑i=1Nwi(x)ui∑i=1Nwi(x),if d(x,xi)≠0 for all i,ui,if d(x,xi)=0 for some i,{displaystyle u(mathbf {x} )={begin{cases}{dfrac {sum _{i=1}^{N}{w_{i}(mathbf {x} )u_{i}}}{sum _{i=1}^{N}{w_{i}(mathbf {x} )}}},&{text{if }}d(mathbf {x} ,mathbf {x} _{i})neq 0{text{ for all }}i,\u_{i},&{text{if }}d(mathbf {x} ,mathbf {x} _{i})=0{text{ for some }}i,end{cases}}}
where
- wi(x)=1d(x,xi)p{displaystyle w_{i}(mathbf {x} )={frac {1}{d(mathbf {x} ,mathbf {x} _{i})^{p}}}}
is a simple IDW weighting function, as defined by Shepard,[2]x denotes an interpolated (arbitrary) point, xi is an interpolating (known) point, d{displaystyle d} is a given distance (metric operator) from the known point xi to the unknown point x, N is the total number of known points used in interpolation and p{displaystyle p} is a positive real number, called the power parameter.
Here weight decreases as distance increases from the interpolated points. Greater values of p{displaystyle p} assign greater influence to values closest to the interpolated point, with the result turning into a mosaic of tiles (a Voronoi diagram) with nearly constant interpolated value for large values of p. For two dimensions, power parameters p≤2{displaystyle pleq 2} cause the interpolated values to be dominated by points far away, since with a density ρ{displaystyle rho } of data points and neighboring points between distances r0{displaystyle r_{0}} to R{displaystyle R}, the summed weight is approximately
- ∑jwj≈∫r0R2πrρdrrp=2πρ∫r0Rr1−pdr,{displaystyle sum _{j}w_{j}approx int _{r_{0}}^{R}{frac {2pi rrho ,dr}{r^{p}}}=2pi rho int _{r_{0}}^{R}r^{1-p},dr,}
which diverges for R→∞{displaystyle Rrightarrow infty } and p≤2{displaystyle pleq 2}. For N dimensions, the same argument holds for p≤N{displaystyle pleq N}. For the choice of value for p, one can consider the degree of smoothing desired in the interpolation, the density and distribution of samples being interpolated, and the maximum distance over which an individual sample is allowed to influence the surrounding ones.
Shepard's method is a consequence of minimization of a functional related to a measure of deviations between tuples of interpolating points {x, u} and i tuples of interpolated points {xi, ui}, defined as:
- ϕ(x,u)=(∑i=0N(u−ui)2d(x,xi)p)1p,{displaystyle phi (mathbf {x} ,u)=left(sum _{i=0}^{N}{frac {(u-u_{i})^{2}}{d(mathbf {x} ,mathbf {x} _{i})^{p}}}right)^{frac {1}{p}},}
derived from the minimizing condition:
- ∂ϕ(x,u)∂u=0.{displaystyle {frac {partial phi (mathbf {x} ,u)}{partial u}}=0.}
The method can easily be extended to other dimensional spaces and it is in fact a generalization of Lagrange
approximation into a multidimensional spaces. A modified version of the algorithm designed for trivariate interpolation was developed by Robert J. Renka and is available in Netlib as algorithm 661 in the toms library.
Example in 1 dimension
Łukaszyk–Karmowski metric
Yet another modification of the Shepard's method was proposed by Łukaszyk[3] also in applications to experimental mechanics. The proposed weighting function had the form
- wk(x)=1(D∗∗(x,xk))12,{displaystyle w_{k}(mathbf {x} )={frac {1}{(D_{**}(mathbf {x} ,mathbf {x} _{k}))^{frac {1}{2}}}},}
where D∗∗(x,xk){displaystyle D_{**}(mathbf {x} ,mathbf {x} _{k})} is the Łukaszyk–Karmowski metric chosen also with regard to the statistical error probability distributions of measurement of the interpolated points.
Modified Shepard's method
Another modification of Shepard's method calculates interpolated value using only nearest neighbors within R-sphere (instead of full sample). Weights are slightly modified in this case:
- wk(x)=(max(0,R−d(x,xk))Rd(x,xk))2.{displaystyle w_{k}(mathbf {x} )=left({frac {max(0,R-d(mathbf {x} ,mathbf {x} _{k}))}{Rd(mathbf {x} ,mathbf {x} _{k})}}right)^{2}.}
When combined with fast spatial search structure (like kd-tree), it becomes efficient N log N interpolation method suitable for large-scale problems.
References
^ Chrisman, Nicholas. "History of the Harvard Laboratory for Computer Graphics: a Poster Exhibit" (PDF)..mw-parser-output cite.citation{font-style:inherit}.mw-parser-output q{quotes:"""""""'""'"}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-limited a,.mw-parser-output .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}
^ ab Shepard, Donald (1968). "A two-dimensional interpolation function for irregularly-spaced data". Proceedings of the 1968 ACM National Conference. pp. 517–524. doi:10.1145/800186.810616.
^ Łukaszyk S. "A new concept of probability metric and its applications in approximation of scattered data sets". Computational Mechanics. 33 (4): 299–304. doi:10.1007/s00466-003-0532-2.
See also
- Multivariate interpolation
- Kernel density estimation