A Method For Approximating Missing Data in Spatial Patterns

J. C. Sprott
Department of Physics, University of Wisconsin, 1150 University Avenue, Madison, WI 53706, USA


ABSTRACT

Spatial patterns such as historical landscape records or digital photographs are often plagued by large numbers of missing or otherwise corrupted data points or pixels that cannot be easily reproduced. A method is described in which a simple stochastic cellular automaton is used to produce fictitious fractal data at arbitrarily many spatial points such that the resulting pattern mimics the morphological features of the actual pattern. The method is simple to implement, preserves all the existing data, has no adjustable parameters, and can be used to fill in regions of arbitrary size and shape, even outside the region for which data are available. Furthermore, it reduces to more conventional interpolation methods when only a few isolated data points are missing.

Ref: J. C. Sprott, Comput. & Graphics 28, 113-117 (2004)

The complete paper is available in PDF format.

Return to Sprott's Books and Publications.

Fig. 1. Hypothetical two-component landscape on a 208 x 208 grid producted by a stochastic cellular automaton after 1000 iterations with random initial conditions. When a 60 x 60 block of data is removed from the center, the plausibly realistic image on the right is generated after 5000 iterations of a stochastic cellular automaton with replacements chosen randomly from an eight-cell neighborhood.
[Figure 1]

Fig. 2. Cluster probability produced by a two-component cellular automaton with replacements chosen randomly from different neighborhood sizes.
[Figure 2]

Fig. 3. The fraction of correctly identified cells in Fig. 1 is about 70% at the boundary and smoothly degrades to about 50% as the boundary recedes.
[Figure 3]

Fig. 4. The eight-level satellite data on a 548 x 548 grid of leaf area index over the Eastern United States on the left (courtesy of Steven Running, MODIS Land Group Member, University of Montana) is assumed to have a 160 x 160 block of data missing from the center and is reconstructed with 1000 iterations of a stochastic cellular automaton, producing the image on the right.
[Figure 3]

Fig. 5. The 256-color dithered image of a cat on the left is assumed to have 400 random blocks of 10 x 10 pixels removed and then replaced after 1000 iterations of a stochastic cellular automaton, producing the image on the right.
[Figure 3]

Fig. 6. The 256-color dithered image of the Matterhorn on the left is assumed to have 25%, 50%, and 75% of the pixels removed in random blocks of 10 x 10 pixels and then replaced after 1000 iterations of a stochastic cellular automaton, producing the images on the right.
[Figure 3]